Hi,
The compiler seems to use algorithms for type derivation that are worse than
exponential with the size of forms compiled. I see this on both IA32 and X86-64
ports, running Linux.
#|
? (tabulate-compilation-time 17)
1, 0, 0.0
2, 0, 0.0
3, 0, 0.0
4, 0, 0.0
5, 8000, 8.987322
6, 8001, 8.987447
7, 16001, 9.680469
8, 52003, 10.859076
9, 128008, 11.759856
10, 388024, 12.868825
11, 556035, 13.228588
12, 1548097, 14.252538
13, 4724295, 15.368229
14, 14188887, 16.46797
15, 41430589, 17.53953
16, 124423776, 18.639204
|#
(defun time-compilation (form)
(let ((before (get-internal-run-time)))
(compile nil form)
(- (get-internal-run-time) before)))
(defun make-form (size)
`(lambda (a)
(declare (type (integer -55555555555555 -4444) a))
(+ 1 ,@(loop :for i :below size :collect 'a))))
(defun tabulate-compilation-time (&optional (max-form-size 15))
(dotimes (i max-form-size)
(let ((ct (time-compilation (make-form i))))
(format t "~d, ~d, ~f~%" i ct (log (1+ ct))))))
