Commit Graph

7 Commits

Author SHA1 Message Date
Nate Cook
80f052e251 [stdlib] Switch to a linear-space variant of Myers diffing (#83212)
This changes the implementation for `Collection.difference(from:)` to
use a linear-space complexity variation of the same Myers algorithm. The
new version is similar in execution time to the existing one, but should
alleviate memory pressure when diffing collections where the number of
differences approaches the size of the collection. While the new
algorithm returns a set of changes that is the same size as the previous
version, the specific changes are not guaranteed to be the same.

rdar://155829876
2025-09-19 10:03:26 -07:00
Nate Cook
a14dbd2fd0 Add and enable another large diffing benchmark (#83832)
Enabling both of these despite the long runtime so that I can get an
accurate measure of the change with the new diffing implementation.
After #83212 is merged I will disable these large benchmarks again.
2025-08-21 09:23:29 -05:00
Nate Cook
a390f026b9 Add a diffing benchmark with large inputs (#83248) 2025-07-23 10:54:29 -07:00
Karoy Lorentey
8944591e71 [benchmark] Simplify benchmark registration 2021-09-15 22:08:08 -07:00
Karoy Lorentey
8910b75cfe [benchmark] Stop capitalizing function and variable names 2021-09-15 22:08:07 -07:00
Scott Perry
3e2e4f8b6f Clean up the Diffing and Diffing.Myers benchmarks 2019-07-16 14:39:16 -07:00
Scott Perry
0fc5d6ad31 Performance improvements and availability updates for Collection.difference(from:using:) 2019-06-26 16:55:29 -07:00