|Truth table evaluation firstname.lastname@example.org (Philip Riebold) (1994-02-25)|
|Truth table evaluation, summary and thanks email@example.com (Philip Riebold) (1994-03-04)|
|From:||Philip Riebold <firstname.lastname@example.org>|
|Keywords:||optimize, theory, summary|
|Date:||Fri, 4 Mar 1994 11:24:57 GMT|
I would like to thank everybody who replied to my post last week about
speeding up the evaluation of truth tables for arbitrary boolean
Whilst some replies were more helpful than others they all suggested
Here is a list of the suggestions I received.
Word level parallelism
Instead of evaluating one bit at a time use the first five variables as
bit vectors and evaluate 32 bits in parallel.
+~32 times faster irrespective of the expression, only took 5 minutes to
incorporate into the original code.
-It's so obvious I could have kicked myself for not thinking of it !
Use two bit vectors, one for the values and the other to indicate if a
value has been evaluated.
+Potentially fast if only a few positions of the table are referenced.
-Unfortunately my program references the table in essentially random
order. The test data I use references _all_ the elements. So there would
be no gain.
Run time code generation
Instead of interpreting the expression generate code at run time that
directly executes it.
+Fast, claimed factor of 10.
-Non-portable, requires knowledge of the specific machine architecture (is
a PD description of the SPARC architecture available anywhere out there
Various logic methods
Included ideas such as common sub expression evaluation, partial
evaluation and conversion to sum of products notation.
+Large gain in certain special cases
-Unlike previous methods any gain is not guaranteed and the time taken may
well outweigh the time saved.
In summary I implemented word level parallelism and the TT generation time
fell to 1/10'th of that for the rest of the program.
Return to the
Search the comp.compilers archives again.