The following was originally published June 2, 2008 at http://clojure.sourceforge.net/news/primitive_support.html
Dismayed by a recent request to embed Java code in Clojure code (yuck), I've tried over the past week to address the only area in which such an endeavor might be reasonable: to attain the arithmetic performance of the Java primitives, and I'm happy to report much success in making that possible directly in Clojure.
This has traditionally been a difficult area for dynamic languages, with their emphasis on treating objects, including numbers, uniformly. On the JVM, that means 'boxing' numbers into some Object (for Clojure, these Objects are the derivees of Java.lang.Number - Integer, Long etc.) The JVM doesn't have support for fast arithmetic with such Numbers, only for 'primitives', the special types int, long, double, float in Java.
Lisp (and Clojure) imposes an additional constraint, that the math be correct - i.e. integer arithmetic should not silently produce corrupt values due to overflow.
Clojure already supported auto-boxing/unboxing in calls to Java methods that take/return primitives, and type inference that tracks the types of calls in order to determine the types of subsequent calls. The trick is to get to the high-performance primitives without turning Clojure into Java, specifically, avoiding lots of type declarations, and lots of additional complexity in the compiler for generating bytecode for primitives.
All of this leans on a tremendous capability of the JVM's HotSpot runtime - given a call to a function whose body contains a call to a primitive operation, and frequent use in a running program, HotSpot will, at runtime, inline those calls by substituting the primitive operation. This means that Clojure's bytecode generator need not know about, nor generate, the bytecodes for arithmetic primitive operations (it doesn't). Note that this inlining capability is limited to within a single fn definition - across fn calls all args/returns are Objects.
In order to facilitate this I've:
Added support for direct passing of primitives between Java method calls with no intervening boxing.
Added support for conditional test of boolean method returns without conversion to Boolean.
Added support for compiler inlining - a specification to the compiler that a function may be inlined, by providing a macro-like expander to be used to replace a direct call to the function. The difference vs a macro is that the resulting function is a proper fn, and can be used as a value, passed to map/reduce/filter etc.
Added support for let/loop-bound locals of primitive types, and the inference to support that. They now have the inferred, possibly primitive type of their init-form.
Added support for recurs that rebind primitive locals without boxing, and type-checking for same.
Overloaded arithmetic (+,-,*,/,inc,dec,<,<=,>,>= etc) for primitive types where semantics are same.
Overloaded aget/aset for arrays of primitives
Added overloaded aclone, alength for arrays of primitives
New constructor fns for primitive arrays: float-array, int-array, etc
Added special type hints for primitive arrays - #^ints, #^floats, #^longs, #^doubles
Coercion ops int/long/float/double now produce primitives
Added a num coercion which boxes primitives
Added cast ops ints/longs/floats/doubles which produce int[]/long[]/float[]/double[] types
Made seq much faster for arrays of primitives
Added set of "unchecked" operations for utmost performing, but potentially unsafe, integer (int/long) ops: unchecked-add/subtract/multiply/divide/inc/dec
Added amap and areduce macros for functionally (i.e. non-destructively) processing one or more arrays in order to produce a new array or aggregate value respectively.
The bottom line - rather than write this Java:
static public float asum(float[] xs){
float ret = 0;
for(int i = 0; i < xs.length; i++)
ret += xs[i];
return ret;
}
you can now write this Clojure:
(defn asum [#^floats xs]
(areduce xs i ret (float 0)
(+ ret (aget xs i))))
and the resulting code is exactly the same speed (when run with java -server).
Similarly:
static public float[] vmul(float[] x, float[] ys){
final float[] xs = x.clone();
for(int i = 0; i < xs.length; i++)
xs[i] *= ys[i];
return xs;
}
becomes:
(defn amul [#^floats xs #^floats ys]
(amap xs i ret
(* (aget ret i) (aget ys i))))
and the resulting code is exactly the same speed.
One notable difference is the behavior of integer primitives (int/long) when overflowing:
That is, all numeric literals are boxed, and all boxed arithmetic is generic (e.g. promotes type on overflow), and generic arithmetic is contagious, but unboxed primitives throw exceptions on overflow (except the unchecked- ones, which do as Java does):
The best aspect of this is that you need not do anything special in your initial coding. Quite often these optimizations are unneeded. Then, should a bit of code be the bottleneck, you can speed it up with minor adornment:
removed implement, use proxy
renamed set to ref-set
renamed ! to send
renamed select to select-keys
renamed to-set to set
renamed scan to dorun
renamed touch to doall
Thanks to all for your feedback and support!
Rich
Changelist:
added dosyncfixed when-first when empty non-seq collsetup default bindings for smap before/aftertightened smap rangere-enabled clearing locals on tail calls, but track locals used in catch/finally clauses and avoid clearing themmade FnExpr publicadded locals clearing on tail callsadded arg clearing on tail callshost calls - use subsuming method, if any, rather than first found, when overloaded w/same aritymade Repl load files in 'user ns, changed Repl to serve as better example of hosting Clojure in Java using public APIsmade IFn extend Runnablestricter overload resolution accessible macro metadata via *macro-meta* more type hints in boot.cljfixed send, send-off docs(str false) => "false"got rid of input purge on exceptionchanged use of ! to send in await, await-foradded if-let, when-let, replacemade distinct lazyswitched to readLine on input purge in Repl exception handleradded newline on EOFproxy - filter all considered methods in superclass traverse, to avoid implementing method turned final in derivedintern compiled string literalsrepl - added System.exit callrenamed ! to send, added send-off, *agent* is currently running agentfixed bug with invoke >= MAX_POSITIONAL_ARGSfixed slurp not closing filefixed build dep of Keyword on AFn, added throwArity to Keywordprevent nested #()son repl exception, put cause message firstprevent take from advancing coll more than n timesimproved error message for bad arityadded flush and read-linefixed bug in ASeq toArray(Object[])bind source paths when reading boot scripts from jar switched to Clojure's box from ASM's in proxy in order to handle booleans correctlyproxy - make method set union of declared and public methods in order to catch unimplemented interface methods of abstract classesnew metadata/docstringsfixed ns prefix on fns - now clojure.fns.fixed fn name propagation, added clojure.fns. namespace segment prefix on all generated fnsmoving to new metadata/docstringspersistent vector - keep tail out of tree, speeding up cons/popadded new metadata/docstring handling to defn, type hint to defmethod, begin moving to new metadata/docstringsmade munge public, upped SMAP range to 10000renamed PersistentHashMap.INode.seq to nodeSeq to avoid override of AMapEntry.seq in Leaffixed MapEntry.seq to use AMapEntry.seqfixed hash-set of empty coll/nilrenamed select select-keysrenamed set to ref-setrenamed to-set to set, returns a set nowadded set.clj, set operations and 'relational' algebrafixed bug with nested try blockssets - read/print/compile/metadata, hash-set, sorted-set, disjstarting set supportadded EnumerationSeq and support for Enumerations in seqadded SeqEnumerationadded destructuring to loopadded slurp, subs, max-key, min-keydoc reformattingfixed declared method detectionunified map entry and vector equality and hashsupport conj of vector pair onto mapmade map entries vectorsproxy support auto-load xml.clj, zip.clj and proxy.clj from clojure.jaradded (class x), returns getClassadded cast cast arg to Number in unary +, *added var?, special-symbol?changed resolve to return nil if not foundadded tree-seq, file-seq, xml-seqtry using getContextClassLoader in implementtry using getContextClassLoader as defaultmore examplesadded zip.clj generic zipperadded symbol support for ->, so (-> x :a) ==> (:a x)added RT.var() helper, made CLOJURE_NS and CURRENT_NS publicxml - fix for mixed content, extensible parse accepts parser fncompleted docsallow use of not-yet-existing names qualified with current namespace when internNewget now returns nil on non-mapsfixed access on helpers, contains? now returns false on non-mapsavoid unread(-1)more docsreturn false consistently on < <= > >= ==defined dissoc for no keysfixed refer NPE on non-existent namespacecommand line args can follow '--', in Repl and Scriptprint doc indicates macro statusfind-doc sorts namesrenamed scan to dorun, touch to doall support for variadic assoc and dissocadded re-pattern, print-doc, find-docmore docsdoc formattingdoc macroadded anonymous fn reader syntax #(), and arg literals %, %1 ,%n %&added rand, rand-int and defn-changed prstr to pr-str in assertfixed self-call in defmulti macro
Dismayed by a recent request to embed Java code in Clojure code (yuck), I've tried over the past week to address the only area in which such an endeavor might be reasonable: to attain the arithmetic performance of the Java primitives, and I'm happy to report much success in making that possible directly in Clojure.
This has traditionally been a difficult area for dynamic languages, with their emphasis on treating objects, including numbers, uniformly. On the JVM, that means 'boxing' numbers into some Object (for Clojure, these Objects are the derivees of Java.lang.Number - Integer, Long etc.) The JVM doesn't have support for fast arithmetic with such Numbers, only for 'primitives', the special types int, long, double, float in Java.
Lisp (and Clojure) imposes an additional constraint, that the math be correct - i.e. integer arithmetic should not silently produce corrupt values due to overflow.
Clojure already supported auto-boxing/unboxing in calls to Java methods that take/return primitives, and type inference that tracks the types of calls in order to determine the types of subsequent calls. The trick is to get to the high-performance primitives without turning Clojure into Java, specifically, avoiding lots of type declarations, and lots of additional complexity in the compiler for generating bytecode for primitives.
All of this leans on a tremendous capability of the JVM's HotSpot runtime - given a call to a function whose body contains a call to a primitive operation, and frequent use in a running program, HotSpot will, at runtime, inline those calls by substituting the primitive operation. This means that Clojure's bytecode generator need not know about, nor generate, the bytecodes for arithmetic primitive operations (it doesn't). Note that this inlining capability is limited to within a single fn definition - across fn calls all args/returns are Objects.
In order to facilitate this I've:
Added support for direct passing of primitives between Java method calls with no intervening boxing.
Added support for conditional test of boolean method returns without conversion to Boolean.
Added support for compiler inlining - a specification to the compiler that a function may be inlined, by providing a macro-like expander to be used to replace a direct call to the function. The difference vs a macro is that the resulting function is a proper fn, and can be used as a value, passed to map/reduce/filter etc.
Added support for let/loop-bound locals of primitive types, and the inference to support that. They now have the inferred, possibly primitive type of their init-form.
Added support for recurs that rebind primitive locals without boxing, and type-checking for same.
Overloaded arithmetic (+,-,*,/,inc,dec,<,<=,>,>= etc) for primitive types where semantics are same.
Overloaded aget/aset for arrays of primitives
Added overloaded aclone, alength for arrays of primitives
New constructor fns for primitive arrays: float-array, int-array, etc
Added special type hints for primitive arrays - #^ints, #^floats, #^longs, #^doubles
Coercion ops int/long/float/double now produce primitives
Added a num coercion which boxes primitives
Added cast ops ints/longs/floats/doubles which produce int[]/long[]/float[]/double[] types
Made seq much faster for arrays of primitives
Added set of "unchecked" operations for utmost performing, but potentially unsafe, integer (int/long) ops: unchecked-add/subtract/multiply/divide/inc/dec
Added amap and areduce macros for functionally (i.e. non-destructively) processing one or more arrays in order to produce a new array or aggregate value respectively.
The bottom line - rather than write this Java:
static public float asum(float[] xs){
float ret = 0;
for(int i = 0; i < xs.length; i++)
ret += xs[i];
return ret;
}
you can now write this Clojure:
(defn asum [#^floats xs]
(areduce xs i ret (float 0)
(+ ret (aget xs i))))
and the resulting code is exactly the same speed (when run with java -server).
Similarly:
static public float[] vmul(float[] x, float[] ys){
final float[] xs = x.clone();
for(int i = 0; i < xs.length; i++)
xs[i] *= ys[i];
return xs;
}
becomes:
(defn amul [#^floats xs #^floats ys]
(amap xs i ret
(* (aget ret i) (aget ys i))))
and the resulting code is exactly the same speed.
One notable difference is the behavior of integer primitives (int/long) when overflowing:
(.MAX_VALUE Integer)
2147483647
(+ 2147483647 2147483647) ;generic
4294967294
(+ (.MAX_VALUE Integer) (.MAX_VALUE Integer)) ;primitive
java.lang.ArithmeticException: integer overflow
(+ (num (.MAX_VALUE Integer)) (.MAX_VALUE Integer)) ;generic
4294967294
That is, all numeric literals are boxed, and all boxed arithmetic is generic (e.g. promotes type on overflow), and generic arithmetic is contagious, but unboxed primitives throw exceptions on overflow (except the unchecked- ones, which do as Java does):
(unchecked-add (.MAX_VALUE Integer) (.MAX_VALUE Integer)) ;unchecked, unsafe
-2
The best aspect of this is that you need not do anything special in your initial coding. Quite often these optimizations are unneeded. Then, should a bit of code be the bottleneck, you can speed it up with minor adornment:
(defn foo [n]
(loop [i 1]
(if (< i n)
(recur (inc i))
i)))
(time (foo 100000))
"Elapsed time: 1.428 msecs"
100000
(defn foo2 [n]
(let [n (int n)]
(loop [i (int 0)]
(if (< i n)
(recur (unchecked-inc i))
i)))))
(time (foo2 100000))
"Elapsed time: 0.032 msecs"
100000
Feedback welcome as always,
Rich
Type in the content of your new page here.
The following was originally published March 29, 2008 at http://clojure.sourceforge.net/news/20080329_release.html
Many new features, including anonymous fn reader syntax, functional tree zippers, streamlined documentation and metadata in defn/defmacro, first-class sets and set algebra, proxies that can extend classes, comprehensive in-source documentation, and many new library functions. Not all of the new functionality has documentation in the prose part of the site yet, but the new API doc page should be comprehensive.
There is some renaming/removing in this release:
removed implement, use proxy
renamed set to ref-set
renamed ! to send
renamed select to select-keys
renamed to-set to set
renamed scan to dorun
renamed touch to doall
Thanks to all for your feedback and support!
Rich
Changelist:
added dosyncfixed when-first when empty non-seq collsetup default bindings for smap before/aftertightened smap rangere-enabled clearing locals on tail calls, but track locals used in catch/finally clauses and avoid clearing themmade FnExpr publicadded locals clearing on tail callsadded arg clearing on tail callshost calls - use subsuming method, if any, rather than first found, when overloaded w/same aritymade Repl load files in 'user ns, changed Repl to serve as better example of hosting Clojure in Java using public APIsmade IFn extend Runnablestricter overload resolution accessible macro metadata via *macro-meta* more type hints in boot.cljfixed send, send-off docs(str false) => "false"got rid of input purge on exceptionchanged use of ! to send in await, await-foradded if-let, when-let, replacemade distinct lazyswitched to readLine on input purge in Repl exception handleradded newline on EOFproxy - filter all considered methods in superclass traverse, to avoid implementing method turned final in derivedintern compiled string literalsrepl - added System.exit callrenamed ! to send, added send-off, *agent* is currently running agentfixed bug with invoke >= MAX_POSITIONAL_ARGSfixed slurp not closing filefixed build dep of Keyword on AFn, added throwArity to Keywordprevent nested #()son repl exception, put cause message firstprevent take from advancing coll more than n timesimproved error message for bad arityadded flush and read-linefixed bug in ASeq toArray(Object[])bind source paths when reading boot scripts from jar switched to Clojure's box from ASM's in proxy in order to handle booleans correctlyproxy - make method set union of declared and public methods in order to catch unimplemented interface methods of abstract classesnew metadata/docstringsfixed ns prefix on fns - now clojure.fns.fixed fn name propagation, added clojure.fns. namespace segment prefix on all generated fnsmoving to new metadata/docstringspersistent vector - keep tail out of tree, speeding up cons/popadded new metadata/docstring handling to defn, type hint to defmethod, begin moving to new metadata/docstringsmade munge public, upped SMAP range to 10000renamed PersistentHashMap.INode.seq to nodeSeq to avoid override of AMapEntry.seq in Leaffixed MapEntry.seq to use AMapEntry.seqfixed hash-set of empty coll/nilrenamed select select-keysrenamed set to ref-setrenamed to-set to set, returns a set nowadded set.clj, set operations and 'relational' algebrafixed bug with nested try blockssets - read/print/compile/metadata, hash-set, sorted-set, disjstarting set supportadded EnumerationSeq and support for Enumerations in seqadded SeqEnumerationadded destructuring to loopadded slurp, subs, max-key, min-keydoc reformattingfixed declared method detectionunified map entry and vector equality and hashsupport conj of vector pair onto mapmade map entries vectorsproxy support auto-load xml.clj, zip.clj and proxy.clj from clojure.jaradded (class x), returns getClassadded cast cast arg to Number in unary +, *added var?, special-symbol?changed resolve to return nil if not foundadded tree-seq, file-seq, xml-seqtry using getContextClassLoader in implementtry using getContextClassLoader as defaultmore examplesadded zip.clj generic zipperadded symbol support for ->, so (-> x :a) ==> (:a x)added RT.var() helper, made CLOJURE_NS and CURRENT_NS publicxml - fix for mixed content, extensible parse accepts parser fncompleted docsallow use of not-yet-existing names qualified with current namespace when internNewget now returns nil on non-mapsfixed access on helpers, contains? now returns false on non-mapsavoid unread(-1)more docsreturn false consistently on < <= > >= ==defined dissoc for no keysfixed refer NPE on non-existent namespacecommand line args can follow '--', in Repl and Scriptprint doc indicates macro statusfind-doc sorts namesrenamed scan to dorun, touch to doall support for variadic assoc and dissocadded re-pattern, print-doc, find-docmore docsdoc formattingdoc macroadded anonymous fn reader syntax #(), and arg literals %, %1 ,%n %&added rand, rand-int and defn-changed prstr to pr-str in assertfixed self-call in defmulti macro