[SR-9323] KeyPaths are quite slow #51793

weissi · 2018-11-22T13:08:58Z


Previous ID	SR-9323
Radar	rdar://problem/52529589
Original Reporter	@weissi
Type	Bug

Attachment: Download

Additional Detail from JIRA


Votes	14
Component/s	Compiler
Labels	Bug, Performance
Assignee	None
Priority	Medium

md5: 8a7995ec006b266bd138d8a19ef4ebed

is duplicated by:

SR-11983 KeyPath performance below expectation compared to alternative (see test)

Issue Description:

Description

Naively I always assumed KeyPaths are quite fast. In my head they were basically a tuple of two function pointers (a getter and a setter, both not capturing so @convention(thin) like) that get just handed around and applied. At least I assumed that would be some sort of fast path when it has enough information at compile-time.

To see how fast/slow keypaths are, I made a quick benchmark which just incremented a struct member (Int) 100 M times. To have an idea what the theoretical maximum is, I compared that to a version that doesn't use key paths at all and just does `thing.x += 1` in a loop. (I checked the assembly and the compiler does spit out every single increment (for overflow checking) it does however unroll the loop five times). Anyway, the result is:

time taken for 100M direct increments (in s)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
0.02154 0.02355 0.02358 0.02613 0.02450 0.03828

Now I benchmarked that against KeyPaths

    var thing = SomeStruct()
    for _ in 0..<100_000_000 {
        thing[keyPath: \SomeStruct.x] += 1
    }

and the result is:

time taken for 100M keypath increments (in s)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  4.691   4.698   4.722   4.738   4.778   4.821

which is 200x the runtime of the original one. I used Apple Swift version 5.0-dev (LLVM cbe8d5e28f, Clang 3452631569, Swift 201dcba300), before that it was even slower.

Then I tried to understand why Keypaths are so slow and I created yet another benchmark which goes through a pretty naive approximation:

public struct SomeStruct {
    public var x: Int = 0

    public init(){}
}

public struct FakeWritableKeyPath<Thing, Element> {
    public let writeIt: (inout Thing, Element) -> Void
    public let readIt: (Thing) -> Element
}

extension SomeStruct {
    public static let fakeKeyPathsForX: FakeWritableKeyPath<SomeStruct, Int> =
        FakeWritableKeyPath(writeIt: { thing, newValue in thing.x = newValue },
                            readIt: { thing in return thing.x })
}

and the loop was

    for _ in 0..<100_000_000 {
        let read = SomeStruct.fakeKeyPathsForX.readIt
        let write = SomeStruct.fakeKeyPathsForX.writeIt

        write(&thing, read(thing) + 1)
    }

to my absolute surprise, that yielded better performance ("only" 47x slower):

   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  1.073   1.091   1.103   1.116   1.131   1.217

To finish off, I benchmarked against what I thought would kind of approximate the implementation at least in a fast path (just handing two function pointers around):

public struct FakeCheatedWritableKeyPath {
    public let writeIt: @convention(thin) (inout SomeStruct, Int) -> Void
    public let readIt: @convention(thin) (SomeStruct) -> Int
}

extension SomeStruct {
    public static let fakeCheatedKeyPathsForX: FakeCheatedWritableKeyPath =
        FakeCheatedWritableKeyPath(writeIt: { thing, newValue in thing.x = newValue },
                                   readIt: { thing in return thing.x })
}

with the loop just like above. That started to yield reasonable performance

   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
 0.2298  0.2329  0.2351  0.2362  0.2401  0.2440

which is only about 10x slower than the direct additions and I think that's reasonable because INC is a processor instruction which naturally is a bit faster than 'function call to read the value, increment, function call to write the value'. Also loop unrolling etc...

Notes

Compiler

Apple Swift version 5.0-dev (LLVM cbe8d5e28f, Clang 3452631569, Swift 201dcba300)
Target: x86_64-apple-darwin18.2.0

OS

macOS 10.14 on

  Model Identifier: MacBookPro15,1
  Processor Name:   Intel Core i9
  Processor Speed:  2.9 GHz

Observations

I found {{ %5 = keypath $WritableKeyPath<SomeStruct, Int>, (root $SomeStruct; stored_property #SomeStruct.x : $Int) // users: %20, %8}} in the SIL which looks like the compiler has actually quite some understanding of key paths, so maybe there's hope they will soon be faster? 😉

Code

the structs/fake key paths were defined in a module Foo and all the calls were always from another module TestApp in order not to get any inlining effects. But even with everything in one module, the slow versions didn't get faster at all.

the whole code is attached (the .tar.gz and can be run with just swift run -c release), but is also here (note that everything below // MODULE: Foo is in another module.

import Foundation
import Foo

public func measure(_ fn: () throws -> Int) rethrows -> [TimeInterval] {
    func measureOne(_ fn: () throws -> Int) rethrows -> (TimeInterval, Int) {
        let start = Date()
        let v = try fn()
        let end = Date()
        return (end.timeIntervalSince(start), v)
    }

    let firstRes = try measureOne(fn).1 /* pre-heat and throw away */
    var measurements = Array(repeating: 0.0, count: 10)
    for i in 0..<10 {
        let timeAndRes = try measureOne(fn)
        measurements[i] = timeAndRes.0
        precondition(firstRes == timeAndRes.1)
    }

    print(firstRes)
    return measurements
}

public func measureAndPrint(desc: String, fn: () throws -> Int) rethrows -> Void {
    print("measuring: \(desc): ", terminator: "")
    let measurements = try measure(fn)
    print(measurements.reduce("") { $0 + "\($1), " })
}


measureAndPrint(desc: "direct") {
    var thing = SomeStruct()
    for _ in 0..<100_000_000 {
        thing.x += 1
    }
    return thing.x
}

measureAndPrint(desc: "fake key paths") {
    var thing = SomeStruct()
    for _ in 0..<100_000_000 {
        let read = SomeStruct.fakeKeyPathsForX.readIt
        let write = SomeStruct.fakeKeyPathsForX.writeIt

        write(&thing, read(thing) + 1)
    }
    return thing.x
}

measureAndPrint(desc: "totally cheated fake key paths") {
    var thing = SomeStruct()
    for _ in 0..<100_000_000 {
        let read = SomeStruct.fakeCheatedKeyPathsForX.readIt
        let write = SomeStruct.fakeCheatedKeyPathsForX.writeIt

        write(&thing, read(thing) + 1)
    }
    return thing.x
}

measureAndPrint(desc: "real key paths") {
    var thing = SomeStruct()
    for _ in 0..<100_000_000 {
        thing[keyPath: \SomeStruct.x] += 1
    }
    return thing.x
}


// MODULE: Foo
public struct SomeStruct {
    public var x: Int = 0

    public init(){}
}


// compiler generated

// fake
public struct FakeWritableKeyPath<Thing, Element> {
    public let writeIt: (inout Thing, Element) -> Void
    public let readIt: (Thing) -> Element
}

extension SomeStruct {
    public static let fakeKeyPathsForX: FakeWritableKeyPath<SomeStruct, Int> =
        FakeWritableKeyPath(writeIt: { thing, newValue in thing.x = newValue },
                            readIt: { thing in return thing.x })
}

// cheat
public struct FakeCheatedWritableKeyPath {
    public let writeIt: @convention(thin) (inout SomeStruct, Int) -> Void
    public let readIt: @convention(thin) (SomeStruct) -> Int
}

extension SomeStruct {
    public static let fakeCheatedKeyPathsForX: FakeCheatedWritableKeyPath =
        FakeCheatedWritableKeyPath(writeIt: { thing, newValue in thing.x = newValue },
                                   readIt: { thing in return thing.x })
}

The text was updated successfully, but these errors were encountered:

belkadan · 2018-11-26T17:13:18Z

cc @jckarter

jckarter · 2018-11-26T17:44:07Z

Yeah, the infrastructure is there to teach the compiler about key paths and optimize them, but nothing's been done yet to take advantage of it. The generic runtime implementation also has not been investigated for performance at all. "Make it correct, then make it fast," as they say. One thing you can do is hoist the key path reference out of the loop; the compiler isn't smart enough to do that itself yet, and while the runtime implementation does cache the result of instantiating a key path object, it nonetheless still does a runtime call to get the cached value. This cuts the overhead down about 15% compared to forming the key path inside the loop for me:

func foo() -> SomeStruct {
  var thing = SomeStruct()
  let kp = \SomeStruct.x
  for _ in 0..<100_000_000 {
      thing[keyPath: kp] += 1
  }
  return thing
}

(If a loop that does `x += 1` 100,000,000 times isn't getting folded into a single `x += 100_000_000`, that's also a bug; it would be valid to do so even in the face of overflow checks.)

kevints · 2019-03-25T21:09:32Z

@jckarter I filed SR-10166 for the optimizer issue and was able to reproduce it independently of this KeyPath issue.

jckarter · 2019-03-25T22:11:48Z

Thanks!

weissi · 2019-07-02T17:57:03Z

@swift-ci create

swift-ci transferred this issue from apple/swift-issues Apr 25, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

[SR-9323] KeyPaths are quite slow #51793

[SR-9323] KeyPaths are quite slow #51793

weissi commented Nov 22, 2018

belkadan commented Nov 26, 2018

jckarter commented Nov 26, 2018

kevints mannequin commented Mar 25, 2019

jckarter commented Mar 25, 2019

weissi commented Jul 2, 2019

[SR-9323] KeyPaths are quite slow #51793

[SR-9323] KeyPaths are quite slow #51793

Comments

weissi commented Nov 22, 2018

Description

Notes

Compiler

OS

Observations

Code

belkadan commented Nov 26, 2018

jckarter commented Nov 26, 2018

kevints mannequin commented Mar 25, 2019

jckarter commented Mar 25, 2019

weissi commented Jul 2, 2019