equality checking of clojure data structures

[Jacob Goodson]

I was wondering something...

Would (= {:x 1} {:x 1}) be just as fast as (= 1 1) since maps are immutable?  The idea is that since clojure data structures are just values can they be compared much faster than there mutable counter parts?  Thanks.

[Andy Fingerhut]

(let [foo {:x 1}]

  (= foo foo))

is fast, because they are identical, and = is fast for things that are identical.

In general, two maps that are = are often not identical.

If two maps have different numbers of elements, = should quickly return false because of the way equiv() is implemented for maps, here: https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/APersistentMap.java#L73-L94

There is a check whether the maps are the same size, and if not, return false without checking all key/value pairs.

If they have equal number of key/value pairs, then it will iterate through all key/value pairs of one, checking whether the key of one is present in the other, and if so, whether their associated values are equiv() or not.

Those checks can be fast if the keys are quickly comparable, and the values are quickly comparable.

If you take one persistent map m1 and remove a few keys and/or add a few keys to produce m2, then all of the unchanged keys and values they have in common will be identical, and very quickly comparable.  The slowest part of comparing them would be comparing their non-identical parts.

Andy

On Sat, Jun 27, 2015 at 5:01 AM, Jacob Goodson <submissio...@gmx.com> wrote:

I was wondering something...

Would (= {:x 1} {:x 1}) be just as fast as (= 1 1) since maps are immutable?  The idea is that since clojure data structures are just values can they be compared much faster than there mutable counter parts?  Thanks.

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Jacob Goodson]

Thanks.

What about the perf of something like this...

({{:x 1 :y 2} :point} {:x 1 :y 2})

vs

({1 2} 1)

and what if the map was mutable as a key?

[Jacob Goodson]

One more thing, is it cheap to hash immutable maps vs mutable ones?

[Andy Fingerhut]

On this last question, most (maybe all) Clojure immutable collections store their hash value after it has been calculated once, so it need not be calculated again.

Even the first time a collection's hash is calculated, it is a function of the hash of its elements (set elements, or map keys & values), and if any of those are collections, and their hash has been earlier calculated and stored, then the stored value is used.

Andy