RE: Swiss table implementation

--_000_AS8P194MB1998ACD72BDA7C21E2231A45A605AAS8P194MB1998EURP_
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable

From the Go implementation: =E2=80=9COverall, in full application benchmark=
s, 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 S=
malltalk code complexity that wouldn=E2=80=99t eat at least that 1.5%, even=
 if you could avoid the extra cache line hit Martin mentioned.

If you like speed optimizations, try a couple of orders of magnitude improv=
ements 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 customer =
calling SOAP operations without persistent connections, as the TimerEphemer=
onQueue filled up with a 20-minute Timer for each call.

Steve

From: [email protected] <[email protected]=
elschool.illinois.edu> 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://urldefe=
nse.com/v3/__https://go.dev/blog/swisstable__;!!DZ3fjg!7duuaBKkavhssAGehqeQ=
5jLL7SRgrchaei6OXLU_S8LWEsEvlMujBUeb02XfqLBSuvzCUhGP0lZpBearjXdOxXimyHOck-g=
$ <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 perform=
ance benefit without SIMD instructions.

Holger


--_000_AS8P194MB1998ACD72BDA7C21E2231A45A605AAS8P194MB1998EURP_
Content-Type: text/html; charset="utf-8"
Content-Transfer-Encoding: base64

PGh0bWwgeG1sbnM6dj0idXJuOnNjaGVtYXMtbWljcm9zb2Z0LWNvbTp2bWwiIHhtbG5zOm89InVy
bjpzY2hlbWFzLW1pY3Jvc29mdC1jb206b2ZmaWNlOm9mZmljZSIgeG1sbnM6dz0idXJuOnNjaGVt
YXMtbWljcm9zb2Z0LWNvbTpvZmZpY2U6d29yZCIgeG1sbnM6eD0idXJuOnNjaGVtYXMtbWljcm9z
b2Z0LWNvbTpvZmZpY2U6ZXhjZWwiIHhtbG5zOm09Imh0dHA6Ly9zY2hlbWFzLm1pY3Jvc29mdC5j
b20vb2ZmaWNlLzIwMDQvMTIvb21tbCIgeG1sbnM9Imh0dHA6Ly93d3cudzMub3JnL1RSL1JFQy1o
dG1sNDAiPg0KPGhlYWQ+DQo8bWV0YSBodHRwLWVxdWl2PSJDb250ZW50LVR5cGUiIGNvbnRlbnQ9
InRleHQvaHRtbDsgY2hhcnNldD11dGYtOCI+DQo8bWV0YSBuYW1lPSJHZW5lcmF0b3IiIGNvbnRl
bnQ9Ik1pY3Jvc29mdCBXb3JkIDE1IChmaWx0ZXJlZCBtZWRpdW0pIj4NCjxzdHlsZT48IS0tDQov
KiBGb250IERlZmluaXRpb25zICovDQpAZm9udC1mYWNlDQoJe2ZvbnQtZmFtaWx5OiJDYW1icmlh
IE1hdGgiOw0KCXBhbm9zZS0xOjIgNCA1IDMgNSA0IDYgMyAyIDQ7fQ0KQGZvbnQtZmFjZQ0KCXtm
b250LWZhbWlseTpDYWxpYnJpOw0KCXBhbm9zZS0xOjIgMTUgNSAyIDIgMiA0IDMgMiA0O30NCkBm
b250LWZhY2UNCgl7Zm9udC1mYW1pbHk6QXB0b3M7fQ0KLyogU3R5bGUgRGVmaW5pdGlvbnMgKi8N
CnAuTXNvTm9ybWFsLCBsaS5Nc29Ob3JtYWwsIGRpdi5Nc29Ob3JtYWwNCgl7bWFyZ2luOjBjbTsN
Cglmb250LXNpemU6MTIuMHB0Ow0KCWZvbnQtZmFtaWx5OiJBcHRvcyIsc2Fucy1zZXJpZjt9DQph
OmxpbmssIHNwYW4uTXNvSHlwZXJsaW5rDQoJe21zby1zdHlsZS1wcmlvcml0eTo5OTsNCgljb2xv
cjpibHVlOw0KCXRleHQtZGVjb3JhdGlvbjp1bmRlcmxpbmU7fQ0Kc3Bhbi5FbWFpbFN0eWxlMTkN
Cgl7bXNvLXN0eWxlLXR5cGU6cGVyc29uYWwtY29tcG9zZTsNCglmb250LWZhbWlseToiQXB0b3Mi
LHNhbnMtc2VyaWY7DQoJY29sb3I6d2luZG93dGV4dDt9DQouTXNvQ2hwRGVmYXVsdA0KCXttc28t
c3R5bGUtdHlwZTpleHBvcnQtb25seTt9DQpAcGFnZSBXb3JkU2VjdGlvbjENCgl7c2l6ZTo2MTIu
MHB0IDc5Mi4wcHQ7DQoJbWFyZ2luOjcyLjBwdCA3Mi4wcHQgNzIuMHB0IDcyLjBwdDt9DQpkaXYu
V29yZFNlY3Rpb24xDQoJe3BhZ2U6V29yZFNlY3Rpb24xO30NCi0tPjwvc3R5bGU+PCEtLVtpZiBn
dGUgbXNvIDldPjx4bWw+DQo8bzpzaGFwZWRlZmF1bHRzIHY6ZXh0PSJlZGl0IiBzcGlkbWF4PSIx
MDI2IiAvPg0KPC94bWw+PCFbZW5kaWZdLS0+PCEtLVtpZiBndGUgbXNvIDldPjx4bWw+DQo8bzpz
aGFwZWxheW91dCB2OmV4dD0iZWRpdCI+DQo8bzppZG1hcCB2OmV4dD0iZWRpdCIgZGF0YT0iMSIg
Lz4NCjwvbzpzaGFwZWxheW91dD48L3htbD48IVtlbmRpZl0tLT4NCjwvaGVhZD4NCjxib2R5IGxh
bmc9IkVOLVVTIiBsaW5rPSJibHVlIiB2bGluaz0icHVycGxlIiBzdHlsZT0id29yZC13cmFwOmJy
ZWFrLXdvcmQiPg0KPGRpdiBjbGFzcz0iV29yZFNlY3Rpb24xIj4NCjxwIGNsYXNzPSJNc29Ob3Jt
YWwiPkZyb20gdGhlIEdvIGltcGxlbWVudGF0aW9uOiDigJxPdmVyYWxsLCBpbiBmdWxsIGFwcGxp
Y2F0aW9uIGJlbmNobWFya3MsIHdlIGZvdW5kIGEgZ2VvbWV0cmljIG1lYW4gQ1BVIHRpbWUgaW1w
cm92ZW1lbnQgb2YgYXJvdW5kIDEuNSUu4oCdPG86cD48L286cD48L3A+DQo8cCBjbGFzcz0iTXNv
Tm9ybWFsIj5BbmQgdGhhdOKAmXMgd2l0aCBTSU1EIGluc3RydWN0aW9ucy4gSGFyZCB0byBpbWFn
aW5lIGFuIGluY3JlYXNlIGluIFNtYWxsdGFsayBjb2RlIGNvbXBsZXhpdHkgdGhhdCB3b3VsZG7i
gJl0IGVhdCBhdCBsZWFzdCB0aGF0IDEuNSUsIGV2ZW4gaWYgeW91IGNvdWxkIGF2b2lkIHRoZSBl
eHRyYSBjYWNoZSBsaW5lIGhpdCBNYXJ0aW4gbWVudGlvbmVkLjxvOnA+PC9vOnA+PC9wPg0KPHAg
Y2xhc3M9Ik1zb05vcm1hbCI+PG86cD4mbmJzcDs8L286cD48L3A+DQo8cCBjbGFzcz0iTXNvTm9y
bWFsIj5JZiB5b3UgbGlrZSBzcGVlZCBvcHRpbWl6YXRpb25zLCB0cnkgYSBjb3VwbGUgb2Ygb3Jk
ZXJzIG9mIG1hZ25pdHVkZSBpbXByb3ZlbWVudHMgaW4gYWRkaW5nIHRvIHRoZSBlbmQgb2YgYSBT
b3J0ZWRDb2xsZWN0aW9uOjxvOnA+PC9vOnA+PC9wPg0KPHAgY2xhc3M9Ik1zb05vcm1hbCI+PG86
cD4mbmJzcDs8L286cD48L3A+DQo8cCBjbGFzcz0iTXNvTm9ybWFsIj5zIDo9IFNvcnRlZENvbGxl
Y3Rpb24gbmV3LjxvOnA+PC9vOnA+PC9wPg0KPHAgY2xhc3M9Ik1zb05vcm1hbCI+VGltZSBtaWxs
aXNlY29uZHNUb1J1bjogWygxIHRvOiAxZTYgYnk6IDEpIGRvOiBbOml4IHwgcyBhZGQ6IGl4XV0u
PG86cD48L286cD48L3A+DQo8cCBjbGFzcz0iTXNvTm9ybWFsIj4mcXVvdDs0NDM3NiAtJmd0OyA0
NjgmcXVvdDs8bzpwPjwvbzpwPjwvcD4NCjxwIGNsYXNzPSJNc29Ob3JtYWwiPjxvOnA+Jm5ic3A7
PC9vOnA+PC9wPg0KPHAgY2xhc3M9Ik1zb05vcm1hbCI+U29ydGVkQ29sbGVjdGlvbiZndDsmZ3Q7
aW5zZXJ0OiBhbk9iamVjdCBiZWZvcmU6IG9yaWdpbmFsU3BvdCA8bzpwPg0KPC9vOnA+PC9wPg0K
PHAgY2xhc3M9Ik1zb05vcm1hbCI+Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7
Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7IHwg
c3BvdCB8PG86cD48L286cD48L3A+DQo8cCBjbGFzcz0iTXNvTm9ybWFsIj4mbmJzcDsmbmJzcDsm
bmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJz
cDsmbmJzcDsmbmJzcDsmbmJzcDsgc3BvdCA6PSBvcmlnaW5hbFNwb3QuPG86cD48L286cD48L3A+
DQo8cCBjbGFzcz0iTXNvTm9ybWFsIj4mbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJz
cDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsg
c3BvdCAmZ3Q7IHNlbGYgYmFzaWNTaXplIGlmVHJ1ZTogPG86cD48L286cD48L3A+DQo8cCBjbGFz
cz0iTXNvTm9ybWFsIj4mbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsm
bmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDsgJm5ic3A7Jm5i
c3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7
Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7ICZuYnNwO1tzZWxmIG1ha2VSb29tQXRMYXN0LjxvOnA+
PC9vOnA+PC9wPg0KPHAgY2xhc3M9Ik1zb05vcm1hbCI+Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7
Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5ic3A7Jm5i
c3A7Jm5ic3A7ICZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNw
OyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyBzcG90IDo9IGxhc3RJ
bmRleCsxXS48bzpwPjwvbzpwPjwvcD4NCjxwIGNsYXNzPSJNc29Ob3JtYWwiPiZuYnNwOyZuYnNw
OyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZuYnNwOyZu
YnNwOyZuYnNwOyZuYnNwOyZuYnNwOyBec3VwZXIgaW5zZXJ0OiBhbk9iamVjdCBiZWZvcmU6IHNw
b3Q8bzpwPjwvbzpwPjwvcD4NCjxwIGNsYXNzPSJNc29Ob3JtYWwiPjxvOnA+Jm5ic3A7PC9vOnA+
PC9wPg0KPHAgY2xhc3M9Ik1zb05vcm1hbCI+SXTigJlzIGEgc3VycHJpc2luZ2x5IGNvbW1vbiBz
cGVjaWFsIGNhc2U6IHdlIGhpdCBpdCB3aXRoIGEgY3VzdG9tZXIgY2FsbGluZyBTT0FQIG9wZXJh
dGlvbnMgd2l0aG91dCBwZXJzaXN0ZW50IGNvbm5lY3Rpb25zLCBhcyB0aGUgVGltZXJFcGhlbWVy
b25RdWV1ZSBmaWxsZWQgdXAgd2l0aCBhIDIwLW1pbnV0ZSBUaW1lciBmb3IgZWFjaCBjYWxsLg0K
PG86cD48L286cD48L3A+DQo8cCBjbGFzcz0iTXNvTm9ybWFsIj48bzpwPiZuYnNwOzwvbzpwPjwv
cD4NCjxwIGNsYXNzPSJNc29Ob3JtYWwiPlN0ZXZlPG86cD48L286cD48L3A+DQo8cCBjbGFzcz0i
TXNvTm9ybWFsIj48bzpwPiZuYnNwOzwvbzpwPjwvcD4NCjxkaXYgc3R5bGU9ImJvcmRlcjpub25l
O2JvcmRlci1sZWZ0OnNvbGlkIGJsdWUgMS41cHQ7cGFkZGluZzowY20gMGNtIDBjbSA0LjBwdCI+
DQo8ZGl2Pg0KPGRpdiBzdHlsZT0iYm9yZGVyOm5vbmU7Ym9yZGVyLXRvcDpzb2xpZCAjRTFFMUUx
IDEuMHB0O3BhZGRpbmc6My4wcHQgMGNtIDBjbSAwY20iPg0KPHAgY2xhc3M9Ik1zb05vcm1hbCI+
PGI+PHNwYW4gc3R5bGU9ImZvbnQtc2l6ZToxMS4wcHQ7Zm9udC1mYW1pbHk6JnF1b3Q7Q2FsaWJy
aSZxdW90OyxzYW5zLXNlcmlmIj5Gcm9tOjwvc3Bhbj48L2I+PHNwYW4gc3R5bGU9ImZvbnQtc2l6
ZToxMS4wcHQ7Zm9udC1mYW1pbHk6JnF1b3Q7Q2FsaWJyaSZxdW90OyxzYW5zLXNlcmlmIj4gdndu
Yy1yZXF1ZXN0QGxpc3RzLnNpZWJlbHNjaG9vbC5pbGxpbm9pcy5lZHUgJmx0O3Z3bmMtcmVxdWVz
dEBsaXN0cy5zaWViZWxzY2hvb2wuaWxsaW5vaXMuZWR1Jmd0Ow0KPGI+T24gQmVoYWxmIE9mIDwv
Yj5Ib2xnZXIgS2xlaW5zb3JnZW48YnI+DQo8Yj5TZW50OjwvYj4gV2VkbmVzZGF5LCBBdWd1c3Qg
MjcsIDIwMjUgMTI6NDAgUE08YnI+DQo8Yj5Ubzo8L2I+IHZ3bmNAbGlzdHMuc2llYmVsc2Nob29s
LmlsbGlub2lzLmVkdTxicj4NCjxiPlN1YmplY3Q6PC9iPiBbdnduY10gU3dpc3MgdGFibGUgaW1w
bGVtZW50YXRpb248bzpwPjwvbzpwPjwvc3Bhbj48L3A+DQo8L2Rpdj4NCjwvZGl2Pg0KPHAgY2xh
c3M9Ik1zb05vcm1hbCI+PG86cD4mbmJzcDs8L286cD48L3A+DQo8ZGl2Pg0KPGRpdj4NCjxwIGNs
YXNzPSJNc29Ob3JtYWwiPkhlbGxvLDxvOnA+PC9vOnA+PC9wPg0KPC9kaXY+DQo8ZGl2Pg0KPHAg
Y2xhc3M9Ik1zb05vcm1hbCI+PG86cD4mbmJzcDs8L286cD48L3A+DQo8L2Rpdj4NCjxkaXY+DQo8
cCBjbGFzcz0iTXNvTm9ybWFsIj5oYXMgYW55b25lIHRyaWVkIHRvIGltcGxlbWVudCBhIFN3aXNz
IHRhYmxlIGRpY3Rpb25hcnkgKHNlZSZuYnNwOzxhIGhyZWY9Imh0dHBzOi8vdXJsZGVmZW5zZS5j
b20vdjMvX19odHRwczovZ28uZGV2L2Jsb2cvc3dpc3N0YWJsZV9fOyEhRFozZmpnITZ6a19MS2gy
WDhOaTBfR2JFaXJnVllWaWJfelBTT1k2UFV6RWRtc3Y0dVlGQVQwMFZrTDA0X2U2YTQ0Vjh3QXk3
XzhRYVNvSE5wRjhRc2J5VGplaUZfTGRpcmpXTUJid2ZhUHBUUSQiPmh0dHBzOi8vZ28uZGV2L2Js
b2cvc3dpc3N0YWJsZTwvYT4pDQogaW4gU21hbGx0YWxrPyBJJ20gY3VyaW91cyBpZiB0aGVyZSBp
cyBhIHBlcmZvcm1hbmNlIGJlbmVmaXQgd2l0aG91dCBTSU1EIGluc3RydWN0aW9ucy48bzpwPjwv
bzpwPjwvcD4NCjwvZGl2Pg0KPGRpdj4NCjxwIGNsYXNzPSJNc29Ob3JtYWwiPjxvOnA+Jm5ic3A7
PC9vOnA+PC9wPg0KPC9kaXY+DQo8ZGl2Pg0KPHAgY2xhc3M9Ik1zb05vcm1hbCI+SG9sZ2VyPG86
cD48L286cD48L3A+DQo8L2Rpdj4NCjxkaXY+DQo8cCBjbGFzcz0iTXNvTm9ybWFsIj48bzpwPiZu
YnNwOzwvbzpwPjwvcD4NCjwvZGl2Pg0KPC9kaXY+DQo8L2Rpdj4NCjwvZGl2Pg0KPC9ib2R5Pg0K
PC9odG1sPg0K

--_000_AS8P194MB1998ACD72BDA7C21E2231A45A605AAS8P194MB1998EURP_--