Sparse vs. Dense Arrays in JavaScript

This is an issue because JavaScript Arrays are not like arrays in other languages - they are dictionaries where the keys happen to be numeric. So it is possible for a numeric key not to be defined, which is different from it being defined but having "undefined" as a value.

sparse arrays are usually called associative arrays, or maps

  [1,,3].length
  // 3

  [1,,3].forEach(v => console.log(v))
  // 1
  // 3
  
  [1,undefined,null,3].forEach(v => console.log(v))
  // 1
  // undefined
  // null
  // 3

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?

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:

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

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.