On 2/1/2012 12:59 PM, Stephan T. Lavavej wrote:
Integer divisions are surprisingly expensive, relatively speaking. While changing deque, we introduced integer divisions that noticeably harmed performance. We got rid of them (restoring the perf and then some) by introducing a power-of-2 guarantee that let us use bitwise operations instead.
Of course, this will only matter in very high performance code, like the fundamental operations performed by a container.
STL
Ah, good. Something non-contentious that I can contribute. There is a standard technique used in hashing and some other situations, that allows a divide/mod to reduce a value to an arbitrary range with a multiply and shift (frequently, in practice, multiplying into a wider width location, then indexing). For this to work well, however, higher order bits/digits/oits/hits/... must be well distributed. If this cannot be relied upon, techniques like bit rotates, swapping halves, xor-oring low bytes onto the high ones or doing a multiply by a constant ignoring overflow, before applying the algorithm can fix things. The technique is to multiply the original value by the range and just use the overflow. Just think of the value to be hashed as the numerator of a rational with one plus the maximum value as the denominator. Topher