Commit Graph
19 Commits
Author SHA1 Message Date
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