Boa: Object properties should be stored ordered

[raskad]

Describe the bug
String and Symbol object properties are currently returned in arbitrary order, because the underlying store is a std::collections::HashMap. The spec specifies, that String and Symbol properties should be returned in order of property creation e.g. OrdinaryOwnPropertyKeys.
Index properties should be returned in ascending numeric order. We currently achieve this by sorting the properties in the ordinary_own_property_keys function.

To Reproduce
This JavaScript code reproduces the issue:

Object.keys({b: 1, a: 2, c: 3});

This currently may return [ "c", "b", "a" ].

Expected behavior
The above code should always return [ 'b', 'a', 'c' ].

We should store the properties in data structures that preserve the expected order, so that we do not have to waste time sorting.

[jedel1043]

I think this is one of the rare instances where a linked list would solve this optimally. What do you think?

[raskad]

I'm not sure about a linked list. I'm currently testing out the indexmap crate that we already use for the Map builtin.

This blog post from the V8 team covers the topic: https://v8.dev/blog/fast-properties. V8 is of course highly optimized. I think we can skip some of those optimizations for now. I was mainly looking at the Slow properties, described as some dict.

[jedel1043]

I thought about indexmap but I think it just preserves the insertion order if you don't call delete on the map.

[raskad]

Ignore what I wrote here before. I think we can just Option the value and set it to None on remove().

[jedel1043]

Ignore what I wrote here before. I think we can just Option the value and set it to None on remove().

I don't know if I understood completely, but wouldn't that leave big memory footprints if you insert a lot of items then delete them?

[jedel1043]

This blog post from the V8 team covers the topic: https://v8.dev/blog/fast-properties. V8 is of course highly optimized. I think we can skip some of those optimizations for now. I was mainly looking at the Slow properties, described as some dict.

Also, those are some good optimizations we could make! Maybe it would be a good idea to open a new discussion with every idea we stumble upon to optimize the engine 😄
@Razican what do you think?

[raskad]

Ignore what I wrote here before. I think we can just Option the value and set it to None on remove().

I don't know if I understood completely, but wouldn't that leave big memory footprints if you insert a lot of items then delete them?

Yes that would be true. But never mind that; indexmap has a shift_remove function. The downside is, that it is O(n) instead of O(1). But I think that is probably the easiest way to be spec compliant with a reasonable performance. I will try to do some benchmarks with this version vs the old FxHashMap to see how this plays out.

[jedel1043]

Ignore what I wrote here before. I think we can just Option the value and set it to None on remove().

I don't know if I understood completely, but wouldn't that leave big memory footprints if you insert a lot of items then delete them?

Yes that would be true. But never mind that; indexmap has a shift_remove function. The downside is, that it is O(n) instead of O(1). But I think that is probably the easiest way to be spec compliant with a reasonable performance. I will try to do some benchmarks with this version vs the old FxHashMap to see how this plays out.

If it makes OrdinaryOwnPropertyKeys spec compliant and doesn't affect too much the performance, I don't see a problem with using that structure. We can optimize later when we have most of the spec implemented and a lot less immediate goals in our plans.

[jedel1043]

Made a little digging and found hasklink. Could be more performant than indexmap, and we can attach it FxHasher to see how it compares with FxHashMap.

[Razican]

This blog post from the V8 team covers the topic: https://v8.dev/blog/fast-properties. V8 is of course highly optimized. I think we can skip some of those optimizations for now. I was mainly looking at the Slow properties, described as some dict.

Also, those are some good optimizations we could make! Maybe it would be a good idea to open a new discussion with every idea we stumble upon to optimize the engine 😄
@Razican what do you think?

Good idea, let's open a separate discussion :) we can then create some issues for it

[raskad]

Made a little digging and found hasklink. Could be more performant than indexmap, and we can attach it FxHasher to see how it compares with FxHashMap.

I used indexmap with FxHasher in my PR. The performance looks good. I looked at hasklink and i feel like it may be a little too immature. The docs look very sparse and I did not see any good/easy examples.