[Ecls-list] Type propagation
Juan Jose Garcia-Ripoll
juanjose.garciaripoll at googlemail.com
Fri May 28 20:14:46 UTC 2010
On Wed, May 26, 2010 at 11:09 PM, Juan Jose Garcia-Ripoll <
juanjose.garciaripoll at googlemail.com> wrote:
> I have stripped down and reimplemented the type propagator. Right now it is
> kind of stable and implements forward type propagation for most forms. You
> will see, however, some harmless notes such as the following one.
> ;;; Note:
> ;;; Refusing to propagate FUNCTION
>
> The result is that some benchmarks are now dominated by stupid statements
> in them (ASSERT) (SBCL first column, ECL tonight second, ECL 10.4.1 last)
>
> 1D-ARRAYS [ 0.03] 1.00 2.67
> 2D-ARRAYS [ 0.24] 3.04 7.17
> 3D-ARRAYS [ 0.68] 2.19 11.78
>
Ok, so this is how it looks now on a newer version that implements type
propagation, fixes type propagation for arrays and takes a different, more
efficient approach to the problem of unboxing temporaries.
1D-ARRAYS [ 0.03] 1.67 2.67
2D-ARRAYS [ 0.24] 0.75 7.17
3D-ARRAYS [ 0.68] 0.68 11.78
1D-ARRAYS is dominated by an assertion and in particular by the call to
SEARCH, a function which I have not optimized. If I change the test as shown
below, with more iterations, no call to SEARCH and yet fully executed (not
optimized away), then the comparison is more fair: ECL performs equally well
or better than SBCL (remember that numbers are relative to the reference)
1D-ARRAYS [ 0.10] 1.00
2D-ARRAYS [ 0.20] 0.85
3D-ARRAYS [ 0.67] 0.70
The full list of benchmarks is shown below. Not all changes are as dramatic
as these ones because type propagation has only been implemented for certain
functions --arithmetics, arrays, and functions with a single type
proclamation that does not depend on the arguments.
(defun bench-1d-arrays (&optional (size 100000) (runs 500))
(declare (fixnum size)
(fixnum runs))
(let ((ones (make-array size :element-type '(integer 0 1000)
:initial-element 1))
(twos (make-array size :element-type '(integer 0 1000)
:initial-element 2))
(threes (make-array size :element-type '(integer 0 2000))))
(dotimes (runs runs)
(dotimes (pos size)
(setf (aref threes pos) (+ (aref ones pos) (aref twos pos))))
(assert (= 3 (aref threes runs))))
(values)))
Benchmark Reference ECLx ECLo
-------------------------------------------------------------------------------------
COMPILER [ 0.97] 0.85 0.80
LOAD-FASL [ 0.15] 0.60 0.53
SUM-PERMUTATIONS [ 0.95] -1.00 -1.00
WALK-LIST/SEQ [ 0.01] 6.00 6.00
WALK-LIST/MESS [ 0.02] 2.50 2.50
BOYER [ 2.03] 1.83 1.81
BROWSE [ 0.17] 1.59 1.76
DDERIV [ 0.11] 5.64 5.64
DERIV [ 0.13] 5.23 5.08
DESTRUCTIVE [ 0.13] 2.85 2.92
DIV2-TEST-1 [ 0.17] 5.53 6.18
DIV2-TEST-2 [ 0.25] 4.44 4.64
FFT [ 0.03] 1.67 18.00
FRPOLY/FIXNUM [ 0.15] 3.07 2.87
FRPOLY/BIGNUM [ 0.12] 1.92 1.92
FRPOLY/FLOAT [ 0.22] 2.27 2.45
PUZZLE [ 0.15] 7.80 11.00
TAK [ 0.12] 1.67 6.83
CTAK [ 0.24] 2.46 3.79
TRTAK [ 0.12] 1.67 6.83
TAKL [ 0.25] 1.36 0.84
STAK [ 0.28] 1.25 1.50
FPRINT/UGLY [ 0.54] 1.69 1.59
FPRINT/PRETTY [ 1.29] 18.62 25.75
TRAVERSE [ 0.74] 1.89 2.05
TRIANGLE [ 0.37] 3.11 5.41
RICHARDS [ 0.36] 5.86 6.00
FACTORIAL [ 0.08] 1.00 1.13
FIB [ 0.14] 2.43 2.43
FIB-RATIO [ 0.03] 1.67 1.67
ACKERMANN [ 0.46] 2.11 2.07
MANDELBROT/COMPLEX [ 0.18] 1.94 2.06
MANDELBROT/DFLOAT [ 0.01] 4.00 47.00
MRG32K3A [ 0.49] 2.45 2.41
CRC40 [ 0.28] 14.61 19.54
BIGNUM/ELEM-100-1000 [ 0.07] 0.43 0.29
BIGNUM/ELEM-1000-100 [ 0.08] 0.38 0.25
BIGNUM/ELEM-10000-1 [ 0.05] 0.60 0.60
BIGNUM/PARI-100-10 [ 0.00] -1.00 -1.00
BIGNUM/PARI-200-5 [ 0.03] 0.00 0.00
PI-DECIMAL/SMALL [ 0.35] 4.40 4.40
PI-DECIMAL/BIG [ 0.18] 6.06 6.06
PI-ATAN [ 0.40] 0.50 0.55
PI-RATIOS [ 0.75] 0.61 0.63
HASH-STRINGS [ 0.11] 2.45 3.09
HASH-INTEGERS [ 0.20] 2.25 2.35
SLURP-LINES [ 0.60] 2.85 2.80
BOEHM-GC [ 0.58] 4.97 5.07
DEFLATE-FILE [ 0.14] 2.71 3.71
1D-ARRAYS [ 0.10] 1.00 23.90
2D-ARRAYS [ 0.20] 0.85 8.65
3D-ARRAYS [ 0.67] 0.70 11.91
BITVECTORS [ 0.19] 10.53 10.47
BENCH-STRINGS [ 0.20] 17.60 12.85
fill-strings/adjustable [ 4.81] 0.07 1.05
STRING-CONCAT [ 1.57] 1.53 1.69
SEARCH-SEQUENCE [ 0.15] 5.07 8.53
CLOS/defclass [ 0.56] 0.30 0.48
CLOS/defmethod [ 2.65] 0.04 0.06
CLOS/instantiate [ 3.96] 4.37 4.52
CLOS/simple-instantiate [ 0.13] 153.77 158.54
CLOS/methodcalls [ 0.54] 3.87 3.15
CLOS/method+after [ 1.68] 1.13 1.02
CLOS/complex-methods [ 1.21] 1.21 0.97
EQL-SPECIALIZED-FIB [ 0.13] 8.85 8.92
Reference time in first column is in seconds; other columns are relative
Reference implementation: SBCL 1.0.29.11.debian
Impl ECLx : ECLx 10.4.2
Impl ECLo : ECLo 10.4.1
=== Test machine ===
Machine-type: X86-64
Machine-version: Intel(R) Core(TM) i7 CPU 920 @ 2.67GHz
--
Instituto de Física Fundamental, CSIC
c/ Serrano, 113b, Madrid 28006 (Spain)
http://tream.dreamhosters.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/ecl-devel/attachments/20100528/bd0e7f4d/attachment.html>
More information about the ecl-devel
mailing list