Improve an algorithm performance step by step

1. RaBitQ

   1 2 124 5.2 C++

   [SIGMOD 2024] RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search

   

   Recently, I've been working on a new approximate nearest neighbor search algorithm called RaBitQ. The author has already provided a C++ implementation that runs quite fast. I tried to rewrite it in Rust (yet another RiiR). But I found that my implementation is much slower than the original one. Here is how I improve the performance step by step.

2. InfluxDB

   www.influxdata.com featured

   InfluxDB – Built for High-Performance Time Series Workloads. InfluxDB 3 OSS is now GA. Transform, enrich, and act on time series data directly in the database. Automate critical tasks and eliminate the need to move data externally. Download now.

   

3. rabitq

   2 1 10 7.9 Rust

   rabitq rust implementation (by kemingy)

   

   Recently, I've been working on a new approximate nearest neighbor search algorithm called RaBitQ. The author has already provided a C++ implementation that runs quite fast. I tried to rewrite it in Rust (yet another RiiR). But I found that my implementation is much slower than the original one. Here is how I improve the performance step by step.

4. samply

   3 16 3,206 9.4 Rust

   Command-line sampling profiler for macOS, Linux, and Windows

   

   I use samply to profile the Rust code. It has a nice integration with the Firefox Profiler. You can also share the profiling results with others by uploading them to the cloud. Here is an example of the C++ version profiling on GIST. The FlameGraph and CallTree are the most common views. Remember to grant the performance event permission and increase the mlock limit:

5. profiler

   4 192 1,356 9.8 JavaScript

   Firefox Profiler — Web app for Firefox performance analysis

   

   I use samply to profile the Rust code. It has a nice integration with the Firefox Profiler. You can also share the profiling results with others by uploading them to the cloud. Here is an example of the C++ version profiling on GIST. The FlameGraph and CallTree are the most common views. Remember to grant the performance event permission and increase the mlock limit:

6. criterion.rs

   5 32 5,134 7.2 Rust

   Statistics-driven benchmarking library for Rust

   

   Criterion is a good statistics-driven benchmark tool. I create another repo to store all the related benchmark code. It turns out that I should put them in the same repo.

7. compiler-explorer

   6 218 17,745 9.9 TypeScript

   Run compilers interactively from your web browser and interact with the assembly

   

   The GodBolt compiler explorer is also useful for comparing the assembly function code between C++ and Rust.

8. rs_bench

   7 1 0 7.4 Rust

   

   Criterion is a good statistics-driven benchmark tool. I create another repo to store all the related benchmark code. It turns out that I should put them in the same repo.

9. Stream

   getstream.io featured

   Stream - Scalable APIs for Chat, Feeds, Moderation, & Video. Stream helps developers build engaging apps that scale to millions with performant and flexible Chat, Feeds, Moderation, and Video APIs and SDKs powered by a global edge network and enterprise-grade infrastructure.

   

10. client_rust

    8 3 556 6.6 Rust

    Prometheus / OpenMetrics client library in Rust

    

    Remember to add some metrics from the start. Many bugs and performance issues can be found by checking the metrics. I use AtomicU64 directly since the current requirements are simple. I may switch to the Prometheus metrics later.

11. hnswlib

    9 14 4,793 0.0 C++

    Header-only C++/python library for fast approximate nearest neighbors

    

    After the profiling, I found that it still has f32::clone(). By checking the source code of nalgebra, I found that there are many clone for some reasons I don't know. I decide to write the SIMD by hand. Fortunately, hnswlib (a popular HNSW implementation) already implements this.

12. faer-rs

    10 1 2,254 9.5 Rust

    Linear algebra foundation for the Rust programming language (by sarah-quinones)

    

    I found another Rust algebra crate called faer while investigating the f32::clone() problem. It's optimized with lots of SIMD and provides better row/column iteration performance. The QR decomposition is also much faster than nalgebra. This commit 0411821 makes the training part faster.

13. popcount

    11 1 9 - C++

    Fastest possible x86 implementation of popcount/population count/Hamming weight/counting set bits

    

    This is a good reference for the popcnt implementation with AVX2. The commit edabd4a re-implement this in Rust which improves the QPS by 11% for GIST.

14. bounds-check-cookbook

    12 2 113 - Rust

    Recipes for avoiding bounds checks in Rust, without unsafe!

    

    There is a bounds-check-cookbook which provides several examples of how to eliminate the boundary checking in safe Rust.

15. llvm-project

    13 424 33,434 10.0 LLVM

    The LLVM Project is a collection of modular and reusable compiler and toolchain technologies.

    

    I tried PGO and BOLT but didn't get any improvement.

16. jemallocator

    14 3 433 4.7 Rust

    Rust allocator using jemalloc as a backend (by tikv)

    

    Switching to jemalloc or mimalloc doesn't improve the performance either.

17. mimalloc

    15 39 11,712 9.6 C

    mimalloc is a compact general purpose allocator with excellent performance.

    

    Switching to jemalloc or mimalloc doesn't improve the performance either.

18. SaaSHub

    www.saashub.com featured

    SaaSHub - Software Alternatives and Reviews. SaaSHub helps you find the best software and product alternatives

    

Suggest a related project