Swiss Tables(abseil.io)

69 pointsby andsoitisletztes Jahr27 comments

https://abseil.io/about/design/swisstables

8 comments

This description reminds me of a hashtable used for some APL things, which is described in a talk online somewhere. The difference is that the APL table did Robin Hood insertions (an open table where new elements are inserted at or after the position corresponding to their hash, but you rearrange things to try to reduce the maximum distance any element is from where it should be) so it stored 4 bits of offset information and 4 bits of hash in each entry of the metadata table. Lookups were still sse based, something like:

  position = (hash>>4) & mask
  test = set1_16x8(hash&0xf) | 0xf0e0d0c0b0a090807060504030201000
  candidates = eq_16x8(load_16x8(table + position), test)
  // convert candidates to mask and test each option

Sesse__letztes Jahr

FWIW, I found that when doing Robin Hood, SSE is just a loss, since you usually find the element so soon. (If you are dominated by non-matching lookups, you can consider putting a Bloom filter in front.)

pkhuongletztes Jahr

With linear probing RH, a failed lookup can stop as early as a successful one, as long as you also store the hash (useful for fast insertion): stop looking when you'd insert the key you're looking for before the current entry.

dan-robertsonletztes Jahr

I think the point of the SSE stuff was to avoid branching (apart from the very exceptional case where you would be more than 15 slots away

fmajidletztes Jahr

Apparently Go 1.24's internal implementation of maps was changed to use Swiss Tables (reimplemented in Go, of course, not the Abseil C++ implementation).

https://www.bytesizego.com/blog/go-124-swiss-table-maps

I'd be interested to see how the new Tiny Pointers algorithm would perform against Swiss Tables, specially when occupation rate is high.

https://www.quantamagazine.org/undergraduate-upends-a-40-yea...

jsheardletztes Jahr

Rust also switched their standard maps over to Swisstables a while ago. Unfortunately despite the original implementation being in C++, I don't think it's possible for C++ implementations to do the same with the STL maps due to constraints imposed by the spec. They'd have to create a new STL type for them.

tialaramexletztes Jahr

Yes, in C++ in 2011 they standardized the hash table design you'd have been shown in a 1980s (or maybe 1990s if you got unlucky in where you went to school) Data Structures class. They called this type std::unordered_map

This was a Closed Addressing aka Separate Chaining table. The idea is easy enough that it's actually an Advent Of Code problem one year which is why this design is much older than the modern efficient Open Addressing tables. In C++ with std::unordered_map you are guaranteed that the address of items in the table won't change while they're in the table, this works because they're not actually stored directly in the table. You also provided an API to work with these chains of related items and to fiddle with "how full" the table is.

This API makes complete sense for a Closed Addressing table, but both the API functions and the pointer stability guarantee don't make any sense for Open Addressing.

If you only need the pointer stability you can pay just for that, Abseil offers a compatible type with that property, but if you need all the Chaining APIs (and you might in principle) then it doesn't have those, too bad.

tonfaletztes Jahr

Tiny Pointers doesn't currently have practical use, it's a complexity results.

> The team’s results may not lead to any immediate applications, but that’s not all that matters, Conway said. “It’s important to understand these kinds of data structures better. You don’t know when a result like this will unlock something that lets you do better in practice.”

tialaramexletztes Jahr

Yeah, naive application of big-O complexity models can lead you far astray when you have real world problems. If you can do F in n*k1 time, but I need n*n*k2 time you may think your algorithm for F is better, O(n) compared to O(n squared) but if k1 is 1 second while k2 is 80 nanoseconds then actually my "worse" algorithm is faster until n is so huge that we have runtimes of about half a year.

camel-cdrletztes Jahr

Here is a great talk about the new boost::unordered_map implementation: https://m.youtube.com/watch?v=Rg8MZ5pJIJA

It's design is clearly inspired by abseil::flat_map but improves it in a few aspects.

spacechild1letztes Jahr

Nitpick, but I think you mean boost::unordered_flat_map.

boost::unordered_map is a drop-in replacement for std::unordered_map and as such uses seperate chaining.

Anyway, thanks for the video!

camel-cdrletztes Jahr

Yeah, thanks for the correction.

jbreckmckyeletztes Jahr

I'm lazy. What's a Swiss table in a couple of sentences? Assume I am _moderately_ competent with C++ but not some Level 800 cyberbrain

procaryoteletztes Jahr

Caveat that this is new to me and I might get it wrong

It seems to be a way to arrange a hashtable so you use most of the hashed value (H1) to identify a range of cells in your table, and the rest of the hashed value (H2) as metadata. In the metadata for a cell it's tagged as empty/full/deleted and a full cell is also tagged with its H2 value

So when looking up things you find the range with H1, then you check H2 against the metadata for that range, to see which of the cells might contain the right value.

I imagine the benefit is that checking H2 against warm metadata is cache friendly and can use vector instructions, whereas with regular double hashing you'd need to lookup cold memory to check the key, and then perhaps do it again a couple of times

Do correct me if I am wrong

tialaramexletztes Jahr

It's an open addressed hash table using SIMD to get faster probing? If all that makes sense but you feel unsatisfied I can't help you and you need to ask somebody who knows exactly what you do or don't know.

If those phrases don't make sense, Wikipedia has entries on Open Addressing and on SIMD which can help you.

jbreckmckyeletztes Jahr

Thanks, I don't fully understand but I know enough about each idea to Google it further

frohletztes Jahr

especially it doesn't "degrade" when nearly full (text book disadvantage of linear probing), by cleverly rearranging existing items on hash table insert (and also on delete).

so there is a kinda sorta "balancing" of the linear probing lengths.

jrimbaultletztes Jahr

Not a couple of sentences

CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step” : https://www.youtube.com/watch?v=ncHmEUmJZf4

n2d4letztes Jahr

A hash table implementation that's faster than the usual

DeathArrowletztes Jahr

Here is some alternative explanation: https://dev.to/huizhou92/swisstable-a-high-performance-hash-...

skunkworkerletztes Jahr

For those reading, Go officially adopted swisstable into Map for 1.24 last week.

cjj_sweletztes Jahr

I always get excited when I see Abseil related things online. I was a member of the team from 2018 until 2022 and had a blast getting to learn from the best.

procaryoteletztes Jahr

Hmm, the article is a bit hard to follow and lacks any elaboration on which cases this data structure is better or worse than other hash tables

As swiss tables are new to me I looked around a bit and found this to be a better explanation

https://faultlore.com/blah/hashbrown-tldr/

bsdoobyletztes Jahr

...and why is it called a Swiss table? (I am from CH, asking for a friend).

GeneralMayhemletztes Jahr

Because they were designed and implemented by a team in Zurich. I'm not joking, that's literally the reason.

DeathArrowletztes Jahr

I believe that's because they were first crafted in 19th century a small village in Jura Mountains by some skilled artisans.

n2d4letztes Jahr

Some of its authors work(ed) at Google Zurich