# Computational time of appending an array and mutating an array

**URL:** <https://discourse.julialang.org/t/computational-time-of-appending-an-array-and-mutating-an-array/89118>\
**Category:** Performance\
**Created:** [October 23, 2022, 1:45am UTC](https://discourse.julialang.org/t/computational-time-of-appending-an-array-and-mutating-an-array/89118 "2022-10-23T01:45:36Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![bdas123](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bdas123/32/32142_2.png) [@bdas123](https://discourse.julialang.org/u/bdas123)\
**Post date:** [October 23, 2022, 1:45am UTC](https://discourse.julialang.org/t/computational-time-of-appending-an-array-and-mutating-an-array/89118/1 "2022-10-23T01:45:36Z")

</div>

I want to transition from Zygote.jl to AbstractDifferentiation.jl so that I can mutate arrays instead of appending them.

Before I do so, I want to make sure that mutating arrays is faster than appending an array. I’ve read that appending an array takes O(n) time. Not sure how long mutating an array is.

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [October 23, 2022, 3:01am UTC](https://discourse.julialang.org/t/computational-time-of-appending-an-array-and-mutating-an-array/89118/2 "2022-10-23T03:01:33Z")

</div>

you probably really want to just use Enzyme which looks like NOT in the AbstractDiff yet

---

<div class="post-metadata">

**Author:** ![dlakelan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dlakelan/32/8491_2.png) [@dlakelan](https://discourse.julialang.org/u/dlakelan)\
**Post date:** [October 23, 2022, 3:12am UTC](https://discourse.julialang.org/t/computational-time-of-appending-an-array-and-mutating-an-array/89118/3 "2022-10-23T03:12:41Z")

</div>

> [@bdas123](#):
>
> I’ve read that appending an array takes O(n) time.

appending an array takes O(1) amortized time up to a certain size though as far as I know. And O(1) time if you preallocate using `sizehint!()`. The amortization over many insertions works out to O(n) because they double the size of the array… But after a certain size around 1% of total ram, they stop doing this.

> <https://github.com/JuliaLang/julia/issues/28588>
>
> Average insertion time for inserting n-elements:
> !\[julia front-back insertion t…ime average\](https://user-images.githubusercontent.com/1582097/43991256-b5d405e2-9d60-11e8-87f0-0224378dd29f.png)
> Total insertion time for inserting n-elements:
> !\[julia front-back insertion time total\](https://user-images.githubusercontent.com/1582097/43991258-b8321202-9d60-11e8-8c92-076480611313.png)
> 
> \_Preliminarily\_, this behavior seems to be true for both push-front and push-back since 0.5 onwards. Still running the profiles.

The best situation is to use sizehint!

---

<div class="post-metadata">

**Author:** ![ToucheSir](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/touchesir/32/14411_2.png) [@ToucheSir](https://discourse.julialang.org/u/ToucheSir)\
**Post date:** [October 23, 2022, 3:53am UTC](https://discourse.julialang.org/t/computational-time-of-appending-an-array-and-mutating-an-array/89118/4 "2022-10-23T03:53:02Z")

</div>

I think “appending” here actually means `vcat`, because Zygote doesn’t support `push!` or `append!` unless you use [`Buffer`](https://fluxml.ai/Zygote.jl/latest/utils/#Zygote.Buffer) (which few know about and isn’t advertised because it has pretty poor performance).

That said, the original question still doesn’t make sense to me because `array[i] = ...` and `vcat(array1, array2)` don’t really have much overlap, and so the latter wouldn’t usually be a workaround for the former. It would help to have more detail about _what_ it is that requires mutation to see whether there are actual workarounds (e.g. using `map` or array comprehensions). Failing that, ReverseDiff is another, non-experimental option that supports array mutation natively and ForwardDiff may even be a contender depending on problem size.

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [November 8, 2022, 1:41pm UTC](https://discourse.julialang.org/t/computational-time-of-appending-an-array-and-mutating-an-array/89118/5 "2022-11-08T13:41:06Z")

</div>

> [@dlakelan](#):
>
> appending an array takes O(1) amortized time up to a certain size

I think it keeps being O(1) amortized, since in the limit (I see from code comment):

> we end by adding about 10% of memory each time

[I.e. of the array size, not of RAM size, so no longer ever adds a constant amount… That said, if you use more than physical RAM and start thrashing, using virtual memory, then at least with old hard disks, since they are not “random-access” it’s no longer O(1), with SSDs, O(1) may still hold…]

That’s at least with 1.8, I do NOT see that this was backported to 1.6 LTS so O(n²) behavior still there:

> <https://github.com/JuliaLang/julia/pull/40453#issuecomment-833137411>
>
> Should this just be merged and backported to 1.6.2, that's now scheduled? I'm no…t sure if it will be the last 1.6.x and since "O(n^2) behavior" is arguably a bug I'm for it, even with a constant-factor regression (it only affects sparse-matrix code, and only that one operation?).
> 
> Is the potential benefit (if I understand the benchmark, up to 9x faster, while rarely that much), to many users, much larger than the drawback, performance regression, for specialized users (that can chose to not upgrade)?
> 
> I wanted to time the operation myself, but can't locate it in the docs or help and googling only found me: https://discourse.julialang.org/t/why-do-a-mul-bc-and-a-mul-bt-belong-to-base-while-a-mul-b-lives-in-base-linalg/7757/4