[Performance, Architecture] Optimize attributes for small stack allocated values (float, int, bool etc)

[twop]

Context

As it stands we have boxing/unboxing shenanigans accessing Attribute values.

simplified pseudocode:

let paddingKey = 4424 // opaque int number
let paddingValue = 3.14 // float value to store in attribute

let padding = Attribute(paddingKey,  box paddingValue) // note 'box' here

Why this is problematic:

1. During creation we allocate an object on the heap just to store a small value
2. During diffing we need to do unbox paddingAttr.Value at least twice. And probably one more time to actually apply the diff. Which is costly due to cache misses and runtime checks to call unbox

Proposal:

1. Use only a part of int or uint to store a key and reserve the rest of the bits for internal use
2. Use 2-4 bits to store a backing type of an attribute (float or int), note that it is not the same as user type. E.g. bool can be encoded as int using simply 0 | 1
3. Add two(?) additional fields to Attribute of float and uint64, actual backing type are TBD
4. Use this information for creation and diffing of Attributes to avoid heap allocation and pointer chasing.

simplified pseudocode:

// converters from user facing value to backing value
// in this example it is 'id' function
let convertFrom = fun p -> p
let convertTo = fun p -> p

let paddingAttr = defineFloatStoredAttr("padding", convertFrom, convertTo)
// will set a flag in the key that it is float backed attribute

let padding = paddingAttr.WithValue(3.14) // no boxing nor allocations
// roughly translates to
// {Key = paddingKey ||| FLOAT_ATTR_TYPE; Value = null; FloatVal = 3.14; UintVal = 0}

Now using that knowledge we can optimize diffing like so

if attr.Key &&& FLOAT_ATTR_TYPE then 
   // optimized case
   a.FloatVal = b.FloatVal
else
  // general case, what we have currently
  let comparer =  getComparer(attr.Key) // <-- cache miss
 comparer.Compare(a.Value, b.Value)  // dynamic dispatch + unboxing

Downsides

1. Declaration of Attributes will get a bit tricky, but that complexity will be a burden for us and not by the library users
2. More complexity: special cases for diffing and handling of bitwise operations
3. Attributes will occupy more space on the heap, which will impact memory footprint. Assuming that we have 1k Attributes stored on the heap (to retain UI tree) that translates into (8 bytes + 8 bytes) * 1000 = 16Kb. Probably totally fine for any reasonably scenario.

Notes

1. In Rust unions are represented differently in memory. E.g. size of the union is the size of the largest variant plus index of the variant. In F# it is as optimized, thus we have to apply some low level tricks like that.
2. It is totally possible that we should just use F# union types for Attributes instead. But as far as I know it will be hard to represent the same concept more efficiently due to limitation of overlapping fields (none allowed). Probably worth sketching out to avoid all this perf "magic".

[<Struct>]
type Attribute = 
  | FloatAttr of key: int * floatVal: float
  | BoxedAttr of key: int * boxedVal: obj

// will produce Error: "key" property is duplicated :(
// also not safe, e.g. for the same key value we can have different variants

3. Ideally, we should not exceed 64 bytes storing Attribute values in memory due to cache line size. But it seems we have plenty of space to work with: Even in the worst case scenario: 8 bytes (pointer) + 8 bytes (float) + 8 bytes (uint value) + 8 bytes (key) = 32 bytes

Links/Resources

• Writing high performance F# code

[edgarfgp]

I think this Code generation will also need to be updated to account for this ? #12

[twop]

@edgarfgp Precisely