[MERGE] rand_chars() optimization

[Robert Collins]

On Sun, 2007-03-11 at 17:14 +0300, Dmitry Vasiliev wrote:
> John Arbash Meinel wrote:
> > John Arbash Meinel has voted +1 (conditional).
> > Status is now: Semi-approved
> > Comment:
> > Well, if we are going to optimize this one, I have a couple other hints.
> > 
> > First, I like the dictionary.
> > 
> > But appending to a string is expensive, because it has to generate a new 
> > string each time. I'm not sure how this effects rand_chars(16) which is 
> > our common case, but it should be a big deal for rand_chars(50).
> > 
> > And then, if you are using a dictionary, you should make it a local 
> > variable before the loop.
> > 
> > So this is what I would do:
> > 
> > def rand_chars(num):
> >   _map = _rand_chars_map
> >   return ''.join([map[b] for b in rand_bytes(num)])
> > 
> > Using a list comprehension, and then doing using string.join should be 
> > faster.
> > 
> > I tested a list comprehension versus a generator, and 'timeit' says that 
> > the list is faster. I assume this is because the string can iterate once 
> > to figure out how long it needs to be, and then again to merge 
> > everything together. (13us per loop versus 10s) per loop.
> > 
> > So I'm happy with your version, but there are a couple more tricks we 
> > can apply.
> > 
> > Can you benchmark it with the alternative, to see how much it helps?
> 
> Actually I've already tested list/generator comprehension versions and 
> surprisingly version which appending to a string was faster. But I 
> didn't test version with the mapping as a local variable.
> 
> After I've added the local variable test results are:
> 
>   - Generator comprehension: 6577ms/6921ms
>   - List comprehension: 5608ms/5921ms
>   - New version with the loop: 5405ms/5750ms
> 
> I've attached the new version with less memory-aggressive benchmark and 
> the mapping as a local variable.

Cool. Can I ask, did you profile this on python 2.4 and 2.5? One thing
to be wary of in micro optimisations is the possibility of pessimissing
on untested platforms.

-Rob

-- 
GPG key available at: <http://www.robertcollins.net/keys.txt>.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20070312/94a09f63/attachment.pgp