Stackless Traversal (2018)

9 months ago

Enlist operation in Dyalog 16.0 is twice as fast as in Dyalog 15.0, especially for nested arrays with small simple arrays.
Traditional recursive C stack traversal is avoided due to stack size limitations, leading to potential segfaults for deeply nested arrays.
Memory management in the workspace is complex due to compaction and squeezing of arrays during memory allocation.
The old approach used a general traversal function 'trav()', which was flexible but slow due to excessive memory allocation and unnecessary checks.
A new strategy avoids using the C stack by reversing pointers during traversal, using constant memory and leveraging unused bits in pointers for metadata.
Stop bits and other markers in pointer bits help manage traversal without additional memory, ensuring correct navigation and termination.
The new method significantly improves performance, especially for deeply nested arrays with few elements, as shown in benchmark comparisons.
The same algorithm benefits other operations like hashing arrays, improving functions such as dyadic iota.
The solution is praised for its technical elegance and pedagogical clarity, deserving recognition within the Dyalog community.

Hasty Briefsbeta