Repository navigation
align: left extension reverses the query twice, then reverses it back #27
Description
On the left-extension path, align.c:643-644 reverses qseq and tseq in place, the kernel then reverses the query again into qr (ksw2_extz2_sse.c:90, ksw2_extd2_sse.c:120), and align.c:652 reverses qseq back:
mb_seq_rev(qs - qs0, qseq);
mb_seq_rev(ts - ts0, tseq);
mb_align_pair(…, KSW_EZ_EXTZ_ONLY|KSW_EZ_RIGHT|KSW_EZ_REV_CIGAR, ez);
…
mb_seq_rev(qs - qs0, qseq); // undoSince the kernel computes qr[t] = query[qlen-1-t], its qr for a left extension is exactly the original forward query slice — the caller's reversal and the kernel's reversal cancel. Three O(qlen) passes where one would do. Same shape at align.c:783-789 and pe.c:283-288.
Two smaller duplications on the same path: mb_align_pair's ungapped pre-pass already streams both sequences (align.c:338-342, 354-357) before the kernel re-copies them, and the Z-drop lift calls the kernel twice on identical input (align.c:690 then 693), rebuilding qr/sf both times.
To be clear about what is not wrong here: neither copy is removable in isolation. sf = memcpy(target, tlen) into the tlen_*16 slab exists so _mm_loadu_si128(&sf[t]) can over-read up to 15 bytes past tlen, and callers pass an unpadded Kmalloc'd tseq (align.c:638). qr gives the anti-diagonal walk (qrr = qr + (qlen-1-r)) contiguous access. The redundancy is at the caller/kernel boundary, not inside the kernel.
Expected impact
Negligible, and this is the measured one. In a sample profile (arm64, 8 threads, hg38), the qr/sf copy lines account for 0.04% of busy samples on HG002 HiFi 10k reads and 0.06% on HG002 WGS 1M pairs; mb_seq_rev never appears. Kernel setup as a whole (the kcalloc, the memsets, the H[] init) is ~10-20x larger than the copies and is the more interesting target if anyone wants to optimize per-call overhead. Filing this as a clarity issue with a measured "don't bother optimizing this" attached.
Activity