Karoy Lorentey
2a53ad50b0
[BasicContainers] Fix insertion algorithm
...
Due to a number of cascading off-by-one errors, the maximum probe length could end up getting set lower than the actual value, _sometimes_ rendering some items unreachable.
Weirdly, the issue seems to be rare enough that it somehow never triggered in any of my previous test runs.
2026-03-10 23:06:07 -07:00
Karoy Lorentey
1c69635852
Add SPDX-License-Identifier tags
2026-03-05 19:39:24 -08:00
Karoy Lorentey
0538000ffd
[BasicContainers] Hashed containers: Add Equatable/Hashable conformances and related methods
2026-02-24 16:40:45 -08:00
Karoy Lorentey
3941dab5b0
[BasicContainers] Implement removals on RigidSet and UniqueSet
...
Dictionaries are still to be done.
2026-02-20 18:19:51 -08:00
Karoy Lorentey
a1902c30aa
[BasicContainers] Make _HTable nonfrozen and most of its operations noninlinable
...
This is a nongeneric type, so it makes sense to see if Swift has matured enough to use opaque/resilient types in high-performance contexts. It would be ideal if the core hash table implementation would remain flexible.
We may need to sprinkle some effect attributes over these.
2026-02-19 17:56:22 -08:00
Karoy Lorentey
0cf34cc3a9
[BasicContainers] Improved debug output for hashed containers
...
- Allow bitmap visualization to be included/omitted as needed
- Visualize chain length distribution for both successful and unsuccessful lookups
Check out this sample test output for Robin Hood hashing:
```
⌗ large@11 1536/1792/2048, maxProbeLength: 11, totalProbeLength: 3712, maxOccupiedRun: 68
├╴[00000000] □□■■■■□□∙□■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■□■■■■■■∙□□□■□■□□∙□□□■■□■■∙■■■■■■■■
├╴[00000064] □□■□□■■■∙■■■■□■□□∙□■■■■■■■∙■■■■■■■■∙■■□□□□■□∙■□■□■■■■∙■■■■■■□□∙■■■■■■■■
├╴[00000128] ■■■■■■■■∙■■■□□□■□∙■■□■□■■□∙□■■■■■□■∙■■■■■■■■∙□■■■■■■■∙■■■■□■□■∙■□■□□■□□
├╴[00000192] ■□■■□■■■∙■■■■□■□■∙□□□□□■■□∙■■■■■■■■∙■■■□■■□■∙□■□■■□□■∙■■■■■■■■∙■■■■■■■■
├╴[00000256] ■■■■■■□□∙■■■■■■■□∙□■■■■■■□∙□■■■■■■□∙□□■■□□■□∙□□□■■■■□∙□■■■■□■■∙■■■■■■■■
├╴[00000320] ■■■■■■■■∙□■■■■■■■∙■■■■■■■□∙□■■□□■□□∙□□□■■□□■∙■■■■■□■□∙■□■■■■■□∙■■■■■■■■
├╴[00000384] ■■■■■■■■∙■■■■■□□■∙□□■■■■□□∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙□■■□□■□■∙□□■■□■■■
├╴[00000448] ■■■■□■■■∙■■■□■■■□∙□□□■□■■■∙■■■□□■■■∙■■■□□□□□∙□■■■■■■■∙■■■■■■■■∙■■■■■■■■
├╴[00000512] ■■■■■□□□∙□□■■□■■■∙■■■□■■■■∙■■■■■■■■∙■■■■■■■□∙□■■■■□□■∙■■■■■■■■∙■■■■■■■■
├╴[00000576] □□□■■■□■∙■■■□■■■■∙■■■■■■■■∙■■■■■■■■∙■■□■■■■■∙■■■■■■■■∙■■□□■□□□∙■■■□□□■□
├╴[00000640] □■■□□■■□∙□□□□■■■■∙□■■□■■■□∙□■■□■■■■∙■■■■■■■■∙■□□■■■■■∙■■■■■□□□∙■■■■■■■□
├╴[00000704] ■■■■■■■□∙■■■■□□□■∙■■□■□■■■∙■■■■■■■■∙■■■■□■■■∙□□□■□■■■∙□□□■□□□□∙□□□■□■■■
├╴[00000768] □■■■■■□■∙□■■□□□■■∙■■■■■■■□∙■■■■■■■■∙■■■■■■■□∙□■■■□■■□∙■□■■□■■■∙■■■■□■□■
├╴[00000832] ■□□■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■□□∙□□■■■■■■∙□□■■■■■■∙■■■■■■■■∙□■□■■■■■
├╴[00000896] ■■■■■■■■∙■■■■■□□■∙■■■□□□□■∙■■□□■■■■∙■□□■■■■□∙■■■□□■■□∙□□■■□■■■∙□■□□■■■■
├╴[00000960] ■■■■■□■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■□∙□■□■■■■■∙■■■■□□■■
├╴[00001024] ■■■■■■□□∙■■■■□■■□∙■■■■■■■□∙□□□■■■□□∙■■■□■■□■∙■□■■□□□■∙■■■■■■■■∙□□□□□□□□
├╴[00001088] ■■□□□□■□∙■■□□□□□■∙■□□■■■■■∙■■■□□□□■∙■■■■■■■■∙■■■■■■■■∙■■■■□□□□∙■■□■□■■■
├╴[00001152] ■■■□□■■□∙□■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■□■■□■■■∙■□■■□■■□∙□■■■■□■■
├╴[00001216] ■■■■■■■■∙■■□■□■■■∙■■■■■■■■∙□□■■□□□■∙□□□□□□□□∙□□■■■■■■∙■■■■■■■■∙■■■□□■■■
├╴[00001280] ■■■■■■■□∙■■□■■■■■∙■■■■■■□□∙■□□■■■■■∙■■■■■■■■∙■□□■□■□■∙■■■■■■■■∙■■■■■■■■
├╴[00001344] ■■■■■■■■∙■□■□■■□□∙■■■■□■□□∙□■■□■□□■∙□■□■■■■■∙■■■□■■■□∙□□■■■■■■∙■■■■■■■■
├╴[00001408] ■■■■■■■■∙■■■■■■■■∙■■■■■□□■∙■■■□■■■■∙■■□■■■■■∙■■■□■■■■∙■■□□■□□□∙■□■■■■■■
├╴[00001472] ■■■■■□■□∙■■□□□□□■∙□□□□□■■□∙■□□■■□■□∙■■■■■■■■∙■■■■■■■■∙□□□□■■■■∙■□■□□■■■
├╴[00001536] ■■■■■■■■∙□□□■■□■□∙□■■□■■□□∙□■□■■□□□∙■■■■■□□■∙■□■■■■■■∙■■■■■■■■∙■□□■□□□□
├╴[00001600] ■■■■■■■■∙■■■■□□■□∙□□■■□■■■∙■■■■■■■□∙□■□□■■□■∙■□■■■□■■∙■■■■■■■■∙□□■■■■■■
├╴[00001664] ■■■■■■■■∙□■■■□□■■∙■■■□■□■□∙■■■■■■□■∙■■■□■■■■∙■■■■■■■□∙□□□□■■■■∙■■■■□■■■
├╴[00001728] ■■■■■■■■∙■□□■■■■■∙■■□□■■□□∙■■■■■■■■∙■■■□□□■■∙□□■■■■■■∙■■■■■■■■∙■■■■■■■■
├╴[00001792] ■■■■■■■■∙■■■■■■■■∙■□□□■■□■∙□□■■□□□□∙□■■□■□□■∙□□■■■■□□∙■■■■■■■■∙■■■■■■■■
├╴[00001856] ■■■■■■■□∙■■■■■■■□∙□■□■□■■□∙■□□□■■■■∙■□■■□■■□∙□□■□■□■■∙■□□□□■■■∙■■■■■■■■
├╴[00001920] ■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■■■■■■■■∙■□□■□■□□
└╴[00001984] ■□□■□□■■∙□■■■■■■□∙□□□□■■■■∙■□□□■■■■∙■■■■■■■■∙■■□■□■■■∙■■■□■■□□∙■□□■■□■□
Chain length distribution (for successful lookups):
AVG: 2.416
1: **************************************************************************** 549
2: ******************************************************** 408
3: ************************************* 264
4: ******************** 142
5: ************** 96
6: ******* 51
7: *** 17
8: * 4
9: * 1
10: * 3
11: * 1
Chain length distribution (for unsuccessful lookups):
AVG: 4.428
0: **************************************************************************** 511
1: **************************************** 269
2: ***************************** 191
3: ******************* 129
4: ***************** 111
5: ************** 94
6: ************* 85
7: *********** 70
8: ********* 60
9: ********* 55
10: ******** 50
11: ************************************************************** 422
```
2026-02-19 12:10:26 -08:00
Karoy Lorentey
099aa3b312
[BasicContainers] Add UniqueSet
2026-02-18 22:05:22 -08:00
Karoy Lorentey
bf9a7033a0
[BasicContainers] Add early drafts for RigidSet/RigidDictionary
2026-02-16 17:15:59 -08:00