# Is it still worthwhile to let TeX try line-breaking without hyphenation?

Here's TeX's line-breaking approach (as I understand it) in a nutshell:

1. If \pretolerance is positive, try to break a paragraph into lines without inserting discretionary hyphens and without exceeding a badness of \pretolerance.

2. If method 1 fails, allow hyphenation and try not to exceed a badness of \tolerance.

3. If method 2 fails and \emergencystretch is positive, try again with the amount of "tolerable" white space per text line increased by \emergencystretch.

On p. 96 of the TeXbook, Knuth reports experiments showing that "the first pass [without hyphenation] succeeds more than 90% of the time" for "fairly wide" lines, but fails quickly for "very narrow" ones. He also states that the first pass is done "[i]n order to save time". My interpretation of this is as follows:

• For cases where line-breaking without hyphenation fails, one would in fact save time by omitting the first pass (i.e., setting \pretolerance=-1).

• It is also possible (though maybe not very likely for languages with a small average word length) that the first pass will succeed, but that allowing hyphenation would have resulted in a solution with smaller badness.

• As Knuth nevertheless chose a default value of 100 for \pretolerance, he must have regarded the net time savings from "trying without hyphenation" as worthwile, given the average processing power of the time when he adopted these settings.

I don't know if the default settings for TeX's line-breaking algorithm changed over time. But isn't it possible that formerly substantial net time savings are irrelevant today?

So: Is it still worthwhile to let TeX try line-breaking without hyphenation? Or is it preferable by now to adopt \pretolerance=-1 as default setting?

-
In general, I'd prefer a non hyphenated paragraph with badness 100 to a hyphenated one with badness 80 (even 50, perhaps). Acting on \hyphenpenalty might be a solution, but I think that the "first pass" takes comparatively short time. Probably @Taco knows better. –  egreg Sep 25 '11 at 19:48
@egreg: Given your preferences, shouldn't one increase the penalty for hyphens and still omit the first pass? –  lockstep Sep 25 '11 at 19:51
If it is simply about time, then you need to benchmark it. I don't think it has a significant impact on time on modern machines. –  Martin Scharrer Sep 25 '11 at 19:54

It does not have any serious impact on performance on modern machines and I can vouch on old machines as well. Depending on your settings more than 50% of text would normally pass through the first pass. Here is a figure of two tests (the red numbers denote badness):

The tests were carried out using code posted by Wilson on Git. Personally I would recommend let the \pretolerance stay at 100 it will probably be faster (as you do not force the other passes in the majority of cases).

\documentclass{article}
\usepackage{xcolor}
%%% Code from GIT posted by Wilson

\frenchspacing
\fussy

\makeatletter
\newbox\trialbox
\newbox\linebox
\newcount\overfulls

\def\trypar#1\par{%
\showtrybox{\linewidth}{#1\par}%
}

\newcommand\showtrybox[2]{%
\setbox\trialbox=\vbox{%
\hsize#1\relax#2%
\eatlines
}%
\setbox\trialbox=\vbox{%
\hsize#1\relax#2%
\printlines
}%
\noindent\usebox\trialbox\par
}

\newcommand\trybox[2]{%
\setbox\trialbox=\vbox{%
\hsize#1\relax#2\par
\eatlines
}%
}

\def\eatlines{%
\begingroup
\setbox\linebox=\lastbox
\setbox0=\hbox to \hsize{\unhcopy\linebox\hss}%
\ifvoid\linebox\else
\unskip\unpenalty\eatlines
\fi
\endgroup
}

\def\printlines{%
\begingroup
\setbox\linebox=\lastbox
\setbox0=\hbox to \hsize{\unhcopy\linebox}%
\ifvoid\linebox\else
\unskip\unpenalty\printlines
\fi
\endgroup
}

\makebox[0pt][l]{%
\fi
}%
}

\makeatother

\begin{document}

\begin{minipage}[t]{4.5cm}
\trypar\hyphenpenalty=500\looseness=1
In olden times when wishing
still helped one, there lived a
king whose daughters were all
beautiful, but the youngest was so
beautiful that the sun itself,
which has seen so much, was
astonished whenever it shone in
her face. Close by the king's
castle lay a great dark forest,
and under an old lime-tree in the
forest was a well, and when
the day was very warm, the
king's child went out into the
forest and sat down by the side
of the cool fountain, and when she was bored she
took a golden ball, and threw it up on a high and caught it, and this
ball was her favorite plaything. \par
\end{minipage}
\hspace{2cm}
\begin{minipage}[t]{4.5cm}
\trypar\hyphenpenalty=10000\looseness=1
In olden times when wishing
still helped one, there lived a
king whose daughters were all
beautiful, but the youngest was so
beautiful that the sun itself,
which has seen so much, was
astonished whenever it shone in
her face. Close by the king's
castle lay a great dark forest,
and under an old lime-tree in the
forest was a well, and when
the day was very warm, the
king's child went out into the
forest and sat down by the side
of the cool fountain, and when she was bored she
took a golden ball, and threw it up on a high and caught it, and this
ball was her favorite plaything. \par
\end{minipage}
\end{document}

-
Thanks for the instructive example! –  lockstep Sep 25 '11 at 20:41
@lockstep What amazed me with trying it out, is how the single hyphen on the text at the left side improved the looks of the paragraph. I use it as an example at work to convert younger Engineers to TeX! –  Yiannis Lazarides Sep 25 '11 at 20:46
My question was motivated by a case (sadly, I can't recall it exactly) where \pretolerance=-1 improved looks. (The language was German, i.e., hyphens were more beneficial.) –  lockstep Sep 25 '11 at 20:49
I like the example, but it's not clear to me what it has to do with the question: it is exceptional (one rarely sees the consequences of choosing to move a word onto the next line propagate for 9 further lines), and it doesn't illustrate any relationship between Knuth's algorithm and the quality of the output. BTW, do you mean the Wilson code was posted on Github? –  Charles Stewart Sep 26 '11 at 9:40
@Charles The example you need to view is the one at the left at which I allowed hyphenation. The one at the right has a '\hyphenpenalty' of 10000 and will not use hyphenation (I provided two columns to allow experimentation side by side). If you make the columns wider Knuth is certainly right for English, but I think lockstep's concerns with German are valid. –  Yiannis Lazarides Sep 26 '11 at 20:32