optimize a loop which uses some linear expression as a condition

Bug #554145 reported by Roman Marynchak
6
This bug affects 1 person
Affects Status Importance Assigned to Milestone
SBCL
Confirmed
Wishlist
Unassigned

Bug Description

SBCL fails to optimize this code at compile time and becomes very busy at runtime, printing nothing after long calculations:

(defun g()
 (loop for i from 2 to 100000 do
  (loop for j from i to 100000
    when (= j (- i 1)) do (print "Hi"))))

When loop variables have a monotonic defined range, and an action condition may be expressed as 'k1x1 + b1 > k2x2 + b2', where x1 and x2 are loop indexes and k1,k2,b1,b2 are some constants, it is easy to say whether a condition will become valid for some pair (x1, x2) or not (recall your geometry course here for a clear analogy). I believe that SBCL as a modern optimizing compiler should analyse cases like this, they are quite simple.

Regards,
Roman

Tags: optimization
Nathan Froyd (froydnj)
Changed in sbcl:
importance: Undecided → Wishlist
tags: added: optimization
Changed in sbcl:
status: New → Confirmed
summary: - SBCL fails to optimize a loop which uses some linear expression as a
- condition
+ optimize a loop which uses some linear expression as a condition
To post a comment you must log in.
This report contains Public information  
Everyone can see this information.

Other bug subscribers

Remote bug watches

Bug watches keep track of this bug in other bug trackers.