Complexity of enum switching

Hello community,

pattern matching with a switch statement conceptually means going down a list and checking if a value matches a given pattern. Since this is in general only knowable at runtime, this is in general an O(n) operation (at least as far as I can see), where n is the number of patterns.

I was wondering if there is some optimization for enums though. Thinking about it, this wouldn't come as too much of a surprise, as enums clearly get a well known special treatment in switch statements: you can exhaustively match them without a default case.

Conceptually, there's a case to be made that enums could be matched in O(1) with a relatively simple mechanism behind the scenes: implicit church encoding.

What I'm referring to is this:


protocol ChurchEncodedPseudoEnum {
   func match<T>(onInt: (Int) -> T,
                 onString: (String) -> T) -> T 
}

extension String : ChurchEncodedPseudoEnum {
   public func match<T>(...) -> T {
      onString(self)
   }
}

extension Int : ChurchEncodedPseudoEnum {
   public func match<T>(...) -> T {
      onInt(self)
   }
}

Both types get a witness table that can (if I'm not mistaken) be looked up in O(1) and the match function is O(1) as well. It doesn't matter how many patterns are matched, the function always takes the same time.

I'm curious if anyone could answer if the compiler does something like that behind the scenes and if there are any guarantees, and if not, why not.

Enums are designed so that we can easily recover an index for the case, so a simple switch over an enum can be compiled by finding this index and then using a standard switch-over-restricted-int pattern, such as a local dispatch table. Church encoding is not a very good implementation technique because of the call it introduces into the switching code, forcing it to be broken into many distinct sub-functions. Type-based dispatch as you suggest has that disadvantage, but more importantly it is an invalid implementation technique because a type does not uniquely determine a case. Additionally, storing a case witness table in the enum would be semantically equivalent to storing a case index but less efficient in every conceivable metric.

3 Likes

I brought up Church encoding merely as an example that O(1) is possible. If Swift‘s implementation is even more efficient, great!

Is the complexity of enum switches officially documented somewhere? Google didn’t give me anything reliable (only rumors and speculations on Reddit), so I guess that I‘m by far not the only person making an incorrect pessimistic assumption.

One more question: if the associated value of an enum is itself an instance of an enum, are there further optimizations when I switch over that too? At least conceptually, an enum containing an enum is just a longer enum, and one lookup in a long „array“ of code blocks is one less instruction than two lookups in shorter nested „arrays“, so I guess it would be possible?

Well, different cases can have different payload types, so to know you can safely extract the case index of a payload enum, you have to know which case of the containing enum you’re in. Also, doing both switches at once might lead to combinatorially large switch tables, which probably isn’t a good trade-off in general. But I know LLVM does do some clever things with switches, so it’s possible.

I don’t think we’d be willing to make a guarantee — I’m not aware of any other languages that do, either — but I would be surprised if a simple switch over an enum with more than a handful of cases was ever compiled as a series of branches.

I tried using nested enum sometime earlier. At least for the memory layout, it's not just a longer enum because the inner enum needs to have a valid memory layout for that inner type. So the inner and outer discriminators are separated.

There are some exceptions, like Unsafe*Pointer?, where the nil case is converted to 0x0 because there is some space left, but I can't figure out if I can trigger that reliably. I'm pretty sure the algorithm is known, or at least fixed on Apple's OS, given ABI stability and all.

When an enum has exactly one case with a payload, Swift checks if the payload type has "extra inhabitants" — bit-patterns that don't correspond to valid values — and uses them if there are enough to express all the non-payload cases.

When an enum has more than one case with a payload, Swift looks to see if the payload types have "spare bits" — bits that aren't set in any valid values — in the same places, and it uses them if there are enough bits to express a case index.

If there are more cases than can be handled by the above, Swift makes the enum bigger so that there's room to store whatever additional discriminator it needs.

There are definitely refinements on the above which could have better results for some enums. However, using a refinement on an arbitrary enum could break ABI on Darwin, which isn't acceptable. We could use a refinement on an enum that we know will only be accessed by a sufficiently advanced compiler. However, we haven't added a way for Swift to know the minimum supported compiler version across module boundaries, so right now refinements would only be possible for non-ABI-exposed types. We haven't bothered to do that yet, in part because we haven't actually thought up any refinements that seem so valuable that it'd actually be worth doing.

2 Likes

Thanks for the answers!

Not sure if useful to you, but some time ago I came across this description of how enums are laid out in memory in Swift (see half-way down the first post), which I found very useful for my own understanding.

1 Like