Steel Bank Common Lisp

SATISFIES makes vectors hairy

Reported by Nikodemus Siivola on 2009-01-11
4
Affects Status Importance Assigned to Milestone
SBCL
Medium
Nikodemus Siivola

Bug Description

Reported by Cedric St-Jean to sbcl-devel on 12/28/08:

Under SBCL 1.0.14:

(defun foo (x)
  (declare (type (and simple-bit-vector (satisfies bar)) x)
  (elt x 5))

Under high speed policy, the compiler treats x as an hairy vector, so
it's slow. Without 'satisfies, it works fine of course.

Changed in sbcl:
importance: Undecided → Medium
status: New → Confirmed
Nikodemus Siivola (nikodemus) wrote :

The issue is with EXTRACT-UPGRADED-ELEMENT-TYPE not understanding intersection types.

description: updated
tags: added: compiler-ir1 easy
removed: compiler
tags: added: types
Gustavo (gugamilare) wrote :

This is my first attempt to fix a bug, so forgive me if I am doing something wrong.

A attempted to modify the function extract-upgraded-element-type to support both intersection and union types. If this is a bit excessive, one can comment or exclude those parts in the code. The support for union types makes the code for extracting the element type of strings superfluous (since string is a union type), and it works exactly the same (at least for some tests I made here).

To test, I've extracted the "extract-from-type" function inside the version I made (look in the attached file). Here are some results:

sb-c> (extract-from-type (specifier-type '(and simple-bit-vector string (satisfies bar))))
#<named-type *>
nil
sb-c> (extract-from-type (specifier-type '(and simple-bit-vector (satisfies bar))))
#<numeric-type bit>
nil
sb-c> (extract-from-type (specifier-type '(or simple-bit-vector string (satisfies bar))))
#<named-type *>
#<named-type t>
sb-c> (extract-from-type (specifier-type '(or simple-bit-vector string)))
#<named-type *>
#<union-type (or character bit)>
sb-c> (extract-from-type (specifier-type 'string))
#<named-type *>
#<character-set-type character>
sb-c> (extract-from-type (specifier-type '(and string base-string)))
#<character-set-type base-char>
nil

Now, some tests around the given problem (after redefining sb-c::extract-upgraded-element-type).

sb-c> (defun bar (x)
 (declare (optimize speed (safety 0))
   (ignore x))
 t)
style-warning: redefining bar in DEFUN
bar
sb-c> (declaim (inline bar))
; No value
sb-c> (defun foo (x)
  (declare (type (and simple-bit-vector (satisfies bar)) x)
    (optimize speed (safety 0)))
  (elt x 5))
style-warning: redefining foo in DEFUN
foo
sb-c> (time (dotimes (i 100000000) (foo #*001010011)))
Evaluation took:
  1.653 seconds of real time
  1.644103 seconds of total run time (1.644103 user, 0.000000 system)
  99.46% CPU
  1,816,503,848 processor cycles
  127,952 bytes consed

nil
sb-c> (defun foo (x)
  (declare (type simple-bit-vector x)
    (optimize speed (safety 0)))
  (elt x 5))
style-warning: redefining foo in DEFUN
foo
sb-c> (time (dotimes (i 100000000) (foo #*001010011)))
Evaluation took:
  1.317 seconds of real time
  1.308082 seconds of total run time (1.308082 user, 0.000000 system)
  99.32% CPU
  1,322,662,844 processor cycles
  96,448 bytes consed

nil
sb-c> (defun foo (x)
  (declare (type (satisfies bar) x)
    (optimize speed (safety 0)))
  (elt x 5))
style-warning: redefining foo in DEFUN
foo
sb-c> (time (dotimes (i 100000000) (foo #*001010011)))
Evaluation took:
  3.816 seconds of real time
  3.764235 seconds of total run time (3.756235 user, 0.008000 system)
  98.64% CPU
  7,153,538,464 processor cycles
  304,064 bytes consed

nil

Note that I didn't recompile SBCL to run those tests, I just changed the function definition. In any case, there is always a small overhead when foo's argument is declared to satisfy bar, but that overhead is not the same overhead if the simple-bit-vector declaration is omitted , so I think this fixes the problem.

Changed in sbcl:
assignee: nobody → Nikodemus Siivola (nikodemus)
Nikodemus Siivola (nikodemus) wrote :

In SBCL 1.0.36.15.

Changed in sbcl:
status: Confirmed → Fix Committed
Changed in sbcl:
status: Fix Committed → Fix Released
To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers

Bug attachments