[pypy-dev] Optimizing Append Only structures

[Romain Guillebert]

Probably because he (as a clojure developer) likes immutability of data
structures.

On Tue, Nov 29, 2011 at 9:15 PM, Maciej Fijalkowski <fijall at gmail.com>wrote:

> On Tue, Nov 29, 2011 at 10:12 PM, Alex Gaynor <alex.gaynor at gmail.com>
> wrote:
> >
> >
> > On Tue, Nov 29, 2011 at 3:04 PM, Timothy Baldridge <tbaldridge at gmail.com
> >
> > wrote:
> >>
> >> I have a dictionary (in RPython) that looks something like this:
> >>
> >>
> >> class MyDict(Obj):
> >>    def add(self, k, v):
> >>         newdict = self.dict.copy()
> >>         newdict[k] = v
> >>         self.dict = newdict
> >>    def get(self, k):
> >>        d = self.dict
> >>        return MyDict._static_get(d, k)
> >>   @staticmethod
> >>   @purefunction
> >>   def _static_get(d, k):
> >>        if d not in k:
> >>            return None
> >>        return d[k]
> >>
> >>
> >> I'm trying to figure out the best way to optimize this. As you see,
> >> this structure is "append only". That is if mydict.get("foo") returns
> >> a value it will always return that value, for all time. In that sense,
> >> the function is pure. If however, the function returns None, then it
> >> could change in the future.
> >>
> >> This is for my Clojure on PyPy implementation. The idea is that types
> >> can be extended via protocols, at runtime, at any point in the
> >> program's execution. However, once a given type is extended to support
> >> a given interface (or protocol) it will never be able to be changed.
> >> That is, once we extend Foo so that it implements Foo.count() it will
> >> implement Foo.count() for all time.
> >>
> >> Any thoughts on how to optimize this further for the jit? I'd like to
> >> promote the value of get() to a constant, but I can only do that as
> >> long as it is not None. After Foo is extended, I'd like the jit to
> >> re-generate the jitted code to remove all guards, hopefully saving a
> >> few cycles.
> >>
> >> Timothy
> >>
> >>
> >> --
> >> “One of the main causes of the fall of the Roman Empire was
> >> that–lacking zero–they had no way to indicate successful termination
> >> of their C programs.”
> >> (Robert Firth)
> >> _______________________________________________
> >> pypy-dev mailing list
> >> pypy-dev at python.org
> >> http://mail.python.org/mailman/listinfo/pypy-dev
> >
> >
> > Sounds like the idea you're looking for is basically out-of-line guards.
> >  Basically the idea of these is you have  field which rarely changes, and
> > when it does you should regenerate all code.  So you would have an object
> > with the dict and a signature, and you could mutate the dict, but
> whenever
> > you did, you'd need to update the signature.  PyPy's module-dictionary
> > implementation shows an example of
> > this:
> https://bitbucket.org/pypy/pypy/src/default/pypy/objspace/std/celldict.py
> >
> > Alex
> >
> > --
> > "I disapprove of what you say, but I will defend to the death your right
> to
> > say it." -- Evelyn Beatrice Hall (summarizing Voltaire)
> > "The people's good is the highest law." -- Cicero
> >
> >
> > _______________________________________________
> > pypy-dev mailing list
> > pypy-dev at python.org
> > http://mail.python.org/mailman/listinfo/pypy-dev
> >
>
> Why do you always make a copy of a dict btw?
> _______________________________________________
> pypy-dev mailing list
> pypy-dev at python.org
> http://mail.python.org/mailman/listinfo/pypy-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/pypy-dev/attachments/20111129/50f6290a/attachment.html>