hybrid-parbuilder.tex /size: 14 Kb    last modification: 2023-12-21 09:43
1% language=us
2
3\startcomponent hybrid-parbuilder
4
5\startbuffer[MyAbstract]
6\StartAbstract
7    In this article I will summarize some experiences with converting the \TEX\
8    par builder to \LUA. In due time there will be a plugin mechanism in
9    \CONTEXT, and this is a prelude to that.
10\StopAbstract
11\stopbuffer
12
13\doifmodeelse {tugboat} {
14    \usemodule[tug-01,abr-01]
15    \setvariables
16      [tugboat]
17      [columns=yes]
18    \setvariables
19      [tugboat]
20      [year=2010,
21       volume=99,
22       number=9,
23       page=99]
24    \setvariables
25      [tugboat]
26      [title=Building paragraphs,
27       subtitle=,
28       keywords=,
29       author=Hans Hagen,
30       address=PRAGMA ADE\\Ridderstraat 27\\8061GH Hasselt NL,
31       email=pragma@xs4all.nl]
32    %
33    % we use a buffer as abstract themselves are buffers and
34    % inside macros we loose line endings and such
35    \getbuffer[MyAbstract]
36    %
37    \StartArticle
38} {
39    \environment hybrid-environment
40    \startchapter[title={Building paragraphs}]
41}
42
43\startsection [title={Introduction}]
44
45You enter the den of the Lion when you start messing around with the parbuilder.
46Actually, as \TEX\ does a pretty good job on breaking paragraphs into lines I
47never really looked into the code that does it all. However, the Oriental \TEX\
48project kind of forced it upon me. In the chapter about font goodies an optimizer
49is described that works per line. This method is somewhat similar to expansion
50level~one support (hz) in the sense that it acts independent of the par builder:
51the split off (best) lines are postprocessed. Where expansion involves horizontal
52scaling, the goodies approach does with (Arabic) words what the original HZ
53approach does with glyphs.
54
55It would be quite some challenge (at least for me) to come up with solutions that
56look at the whole paragraph and as the per-line approach works quite well, there
57is no real need for an alternative. However, in September 2008, when we were
58exploring solutions for Arabic par building, Taco converted the parbuilder into
59\LUA\ code and stripped away all code related to hyphenation, protrusion,
60expansion, last line fitting, and some more. As we had enough on our plate at
61that time, we never came to really testing it. There was even less reason to
62explore this route because in the Oriental \TEX\ project we decided to follow the
63\quotation {use advanced \OPENTYPE\ features} route which in turn lead to the
64\quote {replace words in lines by narrower of wider variants} approach.
65
66However, as the code was laying around and as we want to explore further I
67decided to pick up the parbuilder thread. In this chapter some experiences will
68be discussed. The following story is as much Taco's as mine.
69
70\stopsection
71
72\startsection [title={Cleaning up}]
73
74In retrospect, we should not have been too surprised that the first approximation
75was broken in many places, and for good reason. The first version of the code was
76a conversion of the \CCODE\ code that in turn was a conversion from the original
77interwoven \PASCAL\ code. That first conversion still looked quite \CCODE||ish
78and carried interesting bit and pieces of \CCODE||macros, \CCODE||like pointer
79tests, interesting magic constants and more.
80
81When I took the code and \LUA-fied it nearly every line was changed and it took
82Taco and me a bit of reverse engineering to sort out all problems (thank you
83Skype). Why was it not an easy task? There are good reasons for this.
84
85\startitemize
86
87\startitem The parbuilder (and related hpacking) code is derived from traditional
88\TEX\ and has bits of \PDFTEX, \ALEPH\ (\OMEGA), and of course \LUATEX. \stopitem
89
90\startitem The advocated approach to extending \TEX\ has been to use change files
91which means that a coder does not see the whole picture. \stopitem
92
93\startitem Originally the code is programmed in the literate way which means that
94the resulting functions are build stepwise. However, the final functions can (and
95have) become quite large. Because \LUATEX\ uses the woven (merged) code indeed we
96have large functions. Of course this relates to the fact that succesive \TEX\
97engines have added functionality. Eventually the source will be webbed again, but
98in a more sequential way. \stopitem
99
100\startitem This is normally no big deal, but the \ALEPH\ (\OMEGA) code has added
101a level of complexity due to directional processing and additional begin and end
102related boxes. \stopitem
103
104\startitem Also the \ETEX\ extension that deals with last line fitting is
105interwoven and uses goto's for the control flow. Fortunately the extensions are
106driven by parameters which make the related code sections easy to recognize.
107\stopitem
108
109\startitem The \PDFTEX\ protrusion extension adds code to glyph handling and
110discretionary handling. The expansion feature does that too and in addition also
111messes around with kerns. Extra parameters are introduced (and adapted) that
112influence the decisions for breaking lines. There is also code originating in
113\PDFTEX\ which deals with poor mans grid snapping although that is quite isolated
114and not interwoven. \stopitem
115
116\startitem Because it uses a slightly different way to deal with hyphenation,
117\LUATEX\ itself also adds some code. \stopitem
118
119\startitem Tracing is sort of interwoven in the code. As it uses goto's to share
120code instead of functions, one needs to keep a good eye on what gets skipped or
121not. \stopitem
122
123\stopitemize
124
125I'm pretty sure that the code that we started with looks quite different from the
126original \TEX\ code if it had been translated into \CCODE. Actually in modern
127\TEX\ compiling involves a translation into \CCODE\ first but the intermediate
128form is not meant for human eyes. As the \LUATEX\ project started from that
129merged code, Taco and Hartmut already spent quite some time on making it more
130readable. Of course the original comments are still there.
131
132Cleaning up such code takes a while. Because both languages are similar but also
133quite different it took some time to get compatible output. Because the \CCODE\
134code uses macros, careful checking was needed. Of course \LUA's table model and
135local variables brought some work as well. And still the code looks a bit
136\CCODE||ish. We could not divert too much from the original model simply because
137it's well documented.
138
139When moving around code redundant tests and orphan code has been removed. Future
140versions (or variants) might as well look much different as I want more hooks,
141clearly split stages, and convert some linked list based mechanism to \LUA\
142tables. On the other hand, as already much code has been written for \CONTEXT\
143\MKIV, making it all reasonable fast was no big deal.
144
145\stopsection
146
147\startsection [title={Expansion}]
148
149The original \CCODE||code related to protrusion and expansion is not that
150efficient as many (redundant) function calls take place in the linebreaker and
151packer. As most work related to fonts is done in the backend, we can simply stick
152to width calculations here. Also, it is no problem at all that we use floating
153point calculations (as \LUA\ has only floats). The final result will look okay as
154the original hpack routine will nicely compensate for rounding errors as it will
155normally distribute the content well enough. We are currently compatible with the
156regular par builder and protrusion code, but expansion gives different results
157(actually not worse).
158
159The \LUA\ hpacker follows a different approach. And let's admit it: most \TEX ies
160won't see the difference anyway. As long as we're cross platform compatible it's
161fine.
162
163It is a well known fact that character expansion slows down the parbuilder. There
164are good reasons for this in the \PDFTEX\ approach. Each glyph and intercharacter
165kern is checked a few times for stretch or shrink using a function call. Also
166each font reference is checked. This is a side effect of the way \PDFTEX\ backend
167works as there each variant has its own font. However, in \LUATEX, we scale
168inline and therefore don't really need the fonts. Even better, we can get rid of
169all that testing and only need to pass the eventual \type {expansion_ratio} so
170that the backend can do the right scaling. We will prototype this in the \LUA\
171version \footnote {For this Hartmuts has adapted the backend code has to honour
172this field in the glyph and kern nodes.} and we feel confident about this
173approach it will be backported into the \CCODE\ code base. So eventually the
174\CCODE\ might become a bit more readable and efficient.
175
176Intercharacter kerning is dealt with in a somewhat strange way. If a kern of
177subtype zero is seen, and if it's neighbours are glyphs from the same font, the
178kern gets replaced by a scaled one looked up in the font's kerning table. In the
179parbuilder no real replacement takes place but as each line ends up in the hpack
180routine (where all work is simply duplicated and done again) it really gets
181replaced there. When discussing the current aproach we decided, that manipulating
182intercharacter kerns while leaving regular spacing untouched, is not really a
183good idea so there will be an extra level of configuration added to \LUATEX:
184\footnote {As I more and more run into books typeset (not by \TEX) with a
185combination of character expansion and additional intercharacter kerning I've
186been seriously thinking of removing support for expansion from \CONTEXT\ \MKIV.
187Not all is progress especially if it can be abused.}
188
189\starttabulate
190\NC 0 \NC no character and kern expansion \NC \NR
191\NC 1 \NC character and kern expansion applied to complete lines \NC \NR
192\NC 2 \NC character and kern expansion as part of the par builder \NC \NR
193\NC 3 \NC only character expansion as part of the par builder (new) \NC \NR
194\stoptabulate
195
196You might wonder what happens when you unbox such a list: the original font
197references have been replaced as were the kerns. However, when repackaged again,
198the kerns are replaced again. In traditional \TEX, indeed rekerning might happen
199when a paragraph is repackaged (as different hyphenation points might be chosen
200and ligature rebuilding etc.\ has taken place) but in \LUATEX\ we have clearly
201separated stages. An interesting side effect of the conversion is that we really
202have to wonder what certain code does and if it's still needed.
203
204\stopsection
205
206\startsection [title={Performance}]
207
208% timeit context ...
209
210We had already noticed that the \LUA\ variant was not that slow. So after the
211first cleanup it was time to do some tests. We used our regular \type {tufte.tex}
212test file. This happens to be a worst case example because each broken line ends
213with a comma or hyphen and these will hang into the margin when protruding is
214enabled. So the solution space is rather large (an example will be shown later).
215
216Here are some timings of the March 26, 2010 version. The test is typeset in a box
217so no shipout takes place. We're talking of 1000 typeset paragraphs. The times
218are in seconds an between parentheses the speed relative to the regular
219parbuilder is mentioned.
220
221\startmode[mkiv]
222
223\startluacode
224    local times = {
225        { 1.6,  8.4,  9.8 }, --  6.7 reported in statistics
226        { 1.7, 14.2, 15.6 }, -- 13.4
227        { 2.3, 11.4, 13.3 }, --  9.5
228        { 2.9, 19.1, 21.5 }, -- 18.2
229    }
230
231    local NC, NR, b, format = context.NC, context.NR, context.bold, string.format
232
233    local function v(i,j)
234        if times[i][j]<10 then   -- This is a hack. The font that we use has no table
235            context.dummydigit() -- digits (tnum) so we need this hack. Not nice anyway.
236        end
237        context.equaldigits(format("%0.01f",times[i][j]))
238        if j > 1 then
239            context.enspace()
240            context.equaldigits(format("(%0.01f)",times[i][j]/times[i][1]))
241        end
242    end
243
244    context.starttabulate { "|l|c|c|c|" }
245        NC()                 NC() b("native") NC() b("lua") NC() b("lua + hpack") NC() NR()
246        NC() b("normal")     NC() v(1,1)      NC() v(1,2)   NC() v(1,3)           NC() NR()
247        NC() b("protruding") NC() v(2,1)      NC() v(2,2)   NC() v(2,3)           NC() NR()
248        NC() b("expansion")  NC() v(3,1)      NC() v(3,2)   NC() v(3,3)           NC() NR()
249        NC() b("both")       NC() v(4,1)      NC() v(4,2)   NC() v(4,3)           NC() NR()
250    context.stoptabulate()
251\stopluacode
252
253\stopmode
254
255\startnotmode[mkiv]
256
257% for the tugboat article
258
259\starttabulate[|l|c|c|c|]
260\NC                \NC \bf native \NC \bf lua    \NC \bf lua + hpack \NC \NR
261\NC \bf normal     \NC 1.6        \NC  8.4 (5.3) \NC  9.8 (6.1)      \NC \NR
262\NC \bf protruding \NC 1.7        \NC 14.2 (8.4) \NC 15.6 (9.2)      \NC \NR
263\NC \bf expansion  \NC 2.3        \NC 11.4 (5.0) \NC 13.3 (5.8)      \NC \NR
264\NC \bf both       \NC 2.9        \NC 19.1 (6.6) \NC 21.5 (7.4)      \NC \NR
265\stoptabulate
266
267\stopnotmode
268
269For a regular paragraph the \LUA\ variant (currently) is 5~times slower and about
2706~times when we use the \LUA\ hpacker, which is not that bad given that it's
271interpreted code and that each access to a field in a node involves a function
272call. Actually, we can make a dedicated hpacker as some code can be omitted, The
273reason why the protruding is relatively slow is, that we have quite some
274protruding characters in the test text (many commas and potential hyphens) and
275therefore we have quite some lookups and calculations. In the \CCODE\ variant
276much of that is inlined by macros.
277
278Will things get faster? I'm sure that I can boost the protrusion code and
279probably the rest as well but it will always be slower than the built in
280function. This is no problem as we will only use the \LUA\ variant for
281experiments and special purposes. For that reason more \MKIV\ like tracing will
282be added (some is already present) and more hooks will be provided once the
283builder is more compartimized. Also, future versions of \LUATEX\ will pass around
284paragrapgh related parameters differently so that will have impact on the code as
285well.
286
287\stopsection
288
289\startsection[title=Usage]
290
291The basic parbuilder is enabled and disabled as follows:\footnote {I'm not
292sure yet if the parbuilder has to do automatic grouping.}
293
294\startbuffer[example]
295\definefontfeature[example][default][protrusion=pure]
296\definedfont[Serif*example]
297\setupalign[hanging]
298
299\startparbuilder[basic]
300    \startcolor[blue]
301        \input tufte
302    \stopcolor
303\stopparbuilder
304
305\stopbuffer
306
307\typebuffer[example]
308
309\startmode[mkiv]
310    This results in: \par \getbuffer[example]
311\stopmode
312
313There are a few tracing options in the \type {parbuilders} namespace but these
314are not stable yet.
315
316\stopsection
317
318\startsection[title=Conclusion]
319
320The module started working quite well around the time that Peter Gabriels
321\quotation {Scratch My Back} ended up in my Squeezecenter: modern classical
322interpretations of some of his favourite songs. I must admit that I scratched the
323back of my head a couple of times when looking at the code below. It made me
324realize that a new implementation of a known problem indeed can come out quite
325different but at the same time has much in common. As with music it's a matter of
326taste which variant a user likes most.
327
328At the time of this writing there is still work to be done. For instance the
329large functions need to be broken into smaller steps. And of course more testing
330is needed.
331
332\stopsection
333
334\doifmodeelse {tugboat} {
335    \StopArticle
336} {
337    \stopchapter
338}
339
340\stopcomponent
341