SwissHash

Swiss Table hash map implementation as a Ruby C extension. The design follows the same broad family as Google's Abseil flat_hash_map, Rust's hashbrown, and Go 1.24 Swiss Tables, with Ruby-specific hashing, key preparation, GC integration, and a Hash-like API surface.

gem install swiss_hash

require "swiss_hash"

h = SwissHash::Hash.new
h["key"] = "value"
h["key"]          # => "value"
h.fetch("key")    # => "value"
h.delete("key")   # => "value"
h.stats            # => { capacity: 16, size: 0, ... }

SwissHash::Hash is intentionally not a subclass of Ruby's built-in Hash. Use to_h when you need a real Ruby Hash, and to_sh when you want a shallow SwissHash copy.

Benchmarks below were produced by benchmark.rb on Ruby 3.4.3 / arm64-darwin24.

Methodology: 10 runs × 21 measured iterations, 5 warmup iterations per run, IQR-filtered mean per run, interleaved Ruby/SwissHash measurements with alternating start order, and per-side coefficient of variation (±X.X%) reported to make noise visible.

Ruby Hash uses an AR-table for small hashes, so very small integer-keyed workloads can still favour the built-in implementation. String-heavy workloads continue to be the strongest SwissHash case.

• SwissHash is faster on 6 of 7 operations at N=100k in the current benchmark run.
• The strongest win is still string-key insertion: −34% to −37% across tested sizes.
• Large integer-keyed inserts, delete/reinsert churn, and mixed workloads improved substantially after moving more Hash-like operations into C and keeping the hot paths lean.
• String lookups are workload-sensitive: SwissHash wins at N=1k and N=10k, while the N=100k run is slightly slower than Ruby Hash within a noisier test band.
• Ruby's built-in Hash remains excellent, especially for very small maps and cases that benefit from VM-level Hash specialization.

For 100,000 integer keys in the current benchmark:

Additional stats: load factor 76.3%, max load factor 87.5%, SIMD path reported as SWAR on the benchmark machine.

• Swiss Table probing: 7-bit H2 metadata, group probing, triangular probe sequence, and 87.5% max load factor.
• Fast string-key path: wyhash for string keys, frozen string key preparation, ASCII-7bit equality shortcut, and direct memcmp when encodings are compatible.
• Low GC pressure: keys and values are Ruby objects, while control bytes and slots live in contiguous native arrays.
• Delete/reinsert friendly: tombstones are tracked and compacted to avoid pathological slowdown.
• Hash-like API: basic accessors, enumeration, fetch helpers, merge/update/replace, filtering, transforming, slicing, inversion, and conversion helpers.
• Native hot paths: performance-critical methods are implemented in C; small convenience wrappers live in Ruby where that does not affect the core benchmark paths.

hash = SwissHash::Hash.new(capacity = 16)

# Basic operations
hash[key] = value
hash.store(key, value)
hash[key]                  # returns nil if absent
hash.fetch(key)
hash.fetch(key, default)
hash.fetch(key) { |missing_key| ... }
hash.delete(key)           # returns old value or nil
hash.clear
hash.replace(other_hash)

# Merge/update
hash.merge(other_hash)
hash.merge(other_hash) { |key, old_value, new_value| ... }
hash.merge!(other_hash)
hash.update(other_hash)

# Enumeration
hash.each { |key, value| ... }
hash.each_pair { |key, value| ... }
hash.each_key { |key| ... }
hash.each_value { |value| ... }
hash.keys
hash.values
hash.to_a

# Query helpers
hash.size                  # also: length
hash.empty?
hash.key?(key)             # also: has_key?, include?, member?
hash.value?(value)         # also: has_value?
hash.key(value)            # first key for value, or nil
hash.assoc(key)
hash.rassoc(value)
hash.values_at(*keys)
hash.fetch_values(*keys)
hash.dig(key, *path)
hash.count                 # Enumerable-compatible

# Filtering and transforms
hash.slice(*keys)
hash.except(*keys)
hash.select { |key, value| ... }    # also: filter
hash.select! { |key, value| ... }   # also: filter!
hash.reject { |key, value| ... }
hash.reject! { |key, value| ... }
hash.delete_if { |key, value| ... }
hash.keep_if { |key, value| ... }
hash.compact
hash.compact!
hash.transform_keys { |key| ... }
hash.transform_keys! { |key| ... }
hash.transform_values { |value| ... }
hash.transform_values! { |value| ... }
hash.invert
hash.shift
hash.flatten(level = 1)

# Conversion
hash.to_h                  # returns a Ruby Hash
hash.to_sh                 # returns a shallow SwissHash copy

# Maintenance / debugging
hash.compact_storage!      # drop tombstones without changing values
hash.stats                 # => { capacity:, size:, num_groups:, load_factor:,
                           #      memory_bytes:, growth_left:, tombstones:,
                           #      simd:, layout: }

SwissHash aims to cover the practical subset of Hash that is useful for a fast native hash map, but it is not a drop-in replacement for every Ruby Hash semantic.

Not currently supported:

• default values and default blocks from Hash.new(default) / Hash.new { ... }
• compare_by_identity
• full insertion-order guarantees
• every rarely used method from Ruby's full Hash API

Use SwissHash when:

• keys are mostly strings and insert speed matters;
• the map commonly holds 10,000+ entries;
• workloads include deletes and reinserts;
• predictable native memory layout and lower Ruby-object churn are useful.

Stick with Ruby's built-in Hash when:

• the hash is small and mostly lookup-heavy with integer keys;
• you depend on exact Ruby Hash semantics such as defaults, insertion order, compare_by_identity, or the complete standard API;
• the code path benefits from VM-level Hash#[] specialization more than from the underlying table layout.

• Open addressing with 7-bit H2 metadata byte per slot; group matching rejects non-matching slots in batches.
• Group size 16 on SSE2 and group size 8 on portable SWAR. On the benchmarked Apple Silicon machine the active path is SWAR.
• Triangular probing — i(i+1)/2 — over power-of-two group counts.
• Max load factor 87.5% (7/8).

• wyhash for string keys.
• Fibonacci multiplicative hash for Fixnum and Symbol keys.
• Frozen string key preparation to avoid later key mutation surprises.
• ASCII-7bit and encoding-index equality fast paths before falling back to Ruby-compatible string comparison.
• Inline RTYPEDDATA_DATA on hot methods ([], []=, delete, key?) to avoid repeated typed-data checks.
• Prefetch of slot groups after control-byte load so data fetch overlaps with match extraction.

• Separate control-byte array and slot array.
• Native arrays are allocated outside Ruby's object heap; keys and values are still marked for GC.
• Slot memory is not zero-initialized on allocation; slots are read only after their control byte marks them live.

bundle install
bundle exec rake compile

bundle exec ruby test/hash_api_test.rb
bundle exec ruby test/string_key_mutation_test.rb

bundle exec ruby benchmark.rb

The benchmark includes a smoke test before timing and prints the active SIMD/SWAR path in the memory section.

For profiling on macOS:

bundle exec ruby simp.rb            # runs an infinite lookup loop and prints PID
sample <PID> 60 -f /tmp/swiss.sample
filtercalltree /tmp/swiss.sample | head -100

See CHANGELOG.md.

• Matt Kulukundis, "Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step" — CppCon 2017
• Abseil: SwissTables design
• rust-lang/hashbrown — reference for SSE2/portable group strategy choices
• Go 1.24 maps — probing and resize design trade-offs
• Aria Beingessner, "Swisstable, a Quick and Dirty Description" — implementer's notes

MIT