Karoy Lorentey
16e7715941
[BasicContainers] Speed up removals from hashed containers
2026-03-10 23:50:41 -07:00
Karoy Lorentey
a8cf90f49c
[BasicContainers] Hashed containers: slightly improve maxProbeLength after removals
2026-03-10 23:50:40 -07:00
Karoy Lorentey
5636b32db7
[BasicContainers] Scramble small hashed containers
...
Don’t just append new items to the end of storage — it misleads clients into assuming that the containers preserve insertion order, when they most certainly don’t do that.
Instead, insert new items into the middle of storage, using an extra swap.
2026-03-10 23:06:08 -07:00
Karoy Lorentey
e69d570c59
[BasicContainers] Implement shortcut for insertions
...
We don’t need to calculate the probe length of the item currently occupying the new item’s ideal bucket — it cannot possibly be lower than the new item’s. This spares one hash operation during insertions that result in a hash collision.
2026-03-10 23:06:08 -07:00
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
634a0ae766
[BasicContainers] Implement _checkInvariants on hashed containers
2026-03-10 23:04:49 -07:00
Karoy Lorentey
1c69635852
Add SPDX-License-Identifier tags
2026-03-05 19:39:24 -08:00
Karoy Lorentey
cef50eee26
[BasicContainers] Fix incorrect wraparound implementation in hashed container insertions with NO_ROBIN_HOOD_HASHING
2026-03-05 15:30:10 -08:00
Karoy Lorentey
ffdc48e67e
[BasicContainers] Finalize requirements for hashed containers
...
- UnstableNoncopyableKeys → UnstableHashedContainers
- Delete the GeneralizedEquatable and GeneralizedHashable protocols, replacing them with the standard generalizations in the 6.4 stdlib
- Require Swift 6.4 for {Rigid,Unique}{Set,Dictionary}.
2026-03-03 16:01:45 -08:00
Karoy Lorentey
978ebeda02
[BasicContainers] Fix spelling of a source file
...
Renaming `_Htable+Debugging.swift` to `_HTable+Debugging.swift` did not stick — rename the file to `_HTable+Debug.swift` to get rid of the lowercase t for good.
2026-03-02 16:14:20 -08:00
Karoy Lorentey
318ac805ea
[BasicContainers] Add Index to hashed containers. Implement dictionary iteration using indices
2026-02-27 12:19:54 -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
d318a65867
[BasicContainers] Add UniqueDictionary
2026-02-19 17:57:34 -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
0ed3abd92c
Fix some build errors in some configurations
2026-02-16 17:16:02 -08:00
Karoy Lorentey
bf9a7033a0
[BasicContainers] Add early drafts for RigidSet/RigidDictionary
2026-02-16 17:15:59 -08:00