7 ms·
These functions do different things though, right? push() mutates an array in-place, and concat() completely duplicates the existing array and adds another arr
by wutwut5521 7y ago
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
- 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.
- seanmcdirmid 7y agoUntil 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.
- wolco 7y agoIt 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.
- yongjik 7y agoIf 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.
- acemarke 7y agoImmutability 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/faq/immutable-data https://redux.js.org/recipes/structuring-reducers/immutable-update-patterns https://redux.js.org/recipes/structuring-reducers/immutable-... https://daveceddia.com/react-redux-immutability-guide/ https://daveceddia.com/react-redux-immutability-guide/
- deleted 7y ago[deleted]
- twic 7y ago> 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.
- seanmcdirmid 7y agoNot everyone, or even most of the FP community does that. There is even a famous paper on how lambda is the ultimate imperative.
- Scarbutt 7y agoIs 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.
- staticassertion 7y agoI 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.
- Scarbutt 7y agoHowever, 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.
- StreamBright 7y agoOnly if some hardcore functional purist is around.
- RHSeeger 7y ago> 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
- Izkata 7y agoRead GP's whole sentence; you're agreeing with them.
- asdfasgasdgasdg 7y agoI 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 https://jsperf.com/javascript-array-concat-vs-push/226 [2]: https://jsperf.com/javascript-array-concat-vs-push/228 https://jsperf.com/javascript-array-concat-vs-push/228
- wolco 7y agoGo back to 2017. Mutable programming is back because of the benefits it offers
- sundbry 7y agoAn 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.
- BubRoss 7y agoHow is that true? push shouldn't be reallocating the array on each call. You seem to be alluding to a linked list of arrays.
- jamesfmilne 7y agoconcat() does not mutate the array, it creates a new one. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/concat https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
- skohan 7y agoIt 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.
- scottlamb 7y agoTypically (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 https://cs.stackexchange.com/a/9382
- schiffern 7y agoedit: oops, nvm
- scatters 7y agoNo, 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).
- jemfinch 7y agoYou'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
- TAForObvReasons 7y agoThe 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?
- ng12 7y ago> 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.
- EForEndeavour 7y agoJavascript 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 https://www.tensorflow.org/js [2] https://cs.stanford.edu/people/karpathy/convnetjs/demo/classify2d.html https://cs.stanford.edu/people/karpathy/convnetjs/demo/class...
- ng12 7y agoWhich is why I specified I was talking about the front-end.
- EForEndeavour 7y agoThere's plenty of demand for and work on frontend JS performance as well, e.g, https://greensock.com/ https://greensock.com/