Hello, again. Just wanted to clarify, in case the below speedup didn't
seem worth it. That 6% speedup was in the top-level uuid/v1 function, not
mask!
I'll try to give a clearer picture of my suggestion: Consider
(let [bitmask (mask 8 (* 8 (dec 7)))
off (mask-offset bitmask)
moff (>>> bitmask off)]
(defn ^long ldb6 [^long num]
(bit-and moff (bit-shift-right num off))))
This function gives a speedup of 370% over calling (ldb (mask ...) num),
because you don't really need to calculate the mask, offset, or offset-mask
at runtime.
I envisioned writing a macro that would write the function
(let [bitmask0 (mask 8 (* 8 (dec 1)))
off0 (mask-offset bitmask0)
moff0 (>>> bitmask0 off0)
...]
(defn ^long ldb-j [^long j ^long num]
(case j
0 (bit-and moff0 (bit-shift-right num off0))
...
7 (bit-and moff7 (bit-shift-right num off7))
(throw IAE))))
Or just write the unrolled version by hand. I think you would get a fair
speedup if you did that for ldb and dpb.
Hoping that's clearer,
Leif
On Monday, February 23, 2015 at 9:20:12 PM UTC-5, Leif wrote:
>
>
> If you're trying to squeeze every last bit of performance, and you don't
> mind some messiness and macros, I noticed that many of these functions are
> called with only a few values in the first argument. So you are doing a
> lot of bit-fiddling at runtime that could be done at compile-time. So you
> could partially evaluate (i.e. unroll, i.e. ~make lookup table for) 'ldb'
> and 'dpb' for the 8 or 9 different first arguments you actually call it
> with. I unrolled your 'mask' fn into a 8-way case statement, and got about
> 6% speedup.
>
> --Leif
>
> On Monday, February 23, 2015 at 1:59:32 PM UTC-5, [email protected] wrote:
>>
>> So, much of the pain involved in handling UUID's correctly on the JVM
>> relates to the fact that there is no primitive unsigned numeric type
>> that can represent the full range of possible values of the msb and lsb.
>> Ie., we need to always deal with the unpleasant "am I negative?" approach
>> to
>> reading (writing) that 64th bit. To avoid the complexity of all the
>> edge cases, we encapsulate the basic primitives of working with
>> unsigned numbers entirely within the abstraction of "mask" and
>> "mask offset". Using these, we built the two fundamental bitwise
>> operations
>> that are used for most of the UUID calculation: ldb (load-byte) and
>> dpb (deposit-byte).
>>
>> This scrap of code from my clj-uuid.bitmop library is extremely useful
>> for working
>> with "unsigned" long/binary values (analogously to how one might using
>> the common-lisp
>> functions by the same name). And, it has been "good enough" to do pretty
>> well
>> so far in terms of performance. But I'm sure that there are gifted
>> binariticians
>> in the audience that can improve this. (Note, the namespace uses
>> ztellman/primitive-math
>> which changes the semantics of some arithmetic operations and some type
>> hinting. Also
>> some of the 'let's are there for that reason. It may be helpful to refer
>> to the link.
>>
>> ;;;
>> https://github.com/danlentz/clj-uuid/blob/master/src/clj_uuid/bitmop.clj
>>
>>
>> (defn ^long expt2 [^long pow]
>> (bit-set 0 pow))
>>
>> (defn ^long mask [^long width ^long offset]
>> (if (< (+ width offset) 64)
>> (bit-shift-left (dec (bit-shift-left 1 width)) offset)
>> (let [x (expt2 offset)]
>> (bit-and-not -1 (dec ^long x)))))
>>
>> (declare ^long mask-offset ^long mask-width)
>>
>> (defn ^long mask-offset [^long m]
>> (cond
>> (zero? m) 0
>> (neg? m) (- 64 ^long (mask-width m))
>> :else (loop [c 0]
>> (if (pos? (bit-and 1 (bit-shift-right m c)))
>> c
>> (recur (inc c))))))
>>
>> (defn ^long mask-width [^long m]
>> (if (neg? m)
>> (let [x (mask-width (- (inc m)))]
>> (- 64 ^long x))
>> (loop [m (bit-shift-right m (mask-offset m)) c 0]
>> (if (zero? (bit-and 1 (bit-shift-right m c)))
>> c
>> (recur m (inc c))))))
>>
>> (defn ^long ldb
>> "Load Byte"
>> [^long bitmask ^long num]
>> (let [off (mask-offset bitmask)]
>> (bit-and (>>> bitmask ^long off)
>> (bit-shift-right num off))))
>>
>> (defn ^long dpb
>> "Deposit Byte"
>> [^long bitmask ^long num ^long value]
>> (bit-or (bit-and-not num bitmask)
>> (bit-and bitmask
>> (bit-shift-left value (mask-offset bitmask)))))
>>
>
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
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 [email protected].
For more options, visit https://groups.google.com/d/optout.
