Simulate Nested Array Without Allocating New Memory Every Loop?

General Usage Performance
14

@DNF’s solution is the preferable one, for reasons that are only apparent if you know the implementation in array.c.

push! needs to sometimes resize a vector. In addition to their length, vectors have a capacity: The amount of extra memory reserved. When you push! and the capacity is reached, then the vector is grown by a large amount (typically 2x, details in array.c), the old contents are copied over, and the old buffer is freed (no garbage collection needed). In the cheap case (capacity left over), push! is still surprisingly expensive, due to compiler/linker limitations (foreign function call that cannot be inlined, 10 cycles down the drain).

From this, you learn:

  1. push! is slower than setindex!, even if nothing gets allocated (enough capacity), and
  2. push! into a vector with enough capacity is medium-cheap, so make sure to have capacity
  3. if you ever push! into a vector, then it will waste up to 2x the memory in spare capacity, in order to make subsequent push! fast.

Watch how @DNF takes all of these facts into account: His code has only a single cache object (nit: name it buffer) that gets dynamically resized, and the return is always a copy/slice, i.e. uses tight allocation (no spare capacity that would likely be wasted, because you don’t plan to push! into your runs after construction). Further, cache retains its size between subsequent runs, avoiding push! calls for faster setindex! (the number of push! calls is the length of longest run, and does not scale with the number of runs).

2 Likes