Re: Bit manipulation

[Robert Dewar <robert_dewar@my-deja.com>]

In article <3A0E3116.83AEC906@acm.org>,
  Jeff Carter <jrcarter@acm.org> wrote:
> The fastest but most space-consuming solution would use a
> look-up table. Few implementations will support an array of
> the required size.


You obviously cannot afford a loop through 32 bits, that's
a gruesomely inefficient implementation. The proper thing
is to establish a look up table of 256 entries (that takes
up only 256 bytes and easily fits into primary cache). Then
program the byte swap (if you are on a machine with a byte
swap instruction like the Power PC, it can be used directly).

If you have a bit more space, you can make a table of
64K 16-bit entries and do 16-bit swaps by table lookup.
That still takes only 128K bytes, which can easily fit
in secondary cache.

Even if you could afford a table of 16 gigabytes for the
full lookup, you would not want to use such an approach,
since you would get cache misses, and probably TLB misses
as well on every access, and it would be horribly slow.

You just HAVE to be sensitive to cache and TLB-miss issues
in modern programming if performance is an issue. Far too
many people have not adjusted their thinking and are still
programming for non-pipelined non-cached machines in their
minds :-)


Sent via Deja.com http://www.deja.com/
Before you buy.