adiar
adiar copied to clipboard
Shortcut merge-conditional at compile-time when sink-arcs are known to be in-order
Context
With #128 the sink arcs in an arc_file
was split in two: the ones given in-order and the ones given out-of-order. This reduces the number of elements involved in the sorting of sink arcs before calling adiar::reduce
. Yet, this also introduces an overhead when writing and reading from these files, since the two sink arc files need to be merged.
This seems to result in a 1% or 2% relative slowdown in performance. When we are have implemented many of the internal memory milestone issues, then these "few" percent performance decrease can be quite noticeable.
Tasks
We can reuse the idea from the rest of the internal memory milestone and change the type of the arc_stream
and arc_writer
at the start of the each algorithm.
- [ ] Template the
arc_stream
andarc_writer
classes with a booleansort_sinks
. Based on this boolean, they run the current merging/splitting logic or (at compile time) go-to one of the branches. - [ ] Use policies to derive the
sort_sinks
parameter in a top-down sweep. - [ ] At the start of reduce, check whether there are any out-of-order sinks that needs to be merged in. Call
__reduce
with the boolean moved into a template parameter.
Alternatively, we may also consider whether we can redesign the if-statement to favour the no-sorting case.
Additional Context
The following is a list whether an operation outputs edges in order ( :green_circle: ) or not ( :red_circle: )
-
BDD
- :green_circle:
bdd_apply
- :green_circle:
bdd_ite
- :red_circle:
bdd_restrict
- :red_circle:
bdd_exists
/bdd_forall
- :green_circle:
-
ZDD
- :red_circle:
zdd_binop
- :red_circle:
zdd_change
- :green_circle:
zdd_complement
- :green_circle:
zdd_expand
- :red_circle:
zdd_offset
- :red_circle:
zdd_onset
- :red_circle:
zdd_project
- :red_circle: