9 ms·
JavaScript Array.push is 945x faster than Array.concat
- revskill 7y agoOK, so i'll make a concat function which uses push under the hood. Best of both worlds.
- Izkata 7y agoArray.splice would probably be better (specify adding to the end of the array and deleting 0 elements); it modifies in-place like push.
- darepublic 7y agoThey do different things so it's more like the worst of all worlds.
- im3w1l 7y agoQuadratic vs linear?
- deleted 7y ago[deleted]
- KitDuncan 7y agoHow about [...array1, ...array2] vs Array.concat. Or does 1 just use 2 under the hood?
- braythwayt 7y agoThe 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.
- azhu 7y agoI 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))
- braythwayt 7y agoIf 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.
- bhalp1 7y agoGreat research, great read.
- netsharc 7y agoI 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.
- imtringued 7y agoAm 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.
- braythwayt 7y agoYou 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.
- xtracto 7y agoThat'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.
- barrkel 7y agoAnd 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.
- janpot 7y agoWondering how .flat() compares. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/flat https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
- _bxg1 7y ago.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.
- wutwut5521 7y agoThese 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
- deleted 7y ago[deleted]
- antihero 7y agoYes, 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.
- PerfectElement 7y ago> 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?
- antihero 7y agoThe 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.
- skohan 7y agoI 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.
- scj 7y agoWouldn'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.
- SoReadyToHelp 7y agoIt's not 945x faster, it's O(N) faster.
- nayuki 7y agoIndeed, it's an example of "Shlemiel the Painter's Algorithm". https://en.wikichip.org/wiki/schlemiel_the_painter%27s_algorithm https://en.wikichip.org/wiki/schlemiel_the_painter%27s_algor...
- deleted 7y ago[deleted]
- StreamBright 7y ago945x 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.
- olliej 7y agoThe 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.
- rat9988 7y agoI believe he means it's 945x faster in the current case, but O(N) in the general case.
- _bxg1 7y agoYeesh... 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.
- _bxg1 7y agoAs 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.
- bakhy 7y agoI 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.
- awinder 7y agoIs 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.
- _bxg1 7y agoImmutable 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.
- boxingdog 7y agowell of course, one modifies the array and the other creates a new copy
- lenticular 7y agoCheck 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/ https://funkia.github.io/list/benchmarks/
- twic 7y agoWhy are concat and push easier to optimise if you can assume immutability?
- lenticular 7y agoThese 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.
- seanmcdirmid 7y agoIt’s obvious how to make concat fast if one is willing to give up O(1) random access operations. Push is already O(1).
- lenticular 7y agoModern 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.
- josephscott 7y agohttps://doesitmutate.xyz/ https://doesitmutate.xyz/
- giacomorebonato 7y agoNow I have to change all my Redux reducers!
- antihero 7y agoNot sure if sarcastic comment, but this would entirely break how redux works.
- lenticular 7y agoI 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.
- _bxg1 7y agoRedux 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
- acemarke 7y agoHi, 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_abramov_redux_is_not_an_architecture_or/d51g4k4?context=3 https://www.reddit.com/r/javascript/comments/4rcqpx/dan_abra... [1] https://github.com/immerjs/immer https://github.com/immerjs/immer [2] https://redux-starter-kit.js.org/ https://redux-starter-kit.js.org/
- seattle_spring 7y agoYikes, please no. Mutating your state will put you in a world of hurt.
- dickeytk 7y agoLook into Immutable.js if you want concatenation and the performance of mutating
- darepublic 7y agoI have often preferred concat over push for reasons of perceived elegance.
- skohan 7y agoPerformance 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.
- faragon 7y ago(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.
- staeke 7y agoThis 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.
- TehShrike 7y agoWatch 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!