Author mark.dickinson
Recipients fredrikj, loewis, mark.dickinson, rhettinger, terry.reedy, vstinner
Date 2008-12-13.11:19:17
SpamBayes Score 1.5132e-11
Marked as misclassified No
Message-id <1229167219.09.0.273966928079.issue3439@psf.upfronthosting.co.za>
In-reply-to
Content
> Did you look at the O(lg n) algorithm yet?  Any thoughts?

So there are two places this could be applied:  the int_numbits method 
and _PyLong_NumBits.  I'd be quite surprised if this offered any 
noticeable speedup in either case.  Might be worth a try, though---I'll 
see if I can get some timings.

For int_numbits, it would have to be implemented in a way that works for 
32-bit and 64-bit C longs.  And if it also just happens to work for 
other sizes, that would be good, too.  I'd probably try something like:

while (v > 0xFFFFFFFF) {
     bitcount += 32;
     v >>= 32;
}

before doing a 32-bit bitcount on what's left.  On a 32-bit machine,
the whole while loop should just be optimized away to nothing.  

Similarly, in _PyLong_NumBits it would be good if it could be 
implemented in a way that doesn't have to change if/when PyLong_SHIFT is 
changed.

I prefer the second variant given (the non-branching version).
History
Date User Action Args
2008-12-13 11:20:19mark.dickinsonsetrecipients: + mark.dickinson, loewis, rhettinger, terry.reedy, vstinner, fredrikj
2008-12-13 11:20:19mark.dickinsonsetmessageid: <1229167219.09.0.273966928079.issue3439@psf.upfronthosting.co.za>
2008-12-13 11:19:18mark.dickinsonlinkissue3439 messages
2008-12-13 11:19:18mark.dickinsoncreate