Home Original page

copy-on-write for dict objects?

Matthias Oberlaender matthias.oberlaender at REMOVE.daimlerchrysler.com
Thu Jan 16 08:51:51 EST 2003 
In <7h3n0m2p77m.fsf at pc150.maths.bris.ac.uk> Michael Hudson wrote:
> Matthias Oberlaender <matthias.oberlaender at REMOVE.daimlerchrysler.com> 
writes:
> 
> > Is there an easy way in Python 2.2.1 to add a copy-on-write mechanism to 
> > subclasses of dict, i.e. without extending/modifying the C-code 
> > implementation?  (I guess there is none!)
> 
> Not sure what you mean.  But I doubt it.  You need a level of
> indirection in there, so I don't see how you could do it directly even
> hacking C.
> 
> > I don't want to resort to UserDict again, since, at least for my
> > purposes, it's much slower than direct subclasses of dict (around
> > 10x)
> 
> I know that feeling.
> 
Thanks for all the answers so far (from Andrew, Just and Michael)

A line of "hacking" I could think of is this:

class MyDict(dict):

  def __init__(self, d)
    self.sharedDict = d
    self.oldPtr = getTable(self)
    # getTable should be some external function that returns the C pointer to
    # the object's hashtable
    setTable(self, getTable(self.sharedDict))
    # setTable should be some external function that explicitly sets the C 
    # pointer to the hashtable
    self.mustCopy = 1
    
  def _onWrite(self):
    setTable(self, self.oldPtr)
    self.update(self.sharedDict)
    self.sharedDict = None # give up the reference 
    self.mustCopy = 0
    
  ....

You get the idea? I don't know much about the magic behind the scenes. Maybe 
this is to naive? 

Why do I want this ? I use dictionaries to implement large sets. In my 
framework complementation of sets is allowed and implemented by simply 
switching a boolean attribute. Set union, intersection and complementation 
can be expressed by using a single type of operator. I call it "neggregation" 
(it is analogous to the NOR function). Neggregation is defined to be the 
complement of the union of its (arbitray many) arguments. As a special case 
we immediately have:  

def complement(X): return negg(X). 

A bit more subtle,  intersection can be expressed like this:

def intersection(A, B):  return negg(negg(A), negg(B))

And:

def union(A,B): return negg(negg(A,B))

So, negg(X) with a single argument returns the complement of X. Conceptually, 
this requires flipping only a flag. But if this function call also involved 
actual copying of lots of data, the above reduction would be fairly 
inefficient. Hence I want a copy-on-write. 


--
 ____  __  _/_/ . 
( / / ( /  / / /  

=====================================================================
Matthias Oberlaender, DaimlerChrysler AG, Research Center Ulm
RIC/AP (Machine Perception)
Wilhelm-Runge-Str. 11,  P.O. Box 2360,  89013 Ulm, Germany
Phone: +49 731 505 2354       Fax: +49 731 505 4105
Email: matthias.oberlaender at REMOVE.daimlerchrysler.com
=====================================================================
More information about the Python-list mailing list