<< Back to previous view

[CLJS-516] PersistentArrayMap keys uniqueness Created: 05/Jun/13  Updated: 19/Nov/13  Resolved: 19/Nov/13

Status: Closed
Project: ClojureScript
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Minor
Reporter: Sergey Kupriyanov Assignee: Michał Marczyk
Resolution: Completed Votes: 1
Labels: bug

Attachments: Text File 0001-CLJS-516-make-array-map-work-as-if-by-assoc.patch    


PersistentArrayMap does not check the uniqueness of keys at init.

PersistentHashSet also affected.

cljs.user> (array-map 1 10 2 20 1 100)
{1 10, 2 20, 1 100}

cljs.user> (hash-set 1 1 2 3)
#{1 1 2 3}

Simple (dirty?) workaround - init map by assoc.

(defn array-map
  [& keyvals]
  (apply assoc cljs.core.PersistentArrayMap/EMPTY keyvals))

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 ]

See CLJS-583 and CLJS-584

Comment by Michał Marczyk [ 05/Sep/13 1:29 AM ]

Fix and test, independent of CLJS-583 and CLJS-584.

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 ]

fixed by CLJS-584 - https://github.com/clojure/clojurescript/commit/d929ae942bc2859cc7b684334affc1b590173f88 and CLJS-583 https://github.com/clojure/clojurescript/commit/fe9b5577cd9b9784d0c0c75edccc4441c99ee924

Generated at Fri Jul 21 16:13:21 CDT 2017 using JIRA 4.4#649-r158309.