[boost] Re: [Boost-announce] Formal Review Tribool

From: Haim Cohen (haim.cohen_at_[hidden])
Date: 2004-05-23 02:58:06

Hi,

I am happy to contribute my review for the tribool library.
I am a software engineer developing EDA (Electronic Design Automation) software, so I think I can
contribute my 2 cents to the review of tribool, as I think EDA tools will benefit from this library.
I did not compile the library.
I have made a quick reading of this library, but an in-depth study of this problem domain before.

First of all, my first comment is about the library's name, as well as the class name.
In logic circuit simulation, there are 4 values : 0, 1, x ( which is tribool referred to as undetermine ), and z ( represents high impedance - or
disconnection, and sometime referred to as "tri state" ).
So, I think users will find it quite confusing when they see the 'tri' in the library's name.
Since the library implements a logic value which has some value that is unknown, I would suggest 'unknown bool' or 'x bool'.

Now to the interface.
I think that a macro which enables renaming of the x value should not be supplied. This will make people's code less standard.
Same as we all know what 'true' and 'false' mean, we should adopt a unique name for 'unknown yet quite determined logic value'.
I think the default 'undetermine' name is not a good name.
My suggestions : logic_x, x_value, x_logic, unknwon_bool .
I also think the default tribool constructor should create a tribool object which is 'undetermine'. (Not false, as in the documentation)
Besides the above, I think the interface of the class is good and succinct.

Some point for thought : Users might want arrays of tribools, with all the support of bitwise operations.
Is this should be a part of tribool as well ? I do not know.

Now I will refer to the implementation.
In real-life problems, programs might make a heavy usage of the tribool class for simulations of logic circuits.
A logic circuit (at least the combinatoric part) is a DAG where nodes are logic gates, and directed archs are wires.
This graph might be the result of a synthesis process, where a high level language for hardware description (e.g Verilog) is compiled into
this DAG. Note : This is a very general and simple description of the process. Life are much more difficult.
So, outputs will be calculated by performing lexicographic order of the DAG, and calculating from inputs to outputs.
I am telling this, to convince that performance is *very* important here.

With a quick look at the implementation code, I think that calculating the value using branches (if else) will not result with good performance.
Calculations with true/false values only is fast - CPU vendors dedicate special hardware for this, so calculation can be made in one machine cycle.
Even bitwise calculation (up to some word width) is done in one machine cycle.
Compilers are making use of this, and (hopefully) compiles boolean and bitwise operators to the appropriate instruction.
Unfortunately, I did not see any CPU which supports built in true/false/X arithmetic. And even if there are such CPUs available, we will not be able
to use it, since boost libraries should be portable.

So, it is very tempting to think - how can we implement efficient true/false/X arithmetic using the existing boolean arithmetic ?
One tempting idea is to represent true/false/X with some integers, and use bitwise arithmetic to get the right results.
It seems there are no such integer values. I think I even managed to proof this.

Since there is already a library implementing 4 values logic (0,1,x,z) - which is SystemC - I took a quick look on how they do it with their 4-states
logic data type called sc_logic.
They use an approach which I think should be also used in tribool.
It seems that they maintain lookup tables for each operation: AND, OR, NOT, XOR (!=) and XNOR (==).
As the internal representation of tribool is enumerated type, we can use the integer value of this enumerated type to access
the lookup tables (primitive 2D fixed-size and fixed-values arrays) and get the result of the calculation.
This will be much faster since most CPUs has a special addressing mode for accessing arrays.
So, I suggest to change implementation to use class-static fixed array to perform calculations.

I know that the spirit of Boost is portability and not performance, but since what is suggested here is actually very similar to a primitive
data type which might be heavily used in applications, I think it is important to consider performance as well.

I hope this review would be found useful.

Haim

-- 
_____________________________________________________
Haim Cohen
Software Engineer
haim.cohen_at_[hidden] / haimcohen2002_at_[hidden]
Analog Devices
Israel
(972) - 9 - 9715 406