dictionary.update() enhancement?

[David Bolen]

maj64 at hotmail.com (Mark J) writes:

> The above code merely preserves the semantics of the existing update
> function since that's the fairest test until dictionary.update() is
> changed.  (Note:  removing the conditional in withloop() still keeps
> it about 10x slower.)

But it's not the fairest test for prototyping the overhead - having
just the call to update never uses any callback to Python functions as
the proposed change would.  Thus, you stay entirely within the
internal C code for the update operation.  That's a major difference
from the proposed change.

> Of course, the performance difference will decrease as the complexity
> of the collision function increases, but many useful collision
> functions are about as simple as or even simpler than the one
> currently used by dictionary.update().

Except that they won't be written in C.  The overhead of getting out
to a Python callback function within the update processing will probably
be the major factor, as much as whatever that collision function does.

> By claiming only 10x faster in my last message, I was trying to
> (reasonably and fairly?) account for the extra overhead of running the
> collision function within update().
> 
> Please correct me if I'm missing something.  I'd also be interesting
> in hearing any big discrepancies on the performance factor on
> different platforms.

I think you're severely underestimating the overhead of calling back
out to Python processing code for the comparison function, and your
test case doesn't even try to simulate any overhead for that.  Sure, a
Python loop against complete C code is a big difference, but adding a
Python callback changes that a lot since now you have significant
Python code internal to the process in both cases, but in the callback
you're invoking a function each time.

While not precisely apples to apples, I think this is a reasonable
point of comparison.  In one case I sort a list just using the normal
internal sort comparison.  In the second and third cases I use a
callback function.  The first callback just calls the same internal
function that would be used anyway (but thus calls into the
interpreter C code again within the callback) - the second keeps it in
pure Python code, about as close to a minimum implementation as it
can.  Because the list is already sorted, there are 9999 callbacks to
the comparison routine, or just about the same as one callback per
entry as with a dictionary update.

    import time

    list = range(10000)

    def mycmp(x,y):
	return cmp(x,y)

    def mycmp2(x,y):
	return (x-y)

    start = time.clock()
    for i in range(100):
	list.sort()
    finish = time.clock()

    print (finish-start)/100.0

    start = time.clock()
    for i in range(100):
	list.sort(mycmp)
    finish = time.clock()

    print (finish-start)/100.0

    start = time.clock()
    for i in range(100):
	list.sort(mycmp2)
    finish = time.clock()

    print (finish-start)/100.0


On my machine, here's what I got:

    No cmp  0.00144961120768
    mycmp   0.0589527414929
    mycmp2  0.0315124934838

So you can see, that even in the simplest callback case, there's a
factor of about 22x between not having a Python code callback, and
having one.

Stretching a bit and extrapolating to your test (showing 23.9x faster
for a straight update versus a loop), that would seem to imply good
odds that having a callback in the update might be darn close in
performance to the explicitly written loop.

In any event, I wouldn't think it high odds that you'll actually see
it 10x faster with the callback.

--
-- David
-- 
/-----------------------------------------------------------------------\
 \               David Bolen            \   E-mail: db3l at fitlinxx.com  /
  |             FitLinxx, Inc.            \  Phone: (203) 708-5192    |
 /  860 Canal Street, Stamford, CT  06902   \  Fax: (203) 316-5150     \
\-----------------------------------------------------------------------/