On Thu, 30 Mar 2000, Karen Shaeffer wrote:
> Hi Folks,
>
> I am developing a state space logic machine. In considering the
> implementation, I have two choices.
>
> 1.) I can utilize an array of integers, manipulating the space with
> operations on these integers.
>
> 2.) I can utilize bit-fields, manipulating the space with operations on
> these bit-fields.
>
> Can anyone please advise me about the tradeoffs inherent to these two
> options concerning speed of execution WRT decision logic and the implication
> for porting to other target platforms. I'm looking for maximum execution
> speed. The target platform is initially X86. I have some ideas about this,
> but would be interested in other opinions as well.
>
> You can send responses directly to me or on the list here, whatever is most
> appropriate.
You need to define if you intend to write the bit-fields and manipulate
them in 'C'. If you are using assembler, on an ix86, you can set/reset/
examine a single bit anywhere in memory. Using 'C', the most current
implementations I've seen read longwords, shift/and/or, then write them
back. This is additional overhead.
The fastest memory access you get is reading/writing longwords that are
aligned. In many cases, the register operations on these longwords can
occur while additional memory accesses are occurring. Therefore, overhead
of manipulating bits, if done in registers, can be quite low, possibly
even zero except when a branch is taken, but gcc 'C' usually manipulates
variables by copying them from global memory (if global), to local,
referenced on the stack, then it copies into a register, does a
single logical operation, writes it back to local storage, does another
single logical operation, writes it back, etc., eventually returning
it to global storage. Try your favorite bit operations and compile
with `gcc -O2 -S -o look.at.it filename.c`. 'look.at.it` will
contain the assembly that it generated.
It does not look like the 'gcc folks' have spent much time optimizing
bit operations.
Bit manipulation on most machines is not speed-efficient, instead it's
space-efficient. The fastest running sort, for instance, would have
a bunch of long keys that are being sorted, one key per record, rather
than bit-fields, each defining a record.
Cheers,
Dick Johnson
Penguin : Linux version 2.3.41 on an i686 machine (800.63 BogoMips).
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Fri Mar 31 2000 - 21:00:27 EST