Even a pointer towards the part of the source that handles it would be a good start

https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/LineNumberingPushbackReader.java

Thanks a ton!

Anyone know why the indentation is inconsistent in this class? the constructor has a tab of 8 and some of the other methods are 4…. 😄

and one of the methods isn’t indented at all

welcome to $root/src/jvm

the code is immutable too? 😄

if you don't change it, you don't break it :)

The Clojure core team is not a stickler for changes having indenting consistent with the original code. And it is a stickler for not making wholesale code changes just for whitespace.

I recommend running a pretty-formatter-thingy on it before browsing it, if it bothers you.

It doesn’t bother me one bit. Just curious that’s all

Oh, here we go, never mind! https://clojurians.slack.com/archives/C03S1KBA2/p1679254983827799?thread_ts=1679245480.586599&channel=C03S1KBA2&message_ts=1679254983.827799

The discussion: https://twitter.com/meekaale/status/1777963616144171073 (It’s a bit sad reading in parts, you have been warned).

Equality checks aren't really very efficient when the two structures do not share ancestry 😅

Ha!

So it's more a case of it being possible, because they're values, not that it's always fast

Cool. Then I can relax. This has been bothering me a while.

I know the feeling 😄

Even when they do share stuff, it's not as efficient. For hash maps, for example, it still boils down to comparing all kv-pairs when the size is the same.

Just double-checked tree maps and vectors - same thing.

hashes

No. :)

(def a {:a 1 :b 2})
(def b {:b 2 :a 1})
(= a b) ;=> true
(= (hash a) (hash b)) ;=> true

= doesn't use hash.

Not for some call paths?

Isn't that why "deep equality" gets you so much for free?

(def a {:a 1 :b 2})
  (def b {:b 2 :a 1})

  (time
   (dotimes [i 10000000]
     (= a b)))

  "Elapsed time: 620.7485 msecs"

  (time
   (dotimes [i 10000000]
     (identical? a b)))

  "Elapsed time: 12.702459 msecs"

There is no deep equality in the code.

It's just a few Java classes, there's no magic in there - you can trace the whole path = takes to return something for any combination of types.

identical? is fun in the sense that (identical? {} {}) is true but (identical? {:a 1} {:a 1}) is false. For unrelated reason, though.

Because of the int or what?

No, it has to be the empty map that's the special case, right?

Because identical? is == in Java. It doesn't look inside the object at all. {} is identical to another {} only because the reader expands it to the same static constant.

Right

Naming it == would have been less trippy, but I’m sure there are reasons.

== is already taken. And it'd be less trippy only for people who already know Java.

Oh, there’s already a ==

I had need for that the other day!

Well, = might not use hash but to answer the question of "How are equality checks between large data structures made efficient?", isn't that generally done by hashing? And Clojure uses hash equality checks internally a lot for efficiency reasons, right?

No and no. A "large data structure" is a very ambiguous term. Try computing (hash (map identity (range))). Even a finite collection requires a full loop over its contents to compute its hash. Of course, the hash can be and is often cached. If we're comparing two collections that have their hashes cached, equality can potentially be made faster. But at the cost of behaving differently in the bad cases when two collections are considered equal by the current impl but have different hashes.

Well, that sounds pretty good I guess 🙂

Yeah, I guess I'm conflating the equality of immutability with hash equality. I didn't realize vectors and array-maps completely ignore the hash values of their items. Seems surprising, if you know you're comparing two immutable things with the same hashing semantics, why not just use the hashes?

Because the hash isn't computed in advance. It's computed on demand.

And that aforementioned "comparing things that break the quality/hashing rule or whatever it's called".

> why not just use the hashes? also, hash collisions.

> hash collisions I think John talks only about an early return of false.

Honestly, all the datatypes that impl IHash, I thought it was mostly for more efficient comparisons. But they're mostly just for hash maps and hash sets?

Yes. For everything that requires hashes.

Chance of collision is pretty low though, right? Is a collision domain good enough for hash sets not good enough for deep equality check?

Oh, case might also use hashes. > Chance of collision is pretty low though, right? Not really. Especially when the hash algorithm is known by a potential attacker.

I mean don't use this for crypto lol

The hashing of objects, it's just supposed to be cheap and not require cryptographic strength

I see what you're saying though, you can't depend on that for deep equality check

> I mean don't use this for crypto lol You underestimate how important proper hashing is. It has nothing to do with crypto.

Well, there's no such thing as a perfect collision domain. The hash is smaller than the object, so obviously there's collisions

For shits and giggles, I just tried this:

Clojure 1.11.2
user=> (require '[clojure.spec.alpha :as s])
nil
user=> (require '[clojure.spec.gen.alpha :as gen])
nil
user=> (require '[clojure.test.check.generators])
nil
user=> (def data (gen/sample (s/gen string?) 1000000))
#'user/data
user=> (doseq [a data, b data, :when (not= a b)] (when (= (hash a) (hash b)) (prn a b)))

> Well, there's no such thing as a perfect collision domain. The hash is smaller than the object, so obviously there's collisions True. But if an attacker can submit some data to your server and knows that that data is cached in the same hash map, they can bring your server to a halt by feeding it just the right data. One particularly nasty case is using keyword on user data. I don't know if that's been (or can be) handled though.

What's a key that when passed to a map will return the value of :secret

That's... absolutely not what I meant.

Hash maps don't store a single value under a specific hash.

By exploiting hash collisions, an attacker can make a known hash map put all the data into the same bucket, turning O(1) into O(n).

https://en.wikipedia.org/wiki/Collision_attack#Hash_flooding

hash flooding

Thanks. :) I suck at recalling names of any nature.

Yeah, I get you're point about deep equality checking. But is it possible for hashmaps and hash sets to have any false negatives or false positives on a wrong key? Or do they always always do a full equality check?

Not possible. First a hash check, then an equality check.

We'd be in a very bad place otherwise.

just to be totally pedantic, first the hash is used to navigate the trie structure (HAMT), then equality used to confirm sameness

that's what I thought, it was used internally

it's not a slowpath/fastpath kind of thing

But can we assume two different maps with the same hash are equal or no?

no

I guess it depends on the size

you can assume that two equal maps have the same hash, not the reverse

right, because they could have mutable items

Even that assumption rests on the "equal things generate equal hashes" rule. Ghadi, please recall the name of the rule for me. :D

no, it has nothing to do with mutability

@U050PJ2EU No, because hash implementation is technically independent from equality implementation. You can make the first always return 1 and the second ask an atomic clock.

right

https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/lang/Object.html#hashCode()

read the method docstring for Object.hashCode()

the simplest hash is a counter, right? as long as each is unique in a given runtime is good enough in some cases, right?

Oh, and some data structures don't have commutative equality, which doubles the fun.

> the simplest hash is a counter, right? Such an impractical hash can be made even simpler by always returning the same constant or a random number. There is no practical way of implementing a global counter for all possible data types and values.

So what do hashing datastructures use the hash for? partitioning? randomizing the distribution?

Well, if it's not found, it's absolutely not found

Are you asking for a tl;dr for the Wiki page on hash tables? :)

false negatives aren't possible

And when you have a positive, you double check key's equality

that makes sense

Still, if I'm iterating through two lists, comparing pairs of items for equality, and I see two maps and their hashes are different, then I know I don't even need to travers those maps to check. If they have different hashes, they're definitely not equal. So why not use that hash when doing that comparison?

> and I see two maps and their hashes are different For that, you first need to compute the hashes. What is the hash of {:a (range)}? > If they have different hashes, they're definitely not equal. Using it in = would break it because there absolutely are cases out there that don't adhere to the contract of hashCode that Ghadi has linked above.

You might be able to implement = in a way that uses hashes and doesn't return false results. It will probably be a spaghetti with lots of ifs where you check type combinations. And in the end, it will break a lot of existing code because not everything is hashable (throw or inf loop) and not everything adheres to the contract of hashCode.

Hmm, I thought hash was getting called on creation of a type impling IHash. I guess I figured lazy seqs got a random hash or something. How is the hash computed when something within an infinite seq is in the key position?

(def a {{:x (range)} {:x (range)}
        :b {:c :d}})
(-> a :b hash) ; => -1916895501

Call type on that map.

Yeah so this hangs:

(def a
  (->> (range 20)
       (map (fn [n]
              [{:x (range)} n]))
       (into {})))

I'm surprised it doesn't throw.

That's running in cljs

but this also hangs:

(def a {:x (range)})
(def b {:x (range)})
(= a b)

Ah, it doesn't throw because it hangs even with (range 2), because it tries to compare the keys. This, on the other hand, throws: (def x (into {} (map (fn [n] [{n (range)} n])) (range 10))).

hangs in cljs

In CLJS, even (hash (range)) hangs. It throwing in CLJ is a recent change, CLJ-2839.

Anyway, so = does this too, so same deal

If you have two deeply nested collections, and one was created by doing update on a few key/val pairs from the other using Clojure's update or assoc, then note that = comparison between them can be made faster by the fact that many of the sub-collections will return true for identical?, and Clojure's = does check identical? quickly before any other checks.

It might be nice if = checked to see if the hash value was already calculated and stored for two collections, and if so, return false quickly if their hashes are different, but IIRC Clojure does not have such code.

Well I definitely had the wrong idea how that worked. I thought hashes were used more for equality checking

I think we could get hash-boosted equality if we used immutable collections backed by merkle trees rather than HAMTs. But I believe merkle trees are significantly slower than HAMTs for almost all common use cases (except for equality comparison, which is O(1)). Also, the memory overhead of keeping a long hash (eg SHA-512) for each element is significant. (for people curious about merkle trees, I suggest looking into IPFS)

Interesting. Looks like unison uses 512 bit hashes for all elements and types

A clojure on unison would be neat