forever compiling

[Tomas Hlavaty]

Hi,

we hit an issue when compiling certain function in a big codebase.
The function is conceptually pretty "simple".
The most notable thing is
that it uses (E)TYPECASEs with lots of CLOS types
and often in (or ...) form.
(I am not sure that the problem is with typecase, just guessing.)

I have bisected the breakage to this commit:

commit 75f026302c8f7ca7b04e21218c94ac2bd61c9c1e
Author: Charles Zhang <email address hidden>
Date: Wed Mar 30 13:13:49 2022 -0700

    join-type-constraints: Handle more constraint kinds and NOT-P.

    * Handle <, >, and = constraints.
    * Handle complemented type constraints. The FIXME about infinite
    regress was wrong; that was from before I figured out the infinite
    regress came from the nasty interaction of optimistic EQL propagation
    yielding partial (incorrect) types and type joining, which needs
    correct types always, not just at the fixpoint.

    Most of this patch was written by Jan Moringen. I just debugged some
    cross-float stuff and added a slew of tests showing off the tighter
    type propagation.

    Also I fixed a weird test where the additional type smarts causes the
    compiler to complain in compiler-2.impure-cload.lisp. Fix the values
    to no longer cause a type error. Does the interaction between the
    function type inference and the change in the FDEFINITION make sense
    in that situation?

The problematic 117 lines long function compiled in about 10s on sbcl-2.2.3
without errors or warnings.

Would somebody recommend a strategy how to investigate
and pinpoint the issue further?

Thanks in advance

Cheers

Tomas

[Tomas Hlavaty (q-tom-o)]

So it seems to be a severe performance regression.
Our function which took about 10s to compile
now takes several hours to compile.
(Much longer than our CI timeout.)

Here is an example, which takes about
3sec to compile on sbcl-2.2.3 and now takes about
7min to compile the function FOO:

(progn
  (defclass c0 () ())
  (defclass c1 () ())
  (defclass c2 () ())
  (defclass c3 () ())
  (defclass c4 () ())
  (defclass c5 () ())
  (defclass c6 () ())
  (defclass c7 () ())
  (defclass c8 () ())
  (defclass c9 () ())
  (defclass c10 () ())
  (defclass c11 () ())
  (defclass c12 () ())
  (defclass c13 () ())
  (defclass c14 () ())
  (defclass c15 () ())
  (defclass c16 () ())
  (defclass c17 () ())
  (defclass c18 () ())
  (defclass c19 () ())
  (defclass c20 () ())
  (defclass c21 () ())
  (defclass c22 () ())
  (defclass c23 () ())
  (defclass c24 () ())
  (defclass c25 () ())
  (defclass c26 () ())
  (defclass c27 () ())
  (defclass c28 () ())
  (defclass c29 () ())
  (defclass c30 () ())
  (defclass c31 () ())
  (defclass c32 () ())
  (defclass d0 () ())
  (defclass d1 (d0) ())
  (defclass d2 (d0) ())
  (defclass d3 (d0) ())
  (defclass d4 (d0) ()))
(defun foo (x)
  (etypecase x
    (c1 1)
    ((or c2 c3) 2)
    ((or c4 c5 c6) 3)
    ((or c7 c8 c9 c10) 4)
    ((or c11 c12 c13 c14 c15) 5)
    ((or c16 c17 c18 c19 c20 c21 d0)
     (etypecase x
       (d1 61)
       ((or d2 d3) 62)
       ((or c16 c17 c18 c19 c20 c21) 63)))
    ((or c22 c23 c24 c25 c26 c27 c28) 7)
    ((or c29 c30 c31 c32) 8)))

It seems that maybe somehow union-types explode.

In the following example:

(defclass d0 () ())
(defclass d1 (d0) ())
(defclass d2 (d0) ())
(defclass d3 (d0) ())
(defun foo (x)
  (etypecase x
    (c1 1)
    (c2 2)
    (c3 3)
    ((or d1 d2) 12))))

tracing sb-c::type-from-constraints reveals this type:
(OR
  (AND (NOT C1) (NOT C2) (NOT C3) (NOT D1))
  (AND D1 (NOT C1) (NOT C2) (NOT C3)))

Is it the same type as
(AND (NOT C1) (NOT C2) (NOT C3)) ?
Or it is not possible to simplify the type?