Enhanced Primitive Support, comparing versions 9 and 10 | Clojure Space

Enhanced Primitive Support

This document describes work in progress in the prim, num, equal and equiv branches. This work is not promised to become part of Clojure, as is or otherwise, now or in the future. The purpose of this document is to explain the work and encourage discussion.

Update redux: equiv, the revenge of num

The latest revision is in the equiv branch. It takes the approach of num, with no auto-promotion, and bigint contagion, but adds several things to better support contagion:

Uses equiv for =
- but narrows equiv, only same category numbers are =
- so floats not = to integers
  - but == still available for that
new clojure.lang.BigInt class
as with num, BigInts do not auto-reduce
- BigInts will enable optimizations when fits in long
  - optimzations not yet in place
- unlike BigInteger, BigInt has consistent hashcodes with Long, through range of long
all long-or-smaller integers are boxed as Long
- as with num, you can’t use primitive coercions to force specific box types
hash maps and sets use = for keys
- this will make maps and sets unify 42 and 42N, since =
- will use stricter .equals when calling through java.util interfaces
  - not there yet
  - this will require renaming Associative.containsKey, since semantics will now differ
+’ etc remain available when auto-promotion is required, but they are not needed for polymorphic arithmetic

Re-Update, alternate universe

In an attempt at fairness in evaluation, this version reverses the defaults. If you want arbitrary precision you must use the ‘prime’ versions of the ops.

The current plan is implemented in the equal branch. It includes changes from what is below, which should be looked at for facts other than in the areas stated here. I’ll reorganize soon.

BigIntegers will fully reduce in all cases.

The plan is to offer 2 sets of ops for the few ops that might overflow: +, -, *, inc, dec.

+, -, *, inc, dec have been enhanced. They will never auto-promote on integer overflow, and will instead throw an exception. Thus, the semantics of these operators are now uniform when used with boxed or primitive arguments. They can return integer primitives.

’ is now a constituent character. That means it may appear as a character in symbols in other than the first position, as does #.

+', -', *', inc', dec' For all arguments other than long-or-smaller integers, they do exactly what their non-prime counterparts do. For long-or-smaller integers, they will auto-promote in all cases, even when given integer primitives. As such, they will never return integer primitives. They can and do return double primitives when given doubles, as the semantics match. Unless you need to work with arbitrary-precision integers, there is no reason to use them.

type-specific equality semantics remain in place

literal numbers are always implicitly primitives, and never need (long 42) style coercion except for host interop overloading disambiguation.
- Note: this means that locals initialized with literals will have primitive type, e.g. (let [x 42] …), and especially: (loop [x 42] …). If you intend to recur with a non-primitive, init like this, (loop [x (num 42)] …)


;;;;;;;;;;;;;;;;;;;;;;;;;
;;equal branch, as of:
;;http://github.com/richhickey/clojure/commit/310534b8e7e7f28c75bb122b4bf1bee320cdae67

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

(time (fib 38))
"Elapsed time: 3565.579 msecs"

;; hint arg and return
(defn ^:static fib ^long [^long n]
  (if (<= n 1)
    1
    (+ (fib (dec n)) (fib (- n 2)))))

(time (fib 38))
"Elapsed time: 395.365 msecs"

;Use promoting op' ops for arbitrary precision
(defn fib [n]
  (if (<= n 1)
    1
    (+' (fib (dec' n)) (fib (-' n 2)))))

(time (fib 38))
"Elapsed time: 3705.123 msecs"

;; double arg/return
(defn ^:static fib ^double [^double n]
  (if (<= n 1)
    1
    (+ (fib (dec n)) (fib (- n 2)))))

(time (fib 38))
"Elapsed time: 860.326 msecs"

;; double arg/return, double operands
(defn ^:static fib ^double [^double n]
  (if (<= n 1.0)
    1.0
    (+ (fib (dec n)) (fib (- n 2.0)))))

(time (fib 38))
"Elapsed time: 428.116 msecs"

Update

The current plan is implemented in the equal branch. It includes changes from what is below, which should be looked at for facts other than in the areas stated here. I’ll reorganize soon.

BigIntegers will fully reduce in all cases.

The plan is to offer 2 sets of ops for the few ops that might overflow: +, -, *, inc, dec.

+, -, *, inc, dec will auto-promote in all cases, even when given integer primitives. As such, they will never return integer primitives. They can and do return double primitives when given doubles, as the semantics match. Thus, the semantics of these operators are now uniform when used with boxed or primitive arguments.

’ is now a constituent character. That means it may appear as a character in symbols in other than the first position, as does #.

+’, -‘, *’, inc’, dec’ have been added. For all arguments other than long-or-smaller integers, they do exactly what their non-prime counterparts do. They differ in that they will not auto-promote on integer overflow, and will instead throw an exception. They can return integer primitives. Unless you need the aforementioned performance benefit, there is no reason to use them. In particular, it is not necessary to use them for doubles at all.

type-specific equality semantics remain in place

literal numbers are always implicitly primitives, and never need (long 42) style coercion except for host interop overloading disambiguation.
- Note: this means that locals initialized with literals will have primitive type, e.g. (let [x 42] …), and especially: (loop [x 42] …). If you intend to recur with a non-primitive, init like this, (loop [x (num 42)] …)


;;; equal branch, as of
;;http://github.com/richhickey/clojure/commit/7652f7e935684d3c7851fbcad8ddce97e510a5a6

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

(time (fib 38))
"Elapsed time: 3530.085 msecs"

;; hint arg and return
(defn ^:static fib ^long [^long n]
  (if (<= n 1)
    1
    (+ (fib (dec n)) (fib (- n 2)))))

(time (fib 38))
"Elapsed time: 1238.83 msecs"

;hint arg and return, non-promoting op' ops
(defn ^:static fib ^long [^long n]
  (if (<= n 1)
    1
    (+' (fib (dec' n)) (fib (-' n 2)))))

(time (fib 38))
"Elapsed time: 407.476 msecs"

;; double arg/return
(defn ^:static fib ^double [^double n]
  (if (<= n 1)
    1
    (+ (fib (dec n)) (fib (- n 2)))))

(time (fib 38))
"Elapsed time: 804.862 msecs"

;; double arg/return, double operands, note does not use op'
(defn ^:static fib ^double [^double n]
  (if (<= n 1.0)
    1.0
    (+ (fib (dec n)) (fib (- n 2.0)))))

(time (fib 38))
"Elapsed time: 480.442 msecs"

Objective – Support primitives as fn arguments and return values

Clojure supports primitive arithmetic locally, and primitives in deftype/defrecord
- But not in fn arguments or returns
Means you can’t break up your logic, or write helper functions, without boxing

Issues

fn is specified by an interface (IFn), taking/returning objects
- fns must still satisfy that interface
How will callers know about primitive params/return, and how to invoke?
- New :static support

:static

defn supports {:static true} metadata
:static fns can take/return longs and doubles in addition to Objects
compiler will compile static methods in addition to IFn virtual methods
When compiling direct invocation of :static fn, compiler will look at var metadata and make call to static method
- Note that because it is not going through the var at runtime, will not see any dynamic modifications to the var
  - thus ‘static’
  - Caller won’t see redefs, bindings etc
  - Like macros, recompile client code to see changes
The var still contains IFn object for HOFs etc
- and you can get dynamic call by using (#’foo …)

Features to support :static and primitive args/returns are introduced in the prim branch

New ^:keyword metadata
- turns into ^{:keyword true}
Metadata stacks – ^:static ^:private foo == ^{:static true :private true} foo
^long and ^double hints allowed on args
- other reference type hints allowed as well
  - unlike for non-statics, these will be enforced
hint for return goes on arg vector
- e.g. (defn ^:static foo ^long [x] …)
- this so it supports multi-arity with varied returns
Static linking – replaces direct binding

Static linking

Eliminates the overhead of keeping fns in vars
Normally not an issue, but for small functions vars have 2 overheads:
- volatile can cause cache miss
- volatile inhibits inlining
Useful even when not using primitive args/returns
Known limitations
- static fns can’t be closures
- temporary limitation
  - static fns can’t be protocol call sites


;;;;;;;;;;;;;;;;;pre-prim master
(defn fib [n]
  (if (<= n 1)
    1
    (+ (fib (dec n)) (fib (- n 2)))))

(time (fib 38))
"Elapsed time: 3798.641 msecs"

;with type hints
(defn fib [n]
  (let [n (long n)]
    (if (<= n (long 1))
      (long 1)
      (+ (fib (dec n)) (fib (- n (long 2)))))))

(time (fib 38))
"Elapsed time: 2548.311 msecs"

;;;;;;;;;;;;;;;;; prim branch
(defn fib [n]
  (if (<= n 1)
    1
    (+ (fib (dec n)) (fib (- n 2)))))

(time (fib 38))
"Elapsed time: 3423.861 msecs"

; add primitive arg/return type
(defn ^:static fib ^long [^long n]
  (if (<= n 1)
    1
    (+ (fib (dec n)) (fib (- n 2)))))

(time (fib 38))
"Elapsed time: 3701.73 msecs" ;no benefit, still boxed math

; primitive arg/return type plus hints for primitive math
(defn ^:static fib ^long [^long n]
  (if (<= n (long 1))
    (long 1)
    (+ (fib (dec n)) (fib (- n (long 2))))))

(time (fib 38))
"Elapsed time: 437.96 msecs"

Objective – Unify primitive and boxed integer semantics

Currently, boxed integer arithmetic promotes to bigint as needed
- but primitive arithmetic throws on overflow
Means that you always have to be explicit about primitives
- difficulty with representation choices
- difficulty when optimizing due to change in semantics
- prohibits the compiler from presuming, e.g. that literals can be used as primitives
Would like to have literal numbers be used as primitives automatically, when possible

Features to support unified integer semantics are introduced in the num branch

Includes all of the features of the prim branch
Unifies on the semantics of primitive longs, throw on overflow
For bigints, specify bigints
- new literal bigint format 42N
Polymorphic boxed numeric tower still in place
bigints contagious, no more auto-reductions
- (\+ 0N 21 21) => 42N
Literal non-big numbers are now treated implicitly as primitives (long or double)
Locals known to be non-big numbers (i.e. inits are either literals or typed returns) are automatically coerced to long or double
More automatic conversions in argument matching
- int matches long, float matches double
longs also match ints, and doubles match floats
- long→int is checked for fit
Consistent canonic Integer/Long boxing
- If it fits in int, is Integer, else Long
- Can’t force boxed representation from primitive coercion:
  - (class (long 42)) => Integer
    - it was always wrong to presume otherwise
  - ditto boxed values coming from arrays of primitives
  - and primitive returns from interop


;;;;;;;;;;;;;;;;; num branch
(defn fib [n]
  (if (<= n 1)
    1
    (+ (fib (dec n)) (fib (- n 2)))))

(time (fib 38))
"Elapsed time: 3592.971 msecs"

; add primitive arg/return type
(defn ^:static fib ^long [^long n]
  (if (<= n 1)
    1
    (+ (fib (dec n)) (fib (- n 2)))))

(time (fib 38))
"Elapsed time: 392.605 msecs"

Objective – Get rid of equivalence semantics for numeric =

Current equivalence semantics for numbers introduced early on when Clojure didn’t do consistent boxing
So people had (Integer 42) and (Long 42) etc due to the results of computation
- Not .equals
Solution at the time was to make = more lenient
- this is not a good solution
- leaks into = for collections that might contains numbers
  - already a semantic mismatch with key comparisons, which Java dictates must be based on .equals
- complicates the logic in =, a heavily used function
Consistent boxing in num branch opens the door to fixing this

Features to support type-sensitive numeric equality are introduced in the equal branch

Includes all the features of the num branch
= on numbers now includes the type
- matches .equals
- so no more special handling on collections either
Use == for numeric equivalence
- or better yet, be consistent about types
- uniform boxing should take care of most of that


(doc =)
-------------------------
clojure.core/=
([x] [x y] [x y & more])
  Equality. Returns true if x equals y, false if not. Same as Java
  x.equals(y) except it also works for nil. Boxed numbers must have
  same type. Clojure's immutable data structures define equals() (and
  thus =) as a value, not an identity, comparison.

Summary

New features enable much faster code
Unified semantics reduce complexity
All features other than auto-promotion still available
Optimization more automatic, less work, less subtle

Clojure