hapijs / hoek

Node utilities shared among the extended hapi universe
Other
480 stars 171 forks source link

Make deepEqual's seen consider both sides of the comparison #237

Closed Marsup closed 6 years ago

Marsup commented 6 years ago

Fixes #236.

Ideally we should probably compare those as couples, I could make a reverse lookup but I'm not sure it's necessary.

Marsup commented 6 years ago

I'm suggesting also having in the same Map the opposite, that is <ref, [objs]>, this seems more efficient than iterating through all possibilities.

kanongil commented 6 years ago

The map + set implementation does not iterate. Both lookups are O(1) complexity.

Anyway, it will be quite uncommon to encounter objects that have these kind of references, thus we should optimize for that case. For instance the entire hapi test suite has 0 of such compares.

Marsup commented 6 years ago

I meant iterating on tuples like you mentioned, I think it's preferable to keep it in the Map/Set.

kanongil commented 6 years ago

Hmm, some benchmarking confirms that you are somewhat right. While the lookups are indeed faster with the map solution, the set() is slower than the push().

In reality, it depends on the amount of objects that are seen during the comparison.

For 1 - 50 seens, map is slightly slower at up to ~30% performance loss. At 1000 seens, it is ~5x faster. At 10000 seens, it is ~50x faster.

Note the compared iterating pair implementations is highly optimized, using a custom class instead of a plain array for the pair.

All in all, I prefer the optimized map implementation.

Marsup commented 6 years ago

So keeping it like that ? Do you think it's worth adding the reverse lookup ?

hueniverse commented 6 years ago

I assume this is no longer needed.

lock[bot] commented 4 years ago

This thread has been automatically locked due to inactivity. Please open a new issue for related bugs or questions following the new issue template instructions.