[CLJS-516] PersistentArrayMap keys uniqueness Created: 05/Jun/13 Updated: 19/Nov/13 Resolved: 19/Nov/13
|Reporter:||Sergey Kupriyanov||Assignee:||Michał Marczyk|
PersistentArrayMap does not check the uniqueness of keys at init.
PersistentHashSet also affected.
Simple (dirty?) workaround - init map by assoc.
|Comment by David Nolen [ 05/Jun/13 8:40 AM ]|
Yes that solution is likely too slow. Clojure already solved this problem, we should probably port the existing solution.
|Comment by David Nolen [ 04/Sep/13 11:08 PM ]|
|Comment by Michał Marczyk [ 05/Sep/13 1:29 AM ]|
From the commit message:
The approach taken is to (1) pour input into an array (or extract internal array with IndexedSeq), (2) construct output array by copying from the first array while checking for duplicates, (3) install output array in new array map.
Clojure does all that, except it also makes an initial pass over the array constructed in (1) to check if there are any duplicate keys. If in fact there are none, it skips (2) and just uses the original array in (3).
Crucially, there is a reason for this in Clojure which is absent in ClojureScript, namely if a new array is to be constructed, its length must be known ahead of time, so the check-for-duplicates loop also counts the number of unique items. In JS-land we can simply grow an array. Since presumably nobody's going to construct huge array maps ("slightly larger than the threshold" might make sense; a lot larger would totally kill performance), I don't think we'd gain much by avoiding the allocation, and if there are duplicates, it's good not to have to pay the price by doing the quadratic scan for duplicates twice.
I chose to pour non-IndexedSeq varargs into arrays so that the quadratic looping would be over an array rather than a seq.
|Comment by Michał Marczyk [ 20/Sep/13 8:48 PM ]|
Patch against current master.
|Comment by David Nolen [ 19/Nov/13 9:24 PM ]|