Inline Sets [Was: Tagged Sets]

Evolution Pitches
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