JavaScript Array.push is 945x faster than Array.concat | Hacker News Reader

JavaScript Array.push is 945x faster than Array.concat

dev.to

132 pointsturrini104 comments

These functions do different things though, right?

push() mutates an array in-place, and concat() completely duplicates the existing array and adds another array to it.

    > x=[]; x.push(...[1,2]); console.log(x);
    [1, 2]
    > x=[]; x.concat([1]); console.log(x);
    []

So clearly push should be faster in general in usecases like these, since it does not need to copy.

Edit: grammar and copy paste failures from my console

Yes, they are completely different functions with completely different purposes. If you're still doing mutable programming for some god-forsaken reason using concat to mutate an array is a misuse of the function.

> If you're still doing mutable programming for some god-forsaken reason

What is mutable programming? Using mutable objects is something I do everyday. Am I doing things wrong?

The idea of "editing" stuff instead of creating new versions of them.

Whilst mutable programming is faster on write, it is much more difficult to figure out if something has changed, so any function that needs to only do work when stuff has changed (e.g. a React component), it is much much better to use immutable style programming because you only have to see if the memory address has changed as opposed to deeply compare current and previous objects.

I disagree that mutable code is inherently faster to write. Like any paradigm you can adopt, it probably feels that way igfyou start injecting immutability into an existing project, but sooner or later you settle into different design patterns which support it better, and it's not faster or slower to write. Probably faster to debug though.

Until hardware changes away from being an intrinsically imperative machines, immutable approaches will be slower simply because the hardware doesn’t really support that.

We saw FP hardware leading to performance boosts kind of happen with GPUs (pixel and vertex shaders are just transformers), but then they got back to imperative again with GPGPU.

It is not much better. It is something different. It's popular because of the way React works. It is not always correct because it is easier to understand how state changes. Using array push over concat shouldn't make understanding more difficult and using the slower function for this reason is missing the point.

If you are doing deep structure compare to check if an object was "changed", you're doing "mutable programming" wrong.

IMHO, if you're doing deep compare on anything for any reason, it's usually a sign that the data model is on a shaky ground.

Immutability is a common part of functional programming approaches. In Javascript, it's especially common in the React+Redux community. Redux expects you will update data immutably, and React works best when you do immutable updates as well.

Here's some good overviews of why and how to do immutable updates in JS:

https://redux.js.org/faq/immutable-data

https://redux.js.org/recipes/structuring-reducers/immutable-...

https://daveceddia.com/react-redux-immutability-guide/

> Am I doing things wrong?

No. Mutating state that is shared between different parts of a program is often a bad idea. The functional programming community learned the first half of that, and now goes round preaching the mistaken idea that all mutation is bad.

Not everyone, or even most of the FP community does that. There is even a famous paper on how lambda is the ultimate imperative.

Is useful in single threaded programs too, an example is to avoid having to do deep copies everywhere (which is less performant than using persistent data structures) as to have multiple versions in time of some data that you can hang on to.

I don't think they're referring to multiple threads when they say different part of the program, but instead that you should be able to reason about mutation locally.

For example, if I pass an argument into a function, it may be 'unexpected' that the argument is mutated - I can not reason about that mutation locally (unless it's very explicit or a known idiom such as push).

However, within a function, avoiding mutation seems pointless as you should have no trouble reasoning about it. At some point you really are just throwing away performance with significantly diminishing benefits.

Shared mutability across threads is definitely a huge pain in the ass though.

In the end I think we're all just trying to reduce the state space we have to manage in our heads when we read and write code, and removing mutability reduces that space.

Ok, but here you are doing all the manual work of creating a copy as to avoid mutating the arg/returning a new one and, it may be less peformant because of whole copy, knowing your programming language automtically defaults and does this for you in a performant way is a big win for reducing cognitive overhead in large programs.

I don't disagree, but the way Erlang (and thus Elixir) does it is that you get a small stack space to contain your immutable data -- and when you unwind the function the stack just gets thrown away instead of involving the GC which I'd argue is still plenty fast.

I do agree that copying stuff around is generally expensive. I am just unsure how expensive it is in smaller functions that aren't called 10_000 times a second.

Only if some hardcore functional purist is around.

> If you're still doing mutable programming for some god-forsaken reason

I believe one such "god-forsaken reason" was given to us by the title of the link...

> JavaScript Array.push is 945x faster than Array.concat

Read GP's whole sentence; you're agreeing with them.

I thought that the main cause of slowness was the fact that the accumulator array is being copied one time per array to concatenate. That means that the first array is actually being reallocated n times, where n is the number of input arrays. This is not a necessary feature of immutability; it's a problem with this particular use case.

Another big problem is that the article's benchmark is busted [1]. The author thought they were just concatenating two arrays of a fixed length a bunch of times. But what's actually happening is that arr1 is being built up because it is reused for each test case. That means that the concat version is doing A LOT of copying of the data. If you fix the test so that each run concatenates only two 50k arrays, concat is faster [2].

[1]: https://jsperf.com/javascript-array-concat-vs-push/226

[2]: https://jsperf.com/javascript-array-concat-vs-push/228

Go back to 2017. Mutable programming is back because of the benefits it offers

An efficient immutable vector can be concatenated much faster without any reallocation of either array; one would probably outperform .push for bigger arrays in this case.

How is that true? push shouldn't be reallocating the array on each call. You seem to be alluding to a linked list of arrays.

concat() does not mutate the array, it creates a new one.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

It depends on the implementation. In some cases, where arrays are required to be stored in contiguous memory, appending to an array will result in a copy anyway since the entire contents will have to be moved to a new, larger block of memory.

Typically (I don't know about in Javascript in particular), a vector has both a length and a capacity. The capacity represents total allocated space (always >= the length). If excess capacity is available when you append, that gets used rather than having to copy the array. The capacity grows exponentially (powers of 2 or 1.5 or something). This means that if you take an empty vector and append N elements one at a time, it does O(N) total copying of existing values rather than O(N^2). Another way to put it is that a single append is amortized constant time.

Here's a stackoverflow answer which talks a bit more about this: https://cs.stackexchange.com/a/9382

edit: oops, nvm

No, since the early array copies are on smaller arrays they take far less than O(n) time. The total time in copies is 1 + 2 + 4 + ... + 2^m + ... 2^(floor log2 n), which equals 2^(ceil log2 n) - 1, or O(n).

You're forgetting that half the array is never copied. The total number of copies doesn't exceed a linear cN, so it's O(N), not O(N log(N)).

The constant bound on the number of copies depends on the growth factor. With a growth factor of 2, the constant is 2. As long as the growth factor is greater than 1, the number of copies is linear.

You can verify this yourself with some trivial code:

    struct CountsCopies {
      CountsCopies() {}
      CountsCopies(const CountsCopies& other) { ++CopyCount(); }
      CountsCopies& operator=(const CountsCopies& other) { ++CopyCount(); return *this; }
      static std::size_t& CopyCount() {
        static std::size_t count = 0;
        return count;
      }
    };

    std::size_t last_copies = 0;
    std::vector<CountsCopies> v;
    for (int i = 0; i < 1000; ++i) {
      const std::size_t copies = CountsCopies::CopyCount();
      if (copies != last_copies) {
        std::cout << "size=" << i << " copies=" << copies
                  << " ratio=" << copies / static_cast<double>(i) << '\n';
        last_copies = copies;
      }
      v.emplace_back();
    }

Output:

    size=2 copies=1 ratio=0.5
    size=3 copies=3 ratio=1
    size=5 copies=7 ratio=1.4
    size=9 copies=15 ratio=1.66667
    size=17 copies=31 ratio=1.82353
    size=33 copies=63 ratio=1.90909
    size=65 copies=127 ratio=1.95385
    size=129 copies=255 ratio=1.97674
    size=257 copies=511 ratio=1.98833
    size=513 copies=1023 ratio=1.99415

The number of copies required is a geometric series. With a growth factor of 2x, the number of total copies is only 2N - 1. Thus, it is O(N).

It's O(N) for any geometric growth rate, but using 2x makes it easy to see, because every copy is one larger than all previous copies combined. Consider a concrete example for N=9: 1 + 2 + 4 + 8 = 7 + 8.

It really does depend on the implementation. Only the logical address space needs to be contiguous, not the underlying physical memory. A clever enough implementation could work hand-in-hand with a clever enough allocator, so that realloc would just add new logical pages to the end of the underlying buffer when it’s time to double its size without having to copy anything.

Is this really done? It seems like this approach would require all arrays to be allocated with at least a page's worth of memory, which seems incredibly wasteful if you have a bunch of small arrays with a handful of floats or something.

”It seems like this approach would require all arrays to be allocated with at least a page's worth of memory”

I don’t know whether it is done in practice, but you can postpone doing that until the array gets ‘big’, for some definition of ‘big’.

Allocating a bunch of small arrays is going to be wasteful (performance wise) anyway. That being said, I'm not sure if this is done frequently or not.

Your virtual address space needs room for that, clever allocators can’t violate the laws of physics. Also, you can only do this at page size granules.

At any-rate, it’s not like copying will happen anyways during GC.

The issue is that the community 5-10 years ago heavily favored "pure" approaches like Array#concat rather than mutations like Array#push. So a whole new generation of developers were taught to avoid the functions at all costs. "never use push" is a common mantra in JS circles, and developers favored making a copy of an array even if that array was used nowhere else (where push would've been the appropriate choice) Maybe we're seeing a push back towards performance over purity?

> Maybe we're seeing a push back towards performance over purity?

No, because performance is generally not a huge concern on the front-end. I'm not applying ML strategies to hundreds of thousands of data points, I'm trying to render 10 elements instead of 9. Performance is so rarely a concern that I'd always err on the side cleaner code than hyper-performant code. This stuff isn't even worth thinking about.

Javascript isn't just a frontend language though, is it?

> I'm not applying ML strategies to hundreds of thousands of data points

Maybe you aren't, but the folks over at tensorflow.js [1] certainly are, as well as Andrej Karpathy's ConvnetJS [2].

[1] https://www.tensorflow.org/js [2] https://cs.stanford.edu/people/karpathy/convnetjs/demo/class...

Which is why I specified I was talking about the front-end.

There's plenty of demand for and work on frontend JS performance as well, e.g, https://greensock.com/

You're being pedantic -- I'm not saying that there performance-critical JS code doesn't exist, I'm saying that the push for readability over performance isn't going anywhere.

Performance might not be a concern for you, but it is your users who should be deciding.

As if my users would ever notice. Some of them are still using IE9.

> This stuff isn't even worth thinking about.

If more front-end developers have this mindset, I'm beginning to understand how the web (and the desktop, via electron and such) has become the embarrassingly slow and unusable mess that it is nowadays.

I can promise you the JavaScript runtime is not the cause of whatever "slow and unusable mess" you've experienced.

True, but these things add up. It is definitely not a problem at one spot; make those spots 100 and the problem manifests itself very obviously.

I am a fan of expressive and readable code as well and have fully migrated to functional languages in the last 2-3 years. But I don't think in JS we have the luxury to ignore a 945x performance improvement on a very low-level building-block function. It's used in thousands of places.

So you know, I agree with your premise. As a compromise I'd make an utility that reads much better than `Array.push` but still uses it internally (if such a tool does not already exist).

>performance is generally not a huge concern on the front-end

Everyone who has ever used a web app already knows this unfortunately.

You're like the third person to make this snarky comment in this thread. I promise you the JavaScript runtime is not the bottleneck.

Immutable.js has good functionality to allow you to batch pure operations if you don’t actually need the intermediate values.

Am I seeing this right? Someone is creating 10000 arrays of increasing size and then wonders why it's slow? Why does this even need benchmarks? It should be obvious that copying 0.5 billion elements is far slower than only copying 10000.

You are reading it right. I don’t know if it’s obvious, but it is the kind of thing that gets figured out when you find a hotspot in your code and do a little testing.

That's the funny thing: Those type of articles is what you get when someone without knowledge of CS theory like Big-O notation gets into an issue of a linear vs higher complexity algorithm. They have to do lots of simulations to grok the depth of the performance difference.

And some people object to testing knowledge of the basics of algorithm complexity analysis with big-O in programming interviews because they "never need that theory".

IMO complexity analysis is possibly the single most important bit of theory to understand if you work on apps where there is any n which grows to a large number. More important than being able to reverse a linked list or whatever.

Yeesh... this is why it's good to have some experience with a language where you have to manage your own memory, even if you only write JavaScript at your day job. To anyone who's written C++ before this difference is incredibly obvious.

As a rule of thumb: anything done in a pure-functional/immutable style is probably going to take a performance hit. This tradeoff is often worth it for maintainability, especially if you're using true immutable data structures like Immutable.js or Clojure's structures which reduce copying to the absolute minimum. But always be aware of this tradeoff. If you're doing a simple operation over 15,000 of anything, just use a for loop for goodness' sake.

> just use a for loop for goodness' sake.

Unless you're on Python... /s

I don't know if this works well on JS, but there is a purely functional way that avoids most of the performance hit - generator methods. In C#, I'd write functions that return IEnumerable<T>, using yield return, and others that combine them with LINQ's Concat, and aside from many iterator objects, only one big array would need to be allocated.

When it happens that parts of this work later turn out not to be needed, it's easy to discard an enumerable, and the iteration is not actually performed. It can sometimes lead to really ellegant code that also performs well.

Is there an equivalent for "just use a for loop" if you are in some immutableland though? This has always confused/worried me watching that space -- maybe you're fundamentally restructuring problems in FP to avoid these situations but to my eyes it looks like a world of newly-invented scaling issues.

Immutable data structures let you use pure-functional patterns without most of the associated costs. The OP's original strategy would work just fine with immutable structures.

It really depends, I wouldn't be so forthright. In more complex apps, mutable structures may be shared with other bits of code, and you may end up copying for safety rather than because immutability forces you to. Non-local reasoning is less reliable as complexity and team size (concurrent development!) scales up, and the rules you adopt to ensure development can scale with larger teams can hit you on the other side.

This is a distinct issue from the maintainability argument. I'm saying that if you don't have functional code throughout, you might end up copying more often than you think. Immutability means you can hang on to things and share them with confidence.

For example, consider a method which returns an array in Java or C# or some other language without type-based constness. It's not safe to cache that and return the cached instance, because the array is mutable. So almost invariably such arrays are constructed afresh every time - copying induced by lack of immutable style.

> I'm saying that if you don't have functional code throughout, you might end up copying more often than you think. Immutability means you can hang on to things and share them with confidence.

But if you need to copy you're still following an "immutable" pattern: needing to share data with the guarantee that it won't be changed. Copying is just a very blunt way of accomplishing that. Immutable data structures will of course be a big improvement over simple copying whenever you need to do this sort of thing, but if you can avoid it altogether by modifying things in place instead of relying on their lack of mutation, you'll have even less overhead.

Clojure's transients, for example, were created for exactly this purpose: https://clojure.org/reference/transients

This is nonsense. You're micro-benchmarking some detail without reflecting on how to use these methods. I take it you have this code (sort of)

  const all = [[1,2,3,4,5], [1,2,3,4,5], ...] //15000 items
  let ret = [];
  for (item of all) {
    ret = ret.concat(item);
    // Or ret.push(...item);
  }

The point of using concat is of course that you don't have to do the loop. You're shuffling bytes for no use like crazy there. Not concat's fault. You should be doing:

  [].concat(...all);

This runs in ~1ms on my machine (latest Chrome). Custom versions, and loop + push both come it at around ~4ms.

Wondering how .flat() compares. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

.flat() should be much better, because it "knows" it's flattening. In the author's case, each individual step was treated as stateless, so a new array had to be created each time. In a .flat() function, you could have a single persistent, stateful destination array that everything gets copied into. It would be equivalent to the performance of using push(). Actually, it would probably be faster, because flat() is presumably implemented in native code instead of JS.

Check out Funkia List [0], an persistent O(log n) random access list implementation. I use it pretty extensively when I'm writing typescript.

It actually can beat native arrays on concat and push, often by very wide margins, while also being immutable. These kinds of operations are actually much easier to optimize if you can assume immutability.

[0] https://funkia.github.io/list/benchmarks/

Why are concat and push easier to optimise if you can assume immutability?

These persistent structures use what's called structural sharing. The simplest persistent structure is just a regular linked list. While random access is O(n), inserting, deleting, or concating is O(1). Since the list is not mutated, we can insert an element to the head of the list just by taking the new element and making a pointer between it and the original list. The original list is not modified, nor is it copied.

More sophisticated persistent structures like Funkia List have O(log32n) access, which is basically constant time. This makes them better general-purpose data structures than mutable arrays.

It’s obvious how to make concat fast if one is willing to give up O(1) random access operations. Push is already O(1).

Modern persistent tree-based data structures are usually O(log32n) random access, which is essentially O(1) for all practical purposes. With a mutable array of references, random access follows one pointer, while these structures follow usually less than 5. Sequential access is usually O(1).

These kind of persistent data structures are already the standard data structures in Scala and Clojure, and they are fast enough for the vast majority of non-numerical purposes. In typical access patterns, they are faster than mutable arrays.

As N approaches infinity O(log32 n) approaches O(log n). And really, we don’t care much about N until it gets very large.

> In typical access patterns, they are faster than mutable arrays.

Only if typical is extremely random on large lists that consume many pages/cache lines.

Sequential access is O(1) just like mutable arrays. These structures really are fast and practical. The benefits of immutability are enormous. That's why they are so popular.

Edit: That's true about log32 and log2 become close in the limit, but that's irrelevant for practical data sizes. For example,

log2(10^6) ~ 20,

log32(10^6) ~ 4

That's a 5x difference.

Sequential access in an array has caching advantages because the memory is contiguous. For a linked structure, that is often not true. Linked structure mostly suck at sequential accesses. Extreme random access can actually work against arrays for the same reason.

There is a good reason why the subscript of log is often not even mentioned. Logarithmic is logarithmic, no longer what subscript you bother in investing extra space for.

log32n/log2n is always 5, highlighting why this is such a meaningless comparison. O(logn) (basically) refers to a constant multiple clogn, by which logic O(log32n) = O(5log2n) = O(log2n) = O(logn). It's all the same.

Case in point, if your algorithm takes log32n operations but each OP takes 5x longer its exactly the same as log2n. This is true for any value n, not just large values.

Ah! My explanation was wrong in that sense, thanks for the correction.

Whoops, brain fart.

The problem is making concat fast given the original array still exists and is mutable.

In the major JS engines string concat is essentially O(1) because strings are immutable (and they flatten them out as appropriate according to whatever heuristics make sense).

But for array concatenation in js i can do

a.concat(b)

Followed by

a[0]=something

Delete a[1]

A.push(something)

Or a.length++

Etc

To make this particular array concat fast would require significant perf impact to all other arrays, even those that aren’t involved in concat

https://doesitmutate.xyz/

How about [...array1, ...array2] vs Array.concat. Or does 1 just use 2 under the hood?

The issue here is that the author wants to merge one array into another, so they wrote a = a.concat(b), but that is implemented as:

temp = a.concat(b) a = temp

In creating `temp`, JS copies all the elements of a and all the elements of b.

Whereas,

a.push(...b)

Only copies all the elements of b.

The code you propose copies all the elements of a and b, so it wouldn’t be faster.

I believe you misunderstand. The question refers to whether or not using the spread syntax only would result in similar performance gains as seen when moving from .concat to .push with the spread.

const arraysToMerge = [ arr1, arr2, arr3, ... arrN ];

const spreadMergeFn = (reduced, arr) => [ ...reduced, ...arr ];

const spreadPushMergeFn = (reduced, arr) => reduced.push(...arr);

const merged = arraysToMerge.reduce(________, []);

Pure spreading will be slower. Using push lets you skip that first spread of what you've accumulated so far in favor of mutating a reference. I suspect that the above code using push will not run correctly though. Would need to get under the hood of .reduce to see, but it should break.

My current personal opinion is to use flat() if possible.

// these produce identical data structures

[ arr1, arr2, arr3 ].flat()

[ ...arr1, ...arr2, ...arr3 ]

arr1.slice().push(...arr2.push(...arr3))

If you think a misunderstanding may be afoot, let me be as explicit as possible. I do not believe that moving from:

a = a.concat(b)

To:

a = [...a, ...b]

Would give the same performance gains as moving to:

a.push(...b)

Because [...a, ...b] creates a new array, and copies the elements of both a and b into it.

Old-timers will say that we had this exact same conversation about Java and strings way back in the day. Using a StringBuffer was faster for this kind of thing up and until Java started detecting when your use of string catenation could be replaced by a StringBuffer.

Quadratic vs linear?

(push using geometric pre-reserve) vs ((exact-per-element growth + concat) x N times) vs (exact reserve and then add the elements) . Being the third case analogous to the "builder" concatenation technique (resize the element to receive the concatenation for the final size, and copy the N strings into the resized space).

The concat privitive not doing geometric pre-reserve is not a bad thing, in my opinion, even if in this case is slower, because of memory saving for the most frequent case. Of course, the concat operation should be always efficient when destination container has enough space.

Watch out for this even more obscure gotcha – if you're dealing with large enough arrays, V8 will throw an error:

   [].push(...new Array(120520))

results in `RangeError: Maximum call stack size exceeded` on node v10.15.3.

    [ ...new Array(120520)]

works fine though!

Wouldn't a call to Array.prototype.splice act as a language defined (and hopefully optimized) means of adding elements in-place?

Slightly ugly because you'd need to specify the start index, a command to delete 0 elements, and a call/apply to inject the array, but it should do.

Look into Immutable.js if you want concatenation and the performance of mutating

Now I have to change all my Redux reducers!

Not sure if sarcastic comment, but this would entirely break how redux works.

I probably wouldn't worry about it unless you have really large arrays. It's still probably pretty insignificant compared to the time spent updating the DOM.

Redux is designed to be used with this kind of pattern. Immutable.js, which is often paired with it, mostly solves this particular type of performance problem. You'll still have a performance ceiling when you use Redux, but it's very unlikely that you'll hit it.

Edit: I was using Immutable.js as a stand-in for immutable data structures in general; apparently there are other JS libraries you can use

Hi, I'm a Redux maintainer. I personally would recommend _against_ using Immutable.js, for a number of reasons [0].

Instead, I highly recommend the Immer library [1], which lets you do immutable updates with "mutating" logic in callbacks.

Even better, try out our new Redux Starter Kit package. It uses Immer internally to let you simplify immutable updates in your reducers [2].

[0] https://www.reddit.com/r/javascript/comments/4rcqpx/dan_abra...

[1] https://github.com/immerjs/immer

[2] https://redux-starter-kit.js.org/

Yikes, please no. Mutating your state will put you in a world of hurt.

I have often preferred concat over push for reasons of perceived elegance.

Performance optimization often comes at the cost of elegance. One is about logical and conceptual purity, the other is about doing whatever is required to achieve a result.

It's not 945x faster, it's O(N) faster.

Indeed, it's an example of "Shlemiel the Painter's Algorithm". https://en.wikichip.org/wiki/schlemiel_the_painter%27s_algor...

945x is the actual measured difference, O(N) is the theoretical difference. Many times quadratic time complexity is ok because you are working on very small N.

The point is 945x is just the measurement for this particular test case. If the author made the test larger it would appear even faster.

This is the underlying problem with people who don’t understand what big-O complexity is saying.

I believe he means it's 945x faster in the current case, but O(N) in the general case.

well of course, one modifies the array and the other creates a new copy

Great research, great read.

I couldn't stand the repetitive way she was presenting the information. Sure it was like a monologue or conversation, but the info could've been given in a paragraph or two.

OK, so i'll make a concat function which uses push under the hood. Best of both worlds.

Array.splice would probably be better (specify adding to the end of the array and deleting 0 elements); it modifies in-place like push.

They do different things so it's more like the worst of all worlds.

Reply on news.ycombinator.com