Why are javascript engines so inefficient with sparse arrays and how to work around this?-CodePudding

This is a follow up to my earlier question JavaScript arrays: how do I compact excess length? and I so wish we can do this without downvotes and condescending comments.

I just discovered that all javascript engines I have (Chromium, Node.js, Firefox) are extremely inefficient with sparse arrays! Example:

[,1,2,3,,,,,9,,,].find((x,i,a) => console.log(x,i))

It turns out that all the holes are also hit by this search. But in a real world use case of large sparse arrays this is extremely inefficient!

One might argue that formally one should require that find would return undefined for missing values instead of skipping them and therefore never being able to return them. But that seems to be such a rarely useful property of these iterating functions and instead the spec should say that holes in sparse arrays are to be skipped.

It seems to come down to the iterating with the in vs. the of operator.

So might there be a way of redefining or modifying the iteration of these iterating functions to be based only on indexes actually there? Especially would like to find first index and last index in array, and also next index given an index (that may or may not be the index of a hole).

CodePudding user response：

The length property on an Array takes the last element's index and adds one. So if you have an array with holes between index 0 through 100, and an element at index 101, the length will return 101, as it's the last index 1.

The above happens regardless of how many elements are in the Array.

This is a documented feature. If you want to ignore empty spaces, just check if the item at whatever index is falsy, and then don't do the logic. You're more than welcome to modify prototypes to do this, at your own peril of course.

CodePudding user response：

The hostility against any critical question here compared to the incorrectness and unrelatedness of the answers is like teeth pulling.

The answer is: yes, find, findIndex, findLast, findLastIndex are indeed not efficient on large sparse arrays, but that isn't true for all the iterating array functions.

In fact, forEach, filter, map, and reduce, even some and every, do not call the callback function on the holes in the sparse arrays, which I tested in Chromium, Firefox, and Node.JS). Therefore if the intention of using findLastIndex is to replace naive use of the array length property which is unreliable (and therefore generally useless if often practically useful when ignoring many sparse array scenarios) then the following can be done:

(function(arr) {
  try {
    return arr.reduceRight(
      function(r,x,i,a) {
         console.log(r,x,i,a);
         throw i;
      }, -1);
  } catch(r) {
    if(typeof r = 'number')
      return r;
    else
      throw r;
  }
})([,,,3,,,6,,,9,,,])

I don't know if there is a gentler way of breaking out of such an iterator function loop other than throwing the result value, but it works and it cuts short what would otherwise continue after the result has already been found.

Now go ahead and vote down my answer too. But it is the right answer to a puzzling question which most people aren't even aware of which of course doesn't keep them from downvoting. (I know I can migrate to Somalia if I don't like the hostile downvote and close question culture here).