[Python-ideas] RFC: PEP: Add dict.__version__

[M.-A. Lemburg]

On 09.01.2016 14:21, Steven D'Aprano wrote:
> On Sat, Jan 09, 2016 at 01:09:13PM +0100, M.-A. Lemburg wrote:
> 
>> * Given that this is an optimization and not meant to be exact
>>   science, why would we need 64 bits worth of version information ?
>>
>>   AFAIK, you only need the version information to be able to
>>   answer the question "did anything change compared to last time
>>   I looked ?".
>>
>>   For an optimization it's good enough to get an answer "yes"
>>   for slow changing dicts and "no" for all other cases.
> 
> I don't understand this. The question has nothing to do with 
> how quickly or slowly the dict has changed, but only on whether or not 
> it actually has changed. Maybe your dict has been stable for three 
> hours, except for one change; or it changes a thousand times a second. 
> Either way, it has still changed.

I was referring to how many versions will likely have passed
since the code querying the dict last looked. Most algorithms
won't be interested in the version number itself, but simply
want to know whether the dict has changed or not.

>>   False
>>   negatives don't really hurt. False positives are not allowed.
> 
> I think you have this backwards.

With "false negatives" I meant: the code says the dict has
changed, even though it has not. With "false positives" I meant
the code says the dict has not changed, even though it has.

But you're right: I should have used more explicit definitions :-)

> False negatives potentially will
> introduce horrible bugs. A false negative means that you fail to notice 
> when the dict has changed, when it actually has. ("Has the dict 
> changed?" "No.") The result of that will be to apply the optimization 
> when you shouldn't, and that is potentially catastrophic (the entirely 
> wrong function is mysteriously called).
> 
> A false positive means you wrongly think the dict has changed when it 
> hasn't. ("Has the dict changed?" "Yes.") That's still bad, because you 
> miss out on the possibility of applying the optimization when you 
> actually could have, but it's not so bad. So false positives (wrongly 
> thinking the dict has changed when it hasn't) can be permitted, but 
> false negatives shouldn't be.
> 
> 
>>   What you'd need to answer the question is a way for the
>>   code in need of the information to remember the dict
>>   state and then later compare it's remembered state
>>   with the now current state of the dict.
>>
>>   dicts could do this with a 16-bit index into an array
>>   of state object slots which are set by the code tracking
>>   the dict.
>>
>>   When it's time to check, the code would simply ask for the
>>   current index value and compare the state object in the
>>   array with the one it had set.
> 
> If I've understand that correctly, and I may not have, that will on 
> detect (some?) insertions and deletions to the dict, but fail to 
> detect when an existing key has a new value bound.

This depends on how the state object is managed by the dictionary
implementation.

It's currently just a rough idea. Thinking about this some
more, I guess having external code set the state object
would result in potential race conditions, so not a good
plan.

The idea to add a level of indirection to reduce the
memory overhead, under the assumption that only few
dictionaries will actually need to report changes.

-- 
Marc-Andre Lemburg
eGenix.com

Professional Python Services directly from the Experts (#1, Jan 09 2016)
>>> Python Projects, Coaching and Consulting ...  http://www.egenix.com/
>>> Python Database Interfaces ...           http://products.egenix.com/
>>> Plone/Zope Database Interfaces ...           http://zope.egenix.com/
________________________________________________________________________

::: We implement business ideas - efficiently in both time and costs :::

   eGenix.com Software, Skills and Services GmbH  Pastor-Loeh-Str.48
    D-40764 Langenfeld, Germany. CEO Dipl.-Math. Marc-Andre Lemburg
           Registered at Amtsgericht Duesseldorf: HRB 46611
               http://www.egenix.com/company/contact/
                      http://www.malemburg.com/