Opened 12 years ago

Closed 10 years ago

#186 closed defect (fixed)

Compilation time grows exponentially

Reported by: alms Owned by: gb
Priority: major Milestone:
Component: Compiler Version:
Keywords: Cc: 00003b@…

Description

Time to compile a function containing an n-ary call to + grows exponentially with the number of arguments to +.

(EVAL '#'(LAMBDA NIL (LET ((A 1) (B 2) (C 3) (D 4) (E 5) (F 6) (G 7) (H 8)) (+ A B C D E F G H)))) took 27 milliseconds (0.027 seconds) to run

with 2 available CPU cores.

During that period, 29 milliseconds (0.029 seconds) were spent in user mode

0 milliseconds (0.000 seconds) were spent in system mode

33,968 bytes of memory allocated.

#<Anonymous Function #x300041AF5DEF> ? (EVAL '#'(LAMBDA NIL (LET ((A 1) (B 2) (C 3) (D 4) (E 5) (F 6) (G 7) (H 8) (I 9)) (+ A B C D E F G H I)))) took 70 milliseconds (0.070 seconds) to run

with 2 available CPU cores.

During that period, 71 milliseconds (0.071 seconds) were spent in user mode

0 milliseconds (0.000 seconds) were spent in system mode

39,440 bytes of memory allocated.

#<Anonymous Function #x300041AE9BEF> ? (EVAL '#'(LAMBDA NIL (LET ((A 1) (B 2) (C 3) (D 4) (E 5) (F 6) (G 7) (H 8) (I 9) (J 10)) (+ A B C D E F G H I J)))) took 195 milliseconds (0.195 seconds) to run

with 2 available CPU cores.

During that period, 198 milliseconds (0.198 seconds) were spent in user mode

1 milliseconds (0.001 seconds) were spent in system mode

1 milliseconds (0.001 seconds) was spent in GC.

45,440 bytes of memory allocated.

#<Anonymous Function #x3000419BC23F> ? (EVAL '#'(LAMBDA NIL (LET ((A 1) (B 2) (C 3) (D 4) (E 5) (F 6) (G 7) (H 8) (I 9) (J 10) (K 11)) (+ A B C D E F G H I J K)))) took 560 milliseconds (0.560 seconds) to run

with 2 available CPU cores.

During that period, 561 milliseconds (0.561 seconds) were spent in user mode

1 milliseconds (0.001 seconds) were spent in system mode

53,424 bytes of memory allocated.

#<Anonymous Function #x3000419AC6BF> ? (EVAL '#'(LAMBDA NIL (LET ((A 1) (B 2) (C 3) (D 4) (E 5) (F 6) (G 7) (H 8) (I 9) (J 10) (K 11) (L 12)) (+ A B C D E F G H I J K L)))) took 1,653 milliseconds (1.653 seconds) to run

with 2 available CPU cores.

During that period, 1,651 milliseconds (1.651 seconds) were spent in user mode

5 milliseconds (0.005 seconds) were spent in system mode

59,728 bytes of memory allocated.

#<Anonymous Function #x300041B3B8CF> ? (EVAL '#'(LAMBDA NIL (LET ((A 1) (B 2) (C 3) (D 4) (E 5) (F 6) (G 7) (H 8) (I 9) (J 10) (K 11) (L 12) (M 13)) (+ A B C D E F G H I J K L M)))) took 4,903 milliseconds (4.903 seconds) to run

with 2 available CPU cores.

During that period, 4,906 milliseconds (4.906 seconds) were spent in user mode

9 milliseconds (0.009 seconds) were spent in system mode

66,240 bytes of memory allocated.

#<Anonymous Function #x300041B2827F>

Change History (4)

comment:1 Changed 12 years ago by gb

  • Owner changed from GB to gb
  • Status changed from new to assigned

It's actually moderately hard to fix this without getting dumber in some cases (though of course it's hard to claim that this behavior is anything but dumb.)

N-ary + gets reduced to a tree of nested binary-+ calls:

? (compiler-macroexpand '(+ a b c d e f g h i j k l m n o p))
(+-2 (+-2 (+-2 (+-2 (+-2 (+-2 (+-2 (+-2 (+-2 (+-2 (+-2 (+-2 (+-2 (+-2 (+-2 A B) C) D) E) F) G) H) I) J) K) L) M) N) O) P)
T

and lots and lots of things walk the resulting tree (in source or tokenized form) looking for opportunities to do strength-reduction (maybe +-2 can become %I+, etc) and type inference and other arbitrary things. The trees are never re-written or destructively modified, so if we discover that the innermost (+-2 A B) involves fixnum addition when walking the entire tree we discover it again when walking each subtree. (In particular, if we've already walked the tree and decided that there's nothing interesting there, nothing keeps us from walking it again looking for something interesting again ...)

The innermost (+-2 A B) in your example should have been rewritten as 3 pretty early in the process (and the whole call to + is constant-valued), so all of this huffing and puffing doesn't get us anywhere. A lot of that hysteria happens in things that walk the source, and those things are generally pretty limited in what they can do (e.g., we can't tell that this is constant-valued when looking at the call to +, since we don't know in general whether control could have reached that point after assigning a non-constant value to one of the arguments.)

The right fix for all of this is to replace the compiler frontend with something that does tree-rewriting a little more sanely. I think that there are probably some things that can be done with the current frontend that'd avoid hysteria, and that it's worth spending at least a few days on this.

comment:2 Changed 10 years ago by 3b

  • Cc 00003b@… added

Ran into this on "Version 1.3-r11936 (LinuxX8664)" while trying to compile

(defun matrix-determinant (matrix)
  (macrolet ((a (i j)
               `(aref matrix (+ (- ,i 1) (* 4 (- ,j 1))))))
    ;(declare (notinline +))
    (- (+ (* (a 1 1) (a 2 2) (a 3 3) (a 4 4))
          (* (a 1 1) (a 2 3) (a 3 4) (a 4 2))
          (* (a 1 1) (a 2 4) (a 3 2) (a 4 3))

          (* (a 1 2) (a 2 1) (a 3 4) (a 4 3))
          (* (a 1 2) (a 2 3) (a 3 1) (a 4 4))
          (* (a 1 2) (a 2 4) (a 3 3) (a 4 1))

          (* (a 1 3) (a 2 1) (a 3 2) (a 4 4))
          (* (a 1 3) (a 2 2) (a 3 4) (a 4 1))
          (* (a 1 3) (a 2 4) (a 3 1) (a 4 2))

          (* (a 1 4) (a 2 1) (a 3 3) (a 4 2))
          (* (a 1 4) (a 2 2) (a 3 1) (a 4 3))
          (* (a 1 4) (a 2 3) (a 3 2) (a 4 1)))

       (* (a 1 1) (a 2 2) (a 3 4) (a 4 3))
       (* (a 1 1) (a 2 3) (a 3 2) (a 4 4))
       (* (a 1 1) (a 2 4) (a 3 3) (a 4 2))

       (* (a 1 2) (a 2 1) (a 3 3) (a 4 4))
       (* (a 1 2) (a 2 3) (a 3 4) (a 4 1))
       (* (a 1 2) (a 2 4) (a 3 1) (a 4 3))

       (* (a 1 3) (a 2 1) (a 3 4) (a 4 2))
       (* (a 1 3) (a 2 2) (a 3 1) (a 4 4))
       (* (a 1 3) (a 2 4) (a 3 2) (a 4 1))

       (* (a 1 4) (a 2 1) (a 3 2) (a 4 3))
       (* (a 1 4) (a 2 2) (a 3 3) (a 4 1))
       (* (a 1 4) (a 2 3) (a 3 1) (a 4 2)))))

let it compile for an hour or so before giving up, currently using the (notinline +) declaration as a workaround.

comment:3 Changed 10 years ago by rme

r12861 (which change is in the trunk) tries to address this. Note that the change requires new binaries, so if you've build local binaries, be sure to svn revert them after updating so that you'll be using the new ones (see UpdatingFromSource).

comment:4 Changed 10 years ago by rme

  • Resolution set to fixed
  • Status changed from assigned to closed
Note: See TracTickets for help on using tickets.