LISTS: Extract every other element - SUMMARY

[Christian Tismer]

Hi Mike, Hi List,

I was nearly at home when it hit me:

Why do we get so different timing results here?
I think I got it: It is simply the frame allocation
heuristics which its me.

Frames are cached. Whenever a new frame is requested and
the frame cache isn't empty, the topmost frame on the freelist
is used.
But: If the frame is too small for the local variables of the
function to be called, a realloc takes place. This optimization
is good in the average. In my case, it is the showstopper.

My fast list creation uses 50 extra variables on the stack.
That is quite unusual, and it is very likely that the topmost
cached frame does not fit. A realloc takes place.

Now, Mike runs his tests this way:

1)

		for function in [ forMult,forDiv, numReshape, numSlicing, chrisGiven,
chrisInline]:
			avg = []
			for x in range(5):
				t = clock()
				function( data )
				avg.append( clock()-t )
			print '%s %.4f'%(function, reduce( lambda x,y: x+y, avg )/len(avg))

The result value of function ( data ) is thrown away immediately.

He runs my timing version this way:

2)
		for function in [ forMult,forDiv, numReshape, numSlicing, chrisGiven,
chrisInline]:
			elapsed, result = timing( function, (data,), 1 )
			print '%s %.4f'%(function, elapsed)

That's very different: The result variable is kept alive!

Why does this matter?
Since my functions need to do a realloc due to the frame size, this
will most likely eat the result variable which is freed in 1),
and creating the next result variable will find a big hole
which is too small, causing another expensive allocaiton.

In 2), the result variable is alive before and after the function call,
so it is much more likely that it will be reallocated in the second and
following runs.

Maybe this is no accurate analysis, but I'm very sure that we are
testing malloc here and not algorithms.

ciao - chris

-- 
Christian Tismer             :^)   <mailto:tismer at appliedbiometrics.com>
Applied Biometrics GmbH      :     Have a break! Take a ride on Python's
Kaiserin-Augusta-Allee 101   :    *Starship* http://starship.python.net
10553 Berlin                 :     PGP key -> http://wwwkeys.pgp.net
PGP Fingerprint       E182 71C7 1A9D 66E9 9D15  D3CC D4D7 93E2 1FAE F6DF
     we're tired of banana software - shipped green, ripens at home