On 2011-06-18, at 1:02 PM, Paul Khuong wrote:
> The branch "master" has been updated in SBCL:
> via e7100f143ac497232623ada89aa364b720faa345 (commit)
> from 8f31e3b32926c61b13240c447637d4bb9af10cdc (commit)
>
> - Log -----------------------------------------------------------------
> commit e7100f143ac497232623ada89aa364b720faa345
> Author: Paul Khuong <pvk@...>
> Date: Fri Jun 17 23:23:43 2011 -0400
>
> More explicit high-level interface for consets
>
> Strictly no performance or behaviour difference, but it may be
> helpful to understand constraint propagation or even improve it.
I think this opens up a couple opportunities for rewriting. For instances, I'm pretty sure that inheriting constraints through EQLness is a major source of slowdowns and could be optional. Inversely, if we wanted stronger propagation, an artefact of the way we lazily propagate constraints for variables shows up in the following:
CL-USER> (lambda (x y)
(declare (type fixnum x))
(cond ((eql x y) ; A
(setf x 0) ; B
y)
(t x)))
#<FUNCTION (LAMBDA (X Y)) {1004AA0489}>
CL-USER> (sb-kernel:%simple-fun-type *)
(FUNCTION (FIXNUM T) (VALUES T &OPTIONAL))
What happens is that, at program point A, X and Y are asserted to be EQL. Constraint propagation would have no trouble deducing that Y is a fixnum at A. However, at program point B, everything related to X is forgotten, including the fact that X and Y are EQL (since they're not). However, we also forget that Y is still EQL to X at program point A, and thus that Y is a fixnum. That's the main issue that I can see with the way we implement deduction from constraints, processing constraints in bulk, when needed, instead of tightening types as we go; a simple fix would be to assert that Y is of X's declared type when we delete the constraint (EQL X Y).
Never mind the fact that we pretty much only use the types derived from our flow-sensitive analyses for optimisation, instead of also using useful facts like previously-executed predicates.
Paul Khuong
|