In CUDD every diagram node is unique: If two diagrams have the same structure, they are in fact identical (same position in memory).
Another observation is, that CUDD tries to build a functional style API in the C programming language. This means, that no data is manipulated, only new nodes are created.
Functional programming is a priori very suited for caching and multithreading (at the moment however threading is not possible in POLYBORI).
The ite-operator is the most central function in CUDD. It takes two nodes/diagrams
,
and an index
and creates a diagram with root variable
and
then-branch
, else-branch
. It is necessary that the branches have root variables with bigger index (or are constant).
It creates either exactly one node, or retrieves the correct node from the cache.
Function calls which come essentially down to a single ite call are very cheap.
For example taking the product
is much cheaper than
.
In the first case, in each step a single not is prepended to the diagram, while in the second case, a completely new diagram is created.
The same argument would apply for the addition of these variables.
This example shows, that having a little bit background about the data structure, it is often possible to write code, that looks as well algebraic as provides good performance.
2009-09-10