Sparse Arrays

[Phil Schaf]

Hi, the proposal says

ES6 maps are an adequate replacement for sparse arrays
but this isn’t true according to spec:

calling Map.set appends a new key to the end of the keys array (in the executable reference spec), whereas the (numeric) keys of an Array are always ordered.

Therefore

let a = []
a[1] = 'x'
a[0] = 'y'

assert(Array.from(a.values()) === ['y', 'x'])

let b = new Map
b.set(1, 'x')
b.set(0, 'y')

assert(Array.from(b.values()) === ['x', 'y'])

assert(Array.from(a.values()) !== Array.from(b.values()))

​

[Andreas Rossberg]

Note that ES6 array iterators do not really work for sparse arrays either, since they do not skip over holes:

~> d8 --use-strict --harmony --harmony-arrays

V8 version 4.3.0 (candidate) [console: dumb]

d8> let a = []

undefined

d8> a[10] = 1

1

d8> Array.from(a.values())

[undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, undefined, 1]

So for most purposes, you need to write your own iterator either way -- or use a C-style for-loop.

But it's a good point nevertheless: it would be useful to have an iterator for maps over ordered keys that proceeds in key order.

 

/Andreas

[Phil Schaf]

Am Mittwoch, 11. März 2015 14:12:39 UTC+1 schrieb Andreas Rossberg:

Note that ES6 array iterators do not really work for sparse arrays either, since they do not skip over holes

that’s endearingly stupid of them, given that forEach and map work like expected…

So for most purposes, you need to write your own iterator either way — or use a C-style for-loop.

hmm? i’d use for (let key of Object.keys(sparse)) { ... }, or sparse.forEach(..)/sparse.map(), or even for (let [k, v] of sparse.entries()) { if (!(k in sparse)) continue; ... }

But it’s a good point nevertheless: it would be useful to have an iterator for maps over ordered keys that proceeds in key order.

and for the specific case of integer keys, sparse arrays are exactly that (and have been useful for me in the past.)

/Andreas

best, philipp

​

[Phil Schaf]

yeah so as obviously this was an oversight, how to fix it?

1. leave sparse arrays alone, analyze if arrays become sparse, and fall back to a sparse representation if they do.
2. only allow arrays to be sparse if they are from the beginning. i.e. only make arrays with elisions in the literal sparse
3. some polyfilled helper constructor for sparse arrays
   

2. has the advantage that it would be easy: dense arrays stay dense, sparse ones stay sparse. and since they’ll be likely filled by index access instead of pushing, the mandatory minimum length of 1 would be no big problem.

[Andreas Rossberg]

On 11 March 2015 at 15:53, Phil Schaf <truefly...@gmail.com> wrote:

Am Mittwoch, 11. März 2015 14:12:39 UTC+1 schrieb Andreas Rossberg:

Note that ES6 array iterators do not really work for sparse arrays either, since they do not skip over holes

that’s endearingly stupid of them, given that forEach and map work like expected…

...which leads to them being slow for everybody. In fact, one of the complaints we frequently get is: "Why is forEach so much slower than my hand-written for loop?" Well, the extra check needed in every iteration is a cost that is almost impossible to get rid of.

So for most purposes, you need to write your own iterator either way — or use a C-style for-loop.

hmm? i’d use for (let key of Object.keys(sparse)) { ... }, or sparse.forEach(..)/sparse.map(), or even for (let [k, v] of sparse.entries()) { if (!(k in sparse)) continue; ... }

Sure, that works, too (but might even be slower).

But it’s a good point nevertheless: it would be useful to have an iterator for maps over ordered keys that proceeds in key order.

and for the specific case of integer keys, sparse arrays are exactly that (and have been useful for me in the past.)

There are other options:

  4. Use a C-style for loop

  5. Write a simple iterator for it.

For example:

  function* orderedKeys(map, max) {

    for (let i = 0; i < max; ++i) if (map.has(i)) yield i;

  }

Isn't that simple enough?

/Andreas

[Philipp A.]

Andreas Rossberg ross...@google.com schrieb am Di., 17. März 2015 um 17:07 Uhr:

...which leads to them being slow for everybody. In fact, one of the complaints we frequently get is: "Why is forEach so much slower than my hand-written for loop?" Well, the extra check needed in every iteration is a cost that is almost impossible to get rid of.

eh, implementing them with “an extra check” isn’t something that sound smart or performance-oriented.

a good implementation of sparse arrays would be a hashmap that preserves natural order of its keys.

a good implementation of JS arrays would be a normal dynamic array (arraylist), with a fallback to above implementation once “delete” is called for the first time (or the array is constructed with elisions in the first place)

forEach is slow beacuse function overhead (or so i thought)

There are other options:

  4. Use a C-style for loop

  5. Write a simple iterator for it.

For example:

  function* orderedKeys(map, max) {

    for (let i = 0; i < max; ++i) if (map.has(i)) yield i;

  }

Isn't that simple enough?

/Andreas

it’s not performant at all.

a = []
a[4000000] = 1

try this with your implementation instead of forEach in a non-insane browser.

​

[Andreas Rossberg]

On 18 March 2015 at 09:52, Philipp A. <truefly...@gmail.com> wrote:

Andreas Rossberg ross...@google.com schrieb am Di., 17. März 2015 um 17:07 Uhr:

...which leads to them being slow for everybody. In fact, one of the complaints we frequently get is: "Why is forEach so much slower than my hand-written for loop?" Well, the extra check needed in every iteration is a cost that is almost impossible to get rid of.

eh, implementing them with “an extra check” isn’t something that sound smart or performance-oriented.

a good implementation of sparse arrays would be a hashmap that preserves natural order of its keys.

a good implementation of JS arrays would be a normal dynamic array (arraylist), with a fallback to above implementation once “delete” is called for the first time (or the array is constructed with elisions in the first place)

Oh, the reality is much more complicated than that. V8 does all these things and much more (except that there is no such thing as a "hashmap that preserves order"). Yet we currently still need a per-iteration check, mainly because JavaScript does nothing that would prevent the nature of an array changing at any point in time, including in the middle of a loop.

forEach is slow beacuse function overhead (or so i thought)

No, that's fine, that overhead should usually be optimised out by inlining.

There are other options:

  4. Use a C-style for loop

  5. Write a simple iterator for it.

For example:

  function* orderedKeys(map, max) {

    for (let i = 0; i < max; ++i) if (map.has(i)) yield i;

  }

Isn't that simple enough?

/Andreas

it’s not performant at all.

a = []
a[4000000] = 1

try this with your implementation instead of forEach in a non-insane browser.

Fair enough, for really sparse mappings you want

  function orderedKeys(map) {

    return  Array.from(m.keys()).sort((x,y) => x - y)

  }

 

That is pretty much what the implementations of forEach and friends do for sparse arrays. Iterating sparse arrays in order is already expensive, and thus not recommended. Maps are no worse.

/Andreas

 

​

[Philipp A.]

Andreas Rossberg <ross...@google.com> schrieb am Mi., 18. März 2015 um 11:18 Uhr:

Yet we currently still need a per-iteration check, mainly because JavaScript does nothing that would prevent the nature of an array changing at any point in time, including in the middle of a loop.

so retain the old representation for the duration of the loop and continue looping over that…?

Fair enough, for really sparse mappings you want

  function orderedKeys(map) {

    return  Array.from(m.keys()).sort((x,y) => x - y)

  }

and i don’t have to do that sort if using a sparse array instead.

note that the google inbox team hasn’t unlocked firefox because… it performed badly on sparse arrays (which has since been fixed).

That is pretty much what the implementations of forEach and friends do for sparse arrays. Iterating sparse arrays in order is already expensive, and thus not recommended.

[citation needed]

not recommended by whom?

Maps are no worse.

surely they are if you have to sort their keys every time you want to do it. i bet there’s a less brain-dead implementation in most browsers (note that i didn’t call your code brain-dead, because on JS level it’s the only thing one can do, while on VM level, one can do anything)

/Andreas

best, philipp

​

[Dmitry Lomov]

On Wed, Mar 18, 2015 at 3:21 PM, Philipp A. <truefly...@gmail.com> wrote:

Andreas Rossberg <ross...@google.com> schrieb am Mi., 18. März 2015 um 11:18 Uhr:

Yet we currently still need a per-iteration check, mainly because JavaScript does nothing that would prevent the nature of an array changing at any point in time, including in the middle of a loop.

so retain the old representation for the duration of the loop and continue looping over that…?

Fair enough, for really sparse mappings you want

  function orderedKeys(map) {

    return  Array.from(m.keys()).sort((x,y) => x - y)

  }

and i don’t have to do that sort if using a sparse array instead.

note that the google inbox team hasn’t unlocked firefox because… it performed badly on sparse arrays (which has since been fixed).

That is pretty much what the implementations of forEach and friends do for sparse arrays. Iterating sparse arrays in order is already expensive, and thus not recommended.

[citation needed]

not recommended by whom?

Iterating sparse arrays in order in V8 today will get you a hash check on every key. If you do

   var a = [];

   a[0] = 1;

   a[400000] = 42;

   for (var i = 0; i < a.length; i++) { .... use a[i] .... }

every reference to a[i] does the equivalent of hash table lookup. If iterate with a.iterator(), same thing happens.

This is how it works in V8 today, and this is how it worked in V8 since forever.

Note that changing this comes with a memory tradeoff (you need to keep track of ordered list of keys for a sparse array which is memory overhead, and what is a comparison function?).

Looks like what you want is an ordered map. It is very easy to do a user-land implementation of efficient ordered map - you keep a Map and a separate ordered collection (using your favorite balanced tree) of the keys (use the normal OO patterns to encapsulate). If you think a language should provide an ordered map, this is fair, but I think this is a suggestion best made at es-discuss, this is in no way specific to strong mode.

It is unclear to me why you think sparse arrays should be a canonical ordered map.

Dmitry

To post to this group, send email to streng...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/strengthen-js/CAN8d9gmJNegW-wMzuwh9iy0iFN9UNchpNRHnk7H2m35%2BnZJWzQ%40mail.gmail.com.

For more options, visit https://groups.google.com/d/optout.

[Philipp A.]

why i want them? they are very useful if you want a sequence to which you can append and remove items without the mapping of the items changing, but still regularly iterate over the available items in order.

so once i’ve appended an item while arr.length === 5, its index will stay 5. and arr[5] will return it or undefined (once it’s been deleted)

and anything referencing to it viat its index in the array will always find it using its index, or find that it has been removed. so basically like a WeakMap, but serializable and sorted.

​

[Andreas Rossberg]

On 18 March 2015 at 15:21, Philipp A. <truefly...@gmail.com> wrote:

Andreas Rossberg <ross...@google.com> schrieb am Mi., 18. März 2015 um 11:18 Uhr:

Yet we currently still need a per-iteration check, mainly because JavaScript does nothing that would prevent the nature of an array changing at any point in time, including in the middle of a loop.

so retain the old representation for the duration of the loop and continue looping over that…?

That would not implement the required semantics correctly.

Fair enough, for really sparse mappings you want

  function orderedKeys(map) {

    return  Array.from(m.keys()).sort((x,y) => x - y)

  }

and i don’t have to do that sort if using a sparse array instead.

note that the google inbox team hasn’t unlocked firefox because… it performed badly on sparse arrays (which has since been fixed).

That is pretty much what the implementations of forEach and friends do for sparse arrays. Iterating sparse arrays in order is already expensive, and thus not recommended.

[citation needed]

not recommended by whom?

By me, in this case, because of the reason I just gave. ;)

Maps are no worse.

surely they are if you have to sort their keys every time you want to do it. i bet there’s a less brain-dead implementation in most browsers (note that i didn’t call your code brain-dead, because on JS level it’s the only thing one can do, while on VM level, one can do anything)

As I said, sparse arrays also sort every time (because they use hash tables internally, because only those give you amortised constant time lookup; that's true for V8, but I would presume for other VMs as well).

You want ordered maps. But if you actually care about performance, neither sparse arrays nor maps are actually the right data structure for that, because they are both implemented as hash tables. An efficient implementation of ordered maps would typically use trees instead. Unfortunately, that's not in the JS lib.

If, OTOH, you don't care about ultimate performance, then the only difference between sparse arrays and maps is convenience, and this difference consists of writing a one-line helper function. Do you consider that a show stopper?

/Andreas

[Philipp A.]

Andreas Rossberg <ross...@google.com> schrieb am Mi., 18. März 2015 um 16:51 Uhr:

Iterating sparse arrays in order is already expensive, and thus not recommended.

not recommended by whom?

By me, in this case, because of the reason I just gave. ;)

fair enough

surely they are if you have to sort their keys every time you want to do it. i bet there’s a less brain-dead implementation in most browsers (note that i didn’t call your code brain-dead, because on JS level it’s the only thing one can do, while on VM level, one can do anything)

As I said, sparse arrays also sort every time (because they use hash tables internally, because only those give you amortised constant time lookup; that's true for V8, but I would presume for other VMs as well).

You want ordered maps. But if you actually care about performance, neither sparse arrays nor maps are actually the right data structure for that, because they are both implemented as hash tables. An efficient implementation of ordered maps would typically use trees instead. Unfortunately, that's not in the JS lib.

maybe a good point to talk about putting something like it into ES7. it’s the last big data structure missing from JS.

If, OTOH, you don't care about ultimate performance, then the only difference between sparse arrays and maps is convenience, and this difference consists of writing a one-line helper function. Do you consider that a show stopper?

well put. it isn’t, so the only thing left is that i’m surprised sparse arrayss on V8 are implemented in a surprising way. (sorting for each interation? wow…)

Dmitry Lomov <dsl...@chromium.org> schrieb am Mi., 18. März 2015 um 16:26 Uhr:

On Wed, Mar 18, 2015 at 4:18 PM, Philipp A. <truefly...@gmail.com> wrote:

why i want them?

That was not a question that I asked.

 well, you said

> Looks like what you want is an ordered map. […]

> It is unclear to me why you think sparse arrays should be a canonical ordered map.

because nothing in the spec indicates otherwise