[pypy-dev] Optimizing Append Only structures

[Maciej Fijalkowski]

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?