Re: Swiss table implementation
Holger Kleinsorgen <[email protected]> Sat, 30 Aug 2025 18:44:13 +0200
| Newsgroups | gmane.comp.lang.smalltalk.vwnc |
|---|---|
| Message-ID | <CAGhifEyjORt4774-1Us=WLYzT7ZGDK3RAVjZzMnsJOrCT21SNw@mail.gmail.com> |
--000000000000d3ae01063d97d952 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Another shortcoming of SortedCollection is the lack of an #includes: implementation that utilizes the sorting, for example SortedCollection>>includes: anObject | index | index :=3D self indexForInserting: anObject . ^ firstIndex < index and: [( self basicAt: index - 1 ) =3D anObject ] Regarding Swiss tabes: There are even more micro optimisations that promise to improve the traditional probing: https://urldefense.com/v3/__https://martin.ankerl.com/2019/04/01/hashmap-be= nchmarks-03-04-result-RandomInsertEraseStrings/__;!!DZ3fjg!-Z4IxWsEvLefEN4S= qKhXEDH_RJztjkwXGa1fnyxtR6Vmd0Tkum9LChL4Iekqj7Weqk4-Wu028lRYFAUA-VsnixHLRyw= VjKSgvJX5FA$=20 I tried implementing - Swiss table dictionaries - Robin Hood probing (reorders slots by probe distance) - Hash chaining (stores a linked list instead of probing) The initial results (take with a grain of salt, the tinies errors can cause severe performance penalties): - Swiss tables with a group of 64 bits is not reasonable, beause the upper bits are used, thus creating LargeIntegers. - Swiss tables with a group size of 32 bits are quite slower than a plain dictionary (insert by factor x4, lookup by factor x2) . The performance difference shrinks when the hash function is expensive. - Robin Hood dictionaries are terribly slow (no idea why, but maybe the required slot swapping is far less expensive in C). - Hash chaining is quite versatile, at a cost of some memory, and beats probing in scenarios with a lot of collisions (as expected). Holger Am Sa., 30. Aug. 2025 um 18:12 Uhr schrieb Steven Kelly <[email protected] >: > From the Go implementation: =E2=80=9COverall, in full application benchma= rks, we > found a geometric mean CPU time improvement of around 1.5%.=E2=80=9D > > And that=E2=80=99s with SIMD instructions. Hard to imagine an increase in > Smalltalk code complexity that wouldn=E2=80=99t eat at least that 1.5%, e= ven if you > could avoid the extra cache line hit Martin mentioned. > > > > If you like speed optimizations, try a couple of orders of magnitude > improvements in adding to the end of a SortedCollection: > > > > s :=3D SortedCollection new. > > Time millisecondsToRun: [(1 to: 1e6 by: 1) do: [:ix | s add: ix]]. > > "44376 -> 468" > > > > SortedCollection>>insert: anObject before: originalSpot > > | spot | > > spot :=3D originalSpot. > > spot > self basicSize ifTrue: > > [self makeRoomAtLast. > > spot :=3D lastIndex+1]. > > ^super insert: anObject before: spot > > > > It=E2=80=99s a surprisingly common special case: we hit it with a custome= r calling > SOAP operations without persistent connections, as the TimerEphemeronQueue > filled up with a 20-minute Timer for each call. > > > > Steve > > > > *From:* [email protected] < > [email protected]> *On Behalf Of *Holger > Kleinsorgen > *Sent:* Wednesday, August 27, 2025 12:40 PM > *To:* [email protected] > *Subject:* [vwnc] Swiss table implementation > > > > Hello, > > > > has anyone tried to implement a Swiss table dictionary (see > https://urldefense.com/v3/__https://go.dev/blog/swisstable__;!!DZ3fjg!-Z4= IxWsEvLefEN4SqKhXEDH_RJztjkwXGa1fnyxtR6Vmd0Tkum9LChL4Iekqj7Weqk4-Wu028lRYFA= UA-VsnixHLRywVjKR_djvFxQ$=20 > <https://urldefense.com/v3/__https:/go.dev/blog/swisstable__;!!DZ3fjg!6zk= _LKh2X8Ni0_GbEirgVYVib_zPSOY6PUzEdmsv4uYFAT00VkL04_e6a44V8wAy7_8QaSoHNpF8Qs= byTjeiF_LdirjWMBbwfaPpTQ$>) > in Smalltalk? I'm curious if there is a performance benefit without SIMD > instructions. > > > > Holger > > > --000000000000d3ae01063d97d952 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr"><div>Another=C2=A0shortcoming of SortedCollection is the l= ack of an #includes: implementation that utilizes the sorting, for example<= /div><div><br></div><div>SortedCollection>>includes: anObject <br>=C2= =A0 =C2=A0| index |<br>=C2=A0 =C2=A0index :=3D self indexForInserting:=C2= =A0 anObject=20 .<br>=C2=A0 =C2=A0^ firstIndex < index and: [( self basicAt: index - 1 )= =3D=C2=A0 anObject=20 ]</div><div><br></div><div>Regarding Swiss tabes: There are even more micro= optimisations that promise to improve the traditional probing:</div><div><= a href=3D"https://urldefense.com/v3/__https://martin.ankerl.com/2019/04/01/= hashmap-benchmarks-03-04-result-RandomInsertEraseStrings/__;!!DZ3fjg!-Z4IxW= sEvLefEN4SqKhXEDH_RJztjkwXGa1fnyxtR6Vmd0Tkum9LChL4Iekqj7Weqk4-Wu028lRYFAUA-= VsnixHLRywVjKSgvJX5FA$">https://martin.ankerl.com/2019/04/01/hashmap-benchm= arks-03-04-result-RandomInsertEraseStrings/</a></div><div><br></div><div>I = tried implementing</div><div>- Swiss table dictionaries</div><div>- Robin H= ood probing (reorders slots by probe distance)</div><div>- Hash chaining (s= tores a linked list instead of probing)</div><div><br></div><div>The initia= l results (take with a grain of salt, the tinies errors can cause severe pe= rformance penalties):</div><div>- Swiss tables with a group of 64 bits is n= ot=C2=A0reasonable, beause the upper bits are used, thus creating LargeInte= gers.</div><div>- Swiss tables with a group size of 32 bits are quite slowe= r than a plain dictionary=C2=A0 (insert by factor x4, lookup by factor x2) . The performance difference shr= inks when the hash function is expensive.</div><div>- Robin Hood dictionari= es are terribly slow (no idea why, but maybe the required slot swapping is = far less expensive in C).</div><div>- Hash chaining is quite versatile, at = a cost of some memory, and beats probing in scenarios with a lot of collisi= ons (as expected).</div><div><br></div><div>Holger</div></div><br><div clas= s=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">Am Sa., 30. Aug. 20= 25 um 18:12=C2=A0Uhr schrieb Steven Kelly <<a href=3D"mailto:stevek@meta= case.com" target=3D"_blank">[email protected]</a>>:<br></div><blockquo= te class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px = solid rgb(204,204,204);padding-left:1ex"><div> <div lang=3D"EN-US"> <div> <p class=3D"MsoNormal">From the Go implementation: =E2=80=9COverall, in ful= l application benchmarks, we found a geometric mean CPU time improvement of= around 1.5%.=E2=80=9D<u></u><u></u></p> <p class=3D"MsoNormal">And that=E2=80=99s with SIMD instructions. Hard to i= magine an increase in Smalltalk code complexity that wouldn=E2=80=99t eat a= t least that 1.5%, even if you could avoid the extra cache line hit Martin = mentioned.<u></u><u></u></p> <p class=3D"MsoNormal"><u></u>=C2=A0<u></u></p> <p class=3D"MsoNormal">If you like speed optimizations, try a couple of ord= ers of magnitude improvements in adding to the end of a SortedCollection:<u= ></u><u></u></p> <p class=3D"MsoNormal"><u></u>=C2=A0<u></u></p> <p class=3D"MsoNormal">s :=3D SortedCollection new.<u></u><u></u></p> <p class=3D"MsoNormal">Time millisecondsToRun: [(1 to: 1e6 by: 1) do: [:ix = | s add: ix]].<u></u><u></u></p> <p class=3D"MsoNormal">"44376 -> 468"<u></u><u></u></p> <p class=3D"MsoNormal"><u></u>=C2=A0<u></u></p> <p class=3D"MsoNormal">SortedCollection>>insert: anObject before: ori= ginalSpot <u></u> <u></u></p> <p class=3D"MsoNormal">=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 | spot |<u></u><u></u></p> <p class=3D"MsoNormal">=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 spot :=3D originalSpot.<u></u><u></= u></p> <p class=3D"MsoNormal">=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 spot > self basicSize ifTrue: <u= ></u><u></u></p> <p class=3D"MsoNormal">=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 =C2=A0[self makeR= oomAtLast.<u></u><u></u></p> <p class=3D"MsoNormal">=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 spot :=3D lastInd= ex+1].<u></u><u></u></p> <p class=3D"MsoNormal">=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2= =A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 ^super insert: anObject before: spo= t<u></u><u></u></p> <p class=3D"MsoNormal"><u></u>=C2=A0<u></u></p> <p class=3D"MsoNormal">It=E2=80=99s a surprisingly common special case: we = hit it with a customer calling SOAP operations without persistent connectio= ns, as the TimerEphemeronQueue filled up with a 20-minute Timer for each ca= ll. <u></u><u></u></p> <p class=3D"MsoNormal"><u></u>=C2=A0<u></u></p> <p class=3D"MsoNormal">Steve<u></u><u></u></p> <p class=3D"MsoNormal"><u></u>=C2=A0<u></u></p> <div style=3D"border-width:medium medium medium 1.5pt;border-style:none non= e none solid;border-color:currentcolor currentcolor currentcolor blue;paddi= ng:0cm 0cm 0cm 4pt"> <div> <div style=3D"border-width:1pt medium medium;border-style:solid none none;b= order-color:rgb(225,225,225) currentcolor currentcolor;padding:3pt 0cm 0cm"> <p class=3D"MsoNormal"><b><span style=3D"font-size:11pt;font-family:"C= alibri",sans-serif">From:</span></b><span style=3D"font-size:11pt;font= -family:"Calibri",sans-serif"> <a href=3D"mailto:vwnc-request@lis= ts.siebelschool.illinois.edu" target=3D"_blank">[email protected]= hool.illinois.edu</a> <<a href=3D"mailto:[email protected]= .illinois.edu" target=3D"_blank">[email protected]= du</a>> <b>On Behalf Of </b>Holger Kleinsorgen<br> <b>Sent:</b> Wednesday, August 27, 2025 12:40 PM<br> <b>To:</b> <a href=3D"mailto:[email protected]" target= =3D"_blank">[email protected]</a><br> <b>Subject:</b> [vwnc] Swiss table implementation<u></u><u></u></span></p> </div> </div> <p class=3D"MsoNormal"><u></u>=C2=A0<u></u></p> <div> <div> <p class=3D"MsoNormal">Hello,<u></u><u></u></p> </div> <div> <p class=3D"MsoNormal"><u></u>=C2=A0<u></u></p> </div> <div> <p class=3D"MsoNormal">has anyone tried to implement a Swiss table dictiona= ry (see=C2=A0<a href=3D"https://urldefense.com/v3/__https:/go.dev/blog/swis= stable__;!!DZ3fjg!6zk_LKh2X8Ni0_GbEirgVYVib_zPSOY6PUzEdmsv4uYFAT00VkL04_e6a= 44V8wAy7_8QaSoHNpF8QsbyTjeiF_LdirjWMBbwfaPpTQ$" target=3D"_blank">https://g= o.dev/blog/swisstable</a>) in Smalltalk? I'm curious if there is a performance benefit without SI= MD instructions.<u></u><u></u></p> </div> <div> <p class=3D"MsoNormal"><u></u>=C2=A0<u></u></p> </div> <div> <p class=3D"MsoNormal">Holger<u></u><u></u></p> </div> <div> <p class=3D"MsoNormal"><u></u>=C2=A0<u></u></p> </div> </div> </div> </div> </div> </div></blockquote></div> --000000000000d3ae01063d97d952--