Author: njn
Date: 2007-10-17 05:36:39 +0100 (Wed, 17 Oct 2007)
New Revision: 7011
Log:
Reduce the number of calls to ssort by doing them at print time, rather than
duplication time.
Added:
branches/MASSIF2/massif/tests/insig.c
branches/MASSIF2/massif/tests/insig.post.exp
branches/MASSIF2/massif/tests/insig.stderr.exp
branches/MASSIF2/massif/tests/insig.vgtest
Modified:
branches/MASSIF2/massif/ms_main.c
branches/MASSIF2/massif/tests/Makefile.am
branches/MASSIF2/massif/tests/realloc.post.exp
Modified: branches/MASSIF2/massif/ms_main.c
===================================================================
--- branches/MASSIF2/massif/ms_main.c 2007-10-17 03:31:32 UTC (rev 7010)
+++ branches/MASSIF2/massif/ms_main.c 2007-10-17 04:36:39 UTC (rev 7011)
@@ -74,12 +74,18 @@
// konqueror 3:45 real 3:35 user
//
// Moved main-or-below-main filtering to the end, avoiding *many* calls to
-// VG_(get_fnname):
+// VG_(get_fnname) (r7010):
// heap 0.62s ma:12.4s (20.0x, -----)
// tinycc 0.45s ma: 5.1s (11.4x, -----)
// many-xpts 0.09s ma: 2.1s (23.8x, -----)
// konqueror 0:46 real 0:36 user
//
+// Instead of sorting XPt children at duplication time, sort them at print
+// time (ie. many fewer sorts required) (r7011):
+// heap 0.36s ma:12.3s (34.1x, -----)
+// tinycc 0.46s ma: 4.8s (10.3x, -----)
+// many-xpts 0.09s ma: 2.0s (22.3x, -----)
+// konqueror 0:42 real 0:34 user
//
//
// Todo:
@@ -617,13 +623,13 @@
}
// Reverse comparison for a reverse sort -- biggest to smallest.
-static Int XPt_revcmp_szB(void* n1, void* n2)
+static Int SXPt_revcmp_szB(void* n1, void* n2)
{
- XPt* xpt1 = *(XPt**)n1;
- XPt* xpt2 = *(XPt**)n2;
- return ( xpt1->szB < xpt2->szB ? 1
- : xpt1->szB > xpt2->szB ? -1
- : 0);
+ SXPt* sxpt1 = *(SXPt**)n1;
+ SXPt* sxpt2 = *(SXPt**)n2;
+ return ( sxpt1->szB < sxpt2->szB ? 1
+ : sxpt1->szB > sxpt2->szB ? -1
+ : 0);
}
// Does the xpt account for >= 1% (or so) of total memory used?
@@ -652,9 +658,6 @@
SizeT insig_children_szB;
SXPt* sxpt;
- // Sort XPt's children by szB (reverse order: biggest to smallest).
- VG_(ssort)(xpt->children, xpt->n_children, sizeof(XPt*), XPt_revcmp_szB);
-
// Number of XPt children Action for SXPT
// ------------------ ---------------
// 0 sig, 0 insig alloc 0 children
@@ -664,10 +667,10 @@
// How many children are significant? And do we need an aggregate SXPt?
n_sig_children = 0;
- while (n_sig_children < xpt->n_children &&
- is_significant_XPt(xpt->children[n_sig_children], total_szB))
- {
- n_sig_children++;
+ for (i = 0; i < xpt->n_children; i++) {
+ if (is_significant_XPt(xpt->children[i], total_szB)) {
+ n_sig_children++;
+ }
}
n_insig_children = xpt->n_children - n_sig_children;
n_child_sxpts = n_sig_children + ( n_insig_children > 0 ? 1 : 0 );
@@ -682,13 +685,17 @@
// Create the SXPt's children.
if (n_child_sxpts > 0) {
+ Int j;
SizeT sig_children_szB = 0;
sxpt->Sig.children = VG_(malloc)(n_child_sxpts * sizeof(SXPt*));
// Duplicate the significant children.
- for (i = 0; i < n_sig_children; i++) {
- sxpt->Sig.children[i] = dup_XTree(xpt->children[i], total_szB);
- sig_children_szB += sxpt->Sig.children[i]->szB;
+ j = 0;
+ for (i = 0; i < xpt->n_children; i++) {
+ if (is_significant_XPt(xpt->children[i], total_szB)) {
+ sxpt->Sig.children[j++] = dup_XTree(xpt->children[i], total_szB);
+ sig_children_szB += xpt->children[i]->szB;
+ }
}
// Create the SXPt for the insignificant children, if any, and put it
@@ -1795,7 +1802,7 @@
SizeT snapshot_heap_szB, SizeT snapshot_total_szB)
{
#define BUF_LEN 1024
- Int i;
+ Int i, n_insig_children_sxpts;
Char* perc;
Char ip_desc_array[BUF_LEN];
Char* ip_desc = ip_desc_array;
@@ -1835,20 +1842,24 @@
depth_str[depth+0] = ' ';
depth_str[depth+1] = '\0';
+ // Sort SXPt's children by szB (reverse order: biggest to smallest).
+ // Nb: we sort them here, rather than earlier (eg. in dup_XTree), for
+ // two reasons. First, if we do it during dup_XTree, it can get
+ // expensive (eg. 15% of execution time for konqueror
+ // startup/shutdown). Second, this way we get the Insig SXPt (if one
+ // is present) in its sorted position, not at the end.
+ VG_(ssort)(sxpt->Sig.children, sxpt->Sig.n_children, sizeof(SXPt*),
+ SXPt_revcmp_szB);
+
// Print the SXPt's children. They should already be in sorted order.
+ n_insig_children_sxpts = 0;
for (i = 0; i < sxpt->Sig.n_children; i++) {
pred = child;
child = sxpt->Sig.children[i];
- // Only the last child can be an Insig SXPt.
- if (i < sxpt->Sig.n_children-1)
- tl_assert(SigSXPt == child->tag);
+ if (InsigSXPt == child->tag)
+ n_insig_children_sxpts++;
- // Sortedness check: if this child is a normal SXPt, check it's not
- // bigger than its predecessor.
- if (pred && SigSXPt == child->tag)
- tl_assert(child->szB <= pred->szB);
-
// Ok, print the child.
pp_snapshot_SXPt(fd, child, depth+1, depth_str, depth_str_len,
snapshot_heap_szB, snapshot_total_szB);
@@ -1857,6 +1868,8 @@
depth_str[depth+0] = '\0';
depth_str[depth+1] = '\0';
}
+ // There should be 0 or 1 Insig children SXPts.
+ tl_assert(n_insig_children_sxpts <= 1);
break;
case InsigSXPt: {
Modified: branches/MASSIF2/massif/tests/Makefile.am
===================================================================
--- branches/MASSIF2/massif/tests/Makefile.am 2007-10-17 03:31:32 UTC (rev
7010)
+++ branches/MASSIF2/massif/tests/Makefile.am 2007-10-17 04:36:39 UTC (rev
7011)
@@ -8,6 +8,7 @@
alloc-fns-A.post.exp alloc-fns-A.stderr.exp alloc-fns-A.vgtest \
alloc-fns-B.post.exp alloc-fns-B.stderr.exp alloc-fns-B.vgtest \
basic.post.exp basic.stderr.exp basic.vgtest \
+ insig.post.exp insig.stderr.exp insig.vgtest \
big-alloc.post.exp big-alloc.stderr.exp big-alloc.vgtest \
deep-A.post.exp deep-A.stderr.exp deep-A.vgtest \
deep-B.post.exp deep-B.stderr.exp deep-B.vgtest \
@@ -48,6 +49,7 @@
custom_alloc \
deep \
ignoring \
+ insig \
long-time \
null \
one \
Added: branches/MASSIF2/massif/tests/insig.c
===================================================================
--- branches/MASSIF2/massif/tests/insig.c (rev 0)
+++ branches/MASSIF2/massif/tests/insig.c 2007-10-17 04:36:39 UTC (rev
7011)
@@ -0,0 +1,34 @@
+#include <stdlib.h>
+
+// In this test, the size of the insignificant nodes is greater than the
+// size of two of the significant nodes. This is quite common in big
+// programs, but not so common in small tests, so we test for it here.
+int main(void)
+{
+ malloc(1000);
+ malloc(15);
+ malloc(12);
+ malloc(1);
+ malloc(1);
+ malloc(1);
+ malloc(1);
+ malloc(1);
+ malloc(1);
+ malloc(1);
+ malloc(1);
+ malloc(1);
+ malloc(1);
+ malloc(1);
+ malloc(1);
+ malloc(1);
+ malloc(1);
+ malloc(1);
+ malloc(1);
+ malloc(1);
+ malloc(1);
+ malloc(1);
+ malloc(1);
+
+
+ return 0;
+}
Added: branches/MASSIF2/massif/tests/insig.post.exp
===================================================================
--- branches/MASSIF2/massif/tests/insig.post.exp
(rev 0)
+++ branches/MASSIF2/massif/tests/insig.post.exp 2007-10-17 04:36:39 UTC
(rev 7011)
@@ -0,0 +1,84 @@
+--------------------------------------------------------------------------------
+Command: ./insig
+Massif arguments: --stacks=no --time-unit=B
+ms_print arguments: massif.out
+--------------------------------------------------------------------------------
+
+
+ KB
+1.202^ .:
+ | ..:@::
+ | ..::::@::
+ | .:::@::::@::
+ | : ::::@::::@::
+ | : ::::@::::@::
+ | : ::::@::::@::
+ | : ::::@::::@::
+ | : ::::@::::@::
+ | : ::::@::::@::
+ | : ::::@::::@::
+ | : ::::@::::@::
+ | : ::::@::::@::
+ | : ::::@::::@::
+ | : ::::@::::@::
+ | : ::::@::::@::
+ | : ::::@::::@::
+ | : ::::@::::@::
+ | : ::::@::::@::
+ | : ::::@::::@::
+ 0 [EMAIL PROTECTED]@->KB
+ 0 1.202
+
+Number of snapshots: 24
+ Detailed snapshots: [9, 19]
+--------------------------------------------------------------------------------
+ n time(B) total(B) useful-heap(B) admin-heap(B) stacks(B)
+--------------------------------------------------------------------------------
+ 0 0 0 0 0 0
+ 1 1,008 1,008 1,000 8 0
+ 2 1,031 1,031 1,015 16 0
+ 3 1,051 1,051 1,027 24 0
+ 4 1,060 1,060 1,028 32 0
+ 5 1,069 1,069 1,029 40 0
+ 6 1,078 1,078 1,030 48 0
+ 7 1,087 1,087 1,031 56 0
+ 8 1,096 1,096 1,032 64 0
+ 9 1,105 1,105 1,033 72 0
+93.48% (1033B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
+->90.50% (1000B) 0x80483A4: main (insig.c:8)
+|
+->01.36% (15B) 0x80483B1: main (insig.c:9)
+|
+->01.09% (12B) 0x80483BE: main (insig.c:10)
+|
+->00.54% (6B) in 1+ places, all below ms_print's threshold (01.00%)
+
+--------------------------------------------------------------------------------
+ n time(B) total(B) useful-heap(B) admin-heap(B) stacks(B)
+--------------------------------------------------------------------------------
+ 10 1,114 1,114 1,034 80 0
+ 11 1,123 1,123 1,035 88 0
+ 12 1,132 1,132 1,036 96 0
+ 13 1,141 1,141 1,037 104 0
+ 14 1,150 1,150 1,038 112 0
+ 15 1,159 1,159 1,039 120 0
+ 16 1,168 1,168 1,040 128 0
+ 17 1,177 1,177 1,041 136 0
+ 18 1,186 1,186 1,042 144 0
+ 19 1,195 1,195 1,043 152 0
+87.28% (1043B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
+->83.68% (1000B) 0x80483A4: main (insig.c:8)
+|
+->01.34% (16B) in 16 places, all below massif's threshold (01.00%)
+|
+->01.26% (15B) 0x80483B1: main (insig.c:9)
+|
+->01.00% (12B) 0x80483BE: main (insig.c:10)
+
+--------------------------------------------------------------------------------
+ n time(B) total(B) useful-heap(B) admin-heap(B) stacks(B)
+--------------------------------------------------------------------------------
+ 20 1,204 1,204 1,044 160 0
+ 21 1,213 1,213 1,045 168 0
+ 22 1,222 1,222 1,046 176 0
+ 23 1,231 1,231 1,047 184 0
Added: branches/MASSIF2/massif/tests/insig.stderr.exp
===================================================================
--- branches/MASSIF2/massif/tests/insig.stderr.exp
(rev 0)
+++ branches/MASSIF2/massif/tests/insig.stderr.exp 2007-10-17 04:36:39 UTC
(rev 7011)
@@ -0,0 +1,2 @@
+
+
Added: branches/MASSIF2/massif/tests/insig.vgtest
===================================================================
--- branches/MASSIF2/massif/tests/insig.vgtest (rev 0)
+++ branches/MASSIF2/massif/tests/insig.vgtest 2007-10-17 04:36:39 UTC (rev
7011)
@@ -0,0 +1,4 @@
+prog: insig
+vgopts: --stacks=no --time-unit=B
+post: perl ../../massif/ms_print massif.out
+cleanup: rm massif.out
Modified: branches/MASSIF2/massif/tests/realloc.post.exp
===================================================================
--- branches/MASSIF2/massif/tests/realloc.post.exp 2007-10-17 03:31:32 UTC
(rev 7010)
+++ branches/MASSIF2/massif/tests/realloc.post.exp 2007-10-17 04:36:39 UTC
(rev 7011)
@@ -52,10 +52,10 @@
100.00% (150B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->100.00% (150B) 0x80483E3: main (realloc.c:12)
|
+->00.00% (0B) 0x80483A7: main (realloc.c:5)
+|
->00.00% (0B) 0x80483BA: main (realloc.c:8)
|
-->00.00% (0B) 0x80483A7: main (realloc.c:5)
-|
->00.00% (0B) 0x80483CD: main (realloc.c:10)
--------------------------------------------------------------------------------
-------------------------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc.
Still grepping through log files to find problems? Stop.
Now Search log events and configuration files using AJAX and a browser.
Download your FREE copy of Splunk now >> http://get.splunk.com/
_______________________________________________
Valgrind-developers mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/valgrind-developers
