Primitive function boxes and unboxes result value

134 views
Skip to first unread message

Gunnar Völkel

unread,
Nov 20, 2012, 10:34:49 AM11/20/12
to clo...@googlegroups.com
I have written a primitive function for exponentiation with integers as power using the multiply-and-square algorithm.
For performance reasons I used primitive type hints for the arguments and the return value.
Profiling the whole application I noticed that there are a lot of java.lang.Double/valueOf calls.
Looking at the bytecode I see that in Clojure 1.3 as well as in Clojure 1.4 the result value gets boxed and unboxed like Double.valueOf(result).doubleValue().

Am I doing something wrong? Is there a serious bug related to the support of primitive functions?

The source code:

(defn first-bit?
  {:inline (fn [n] `(== 1 (clojure.lang.Numbers/and ~n, 1)) )}
  [^long n]
  (== 1 (clojure.lang.Numbers/and n, 1)))

(defn exp-int
  ^double [^double x, ^long c]
  (loop [result 1.0, factor x, c c]
    (if (> c 0)
        (recur
         (if (first-bit? c)
           (* result factor)
           result),
         (* factor factor),
         (bit-shift-right c 1))
      result)))

Last lines of the Java bytecode of `exp-int`:
59 dload 5;               /* result */
61 invokestatic 40;       /* java.lang.Double java.lang.Double.valueOf(double c) */
64 checkcast 85;          /* java.lang.Number */
67 invokevirtual 89;      /* double doubleValue() */
70 dreturn;

Gunnar Völkel

unread,
Nov 20, 2012, 11:20:33 AM11/20/12
to clo...@googlegroups.com
I can add some additional information. I compiled the fibonacci example with double and long type hints:

(defn fib ^long [^long n]
  (if (<= n 1) 1 (+ (fib (dec n)) (fib (- n 2)))))

(defn fib ^double [^double n]
  (if (<= n 1) 1 (+ (fib (dec n)) (fib (- n 2)))))

The one with ^long works as expected but the one with ^double has the Double.valueOf(result).
doubleValue() bytecode before the return.

Christophe Grand

unread,
Nov 20, 2012, 12:15:08 PM11/20/12
to clojure
Hi,

It looks like, because of the recur, the compiler fails to notice that if returns a primitive.
As far as I understand in Compiler.java, RecurExpr does not implement MaybePrimitiveExpr and thus causes on canEmitPrimitive the surrounding IfExpr to return false.

Someone to confirm this analysis?



--
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



--
Professional: http://cgrand.net/ (fr)
On Clojure: http://clj-me.cgrand.net/ (en)

Andy Fingerhut

unread,
Nov 20, 2012, 12:30:10 PM11/20/12
to clo...@googlegroups.com
Any relationship to CLJ-701, other than similar symptoms?


Andy

David Nolen

unread,
Nov 20, 2012, 1:01:09 PM11/20/12
to clojure
I can't speak to the implementation details but loop/recur does not return primitives in my experience.

Christophe Grand

unread,
Nov 20, 2012, 4:27:54 PM11/20/12
to clojure
I think CLJ-701 is about loop in non-terminal position.


--
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

Christophe Grand

unread,
Nov 21, 2012, 6:21:43 AM11/21/12
to clojure
I created an issue and attached a patch http://dev.clojure.org/jira/browse/CLJ-1111

Now the 5 last lines of bytecode are:
   52:  goto    9
   55:  goto    61
   58:  pop
   59:  dload   5
   61:  dreturn

Christophe

Gunnar Völkel

unread,
Nov 21, 2012, 7:34:16 AM11/21/12
to clo...@googlegroups.com, chris...@cgrand.net
I think Cristophe is on the right path. But it is possible that there is another Bug concerning primitive functions.
Consider the following two functions:


(defn fib ^long [^long n]
  (if (<= n 1) 1 (+ (fib (dec n)) (fib (- n 2)))))

(defn fib2 ^double [^double n]
  (if (<= n 1) 1 (+ (fib2 (dec n)) (fib2 (- n 2)))))

The bytecode of `fib` ends as expected with
42 invokestatic 81;       /* long clojure.lang.Numbers.minus(long arg0, long arg1) */
45 invokeinterface 77 3;  /* long invokePrim(long arg0) */
50 invokestatic 84;       /* long clojure.lang.Numbers.add(long arg0, long arg1) */
53 lreturn;

But `fib2` boxes and unboxes again:
45 invokestatic 83;       /* double clojure.lang.Numbers.minus(double arg0, long arg1) */
48 invokeinterface 79 3;  /* double invokePrim(double arg0) */
53 invokestatic 87;       /* double clojure.lang.Numbers.add(double arg0, double arg1) */
56 invokestatic 92;       /* java.lang.Double java.lang.Double.valueOf(double arg0) */
59 checkcast 94;          /* java.lang.Number */
62 invokevirtual 98;      /* double doubleValue() */
65 dreturn;

I also rewrote the multiply-and-square algorithm so that it does not use `loop`:
(defn multiply-and-square
  ^double [^double result, ^double factor, ^long c]

  (if (> c 0)
    (recur
       (if (first-bit? c)
         (* result factor)
         result),
       (* factor factor),
       (bit-shift-right c 1))
    result))

(defn exp-int2

  ^double [^double x, ^long c]
  (multiply-and-square 1.0, x, c))

Here the bytecode of `exp-int2` looks fine, but the recursive function `multiply-and-square` performs the boxing and unboxing again:
43 dload_1;               /* result */
44 invokestatic 70;       /* java.lang.Double java.lang.Double.valueOf(double factor) */
47 checkcast 72;          /* java.lang.Number */
50 invokevirtual 76;      /* double doubleValue() */
53 dreturn;

Christophe, can you try `fib2` with your patched Clojure?

Christophe Grand

unread,
Nov 21, 2012, 8:41:26 AM11/21/12
to clojure
Hi Gunnar,

The only thing I fixed is related to recur (whose type was null and thus not unifiable with a primitive type).

Concerning your fib2, I think the proble comes from the "then" being a long (1) and the else a double.
Thus boxing is required to return either a long or double (well a Long and a Double).
I think if you change fib2 to always return double you'll see the boxing ops go away:


(defn fib2 ^double [^double n]
  (if (<= n 1) 1.0 (+ (fib2 (dec n)) (fib2 (- n 2)))))

Concerning multiply-and-square, since my patch deals with correctly typing recur in a primitive context, it is solved:

   35:  dstore_1
   36:  goto    0
   39:  goto    44
   42:  pop
   43:  dload_1
   44:  dreturn

Christophe


On Wed, Nov 21, 2012 at 1:34 PM, Gunnar Völkel <gunnar....@googlemail.com> wrote:
(defn fib ^long [^long n]
  (if (<= n 1) 1 (+ (fib (dec n)) (fib (- n 2)))))



Gunnar Völkel

unread,
Nov 21, 2012, 3:55:58 PM11/21/12
to clo...@googlegroups.com, chris...@cgrand.net
Of course. You are right. I did forget about the long constant.
I hope your patch will be included in Clojure 1.5.
Reply all
Reply to author
Forward
0 new messages