Implement CASE on fixnums or characters by binary search

Bug #1841993 reported by Paul F. Dietz
6
This bug affects 1 person
Affects Status Importance Assigned to Milestone
SBCL
Fix Released
Wishlist
Douglas Katzman

Bug Description

CASE forms in which the constants are fixnums or characters are currently implemented as linear searches. Instead, be smarter and exploit the ordering of these values to do binary search.

Example:

(defun f (x) (case x (#.(loop for i from 0 to 25 collect (code-char (+ i (char-code #\a)))) t)))

(defun g (x) (case x (#.(loop for i from 1 to 30 collect i) t)))

Stas Boukarev (stassats)
Changed in sbcl:
importance: Undecided → Wishlist
Revision history for this message
Douglas Katzman (dougk) wrote :

These examples both turn into jump tables (on supported architectures) now.

There's an argument to be made that the CASE macro could be smart enough to expand G into
  (if (typep x '(integer 1 30)) t) nil)
Patches are welcome, as always.

Changed in sbcl:
assignee: nobody → Douglas Katzman (dougk)
status: New → Fix Committed
Douglas Katzman (dougk)
Changed in sbcl:
status: Fix Committed → Fix Released
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.