From 9882c8ab29fe623518257b17753928554445310f Mon Sep 17 00:00:00 2001
From: Leandro Lucarella <llucax@gmail.com>
Date: Sun, 14 Nov 2010 20:05:46 -0300
Subject: [PATCH] Add scripts to generate memory usage pattern charts

---
 mempat-run.sh |  46 +++++++++++++
 mempat-tsv.py | 156 ++++++++++++++++++++++++++++++++++++++++++
 mempat.py     | 186 ++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 388 insertions(+)
 create mode 100755 mempat-run.sh
 create mode 100755 mempat-tsv.py
 create mode 100755 mempat.py

diff --git a/mempat-run.sh b/mempat-run.sh
new file mode 100755
index 0000000..aea1c3e
--- /dev/null
+++ b/mempat-run.sh
@@ -0,0 +1,46 @@
+#!/bin/sh
+
+args_voronoi="-n 30000"
+args_sbtree="16"
+args_split="micro/bible.txt 2"
+args_em3d="-n 4000 -d 300 -i 74"
+args_bh="-b 4000"
+# Using up to -c 1048575 takes ~2.5s (and uses ~256KiB),
+# using -c 1048576 takes ~9s (and uses ~512KiB)
+args_tsp="-c 1000000"
+# Same as tsp but the limit is between 209000 and 2100000,
+# the memory usage and time doubles (from ~3s/~128KiB to ~6s/256KiB)
+args_bisort="-s 2000000"
+
+tango_files=`find ../tango/tango -name '*.d' -o -name '*.di' | grep -v invariant`
+args_dil="ddoc /tmp/tangodoc -hl --kandil -version=Tango -version=TangoDoc"
+args_dil="$args_dil -version=Posix -version=linux $tango_files"
+
+NAMES=${NAMES:-`echo ./micro/*.d | xargs -n1 sh -c 'basename $0 .d'` dil}
+
+gc=cdgc
+
+mkdir -p ./build/$gc/mempat
+
+make -srj4 micro-gc-build dil-gc-build
+for name in $NAMES
+do
+	prog="./build/$gc/bin/$name"
+	log="/tmp/$name.malloc.csv"
+	dst_txt="./build/$gc/mempat/$name.txt"
+	dst_tsv="./build/$gc/mempat/$name.tsv"
+	eval "args=\"\$args_$name\""
+	pa="$args"
+	test ${#args} -gt 40 &&
+		pa="`echo $args | cut -b1-40`..."
+	echo -n "   RUN     $name $pa"
+	D_GC_OPTS=malloc_stats_file=$log $prog $args > /dev/null
+	echo
+	echo -n "   MEMPAT  $dst_txt"
+	./mempat.py $log > $dst_txt
+	echo
+	echo -n "   MEMPAT  $dst_tsv"
+	./mempat-tsv.py $log > $dst_tsv
+	echo
+done
+
diff --git a/mempat-tsv.py b/mempat-tsv.py
new file mode 100755
index 0000000..030287e
--- /dev/null
+++ b/mempat-tsv.py
@@ -0,0 +1,156 @@
+#!/usr/bin/env python
+
+import sys
+import numpy
+
+SIZE = 3
+NO_SCAN = 6
+
+KiB = 2**10
+MiB = 2**20
+GiB = 2**30
+
+bytes_suffix = {
+	KiB: 'KiB',
+	MiB: 'MiB',
+	GiB: 'GiB',
+}
+
+# 16 32 ... 2048 4096
+bins = [1 << n for n in range(4, 13)]
+
+class Info:
+	pass
+
+def p(msg='', *args):
+	print msg % args
+
+def num(n):
+	return str(n)
+
+def percent(n, total):
+	return '%f' % (float(n) / total * 100)
+
+def bytes(n):
+	return str(n)
+
+f = file(sys.argv[1])
+f.readline() # ignore headers
+
+sizes = list()
+sizes_ti = list()
+size_freq = dict()
+size_freq_ti = dict()
+for l in f:
+	d = l.split(',')
+	size = int(d[SIZE])
+	no_scan = bool(int(d[NO_SCAN]))
+	if no_scan:
+		sizes.append(size)
+		size_freq[size] = size_freq.get(size, 0) + 1
+	else:
+		sizes_ti.append(size)
+		size_freq_ti[size] = size_freq_ti.get(size, 0) + 1
+
+scan_c = len(sizes_ti)
+no_scan_c = len(sizes)
+total_c = scan_c + no_scan_c
+
+scan_b = sum(sizes_ti)
+no_scan_b = sum(sizes)
+total_b = scan_b + no_scan_b
+
+p('Number of objects')
+p('Scanned\tNot scanned\tTotal')
+p('%s\t%s\t%s', num(scan_c), num(no_scan_c), num(total_c))
+p()
+
+p('Bytes')
+p('Scanned\tNot scanned\tTotal')
+p('%s\t%s\t%s', bytes(scan_b), bytes(no_scan_b), bytes(total_b))
+p()
+
+different_sizes_c = len(set(size_freq.keys()).union(size_freq_ti.keys()))
+p('Different object sizes')
+p(num(different_sizes_c))
+p()
+
+p('Objects requested')
+p('Bin Size\tNumber\tBytes')
+alloc_c = dict()
+n = sum((freq for size, freq in size_freq.iteritems() if size <= bins[0]))
+n += sum((freq for size, freq in size_freq_ti.iteritems() if size <= bins[0]))
+b = sum((size*freq for size, freq in size_freq.iteritems() if size <= bins[0]))
+b += sum((size*freq for size, freq in size_freq_ti.iteritems()
+		if size <= bins[0]))
+alloc_c[bins[0]] = n
+p('%s\t%s\t%s', bins[0], num(n), bytes(b))
+n_prev = n
+b_prev = b
+for bin in bins[1:]:
+	n = sum((freq for size, freq in size_freq.iteritems() if size <= bin))
+	n += sum((freq for size, freq in size_freq_ti.iteritems()
+			if size <= bin))
+	b = sum((size*freq for size, freq in size_freq.iteritems()
+			if size <= bin))
+	b += sum((size*freq for size, freq in size_freq_ti.iteritems()
+			if size <= bin))
+	nn = n - n_prev
+	bb = b - b_prev
+	alloc_c[bin] = nn
+	p('%s\t%s\t%s', bin, num(nn), bytes(bb))
+	n_prev = n
+	b_prev = b
+n = sum((freq for size, freq in size_freq.iteritems() if size > 4096))
+n += sum((freq for size, freq in size_freq_ti.iteritems() if size > 4096))
+b = sum((size*freq for size, freq in size_freq.iteritems() if size > 4096))
+b += sum((size*freq for size, freq in size_freq_ti.iteritems() if size > 4096))
+alloc_pplus_c = n
+p('>4096\t%s\t%s', num(n), bytes(b))
+p()
+
+def wasted_bin(start, end, extra=0):
+	w = 0
+	for i in range(start, end+1):
+		w += (end - i) * size_freq.get(i, 0)
+		if i <= (end - extra):
+			w += (end - i) * size_freq_ti.get(i, 0)
+		elif extra:
+			w += (2*end - i) * size_freq_ti.get(i, 0)
+	return w
+
+def wasted_pageplus(extra=0):
+	w = 0
+	for size, freq in size_freq.iteritems():
+		if size > 4096:
+			w += (size % 4096) * freq
+	for size, freq in size_freq_ti.iteritems():
+		size += extra
+		if size > 4096:
+			w += (size % 4096 + extra) * freq
+	return w
+
+def print_wasted(mode, extra=0):
+	wasted = dict()
+	wasted[bins[0]] = wasted_bin(1, bins[0], extra)
+	for bin in bins[1:]:
+		wasted[bin] = wasted_bin(bin/2 + 1, bin, extra)
+	wasted_pplus = wasted_pageplus()
+	wasted_total = sum((w for w in wasted.values())) + wasted_pplus
+	alloc_total = total_b + wasted_total
+	p('Real allocated bytes for mode %s', mode)
+	p('Totals')
+	p('Requested\tWasted\tTotal')
+	p('%s\t%s\t%s', bytes(total_b), bytes(wasted_total), bytes(alloc_total))
+	p('Bin\tWasted')
+	p('%s\t%s', bins[0], bytes(wasted[bins[0]]))
+	for bin in bins[1:]:
+		p('%s\t%s', bin, bytes(wasted[bin]))
+	p('>4096\t%s', bytes(wasted_pplus))
+	p()
+
+print_wasted('Conservative')
+print_wasted('Precise', 4)
+
+#print size_freq, size_freq_ti
+
diff --git a/mempat.py b/mempat.py
new file mode 100755
index 0000000..d4aacf7
--- /dev/null
+++ b/mempat.py
@@ -0,0 +1,186 @@
+#!/usr/bin/env python
+
+import sys
+import numpy
+
+SIZE = 3
+NO_SCAN = 6
+
+KiB = 2**10
+MiB = 2**20
+GiB = 2**30
+
+bytes_suffix = {
+	KiB: 'KiB',
+	MiB: 'MiB',
+	GiB: 'GiB',
+}
+
+# 16 32 ... 2048 4096
+bins = [1 << n for n in range(4, 13)]
+
+class Info:
+	pass
+
+def p(msg, *args):
+	print msg % args
+
+def num(n):
+	sn = str(n)
+	c = len(sn)
+	if c <= 3:
+		return sn
+	sep_pos = reversed(range(c-3, 0, -3))
+	return ','.join([sn[:c%3 or 3]] + [str(sn[i:i+3]) for i in sep_pos])
+
+def rm0(n):
+	s = '%.02f' % n
+	if s.endswith('00'):
+		return s[:-3]
+	if s.endswith('0'):
+		return s[:-1]
+	return s
+
+def percent(n, total):
+	return rm0(float(n) / total * 100) + '%'
+
+def bytes(n):
+	for mult in sorted(bytes_suffix.keys(), reverse=True):
+		if n >= mult:
+			return '%s bytes [%s%s]' % (num(n),
+					rm0(float(n) / mult),
+					bytes_suffix[mult])
+	return '%s bytes' % n
+
+f = file(sys.argv[1])
+f.readline() # ignore headers
+
+sizes = list()
+sizes_ti = list()
+size_freq = dict()
+size_freq_ti = dict()
+for l in f:
+	d = l.split(',')
+	size = int(d[SIZE])
+	no_scan = bool(int(d[NO_SCAN]))
+	if no_scan:
+		sizes.append(size)
+		size_freq[size] = size_freq.get(size, 0) + 1
+	else:
+		sizes_ti.append(size)
+		size_freq_ti[size] = size_freq_ti.get(size, 0) + 1
+
+scan_c = len(sizes_ti)
+no_scan_c = len(sizes)
+total_c = scan_c + no_scan_c
+
+scan_b = sum(sizes_ti)
+no_scan_b = sum(sizes)
+total_b = scan_b + no_scan_b
+
+p('Total requested: %s objecs, %s', num(total_c), bytes(total_b))
+p('\tScanned: %s (%s) objecs, %s (%s)', num(scan_c), percent(scan_c, total_c),
+		bytes(scan_b), percent(scan_b, total_b))
+p('\tNot scanned: %s (%s) objecs, %s (%s)', num(no_scan_c),
+		percent(no_scan_c, total_c), bytes(no_scan_b),
+		percent(no_scan_b, total_b))
+
+different_sizes_c = len(set(size_freq.keys()).union(size_freq_ti.keys()))
+p('Different object sizes: %s', num(different_sizes_c))
+
+p('Objects requested with a bin size of:')
+alloc_c = dict()
+n = sum((freq for size, freq in size_freq.iteritems() if size <= bins[0]))
+n += sum((freq for size, freq in size_freq_ti.iteritems() if size <= bins[0]))
+b = sum((size*freq for size, freq in size_freq.iteritems() if size <= bins[0]))
+b += sum((size*freq for size, freq in size_freq_ti.iteritems()
+		if size <= bins[0]))
+alloc_c[bins[0]] = n
+if n:
+	p('\t%s bytes: %s (%s) objects, %s (%s)', bins[0], num(n),
+			percent(n, total_c), bytes(b), percent(b, total_b))
+n_prev = n
+b_prev = b
+for bin in bins[1:]:
+	n = sum((freq for size, freq in size_freq.iteritems() if size <= bin))
+	n += sum((freq for size, freq in size_freq_ti.iteritems()
+			if size <= bin))
+	b = sum((size*freq for size, freq in size_freq.iteritems()
+			if size <= bin))
+	b += sum((size*freq for size, freq in size_freq_ti.iteritems()
+			if size <= bin))
+	nn = n - n_prev
+	bb = b - b_prev
+	alloc_c[bin] = nn
+	if nn:
+		p('\t%s bytes: %s (%s, %s cumulative) objects, '
+				'%s (%s, %s cumulative)', bin, num(nn),
+				percent(nn, total_c), percent(n, total_c),
+				bytes(bb), percent(bb, total_b),
+				percent(b, total_b))
+		n_prev = n
+		b_prev = b
+n = sum((freq for size, freq in size_freq.iteritems() if size > 4096))
+n += sum((freq for size, freq in size_freq_ti.iteritems() if size > 4096))
+b = sum((size*freq for size, freq in size_freq.iteritems() if size > 4096))
+b += sum((size*freq for size, freq in size_freq_ti.iteritems() if size > 4096))
+alloc_pplus_c = n
+if n:
+	p('\tmore than a page: %s (%s) objects, %s (%s)', num(n),
+			percent(n, total_c), bytes(b), percent(b, total_b))
+
+def wasted_bin(start, end, extra=0):
+	w = 0
+	for i in range(start, end+1):
+		w += (end - i) * size_freq.get(i, 0)
+		if i <= (end - extra):
+			w += (end - i) * size_freq_ti.get(i, 0)
+		elif extra:
+			w += (2*end - i) * size_freq_ti.get(i, 0)
+	return w
+
+def wasted_pageplus(extra=0):
+	w = 0
+	for size, freq in size_freq.iteritems():
+		if size > 4096:
+			w += (size % 4096) * freq
+	for size, freq in size_freq_ti.iteritems():
+		size += extra
+		if size > 4096:
+			w += (size % 4096 + extra) * freq
+	return w
+
+def print_wasted(mode, extra=0):
+	wasted = dict()
+	wasted[bins[0]] = wasted_bin(1, bins[0], extra)
+	for bin in bins[1:]:
+		wasted[bin] = wasted_bin(bin/2 + 1, bin, extra)
+	wasted_pplus = wasted_pageplus()
+	wasted_total = sum((w for w in wasted.values())) + wasted_pplus
+	alloc_total = wasted_total + total_b
+	p('%s mode:', mode)
+	p('\tTotal allocated: %s', bytes(alloc_total))
+	p('\tTotal wasted: %s, %s', bytes(wasted_total), percent(wasted_total,
+			alloc_total))
+	p('\tWasted due to objects that should use a bin of:')
+	if alloc_c[bins[0]]:
+		p('\t  %s bytes: %s (%s)', bins[0], bytes(wasted[bins[0]]),
+				percent(wasted[bins[0]], wasted_total))
+	w_cumulative = wasted[bins[0]]
+	for bin in bins[1:]:
+		if wasted[bin] == 0 and alloc_c[bin] == 0:
+			continue
+		w_cumulative += wasted[bin]
+		p('\t  %s bytes: %s (%s, %s cumulative)', bin,
+				bytes(wasted[bin]), percent(wasted[bin],
+				wasted_total), percent(w_cumulative,
+				wasted_total))
+	if alloc_pplus_c:
+		p('\t  more than a page: %s (%s)', bytes(wasted_pplus),
+				percent(wasted_pplus, wasted_total))
+
+print_wasted('Conservative')
+print_wasted('Precise', 4)
+
+#print size_freq, size_freq_ti
+
-- 
2.43.0