🚀 go-pugleaf

Richard A. O'Keefe (ok@cs.rmit.edu.au) wrote:

> Packing to the bit level is a good way to optimise SPACE but a truly
> dreadful way to optimise TIME, particularly when you aren't even optimising
> space in the first place.

Packing to bit level can be a good way both to optimize space and time, in
suitable circumstances. A trivial example is that if your application only
require (a multiple of) boolean operations you can do 32 of them at the
same time in a 32 bit machine by using bitwise operations, performing
32-times faster. (No optimizing compiler can do this for you, unluckily.)
A more crazy application pack 8 nibbles to the same word and the only
thing he want to do to it is to add up them nibble by nibble as unsigned
integers and there's guaranteed to be no overflow. This is done 8 times
faster (in a routine in a MPEG encoder). I also see a program which pack
the whole row of a scene of reversi (or othello, whatever you call it)
in a 8-bit char, so that he can use a precalculated array to find the
leftmost bit set and rightmost bit set in single cycle rather than some
dozens. The craziest one I've seen is one from the Sun strlen() routine,
which pack 4 characters in a single memory word and use boolean
operations to test whether there's a 0 in any of the characters, allowing
a 10% increase in performance (as compared to loading the word and extract
the characters one by one within memory) and also allowing speedup if
memory word size grow.

Of course, no one will use such tricks everywhere (or you'll have perfect
secure code by obscurity :>), but in the bottleneck of a loop everything
would be exploited. Of course, relying in compiler support for this is, I
believe, stupid.

--
/-----------------------------------v
|Isaac To, kar-keung                |
|MPhil, Computer Science            |
|Mail: mailto:kkto@cs.hku.hk        |
|      mailto:kkto@hkusub.hku.hk    |
|      mailto:h9206479@hkuxa.hku.hk |
|URL: http://www.cs.hku.hk/~kkto    |
\-----------------------------------^