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.
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.
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.
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.
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.
.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.
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.
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.
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:
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.
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.
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
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.
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].
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.
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.
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:
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.
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.
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.
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.
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).
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.
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.
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.
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.
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.
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.
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,
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.
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
Or
Delete a[1]
Or
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
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
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.
(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.
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.
109 comments
[ 4.7 ms ] story [ 92.5 ms ] threadtemp = 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.
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))
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.
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.
push() mutates an array in-place, and concat() completely duplicates the existing array and adds another array to it.
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
What is mutable programming? Using mutable objects is something I do everyday. Am I doing things wrong?
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.
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.
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.
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/
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.
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 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.
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
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
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
Here's a stackoverflow answer which talks a bit more about this: https://cs.stackexchange.com/a/9382
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:
Output: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.
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’.
At any-rate, it’s not like copying will happen anyways during GC.
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.
> 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...
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 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).
Everyone who has ever used a web app already knows this unfortunately.
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.
This is the underlying problem with people who don’t understand what big-O complexity is saying.
Unless you're on Python... /s
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.
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.
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
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/
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.
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.
> 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.
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.
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.
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.
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
Or
Delete a[1]
Or
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
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
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/
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.