Why does the use of microtype and xfrac lead to a long compile time?

Question

While I was discussing another issue I came across this problem:

I included the xfrac package and the compile time of my document 100folded. After playing around I found out that microtype caused the problem. Assume the following document:

\documentclass{minimal}
\usepackage{microtype}
\usepackage{xfrac}
\begin{document}
Divide $4$ by $2$: $\sfrac{4}{2}=\sfrac{40}{20}\neq
\sfrac{42}{22}\neq\sfrac{2}{3}=\sfrac{4}{6}$. If you use many
$\sfrac{1}{2}$, $\sfrac{7}{8}$ and
microtype together it will take loooong to compile.
\end{document}

If you insert more copies of the text you'll encounter longer compile times. I inserted 16 copies and the document compiled ~20 seconds. When I remove the microtype package it will compile in under one second.

Can anybody explain why it takes that long? Is it maybe a bug in microtype?

Answer 1

(First a suspicion, now the answer, as per Joseph's request:)

The performance issues you encounter with microtype version 2.4 are fixed in v2.5 available from tlcontrib.

Answer 2

Packages that use a lot of calculations and loops can cause execution to be slowed down. Microtype does a lot of calculations and iterations to optimize spacing between letters, words and determining optimum lines. I would guess in O(n³) time.

See my answer at Benchmarking various operations of TeX

xfrac and anything using LaTeX3 in general runs slower. If you are after speed use TeX straight.

Answer 3

I've replicated your MWE with 20 copies over the sample text. Importantly, if you replace all \sfrac commands with "ordinary" \frac commands, the difference in compile times between the programs with and without microtype feels negligible. This suggests that it's not some inherent deficiency (or, if you will, programming bug) in the microtype package that's causing the big slowdown but, rather, some kind of extra spacing/stretchability features built into the \sfrac macro that is forcing microtype to work extra hard.

By the way, with 20 copies of the sample text you provide, the outputs of the program with and without microtype are definitely not identical. Specifically, whereas both pdf files consist of one long paragraph of 24 lines, only lines 1-6 and 18-24 of these paragraphs are identical. The 11 lines in between these blocks, i.e., lines 7-17, are at first set more loosely in the version with microtype enabled than in the "plain" version (without microtype), but by the end of line 17 the microtype version has fully caught up with the plain version (thus causing lines 18-24 to be the same again). Eyeballing the two pdf files side-by-side does not show much of a visual difference at first glance. However, on further inspection I notice that the microtype version succeeds, in lines 14-17, in displaying the longer math sequence somewhat more harmoniously (i.e., more even interword spacing). Not a huge difference, for sure, but it may be important for sticklers...

Finally, in case someone wants to experiment with what I've reported, here's my version of the MWE:

\documentclass{minimal}
\usepackage{xfrac,microtype}
\newcommand{\textblock}{Divide $4$ by $2$: $\sfrac{4}{2} = 
  \sfrac{40}{20} \neq \sfrac{42}{22} \neq\sfrac{2}{3}= \sfrac{4}{6}$. 
  If you use many $\sfrac{1}{2}$, $\sfrac{7}{8}$ and
  microtype together it will take loooong to compile. }
\begin{document}
%% 20 repetitions of the text contained in "textblock"
\textblock \textblock \textblock \textblock \textblock
\textblock \textblock \textblock \textblock \textblock
\textblock \textblock \textblock \textblock \textblock
\textblock \textblock \textblock \textblock \textblock
\end{document}