myers-batch

Coverage Types SIMD Python

Batched infix edit distance for DNA. Bit-parallel Myers on aarch64 NEON and x86-64 AVX2, runtime-dispatched, 7.5-10x faster than edlib single-threaded on the reference machine, with bit-identical results.

Adapter trimming, primer matching, barcode and UMI demultiplexing, and probe search all reduce to the same question asked hundreds of millions of times: what is the minimum edit distance between this short query and any substring of this read? edlib is the standard answer and is excellent, but it exposes one alignment per call and its inner loop is scalar 64-bit — there are no SIMD intrinsics anywhere in its 1482 lines. This library keeps edlib's algorithm and semantics, and changes the two things that were leaving performance on the floor: it takes the whole batch in one call, and it runs eight alignments per inner iteration.

Install

python -m pip install myers-batch

For editable development:

python -m pip install -e ".[dev]"

Building needs a C compiler; there are no runtime dependencies.

Quickstart

>>> import myers_batch
>>> myers_batch.distances(b"ACGTACGT", [b"TTACGTACGTTT", b"TTTTTTTT"])
[0, 6]
>>> myers_batch.have_neon(), myers_batch.lanes()
(True, 8)

One query against many targets. The query must be 1-64 bp; targets are any length. distances releases the GIL, so you can shard a batch across a thread pool.

Benchmark

Reproduce with python bench/bench.py. It refuses to print timings unless every result matches edlib first. Numbers below are one run, typical of three consecutive runs: this kernel varies about 2% run to run, edlib about 5%, so treat the headline as 7.5-10x rather than any single decimal.

These timings were measured on an Apple M3 Max and exercise the NEON kernel. No x86-64 timing is quoted because none was measured; x86-64 CI establishes AVX2 activation and bit-identical correctness, not a performance claim.

machine : macOS-15.5-arm64-arm-64bit / arm64
python  : 3.11.12
kernel  : NEON=True lanes=8

=== TruSeq Read 1 adapter  (query 33bp, 200000 x 150bp reads) ===
  results identical to edlib on all 200000 reads: True
  edlib k=-1             374.48 ms     0.53M pairs/s
  edlib k=5              305.36 ms     0.65M pairs/s
  edlib k=2              306.57 ms     0.65M pairs/s
  myers-batch scalar     103.56 ms     1.93M pairs/s
  myers-batch NEON        37.57 ms     5.32M pairs/s
  speedup vs edlib unbounded :  9.97x
  speedup vs edlib k=5        :  8.13x
  speedup vs edlib k=2        :  8.16x
  of which: batch API + single-word path  3.62x, NEON vectorization  2.76x
  [8 threads, not part of the algorithmic claim]    23.82 ms     8.40M pairs/s   15.72x vs single-thread edlib

=== 16bp cell barcode  (query 16bp, 200000 x 150bp reads) ===
  results identical to edlib on all 200000 reads: True
  edlib k=-1             367.35 ms     0.54M pairs/s
  edlib k=3              304.24 ms     0.66M pairs/s
  edlib k=1              300.76 ms     0.66M pairs/s
  myers-batch scalar     104.35 ms     1.92M pairs/s
  myers-batch NEON        37.55 ms     5.33M pairs/s
  speedup vs edlib unbounded :  9.78x
  speedup vs edlib k=3        :  8.10x
  speedup vs edlib k=1        :  8.01x
  of which: batch API + single-word path  3.52x, NEON vectorization  2.78x

=== 64bp capture probe  (query 64bp, 100000 x 300bp reads) ===
  results identical to edlib on all 100000 reads: True
  edlib k=-1             279.72 ms     0.36M pairs/s
  edlib k=8              241.69 ms     0.41M pairs/s
  myers-batch scalar     105.14 ms     0.95M pairs/s
  myers-batch NEON        37.28 ms     2.68M pairs/s
  speedup vs edlib unbounded :  7.50x
  speedup vs edlib k=8        :  6.48x
  of which: batch API + single-word path  2.66x, NEON vectorization  2.82x

Read the decomposition line, not just the headline. Roughly 2.7-3.6x comes from taking the batch in one call and specializing the single-word case, and a further 2.8x from the vectorization. Both are real, but they are different kinds of win, and attributing all of it to SIMD would be misleading.

The multi-threaded row is listed for completeness and is deliberately excluded from the claim: edlib is single-threaded by design, so comparing 8 threads against 1 measures the thread count, not the kernel.

How it works

flowchart LR; Q[query ≤64 bp] --> P[Peq table 256×u64]; T[targets, packed batch] --> G{group of 8}; P --> K; G --> K[8 lockstep Myers chains<br/>NEON 2×u64 ×4 / AVX2 4×u64 ×2]; K --> F[per-lane scalar finish]; F --> O[min infix distance per target]

The recurrence is Hyyro's formulation of Myers (1999), the same one edlib uses. Per target character, with VP/VN the vertical delta bitvectors:

Xv = Eq | VN
Xh = (((Eq & VP) + VP) ^ VP) | Eq
Ph = VN | ~(Xh | VP)
Mh = VP & Xh
score += (Ph >> (m-1)) & 1 ;  score -= (Mh >> (m-1)) & 1
VP = (Mh << 1) | ~(Xv | (Ph << 1))
VN = (Ph << 1) & Xv

Three properties make it vectorize cleanly:

The score updates are branch-free. Ph and Mh are provably disjoint: Mh is a subset of VP, and Ph & VP == 0 because VP & VN == 0. So both updates apply unconditionally instead of as an if/else if, which is what lets lanes proceed in lockstep.
Every operation is per-lane 64-bit. AND, OR, XOR, NOT, ADD, SHIFT. The carry in (Eq & VP) + VP propagates upward within a lane and never crosses lanes. NEON therefore uses four independent chains of two 64-bit lanes; AVX2 uses two independent chains of four lanes. Both advance eight targets per iteration without cross-lane shuffles.
The loop is latency-bound, not throughput-bound. The add feeds the xor feeds the or feeds the next iteration. The independent chains let the scheduler overlap that latency. On the reference M3 Max, two NEON lanes measured only 1.26x over scalar; four lanes across two chains gave 2.35x, and eight lanes across four chains gave 3.61x, using 16 of 32 vector registers with no spills.

Infix semantics come from the horizontal carry into the shift being zero, mirroring edlib's calculateBlock with hin == 0. A carry of one would give global (NW) distance instead.

The C API retains the scalar and NEON widths for differential measurement. The public hw_batch dispatcher selects NEON at compile time on aarch64, checks __builtin_cpu_supports("avx2") at runtime on x86-64, and otherwise selects the portable scalar kernel. The AVX2 functions carry a per-function target("avx2") attribute, so wheels remain portable and AVX2 instructions are isolated from the fallback path. Python exposes the dispatcher as distances, the portable path as distances_scalar, and the active selection as simd_backend.

Correctness

The claim is bit-identical output, so that is what the tests check, against two independent oracles:

a pure-Python O(nm) dynamic-programming reference, which keeps the suite self-contained
edlib itself, differentially, over randomized queries, target lengths and planted approximate occurrences

Batch sizes 1-17 plus 63/64/65 are all exercised, so every possible scalar remainder after the 8-wide blocks is covered, and ragged target lengths are tested explicitly because that is where lanes finish at different times and the per-lane scalar tail has to take over. CI requires the NEON backend on aarch64 and AVX2 on hosted x86-64, then checks both against edlib and the scalar implementation for bit-identical output.

The CI 100% coverage gate measures the Python API and dispatcher only; it does not claim C line coverage for the compiled kernel. Native-kernel correctness is instead checked differentially against edlib across randomized and structured inputs, in addition to the independent dynamic-programming oracle.

Limitations

Query length 1-64 bp. One bitvector word. Longer queries need Hyyro's multi-word blocks, which are not implemented. This covers adapters, primers, barcodes, UMIs and probes; it does not cover read-to-read alignment.
Infix distance only. No global (NW) or prefix (SHW) mode.
Distance only. No CIGAR, no alignment path, no match location. If you need those, use edlib.
No Ukkonen banding. edlib can early-terminate under a k cutoff; this kernel always scans the full target. It still wins at the cutoffs benchmarked above, but for very long targets with a very small k that advantage will narrow and could reverse.
Two SIMD ISAs, no generic-vector fallback. aarch64 uses NEON and supported x86-64 CPUs use AVX2; other CPUs use the portable scalar kernel. The AVX2 path is activated and compared against edlib on x86-64 CI, but no x86 speed claim is made because none was benchmarked.

Non-goals

Not a general alignment library, not a replacement for edlib's full feature set, and not a scoring-matrix aligner. It does one kernel on two ISAs (NEON, AVX2), faster.

License

MIT.

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

myers_batch-1.0.0.tar.gz (21.1 kB view details)

Uploaded Aug 13, 2026 Source

Built Distributions

If you're not sure about the file name format, learn more about wheel file names.

The dropdown lists show the available interpreters, ABIs, and platforms. Enable javascript to be able to filter the list of wheel files.

myers_batch-1.0.0-cp313-cp313-musllinux_1_2_x86_64.whl (46.8 kB view details)

Uploaded Aug 13, 2026 CPython 3.13musllinux: musl 1.2+ x86-64

myers_batch-1.0.0-cp313-cp313-musllinux_1_2_aarch64.whl (56.0 kB view details)

Uploaded Aug 13, 2026 CPython 3.13musllinux: musl 1.2+ ARM64

myers_batch-1.0.0-cp313-cp313-manylinux2014_aarch64.manylinux_2_17_aarch64.manylinux_2_28_aarch64.whl (57.7 kB view details)

Uploaded Aug 13, 2026 CPython 3.13manylinux: glibc 2.17+ ARM64manylinux: glibc 2.28+ ARM64

myers_batch-1.0.0-cp313-cp313-manylinux1_x86_64.manylinux_2_28_x86_64.manylinux_2_5_x86_64.whl (46.9 kB view details)

Uploaded Aug 13, 2026 CPython 3.13manylinux: glibc 2.28+ x86-64manylinux: glibc 2.5+ x86-64

myers_batch-1.0.0-cp313-cp313-macosx_11_0_arm64.whl (22.7 kB view details)

Uploaded Aug 13, 2026 CPython 3.13macOS 11.0+ ARM64

myers_batch-1.0.0-cp312-cp312-musllinux_1_2_x86_64.whl (46.7 kB view details)

Uploaded Aug 13, 2026 CPython 3.12musllinux: musl 1.2+ x86-64

myers_batch-1.0.0-cp312-cp312-musllinux_1_2_aarch64.whl (56.0 kB view details)

Uploaded Aug 13, 2026 CPython 3.12musllinux: musl 1.2+ ARM64

myers_batch-1.0.0-cp312-cp312-manylinux2014_aarch64.manylinux_2_17_aarch64.manylinux_2_28_aarch64.whl (57.6 kB view details)

Uploaded Aug 13, 2026 CPython 3.12manylinux: glibc 2.17+ ARM64manylinux: glibc 2.28+ ARM64

myers_batch-1.0.0-cp312-cp312-manylinux1_x86_64.manylinux_2_28_x86_64.manylinux_2_5_x86_64.whl (46.8 kB view details)

Uploaded Aug 13, 2026 CPython 3.12manylinux: glibc 2.28+ x86-64manylinux: glibc 2.5+ x86-64

myers_batch-1.0.0-cp312-cp312-macosx_11_0_arm64.whl (22.8 kB view details)

Uploaded Aug 13, 2026 CPython 3.12macOS 11.0+ ARM64

myers_batch-1.0.0-cp311-cp311-musllinux_1_2_x86_64.whl (46.6 kB view details)

Uploaded Aug 13, 2026 CPython 3.11musllinux: musl 1.2+ x86-64

myers_batch-1.0.0-cp311-cp311-musllinux_1_2_aarch64.whl (56.0 kB view details)

Uploaded Aug 13, 2026 CPython 3.11musllinux: musl 1.2+ ARM64

myers_batch-1.0.0-cp311-cp311-manylinux2014_aarch64.manylinux_2_17_aarch64.manylinux_2_28_aarch64.whl (57.6 kB view details)

Uploaded Aug 13, 2026 CPython 3.11manylinux: glibc 2.17+ ARM64manylinux: glibc 2.28+ ARM64

myers_batch-1.0.0-cp311-cp311-manylinux1_x86_64.manylinux_2_28_x86_64.manylinux_2_5_x86_64.whl (46.8 kB view details)

Uploaded Aug 13, 2026 CPython 3.11manylinux: glibc 2.28+ x86-64manylinux: glibc 2.5+ x86-64

myers_batch-1.0.0-cp311-cp311-macosx_11_0_arm64.whl (22.7 kB view details)

Uploaded Aug 13, 2026 CPython 3.11macOS 11.0+ ARM64

myers_batch-1.0.0-cp39-cp39-musllinux_1_2_x86_64.whl (45.2 kB view details)

Uploaded Aug 13, 2026 CPython 3.9musllinux: musl 1.2+ x86-64

myers_batch-1.0.0-cp39-cp39-musllinux_1_2_aarch64.whl (54.4 kB view details)

Uploaded Aug 13, 2026 CPython 3.9musllinux: musl 1.2+ ARM64

myers_batch-1.0.0-cp39-cp39-manylinux2014_aarch64.manylinux_2_17_aarch64.manylinux_2_28_aarch64.whl (56.0 kB view details)

Uploaded Aug 13, 2026 CPython 3.9manylinux: glibc 2.17+ ARM64manylinux: glibc 2.28+ ARM64

myers_batch-1.0.0-cp39-cp39-manylinux1_x86_64.manylinux_2_28_x86_64.manylinux_2_5_x86_64.whl (45.3 kB view details)

Uploaded Aug 13, 2026 CPython 3.9manylinux: glibc 2.28+ x86-64manylinux: glibc 2.5+ x86-64

myers_batch-1.0.0-cp39-cp39-macosx_11_0_arm64.whl (22.7 kB view details)

Uploaded Aug 13, 2026 CPython 3.9macOS 11.0+ ARM64

File details

Details for the file myers_batch-1.0.0.tar.gz.

File metadata

Download URL: myers_batch-1.0.0.tar.gz
Upload date: Aug 13, 2026
Size: 21.1 kB
Tags: Source
Uploaded using Trusted Publishing? Yes
Uploaded via: twine/7.0.0 CPython/3.13.14

File hashes

Hashes for myers_batch-1.0.0.tar.gz
Algorithm	Hash digest
SHA256	`5fd0b80c08ea2a6672b272818bb58a5816265f1376a9b6ebef1f8337855e545d`
MD5	`63f9927d7220f55fb2e837cd703b9436`
BLAKE2b-256	`62b5369559290d48a323ac8c6324354b8bf90b660aa836679b4f007a6db2a44b`

Algorithm	Hash digest
SHA256	`b3fc6f66f05a20e7df1c24de8fdce6e31382f31677920772433490567c524ab6`
MD5	`56234cd51592a8bcf913f80917deb605`
BLAKE2b-256	`395cca7840f9b82a6fc4eceaf8005c3b6cae2c594ac3e0e6aba533a1bb6422bc`

Algorithm	Hash digest
SHA256	`bd56b8c66773960bea8fbf76089a40f40a5419f0ed3f318c8db3c84fff7cb046`
MD5	`d104538f115fad99652fc8657c35287b`
BLAKE2b-256	`d957aeb78618f0847dab0b0927edbd6f325670a693145ed6bd7cae5e6e24b2d7`

Algorithm	Hash digest
SHA256	`eb216c5ca5baf5032ed354d1eb802500d94370399d9301525cf6e72e240fa4a7`
MD5	`9d1ce8c3ef1048108de1d5127a065c28`
BLAKE2b-256	`685b712ad017fbcc0dcfef1f74e6cb305d486dbb28b422ffd77c8849ba8d8b49`

Algorithm	Hash digest
SHA256	`a884682a799945ab7c2779f81229d4e108765526856056725887511f10916f23`
MD5	`cfa347b197abd3c60b1611a37d1e7278`
BLAKE2b-256	`c4b9635a61fc384f210404d0953223cb2dcd8e9ced849ace9756522f9293683b`

Algorithm	Hash digest
SHA256	`5f75f98abebebeb001c97ab20c6cb9c3f1b1db224678e2e252324562ddd20ed9`
MD5	`b91a0da762c10b0516ad317db68ae30e`
BLAKE2b-256	`d60267bd2564449d03935a46689790b4fa27cd30e9588a7d58a310260cc80810`

Algorithm	Hash digest
SHA256	`3e2621f9caafd0a04f33454fdb4e0468eee8aa192b41f123ef0ecc66a36f2cf7`
MD5	`822cadea215c140e3a58e19711735fca`
BLAKE2b-256	`967149d4b713a9337175851e4f25f0eb4caab86c44a2d4fadd28bd8e8029ad94`

Algorithm	Hash digest
SHA256	`4894e58ef82497596900010ccead119ca8b38ddbdaf75754bb9d99f1c543cd67`
MD5	`8d0c64aa0c04a960b6c61dfac2f5a1c6`
BLAKE2b-256	`2fb4c3339422e1d8965427126490701d632da6faaaf1bff93f3db0c5404c9f68`

Algorithm	Hash digest
SHA256	`11f5835bb2868697e794a0f9532a45cd9d6080f0d6e48ca00812336e4ceef980`
MD5	`4000b67e78384d944e6c7431d6f20800`
BLAKE2b-256	`354640820ffe6f54ad4ec1c98260454f6f5dc380ab8192fd1883708159fd9038`

Algorithm	Hash digest
SHA256	`f30e1b7c9d7c34b51a9ada033b03f84ae54b2f0a1e61881a3700e3a8f0276f2e`
MD5	`b64aa07ab55118dc9cac2cfaafe31440`
BLAKE2b-256	`1ae5dbb262bebdf6c951ea766a4d9cb034fca5294091b40823fb829aff9afd10`

Algorithm	Hash digest
SHA256	`f059066a3debad86f3f9a04c184600e58cc0c4e03a4137d36d77ee023101e612`
MD5	`5b8871b3fbf11578d4408dbc2510fedd`
BLAKE2b-256	`9b55275cd8bf6dd2b59f2dba9e1bc6bc4fa63ab0adf241d81913d001d15d21d9`

Algorithm	Hash digest
SHA256	`3b629c2dcac37046b05ca372d29d0de286f0c488d849ffe9512e634b8f776fe2`
MD5	`b2edeac9c5ca367d40e8182b24bd9615`
BLAKE2b-256	`3d4f1d5bfb80b1336ac243f4101ba86ccf640cd744b9e191ebac5a1a88abf689`

Algorithm	Hash digest
SHA256	`5409ff783e41e14314ec192756141f5b42b9f1cc514942a2dc1b5fe1359a10da`
MD5	`370fc9b7c03c43508404934cf7d81fe6`
BLAKE2b-256	`632e5bed73a7dea97564f69ecce056c44a148c7c8f5d65f91efd53ab064b5939`

Algorithm	Hash digest
SHA256	`82290d5a1039e5ef9fef4fff72886b5e2d8f63385bfe3c8e123ab0edd92e16f2`
MD5	`747fa9a6e024c77723eb2fa833ceede5`
BLAKE2b-256	`6887778e0ce9ebdb9bbfef845c2cb52466ae14e3c39ad0b052dbe57bbea84c0b`

Algorithm	Hash digest
SHA256	`b459b6a3675b7d5429cbc0c25625ee1979233947372a231bf27af48e985554bf`
MD5	`16a75289c439f092b0492e41066009ee`
BLAKE2b-256	`f9736bee7a4bd8809c364220e0ce401669ccfccf860003feeec97e9652039e43`

Algorithm	Hash digest
SHA256	`808d72de982c682fe4bb865fd2c184bebd7c985f7b9b0e93c9ab189c3e27552a`
MD5	`37b5d50631774fcf94feb103ea4fee6c`
BLAKE2b-256	`30363f6ecddfb8ed2aa75d1835e9368178ffe6953dab9c77885698e2f173344c`

Algorithm	Hash digest
SHA256	`14763ce018b5ddd5ea22957013aaa2109b793298333404b78ddd39e5d1e4bbe8`
MD5	`23bc7e4028ee22b34afecff494792d0b`
BLAKE2b-256	`078ca46200efc473365694b8a96c19729bb9396f4d25da1b6bc70c3cd18e3a46`

Algorithm	Hash digest
SHA256	`3f485df60edbc04aef1b8e15e550f6c6f9255283db092ca674481475c0672444`
MD5	`c60f3883aa14814a7ab98180556302c0`
BLAKE2b-256	`387784a5c425ef4e2a5b1ab228c108cf18bc4e31a1a3b61c89fb60ad9cdea618`

Algorithm	Hash digest
SHA256	`512733737aac8389ada6e35f19e72e9fc8ae222d6f6a0f2e70e26ca6165bc60c`
MD5	`21fa874e10cb25f728fd96bb6a471874`
BLAKE2b-256	`aa5602937c3dcec1cea1666ca4bf1e82841dd0ea2d5264672417d17820987e70`

Algorithm	Hash digest
SHA256	`1e816f0a1faae687d3b37384e188b56e9bd833237c2b450f00ccde417d39c108`
MD5	`3e24bb76e1944c78849ffa19184d9de6`
BLAKE2b-256	`a6a1d2112fefecfff933bc50335a6e125ca7e28c02077ee37e2d25aed4c10f8a`

Algorithm	Hash digest
SHA256	`8a3bd70719cf155f4a85121d81f71820f0e6a2f1105378e51240cb9297494e93`
MD5	`ca787fb13662627739f72e9ddc16020a`
BLAKE2b-256	`ececf23ed79418f65b4e14ce7e64fa70dde2a511368f1aec175f1cab39f44153`

myers-batch 1.0.0

myers-batch

Install

Quickstart

Benchmark

How it works

Correctness

Limitations

Non-goals

License

Project links

Key dates

1 maintainer

Credits

GitHub Statistics

License expression

Requires

Provides Extra

Tags

Classifiers

Download files

Source Distribution

Built Distributions

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details

File metadata

File hashes

Provenance

File details