[committed] Use incoming_tail for superset/subset in create_import_tree

[committed] Use incoming_tail for superset/subset in create_import_tree

[Tom de Vries]

Hi,

Use the new incoming_tail field of struct import_cu to speed up the
superset/subset test in create_import_tree.

[ The baseline for the measurements is the commit before the incoming_tail
field addition.  The incoming_tail commit is separate from this one, in order
to allow easy identification of performance regressions specifically related
to that commit.  But we measure here the performance of the two commits
combined. ]

This reduces execution time for vmlinux with ~38%:
...
real:  mean:  26802.80 100.00%  stddev:  582.58
       mean:  16590.60  61.90%  stddev:   92.71
user:  mean:  26271.80 100.00%  stddev:  207.98
       mean:  16278.80  61.96%  stddev:   86.84
sys:   mean:    392.00 100.00%  stddev:  177.20
       mean:    310.40  79.18%  stddev:   28.09
...

This at the cost of 0.01% more memory:
...
$ time.sh ./dwz.1 vmlinux.debug -lnone -Lnone
maxmem: 2163948
real: 26.96
user: 26.60
system: 0.35
$ time.sh ./dwz.2 vmlinux.debug -lnone -Lnone
maxmem: 2164120
real: 16.63
user: 16.30
system: 0.32
...

Committed to trunk.

Thanks,
- Tom

Use incoming_tail for superset/subset in create_import_tree

2019-12-17  Tom de Vries  <tdevries@suse.de>

	PR dwz/25276
	* dwz.c (create_import_tree): Use incoming_tail to speed up
	calculation of maybe_superset and maybe_subset.

---
 dwz.c | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)

diff --git a/dwz.c b/dwz.c
index 82b7d83..48833bc 100644
--- a/dwz.c
+++ b/dwz.c
@@ -7318,6 +7318,26 @@ create_import_tree (void)
 	      maybe_subset = (e1 == ipu->incoming
 			      && ipu->incoming_count <= ipu2->incoming_count);
 	      maybe_superset = ipu->incoming_count >= ipu2->incoming_count;
+	      if (maybe_superset)
+		{
+		  /* If the referrer nodes of ipu are a superset of the
+		     referrer nodes of ipu2, then ipu's last referrer node
+		     should have index larger or equal to the last referrer
+		     node of ipu2.  */
+		  maybe_superset
+		    = (ipu->incoming_tail->icu->idx
+		       >= ipu2->incoming_tail->icu->idx);
+		}
+	      if (maybe_subset)
+		{
+		  /* If the referrer nodes of ipu are a subset of the
+		     referrer nodes of ipu2, then ipu's last referrer node
+		     should have index smaller or equal to the last referrer
+		     node of ipu2.  */
+		  maybe_subset
+		    = (ipu->incoming_tail->icu->idx
+		       <= ipu2->incoming_tail->icu->idx);
+		}
 	      e3 = e1;
 	      e4 = ipu2->incoming;
 	      intersection = 0;