Declaring functions with side effects

After Swift 5.2 I noticed that one of my loops using a pthread_cond_wait would hang.

struct BlockingDeque {
  public mutating func waitUntilEmpty() {
    mutex.lock()
    defer { mutex.unlock() }

    while !deque.isEmpty {
      readCond.wait(mutex)
    }
  }
  ...
}

Looking at the disassembly (pasted below) the test '!deque.isEmpty' has been evaluated once and the compiler has emitted a loop purely around readCond.wait - definitely not the intent.

I can see why the compiler thought it was a safe transform (there's just nothing that says the isEmpty getter has side effects) and I've fixed this for now by making the getter mutating, e.g.

struct Deque {
  var isEmpty : Bool {
    mutating get {
      return head != nil
    }
  }
}

Was that the best way to fix it? Is there an annotation to declare a function/getter as having side effects? My main concern is whether mutating implies 'has side effects' or if, should the compiler get just a bit smarter, and look inside 'isEmpty' it may decide the guts don't have side effects and we're back to square one.

BTW I realise Swift doesn't define a concurrency model and therefore there's no good memory model and around this stuff either. It's largely a self inflicted wound but I'm looking for a robust solution even in the face of that.

Disassembly:

...snip..

; Call isEmpty first
0x100399b44 <+68>:  callq  0x10039a2e0               ; XYZ.Deque.isEmpty.getter : Swift.Bool at Deque.swift:24
0x100399b49 <+73>:  testb  $0x1, %al
0x100399b4b <+75>:  jne    0x100399b85               ; <+133> [inlined] $defer #1 <A>() -> () in XYZ.BlockingDeque.waitUntilEmpty() -> () at BlockingDeque.swift:28


0x100399b4d <+77>:  movq   %rbx, %rdi
0x100399b50 <+80>:  movq   %r15, %rsi
0x100399b53 <+83>:  movq   %r12, %rdx
0x100399b56 <+86>:  movq   -0x28(%rbp), %rcx
0x100399b5a <+90>:  callq  0x10039a2e0               ; XYZ.Deque.isEmpty.getter : Swift.Bool at Deque.swift:24

; result moved to ebx
0x100399b5f <+95>:  movl   %eax, %ebx
0x100399b61 <+97>:  nopw   %cs:(%rax,%rax)
0x100399b6b <+107>: nopl   (%rax,%rax)

; This is the start of the loop
0x100399b70 <+112>: movq   0x28(%r13), %rdi
0x100399b74 <+116>: addq   $0x10, %rdi
0x100399b78 <+120>: movq   %r14, %rsi
0x100399b7b <+123>: callq  0x10041a08e               ; symbol stub for: pthread_cond_wait
; EBX was callee saved so we are testing a stale value
0x100399b80 <+128>: testb  $0x1, %bl
0x100399b83 <+131>: je     0x100399b70               ; <+112> at BlockingDeque.swift:31:7
; loop does not include the getter anymore


0x100399b85 <+133>: movq   0x18(%r13), %rdi
0x100399b89 <+137>: addq   $0x10, %rdi
0x100399b8d <+141>: addq   $0x10, %rsp

I think you hit the optimiser exploiting knowledge about the exclusivity (see the Ownership Manifesto) of accesses.

All of what I say below is dependent of (at least) the following assumptions to be true:

  • deque really is self.deque
  • readCond is really self.readCond
  • deque is a struct type and not a reference (class or Unsafe*Pointer)

In Swift, when you call a mutating func, the value you're calling the mutating func on is exclusively owned which means nothing else in that program outside of the mutating func itself must access the value whilst the mutating func is running. This is the case because you're using a struct BlockingDeque which is a value.

I'm not 100% sure but I think what's going on here is the optimiser sees that in this bit of the code

while !deque.isEmpty {
    readCond.wait(mutex)
}

The optimiser knows the following bits of information:

  • [self.]dequeue.isEmpty cannot mutate self because isEmpty is a getter only
  • [self.]readCond.wait(mutex) cannot (legally) mutate self because (I assume) readCond is probably non-mutating too

Therefore, the optimiser can cache self.dequeue.isEmpty because it "knows" that self cannot be mutated in this snippet of code.

So how come this code appeared to work correctly? I assume that in previous versions of the compiler, the compiler didn't see the exclusivity violation that your code is presumably doing. I'm a bit surprised why you don't get a crash telling you about the exclusivity violation.

Why am I guessing there's an exclusivity violation? The snippet

while !deque.isEmpty {
    readCond.wait(mutex)
}

is blocking until deque.isEmpty is no longer true but how could the emptiness of [self.]dequeue ever change? The only way that the emptiness of deque to change is to mutate it but. Assuming that deque is also a struct and not a class, this is impossible because self is exclusively owned by func waitUntilEmpty and if all of self is exclusively owned, so is self.deque.

How can you fix your code? A blocking deque needs to be a class in Swift because clearly you want to share the reference to the deque across multiple threads (or else the condition variable and the mutex would make sense).

3 Likes

structs may also have reference semantics, so I’m not sure it’s valid for the compiler to assume the semantics based on whether something is a struct or class.

I suppose that's a good way of looking at it and thanks for the great explanation.

Your assumptions were mostly correct, in practice I embed the BlockingDeque in a class and it's that class which is shared between threads.

After reading your comment I was also curious why no exclusivity conflicts were reported. FYI the implementation of swift_beginAccess uses TLS to store the exclusivity state. Given that the exlusivity is being violated on 2 different threads there's never a conflict 'thread locally' (but obviously there is globally).

structs may also have reference semantics, so I’m not sure it’s valid
for the compiler to assume the semantics based on whether something is
a struct or class.

It’s not whether this is a struct or a class, it’s about exclusive access. You see this in a struct because the mutating method gets exclusive access to self. If the compiler can ‘see’ all of the code that has that exclusive access — that is, unless some part of the code ‘passes’ the exclusive access to other code that the compile can’t see — it’s free to make this optimisation.

Also, while structs with reference semantics are a thing (not a good thing, but a thing nevertheless :-) you can’t implement that entirely within the struct (because structs can be copied by the compiler at will). Rather, your struct must have a reference to something that holds the actual state, and that reference would prevent the optimisation we’re seeing here.

Share and Enjoy

Quinn “The Eskimo!” @ DTS @ Apple

That is totally true but then you wouldn't (need to) use a mutating func to mutate them. Let's for example say you have

class Box<T> {
    var value: T
}

struct MyIntRef {
    let value: Box<Int>
}

then indeed, MyIntRef certainly doesn't have value semantics but let's say we want to add a increment function to MyIntRef, then we can just do

extension MyIntRef {
    func increment() { // not a `mutating func` still mutating :)
        self.value.value += 1
    }
}

in which case the value MyIntRef is not exclusively owned because the value really only carries the reference to Box<Int>. So mutating through the reference doesn't count as mutating the struct. I was just assuming (which I forgot to mention) that self.deque is var deque: SomeValue.

Ah, that could indeed be why. In that case TSan (thread sanitiser, enable with swift test --sanitize=thread or swift build --sanitize=thread) would have probably told you about that issue.