106 Commits
Author SHA1 Message Date
Karoy Lorentey f9fe9f44f7 [Benchmarks] Add basic lookup benchmarks for hashed containers 2026-11-18 16:29:40 -08:00
Karoy Lorentey 29fd239474 [Benchmarks] Unconditionally enable unstable traits in swift-collections
Evidently some versions of Xcode have trouble dealing with conditionally forwarded traits.
2026-11-18 16:28:47 -08:00
Karoy Lorentey 017f766cb9 Update package manifest for benchmarks
- Bump required toolchain to 6.4
- Add availability macros for 6.4 and 6.5.
2026-10-01 13:41:06 -07:00
Karoy Lorentey 0ec72a9532 Stop using @_spi attribute and @testable import 2026-09-29 18:32:55 -07:00
Karoy Lorentey f425dffd5b Merge pull request #702 from apple/dn/bit-set-count
Improve `BitSet.count` performance by ~3x
2026-08-18 13:54:33 -07:00
David Nadoba 962d21d92d Mark _Word.allBits as @inlinable 2026-08-14 16:32:50 -07:00
David Nadoba 8a050cd30d Improve BitSet.count performance 2026-08-13 13:52:01 -07:00
inju2403 a3baec1887 [Benchmark] Add OrderedSet<Int> reverse benchmark 2026-06-12 09:41:47 +09:00
Karoy Lorentey 5c8d97dccb Merge pull request #660 from apple/dn/ordered-set-move
[OrderedCollections] Add move operations
2026-06-05 17:45:16 -07:00
David Nadoba 5a6af29d55 [OrderedCollections] Refine move APIs and simplify no-op check 2026-06-05 14:44:22 -07:00
David Nadoba a83773321e [OrderedCollections] Rework move APIs and extend to OrderedDictionary
Reworks the relocation API and extends it to `OrderedDictionary`:

* Renames the index-range move to `moveSubrange(_:to:)` (with a
  `RangeExpression` overload) and the by-value move to `move(contentsOf:to:)`,
  matching the conventions of `removeSubrange`/`insert(_:at:)`. Adds
  `move(fromIndices:to:)`, which takes the source indices directly.
* Factors the element rearrangement into generic
  `UnsafeMutableBufferPointer` operations (rotation / rotation+permutation /
  scatter) so `OrderedDictionary` relocates its keys and values in lockstep
  through the same code, adding only the parallel value move; the hash-table
  maintenance stays entirely in `OrderedSet`.
* The hot path runs in O(*d* + *k*) and falls back to O(`count`) for large
  moves; bucket maintenance chooses targeted updates or a full rebuild by the
  same threshold.
* `move(contentsOf:to:)` ignores elements/keys that aren't present; duplicate
  members are detected and trap.

Adds tests (exhaustive hash-table integrity, value alignment under lifetime
tracking) and move benchmarks for both types.
2026-06-04 22:33:54 -07:00
Karoy Lorentey c86ed20fc1 [Benchmark] Shareable(Set|Dictionary)Benchmarks → Tree$1Benchmarks 2026-06-02 17:57:49 -07:00
Karoy Lorentey b78086e6df [Benchmark] Resolve warnings under Swift 6.4 2026-06-02 17:48:22 -07:00
Karoy Lorentey 7a32c7582b [Benchmark] Enable sorted collection benchmarks, conditional on UnstableSortedCollections 2026-06-02 17:48:04 -07:00
Karoy Lorentey 346ab74f17 [Benchmark] Properly declare module dependencies 2026-06-02 17:47:14 -07:00
Karoy Lorentey 7220421ea8 [Benchmark] Define forwarding traits for swift-collections options 2026-06-02 17:46:53 -07:00
Karoy Lorentey 76f3560f3f [Benchmark] ENABLE_RUST_BENCHMARKS → EnableRustBenchmarks 2026-06-02 17:43:37 -07:00
David Nadoba 508f36f48d [OrderedSet] Add move(_:toOffset:)
Adds two overloads for relocating elements within an `OrderedSet`: one
taking a contiguous `Range<Int>`, and one taking a `Sequence<Element>`.
The moved elements occupy consecutive positions starting at the
destination, in the order they appear in the input.

The hot path runs in O(*d* + *k*) time, where *d* is the distance moved
and *k* is the number of elements moved; the implementation falls back
to O(`count`) for large moves.
2026-05-25 23:01:28 -07:00
Karoy Lorentey 32e7c0e1ec [Benchmark] Add BitSet iteration vs index(after:) benchmarks 2026-04-21 16:28:11 -07:00
Karoy Lorentey 11443c0531 Enforce uniform license headers 2026-03-07 10:26:28 -08:00
Karoy Lorentey 1c69635852 Add SPDX-License-Identifier tags 2026-03-05 19:39:24 -08:00
Karoy Lorentey 11a49663d0 [Benchmarks] Update benchmarking sub-package
- Fix issues with the main package no longer exposing internal helper functions
- Move Rust benchmarks behind an EnableRustBenchmarks trait
- Allow traits to be enabled in `Utils/run-benchmarks.sh` through the BENCHMARK_TRAITS environment variable.
2026-03-05 19:39:22 -08:00
Karoy Lorentey d9b09ecde8 Update copyright dates 2026-03-05 19:39:20 -08:00
Karoy Lorentey 7de30041d3 Delete stray benchmark results files 2026-01-30 16:07:55 -08:00
Alejandro Alonso 3975774393 wip 2025-10-23 15:05:12 -07:00
Karoy Lorentey 05ad8633a8 Merge branch 'release/1.2' 2025-06-24 15:06:25 -07:00
Karoy Lorentey f1b0eba948 [BigString] Add some basic benchmarks 2025-06-23 15:21:36 -07:00
Karoy Lorentey c50c57f52e Bump requirements of nested benchmarking package
- swift-collections-benchmark 0.0.4
- Swift 6.1 minimum toolchain version
- macOS 15 minimum deployment target
2025-05-21 21:20:52 -07:00
Karoy Lorentey ecf44620d2 Also disable SortedCollections benchmarks 2025-05-20 15:23:02 -07:00
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