mirror of
https://github.com/apple/swift.git
synced 2025-12-14 20:36:38 +01:00
80f052e251
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
84 lines
3.8 KiB
Swift
84 lines
3.8 KiB
Swift
//===--- Diffing.swift ----------------------------------------------------===//
|
|
//
|
|
// This source file is part of the Swift.org open source project
|
|
//
|
|
// Copyright (c) 2014 - 2021 Apple Inc. and the Swift project authors
|
|
// Licensed under Apache License v2.0 with Runtime Library Exception
|
|
//
|
|
// See https://swift.org/LICENSE.txt for license information
|
|
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
import TestsUtils
|
|
|
|
let t: [BenchmarkCategory] = [.api]
|
|
public let benchmarks = [
|
|
BenchmarkInfo(
|
|
name: "Diffing.Same",
|
|
runFunction: { diff($0, from: longPangram, to: longPangram) },
|
|
tags: t,
|
|
setUpFunction: { blackHole(longPangram) }),
|
|
BenchmarkInfo(
|
|
name: "Diffing.PangramToAlphabet",
|
|
runFunction: { diff($0, from: longPangram, to: alphabets) },
|
|
tags: t,
|
|
setUpFunction: { blackHole((longPangram, alphabets)) }),
|
|
BenchmarkInfo(
|
|
name: "Diffing.Pangrams",
|
|
runFunction: { diff($0, from:typingPangram, to: longPangram) },
|
|
tags: t,
|
|
setUpFunction: { blackHole((longPangram, typingPangram)) }),
|
|
BenchmarkInfo(
|
|
name: "Diffing.ReversedAlphabets",
|
|
runFunction: { diff($0, from:alphabets, to: alphabetsReversed) },
|
|
tags: t,
|
|
setUpFunction: { blackHole((alphabets, alphabetsReversed)) }),
|
|
BenchmarkInfo(
|
|
name: "Diffing.ReversedLorem",
|
|
runFunction: { diff($0, from: loremIpsum, to: loremReversed) },
|
|
tags: t,
|
|
setUpFunction: { blackHole((loremIpsum, loremReversed)) }),
|
|
BenchmarkInfo(
|
|
name: "Diffing.Disparate",
|
|
runFunction: { diff($0, from: numbersAndSymbols, to: alphabets) },
|
|
tags: t,
|
|
setUpFunction: { blackHole((numbersAndSymbols, alphabets)) }),
|
|
BenchmarkInfo(
|
|
name: "Diffing.Similar",
|
|
runFunction: { diff($0, from: unabridgedLorem, to: loremIpsum) },
|
|
tags: t,
|
|
setUpFunction: { blackHole((unabridgedLorem, loremIpsum)) }),
|
|
BenchmarkInfo(
|
|
name: "Diffing.Large.Similar",
|
|
runFunction: { diff($0, from: bigUnabridgedLorem, to: bigLoremIpsum) },
|
|
tags: t + [.skip],
|
|
setUpFunction: { blackHole((bigUnabridgedLorem, bigLoremIpsum)) }),
|
|
BenchmarkInfo(
|
|
name: "Diffing.Large.Disparate",
|
|
runFunction: { diff($0, from: bigNumbersAndSymbols, to: bigAlphabets) },
|
|
tags: t + [.skip],
|
|
setUpFunction: { blackHole((bigNumbersAndSymbols, bigAlphabets)) }),
|
|
]
|
|
|
|
let numbersAndSymbols = Array("0123456789`~!@#$%^&*()+=_-\"'?/<,>.\\{}'")
|
|
let alphabets = Array("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ")
|
|
let alphabetsReversed = Array(alphabets.reversed())
|
|
let longPangram = Array("This pangram contains four As, one B, two Cs, one D, thirty Es, six Fs, five Gs, seven Hs, eleven Is, one J, one K, two Ls, two Ms, eighteen Ns, fifteen Os, two Ps, one Q, five Rs, twenty-seven Ss, eighteen Ts, two Us, seven Vs, eight Ws, two Xs, three Ys, & one Z")
|
|
let typingPangram = Array("The quick brown fox jumps over the lazy dog")
|
|
let loremIpsum = Array("Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.")
|
|
let unabridgedLorem = Array("Lorem ipsum, quia dolor sit amet consectetur adipisci[ng] velit, sed quia non-numquam [do] eius modi tempora inci[di]dunt, ut labore et dolore magnam aliqua.")
|
|
let loremReversed = Array(loremIpsum.reversed())
|
|
let bigLoremIpsum = Array(repeatElement(loremIpsum, count: 100).joined())
|
|
let bigUnabridgedLorem = Array(repeatElement(unabridgedLorem, count: 100).joined())
|
|
let bigNumbersAndSymbols = Array(repeatElement(numbersAndSymbols, count: 250).joined())
|
|
let bigAlphabets = Array(repeatElement(alphabets, count: 250).joined())
|
|
|
|
@inline(never) func diff(_ n: Int, from older: [Character], to newer: [Character]) {
|
|
if #available(macOS 10.15, iOS 13, tvOS 13, watchOS 6, *) {
|
|
for _ in 1...n {
|
|
blackHole(newer.difference(from: older))
|
|
}
|
|
}
|
|
}
|