search

cockroachdb / swiss

Go port of Google's Swiss Table hash table
Apache License 2.0
317 stars 12 forks source link

swiss: Go implementation of Swiss Tables #1

Closed petermattis closed 9 months ago

petermattis commented 9 months ago

A swiss.Map has similar or slightly better performance than Go's builtin map for small map sizes, and is much faster at large map sizes (old=go-map, new=swissmap):

name                        old time/op  new time/op  delta
StringMaps/n=16/map-10      7.19ns ± 3%  7.28ns ± 0%     ~     (p=0.154 n=9+9)
StringMaps/n=128/map-10     7.66ns ± 5%  7.37ns ± 3%   -3.74%  (p=0.008 n=10+9)
StringMaps/n=1024/map-10    10.8ns ± 3%   7.6ns ± 3%  -29.76%  (p=0.000 n=10+10)
StringMaps/n=8192/map-10    20.3ns ± 2%   7.9ns ± 1%  -61.16%  (p=0.000 n=10+10)
StringMaps/n=131072/map-10  26.1ns ± 0%  14.0ns ± 1%  -46.56%  (p=0.000 n=10+10)
Int64Maps/n=16/map-10       4.96ns ± 1%  4.83ns ± 0%   -2.73%  (p=0.000 n=9+9)
Int64Maps/n=128/map-10      5.19ns ± 3%  4.89ns ± 5%   -5.80%  (p=0.000 n=10+10)
Int64Maps/n=1024/map-10     6.80ns ± 5%  5.01ns ± 2%  -26.32%  (p=0.000 n=10+10)
Int64Maps/n=8192/map-10     17.4ns ± 1%   5.3ns ± 0%  -69.59%  (p=0.000 n=10+7)
Int64Maps/n=131072/map-10   20.6ns ± 0%   6.7ns ± 0%  -67.67%  (p=0.000 n=10+9)

A swiss.Map dominates the performance of the RobinHood map used by Pebble's block-cache (old=robinhood, new=swissmap):

name                        old time/op  new time/op  delta
StringMaps/n=16/map-10      11.7ns ±28%   7.3ns ± 0%  -37.68%  (p=0.000 n=10+9)
StringMaps/n=128/map-10     12.6ns ± 5%   7.4ns ± 3%  -41.44%  (p=0.000 n=9+9)
StringMaps/n=1024/map-10    14.1ns ± 7%   7.6ns ± 3%  -46.30%  (p=0.000 n=10+10)
StringMaps/n=8192/map-10    17.7ns ± 4%   7.9ns ± 1%  -55.39%  (p=0.000 n=10+10)
StringMaps/n=131072/map-10  25.5ns ± 1%  14.0ns ± 1%  -45.20%  (p=0.000 n=10+10)
Int64Maps/n=16/map-10       4.96ns ± 7%  4.83ns ± 0%   -2.72%  (p=0.012 n=10+9)
Int64Maps/n=128/map-10      4.92ns ± 4%  4.89ns ± 5%     ~     (p=0.085 n=10+10)
Int64Maps/n=1024/map-10     5.63ns ± 5%  5.01ns ± 2%  -11.02%  (p=0.000 n=10+10)
Int64Maps/n=8192/map-10     11.1ns ± 4%   5.3ns ± 0%  -52.46%  (p=0.000 n=10+7)
Int64Maps/n=131072/map-10   14.3ns ± 1%   6.7ns ± 0%  -53.33%  (p=0.000 n=10+9)

The inspiration behind writing a Go implementation of Swiss Tables came from https://github.com/dolthub/swiss. That implementation is quite a bit slower and does not follow the original design (the slots are divided into groups which do not overlap).

name                        old time/op  new time/op  delta
StringMaps/n=16/map-10      11.2ns ±15%   7.3ns ± 1%  -34.24%  (p=0.000 n=10+8)
StringMaps/n=128/map-10     12.2ns ±10%   7.4ns ± 4%  -38.76%  (p=0.000 n=10+10)
StringMaps/n=1024/map-10    12.7ns ± 5%   7.5ns ± 2%  -40.65%  (p=0.000 n=10+10)
StringMaps/n=8192/map-10    14.3ns ± 3%   7.9ns ± 1%  -44.87%  (p=0.000 n=10+10)
StringMaps/n=131072/map-10  18.5ns ± 2%  13.9ns ± 2%  -24.86%  (p=0.000 n=10+8)
Int64Maps/n=16/map-10       6.26ns ±17%  4.85ns ± 1%  -22.47%  (p=0.000 n=10+8)
Int64Maps/n=128/map-10      6.76ns ± 4%  4.99ns ± 0%  -26.20%  (p=0.001 n=8+6)
Int64Maps/n=1024/map-10     7.07ns ± 3%  4.97ns ± 2%  -29.71%  (p=0.000 n=10+10)
Int64Maps/n=8192/map-10     8.52ns ± 5%  5.30ns ± 1%  -37.77%  (p=0.000 n=10+10)
Int64Maps/n=131072/map-10   12.0ns ± 2%   6.7ns ± 1%  -44.11%  (p=0.000 n=10+10)
petermattis commented 9 months ago

This is pretty much exactly https://github.com/cockroachdb/cockroach/pull/118742. Rather than fleshing out all of the TODOs and having you re-review the code again, I felt it might be easier to review this as-is, get it checked in and follow up with subsequent PRs to address the TODOs and set up CI.