On 28/05/2006 12:10 AM, Gonzalo Monzón wrote:
[good advice snipped]
Example A:
This code is more than 80 times faster than a "easy" Python
implementation. For every call, it does some bitwise operations and does
an array lookup for every string character from argument. Its a lot
faster because in Python approach a list lookup is done and it is a lot
faster to do a C array lookup -thought that in these C loops no Python
type value conversions are needed, if it where the case, C approach
would not be so faster than python. I don't know how would perform an
array based Python code, but I expect it to be a lot faster than using a
list, so Python code can be speed up a lot if you know how to do it.
// C code:
int CRC16Table[256]; // Filled elsewhere
int CalcCRC16(char *str)
{
int crc;
for(crc = 0xFFFF; *str != 0; str++) {
crc = CRC16Table [(( crc >> 8 ) & 255 )] ^ ( crc << 8 ) ^ *str;
Gonzalo, just in case there are any C compilers out there which need to
be told:
> for(crc = 0xFFFF; *str != 0
{
> crc = CRC16Table [(( crc >> 8 ) & 255 )] ^ ( crc << 8 ) ^ *str++;
}
return crc;
}
# Python code
gCRC16Table = [] # Filled elsewhere
def CalcCRC16(astr):
crc = 0xFFFFL
Having that L on the end (plus the fact that you are pointlessly
maintaining "crc" as an *unsigned* 32-bit quantity) will be slowing the
calculation down -- Python will be doing it in long integers. You are
calculating a *sixteen bit* CRC! The whole algorithm can be written
simply so as to not need more than 16-bit registers, and not to pollute
high-order bits in 17-or-more-bit registers.
for c in astr:
crc = gCRC16Table[((crc >> 8) & 255)] ^ ((crc & 0xFFFFFF) << 8) ^
ord(c)
Note that *both* the C and Python routines still produce a 32-bit result
with 16 bits of high-order rubbish -- I got the impression from the
previous thread that you were going to fix that.
This Python routine never strays outside 16 bits, so avoiding your "&
255" and a final "& 0xFFFF" (which you don't have).
def CalcCRC16(astr):
crc = 0xFFFF
for c in astr:
crc = gCRC16Table[crc >> 8] ^ ((crc & 0xFF) << 8) ^ ord(c)
return crc
==============
To the OP:
I'd just like to point out that C code and Pyrex code can gain
signicantly (as the above example does) by not having to use ord() and
chr().
As Gonzalo says, read the generated C code. Look for other cases of
using Python built-ins that could be much faster with a minor bit of
effort in Pyrex e.g. "max(a, b)" -> "(a) > (b) ? (a) : (b) " or if you
don't like that, a cdef function to get the max of 2 ints will be *way*
faster than calling Python's max()
