Linux diff Command: From Line-by-Line Comparison to Unified Format#

During a recent code review, I needed to compare two config files. Staring at them side-by-side was painful. Then I remembered diff — a tool I’d used countless times but never really understood. Turns out, its implementation is more interesting than I expected.

The Core Algorithm: LCS (Longest Common Subsequence)#

The essence of diff is finding the minimum set of differences between two files. Sounds simple, but what does “minimum” mean?

The algorithm uses LCS (Longest Common Subsequence). Simply put: find the “common parts” on both sides, and everything else is the difference.

Example:

File A:         File B:
apple           apple
banana          berry
cherry          cherry
date            date

LCS is apple, cherry, date. The difference is banana → berry.

LCS Dynamic Programming Implementation#

function lcs(a: string[], b: string[]): string[] {
  const m = a.length, n = b.length
  const dp: number[][] = Array(m + 1)
    .fill(null)
    .map(() => Array(n + 1).fill(0))

  // Build DP table
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
      }
    }
  }

  // Backtrack to find LCS
  const result: string[] = []
  let i = m, j = n
  while (i > 0 && j > 0) {
    if (a[i - 1] === b[j - 1]) {
      result.unshift(a[i - 1])
      i--; j--
    } else if (dp[i - 1][j] > dp[i][j - 1]) {
      i--
    } else {
      j--
    }
  }
  return result
}

Time complexity: O(m×n). Space complexity: O(m×n). For large files, this can be slow, so GNU diff has many optimizations.

Three Output Formats Explained#

1. Default Format (Normal Format)#

diff file1.txt file2.txt

Output:

2c2
< banana
---
> berry

• 2c2: line 2 in first file changes to line 2 in second file
• < means deletion, > means addition
• a = add, d = delete, c = change

2. Unified Format — Most Common#

diff -u file1.txt file2.txt

Output:

--- file1.txt
+++ file2.txt
@@ -1,4 +1,4 @@
 apple
-banana
+berry
 cherry
 date

This is the Git diff format! - at line start means deletion, + means addition, space means unchanged.

Why “unified”?

Because it “unifies” differences into one block instead of scattering them. Context defaults to 3 lines for easy location.

3. Context Format#

diff -c file1.txt file2.txt

Output:

*** file1.txt
--- file2.txt
***************
*** 1,4 ****
  apple
! banana
  cherry
  date
--- 1,4 ----
  apple
! berry
  cherry
  date

Old-school format, rarely used now. ! means modified, + means added, - means deleted.

Practical Tips#

1. Side-by-Side Comparison#

diff -y file1.txt file2.txt

Output:

apple                               apple
banana                            | berry
cherry                              cherry
date                                date

| indicates difference, < and > indicate deletion and addition. Great for quick browsing.

2. Recursive Directory Comparison#

diff -r dir1/ dir2/

Only see which files differ:

diff -rq dir1/ dir2/

-q (brief) only reports differences, no content.

3. Ignore Whitespace Differences#

diff -w file1.txt file2.txt   # Ignore all whitespace
diff -b file1.txt file2.txt   # Ignore whitespace quantity changes

Perfect for differences caused by code formatting.

4. Working with patch#

# Generate patch
diff -u original.txt modified.txt > changes.patch

# Apply patch
patch original.txt < changes.patch

This is the standard workflow for open source contributions: fork → modify → diff → pull request.

Performance Optimization Principles#

GNU diff makes key optimizations to the LCS algorithm:

1. Hash Acceleration#

First hash files by line, lines with same hash match directly. Complexity drops from O(n²) to O(n).

2. Equivalence Classes#

Identical lines are grouped into equivalence classes, only LCS is computed on these classes.

3. Preprocessing#

Quick scan to find definitely same and definitely different parts, reducing LCS computation scope.

Benchmark:

Web Implementation: From LCS to Visualization#

Implementing a simple diff in browser:

function simpleDiff(oldText: string, newText: string) {
  const oldLines = oldText.split('\n')
  const newLines = newText.split('\n')
  const common = lcs(oldLines, newLines)

  const result: DiffLine[] = []
  let oldIdx = 0, newIdx = 0, commonIdx = 0

  while (oldIdx < oldLines.length || newIdx < newLines.length) {
    if (commonIdx < common.length) {
      // Handle old file differences
      while (oldIdx < oldLines.length && oldLines[oldIdx] !== common[commonIdx]) {
        result.push({ type: 'delete', content: oldLines[oldIdx] })
        oldIdx++
      }
      // Handle new file differences
      while (newIdx < newLines.length && newLines[newIdx] !== common[commonIdx]) {
        result.push({ type: 'add', content: newLines[newIdx] })
        newIdx++
      }
      // Common line
      result.push({ type: 'equal', content: common[commonIdx] })
      oldIdx++; newIdx++; commonIdx++
    } else {
      // Remaining differences
      while (oldIdx < oldLines.length) {
        result.push({ type: 'delete', content: oldLines[oldIdx] })
        oldIdx++
      }
      while (newIdx < newLines.length) {
        result.push({ type: 'add', content: newLines[newIdx] })
        newIdx++
      }
    }
  }

  return result
}

This implementation works for code comparison, config file diffs, etc.

Common Pitfalls#

1. Binary Files#

diff only reports “differ” for binary files by default, no content shown. Use -a to force text treatment (but output will be messy).

2. Large File Memory#

When files exceed memory, GNU diff uses temp files. Ensure /tmp has enough space.

3. Line Endings#

Windows (CRLF) vs Linux (LF) line endings cause many “false differences”. Use --strip-trailing-cr to ignore.

Related Tools Comparison#

Summary#

The core of diff command is the LCS algorithm. Output formats include default, unified, and context. In practice:

• Generate patches: diff -u
• Quick comparison: diff -y or diff -q
• Directory comparison: diff -r
• Ignore whitespace: diff -w

Next time you see Git diff output, you’ll know the principle behind it.

Related Tools:

• Text Diff Checker - Online diff tool
• JSON Diff - JSON data comparison