Optimizing And Compiling Expressions

---

This section of this tutorial showcases expresso’s facilities to optimize expressions. Expresso’s optimizer, coupled with it’s expression compiler provides a seemingless to use interface and enables considerable performance improvements in some cases.

(ns expresso-tutorial.optimize-compile
  (:use [numeric.expresso.core]))

Optimizing Expressions

The interface to optimize expressions is very simple: The function optimize takes an expression and emits an optimized expression which can then be compiled to an efficient clojure function. The following code snippets highlights some of the optimizations, which are performed by the optimizer on small expression inputs.

(in-ns 'expresso-tutorial.optimize-compile)

;;the optimizer provides constant folding
(optimize (ex (* (+ x 3 4) 5 2))) ;=> (* 10 (+ 7 x))

(optimize (ex (* (+ [1 2] x [3 4]) [[1 2][3 4]])))
;;=> (* (+ [4 6] x) [[1 2] [3 4]])

;;A very important feature is common-subexpression removal which recognizes
;;the subexpressions in the expression which are equal to each other and
;;replaces each set of equivalent equations with a binding in a let expression
(optimize (ex (+ (expensive-operation) (expensive-operation))))
;;=> (let [local658470 (expensive-operation)] (* 2 local658470))

(optimize (ex (+ (* a b c) (** (* c b a) 2))))
;;=> (let [local660809 (* a b c)] (+ local660809 (** local660809 2)))

;;expresso also does some transformation with applies some simplifications which
;;reduce the excecution time. These include canceling out inverses, some
;;factorization of the input, special constant removal ...
(optimize (ex (* b 0))) ;=> 0.0

(optimize (ex (+ (* 1000 x) (* 100 x) (** x 2)))) ;=> (+ (* 1100 x) (** x 2))

;;there is also experimental support for optimizations of summation.
;;the expression (sum k 0 5 (** k 2)) means sum with k over the range from 0
;;to 5 with the formula (** k 2). The optimizations includes the rule to
;;move a factor out of the sum.
(optimize (ex (sum k 0 10 (* a (** k 2)))))

;;=> (* a (sum k (<= 0 k 10) (** k 2)))
;;Sum expressions compile to an optimized clojure loop expression.
;;See the section about expresso's internals about how this is accomplished

;;the optimizer also has the ability to swap general functions for specialized
;;ones which run faster. The simplest example of this is the following
(optimize (ex (** a 0.5))) ;=> (sqrt a)

;;Expresso can even optimize the order of multiplication in a matrix chain.
;;This can result in very high speedups. While matrix multiplication is
;;associative, the actual number of multiplications which are performed is
;;dependent on the actual order in which the matrix multiplications are
;;performed.

;;expresso can't optimize the call here because the shapes of a b c and d are
;;undetermined.
(optimize (ex (inner-product a b c d))) ;=> (inner-product a b c d)
;;If they are specified with the shape metadata, the optimization is applied.

(optimize (ex (inner-product
               ^{:shape [40 20]} a
               ^{:shape [20 30]} b
               ^{:shape [30 10]} c
               ^{:shape [10 30]} d)))
 ;=> (inner-product (inner-product a (inner-product b c)) d)

The single optimizations are also available in the numeric.expresso.optimize namespace. You can specify there an optional second argument to the optimize function which lets you specify the optimizations and the order in which they are applied. More about this can be found in the section about Extending expresso.

Compiling

After you have the optimized version of your expressions, you can compile them to an efficient clojure function.

(in-ns 'expresso-tutorial.optimize-compile)

(def func (compile-expr [a b] (ex (+ (* a b) (* b a)))))

(func 2 3) ;=> 12

;;the copmile-expr* is the function version of compile-expr. You have to quote
;;the binding vector to use it but therefore it is just a normal clojure function

(def funcs (map #(compile-expr* '[a b] %)
                [(ex (+ (* a b) (* b a))) (ex (** a b)) (ex (+ a b))]))

((first funcs) 2 3) ;=> 12

The compilation works by emitting clojure code for the expressions. In the normal case the emitted code will be (execution-function args*), but it can be more complicated code for something like a sum expression. The emitted code together with the binding vector is then eval’ed to a clojure function. The code that expresso emits for the compiled function is an implementation details, but if you are interested to find out what it does under the hood, you can do it like the following snippet shows:

(in-ns 'expresso-tutorial.optimize-compile)

(require '[numeric.expresso.protocols :as p])

(p/emit-code (ex (+ a b))) ;=> (+ a b)

(p/emit-code (ex (+ ^:matrix a b)))
;;=> (#<matrix$add clojure.core.matrix$add@3e322a4c> a b)

(p/emit-code (ex (exp x))) ;=> (#<matrix$exp clojure.core.matrix$exp@60e04338> x)

;;let-expressions compile to let expressions
(p/emit-code (optimize (ex (+ (* a b) (* b a)))))
;;=> (clojure.core/let [local686013 (* b a)] (* 2 local686013))

;;sum expressions compile to a fast clojure loop-recur block of code
(p/emit-code (ex (sum k 0 a (ex (+ k 3)))))
;;=> (clojure.core/loop [n__2521__auto__ (clojure.core/long 0)
;;                       res__2522__auto__ 0]
;;     (if (clojure.core/<= n__2521__auto__ a)
;;           (clojure.core/let [k n__2521__auto__]
;;             (recur (clojure.core/inc n__2521__auto__)
;;                    (clojure.core.matrix/add res__2522__auto__ (+ k 3))))
;;            res__2522__auto__))