How to read Git 3-way unified diff output format?

You are referring to the 'combined diff format'. This extension of the original uni-diff format deals with two or more files as input and one file as the result merge. This format is described in details as part of the 'combined diff format' section of the git-diff command manual.

Note that the git diff "combined diff format", with one column for each of fileN is prepended to the output line to note how X's line is different from it, can be costly to generate.

The recent commit 72441af (April 2014) from Kirill Smelkov is very instructive on how such a diff will now be optimized (for Git 2.x, Q3 2014)

D(A,P2) is huge, because, if merge-base of A and P2 is several dozens of merges (from A, via first parent) below, that D(A,P2) will be diffing sum of merges from several subsystems to 1 subsystem.

The solution is to avoid computing n 1-parent diffs, and to find changed-to-all-parents paths via scanning A's and all Pi's trees simultaneously, at each step comparing their entries, and based on that comparison, populate paths result, and deduce we could skip recursing into subdirectories, if at least for 1 parent, sha1 of that dir tree is the same as in A.
That would save us from doing significant amount of needless work.