# Performance implications of Array mutations (\`push\`, \`splice\`, \`pop\`, etc.)

**URL:** <https://discourse.julialang.org/t/performance-implications-of-array-mutations-push-splice-pop-etc/5482>\
**Category:** General Usage\
**Tags:** question, performance\
**Created:** [August 21, 2017, 3:29pm UTC](https://discourse.julialang.org/t/performance-implications-of-array-mutations-push-splice-pop-etc/5482 "2017-08-21T15:29:02Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![nickeubank](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nickeubank/32/3878_2.png) [@nickeubank](https://discourse.julialang.org/u/nickeubank)\
**Post date:** [August 21, 2017, 3:29pm UTC](https://discourse.julialang.org/t/performance-implications-of-array-mutations-push-splice-pop-etc/5482/1 "2017-08-21T15:29:02Z")

</div>

Could anyone speak to the performance implications of modifications of arrays that change array length? My understanding has always been it’s best to minimize modifications of array that change length, as the fact arrays generally require contiguous memory blocks means that adding an element requires the compiler to allocate a new block of memory and copy over the entire array plus the new element. Yet I see a lot of the use of `push!` and `pop!` in tutorials.

Relatedly, Julia doesn’t seem to have linked-lists as a core collection, and people seem to use Vector{Any} as though they were linked lists, but seems like if they are using contiguous blocks of memory, that’s a problem…

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [August 21, 2017, 4:32pm UTC](https://discourse.julialang.org/t/performance-implications-of-array-mutations-push-splice-pop-etc/5482/2 "2017-08-21T16:32:58Z")

</div>

When an array in Julia (and in many other languages) grows beyond its capacity, its capacity is increased by a fixed factor (it might be 2, or maybe 1.5, or somewhere in between). That means that “most” `push!()` operations will be able to expand into that extra space without any new allocations or copying. This means that `push!()` in Julia has [amortized constant time](https://en.wikipedia.org/wiki/Dynamic_array#Geometric_expansion_and_amortized_cost).

As for linked lists, I think that the (amortized) constant time append operations for `Vector`, combined with `O(1)` indexing and good cache locality mean that `Vector{Any}` is a good choice for storing generic lists of stuff.

Of course, if you’re going to be doing things like adding elements to the middle of an array, and you’re not interested in indexing into that array, then a linked list makes a lot of sense. There’s one available in [DataStructures.jl](http://datastructuresjl.readthedocs.io/en/latest/linked_list.html).

---

<div class="post-metadata">

**Author:** ![nickeubank](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nickeubank/32/3878_2.png) [@nickeubank](https://discourse.julialang.org/u/nickeubank)\
**Post date:** [August 21, 2017, 4:38pm UTC](https://discourse.julialang.org/t/performance-implications-of-array-mutations-push-splice-pop-etc/5482/3 "2017-08-21T16:38:15Z")

</div>

@rdelts Brilliant, thanks!

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [August 21, 2017, 6:20pm UTC](https://discourse.julialang.org/t/performance-implications-of-array-mutations-push-splice-pop-etc/5482/4 "2017-08-21T18:20:43Z")

</div>

sizehint! could also help.  
[https://docs.julialang.org/en/stable/stdlib/collections/](https://docs.julialang.org/en/stable/stdlib/collections/)

---

<div class="post-metadata">

**Author:** ![nickeubank](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nickeubank/32/3878_2.png) [@nickeubank](https://discourse.julialang.org/u/nickeubank)\
**Post date:** [August 21, 2017, 6:51pm UTC](https://discourse.julialang.org/t/performance-implications-of-array-mutations-push-splice-pop-etc/5482/5 "2017-08-21T18:51:28Z")

</div>

That is also super useful, thanks @Elrod