Opened 11 years ago

Closed 11 years ago

Last modified 11 years ago

#365 closed defect (duplicate)

Worse than exponential algorithms in type derivation

Reported by: emarsden Owned by: gb
Priority: normal Milestone:
Component: Compiler Version: trunk
Keywords: Cc:

Description

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

Change History (2)

comment:1 Changed 11 years ago by gb

  • Resolution set to duplicate
  • Status changed from new to closed

This is the same issue as ticket:186

comment:2 Changed 11 years ago by rme

  • Milestone 1.2 deleted

Milestone 1.2 deleted

Note: See TracTickets for help on using tickets.