Myers diff in linear space: implementation

If you enjoy this article, I have published a book explaining the internals of Git through implementation: Building Git.

In the last article we explored a linear space variant of the Myers diff algorithm, which is the version of the algorithm actually used by Git. We saw how it achieves its space-saving trick and how it can lead to multiple possible edit paths since it can discover many possible optimal edit paths.

Now I’d like to step through an implementation so you can see this working in code. We’d like a function MyersLinear.diff(a, b) to take two arrays of Diff::Line values and return an array of Diff::Edit objects that record the line number and content of each line and whether it’s a deletion, insertion, or unchanged line.

Let’s start off by creating a class. Many of the functions here will need to refer to a and b and so rather than pass those around everywhere, I’m just going to store them off as instance variables on this object.

class MyersLinear
  def self.diff(a, b)
    new(a, b).diff

  def initialize(a, b)
    @a, @b = a, b

  def diff
    # TODO

Now, recall that this algorithm works by recursively splitting the edit graph into smaller and smaller sub-regions. As we implement this recursive process, we’re going to need a way to represent the region we’re currently working on. We could pass the co-ordinates or width and height around, but I’d like to encapsulate this idea as a single value. The following Box class represents a region by its top-left and bottom-right co-ordinates and provides some convenience methods that will clarify the subsequent code. In Ruby, Struct just creates a class whose constructor assigns its arguments to the given names.

  Box =, :top, :right, :bottom) do
    def width
      right - left

    def height
      bottom - top

    def size
      width + height

    def delta
      width - height

Our implementation will work in two phases: first, we run the algorithm described in the previous article, that is the recursive procedure for finding the series of snakes that form the midpoint of each region. Then, we will use this series to reconstruct the line-by-line diff.

Let’s introduce a method in the MyersLinear class for the first phase; this is the core of the recursive algorithm. Given any set of co-ordinates left, top, right and bottom, we find the middle snake within that box. If we don’t find a snake, it means this region is already as small as possible (it’s a single point) and we return nil to indicate this yielded no new moves. But if we do find a snake, we take its start and end points and construct two new regions from the top-left of our original box to the start of the snake, and from the end of the snake to the bottom-right of our box, and recursively find the edit path for each of them. Finally, we combine the edit paths for these two regions into a single list and return it.

  def find_path(left, top, right, bottom)
    box   =, top, right, bottom)
    snake = midpoint(box)

    return nil unless snake

    start, finish = snake

    head = find_path(box.left,, start[0], start[1])
    tail = find_path(finish[0], finish[1], box.right, box.bottom)

    (head || [start]) + (tail || [finish])

The midpoint method will return a representation of a snake, which is a pair of points for the start and end of the snake, for example [[6, 5], [9, 7]]. Each recursive call to find_path will either return a list of points or nil, and when it does return nil we use one of the snake’s points in its place. For example, when head is nil, that means the region from the top-left of the box to the start of the middle snake is just a single point, so we can use the start of the snake to represent it. In this way, the method ends up building a list of the ends of all the middle snakes it found as it divided the graph into smaller boxes.

Having defined the basic outline of the algorithm, we now need to implement the method for actually finding the midpoint for each region. Our midpoint method shown below will take a Box structure and try to return a pair of points representing the middle snake, in the form [[left, top], [right, bottom]]. To do this, it runs the original version of the algorithm for finding the shortest edit, but it runs it simultaneously in both directions, one beginning at the top-left and one at the bottom-right.

Therefore, rather than a single v array for storing the best position for each diagonal, we need two: vf for the forward direction and vb for the backward one. As before, I’m seeding the forward-scan with box.left, i.e. the x co-ordinate of the start of the search. However, for the backward scan I’m starting with box.bottom, rather than box.right. When we scan forward, we’re looking to maximise x, so as to prioritise deletions over insertions. But when we scan in the reverse direction, we’d like the opposite: we want prioritise insertions, so that those appear last in the final output. So, I’m basing the backward scan around minimising y rather than x, and have therefore used box.bottom as my starting value. This is an entirely arbitrary decision, and you can just as well use x for both scans and experiment to see what edit paths you end up with.

With the starting arrays set up, we then iterate d as before, but on each iteration we fill in a row of values in both the forwards and the backwards direction. I’ve implemented this as two method calls, forwards and backward, that perform the scan and yield any potential snakes they found. To do this, they need to take both vf and vb so they can detect whether they’ve found any overlapping paths.

As soon as forwards or backward yields a snake, we return it. This mirrors the behaviour of Git, which stops on the first overlap it finds. However you could experiment with different results by storing off all the snakes yielded and then implementing a scoring method to choose between them.

  def midpoint(box)
    return nil if box.size == 0

    max = (box.size / 2.0).ceil

    vf    = * max + 1)
    vf[1] = box.left
    vb    = * max + 1)
    vb[1] = box.bottom

    (0 .. max).step do |d|
      forwards(box, vf, vb, d) { |snake| return snake }
      backward(box, vf, vb, d) { |snake| return snake }

The forwards and backward methods themselves will look quite familiar from the original Myers algorithm. To refresh your memory, here’s our original shortest_edit method:

  def shortest_edit
    n, m = @a.size, @b.size
    max  = n + m

    v    = * max + 1)
    v[1] = 0

    (0 .. max).step do |d|
      (-d .. d).step(2) do |k|
        if k == -d or (k != d and v[k - 1] < v[k + 1])
          x = v[k + 1]
          x = v[k - 1] + 1

        y = x - k

        while x < n and y < m and @a[x].text == @b[y].text
          x, y = x + 1, y + 1

        v[k] = x

        return d if x >= n and y >= m

Our new methods (see below) are just performing the inner loop over k, but there are a few modifications we’ve had to make. The first is that, because we’re trying to return the start and end points of the snake, not just the length of the edit sequence, we need to store the previous value of x before we make our next move. I’ve called this value px and it’s the same as x if we take a downward step, but one less than x if we step rightward.

The second change is that rather than simply saying y = x - k, we need to adjust our x and y values relative to the box’s top-left corner, so this becomes y = + (x - box.left) - k. Then we must also calculate py, which will be one less than y if we moved downward (i.e. x did not change) and equal to y otherwise.

Then, as before, we follow any possible diagonal steps, taking care not to overshoot box.right or box.bottom, and we store off the final value of x. The final change is that at the end of this method, we check for overlaps between the forward and backward scans, here comparing our current y value to the value found in the corresponding c diagonal in the vb array. If our y value is greater than or equal to the corresponding vb[c] value, the scans have overlapped and we can yield the move we just took back to the caller as a potential middle snake. Mirroring Git again, I’m iterating k in descending order, so we pick the overlap on the uppermost diagonal possible.

  def forwards(box, vf, vb, d)
    (-d .. d).step(2).reverse_each do |k|
      c = k -

      if k == -d or (k != d and vf[k - 1] < vf[k + 1])
        px = x = vf[k + 1]
        px = vf[k - 1]
        x  = px + 1

      y  = + (x - box.left) - k
      py = (d == 0 || x != px) ? y : y - 1

      while x < box.right and y < box.bottom and @a[x].text == @b[y].text
        x, y = x + 1, y + 1

      vf[k] = x

      if and c.between?(-(d - 1), d - 1) and y >= vb[c]
        yield [[px, py], [x, y]]

The backward method is much the same, except that it tries to minimise y rather than maximise x, and values in the vb array are indexed by c rather than k.

  def backward(box, vf, vb, d)
    (-d .. d).step(2).reverse_each do |c|
      k = c +

      if c == -d or (c != d and vb[c - 1] > vb[c + 1])
        py = y = vb[c + 1]
        py = vb[c - 1]
        y  = py - 1

      x  = box.left + (y - + k
      px = (d == 0 || y != py) ? x : x + 1

      while x > box.left and y > and @a[x - 1].text == @b[y - 1].text
        x, y = x - 1, y - 1

      vb[c] = y

      if and k.between?(-d, d) and x <= vf[k]
        yield [[x, y], [px, py]]

We’ve now seen all the methods that find the shortest edit path: find_path uses midpoint to find the middle snake, which in turn uses forwards and backward methods to scan the current box. find_path then recurses into the two smaller boxes defined by the middle snake. When we run this on the C code in the previous article, it generates this sequence of points:

[ [0, 0],   [1, 0],   [2, 2],   [3, 2],   [4, 2],
  [5, 4],   [6, 4],   [6, 5],   [9, 7],   [10, 9],
  [11, 9],  [11, 10], [11, 11], [12, 12], [13, 12],
  [13, 13], [14, 14] ]

Notice that not every point in this sequence is a single step from the one before it. For example, while the difference between [6, 4] and [6, 5] is a single downward step, the gap between [6, 5] and [9, 7], or between [9, 7] and [10, 9], is composed of multiple steps. To construct the complete diff, we need to work out all the single steps that make up the jumps between these points.

Take that snake we found at the first iteration of the algorithm, from [6, 5] to [9, 7]. We know a snake is composed of a single rightward and downward step followed by zero or more diagonal ones. Because of snakes found by scanning backward, they can also be a sequence of diagonal steps followed by a single rightward or downward one (leftward or upward in reverse direction). So, this snake could correspond to one of these sets of steps:

        o---o   o   o               o   o   o   o
              \                       \
        o   o   o   o       or      o   o   o   o
                  \                       \
        o   o   o   o               o   o   o---o

We know this move includes a rightward step rather than a downward one, because the change in the x co-ordinate from 6 to 9 is greater than the change in y from 5 to 7. A greater change in y than x would indicate a downward move.

As well as deciding which direction this step is in, we also need to decide whether it appears at the beginning or the end of the snake, that is, do we have the sequence on the left in the above figure, or the one on the right? To figure this out we can compare the lines at the starting point of the snake. If line 6 in the old version is equal to line 5 in the new one, then the first step is a diagonal and the rightward step comes at the end. Otherwise, it comes at the start.

Putting all this together, we can write a method the uses the output of find_path to to reconstruct the complete diff. The walk_snakes method below takes each consecutive pair of points in the find_path output and derives the complete path between them. For each pair of points, it first tries to walk a diagonal from the first point by checking the lines in the @a and @b strings. From there, it compares the change in x to the change in y; if it’s negative then the y change is greater and we yield a downward step, but if it’s positive then we yield a rightward step. Note that this code explicitly does nothing if the changes in x and y are equal. Some snakes will consist only of diagonals so there is no rightward or downward step to yield. Finally, we try to walk diagonals again to handle the case where the rightward/downward move happens first.

  def walk_snakes(&block)
    path = find_path(0, 0, @a.size, @b.size)
    return unless path

    path.each_cons(2) do |(x1, y1), (x2, y2)|
      x1, y1 = walk_diagonal(x1, y1, x2, y2, &block)

      case x2 - x1 <=> y2 - y1
      when -1
        yield x1, y1, x1, y1 + 1
        y1 += 1
      when 1
        yield x1, y1, x1 + 1, y1
        x1 += 1

      walk_diagonal(x1, y1, x2, y2, &block)

  def walk_diagonal(x1, y1, x2, y2, &block)
    while x1 < x2 and y1 < y2 and @a[x1].text == @b[y1].text
      yield x1, y1, x1 + 1, y1 + 1
      x1, y1 = x1 + 1, y1 + 1
    [x1, y1]

Now we can loop back to where we started and implement the diff method. All this does is call walk_snakes and consumes the pairs of points yielded by that method. For each pair of points, if x is unchanged then we have a downward move, which corresponds to an insertion; if y is unchanged then we have a deletion; and otherwise we have a diagonal move and the lines are equal.

  def diff
    diff = []

    walk_snakes do |x1, y1, x2, y2|
      if x1 == x2
        diff <<, nil, @b[y1])
      elsif y1 == y2
        diff <<, @a[x1], nil)
        diff <<, @a[x1], @b[y1])


Putting everything together, when we run Diff.diff(a, b, differ: MyersLinear) where a and b are the two versions of the C code in the last article, we indeed get the diff that Git produces:

-    1         void Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
+         1    int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
     2    2    {
-    3             if (!Chunk_bounds_check(src, src_start, n)) return;
-    4             if (!Chunk_bounds_check(dst, dst_start, n)) return;
+         3        if (chunk == NULL) return 0;
     5    4
-    6             memcpy(dst->data + dst_start, src->data + src_start, n);
+         5        return start <= chunk->length && n <= chunk->length - start;
     7    6    }
     8    7
-    9         int Chunk_bounds_check(Chunk *chunk, size_t start, size_t n)
+         8    void Chunk_copy(Chunk *src, size_t src_start, Chunk *dst, size_t dst_start, size_t n)
    10    9    {
-   11             if (chunk == NULL) return 0;
+        10        if (!Chunk_bounds_check(src, src_start, n)) return;
+        11        if (!Chunk_bounds_check(dst, dst_start, n)) return;
    12   12
-   13             return start <= chunk->length && n <= chunk->length - start;
+        13        memcpy(dst->data + dst_start, src->data + src_start, n);
    14   14    }

The ability of this algorithm to make choices about which snake to pick means you can experiment with it. Try iterating k in ascending order to see how that changes the diffs you get. Try making the backward method work using x rather than y co-ordinates. Allow snakes to be selected from either direction, regardless of whether delta is even or not. Invent a scoring method for selecting between multiple candidate snakes. There are endless tweaks you can make to this algorithm, and getting it “right” is a question of observing how it works on real-world inputs. Why not have a look at Git’s source code to see how it does things, and try out your own ideas for improving its output.