4 ms·
SimSIMD: Hardware-accelerated similarity metrics and distance functions
- muzamil2002 3y ago[dead]
- ttul 3y agoThis is the kind of basement sorcery that makes the world go round. Nicely done.
- turnsout 3y agoAre vector databases like Chroma already doing some of this? If not, it could be a huge win for RAG workflows!
- ashvardanian 3y agoSimSIMD is already used in USearch, ClickHouse, and Lantern. In other solutions SIMD is generally limited to pre-2015 Assembly instructions. So yes, there a lot of RAG workflows to accelerate :)
- behnamoh 3y agothe sad part is that they are the ones ripping the benefits of this tech by capturing that sweet VC money
- teaearlgraycold 3y agoI’m curious if pgvector is using it. It’s actually pretty fast for us without even indexing.
- sakras 3y agoAs far as I'm aware pg_vector just uses the compiler's autovectorization on float32. I think specifically for Euclidean distance you won't really beat GCC (the README even admits it: "GCC handles single-precision float but might not be the best choice for int8 and _Float16 arrays, which has been part of the C language since 2011.")
- ashvardanian 3y agoYes, the improvements for float32 aren't very dramatic, but it can be 3x NumPy/SciPy: https://ashvardanian.com/posts/simsimd-faster-scipy/ https://ashvardanian.com/posts/simsimd-faster-scipy/ C11 is also a bit tricky, as its support is optional, as far as I remember.
- sakras 3y agoI also notice you use FMA in your AVX2 L2 distance calculation. I don't think pg_vector enables that, so SimSIMD might be slightly faster. Also interesting that it beats NumPy/SciPy by so much! I wonder what they're doing..
- menaerus 3y agoNot using SIMD at all as it seems. Thus relying on auto-vectorization of I'm not reading it indirectly. https://github.com/scipy/scipy/blob/main/scipy/spatial/src/distance_impl.h https://github.com/scipy/scipy/blob/main/scipy/spatial/src/d...
- teaearlgraycold 3y agoIt doesn’t support f16 or i8 at all yet (at least not in the released version).
- sroussey 3y agoI’m using this and became a contributor this year (prebuilt binaries for nodejs and bun, as well as some ts/js mangling). :)
- chaps 3y agoNice! Similarity searching is the bane of my existence, but also gives life to so many of the things I work on. 200x sounds wonderfully fast. Does this do levenshtein distance? Didn't see it in the main document. Edit: also, THANK YOU for adding a parameter to specify # of threads. Wish this was a wider standard practice.
- lifthrasiir 3y agoThe author is also responsible for the StringZilla library that includes levenstein distance: https://github.com/ashvardanian/StringZilla https://github.com/ashvardanian/StringZilla
- brrrrrm 3y agoOMP_NUM_THREADS=n is pretty standard in HPC workloads
- chaps 3y agoHuh, thanks. I'll check it out and see if I can drop that in.
- ashvardanian 3y agoHe-hey! For Levenshtein distance check out the development branch of StringZilla. Hopefully will release this week :) Oh, and for multithreading, USearch might be more practical.
- chaps 3y agoHeck yeah, thanks. If the first 4 bytes of the string are the same, the strings are likely to be equal. Similarly, the first 4 bytes of the strings can be used to determine their relative order most of the time. That's a fun heuristic.
- ashvardanian 3y agoYes, it was very practical in most cases, but v3 only uses it for short needles with SWAR. SIMD variants will use Raita-style heuristics.
- behnamoh 3y agoTangential: How do you guys decide which similarity metric to use? Euclidean seems the most intuitive but I'm sure others also have use cases. This situation is similar to the similarity metrics used to compare two distributions (KL for insurance, tho technically it's not a metric). Is there some art to it or is there really a systematic way to choose metrics for different tasks?
- ashvardanian 3y agoMy intuition: L2 in low dims, Cosine in high dims. Hamming on similar size sets, Jaccard on others. Jensen-Shannon (symmetric KL) when dealing with histograms and probability distribution.
- SubiculumCode 3y agoManhattan is better than L2 at high dimensions..but why cos?
- SubiculumCode 3y agohttps://stats.stackexchange.com/questions/341535/curse-of-dimensionality-does-cosine-similarity-work-better-and-if-so-why https://stats.stackexchange.com/questions/341535/curse-of-di...
- godelski 3y agoCosine similarity is certainly not immune to the curse of dimensionality. In fact, it is explicitly prone to it. As dimensions increase, the likelihood that any two tensors are orthogonal rapidly increases. This is easy to reason out if you start from 2 dimensions, count the number of orthogonal vectors, and then move to 3D, and so on.
- godelski 3y agoThis is actually a really underappreciated question! (and also really interesting!) There's a lot of nuance to this because the truth is that distance becomes less meaningful as you increase dimensions. You can find some papers comparing Lp distances with different p values (p=2 == Euclidean == L2). But as dimension increases, the distance to the furthest points decreases (making it harder to differentiate near points from far points). Cosine similarity is a commonly used one, but as dimensions increase the likelihood that any two tensors are orthogonal rapidly increases. This might seem counterintuitive because the probability is really low in 2 or 3 dims as you only have 2 or a plane in R3. So really the answer honestly tends to be ad hoc: "whatever works best". It's good to keep in mind that any intuition you have about geometry goes out the window as dimensions increase. It's always important to remember assumptions made, especially when focusing on empiricism. There are definitely some nuances that can point you in better directions (pun intended :) than random guessing, especially if you know a lot about your geometry, but it is messy and nuances can make big differences. I wish I had a better answer but I hope this is informative. Maybe some mathematician will show up and add more. I'm sure there's someone on HN that loves to talk about higher dimensional geometry and I'd love to hear those "rants."
- egorfine 3y agoI wonder how it compares to faiss in terms of performance on Intel CPUs
- ashvardanian 3y agoIf I remember correctly, for dot product it uses BLAS libraries and for Cosine distance and L2 have very minimal SIMD support. In both cases SimSIMD should be faster for distance computations. Multiply it by a more efficient HNSW implementation and you might be looking at a 100x performance difference on a scale of a billion vectors: https://www.unum.cloud/blog/2023-11-07-scaling-vector-search-with-intel https://www.unum.cloud/blog/2023-11-07-scaling-vector-search...
- egorfine 3y agoThanks for the link!
- dmezzetti 3y agoInteresting project. Would be nice to see how it compares to the built-in operations provided in Faiss. https://github.com/facebookresearch/faiss/wiki/How-to-make-Faiss-run-faster#avx-512-support https://github.com/facebookresearch/faiss/wiki/How-to-make-F...
- ashvardanian 3y agohttps://news.ycombinator.com/reply?id=39115268&goto=item%3Fid%3D39111114%2339115268 https://news.ycombinator.com/reply?id=39115268&goto=item%3Fi...
- dmezzetti 3y agoThinking more of a scientific comparison with metrics. Definitely looks interesting overall, appreciate you sharing this library as open source.
- ashvardanian 3y agoYou are welcome :) There are more materials in my blog, including 4 articles from October 2023: https://ashvardanian.com/archives/ https://ashvardanian.com/archives/ Benchmarks are quite easy to reproduce, especially in Python. The numbers for AWS Graviton 3, Apple M2 and Intel Sapphire Rapids CPUs can be found here: https://ashvardanian.com/posts/simsimd-faster-scipy/ https://ashvardanian.com/posts/simsimd-faster-scipy/
- dmezzetti 3y agoGreat, I'll take a look!
- CyberDildonics 3y agoIs this calling SIMD 'hardware acceleration' and is it claiming all its improvements to python?