Shortcut merge-conditional at compile-time when sink-arcs are known to be in-order

[SSoelvsten]

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 and arc_writer classes with a boolean sort_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
• 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