search

geisserf / lemon-dd

Library for Edge-valued MONoid-based decision diagrams.
Boost Software License 1.0
2 stars 0 forks source link

Optimize memory consumption #4

Open geisserf opened 5 years ago

geisserf commented 5 years ago

Currently the library is not optimised for memory. One easy optimisation is to remove the variable names in EVMDD nodes and instead rely on the ordering (which gives the name for each level). A more sophisticated optimisation would be to store the nodes in a continuous vector instead in a map. This would hopefully also increase cache locality.

geisserf commented 5 years ago

Discussion from an issue from the old repository which is related to this:

Initially, we wanted to store nodes by their ID in the storage and look up their IDs to see if we already cached them. Right now, we immediately look up the pointer to the node, instead of first retrieving the node id and then the pointer.

The upside is that we can immediately check if the node exists (nullptr check), which is easier than to check if the id exists (because map[key] = value default initializes value, if key does not exist in the map, which is nullptr for pointers, but 0 for ints, which would be the id of the terminal node). We also do not have to retrieve the node by its id after we get the id.

One possible downside could be that nodes are not stored contigously in memory. However, since we store potentially many nodes that are not used in the current evmdd, this may not matter.

We should either remove the node ids altogether, or hash keys to ids instead of pointers.

geisserf commented 5 years ago

Further discussion:

Currently, each node has a field for its variable. However, in practice we know which node corresponds to which variable, because we know the ordering (therefore the variable of a node is identified by its level in the graph). As a consequence, the evmdd is responsible for correct assignment from variables to levels (since each evmdd has its own ordering). The only question is how to quickly identify the correct (partial) state index for node evaluation.

If we want to further save memory we could also get rid of the node id. It is currently only used to sort nodes, which is required for EvaluationCache. However, I believe we could simply store node pointers instead of nodes in the EvaluationCache. It might however be used in our fast-downward compilation, so we would have to double check there.

As a result, a node would only consist of its assigned level and its children.

geisserf commented 5 years ago

Please update the wiki page when this issue is closed.

digitalw commented 5 years ago

As of now the node ID is used in the EVMDD compilation of fast-downward. A workaround would be to use an FD internal id instead.

For the variable, we could provide a map level->var for external use, when using LEMON-DD as a library.

geisserf commented 5 years ago

For the variable, we could provide a map level->var for external use, when using LEMON-DD as a library.

I think the ordering can be used instead, since it already stores the information of level -> variable.