ClojureScript

PersistentArrayMap keys uniqueness

Details

  • Type: Defect Defect
  • Status: Closed Closed
  • Priority: Minor Minor
  • Resolution: Completed
  • Affects Version/s: None
  • Fix Version/s: None
  • Component/s: None
  • Labels:

Description

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))

Activity

Hide
David Nolen added a comment -

Yes that solution is likely too slow. Clojure already solved this problem, we should probably port the existing solution.

Show
David Nolen added a comment - Yes that solution is likely too slow. Clojure already solved this problem, we should probably port the existing solution.
Hide
David Nolen added a comment -
Show
David Nolen added a comment - See CLJS-583 and CLJS-584
Michał Marczyk made changes -
Field Original Value New Value
Assignee Michał Marczyk [ michalmarczyk ]
Hide
Michał Marczyk added a comment -

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.

Show
Michał Marczyk added a comment - 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.
Michał Marczyk made changes -
Attachment 0001-CLJS-516-make-array-map-work-as-if-by-assoc.patch [ 12236 ]
Michał Marczyk made changes -
Attachment 0001-CLJS-516-make-array-map-work-as-if-by-assoc.patch [ 12236 ]
Hide
Michał Marczyk added a comment -

Patch against current master.

Show
Michał Marczyk added a comment - Patch against current master.
Michał Marczyk made changes -
David Nolen made changes -
Resolution Completed [ 1 ]
Status Open [ 1 ] Resolved [ 5 ]
David Nolen made changes -
Status Resolved [ 5 ] Closed [ 6 ]

People

Vote (1)
Watch (2)

Dates

  • Created:
    Updated:
    Resolved: