tree 247c2e6fe2d5dcd24e44b32afbf7fba58559dcf4
parent 433f638d04b65dbccbd1f59d468ed00bc6b7ae2f
author Matthias Boehm <mboehm7@gmail.com> 1593554744 +0200
committer Matthias Boehm <mboehm7@gmail.com> 1593554884 +0200

[SYSTEMDS-418] Performance lineage tracing and reuse probing

This patch makes the following performance improvements in the context
of basic lineage tracing and lineage-based reuse probing:

1) Avoid string handling: Materialize the flag if a createvar
instruction has a persistent-read prefix in the name, which avoid
unnecessary string comparisons for ALL createvar instructions, so almost
30% of all instructions.

2) Apply the existing constant folding rewrite not just during static
rewrites but now also as a cleanup rewrite in order to remove remaining
constant expressions (introduced by rewrites) inside loops. This has
especially large impact in lineage because constructing the lineage item
is more expensive than the entire scalar operation.

3) Leverage the materialized hash code in lineage items as early-out
condition in the recursive equals check of lineage DAGs. This is
especially useful where all lineage DAGs have the same repreated
structure (e.g., from unrolled iterations) but a different input. The
equals would go all the way to the first differences, while the
comparison of hash codes (aggregates over all inputs) very likely differ
earlier.

On a mini-batch scenario of 250,000 iterations batch size 8, and 40
operations per iteration, the runtime w/o lineage was 65.6s, and the
changes (1) and (2) improved the runtime with lineage tracing from 76.5s
to 72.6s. Furthermore, we also seen some improvements for reuse probing
in this scenario, but this requires but work too.