[tug-summer-of-code] Project ideas

[Scott Pakin]

Karl Berry wrote:
>     I also have an idea to propose. In short, the idea is parallel
>     version of TeX. My plan is to use OpenMP for parallelization. It
>     should make TeX run faster without much more complication in the
>     code base. Please give me some thoughts.
> 
> The basic TeX code is monolithic and relies almost entirely on global
> variables.  There have been some discussions of parallelizing certain
> small parts of the code, such as the output routine, but even this is
> fraught with extreme difficulty.  I am not sure what can be usefully
> parallelized.

While it's true that TeX is monolithic and relies almost entirely on
global variables, the real problem for parallelism as I see it is
that TeX implements an extremely sequential state machine.  Each
character must be read and processed before proceeding with the next
character.  This is because earlier processing can affect later
processing (cf.  \catcode).  One can't even process pages in
parallel because it is not known in advance where the page breaks
will wind up.

It might be possible to utilize speculative parallelism with various
reasonable assumptions (e.g., that category-code changes are local
and that macros are mostly defined before the first shipout) to
pregenerate boxes without shipping them out although with the
ability to cancel all future boxes if an assumption is violated.
This approach is almost certainly fraught with at least as much
difficulty as parallelizing TeX's output routine.

-- Scott