I used ```hamming_bitwise(x::Union{UInt, UInt128, BigInt}, y::Union{UInt, UInt128, BigInt}) = count_ones(x ⊻ y)``` to get a fast hamming distance with "binary vectors" encoded as ints.
Exact binary vector search for RAG in 100 lines of Julia
21–25 of 25 posts
Re: Exact binary vector search for RAG in 100 lines of Julia
#22Why not use the built in BitVector type that has specialized code for things like xor? https://docs.julialang.org/en/v1/base/arrays/#Base.BitArray
it doesn't seem to have better support for things like xor and count_ones. I believe the main use case is comparisons.
Combined with broadcasting its fast.
Under the hood it’s doing the same thing with a vector of ints (64 bits for bitvectors) and all the bulk manipulation is handled that way so SIMD in inherent as well. Worth a shot.
Re: Exact binary vector search for RAG in 100 lines of Julia
#23for i in 0:7 c += (r >> i) & 1 end This is just popcnt, surely Julia has a built in for that.
author here. I thought there might be a machine instruction for this but wasn't sure, I also didn't know Julia had a count_ones that counted the 1s. Thanks! With this the timings are even faster. I'll update the post.
I think you may need to update the figures in the rest of the article. At some point you mention it should take around 128ns but with the new benchmark that's probably closer to 64*1.25=80ns.
Re: Exact binary vector search for RAG in 100 lines of Julia
#24Dom! Fellow Julian here! I loved this post hamming_distance(s1, s2) = mapreduce(!=, +, s1, s2) I'm a bit swamped at the moment but I'll a response article later - they're still some juicy perf on the table here. Thanks for the post, such a good showcase.
please make it even faster!
I wanted to get too fancy and I tried
* LoopVectorization.jl - @turbo choked on the loop
* a direct llvmcall to use AVX512 pop count - I malformed the types for the instruction
* Defining the `db` as
db = [rand(Int8) for _ in 1:64, j in 1:(10^6)];
to avoid the vec of vecs structure,
and then
function my_cluster!(db, query, k) db .= query .⊻ db popcounts = mapreduce(count_ones, +, db, dims = 1) results = reshape(popcounts, last(size(db))) partialsortperm!(results, results, k) @views results[begin:k] end
...which I couldn't get to be faster than your version. If you use the `partialsortperm!` and reuse the same cache array, I suspect you'll get good speedups, as you won't be sorting the array every time. This is a classic `nth_element` algorithm.
The above is not the most amazing code, but I suspect the lack of indexing will make it ridiculously friendly for a GPU (Edit: Nope, it chokes on `partialsortperm!`).
I'm guessing the manual loopy approach should be just as good but I battled hard to get it somewhat competitive here in 6 lines of code
#@be my_cluster!(X2, q1, 5) Benchmark: 3 samples with 1 evaluation 42.883 ms (17 allocs: 15.259 MiB) 45.711 ms (17 allocs: 15.259 MiB) 46.670 ms (17 allocs: 15.259 MiB)
#@be k_closest(X1, q1, 5) Benchmark: 4 samples with 1 evaluation 27.994 ms (2 allocs: 176 bytes) 28.733 ms (2 allocs: 176 bytes) 29.000 ms (2 allocs: 176 bytes) 30.709 ms (2 allocs: 176 bytes)
I also didn't try using `FixedSizedArrays.jl` as Mose Giordano recommended in my livestream chat.
Re: Exact binary vector search for RAG in 100 lines of Julia
#25Nice speed up! Have you tried to benchmark also this heap implementation? https://juliacollections.github.io/DataStructures.jl/latest/...
i did it does a ton of allocations, which is why i made a simple maxheap implementation and then sort the final result