compiler performance regressions from 1.0.10 -> 1.0.23 -> 1.0.29.54.rc1

[Nikodemus Siivola]

As reported on sbcl-bugs:

--snip--
I tried building 1.0.29.54.rc1 from the tar file Nikodemus Siivola
linked to this morning, and tried compiling and running our Specware
system. The good news is that everything worked. The bad news is that
the time and space to compile Specware is so large as to make it
effectively unusable. In fact I couldn't make --dynamic-space-size
large enough on Windows XP to get the compilation to go through.
Actually, this was also true of 1.0.29 as well, but I only now got
round to documenting it.

The slow-down has gotten worse from 1.0.10 where compilation takes a
minute to 1.0.23 where it takes 3 minutes to 1.0.29 where it takes 10
minutes. The results of calls to time are below. Specware is a fairly
large system for specification and refinement. It includes an
executable sub-language like ML in which most of the system is
written, from which the lisp code is automatically generated. Most of
the code produced is very vanilla lisp, but some functions can be
larger than you might find in hand-written code (like 600 lines,
although prettyprinted and highly nested so not much per line), and
there is more use of local functions (labels). The compiler settings
used were Speed 3 Safety 1 Debug 3, but using Speed 1 made no
difference. The compiled code from 1.0.29.54.rc1 runs about 4% faster
than that of 1.0.10, although we do have applications where the speed-
up is more substantial.

I would very much appreciate it if new versions of SBCL could be
usable for us, as otherwise our experience with SBCL has been very good.

Thanks,
Stephen Westfold
Kestrel Institute
--snap--

Stephen kindly sent me SB-SPROF output from the build, where constraint propagation featured even more prominently than usually. I then tracked this down to the new constraint set implementation, and it was confirmed that reverting to the old SSET based one takes the performance back to 1.0.23 levels.

No idea as of yet for the 1.0.10 -> 1.0.23 slowdown.

[petdog (petdog)]

Using a better hash function along with linear probing instead of double hashing makes ssets as fast as bitvectors on anything I could measure, and should be faster on pathological cases; for example with this test by David Lichteblau on sbcl-devel

(defun make-test (n)
  (flet ((local (i)
    (intern (write-to-string i) :cl-user)))
    `(lambda (,(local 0))
       (let (,@(loop
     for i from 1 below n
     collect (local i)))
  ,@(loop
        for i from 0 below (1- n)
        collect `(setf ,(local (1+ i)) ,(local i)))
  ,(local (1- n))))))

(defun test (n)
  (time (compile nil (make-test n))))

I get (with bitvectors)

* (test 200)
Evaluation took:
  47.830 seconds of real time

(with ssets)

* (test 200)
Evaluation took:
  4.096 seconds of real time

Here's a patch, if anybody is interested. (I also removed double-hashing from globaldb.lisp, hopefully in a correct way)

[Paul Khuong (pvk)]

This actually seems to be a test of FIND-CONSTRAINT more than CONSETs per se (bitvectors do suck DO-CONSET, but the fact that we even use DO-CONSET for FIND-CONSTRAINT is lossy).

[Paul Khuong (pvk)]

Fixed in 1.0.49.55-e7100f1

The bitvector-based consets are better for bulk operations (union, intersection, equality, copy), and using a couple indices smartly avoid their weakness (iteration). I tried the same rewrite on top of hash-based consets, but it worked slightly worse.

Compile time for the example above down to < .5 second.