On Wed, May 26, 2010 at 11:09 PM, Juan Jose Garcia-Ripoll <juanjose.garciaripoll@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