[PATCH/RFC/GSoC 00/17] A barebones git-rebase in C

Hi all,

Last year I rewrote git-am from shell script to C. This succeeded in speeding up a non-interactive git-rebase by 6-7x[1], which is really handly when rebasing multiple topic branches.

[1] http://thread.gmane.org/gmane.comp.version-control.git/271967

However, it turns out that when working on a topic branch, I frequently use interactive rebase instead to edit and squash commits. Unfortunately, as git-rebase--interactive.sh is still a shell script, it is a bit slower (e.g. taking a few seconds longer compared to non-interactive rebase when rebasing big topic branches).

The situation is much worse on Windows, as from the invocation of git rebase -i, it takes a few seconds before the editor even pops up, and the actual rebase proceeds at a snails pace, taking around 3 minutes for a 50-patch series, which is a huge deal-breaker since my workflow depends on frequent commits and squashes.

As such, this year I would like to apply for GSoC to work on a rewrite of git-rebase to C. It is slightly hefty, as there are three backends (am, merge and interactive), along with the git-rebase.sh script.

To get a gauge of how much code is needed for the rewrite, I explored rewriting the scripts into C, and then extracted some bits out and polished them a bit to make a barebones git-rebase in C, creating this patch series:

[01/17] perf: introduce performance tests for git-rebase

A simple performance test for the three rebase backends so we can compare this C version and the shell version below.

[02/17] sha1_name: implement get_oid() and friends [03/17] builtin-rebase: implement skeletal builtin rebase [04/17] builtin-rebase: parse rebase arguments into a common rebase_options struct [05/17] rebase-options: implement rebase_options_load() and rebase_options_save()

The three rebase backends (am, merge, interactive) have vastly different capabilities, so I did not try to shoehorn them into the same interface. However, they do share a few common options and functionality, so I introduced the common rebase-common.c library and rebase_options struct.

In the above patches we implement the essential arguments for a rebase: the upstream, branch_name and --onto <newbase>.

[06/17] rebase-am: introduce am backend for builtin rebase

This patch implements a barebones rebase-am backend.

[07/17] rebase-common: implement refresh_and_write_cache() [08/17] rebase-common: let refresh_and_write_cache() take a flags argument [09/17] rebase-common: implement cache_has_unstaged_changes() [10/17] rebase-common: implement cache_has_uncommitted_changes() [11/17] rebase-merge: introduce merge backend for builtin rebase

These patches implement a barebones rebase-merge backend.

[12/17] rebase-todo: introduce rebase_todo_item [13/17] rebase-todo: introduce rebase_todo_list [14/17] status: use rebase_todo_list [15/17] wrapper: implement append_file() [16/17] editor: implement git_sequence_editor() and launch_sequence_editor() [17/17] rebase-interactive: introduce interactive backend for builtin rebase

And these patches implement a barebones rebase-interactive backend.

With these patches the performance numbers when rebasing 50 commits on the git.git repository are, on Linux,

Before patch series:

Test this tree -------------------------------------------------- 3400.2: rebase --onto master^ 1.10(0.84+0.06) 3402.2: rebase -m --onto master^ 2.38(1.38+0.13) 3404.2: rebase -i --onto master^ 3.11(1.37+0.27)

After patch series:

Test this tree -------------------------------------------------- 3400.2: rebase --onto master^ 0.74(0.51+0.08) 3402.2: rebase -m --onto master^ 1.72(1.26+0.17) 3404.2: rebase -i --onto master^ 1.74(1.20+0.18)

And on Windows,

Before patch series:

Test this tree ---------------------------------------------------- 3400.2: rebase --onto master^ 10.90(0.06+0.47) 3402.2: rebase -m --onto master^ 86.87(0.04+0.47) 3404.2: rebase -i --onto master^ 191.65(0.09+0.44)

After patch series:

Test this tree --------------------------------------------------- 3400.2: rebase --onto master^ 6.45(0.13+0.40) 3402.2: rebase -m --onto master^ 12.32(0.13+0.40) 3404.2: rebase -i --onto master^ 14.16(0.15+0.40)

(Thanks to the git-am rewrite, non-interactive rebase on Windows is already relatively fast ;-) )

So, we have around a 1.4x-1.8x speedup for Linux users, and a 1.7x-13x speedup for Windows users. The annoying long delay before the interactive editor is launched on Windows is gotten rid of, which I'm very happy about :-)

On the code side, we do get some nice things with a rewrite to C. For example, we get the rebase-todo library for parsing and writing git-rebase-todo files, which means that wt-status.c and rebase-interactive.c can share the same parsing code. Although not in this patch series, rebase-interactive.c can also now share the same author-script parsing and writing code from builtin/am.c as well.

Regards, Paul

Paul Tan (17):
  perf: introduce performance tests for git-rebase
  sha1_name: implement get_oid() and friends
  builtin-rebase: implement skeletal builtin rebase
  builtin-rebase: parse rebase arguments into a common rebase_options
    struct
  rebase-options: implement rebase_options_load() and
    rebase_options_save()
  rebase-am: introduce am backend for builtin rebase
  rebase-common: implement refresh_and_write_cache()
  rebase-common: let refresh_and_write_cache() take a flags argument
  rebase-common: implement cache_has_unstaged_changes()
  rebase-common: implement cache_has_uncommitted_changes()
  rebase-merge: introduce merge backend for builtin rebase
  rebase-todo: introduce rebase_todo_item
  rebase-todo: introduce rebase_todo_list
  status: use rebase_todo_list
  wrapper: implement append_file()
  editor: implement git_sequence_editor() and launch_sequence_editor()
  rebase-interactive: introduce interactive backend for builtin rebase

 Makefile                           |  10 +-
 builtin.h                          |   1 +
 builtin/am.c                       |  16 +-
 builtin/pull.c                     |  41 +---
 builtin/rebase.c                   | 264 ++++++++++++++++++++++++++
 cache.h                            |   8 +
 editor.c                           |  27 ++-
 git.c                              |   1 +
 rebase-am.c                        | 110 +++++++++++
 rebase-am.h                        |  22 +++
 rebase-common.c                    | 220 ++++++++++++++++++++++
 rebase-common.h                    |  48 +++++
 rebase-interactive.c               | 375 +++++++++++++++++++++++++++++++++++++
 rebase-interactive.h               |  33 ++++
 rebase-merge.c                     | 256 +++++++++++++++++++++++++
 rebase-merge.h                     |  28 +++
 rebase-todo.c                      | 251 +++++++++++++++++++++++++
 rebase-todo.h                      |  55 ++++++
 sha1_name.c                        |  30 +++
 strbuf.h                           |   1 +
 t/perf/p3400-rebase.sh             |  25 +++
 t/perf/p3402-rebase-merge.sh       |  25 +++
 t/perf/p3404-rebase-interactive.sh |  26 +++
 wrapper.c                          |  23 +++
 wt-status.c                        | 100 +++-------
 25 files changed, 1863 insertions(+), 133 deletions(-)
 create mode 100644 builtin/rebase.c
 create mode 100644 rebase-am.c
 create mode 100644 rebase-am.h
 create mode 100644 rebase-common.c
 create mode 100644 rebase-common.h
 create mode 100644 rebase-interactive.c
 create mode 100644 rebase-interactive.h
 create mode 100644 rebase-merge.c
 create mode 100644 rebase-merge.h
 create mode 100644 rebase-todo.c
 create mode 100644 rebase-todo.h
 create mode 100755 t/perf/p3400-rebase.sh
 create mode 100755 t/perf/p3402-rebase-merge.sh
 create mode 100755 t/perf/p3404-rebase-interactive.sh