compiler performance regressions from 1.0.10 -> 1.0.23 ->

Bug #394206 reported by Nikodemus Siivola
This bug affects 1 person
Affects Status Importance Assigned to Milestone
Fix Released

Bug Description

As reported on sbcl-bugs:

I tried building 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 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.

Stephen Westfold
Kestrel Institute

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.

Revision history for this message
Nikodemus Siivola (nikodemus) wrote :
Revision history for this message
petdog (petdog) wrote :

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)))
        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)

tags: added: optimization
removed: performance
Changed in sbcl:
assignee: Nikodemus Siivola (nikodemus) → Paul Khuong (pvk)
Revision history for this message
Paul Khuong (pvk) wrote :

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)
Changed in sbcl:
status: Confirmed → In Progress
Revision history for this message
Paul Khuong (pvk) wrote :

Fixed in

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.

Changed in sbcl:
status: In Progress → Fix Committed
Paul Khuong (pvk)
Changed in sbcl:
assignee: Paul Khuong (pvk) → nobody
Changed in sbcl:
status: Fix Committed → Fix Released
To post a comment you must log in.
This report contains Public information  
Everyone can see this information.

Other bug subscribers

Remote bug watches

Bug watches keep track of this bug in other bug trackers.