Idea: Immutable lists with modifications returning new lists - look into Relaxed Radix Binary Trees

[TysonAndre]

Google searching mentioned Relaxed Radix Binary Trees, an immutable datastructure surprisingly claiming performance near arrays in most operations. https://hypirion.com/musings/thesis https://github.com/hyPiRion/c-rrb

• gc may be difficult, immutable lists should either contain ranges of values or other immutable lists?
• once a reference count drops to 1 (the container is the only reference) lists can be extracted and reused (and unused elements can be garbage collected)?

[TysonAndre]

Those are technically logarithmic, the log depth is just small for realistic amounts of memory (only several times slower than arrays in that language).

Transients are a lot less convenient in php.

PHP's gc algorithm also poses unique problems - gc will be slow if a lot of immutable collections reference the same array

Something simpler that would have okay typical-case but worse worst-case performance: Storing references to at most 4 zend_array (packed list) instances/ImmutableList/individual zvals internally (and ranges of those arrays) may work for some common use case, for the head/tail for appending/prepending, combining them in place/freeing internally when reference counts drop to 1