Deprecate and move StrMap?

[hdgarrood]

Continuing discussion from #116.

StrMap seems to only earn its place in this library if it can be treated as a general-purpose map data structure with string keys. However, it's difficult to justify this: asymptotically it's significantly worse than Map String for many operations, and the order that Foldable and Traversable instances iterate over entries is unpredictable (since it is based on a JS for-in loop underneath). Moreover, it's not at all clear how we might implement StrMap for other backends, since it has various JS quirks (not just the traversal order issue, but also things like keys with names like __proto__). StrMap clearly is useful for JS interop, though.

Given all this, I'd like to consider deprecating StrMap, and moving it to a different (new?) package. I'd suggest calling the package purescript-js-objects and renaming the StrMap type to JSObject; I think that's a better reflection of what its intended use is.

[sharkdp]

Naively (without ever checking), I always thought StrMap was here because of its superior performance compared to Map String. How general is your statement "asymptotically it's significantly worse than Map String for many operations"?

Arguably, one of the basic operations of a Map is a key lookup, where I would expect the StrMap to be much faster.

Indeed, I just ran this little benchmark: Time to look up a single element by key (times are averaged over all keys in the map)

For these (moderate) sizes, Map String shows the expected(?) scaling, i.e. O(log(n)). StrMap seems the be almost constant, which could indicate that the logarithmically increasing time at these sizes is still dominated by some constant offset(?).

(Note: I'm not necessarily saying it's a bad idea to rename and move StrMap)

[natefaubion]

StrMap is good for lookups, but it's an ephemeral data structure. My primary reason for supporting this change is that all of it's characteristics depend on whatever the JS runtime is using for property look ups. It's implementation completely defers to FFI. It's not a general purpose, optimized hash table which can be translated to other backends (as a real PureScript implementation would). It's a very useful thing, with useful characteristics, but I don't think it belongs here. I think purescript-maps should provide portable implementations.

[hdgarrood]

@sharkdp you're right, we would expect StrMap to win on lookup. It will do worse on pretty much any operation which returns a new StrMap, though: insert, update, delete, pop, update, and so on, because we have to create an entire new JavaScript object. Also, it's very easy to write functions with StrMap which are quadratic when they should be linear or O(n log n) or similar as a result of this.

[paf31]

👍

[sharkdp]

@natefaubion Absolutely agreed. I was just surprised by "asymptotically it's significantly worse than Map String for many operations".

@hdgarrood Thank you for the clarification.

[nwolverson]

The documentation is a little misleading in using the words "to maximize performance" without making clear the situations where StrMap may or may not be performant (i.e. that like Array it's a persistant data structure implemented via cloning - just had this discussion on IRC.

As point of reference I sort-of ported purescript-maps to the Erlang backend, and while I was able to provide something usefully like StrMap, I needed to rip out Data.StrMap.ST anyway, and rewrite the mutation-based implementation of much of Data.StrMap.

It also does feel like 2 separate libraries, given there is no inter-reference and not even a shared module name...

[hdgarrood]

Do we think the new purescript-js-objects library should be in core? Or maybe contrib would be better, since it wouldn't be portable?

[paf31]

Every runtime already needs to implement records anyway, so I think it can be portable. The only non-portable bit is due to the way JS implements things like __proto__ fields, I think.

[hdgarrood]

Also traversal order?

[hdgarrood]

Plus:

> SM.lookup "hasOwnProperty" SM.empty :: Maybe Unit
(Just unit)

although I guess we can fix that by using Object.create(null) rather than {}.

[paf31]

I think we can make the Traversable instance work properly and portably though, by getting a list of keys first, and then traversing in key order.

[hdgarrood]

If the main use case for StrMap is JS interop, surely the current Foldable and Traversable instances are the right ones?

[paf31]

Why's that? Is insertion order important for JS interop? I've never needed it.

[hdgarrood]

Nor have I, but then again I've never used PureScript alongside a large and terrible JS codebase; I'm sure there's plenty of JavaScript code out there which does depend on iteration order. I think it's reasonable for people to expect to be able to translate for (var key in obj) {...} to for_ obj \key -> ... without anything changing; JavaScript objects have an iteration order already so I think the obvious choice is to use it.

[natefaubion]

I agree with @hdgarrood. If the goal is JS-object interop, it should be JS iteration order.