Fork me on GitHub

@dnolen: For equality checks between two Lean HAMT's I'm seeing a (8 - 10)x speed up in the worst case (comparing equal maps that have no structural sharing) and around (60 - 100)x speed up when comparing two maps that have structural sharing. I've run collection check for 10000 iterations to make sure I'm wasn't missing anything and have tried to think of any scenarios where the equality check is incorrect or has a worse case perf but haven't found one so far.


The same technique used for equality checks should be applicable to diffing two Lean HAMT's


Indeed, I didn't believe the results when I first got it working (they seemed too good) but so far everything checks out

Alex Miller (Clojure team)19:12:46

I assume these numbers are in the context of comparing maps that are equal. Have you done any tests on cases where they are not equal? Was curious if the failures were faster too or if that's a wash.


Only for unequal maps with structural sharing. I used the worse case of one different value.

Alex Miller (Clojure team)19:12:25

oh, cool. What about equal then?

Alex Miller (Clojure team)19:12:50

I assume significantly faster failures would be a big help for react dom comparisons?


@alexmiller: yes it can help


The location of the one different value is the determining factor for the current HAMT implementation, it really makes no difference for the Lean HAMT since the equality algorithm is log n


@alexmiller: @spinningtopsofdoom: however note this makes a difference if the maps are big enough


another dimension worth looking at is how much this closes the gap with PersistentArrayMap


@dnolen agreed the maps I did perf testing for are size 100, 4000, and 10000


I'm looking into that now


For equality (with and without structural sharing ) it's about the same perf, for the worse case of equals failing (only one value changed )it's about 2x slower