loading...

re: Javascript Array.push is 945x faster than Array.concat πŸ€―πŸ€” VIEW POST

FULL DISCUSSION
 

Note that your tests may be returning biased results as for example Chrome and likely other browsers have special cased arrays that are known to (not) be sparse.

Doing Array.from(Array(50000), (x,i) => i + 1) looks nice but will create a "hole-y" (sparse) Array. That is, the initial array will be 50000 "holes" or empty values. That you then fill them in later will not upgrade the array to be non-sparse later on. These things change quickly but this is what was featured in a session by a Chrome engineer on Array implementations from last year: youtube.com/watch?v=m9cTaYI95Zc

I work with large arrays as well (3D model data), these are anywhere from 1KB to 100MB in size and I have to sometimes append them all together without wasting memory etc. I use the following method to append them together. It uses Array.slice but browsers (seem to) implement slicing as CopyOnWrite so the slice creates a view on the array and doesn't make copies constantly I've found empirically.

const MAX_BLOCK_SIZE = 65535; // max parameter array size for use in Webkit

export function appendArrayInPlace<T>(dest: T[], source: T[]) {
    let offset = 0;
    let itemsLeft = source.length;

    if (itemsLeft <= MAX_BLOCK_SIZE) {
        dest.push.apply(dest, source);
    }
    else {
        while (itemsLeft > 0) {
            const pushCount = Math.min(MAX_BLOCK_SIZE, itemsLeft);
            const subSource = source.slice(offset, offset + pushCount);
            dest.push.apply(dest, subSource);
            itemsLeft -= pushCount;
            offset += pushCount;
        }
    }
    return dest;
}

Linked here in my repo, which also has quite a few other array methods, check 'em out ;)
github.com/stardazed/stardazed/blo...

 

Definately a biased sample for browser point of view - not fully intentional though. We tried to get firefox results for extreamly large arrays.... and err lets say it didnt go well at all for the other browsers when put side by side, so we left them out.

Bigger impact though is probably gonna be on the server side (node.js) of things, which is the case for us.

Despite my involvement in GPU.JS, and all things 3D, which is cool in its own right. For most other sites, I do personally feel that its usually a bad idea to overbloat the UI, especially for those with older devices.

Big thanks for the youtube link =)

 

Yes, my focus is in-browser (on desktop) high-end 3D scenes, which is very different from web pages and server-side stuff. I've spent a good amount of time benchmarking various approaches to array based data manipulations so certain of my functions have separate paths for diff browsers but in general with my code Safari (since v11) and Chrome are very close with my code usually performing best in STP and Firefox generally coming in 3rd place by about -10% to -30%, unless it faster by a good margin in particular things… JS engines.

This problem also exists for ArrayBuffers as the changes to JS engines to accommodate ES6 runtime features negatively affected many common functions on those types. New patches have come in since then and they're better now, but certain functions on ArrayBuffer, like set, are still very slow on all browsers.

Thanks to Shi Ling for the nice article.

Actually your time spent on various array benchmarks across browsers, would be a cool article on its own - especially the various other browsers, safari desktop, mobile, edge, ie11? (haha).

Would actually love to see your browser specific implementations πŸ€” It is admittingly a lot of work though

Thanks! A lot of this work is in various test files (not in repos) and quite a bit of it was done over the last 3 years so I'd have to retest all permutations etc. I often feel like writing an article here but instead I just write a long comment on someone else's story as that feels less "weighty." But cool that you'd be interested!

As for browsers, given the scope of my project I have the luxury of requiring essentially the latest versions of desktop browsers, so my project outputs ES2018 code and I only need to check a few different engines.

 

Oh, I get it - you mean those holey arrays will be evaluated as holey arrays forever even if they become packed.

That video is really helpful - I learnt yet another thing about Array implementations in V8 today. Gee I wish more of these good videos are transcribed into searchable online literature.

Hm... I could change the array initialisation so that it's not holey and redo the experiments - concat will still be slower than push, but the results for the vanilla implementations could perform faster.

Huh, that's interesting! I was wondering what are the memory footprints of different implementations to merge arrays!

 

A thing I do wonder though is that if you an extra .slice(0) operation after the array is packed, wouldn't that result into a true fast-to-operate non-holey array? So the cost would be an extra allocation and copy, which would still be better than continuous .push() into a packed array.

Of course this only holds true as long there will be thousands of items to process and you know the final size before you start working on it.

This is Javascript engine dependent, but please have a look at my initial comment, I observed that Array.slice creates a view on an array instead of making a new one until it is modified (CopyOnWrite). This behaviour likely will vary for example based on what the VM thinks is best given the size and contents of the array and will again vary per VM implementation. Also, my observation is just that, I did not verify this in the source of each VM, so consider this an unconfirmed opinion.

The video may also give a real answer to this Q as the presenter goes into detail about these things, but I haven't watched it recently. Good to have a look.

I watched the video and it didn't answer that specific question. However if slice creates a view then it still does need to make a new array once any modification is made on the sliced copy. At that point shouldn't it regard it as a new array and be able to optimize it?

It would be awesome though if holey arrays could become non-holey without this kind of VM specific tricking once there are no holes remaining.

code of conduct - report abuse