hashtable-benchmarks
zig
hashtable-benchmarks | zig | |
---|---|---|
8 | 816 | |
29 | 30,773 | |
- | 2.7% | |
4.7 | 10.0 | |
5 months ago | 1 day ago | |
Java | Zig | |
Apache License 2.0 | MIT License |
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
hashtable-benchmarks
-
Building a faster hash table for high performance SQL joins
Since the blog post mentioned a PR to replace linear probing with Robin Hood, I just wanted to mention that I found bidirectional linear probing to outperform Robin Hood across the board in my Java integer set benchmarks:
https://github.com/senderista/hashtable-benchmarks/blob/mast...
https://github.com/senderista/hashtable-benchmarks/wiki/64-b...
-
Ask HN: Who wants to be hired? (December 2023)
https://homes.cs.washington.edu/~magda/papers/wang-cidr17.pd...
I'm most interested in developing high-performance database engines in low-level languages, but open to any challenging systems programming project. I've been working in C++ for the last 3 years, but have written nontrivial projects in Rust and Java as well (e.g., https://github.com/senderista/rotated-array-set, https://github.com/senderista/hashtable-benchmarks). I would enjoy using Rust or Zig on a new project, but I consider the project itself to be much more important than the language it's written in. I am not interested in cryptocurrency, adtech, or fintech projects.
-
Factor is faster than Zig
Thanks for the details on your benchmarks. I would like sometime to extend BLP to a more generic setting; as I said I think any trick used with RH would also work with BLP. I just used an integer set because that's all I needed for my use case and it was easy to implement several different approaches for benchmarking. As you note, it favors use cases where the hash function is cheap (or invertible) and elements are cheap to move around.
About your question on load factors: no, the benchmarks are measuring exactly what they claim to be. The hash table constructor divides max data size by load factor to get the table size (https://github.com/senderista/hashtable-benchmarks/blob/mast...), and the benchmark code instantiates each hash table for exactly the measured data set size and load factor (https://github.com/senderista/hashtable-benchmarks/blob/mast...).
I can't explain the peaks around 1M in many of the plots; I didn't investigate them at the time and I don't have time now. It could be a JVM artifact, but I did try to use JMH "best practices", and there's no dynamic memory allocation or GC happening during the benchmark at all. It would be interesting to port these tables to Rust and repeat the measurements with Criterion. For more informative graphs I might try a log-linear approach: divide the intervals between the logarithmically spaced data sizes into a fixed number of subintervals (say 4).
-
Inside boost::unordered_flat_map
I think "bidirectional linear probing" is an underrated approach (and much simpler): https://github.com/senderista/hashtable-benchmarks/blob/master/src/main/java/set/int64/BLPLongHashSet.java
-
A fast & densely stored hashmap and hashset based on robin-hood backward shift deletion
I will probably never get around to porting my bidirectional linear probing integer hash set from Java to C++, but I hope someone can try adapting BLP to general C++ hashmaps and hashsets, because it significantly outperforms Robin Hood in my benchmarks.
-
Ask HN: Who wants to be hired? (March 2022)
https://homes.cs.washington.edu/~magda/papers/wang-cidr17.pd...
I'm most interested in developing high-performance database engines in low-level languages, but open to any challenging systems programming project. I've been working in C++ for the last 2 years, but have written nontrivial projects in Rust and Java as well (e.g., https://github.com/senderista/rotated-array-set, https://github.com/senderista/hashtable-benchmarks). I would enjoy using Rust or Zig on a new project, but I consider the project itself to be much more important than the language it's written in. I am not interested in cryptocurrency, adtech, or fintech projects.
zig
-
Memory-mapped IO registers in Zig. (2021)
There is an issue proposing this approach: https://github.com/ziglang/zig/issues/4284
- Zig Programming Language
- Zig Language 0.12 Release
-
Zig 0.12.0 Release Notes
https://github.com/ziglang/zig/issues/224
e.g.:
> > When debugging/prototyping, it's useful to comment out a line without having to refactor, e.g.
-
How to Write a PHP Extension with Zig?
When writing code in a scripting language, sometimes you need that extra bit of performance (or maybe an async feature from Zig).
-
Bun - The One Tool for All Your JavaScript/Typescript Project's Needs?
NodeJS is by no means a slow runtime, it wouldn’t be so popular if it was. But compared to Bun, it’s slow. Bun was built from the ground up with speed in mind, using both JavascriptCore and Zig. The Bun team spent an enormous amount of time and energy trying to make Bun fast, including lots of profiling, benchmarking, and optimizations.
-
Bun 1.1
ntdll.dll!RtlUserThreadStart()
There are valid reasons to use APIs from NTDLL. Where I disagree with zig#1840 is the idea that it is always better to use NTDLL versions of API. Every other software ecosystem uses the standard Win32 APIs and diverging from that without a good reason seems like a good way to have unexpected behavior. One concrete example is most users and programmers expect Windows to redirect some file system paths when running on WOW64. But this is implemented in Kernel32, not ntdll.
https://github.com/ziglang/zig/issues/11894
- Zig, Rust, and Other Languages
-
Nanos – A Unikernel
Zig also has an IRC channel on libera (#zig) that is moderated by Andrew Kelley.[1]
[1] https://github.com/ziglang/zig/wiki/Community
- Ask HN: What Underrated Open Source Project Deserves More Recognition?
What are some alternatives?
unordered_dense - A fast & densely stored hashmap and hashset based on robin-hood backward shift deletion
Nim - Nim is a statically typed compiled systems programming language. It combines successful concepts from mature languages like Python, Ada and Modula. Its design focuses on efficiency, expressiveness, and elegance (in that order of priority).
myria - Myria is a scalable Analytics-as-a-Service platform based on relational algebra.
Odin - Odin Programming Language
js2scheme
v - Simple, fast, safe, compiled language for developing maintainable software. Compiles itself in <1s with zero library dependencies. Supports automatic C => V translation. https://vlang.io
flat_hash_map - A very fast hashtable
rust - Empowering everyone to build reliable and efficient software.
robin-hood-hashing - Fast & memory efficient hashtable based on robin hood hashing for C++11/14/17/20
go - The Go programming language
nafeez.xyz - ⚡ My personal website.
ssr-proxy-js - A Server-Side Rendering Proxy focused on customization and flexibility!