Re: Swiss table implementation
Martin McClure <[email protected]> Wed, 27 Aug 2025 22:16:24 -0700
| Newsgroups | gmane.comp.lang.smalltalk.vwnc |
|---|---|
| Message-ID | <[email protected]> |
This is a multi-part message in MIME format.
--------------C2JIbtXq2XrgiPgTR4dHoN07
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: quoted-printable
Hi Holger,
Interesting -- I hadn't seen Swiss tables.
In my experience, the most important factor in how hash table lookup=20
performs is the number of cache line reads it takes, on average, to find=20
an entry. With a modern hardware cache line read taking a couple of=20
orders of magnitude more time than executing an instruction, what and=20
how many instructions you use is less of a factor. With open-addressing=20
linear-probing tables like Smalltalk has used for decades, if your hash=20
function is decent and you don't load the table beyond 70%-80%, most=20
lookups can be done in one cache line read, and very few take more than=20
two cache line reads.
It doesn't look like Swiss tables improve much on this. Even if you=20
store each metadata word in the same cache line as the data word, you=20
still have to read one cache line, and sometimes more. It's possible=20
that the Swiss table tolerates mediocre hash functions better, or might=20
save memory by allowing higher loading with similar speed. It's also=20
possible that its insert/delete performance is better -- most of my=20
experience has been with tables that have far more lookups than changes.
So my first guess (and with performance one does need to test to be=20
sure) is that Swiss tables would give little to no speed advantage in=20
Smalltalk. over the open-addressing linear probing tables of the kind=20
that Smalltalk as used for decades. I'm not sure what was wrong with=20
Go's and C++'s older map implementations, but that's something that a=20
lot of people get wrong. Even getting a hash table design /almost/ right=20
has a penalty.
But I'd also be interested in seeing the results if someone were to try it.
Regards,
-Martin
On 8/27/25 2:40 AM, Holger Kleinsorgen wrote:
> Hello,
>
> has anyone tried to implement a Swiss table dictionary (see=20
> https://urldefense.com/v3/__https://go.dev/blog/swisstable__;!!DZ3fjg!8Z3=
XGyBHxwt6G4_jYTjFhcxayB-6TsB0CINXIN_LZ9-cwX1VQJ9CfnfLCLqqNsUR7A9USTatcELwUa=
_hoASvX-pQJBL0UIjQuA$ =20
> <https://urldefense.com/v3/__https://go.dev/blog/swisstable__;!!DZ3fjg!6z=
k_LKh2X8Ni0_GbEirgVYVib_zPSOY6PUzEdmsv4uYFAT00VkL04_e6a44V8wAy7_8QaSoHNpF8Q=
sbyTjeiF_LdirjWMBbwfaPpTQ$>)=20
> in Smalltalk? I'm curious if there is a performance benefit without=20
> SIMD instructions.
>
> Holger
>=
--------------C2JIbtXq2XrgiPgTR4dHoN07
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: 8bit
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p>Hi Holger,</p>
<p>Interesting -- I hadn't seen Swiss tables.</p>
<p>In my experience, the most important factor in how hash table
lookup performs is the number of cache line reads it takes, on
average, to find an entry. With a modern hardware cache line read
taking a couple of orders of magnitude more time than executing an
instruction, what and how many instructions you use is less of a
factor. With open-addressing linear-probing tables like Smalltalk
has used for decades, if your hash function is decent and you
don't load the table beyond 70%-80%, most lookups can be done in
one cache line read, and very few take more than two cache line
reads.</p>
<p>It doesn't look like Swiss tables improve much on this. Even if
you store each metadata word in the same cache line as the data
word, you still have to read one cache line, and sometimes more.
It's possible that the Swiss table tolerates mediocre hash
functions better, or might save memory by allowing higher loading
with similar speed. It's also possible that its insert/delete
performance is better -- most of my experience has been with
tables that have far more lookups than changes.<br>
</p>
<p>So my first guess (and with performance one does need to test to
be sure) is that Swiss tables would give little to no speed
advantage in Smalltalk. over the open-addressing linear probing
tables of the kind that Smalltalk as used for decades. I'm not
sure what was wrong with Go's and C++'s older map implementations,
but that's something that a lot of people get wrong. Even getting
a hash table design <i>almost</i> right has a penalty.</p>
<p>But I'd also be interested in seeing the results if someone were
to try it.</p>
<p>Regards,</p>
<p>-Martin<br>
</p>
<div class="moz-cite-prefix">On 8/27/25 2:40 AM, Holger Kleinsorgen
wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CAGhifExbD6LLP_rS+H=f1NxPVfzZqsnQVCaSSEqCSz++qtqG_w@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<div dir="ltr">
<div>Hello,</div>
<div><br>
</div>
<div>has anyone tried to implement a Swiss table dictionary
(see <a
href="https://urldefense.com/v3/__https://go.dev/blog/swisstable__;!!DZ3fjg!6zk_LKh2X8Ni0_GbEirgVYVib_zPSOY6PUzEdmsv4uYFAT00VkL04_e6a44V8wAy7_8QaSoHNpF8QsbyTjeiF_LdirjWMBbwfaPpTQ$"
moz-do-not-send="true">https://go.dev/blog/swisstable</a>)
in Smalltalk? I'm curious if there is a performance benefit
without SIMD instructions.</div>
<div><br>
</div>
<div>Holger</div>
<div><br>
</div>
</div>
</blockquote>
</body>
</html>
--------------C2JIbtXq2XrgiPgTR4dHoN07--