[StGit PATCH 1/5] Add some performance testing scripts

["Karl Hasselström" <kha@treskal.com>]

find_patchbomb.py: Given a git repo, finds the longest linear sequence
  of commits. Useful for testing StGit on a real repository.

setup.sh: Creates two test repositories, one synthetic and one based
  on the Linux kernel repo, with strategically placed tags.

create_synthetic_repo.py: Helper script for setup.sh; it produces
  output that is to be fed to git fast-import.

perftest.py: Runs one of a (small) number of hard-coded performance
  tests against a copy of one of the repos created by setup.sh. The
  initial testcases all involve uncommitting a large number of patches
  and then rebasing them.

Signed-off-by: Karl Hasselström <kha@treskal.com>

---

 perf/.gitignore               |    2 +
 perf/create_synthetic_repo.py |   61 ++++++++++++++++++++++++++++
 perf/find_patchbomb.py        |   31 ++++++++++++++
 perf/perftest.py              |   88 +++++++++++++++++++++++++++++++++++++++++
 perf/setup.sh                 |   52 ++++++++++++++++++++++++
 5 files changed, 234 insertions(+), 0 deletions(-)
 create mode 100644 perf/.gitignore
 create mode 100644 perf/create_synthetic_repo.py
 create mode 100644 perf/find_patchbomb.py
 create mode 100644 perf/perftest.py
 create mode 100644 perf/setup.sh


diff --git a/perf/.gitignore b/perf/.gitignore
new file mode 100644
index 0000000..dfae110
--- /dev/null
+++ b/perf/.gitignore
@@ -0,0 +1,2 @@
+/*.orig
+/*.trash
diff --git a/perf/create_synthetic_repo.py b/perf/create_synthetic_repo.py
new file mode 100644
index 0000000..4d6ef6b
--- /dev/null
+++ b/perf/create_synthetic_repo.py
@@ -0,0 +1,61 @@
+next_mark = 1
+def get_mark():
+    global next_mark
+    next_mark += 1
+    return (next_mark - 1)
+
+def write_data(s):
+    print 'data %d' % len(s)
+    print s
+
+def write_blob(s):
+    print 'blob'
+    m = get_mark()
+    print 'mark :%d' % m
+    write_data(s)
+    return m
+
+def write_commit(branch, files, msg, parent = None):
+    print 'commit %s' % branch
+    m = get_mark()
+    print 'mark :%d' % m
+    auth = 'X Ample <xa@example.com> %d +0000' % (1000000000 + m)
+    print 'author %s' % auth
+    print 'committer %s' % auth
+    write_data(msg)
+    if parent != None:
+        print 'from :%d' % parent
+    for fn, fm in sorted(files.iteritems()):
+        print 'M 100644 :%d %s' % (fm, fn)
+    return m
+
+def set_ref(ref, mark):
+    print 'reset %s' % ref
+    print 'from :%d' % mark
+
+def stdblob(fn):
+    return ''.join('%d %s\n' % (x, fn) for x in xrange(10))
+
+def iter_paths():
+    for i in xrange(32):
+        for j in xrange(32):
+            for k in xrange(32):
+                yield '%02d/%02d/%02d' % (i, j, k)
+
+def setup():
+    def t(name): return 'refs/tags/%s' % name
+    files = dict((fn, write_blob(stdblob(fn))) for fn in iter_paths())
+    initial = write_commit(t('bomb-base'), files, 'Initial commit')
+    set_ref(t('bomb-top'), initial)
+    for fn in iter_paths():
+        write_commit(t('bomb-top'),
+                     { fn: write_blob(stdblob(fn) + 'Last line\n') },
+                     'Add last line to %s' % fn)
+    write_commit(t('add-file'), { 'woo-hoo.txt': write_blob('woo-hoo\n') },
+                 'Add a new file', parent = initial)
+    files = dict((fn, write_blob('First line\n' + stdblob(fn)))
+                 for fn in iter_paths())
+    write_commit(t('modify-all'), files, 'Add first line to all files',
+                 parent = initial)
+
+setup()
diff --git a/perf/find_patchbomb.py b/perf/find_patchbomb.py
new file mode 100644
index 0000000..69a78c7
--- /dev/null
+++ b/perf/find_patchbomb.py
@@ -0,0 +1,31 @@
+# Feed this with git rev-list HEAD --parents
+
+import sys
+
+parents = {}
+for line in sys.stdin.readlines():
+    commits = line.split()
+    parents[commits[0]] = commits[1:]
+
+sequence_num = {}
+stack = []
+for commit in parents.keys():
+    stack.append(commit)
+    while stack:
+        c = stack.pop()
+        if c in sequence_num:
+            continue
+        ps = parents[c]
+        if len(ps) == 1:
+            p = ps[0]
+            if p in sequence_num:
+                sequence_num[c] = 1 + sequence_num[p]
+            else:
+                stack.append(c)
+                stack.append(p)
+        else:
+            sequence_num[c] = 0
+
+(num, commit) = max((num, commit) for (commit, num)
+                    in sequence_num.iteritems())
+print '%s is a sequence of %d patches' % (commit, num)
diff --git a/perf/perftest.py b/perf/perftest.py
new file mode 100644
index 0000000..7072772
--- /dev/null
+++ b/perf/perftest.py
@@ -0,0 +1,88 @@
+import datetime, subprocess, sys
+
+def duration(t1, t2):
+    d = t2 - t1
+    return 86400*d.days + d.seconds + 1e-6*d.microseconds
+
+class Run(object):
+    def __init__(self):
+        self.__cwd = None
+        self.__log = []
+    def __call__(self, *cmd, **args):
+        kwargs = { 'cwd': self.__cwd }
+        if args.get('capture_stdout', False):
+            kwargs['stdout'] = subprocess.PIPE
+        start = datetime.datetime.now()
+        p = subprocess.Popen(cmd, **kwargs)
+        (out, err) = p.communicate()
+        stop = datetime.datetime.now()
+        self.__log.append((cmd, duration(start, stop)))
+        return out
+    def cd(self, dir):
+        self.__cwd = dir
+    def summary(self):
+        def pcmd(c): return ' '.join(c)
+        def ptime(t): return '%.3f' % t
+        (cs, times) = zip(*self.__log)
+        ttime = sum(times)
+        cl = max(len(pcmd(c)) for c in cs)
+        tl = max(len(ptime(t)) for t in list(times) + [ttime])
+        for (c, t) in self.__log:
+            print '%*s  %*s' % (tl, ptime(t), -cl, pcmd(c))
+        print '%*s' % (tl, ptime(ttime))
+
+perftests = {}
+perftestdesc = {}
+def perftest(desc, name = None):
+    def decorator(f):
+        def g():
+            r = Run()
+            f(r)
+            r.summary()
+        perftests[name or f.__name__] = g
+        perftestdesc[name or f.__name__] = desc
+        return g
+    return decorator
+
+def copy_testdir(dir):
+    tmp = dir + '.trash'
+    r = Run()
+    r('rsync', '-a', '--delete', dir + '.orig/', tmp)
+    return tmp
+
+def new_rebase(r, ref):
+    top = r('stg', 'top', capture_stdout = True)
+    r('stg', 'pop', '-a')
+    r('git', 'reset', '--hard', ref)
+    r('stg', 'goto', top.strip())
+
+def old_rebase(r, ref):
+    r('stg', 'rebase', ref)
+
+def def_rebasetest(rebase, dir, tag):
+    @perftest('%s rebase onto %s in %s' % (rebase, tag, dir),
+              'rebase-%srebase-%s-%s' % (rebase, tag, dir))
+    def rebasetest(r):
+        r.cd(copy_testdir(dir))
+        r('stg', 'init')
+        if dir == 'synt':
+            r('stg', 'uncommit', '-n', '500')
+        else:
+            r('stg', 'uncommit', '-x', '-t', 'bomb-base')
+        if rebase == 'new':
+            new_rebase(r, tag)
+        else:
+            old_rebase(r, tag)
+for rebase in ['old', 'new']:
+    for (dir, tag) in [('synt', 'add-file'),
+                       ('synt', 'modify-all'),
+                       ('linux', 'add-file')]:
+        def_rebasetest(rebase, dir, tag)
+
+args = sys.argv[1:]
+if len(args) == 0:
+    for (fun, desc) in sorted(perftestdesc.iteritems()):
+        print '%s: %s' % (fun, desc)
+else:
+    for test in args:
+        perftests[test]()
diff --git a/perf/setup.sh b/perf/setup.sh
new file mode 100644
index 0000000..b92ddfc
--- /dev/null
+++ b/perf/setup.sh
@@ -0,0 +1,52 @@
+krepo='git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6.git'
+
+get_linux() {
+    rm -rf linux.orig
+    git clone "$krepo" linux.orig
+}
+
+mod_linux() {
+    # Tag the top and base of a very long linear sequence of commits.
+    git tag bomb-top 85040bcb4643cba578839e953f25e2d1965d83d0
+    git tag bomb-base bomb-top~1470
+
+    # Add a file at the base of the linear sequence.
+    git checkout bomb-base
+    echo "woo-hoo" > woo-hoo.txt
+    git add woo-hoo.txt
+    git commit -m "Add a file"
+    git tag add-file
+
+    # Clean up and go to start position.
+    git gc
+    git update-ref refs/heads/master bomb-top
+    git checkout master
+}
+
+setup_linux () {
+    get_linux
+    ( cd linux.orig && mod_linux )
+}
+
+create_empty () {
+    dir="$1"
+    rm -rf $dir
+    mkdir $dir
+    ( cd $dir && git init )
+}
+
+fill_synthetic () {
+    python ../create_synthetic_repo.py | git fast-import
+    git gc --aggressive
+    git update-ref refs/heads/master bomb-top
+    git checkout master
+}
+
+setup_synthetic()
+{
+    create_empty synt.orig
+    ( cd synt.orig && fill_synthetic )
+}
+
+setup_linux
+setup_synthetic