8000 perf: right-size radix-sort key widths (coordinate & chain-score sorts) by nh13 · Pull Request #46 · nh13/minibwa · GitHub
[go: up one dir, main page]
Skip to content

perf: right-size radix-sort key widths (coordinate & chain-score sorts) #46

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Draft
nh13 wants to merge 1 commit into
base: master
Choose a base branch
< 8000 /div>
from
Draft

perf: right-size radix-sort key widths (coordinate & chain-score sorts) #46

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
4 changes: 2 additions & 2 deletions lchain.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -54,7 +54,7 @@ static uint64_t *mb_chain_backtrack(void *km, int64_t n, const int32_t *f, const
z = Kmalloc(km, mb128_t, n_z);
for (i = 0, k = 0; i < n; ++i) // populate z[]
if (f[i] >= min_sc) z[k].x = f[i], z[k++].y = i;
radix_sort_mb128x(z, z + n_z);
radix_sort_mb128x_b4(z, z + n_z);

memset(t, 0, n * 4);
for (k = n_z - 1, n_v = n_u = 0; k >= 0; --k) { // precompute n_u
Expand Down Expand Up @@ -115,7 +115,7 @@ static mb_anchor_t *compact_a(void *km, const l2b_t *l2b, int32_t n_u, uint64_t
w[i].y = (uint64_t)k<<32 | i;
k += (int32_t)u[i];
}
radix_sort_mb128x(w, w + n_u);
radix_sort_mb128x_b5(w, w + n_u);
u2 = Kmalloc(km, uint64_t, n_u);
for (i = k = 0; i < n_u; ++i) {
int32_t j = (int32_t)w[i].y, n = (int32_t)u[j];
Expand Down
8 changes: 8 additions & 0 deletions map-algo.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -8,6 +8,14 @@

#define key_128x(a) ((a).x)
KRADIX_SORT_INIT(mb128x, mb128_t, key_128x, 8)
// Narrowed key-width variants for radix_sort. The klib radix does one 8-bit pass
// per key byte, so declaring the true key width skips passes over always-zero high
// bytes. Both bounds below are structural, not workload-dependent:
// _b5: keys that are concatenated-reference coordinates, bounded by the index
// length (< 2^40, i.e. references up to ~1 Tbp).
// _b4: keys that are a non-negative int32 chain score stored in a uint64 (< 2^32).
KRADIX_SORT_INIT(mb128x_b5, mb128_t, key_128x, 5)
KRADIX_SORT_INIT(mb128x_b4, mb128_t, key_128x, 4)

#define key_64(a) (a)
KRADIX_SORT_INIT(mb64, uint64_t, key_64, 8)
Expand Down
2 changes: 2 additions & 0 deletions mbpriv.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -81,6 +81,8 @@ mb_hit_t *mb_map_sai(const mb_opt_t *opt, const mb_idx_t *idx, int64_t qlen, con

void radix_sort_mb64(uint64_t *st, uint64_t *en);
void radix_sort_mb128x(mb128_t *st, mb128_t *en);
void radix_sort_mb128x_b5(mb128_t *st, mb128_t *en); // 5-byte key: reference coordinate
void radix_sort_mb128x_b4(mb128_t *st, mb128_t *en); // 4-byte key: int32 chain score

// in cs.c
void mb_write_cs_ds(void *km, kstring_t *s, const uint8_t *tseq, const uint8_t *qseq, const mb_hit_t *r, int is_ds);
Expand Down
2 changes: 1 addition & 1 deletion pe.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -159,7 +159,7 @@ static void mb_pair_hits(void *km, const mb_opt_t *opt, const l2b_t *l2b, int32_
p->y = (uint64_t)i << 2 | (uint64_t)h->rev << 1 | r;
}
}
radix_sort_mb128x(pa, pa + n_pa);
radix_sort_mb128x_b5(pa, pa + n_pa);

y[0] = y[1] = y[2] = y[3] = -1;
for (i = 0; i < n_pa; ++i) {
Expand Down
6 changes: 4 additions & 2 deletions seed.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -6,7 +6,8 @@
#include "ksort.h"

#define key_sai0(a) ((a).x[0])
KRADIX_SORT_INIT(mb_sai0, mb_sai_t, key_sai0, 8)
// key_sai0 is an SA/BWT coordinate, bounded by the index length (< 2^40); 5 bytes suffice.
KRADIX_SORT_INIT(mb_sai0, mb_sai_t, key_sai0, 5)

#define key_sais(a) ((a).size)
KRADIX_SORT_INIT(mb_sais, mb_sai_t, key_sais, 8)
Expand All @@ -15,7 +16,8 @@ KRADIX_SORT_INIT(mb_sais, mb_sai_t, key_sais, 8)
KRADIX_SORT_INIT(mb_saii, mb_sai_t, key_saii, 8)

#define key_anchor(a) ((a).tpos)
KRADIX_SORT_INIT(mb_anchor, mb_anchor_t, key_anchor, 8)
// key_anchor is a concatenated-reference coordinate, bounded by the index length (< 2^40); 5 bytes suffice.
KRADIX_SORT_INIT(mb_anchor, mb_anchor_t, key_anchor, 5)

/***********
* Seeding *
Expand Down
0