I was a bit surprised by this. It could be because of a lack of understanding of JavaScript, but the biggest reason that surprised is because I was under the impression that the time it takes to access any element in a JavaScript Array is constant.
I took the code in that post, played around a little bit (code: https://jsfiddle.net/x7sz1fhr), and the results of a hundred runs performed differently are shown below (NodeJS 12.6.1; Chrome 81.0.4044.122; Firefox Developer Edition 78.09b):
8. "Non-local", using sorted indices stored in an array — NodeJS: 57.6 ± 7.8 ms; Chrome: 35.9 ± 6.7 ms; Firefox: 155 ± 2.
These numbers are inflated as an artefact of them being the first thing to run. Please see the comment of @minitech below.
The first thing to note here is that the results obtained for Firefox are not a mistake: I have repeated by copy-and-pasting the same code a few times and, unfortunately, in all cases Firefox performed approximately 4–20 times slower than both Chrome and NodeJS. That's a bit disappointing because a couple of years ago I switched back to Firefox for its performance (I did some tests back then for my use cases before I decided). It is odd that the time difference is between 4–20 times, so it is possible that I did some non-standard things by quickly modifying the author's code.
There is also a difference between the times for array and objects across different environment, with an object generally taking longer. This result isn't directly related to our primary interest here, but I thought it was interesting and worth pointing out because of object-related concept in JavaScript.
Finally, if we use a pre-sorted array of indices to access elements in the original array containing instances of `Boom`, we see a substantial reduction in the time for Firefox but not NodeJS and Chrome. This result was a bit "unexpected" but, again, this comes back to the point @londons_explore made.
Edit: updated code to allow the environment to be changed.
Edit 2: Edited according to the of @minitech's comment.
I have similar results when running the code in the Firefox devtools console, however, running these benchmarks in a dedicated webpage does not show the results.
When using a dedicated web page, I see results which are in the same ranges as NodeJS and Chrome: (not comparable, as running on different hardware)
Started data Local (original) foo.html:120:11
Finished data locality test run in 8.6800 ± 1.3095 ms. foo.html:144:11
Started data Non-local (original) foo.html:120:11
Finished data locality test run in 38.9400 ± 1.6195 ms. foo.html:144:11
Started data Local foo.html:120:11
Finished data locality test run in 6.6600 ± 1.1390 ms. foo.html:144:11
Started data Non-local foo.html:120:11
Finished data locality test run in 38.6400 ± 1.5861 ms. foo.html:144:11
Started data Non-local (sorted) foo.html:120:11
Finished data locality test run in 12.1800 ± 1.8334 ms. foo.html:144:11
Started data Local (object) foo.html:120:11
Finished data locality test run in 14.4500 ± 1.1492 ms. foo.html:144:11
Started data Non-local (object) foo.html:120:11
Finished data locality test run in 49.0000 ± 1.6576 ms. foo.html:144:11
Started data Non-local (sorted array of indices) foo.html:120:11
Finished data locality test run in 53.8500 ± 2.9725 ms.
SpiderMonkey dev here. Does this reproduce for you with a clean profile? Because I just tried this with 78.0b9 too and for the first one, Local (original), I get 6.7 ms in the Web Console, very similar to what I see in Chrome. I didn't look at the other ones.
Hello! Many apologies for having taken a while to reply, I finally found some time to sit down and do some tests because > 200 ms vs. < 10 ms is too big of a difference, and also because of what london_explore said:
> and if that performs badly, open a bug with V8 or other JavaScript engines to optimize it.
Anyhow! Just to clarify before moving on, I also did the tests in the Web Console. All numbers noted below are for the same (first) test I initially mentioned.
What I have done in exactly the same order as follows:
1. I first tested with a clean profile as you suggested and the times haven't changed. ~240 ms was observed.
2. I downloaded Firefox and tested with a clean installation of 77.0.1. ~240 ms was observed.
3. I removed both Firefox (77.0.1) and Firefox Developer edition (78.09b), and manually removed the ~/Library/Application Support/Firefox folder. I then reinstalled Firefox Developer edition (78.09b) and, without restoring my profiles, I tested again. ~240 ms was observed.
4. I re-ran exactly the same tests on NodeJS and Chrome. ~6 ms was observed.
Assuming that it's just me, I can't immediately think of what is causing this.
Otherwise, if it's not just my setup, could it be related to the operating system? I'm currently running macOS 10.15.5. I don't have a machine with a different OS that I can test on at the moment, I should be able to try this in the next 2 hours and will update this post.
Edit: I have tested on Windows 10 as well and the issue is the same!
> I was under the impression that the time it takes to access any element in a JavaScript Array is constant.
It’s O(1), like the equivalent structure in other languages, but individual timings are influenced by other factors, like cache, as seen here. Still with a constant bound for all intents and purposes.
> Another interesting point to note here is that in the second half of the article, the author modified the `localAccess` function to accept an optional array. That may actually have side effects that are unaccounted for, which is clear upon comparison of Entry 1 and Entry 3 for all environments; and Entry 2 and Entry 4 for only Firefox. If we ignore the order-of-magnitude difference and focus on the trends, it appears that the optimisation used in different engines seen here corroborates what @londons_explore has already pointed out.
The margin of error is huge for 1, and 1 and 3 are within margins of error for the V8s, so my guess is that you ran them in the same order every time and the difference is just an artefact of being the first to run. You should wait for the page to settle down to start tests and try reordering or separating them.
> The margin of error is huge for 1, and 1 and 3 are within margins of error for the V8s, so my guess is that you ran them in the same order every time and the difference is just an artefact of being the first to run. You should wait for the page to settle down to start tests and try reordering or separating them.
You are absolutely right about the larger margin of error for 1 being artefact of it being the first one to run. In fact, the point I made about the difference between Entry 1 and Entry 3 no longer stands because the higher average (and error) is actually an effect of inflated times at the beginning.
I took the code in that post, played around a little bit (code: https://jsfiddle.net/x7sz1fhr), and the results of a hundred runs performed differently are shown below (NodeJS 12.6.1; Chrome 81.0.4044.122; Firefox Developer Edition 78.09b):
1. "Local", original — NodeJS: 7.05 ± 13.54 ms; Chrome: 6.13 ± 13.91 ms; Firefox: 241 ± 6.
2. "Non-local", original — NodeJS: 52.2 ± 1.4 ms; Chrome: 33.8 ± 1.1 ms; Firefox: 294 ± 2.
3. "Non-local (sorted)", original — NodeJS: 10.3 ± 0.9 ms; Chrome: 8.58 ± 0.94 ms; Firefox: 200 ± 1.
4. "Local", array — NodeJS: 5.05 ± 0.90 ms; Chrome: 4.22 ± 0.87 ms; Firefox: 193 ± 1.
5. "Non-local", array — NodeJS: 51.9 ± 1.4 ms; Chrome: 34.7 ± 01.6 ms; Firefox: 252 ± 3.
6. "Local", object — NodeJS: 6.50 ± 9.84 ms; Chrome: 5.80 ± 10.31 ms; Firefox: 201 ± 2.
7. "Non-local", object — NodeJS: 58.1 ± 1.2 ms; Chrome: 42.1 ± 3.3 ms; Firefox: 247 ± 2.
8. "Non-local", using sorted indices stored in an array — NodeJS: 57.6 ± 7.8 ms; Chrome: 35.9 ± 6.7 ms; Firefox: 155 ± 2.
These numbers are inflated as an artefact of them being the first thing to run. Please see the comment of @minitech below.
The first thing to note here is that the results obtained for Firefox are not a mistake: I have repeated by copy-and-pasting the same code a few times and, unfortunately, in all cases Firefox performed approximately 4–20 times slower than both Chrome and NodeJS. That's a bit disappointing because a couple of years ago I switched back to Firefox for its performance (I did some tests back then for my use cases before I decided). It is odd that the time difference is between 4–20 times, so it is possible that I did some non-standard things by quickly modifying the author's code.
A̶n̶o̶t̶h̶e̶r̶ ̶i̶n̶t̶e̶r̶e̶s̶t̶i̶n̶g̶ ̶p̶o̶i̶n̶t̶ ̶t̶o̶ ̶n̶o̶t̶e̶ ̶h̶e̶r̶e̶ ̶i̶s̶ ̶t̶h̶a̶t̶ ̶i̶n̶ ̶t̶h̶e̶ ̶s̶e̶c̶o̶n̶d̶ ̶h̶a̶l̶f̶ ̶o̶f̶ ̶t̶h̶e̶ ̶a̶r̶t̶i̶c̶l̶e̶,̶ ̶t̶h̶e̶ ̶a̶u̶t̶h̶o̶r̶ ̶m̶o̶d̶i̶f̶i̶e̶d̶ ̶t̶h̶e̶ ̶`̶l̶o̶c̶a̶l̶A̶c̶c̶e̶s̶s̶`̶ ̶f̶u̶n̶c̶t̶i̶o̶n̶ ̶t̶o̶ ̶a̶c̶c̶e̶p̶t̶ ̶a̶n̶ ̶o̶p̶t̶i̶o̶n̶a̶l̶ ̶a̶r̶r̶a̶y̶.̶ ̶T̶h̶a̶t̶ ̶m̶a̶y̶ ̶a̶c̶t̶u̶a̶l̶l̶y̶ ̶h̶a̶v̶e̶ ̶s̶i̶d̶e̶ ̶e̶f̶f̶e̶c̶t̶s̶ ̶t̶h̶a̶t̶ ̶a̶r̶e̶ ̶u̶n̶a̶c̶c̶o̶u̶n̶t̶e̶d̶ ̶f̶o̶r̶,̶ ̶w̶h̶i̶c̶h̶ ̶i̶s̶ ̶c̶l̶e̶a̶r̶ ̶u̶p̶o̶n̶ ̶c̶o̶m̶p̶a̶r̶i̶s̶o̶n̶ ̶o̶f̶ ̶E̶n̶t̶r̶y̶ ̶1̶ ̶a̶n̶d̶ ̶E̶n̶t̶r̶y̶ ̶3̶ ̶f̶o̶r̶ ̶a̶l̶l̶ ̶e̶n̶v̶i̶r̶o̶n̶m̶e̶n̶t̶s̶;̶ ̶a̶n̶d̶ ̶E̶n̶t̶r̶y̶ ̶2̶ ̶a̶n̶d̶ ̶E̶n̶t̶r̶y̶ ̶4̶ ̶f̶o̶r̶ ̶o̶n̶l̶y̶ ̶F̶i̶r̶e̶f̶o̶x̶.̶ ̶I̶f̶ ̶w̶e̶ ̶i̶g̶n̶o̶r̶e̶ ̶t̶h̶e̶ ̶o̶r̶d̶e̶r̶-̶o̶f̶-̶m̶a̶g̶n̶i̶t̶u̶d̶e̶ ̶d̶i̶f̶f̶e̶r̶e̶n̶c̶e̶ ̶a̶n̶d̶ ̶f̶o̶c̶u̶s̶ ̶o̶n̶ ̶t̶h̶e̶ ̶t̶r̶e̶n̶d̶s̶,̶ ̶i̶t̶ ̶a̶p̶p̶e̶a̶r̶s̶ ̶t̶h̶a̶t̶ ̶t̶h̶e̶ ̶o̶p̶t̶i̶m̶i̶s̶a̶t̶i̶o̶n̶ ̶u̶s̶e̶d̶ ̶i̶n̶ ̶d̶i̶f̶f̶e̶r̶e̶n̶t̶ ̶e̶n̶g̶i̶n̶e̶s̶ ̶s̶e̶e̶n̶ ̶h̶e̶r̶e̶ ̶c̶o̶r̶r̶o̶b̶o̶r̶a̶t̶e̶s̶ ̶w̶h̶a̶t̶ ̶@̶l̶o̶n̶d̶o̶n̶s̶_̶e̶x̶p̶l̶o̶r̶e̶ ̶h̶a̶s̶ ̶a̶l̶r̶e̶a̶d̶y̶ ̶p̶o̶i̶n̶t̶e̶d̶ ̶o̶u̶t̶.̶
There is also a difference between the times for array and objects across different environment, with an object generally taking longer. This result isn't directly related to our primary interest here, but I thought it was interesting and worth pointing out because of object-related concept in JavaScript.
Finally, if we use a pre-sorted array of indices to access elements in the original array containing instances of `Boom`, we see a substantial reduction in the time for Firefox but not NodeJS and Chrome. This result was a bit "unexpected" but, again, this comes back to the point @londons_explore made.
Edit: updated code to allow the environment to be changed. Edit 2: Edited according to the of @minitech's comment.