Re: Counting Bits

From: SINCLAIR DOUGLAS N <sinclai@ecf.toronto.edu>
	The only sane way to count the number of 1 bits in a byte is to use
	a lookup table:

		return table[result];

	On an intel chip this produces ONE opcode:

		XLAT

Do you think we'd all be spending weeks on it if it were that easy?

Or are you suggesting that 32-bits of address space of RAM is reasonable
for this problem?  Even if it's a 16-bit table you still have to do the
add; worse, the non-local access shits all over the bus timings and
the cache.  Much better to avoid going off-chip and keep the CPU
running at full speed (which might be 100 times faster than memory).

Again, remember we're nottalking about PCs here but real computers.

G
PS I dunno what superoptimisizer Perry is talking about but I've
never heard of a real one that works.  You have to feed in a complete
machine description at register transfer level and i don't know if
those exist for real machines; also the problem is almost certainly
exponential time for a *guaranteed* solution as Perry claims is
possible.

Graham Toal says:
> PS I dunno what superoptimisizer Perry is talking about but I've
> never heard of a real one that works.  You have to feed in a complete
> machine description at register transfer level and i don't know if
> those exist for real machines; also the problem is almost certainly
> exponential time for a *guaranteed* solution as Perry claims is
> possible.

As I've noted, Henry Massalin invented the superoptimizer -- and it
works -- a much slower but publically available implementation that
Henry had nothing to do with is available from the FSF as "Gnu
Superopt".

Perry