Truth table evaluation, summary and thanks

I would like to thank everybody who replied to my post last week about
speeding up the evaluation of truth tables for arbitrary boolean
expressions.


Whilst some replies were more helpful than others they all suggested
something worthwhile.


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 !


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


Thanks,


Philip
--

Return to the comp.compilers page.
Search the comp.compilers archives again.