tech-toolchain archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

Fast fixed division / remainder support

Hi all,
one of the slower parts of the cdb implementation are the computation of
the three remainder. There are well-known algorithms for replacing
division by constant with multiplication and shifts.

A small test shows that the resulting algorithm is consistently between
30% and 60% faster than a plain % if the (small) overhead of the
precomputation is not counted.

What do you think about adding something like sys/divide.h or extending
sys/bitops.h with three macros:
        fast_divide_prep(d, m, s1, s2)
        fast_divide(q, d, m, s1, s2)
        fast_remainder(q, d, m, s1, s2)

The first function does the precomputation, the other two compute q / d
and q % d. Comments?


Home | Main Index | Thread Index | Old Index