Commit Graph
77 Commits
Author SHA1 Message Date
Karoy Lorentey 5dd817c33d Merge branch 'release/1.1' 2024-08-05 20:10:26 -07:00
Karoy Lorentey 5e1fe6e8f0 [BigString] Fix accidentally quadratic BigString.init
When ingesting a `String` instance, `BigString` assumes that the input string has a reasonably efficient UTF-8 view.

Unfortunately, that is very much not the case when the input happens to be backed by a bridged NSString object — it appears that in this case, the ingester loop invokes some operation(s) with linear complexity in the size of the entire input, rendering the ingester’s overall complexity quadratic.

The BigString ingester is only expected to operate within a single chunk at the time. It’s unclear precisely which operation triggers the quadratic behavior; ideally we should figure it out and resolve it with a more targeted fix.

In the meantime, a blunt stopgap fix is to force-transcode the input string to UTF-8 at the time the ingester is initialized. This unnecessarily wastes some (temporary) memory on holding the transcoded string, but it avoids the quadratic cliff.
2024-07-15 13:13:44 -07:00
Karoy Lorentey e004cd36fa Merge branch 'release/1.1' into merge.1.1→main
# Conflicts:
#	CMakeLists.txt
#	README.md
2024-02-07 17:35:40 -08:00
Karoy Lorentey 94cf62b3ba Merge pull request #352 from vanvoorden/vanvoorden/tree-dictionary-keys-equality
[TreeDictionary][Keys] Add Equatable and Hashable Conformance to TreeDictionary.Keys
2024-02-06 18:58:46 -08:00
Karoy Lorentey def1b63177 Merge pull request #355 from lorentey/release-1.1-prep
Release preparations for 1.1
2024-02-06 15:43:23 -08:00
Karoy Lorentey 4d1e23176b [Benchmark] Require Swift 5.7 2024-02-02 22:01:15 -08:00
Karoy Lorentey ffa4a58bc1 Update remaining copyright notices 2024-02-02 16:20:22 -08:00
Rick van Voorden 3c9df19f7d add collection equality benchmarks 2024-01-28 15:32:02 -08:00
Rick van Voorden 0e4014c468 tree dictionary keys equality 2024-01-28 13:49:26 -08:00
Karoy Lorentey 1a0ac8c06c Merge branch 'release/1.0' into release/1.1
# Conflicts:
#	Sources/DequeModule/CMakeLists.txt
#	Sources/DequeModule/Deque+Collection.swift
#	Sources/DequeModule/Deque+Sendable.swift
#	Sources/OrderedCollections/OrderedDictionary/OrderedDictionary+Elements.SubSequence.swift
#	Sources/OrderedCollections/OrderedDictionary/OrderedDictionary+Elements.swift
#	Sources/OrderedCollections/OrderedDictionary/OrderedDictionary+Sendable.swift
#	Sources/OrderedCollections/OrderedDictionary/OrderedDictionary+Sequence.swift
#	Sources/OrderedCollections/OrderedDictionary/OrderedDictionary+Values.swift
#	Sources/OrderedCollections/OrderedSet/OrderedSet+Sendable.swift
#	Sources/OrderedCollections/OrderedSet/OrderedSet+SubSequence.swift
#	Sources/OrderedCollections/OrderedSet/OrderedSet+UnorderedView.swift
#	Sources/OrderedCollections/OrderedSet/OrderedSet+UnstableInternals.swift
2023-12-21 15:17:15 -08:00
Karoy Lorentey 1016901f5e Merge pull request #341 from vanvoorden/vanvoorden/deque-equality
[Deque] check deque equality with buffer identity
2023-12-12 21:54:46 -05:00
Karoy Lorentey 8b8a14f0e1 Merge pull request #340 from vanvoorden/vanvoorden/ordered-set-equality
[OrderedSet] forward ordered set equality to elements property
2023-12-12 21:54:30 -05:00
Rick van Voorden 22306e061a check deque equality with buffer identity 2023-12-11 19:30:34 -08:00
Rick van Voorden a71f2cc7d8 ordered dictionary equality benchmarks 2023-12-11 15:58:32 -08:00
Rick van Voorden 90d31f5dec ordered set equality benchmarks 2023-12-11 15:18:20 -08:00
Karoy Lorentey cd03e5b471 Merge branch 'release/1.1'
# Conflicts:
#	Sources/BitCollections/CMakeLists.txt
#	Sources/HashTreeCollections/CMakeLists.txt
2023-11-27 12:02:32 -08:00
Karoy Lorentey 33e2e610f5 Merge branch 'release/1.0' into release/1.1
# Conflicts:
#	Tests/_CollectionsTestSupport/MinimalTypes/MinimalDecoder.swift
2023-11-14 18:06:24 -08:00
Karoy Lorentey 9efa05c583 [benchmark] Update std::function syntax for current C++ 2023-10-02 21:10:12 -07:00
Karoy Lorentey 10a01bd9fb Merge branch 'release/1.1'
# Conflicts:
#	Package.swift
2022-11-30 16:36:22 -08:00
Karoy Lorentey b8ef14f0c0 ShareableHashedCollections → HashTreeCollections 2022-11-28 21:35:37 -08:00
Karoy Lorentey ff85ea9e4f [Benchmarks] Split default huge library up into individual files, one per type 2022-11-09 19:34:58 -08:00
Karoy Lorentey b985c6bc1d [Benchmarks] Update/fix ShareableSet benchmarks 2022-11-07 18:10:16 -08:00
Karoy Lorentey e8fc3ee4cd [PersistentCollections] Rename to SharableHashedCollections
`PersistentSet` → `ShareableSet`
`PersistentDictionary` → `ShareableDictionary`
`PersistentCollections` → `ShareableHashedCollections`
2022-11-07 18:10:16 -08:00
Karoy Lorentey 84e324dc45 [Benchmarks] Add the model diffing tasks to the PersistentSet library 2022-11-06 13:20:50 -08:00
Karoy Lorentey 898d3c9a51 [PersistentCollections] Doc & benchmark updates in preparation of API review 2022-10-31 16:45:42 -07:00
Karoy Lorentey a32048d44e Merge branch 'release/1.1' to ‘main’ 2022-10-28 18:21:18 -07:00
Karoy Lorentey 7dd47aa336 [Benchmark] Work on PeristentSet and PersistentDictionary benchmarks 2022-10-27 18:08:27 -07:00
Karoy Lorentey b1506b6225 [SortedCollections] Remove for now
These are still on track for 1.2.0, but I’ll need to bump them from
the release/1.1 branch.
2022-10-11 17:55:35 -07:00
Karoy Lorentey 33b759b842 [Heap] PriorityQueueModule → HeapModule 2022-10-09 15:44:44 -07:00
Karoy Lorentey 92d1d1297e [PersistentDictionary] Add a quick&dirty memory benchmark
The new executable target `memory-benchmark` collects some memory usage statistics and outputs average memory efficiency for a range of sizes in CSV format.

Bump required toolchain version for benchmarks to Swift 5.5.
2022-09-23 16:47:30 -07:00
Karoy Lorentey 9407eff8ca [PersistentDictionary] Add index striding benchmark 2022-09-23 11:15:46 -07:00
Karoy Lorentey 94d979c523 [Benchmarks] Fix header name in #include 2022-09-23 11:15:26 -07:00
Karoy Lorentey 12e3867ccb [Collections] Allow determining if internal checking is enabled
In the benchmark target, complain loudly if consistency checks
are enabled.
2022-09-19 21:25:07 -07:00
Karoy Lorentey b3227e63ea [PersistentCollections] New benchmarks measuring behavior on string data 2022-09-19 21:24:37 -07:00
Karoy Lorentey 9d113c8c6a [Benchmarks] Update dependencies 2022-09-19 16:59:53 -07:00
Karoy Lorentey b263fb442e [Benchmarks] Move source files under Sources/
This eliminates the need to use path overrides.

Also, explicitly define a product for the “benchmark” executable.
2022-09-19 16:58:25 -07:00
Karoy Lorentey f4dc3aa4a9 Merge branch 'feature/SortedCollections' into release/1.1
# Conflicts:
#	Package.swift
#	Utils/swift-collections.xcworkspace/xcshareddata/xcschemes/SortedCollections.xcscheme
2022-09-19 16:06:24 -07:00
Karoy Lorentey de31437ee5 Merge branch 'feature/PersistentCollections' into release/1.1 2022-09-19 16:02:51 -07:00
Karoy Lorentey 31eca4a02c Merge branch 'feature/BitSet' into release/1.1
# Conflicts:
#	Utils/swift-collections.xcworkspace/xcshareddata/xcschemes/Collections.xcscheme
2022-09-19 16:00:20 -07:00
Karoy Lorentey 1a87233bcd [PersistentCollections] Review & update benchmarks 2022-09-07 17:35:59 -07:00
Karoy Lorentey de5fad7477 Merge pull request #31 from msteindorfer/capsule-collections
Incubate persistent data structures
2022-09-07 09:18:23 -07:00
Michael Steindorfer e2f53441d6 [Capsule] Add subscript(position:) benchmarks 2022-09-06 20:39:38 +02:00
Michael Steindorfer 49283d3251 [Capsule] Remove unchecked variant of initializer 2022-09-06 16:37:23 +02:00
Michael Steindorfer 26b97f95d2 [Capsule] Unify insertion/deletion methods
Note, always tracking discardable result negatively impacts batch
use cases.
2022-09-06 16:11:17 +02:00
Michael Steindorfer 5bc17ffe84 [Capsule] Rename package to PersistentCollections 2022-09-06 13:22:10 +02:00
Michael Steindorfer f6fe3c0658 [Capsule] Add init(uncheckedUniqueKeysWithValues:) benchmark
Further add missing items to the benchmark library.
2022-09-06 09:38:36 +02:00
Michael Steindorfer 8bc5e20b29 [Capsule] Enable Keys and Values view benchmarks 2022-09-05 20:53:41 +02:00
Michael Steindorfer afcd915044 [Capsule] Add persistent dictionary index benchmarks 2022-09-02 09:00:52 +02:00
Karoy Lorentey eb541ed4c6 [Deque] Add direct benchmarks for indexing subscript’s _modify accessor
(cherry picked from commit c82261a529)
2022-08-31 17:13:53 -07:00
Karoy Lorentey c82261a529 [Deque] Add direct benchmarks for indexing subscript’s _modify accessor 2022-08-31 14:59:50 -07:00