#21 COLLECT-FIRST optimization bug

open
nobody
None
5
2008-09-30
2008-09-30
Michael Weber
No

COLLECT-FIRST sometimes returns the last element:

(let ((nums (scan-range :below 4)))
(values (collect-first nums)
(collect (subseries nums 0))))
=> 3, (0 1 2 3)

Macroexpanding the form shows that there is a test missing:
#:LL-1945
(SETQ NUMS (+ NUMS (SERIES::COERCE-MAYBE-FOLD 1 'NUMBER)))
(IF (NOT (< NUMS 4)) (GO SERIES::END))
;; MISSING: (IF #:TERMINATED-1944 (GO #:CC-1943))
(SETQ #:ITEM-1929 NUMS)
#:BB-1942
(SETQ #:TERMINATED-1944 T)
#:CC-1943
(INCF #:INDEX-1938)

Note that the following versions work:
(let ((nums (scan-range :below 4)))
(values (collect-first nums)
(collect nums)))
=> 0, (0 1 2 3)

(let ((nums (scan-range :below 4)))
(values (collect-first nums)
(subseries nums 0))) ; return series, i.e., no optimization
=> 0, #Z(0 1 2 3)

Discussion

  • Raymond Toy
    Raymond Toy
    2008-10-27

    Sorry for the delay.

    Yes, I can reproduce this. Unfortunately, the bug appears to be rather deep and will take some time to fix. I'm not sure exactly what the cause of the bug is.

     
  • Raymond Toy
    Raymond Toy
    2010-05-20

    Not sure, but the bug appears to be in check-termination. The termination condition for collect-first is created, but for some reason, check-termination decides that the termination is not needed.

    Needless to say, I don't understand this code at all.

     
  • Raymond Toy
    Raymond Toy
    2010-05-21

    This bug is very old. It exists in rev 1.1, i.e., the original version of series.

     
  • Raymond Toy
    Raymond Toy
    2010-06-04

    Not exactly sure where the bug is. The issue appears to be that the graph is split into two parts. The first part contains scan-range and collect-first. The second has scan-range and collect subseries. When considering these in isolation in check-termination, no termination is needed. But when the two parts are combined, the result needs a termination.

    I don't know if the problem is how the parts are split (because subseries if off-line) or if the problem is combining the parts together.