2
\$\begingroup\$

I want to create a wrapper class for byte arrays so that I can use them as keys in fastutil's Object2LongAVLTreeMap. I have created a wrapper like this:

(deftype Bytes [^bytes ba]
  Comparable
  (compareTo
    [this other]
    (let [m (alength ^bytes (.ba this))
          n (alength ^bytes (.ba other))
          l (min m n)]
      (loop [i 0]
        (if (< i l)
          (let [a (aget ^bytes (.ba ^Bytes this) i)
                b (aget ^bytes (.ba ^Bytes other) i)
                d (compare a b)]
            (if (zero? d)
              (recur (inc i))
              d))
          (compare m n))))))

The wrapper needs to implement Comparable for the insertions in the AVL Tree.

I am looking for feedback regarding my overall approach and my implementation of compareTo. I will be inserting lots of entries into the tree so I don't want to be creating unnecessary objects, etc. during the comparison.

EDIT: I believe the code above has a bug. See my comment below.

\$\endgroup\$
  • \$\begingroup\$ I wouldn't have accepted my answer quite yet. A little over an hour isn't very long for a question to be up on Code Review. \$\endgroup\$ – Carcigenicate Mar 23 at 13:44
  • \$\begingroup\$ Ah okay. I'll leave it open a little longer. Thanks for point out the reflection issue. \$\endgroup\$ – Martin Harrigan Mar 23 at 20:22
  • \$\begingroup\$ Np. Honestly, considering it's outside the loop, the effect will likely be minimal, but it's the only thing I noticed. \$\endgroup\$ – Carcigenicate Mar 23 at 20:31
  • \$\begingroup\$ I believe the code above has a bug: (compare a b) compares two (signed) bytes. For example, if a is (unchecked-byte 0xFF) and b is (unchecked-byte 0x00)), it returns -1 rather than 1. In my case, this caused the byte arrays to be inserted incorrectly in the AVL tree. A solution is to set a to (bit-and (aget ba i) 0xFF) and b to (bit-and (aget ^bytes (.ba ^Bytes o) i) 0xFF). \$\endgroup\$ – Martin Harrigan Mar 24 at 13:38
1
\$\begingroup\$

First, your calls to .ba aren't being resolved for other, so that's forcing use of reflection. If you run lein check, you'll see:

Reflection warning, thread_test.clj:22:22 - reference to field ba on java.lang.Object can't be resolved.

This has the potential to slow the method down, although it only happens once per call, so the effect wouldn't be huge.

Use explicit type hints to ensure it knows what types you're working with, just like you did below that:

(let [m (alength ^bytes (.ba ^Bytes this))
      n (alength ^bytes (.ba ^Bytes other))

I tried type hinting the parameters instead, and got an error I've never gotten before. I think it was looking for a compareTo with Object parameters, so saying the parameters were Bytes was throwing it.


Other than that, I don't see anything performance related. I'll just point out, in case you don't know, this' ba is actually in scope. You can use it directly which gets rid of some bulk, although makes some of the code less symmetrical:

(deftype Bytes [^bytes ba]
  Comparable
  (compareTo
    [_ other]
    (let [m (alength ba) ; Here
          n (alength ^bytes (.ba ^Bytes other))
          l (min m n)]
      (loop [i 0]
        (if (< i l)
          (let [a (aget ba i) ; And here
                b (aget ^bytes (.ba ^Bytes other) i)
                d (compare a b)]
            (if (zero? d)
              (recur (inc i))
              d))
          (compare m n))))))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.