Exponential compile time

[Syll]

The attached file is very long to compile :
    sbcl --dynamic-space-size 2048
    (time (load "test-perf"))

This is a long function, but I wonder why the compile time seems
exponential with function length. For example cutting the function
in half makes the compiling much faster (the two parts are
independant, even placed in the same function).

A few elements seem very expensive :
    - Removing unwind-protect in the first macro, used only 30 times :
      -20% to compile time.
    - Removing handler-case from test-error, used 16 times : -40%
      (I'm pretty sure that compiling 16 times handler-case does not
      cost several seconds in another context).
    - Cutting the function in half without removing anything : -55%.

Maybe there is something with combining these elements ? Or they add
much work to the compilation, the compiling being executed in exponential
time ?

----

SBCL 2.0.5
Linux yggdrasil 5.7.7-arch1-1 #1 SMP PREEMPT Wed, 01 Jul 2020 14:53:16 +0000 x86_64 GNU/Linux

[Charles (karlosz)]

This doesn't seem to be exponential time, since cutting it in half reduces the time by 50%. I looked at the test case and didn't see anything out of the ordinary - it's compiling 2,847 lambdas according to TIME which does take some time to do. I'll mark this as invalid. However, some latest changes to HANDLER-BIND have actually cut the amount of consing and time spent in compilation by a bit, if that helps.

[Syll (syll)]

I meant splitting the function in two functions, without removing lines of code. Please check the test case that is attached to this report : if you uncomment lines 150-152 to split the function in two, the compile time of the file is significantly lower (I just made the test, it is not by half anymore but maybe -30%).

The file with the splitting is attached to this comment.

Context (discussion on sbcl-bugs) :
    https://sourceforge.net/p/sbcl/mailman/sbcl-bugs/thread/af42ca2b552a67b5ca6d48a3f50d5ad2765c5f0b.camel%40laposte.net/
    https://sourceforge.net/p/sbcl/mailman/sbcl-bugs/thread/f6a4bd47d23227c528efe47201501795d0a6f5f9.camel%40laposte.net/

Please reopen the bug.

[Syll (syll)]

One function :

* (time (load "test-perf"))
  2.016 seconds of real time
  2,904 lambdas converted

Two functions, same number of lines of code, same number of lambdas :

* (time (load "test-perf-short"))
  1.290 seconds of real time
  2,905 lambdas converted

[Christophe Rhodes (csr21-cantab)]

We would need more evidence that this that compilation times are exponential.

I ran

(defun test-size (n)
  (let ((form
          `(defun test ()
             ,@(loop for i from 1 to n
                    collect
                    `(tests-group
                      (test-eq)
                      (test-error error))))))
    (compile nil `(lambda () ,form))))

for various values of N, timing the compilation in internal time units, and got

10,36596
20,111849
30,216176
40,445397
50,750278
60,950198
70,1445848
80,2355965
90,2706998

Plotting time vs n, log(time) vs n, and log(time) vs log(n), to my eye the data are best explained by time \propto n^2 -- approximately a straight line with gradient 2 on the log(time) vs log(n) plot. Quadratic scaling isn't great, but also it's not too surprising to find that there might be some things that scale quadratically in a compiler. It would be nice if users could request turning those quadratic (or worse) things off with compilation-speed optimize directives, but we are not there; I'm not sure we even know which bits scale worse than linearly in practice (plenty of places do in theory but the bad range might not be reached in this size of code).

In any case I don't think this bug is actionable. By all means continue investigating the performance of the compiler, and if you find out which area of the compiler is scaling badly for your actual code, please report that.

[Syll (syll)]

Ok, thank you for your analysis and your explanations.