sort-benchmark-results.md

Sort benchmark results

All times are in milliseconds.

Proposed merge sort

=========================================
Int
=========================================
Shape                      1000    100000
-----------------------------------------
ascending                 0.705     1.779
descending                0.020     1.776
mostly sorted             0.029     2.904
shuffled                  0.076     9.402
random (1...100)          0.075     7.245
random (full range)       0.078     9.186
new at end                0.024     1.849
pyramid                   0.024     1.752
double pyramid            0.025     1.875
valley                    0.024     1.900
double valley             0.025     1.987
many runs                 0.048     2.090
all equal                 0.022     1.754

=========================================
Large structs
=========================================
Shape                      1000    100000
-----------------------------------------
ascending                 0.053     3.865
descending                0.048     3.064
mostly sorted             0.058    10.505
shuffled                  0.183    24.660
random (1...100)          0.178    23.190
random (full range)       0.193    24.672
new at end                0.027     3.487
pyramid                   0.033     4.163
double pyramid            0.048     5.241
valley                    0.039     4.468
double valley             0.043     5.416
many runs                 0.118     7.438
all equal                 0.050     2.708

=========================================
Reference types
=========================================
Shape                      1000    100000
-----------------------------------------
ascending                 0.089     8.284
descending                0.090     8.494
mostly sorted             0.153    46.613
shuffled                  0.806   106.037
random (1...100)          0.850   103.682
random (full range)       0.814   100.645
new at end                0.124    12.975
pyramid                   0.126    12.354
double pyramid            0.177    16.930
valley                    0.125    12.762
double valley             0.176    16.018
many runs                 0.460    25.072
all equal                 0.089     8.168

=========================================
Long strings
=========================================
Shape                      1000    100000
-----------------------------------------
ascending                 2.843   185.441
descending                1.727   191.978
mostly sorted             3.838   902.216
shuffled                 16.336  2138.377
random (1...100)         16.317  2052.829
random (full range)      16.722  2106.712
new at end                3.501   290.673
pyramid                   3.482   278.084
double pyramid            5.649   377.398
valley                    3.359   241.646
double valley             5.542   364.750
many runs                12.180   578.856
all equal                 0.819    96.406

=========================================
NSObject subclasses
=========================================
Shape                      1000    100000
-----------------------------------------
ascending                 0.065     5.595
descending                0.071     5.634
mostly sorted             0.156    41.740
shuffled                  0.817    98.991
random (1...100)          0.749    77.971
random (full range)       0.924   124.055
new at end                0.130    10.371
pyramid                   0.086     8.378
double pyramid            0.125    11.997
valley                    0.094     8.255
double valley             0.105    10.393
many runs                 0.464    17.103
all equal                 0.031     2.485

================================
Comparisons per 10,000 elements
================================
Shape                Comparisons
--------------------------------
ascending                   9999
descending                  9999
mostly sorted              71921
shuffled                  185386
random (1...100)          184876
random (full range)       184818
new at end                 20837
pyramid                    19998
double pyramid             32492
valley                     19998
double valley              29993
many runs                  55190
all equal                   9999

Sort is stable in all cases

Current sort

=========================================
Int
=========================================
Shape                      1000    100000
-----------------------------------------
ascending                 0.017     2.261
descending                0.030     3.854
mostly sorted             0.037     9.317
shuffled                  0.132    20.930
random (1...100)          0.098    12.551
random (full range)       0.132    21.122
new at end                0.075     8.362
pyramid                   0.198    37.752
double pyramid            0.130    22.566
valley                    0.177    36.718
double valley             0.154    19.902
many runs                 0.093    14.136
all equal                 0.045     5.362

=========================================
Large structs
=========================================
Shape                      1000    100000
-----------------------------------------
ascending                 0.025     4.349
descending                0.059     7.287
mostly sorted             0.058    13.950
shuffled                  0.192    33.760
random (1...100)          0.158    18.996
random (full range)       0.194    33.256
new at end                0.120    15.255
pyramid                   0.234    51.359
double pyramid            0.201    37.561
valley                    0.231    50.923
double valley             0.179    34.701
many runs                 0.145    26.565
all equal                 0.056    13.142

=========================================
Reference types
=========================================
Shape                      1000    100000
-----------------------------------------
ascending                 0.179    32.385
descending                0.201    34.383
mostly sorted             0.269    52.983
shuffled                  0.432    71.421
random (1...100)          0.334    93.449
random (full range)       0.453    74.121
new at end                0.375    54.909
pyramid                   1.009   226.178
double pyramid            0.656   127.816
valley                    0.944   218.427
double valley             0.566   106.047
many runs                 0.345    62.191
all equal                 0.578    86.671

=========================================
Long strings
=========================================
Shape                      1000    100000
-----------------------------------------
ascending                 8.079  1507.175
descending                8.063  1414.811
mostly sorted             7.497  1388.045
shuffled                  8.430  1638.150
random (1...100)          6.952  2878.967
random (full range)       8.961  1688.647
new at end                7.850  1493.320
pyramid                   9.961  1782.700
double pyramid           11.222  1823.674
valley                    9.424  1736.871
double valley             8.612  1650.692
many runs                 7.527  1570.025
all equal                15.470  2740.747

=========================================
NSObject subclasses
=========================================
Shape                      1000    100000
-----------------------------------------
ascending                 0.285    56.505
descending                0.307    57.989
mostly sorted             0.394    83.645
shuffled                  0.582    96.893
random (1...100)          0.435    70.496
random (full range)       0.878   148.195
new at end                0.495    78.378
pyramid                   1.304   274.418
double pyramid            0.912   182.413
valley                    1.206   263.054
double valley             0.740   154.503
many runs                 0.445    87.551
all equal                 0.309    41.852

================================
Comparisons per 10,000 elements
================================
Shape                Comparisons
--------------------------------
ascending                 104538
descending                104556
mostly sorted             139940
shuffled                  149398
random (1...100)          268503
random (full range)       149822
new at end                144282
pyramid                   404245
double pyramid            277332
valley                    383303
double valley             236871
many runs                 143149
all equal                 289591

Sort was unstable in: valley, double valley, many runs, all equal, pyramid, new at end, double pyramid, random (1...100), mostly sorted

sort-benchmark.swift.gyb

//
//  sort-benchmark.swift
//

import Foundation

//===----------------------------------------------------------------------===//
// Helper functions
//===----------------------------------------------------------------------===//

func time(_ body: () -> ()) -> Double {
  return time_milliseconds(body) / 1_000
}

func time_milliseconds(_ body: () -> ()) -> Double {
  return time_nanoseconds(body) / 1_000
}

func time_nanoseconds(_ body: () -> ()) -> Double {
  let start = mach_absolute_time()
  body()
  let end = mach_absolute_time()
  return Double(end - start) / 1_000
}

extension Array where Element == Double {
  func mean() -> Double {
    return reduce(0, +) / Double(count)
  }
  
  func stddev() -> Double {
    let m = mean()
    return self
      .map({ ($0 - m) * ($0 - m) })
      .reduce(0, +)
      .squareRoot()
  }
}

// Check of sortedness for comparable types
func check<C: Collection>(_ c: C) -> Bool where C.Element: Comparable {
    return zip(c, c.dropFirst()).allSatisfy(<=)
}

//===----------------------------------------------------------------------===//
// Data shape
//===----------------------------------------------------------------------===//

enum DataShape: String, CaseIterable {
  /// Unique values in ascending order.
  case ascending
  /// Unique values in descending order.
  case descending
  /// Values in ascending order with random ~1% replaced w/ random value.
  case mostlySorted = "mostly sorted"
  /// Unique values in random order.
  case shuffled
  /// The values 1-100, randomized (lots of equal values at large N).
  case random1To100 = "random (1...100)"
  /// The value Int.min to Int.max, randomized.
  case randomMinToMax = "random (full range)"
  /// Unique values in ascending order, with the last 1% random.
  case newAtEnd = "new at end"
  /// Ascending order to middle, then descending.
  case pyramid
  /// Like .pyramid, but doubled. ^^
  case doublePyramid = "double pyramid"
  /// Descending order to middle, then ascending.
  case valley
  /// Like .valley, but doubled. vv
  case doubleValley = "double valley"
  /// Lots of ascending runs of length 1-1000
  case manyRuns = "many runs"
  /// The same value, repeated.
  case equal = "all equal"
  
  func generate(_ size: Int) -> [Int] {
    switch self {
    case .ascending:
      return Array(0..<size)
    case .descending:
      return (0..<size).reversed()
    case .mostlySorted:
      return Array(0 ..< size).map({
        Int.random(in: 0..<100) == 0 ? Int.random(in: 0..<size) : $0
      })
    case .shuffled:
      var generator = SystemRandomNumberGenerator()
      return (0..<size).shuffled(using: &generator)
    case .random1To100:
      return (0..<size).map({ _ in Int.random(in: 1...100) })
    case .randomMinToMax:
      return (0..<size).map({ _ in Int.random(in: Int.min...Int.max) })
    case .newAtEnd:
      let sortedSize = Int(Double(size) * 0.99)
      return Array(0 ..< size).map({
        $0 < sortedSize ? $0 : Int.random(in: 0..<size)
      })
    case .pyramid:
      let half = max(size / 2, 1)
      return Array(0 ..< half) + (0 ..< half).reversed()
    case .doublePyramid:
      return DataShape.pyramid.generate(size / 2) + DataShape.pyramid.generate(size / 2)
    case .valley:
      let half = max(size / 2, 1)
      return (0 ..< half).reversed() + Array(0 ..< half)
    case .doubleValley:
      return DataShape.valley.generate(size / 2) + DataShape.valley.generate(size / 2)
    case .manyRuns:
      let runMax = max(size / 10, 1)
      var a: [Int] = []
      while a.count < size {
        a.append(contentsOf: (0..<Int.random(in: 1...min(size - a.count, runMax))))
      }
      a.append(contentsOf: 0..<(size - a.count))
      return a
    case .equal:
      return Array(repeating: 0, count: size)
    }
  }
}

//===----------------------------------------------------------------------===//
// Data types
//===----------------------------------------------------------------------===//

/// A reference type that wraps an `Int`.
class IntBox: Comparable {
    var value: Int
    
    init(_ value: Int) {
        self.value = value
    }
    
    static func == (lhs: IntBox, rhs: IntBox) -> Bool {
        return lhs.value == rhs.value
    }
    
    static func < (lhs: IntBox, rhs: IntBox) -> Bool {
        return lhs.value < rhs.value
    }
}

/// A large struct that bases its `Comparable` conformance on just its `value`.
struct LargeInt: Comparable {
    var value: Int
    var otherstuff: (Int, Int, Int, Int, Int, Int, Int, Int, Int, Int) =
        (0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
    
    init(_ value: Int) {
        self.value = value
    }
    
    static func == (lhs: LargeInt, rhs: LargeInt) -> Bool {
        return lhs.value == rhs.value
    }
    
    static func < (lhs: LargeInt, rhs: LargeInt) -> Bool {
        return lhs.value < rhs.value
    }
}

extension NSNumber: Comparable {
    public static func ==(lhs: NSNumber, rhs: NSNumber) -> Bool {
        return lhs.compare(rhs) == .orderedSame
    }
    public static func < (lhs: NSNumber, rhs: NSNumber) -> Bool {
        return lhs.compare(rhs) == .orderedAscending
    }
}

//===----------------------------------------------------------------------===//
// Data selection: toggle these to change the type of data being sorted
//===----------------------------------------------------------------------===//

let sizes = [1000, 100_000]
let shapeWidth = DataShape.allCases.map({ $0.rawValue.count }).max()! + 2

%{
selections = [
    ('int', 'Int'),
    ('large', 'Large structs'),
    ('ref', 'Reference types'),
    ('str', 'Long strings'),
    ('ns', 'NSObject subclasses'),
]
}%
% for (key, name) in selections:

do {

%   if key == 'int':
// Single-word type
    let adapter: (Int) -> Int = { $0 }
%   elif key == 'large':
// Large structs (slower copying)
    let adapter: (Int) -> LargeInt = { LargeInt($0) }
%   elif key == 'ref':
// Reference types (ref counting, etc)
    let adapter: (Int) -> IntBox = { IntBox($0) }
%   elif key == 'str':
// Strings with lots of complexity before any difference. (slow comparisons?)
    let adapter: (Int) -> String = { String(repeating: "Hello! Hi! 👨🏼‍💻👩‍👩‍👧‍👧🏃🏼‍♂️", count: 5) + "\($0)" }
%   elif key == 'ns':
// NSValue array
    let adapter: (Int) -> NSNumber = { NSNumber(value: $0) }
%   end

    let header = "Shape"
      + String(repeating: " ", count: shapeWidth - 5)
      + sizes.map({ String(format: "%10d", $0) }).joined()

    print()  
    print(String(repeating: "=", count: header.count))
    print("${ name }")
    print(String(repeating: "=", count: header.count))
    print(header)
    print(String(repeating: "-", count: header.count))

    for shape in DataShape.allCases {
      shape.rawValue.withCString { cstr in
        print(String(format: "%-*s", shapeWidth, cstr), terminator: "")
      }
      for size in sizes {
        let durations: [Double] = (1...3).map({ _ in
          var a = Slice<Array>(shape.generate(size).map(adapter))
          let t = time_milliseconds {
            a.sort(by: <)
          }
          precondition(check(a))
          return t
        })

        print(String(format: " % 9.3f", durations.mean()), terminator: "")
      }
      print()
    }

}
% end

//===----------------------------------------------------------------------===//
// Comparison check
//===----------------------------------------------------------------------===//

struct CountedComparable: Comparable {
    var value: Int
    
    static var comparisonCounter = 0
    static func reset() { comparisonCounter = 0 }
    
    init(_ value: Int) {
        self.value = value
    }
    
    static func == (lhs: CountedComparable, rhs: CountedComparable) -> Bool {
        return lhs.value == rhs.value
    }
    
    static func < (lhs: CountedComparable, rhs: CountedComparable) -> Bool {
        CountedComparable.comparisonCounter += 1
        return lhs.value < rhs.value
    }
}

do {
    let header = "Shape"
      + String(repeating: " ", count: shapeWidth - 5)
      + "Comparisons"

    print()  
    print(String(repeating: "=", count: header.count))
    print("Comparisons per 10,000 elements")
    print(String(repeating: "=", count: header.count))
    print(header)
    print(String(repeating: "-", count: header.count))

    for shape in DataShape.allCases {
      shape.rawValue.withCString { cstr in
        print(String(format: "%-*s", shapeWidth, cstr), terminator: "")
      }
      var a = shape.generate(10000).map(CountedComparable.init)
      CountedComparable.reset()
      a.sort(by: <)
      print(String(format: " %10d", CountedComparable.comparisonCounter))
    }
}

//===----------------------------------------------------------------------===//
// Stability check
//===----------------------------------------------------------------------===//

// Comprehensive sorted/stability check for MajorMinor type
func checkStability(_ data: [MajorMinor]) -> Bool {
    for (a, b) in zip(data, data.dropFirst()) {
        guard a == b else { continue }
        if a.minor > b.minor {
            return false
        }
    }
    return true
}

/// A type with a continually autoincremented `minor` value, used for checking
/// stability. Only the `value` is considered for `Comparable` conformance.
struct MajorMinor: Comparable {
    var value: Int
    var minor: UInt
    
    static var minor: UInt = 0
    
    init(_ value: Int) {
        self.value = value
        self.minor = MajorMinor.minor
        MajorMinor.minor += 1
    }
    
    static func == (lhs: MajorMinor, rhs: MajorMinor) -> Bool {
        return lhs.value == rhs.value
    }
    
    static func < (lhs: MajorMinor, rhs: MajorMinor) -> Bool {
        return lhs.value < rhs.value
    }
}

var stabilityFailures: Set<String> = []
for shape in DataShape.allCases {
  for size in sizes {
    for _ in 1...3 {
      var a = shape.generate(size).map(MajorMinor.init)
      a.sort(by: <)
      if !checkStability(a) {
        stabilityFailures.insert(shape.rawValue)
      }
    }
  }
}

print()
if stabilityFailures.isEmpty {
  print("Sort is stable in all cases")
} else {
  print("Sort was unstable in: " + stabilityFailures.joined(separator: ", "))
}