[pypy-dev] Optimizing Append Only structures

Alex Gaynor alex.gaynor at gmail.com
Tue Nov 29 21:12:18 CET 2011


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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/pypy-dev/attachments/20111129/0abe78d2/attachment-0001.html>


More information about the pypy-dev mailing list