[raphaelrk]

Interesting! As a quick test on Chrome ("Version 95.0.4638.69 (Official Build) (x86_64)")

  t0 = new Date();
  a = Array(100000000).fill(0);
  console.log("time elapsed: ", new Date() - t0); // 22912
  a[100000] = 1;
  a[10000000] = 1;
  a.forEach(e => e == 1 && console.log(e));
  console.log("time elapsed: ", new Date() - t0); // 28371
  
  t1 = new Date();
  a = Array(100000000);
  a[100000] = 1;
  a[10000000] = 1;
  a.forEach(e => e == 1 && console.log(e));
  console.log("time elapsed: ", new Date() - t1); // 2787

Upon doing a couple not-so-scientific runs of this, it looks like the latter isn't really faster than the former.

[Sawamara]

This is a misunderstanding of how Arrays work. When you have an object with exactly two keys, it is very fast to iterate through them.

So what this code demonstrates is that if you have to look up a billion keys, that is going to be slower than if you have to look up two keys for an object.

Additional reading for this: https://v8.dev/blog/fast-properties From this article:

const sparseArray = []; sparseArray[9999] = 'foo'; // Creates an array with dictionary elements. In this example, allocating a full array with 10k entries would be rather wasteful. What happens instead is that V8 creates a dictionary where we store a key-value-descriptor triplets. The key in this case would be '9999' and the value 'foo' and the default descriptor is used. Given that we don't have a way to store descriptor details on the HiddenClass, V8 resorts to slow elements whenever you define an indexed properties with a custom descriptor:

[Rygian]

If the array is implemented internally as a map, then the forEach method on t1 already knows it has only two items to process.

You can show that as follows:

  t0 = new Date();
  a = Array(100000000).fill(0);
  a[100000] = 1;
  a[10000000] = 1;
  counter = 0;
  a.forEach(e => e == 1 ? console.log(e) : counter++);
  console.log("elapsed: ", new Date() - t0); // 19415
  console.log("visited but not logged: ", counter); // 99999998

  t1 = new Date();
  a = Array(100000000);
  a[100000] = 1;
  a[10000000] = 1;
  counter = 0;
  a.forEach(e => e == 1 ? console.log(e) : counter++);
  console.log("elapsed: ", new Date() - t1); // 1936
  console.log("visited but not logged: ", counter); // 0

[austincheney]

As an interesting fun fact many languages, including JavaScript, inherit complex type memory organization from C lang. So the same fundamental performance implications work the same way in all these related languages, because it is more about what happens on the metal than at the syntax.

Please note this observation only applies to access during execution.

During the late 70s a developer named Paul Heckel discovered that hash maps (what JavaScript objects are) were randomly accessed in memory until the specified key was found. That random access was faster than the access of a specified index from an array, because array indexes are accessed sequentially. Because arrays are ordered sequentially, even in memory, they are substantially faster to iterate over, though.

http://documents.scribd.com/docs/10ro9oowpo1h81pgh1as.pdf

Interesting (and unexpected): I tried searching for "Paul Heckel" in Google and only found stuff about a jazz musician. Then I searched for "Paul Heckel's algorithm" and my writing about implementing the algoritm in JavaScript was one of the first Google results.

[mdp2021]

> it looks like the latter isn't really

Sorry, I don't quite understand: running through a sparse array - running through the "undefined" - is much faster than running through a dense array. What have I missed?

[vorticalbox]

they are trying to show that looping a dense array is not much slower than looping the sparse, I just did a test on FF and is 78% slower to loop the dense vs the sparse

https://jsbench.me/ukkvgj16gg/1