# Simulate Nested Array Without Allocating New Memory Every Loop?

**URL:** <https://discourse.julialang.org/t/simulate-nested-array-without-allocating-new-memory-every-loop/29215>\
**Category:** Performance\
**Tags:** question\
**Created:** [September 27, 2019, 3:04am UTC](https://discourse.julialang.org/t/simulate-nested-array-without-allocating-new-memory-every-loop/29215 "2019-09-27T03:04:59Z")\
**Posts on this page:** 1\
**Showing post:** 14

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [September 28, 2019, 10:50am UTC](https://discourse.julialang.org/t/simulate-nested-array-without-allocating-new-memory-every-loop/29215/14 "2019-09-28T10:50:51Z")

</div>

@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).

---

_[View the full topic](https://discourse.julialang.org/t/simulate-nested-array-without-allocating-new-memory-every-loop/29215)._