GeezerVison

You should use PyAPI_FUNC(unsigned int) rather than extern.

By the way, _Py symbols should be moved to a new Include/cython/pymath.h header IMHO, and excluded from the stable API.

(1) Done.

(2) Sounds reasonable. Would you prefer to start this new file now (and move the other private functions later), or a seperate patch that moves all of the existing private functions including this new one?

Can't we unroll manually the loop using SIZEOF_LONG? For example, 4 bytes long need 0 loop. 8 bytes long only require a single if(). There is no platform supported by Python with long larger than 8 bytes (64 bits).

A 4-byte long would need up to 6 iterations (and an 8-byte long up to 11): we're only removing 6 bits per iteration.

This can probably be optimized to work without branching (using the __clz intrinsic or equivalents). But I'd prefer to keep this patch as a pure refactoring, simply chosing the better of the existing implementations, for now.

Oh wait, I didn't notice that it's "only" 6 bits per iteration. I read 32 bits by mistake. You can ignore my comment.

Using clz was discussed in: https://bugs.python.org/issue29782

But it was rejected: https://bugs.python.org/issue29782#msg290973

Maybe the best we can do is to add a short comment to explain why we use a "naive" implementation (not really naive, it uses a precomputed table) linking to bpo-29782.

Would you mind to add such short comment?

By the way, int.bit_length() has a complexity of compleO(1) in practice, no? (I consider that this function has a complexity of O(1), especially when you consider Python int objects made of many "Python digits".)

Would it make sense to convert this function to an static inline function only exposed in the internal C API?

For sure, the declaration in pymath.h should be protected by an #ifndef Py_LIMITED_API. @vstinner: I'm not sure I'm understanding you correctly, though. Making this static would make it unavailable to the other files that need it, wouldn't it?

Ah, I see: you're suggesting moving the entire function definition to pymath.h, and making it static inline. Is that right?

Right. Sorry, my comment was unclear. I converted some macros to static inline functions in header files.

I don't know if it would be worth it in term of performance.

Could be worth a try; I'd be surprised if it makes a measurable difference, but we won't know without testing.

But if not, we do need the Py_LIMITED_API guard: we don't want to expose _Py_bit_length to 3rd party libraries.