Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Exact binary vector search for RAG in 100 lines of Julia

domluna.com

Post reply on HN
Print view View original

11–20 of 25 posts

Re: Exact binary vector search for RAG in 100 lines of Julia

#11

Post by lunaticd »

floobertoober wrote: post #5

I'm not sure what is meant by "exact" here - do they describe their binarisation process at all? This seems more like an XOR benchmark than a rag benchmark, no mention of recall or other relevant performance metrics

exact in this case means that all the vectors are compared against the query vector. Where as other search methods such as HNSW are approximate searches.

Re: Exact binary vector search for RAG in 100 lines of Julia

#12

Post by sitkack »

lunaticd wrote: post #10
mik1998 wrote: post #2

for 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 had Opus translate your code to Rust

    fn hamming_distance_u8(x1: u8, x2: u8) -> usize {
        (x1 ^ x2).count_ones() as usize
    }

Re: Exact binary vector search for RAG in 100 lines of Julia

#14

Post by lunaticd »

lunaticd wrote: post #10
mik1998 wrote: post #2

for 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.

julia> @code_typed hamming_distance(Int8(33), Int8(125)) CodeInfo( 1 ─ %1 = Base.xor_int(x1, x2)::Int8 │ %2 = Base.ctpop_int(%1)::Int8 │ %3 = Base.sext_int(Int64, %2)::Int64 │ nothing::Nothing └── return %3 ) => Int64

julia> @code_llvm hamming_distance(Int8(33), Int8(125)) ; Function Signature: hamming_distance(Int8, Int8) ; @ /Users/lunaticd/code/tiny-binary-rag/rag.jl:13 within `hamming_distance` define i64 @julia_hamming_distance_16366(i8 signext %"x1::Int8", i8 signext %"x2::Int8") #0 { top: ; @ /Users/lunaticd/code/tiny-binary-rag/rag.jl:14 within `hamming_distance` ; ┌ @ int.jl:373 within `xor` %0 = xor i8 %"x2::Int8", %"x1::Int8" ; └ ; ┌ @ int.jl:415 within `count_ones` %1 = call i8 @llvm.ctpop.i8(i8 %0) ; │┌ @ int.jl:549 within `rem` %2 = zext i8 %1 to i64 ; └└ ret i64 %2 }

it lowers to the machine instruction now.

I also tried 8 Int64s vs 64 Int8s and it doesn't seem to make a difference when doing the search.

EDIT: apologize for the formatting

Re: Exact binary vector search for RAG in 100 lines of Julia

#15

Post by lunaticd »

klowrey wrote: post #6

Why 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.

Re: Exact binary vector search for RAG in 100 lines of Julia

#16

Post by lunaticd »

miguelraz wrote: post #13

Dom! 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!

Re: Exact binary vector search for RAG in 100 lines of Julia

#19

Post by Joel_Mckay »

lunaticd wrote: post #16
miguelraz wrote: post #13

Dom! 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!

And this right here is why the Julia crowd is awesome...

A great article inspires everyone to participate in the fun.

Cheers =3

Post reply on HN