Speeding Up (small) Ruby Hashes

This post explores an idea that emerged after publishing a previous article on shrinking Ruby hashes. Ruby's Hash class, up to eight entries, is not a true hash table but rather an array of key-value pairs. This is due to storing only the lower byte of the hash-code, which can lead to hash collisions but is acceptable when the number of keys is limited.

The core of the hash lookup routine is a linear search, which is O(n) in complexity. While this is acceptable for eight entries, it deviates from the typical O(1) access time expected from hash tables. The author suggests that ar_table lookups could be made O(1) by employing a technique called SWAR (SIMD within a register), which searches for a specific byte within a string of length 8. This is efficient because manipulating bytes fits perfectly within CPU registers.

The SWAR method involves interpreting ar_hint as a single 8-byte number and performing bitwise operations to determine if any byte is zero. If no byte is zero, the result is 0, indicating that none of the bytes were zero. This boolean condition can be further expanded to derive the byte index. By doing so, Ruby's hash lookups could potentially achieve O(1) performance, closing the gap with traditional hash tables while still maintaining the space-saving benefits of the ar_table implementation.