Ultra-fast binary similarity at CPU speed
We have binary embeddings — 128-bit vectors that encode semantic meaning. We need to compare millions of them quickly to find similar items (pheromones, memories, documents).
Load all embeddings into JavaScript, loop through each one, compute similarity. Slow at scale.
Let SQLite compute similarity inline using CPU bit operations. 100x faster!
Our embeddings are 128 bits (16 bytes). Each bit represents a semantic feature:
XNOR (Exclusive NOR) tells us which bits match between two embeddings:
| A | B | A XNOR B |
|---|---|---|
| 0 | 0 | 1 ✓ |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 ✓ |
POPCOUNT (Population Count) counts how many 1-bits are in a value:
This is a single CPU instruction on modern processors! (POPCNT on x86)
Instead of counting bits in a loop, we pre-compute all 256 possible byte values:
const POPCOUNT_TABLE = new Uint8Array(256);
for (let i = 0; i < 256; i++) {
let count = 0, n = i;
while (n) { count++; n &= n - 1; }
POPCOUNT_TABLE[i] = count;
}
// Now popcount is just a table lookup!
const bits = POPCOUNT_TABLE[0b11101110]; // → 6Everything operates on existing buffers. No new objects created, no garbage collection.
By embedding this in SQLite as a custom function, comparisons happen during query execution:
-- SQLite does the comparison, only returns matches
SELECT * FROM pheromones
WHERE hamming_similarity(embedding, ?) > 0.7
ORDER BY hamming_similarity(embedding, ?) DESC| Method | Speed | Memory | At 1M items |
|---|---|---|---|
| JavaScript loop | ~100K/sec | High (load all) | ~10 seconds |
| SQLite without XNOR | ~500K/sec | Medium | ~2 seconds |
| SQLite + XNOR+POPCOUNT | ~10M/sec | Low | ~100ms |
SQLite + XNOR+POPCOUNT
JavaScript Loop
// Popcount lookup table
const POPCOUNT_TABLE = new Uint8Array(256);
for (let i = 0; i < 256; i++) {
let count = 0, n = i;
while (n) { count++; n &= n - 1; }
POPCOUNT_TABLE[i] = count;
}
// Register with better-sqlite3
db.function('hamming_similarity', { deterministic: true }, (a, b) => {
if (!Buffer.isBuffer(a) || !Buffer.isBuffer(b)) return 0;
if (a.length !== b.length) return 0;
let matching = 0;
for (let i = 0; i < a.length; i++) {
// XNOR: ~(a XOR b) gives bits that match
const xnor = ~(a[i] ^ b[i]) & 0xFF;
// POPCOUNT via lookup table
matching += POPCOUNT_TABLE[xnor];
}
return matching / (a.length * 8);
});// Find similar pheromones
const results = db.prepare(`
SELECT *, hamming_similarity(embedding, ?) as sim
FROM pheromones
WHERE hamming_similarity(embedding, ?) > 0.65
ORDER BY sim DESC
LIMIT 20
`).all(queryEmbedding, queryEmbedding);Alpha, Beta, Gamma colonies use it to find similar pheromones for stigmergic coordination.
Searching through memory files and daily logs to find relevant context.
Checking if a question was asked before to avoid repetition.
Finding connections between document chunks for the ant colony intelligence.