incomplete node map

[lee30sonia]

incomplete_node_map has similar interfaces as unordered_node_map, e.g. has, erase. They can hold "empty" values. unordered_node_map uses std::unordered_map (i.e. hash map) as the underlying data structure, which saves memory when the map is sparse. incomplete_node_map uses std::vector together with std::variant to mark data validity, which has a faster access time and is more cache-friendly when elements are frequently accessed.

A simple runtime experiment:

partial_simulator sim( aig.num_pis(), 1024 );
//unordered_node_map<kitty::partial_truth_table, aig_network> tts( aig );
incomplete_node_map<kitty::partial_truth_table, aig_network> tts( aig );
simulate_nodes( aig, tts, sim ); // simulate the whole circuit
std::vector<bool> pattern( aig.num_pis(), false );
sim.add_pattern( pattern );
aig.foreach_po( [&]( auto const f ){
    simulate_node( aig, aig.get_node( f ), tts, sim ); // re-simulate the transitive fanin cone of each PO
});

Using incomplete_node_map instead of unordered_node_map in the second line provides about 20% speed up when using large benchmarks (e.g. IWLS leon2).

[codecov-commenter]

Codecov Report

Merging #494 (63eefe7) into master (d1925fe) will increase coverage by 0.03%. The diff coverage is 96.07%.

@@            Coverage Diff             @@
##           master     #494      +/-   ##
==========================================
+ Coverage   83.55%   83.58%   +0.03%     
==========================================
  Files         140      140              
  Lines       16638    16677      +39     
==========================================
+ Hits        13902    13940      +38     
- Misses       2736     2737       +1     

Impacted Files	Coverage Δ
...clude/mockturtle/algorithms/pattern_generation.hpp	65.10% <ø> (ø)
include/mockturtle/algorithms/sim_resub.hpp	51.66% <0.00%> (-0.44%)	:arrow_down:
include/mockturtle/algorithms/simulation.hpp	92.30% <90.90%> (+0.07%)	:arrow_up:
include/mockturtle/algorithms/dont_cares.hpp	94.17% <100.00%> (ø)
include/mockturtle/utils/node_map.hpp	98.91% <100.00%> (+0.69%)	:arrow_up:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update d1925fe...63eefe7. Read the comment docs.