[cells-devel] Optimized away/dying rules

[Peter Hildebrandt]

Ken,

thanks again for the info.  I guess some stuff got out of order here:

> First, just a point of information: do I understand correctly that the
> original example below uses an assoc instead of your store just to simplify
> the problem and highlight the key issue?

Yes and no.  Yes, the list stuff was my attempt of singling out what
was going on.  But! -- I wrote the stuff *before* I understood the
issue; in other words, this is how I tried (!) to do it before I made
the cells store.


> I am guessing yes, so I will charge ahead with my thoughts: basically you
> need to make the lookup itself establish a dependency. I had assumed that
> this what you had done when you said you had created a cells-aware store.

And you were assuming right -- That is, I hope what I did is what you
mean.  Indeed bwen-(c-)gethash (which I will rename to
bwhen-in-c-store or sth like that) expands into some code that creates
a dependency on a listener object in the store, which then in turn is
kicked when the hash table is updated.

> I
> was guessing that behind the scenes there was a second hashtable with the
> same key but a value that was a list of the cells that had looked it up. (Or
> you could try stuffing the thing stored with a list of asking cells in the
> one hash-value.)

Indeed there are two hash tables, one with the actual stored stuff and
one with auxiliary objects that are uses to toggle the update.  This
way we have two hash table lookups for every access, so maybe it would
make sense to keep the two in a cons in one table.  But hold on, I
hear "premature optimization".

> That would have gotten you into c-link, c-unlink, and other
> good stuff.

Not sure whether we are on the same page.  I have register-listener,
kick-listener, and unregister-listener as internal methods on the
store.  I assume we're talking similar ideas here.  I like your naming
convention, tho.

> And then you are done. Everything (including sensible optimization) just
> flows from that.

True.

> Sorry if I am all wet or if not for not examining your code earlier. I'd
> look now but jet lag beckons. I'll try later or just let me know if this is
> making sense.

Just for clarification:  I assume you have not yet looked at the code
in md-utilities, but were just going from what I had described here,
right?

I'lll put in a few changes based on what I ran into in test-gtk and on
what you wrote here and commit later today.

> ps. I did not stare too hard either at your deferred optimizarion or
> something idea because I saw this other more standard approach to the
> problem, but again if it turns out I missed something I'll stare at that too
> when I recover a little. k

Deferred optimization?  Now you lost me.  Not quite sure what you are
referring too.

> pps. Interesting idea: if things never go away you can lose the dependency
> of the seeker on the store once the sought key appears. Not sure how to
> express that, unless we tackle the not-to-be issue by doing something I have
> toyed with before (and might even still be out there): a rule that says when
> an instance dies. In the case where that is a hardcoded nil or a rule that
> produced nil and then got optimized away, the cells-store could drop the
> dependency from its side after propagating to the asker. k

That is interesting indeed.  I thought about that before, but I am not
sure my scheme will provide for that, it might need some major change
to what I do so far.  OTOH, the good news is that my idea of listener
or link cells reduces the overhead through this -- even if we have a
dependency on the link, this does not matter as long as we don't touch
the link.

Just random thought,

Peter

> On Wed, Apr 16, 2008 at 11:26 AM, Peter Hildebrandt
> <peter.hildebrandt at gmail.com> wrote:
> >
> >
> >
> > While working on the hash-table lookup for md-names (as an alternative
> > to fm-other) I came across an interesting phenomenon: Some rules die,
> > others don't.  Following the XP idea for RFEs, I'll try to present a
> > test case:
> >
> > (defpackage :c-test (:use :cl :cells :utils-kt))
> > (in-package :c-test)
> >
> > (defparameter *hash* (make-hash-table))
> > (defun val (name) (bwhen (obj (gethash name *hash*))
> >                            (value obj)))
> >
> > (defparameter *m1* (make-instance 'model :value (c? (bif (v (val
> > :foo)) (1+ v) 'nothing))))
> > (assert (eql (value *m1*) 'nothing))
> >
> > (setf (gethash :foo *hash*) (make-instance 'model :value (c-in nil)))
> >
> > (defparameter *m2* (make-instance 'model :value (c? (bif (v (val
> > :foo)) (1+ v) 'nothing))))
> >
> > (assert (eql (value *m1*) 'nothing))
> > (assert (eql (value *m2*) 'nothing))
> >
> > (setf (value (gethash :foo *hash*)) 42)
> > (assert (eql (value *m1*) 43))  ;;; #### FAILS ####
> > (assert (eql (value *m2*) 43))  ;;; ok
> >
> > (setf (value (gethash :foo *hash*)) 17)
> > (assert (eql (value *m1*) 18))  ;;; #### FAILS ####
> > (assert (eql (value *m2*) 18))  ;;; ok
> >
> > ;;; or with a list
> >
> > (defparameter *list* nil)
> > (defun valb (name) (bwhen (obj (assocd name *list*))
> >                            (value obj)))
> > (defparameter *m1b* (make-instance 'model :value (c? (bif (v (valb
> > :foo)) (1+ v) 'nothing))))
> >
> > (assert (eql (value *m1b*) 'nothing))
> >
> > (push (cons :foo (make-instance 'model :value (c-in nil))) *list*)
> >
> > (defparameter *m2b* (make-instance 'model :value (c? (bif (v (valb
> > :foo)) (1+ v) 'nothing))))
> >
> > (assert (eql (value *m1b*) 'nothing))
> > (assert (eql (value *m2b*) 'nothing))
> >
> > (setf (value (assocd :foo *list*)) 17)
> > (assert (eql (value *m1b*) 18))  ;;; #### FAILS ####
> > (assert (eql (value *m2b*) 18))  ;;; ok
> >
> > (setf (value (assocd :foo *list*)) 42)
> > (assert (eql (value *m1b*) 43))  ;;; #### FAILS ####
> > (assert (eql (value *m2b*) 43))  ;;; ok
> >
> > --------
> >
> > An interesting indicator might be that the first call to (value *m1*)
> > returns two values, 'nothing and nil -- does that mean that cells
> > somehow realizes there that this cell can be optimized out?
> >
> > And -- more importantly -- how can I tell cells not to optimize away
> > the ruled cell in *m1*/*m1b*?
> >
> > Thanks,
> > Peter
> > _______________________________________________
> > cells-devel site list
> > cells-devel at common-lisp.net
> > http://common-lisp.net/mailman/listinfo/cells-devel
> >
>
>