Performance Analysis of Depth-1 Vector/Hashtables vs Depth-2 Vector/Hashtables

[andrew-johnson-4]

Depth-1:

• pointer to OwnedData -> Flexible Array Member Data (not resizable)
• cons: not resizable
• cons: old references to the data structure must be updated if resize happens
• pro: can be allocated on stack-only if size = 0
• pro: eliminates one level of pointer indirection

Depth-2:

• pointer to OwnedData -> pointer to OwnedData (can be swapped during resize) -> Flexible Array Member
• pros: resizable
• pros: old references to the data structure are always up to date
• cons: must allocate heap data, even if size = 0
• cons: adds one level of pointer indirection

Yes, this is nice in theory, but HOW FAST IS IT? What is the actual performance improvement?

[andrew-johnson-4]

Note: Depth-1 vectors can be entirely stack-allocated up to a fixed length, i.e. boost::container::small_vector.

[andrew-johnson-4]

Personally, I prefer the depth-1 Vector to be very small as a reference (single word size for the entire Vector value, because it is just a pointer). This prevents struct size explosion.

[andrew-johnson-4]

@alex-s168 Thoughts?

I am trying to hyper-optimize the Vector / Hashtable data structures for use in the compiler. I think depth-1 simple vectors are optimal, but we need to do some actual benchmarks to do the comparison. We have a few options to compare, feel free to suggest any other options:

Option 1: depth-2 Vector like C++ std::vector (size is 1 word)
Option 2: depth-1 Vector like C++ boost::container::small_vector but without the stack storage (size is 1 word)
Option 3: depth-1 Vector exactly like C++ boost::container::small_vector (size is 1 word + header size + N * content size)

This is not a high-priority issue right now, I just want some diversity of thought here for when I can get back to it.

[alex-s168]

In LM, we can maybe do runtime dependent struct field offsets and sizes?
That would optimize the storage of immutable datastructures containing variable length members a lot

most languages can't do that, but maybe we can?

[andrew-johnson-4]

Backend Options: what do you need?

• Can work in standard C (yay!)
• Needs custom assembly (ok?)
• Needs dynamic code generation (hmm?)

It is great to play around with this stuff. That is what LM exists for: to be a playground for new ideas. However, LSTS will always try to support C as a fallback backend. LM is just a general backend for whatever you want. Custom instructions and dynamic code generation are definitely long term goals for LM.

[alex-s168]

it can work in standard C, but we can't use structs for that in C