Inline Sets [Was: Tagged Sets]

Evolution Pitches
1

Edit: See the third post below for a refined version of this idea.

Discussion in another thread lead me to the following idea, but I don't want to sidetrack that thread any further, especially given this idea won't give C / NS_Options compatible layout interesting in the specific context of OptionSets.

Could we store small sets as tagged pointers?

This idea could work for enumerations whose domain is small:

enum E { case a, b, c }
Set<E> ✅

Enumerations in this case could have rawValues but should have no associated values.

This idea could could also work for a set made from a short range defined on integers:

Set<6...42>    ✅
Set<100...150> ✅

However this idea won't work for arbitrary sets †, for example:

[0, 1, 2] as Set<Int> ❌

(† Edit: in fact the idea could still work in this case at the price of some runtime overhead. E.g. if the old set was not tagged and it got a change, and the changed set size is less than 52 we can check that all elements are within a specific range (e.g. the logical choice of 0..<52) - if so this can be converted into a tagged set. and if the set is tagged and we are adding an element that's outside 0..<52 range - we convert it into a non tagged set. The difference here is that with large domains the set could be switched between being tagged and not tagged while in small domains it would always be represented as a tagged pointer.)

AFAIU all 7 main tag values of tagged pointers are already used (BTW, what's "OBJC_TAG_1"?) and we'd have to use an extended tag with a smaller 52-bit payload, which is still good enough for small sets with up to 52 elements.

For this exemplar set:

enum E: String {
    case foo, bar, baz, .qux, .quux = "Hello, World"
}
var e: Set<E> = [.foo, .baz, .qux]

we may have the following layout in memory when using tagged pointers:

// Intel:
// 0000 <10 nibbles skipped> 0000 1101 xxxx xxxx 1111
                                │ ││││ ││││ ││││ ││││
                                │ ││││ ││││ ││││ │││└─ tagged pointer
                                │ ││││ ││││ ││││ └┴┴── use extended tag
                                │ ││││ ││││ ││││
                                │ ││││ └┴┴┴─┴┴┴┴────── tagged set tag (TBD)
                                │ ││││
                                │ │││└──────────────── foo = on
                                │ ││└───────────────── bar = off
                                │ │└────────────────── baz = on
                                │ └─────────────────── qux = on
                                │
                                └───────────────────── quux = off

// ARM format old:
// 1111 xxxx xxxx <10 nibbles skipped> 0000 0000 1101

// ARM new format:
// 1xxx xxxx x000 <10 nibbles skipped> 0000 0110 1111

Curiously, Hashability (and even Equatability!) of elements won't be needed in the implementation of tagged set variant.

Thoughts?

3 Likes
2

The Obj-C tags 1 and 7 (starting from 0) I think are unused, but that tagging scheme is only used for Obj-C types. Swift is completely different.

Pure Swift has its own pointer tagging scheme and Swift classes are never tagged. You can't tag value types like sets. It should be possible to tag Swift classes if you want, although it might be a good idea to get input from someone that knows how safe that is better than me. There may be some edge cases where you would lose the tags.

I'm having trouble following what you are trying to do though... It wouldn't matter the size of the set as much as which index the enum cases in the set have. A Set is a value type so you couldn't even use it with tagged pointers unless it were wrapped in a class first. Basically a set with just one element that has an enum case index of 53 would not be able to be stored tagged. If you have 64 or fewer cases you should just use a OptionSet, if you have more then that it would almost always use the set version only it would be less efficient. Since the number of enum cases is a fixed known quantity, it doesn't make sense to use tagged pointers.

The only variation that might make sense is some sort of macro that automatically changes the implementation based on how many cases you have in the enum. That wouldn't need pointer tags.

I've gone down the pointer tag optimization route before and it almost never makes sense. Since you are using reference types it usually isn't very Swifty and the best way to improve performance is to move away from reference types. I guess it would still be cool to see a macro that makes it easier to use pointer tags, but I don't think it would get much use. They also are not very portable. 32-bit systems only have 2 bits for tags. Although 32-bit is somewhat rare, it is still common for WASM and IoT.

3

Thanks for straightening this out, changing the title accordingly.

Sorry for using the wrong terminology before, the basic idea is to not have the underlying reference object when it is possible. Do this choice either dynamically (which would be similar to how "var string: String" can either store small strings inline and large strings out-of-line using a helper reference object, or in some cases statically (when the domain of values is known to be small). Perhaps that's not "tagged pointers", which would be more appropriate for NSSet and for Swift it could be done differently.

Let me start over. Consider the simple case of an enum (or a short range of integers like 1234...5678). The ideal "bit set" type I, as a developer would like to see would have these properties:

  1. can hold reasonably big number of elements. 64 is good, 100 is still good, even 1000 is good. 10K - probably too much as with a struct or a tuple with 10K fields.
  2. is POD (always)
  3. Has collection and "set" API (union, intersection, etc).
  4. As a side bonus (still important), when the size of this type is 1, 2, 4 and 8 bytes – it matches the layout of the corresponding C / NS_Options type – this is for Obj-C compatibility (including NS_Options usages in UIKit, etc).

What I'm implying by (1) is that this type could behave similar to structs / tuples – I can have those with (reasonably) arbitrary number of fields. If that's only 8 choices – fine, the corresponding MemoryLayout<S>.size will be 1. If there are 1000 choices – also fine, it will be some 125 bytes. Attempting to have 10K elements would fail the same way it now unfeasible to have a struct or a tuple with 10K elements – sometimes compiler just hangs forever or fails with "the operation took too long".

It could be a new type. Or, it could be done using existing tuple type, perhaps with these modifications:

  • introduce homogenius tuples
  • introduce tuple subscript operations
  • introduce a new Bit type (whose stride is 1 bit). A homogenius tuple of 80 bits would only take 10 bytes.
  • on top of these make this type to conform to collection and set API (or its subset).

As I mentioned elsewhere there could be a nice symmetry and completeness in the type system:

dynamic          static
–––––––––––––––––––––––––––
Dictionary       struct
Array            fixed array (`int array[42]` in C)
Set              fixed / inline set being discussed here

with OptionSet as either a separate thing or just InlineSet<with size=8,16,32 or 64 bits>

1 Like