[Bug-openmcl] type cache

[Gary Byers]

On Wed, 25 Feb 2004, bryan o'connor wrote:

> > is there anything in the spec which says anything about
> > whether/when/how
> > a list that's used as a type specifier can be destructively modified ?
>
> not that i have seen.
>
> i think regardless of immutability, if things* like this are
> allowed then the cache has problems because two similar but
> different types hash the same.  (i haven't convinced myself
> that things like this are used much outside of test suites)
>
>    (let* ((o1 '(foo bar))
>           (x1 `(member ,o1))
>           (o2 '(foo bar))
>           (x2 `(member ,o2)))
>      (values
>       (ccl::hash-type-specifier x1)      ; hashes to 710.
>       (typep o1 x1)
>       (typep o2 x1)
>       (ccl::hash-type-specifier x2)      ; hashes to 710.
>       (typep o1 x2)
>       (typep o2 x2))))
>
> with a cache enabled image, we get (values 710 T NIL 710 T NIL)
> without, the expected (avoiding the use of "correct" here) result
> (values 710 T NIL 710 NIL T).

Whoops. It's clearly wrong to assume that two EQUAL type-specifiers
denote the same type (EQL and MEMBER types being obvious exceptions,
when their subforms can be EQUAL without being EQL.)

One approach to allowing mutable list type-specifiers that generally
works is to cache a copy.  If an EQL or MEMBER specifier was encountered
in the copying process and its subform loses EQLness if it's copied,
the subform would have to be preserved.  Those subform cases are
generally those which could have dynamic-extent, so caching them
would be a bad idea.

I think that I'm starting to agree with your suggestion: we don't
cache anything where the translated type involves an EQL or MEMBER
type whose subform is of a type where EQLness can't be preserved
in a copy (so (EQL 1.0d0) is fine but `(EQL ,(list 1.0d0)) isn't).

If we don't cache those cases, I -think- that it's true that:

a) we can continue to use EQUAL for cache comparisons.
b) we can use COPY-TREE to ensure that we're caching something that
   the user can't modify.
c) we don't lose because of cached references to stack-consed things.
d) we'd preserve the benefits of caching (whatever they are, exactly ...)
   in call cases other than those where the current caching scheme
   can generate incorrect results.

At one point (when caching was first added to MCL) it seemed to be
a pretty big win performance-wise.  Whether that's true and to what
extent probably depends on the code mix.

CCL::TYPE-CACHE-HIT-RATE returns the number of successful probes
and total probes (and forces you to do the math ...).  I just checked;
in a lisp that I'd done some compilation and other things in, I had
about 200 misses in >85000 probes (99.6%).  The COPY-TREE and/or
analysis of MEMBER/EQL types would only have happened on the misses,
so it doesn't sound like it'd have much of a negative impact.

The test suite probably uses EQL/MEMBER types heavily in a few cases;
it'd be better to get the right answers slowly than the wrong ones
quickly ...


>
> although this case is written as one form, it could be two separate
> forms where o1/x1 have fallen out of scope before o2/x2 are bound.
> the type cache still has the previous type-spec keyed at 710.  this
> test form just shows that x1 is still in scope, so cache invalidation
> wouldn't solve this specific issue.
>
> this is what is causing the previously mentioned subtype failures.
> some tests use the same literals for the type-specs.
>

I have some questions about whether that's a good idea, but if it isn't
clearly prohibited it should probably be made to work reasonably.  I
think that we can keep the notion of caching in general, refuse to cache
a few cases, and be careful to cache EQUAL copies of things*.

>                              ...bryan
>
>
> *  "things" for lack of the right vocabulary.
>
> _______________________________________________
> Bug-openmcl mailing list
> Bug-openmcl at clozure.com
> http://clozure.com/mailman/listinfo/bug-openmcl
>
>