How is typesetting in multiple columns implemented

Question

I can type

\documentclass[twocolumn]{scrartcl}

to get a document typeset in two columns. But how does this works internally? I read The TeXbook, but didn't find a single paragraph about this. (Maybe I didn't look carefully enough.)

Answer 1

The routine is described by Knuth in Appendix E: Example Formats, page 417. The macros were used for two-column formatting of Appendix I, the index.

The algorithm is not to difficult to follow. Everything is placed in a tall box of a width equal to the column width and then split. For a page that is full this simple algorithm works quite well. The only complication is when one needs to balance the columns in a page when there is not enough content. Here Knuth uses a loop to achieve it.

The \begindoublecolumns macro operates by first saving the current \box255 in \partialpage.

It then changes the output routine to \doublecolumnout, changing \hsize to \colwidth, and changing \vsize to \bigcolheight. The last one is a bit more than twice the original \vsize.

This allows a very tall column to accumulate. When \doublecolumnout is called, \vsplit is used to extract columns of the correct height.

When \enddoublecolumns occurs, the output routine \balancecolumns uses a \loop in an attempt to split the current \box255 into two columns of equal height.

Then \pagesofar packages these boxes side by side and contributes the result (along with the \partialpage, if any) to the current vertical list, and normal processing resumes.

Knuth writes,

A more difficult approach would be necessary if the index contained insertions (e.g., footnotes); fortunately, it doesn't.

Unfortunately most do and they include floating figures and tables! The LaTeX Team took extra care to provide a highly complicated two-column algorithm to cater for all these, albeit still in not such a perfect way.

Answer 2

ConTeXt supports two types of multi-column output: simple multi-columns (similar to LaTeX's twocolumn) and column-sets (much more control over spanning figures, etc.). The source code for simple multi-columns gives a lot of implementation details and history; the source code for column sets has a few comments about the implementation.