🚀 go-pugleaf

I wrote, in connection with a failed attempt to obtain
ELEMENT-WISE access to a packed array of bits, that

>> 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.

kkto@csd.hku.hk (Isaac To ~{6E<RG?~}) writes:

>Packing to bit level can be a good way both to optimize space and time, in
>suitable circumstances.

but shifts the grounds of comparison to *successful* packing of sets
and doing SET-WISE operations.  That is a *very* different matter, because
(a) word-at-a-time operations do 16 or 32 or 64 or however many
    element operations in parallel
(b) the packing is effective (the method I was discussing is not)
(c) element-wise access to bits has overhead:

	b = a[i];
=>
	r1 := i				-- bit index
	r2 := r1 >> 3			-- byte index
	r1 := r1 & 7			-- bit within byte
	r2 := Byte[a + r2]		-- fetch byte
	r2 := r2 >> r1			-- shift so bit is in bit 0
	r2 := r2 & 1			-- isolate required bit
	b  := r1

    Contrast this with access to a byte:

	r2 := i
	r2 := Byte[a + r2]
	b  := r2

    Ignoring the initial fetch of "i" and the store to "b", because they
    may be bound to registers anyway, and the compiler can probably 
    eliminate those instructions, we find that

    ELEMENT-WISE fetch from a packed bit array has about 4 cycles of
    overhead compared with ELEMENT-WISE fetch from a byte array.

(d) In favour of set-wise operations, I note that byte access itself is
    expensive on some machines.


Note the following trick for walking through an array of unsigned longs,
processing each bit.  It assumes that each bit in the array is used.

	void walk_bits_in_ulongs(
	    unsigned long const *base,
	    unsigned             nwords,
	    void (*f)(unsigned /*bitno*/, int /*bit*/)
	) {
	    unsigned bitno;
	    unsigned i;

	    for (bitno = 0, i = 0; i < nwords; i++) {
		unsigned long const word = base[i];
		unsigned long mask;

		for (mask = 1; mask != 0; mask <<= 1, bitno++)
		    f(bitno, (word & mask) != 0);
	    }
	}

Again, the saving comes about because we are NOT fetching bits in a
true ELEMENT-WISE fashion, but in groups.

It is also worth noting that some machines have bit load, store, &c
operations.  Where would the 8051 be without them?  Bit packing makes
a lot of sense in such a case.  Not in portable C.

-- 
Result of state election = 50% Victorians didn't get MP of their choice.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.