You are viewing a plain text version of this content. The canonical link for it is here.
Posted to fop-dev@xmlgraphics.apache.org by Dario Laera <la...@cs.unibo.it> on 2008/10/21 16:36:16 UTC
Active node tree pruning in FOP trunk
Hi all,
after noticing that the layout tree pruning in the prototype [1] was
improving performance I decided to implement it in FOP trunk to see
how it was behaving in the real world. The concept I've applied to the
general breaking algorithm can be defined as a "last-n-lines fit"
algorithm; if n=5, when the algorithm find the first node for the
sixth line it choose the final active node for the first line that
have the best active node as child (this is a correction from the
prototype implementation). Other nodes for line 1 gets discarded with
relative children. When the algorithm determine a line break for line
7 the pruning is performed for line 2. This is equivalent to say that
line 1 is chosen as the best in the context of lines 1-5, line 2 in
the context of lines 2-6, and so on. While this algorithm won't give
you the best possible layout (well, not always, depending on n value)
as total fit do, it can improve performance and shrink memory usage by
reducing the number of active node in some cases. Anyway it gets
"nice" layouts, surely better than best fit, and by choosing the value
of 'n' we can set the trade off between performance and quality.
In the tests I've done I saw a sensible improvement when two
conditions were satisfied:
1) the layout constraints was leading to an high number of active
nodes (short lines, hyphenation enabled, non justified alignment);
2) the paragraph was long enough to produce many lines (if n is
greater than the total number lines the pruning doesn't even get
activated).
As worst case I considered an A4 page with a single column with
justified text split in many paragraphs: no performance improvements.
Even if I process a single paragraph that is 8 page long the
processing time is the same as if pruning was disabled, while the
layout result is slightly different (but not bad).
As best case I considered an A4 page with two columns, hyphenation
enabled, left aligning for a single paragraph 8 page long. Here the
performance boost is embarrassing:
| cpu t | mem
---------+-------+--------
No prune | 2'20" | 570 MB
---------+-------+--------
n = 30 | 0'12" | 35 MB
---------+-------+--------
n = 1 | 0'07" | 35 MB
Well, this is a really extreme test that unlikely will represent a use
case, let's look at more tests:
Just | 1 col | 1 par || no pru | n=30 | n=1
------+-------+-------++--------+------+------
X | X | X || 6"7 | 6"6 | 6"6
------+-------+-------++--------+------+------
X | X | || 6"6 | 6"6 | 6"7
------+-------+-------++--------+------+------
X | | X || 14"4 | 7"1 | 6"9
------+-------+-------++--------+------+------
X | | || 7"9 | 7"3 | 6"9
------+-------+-------++--------+------+------
| X | X || 32"6 | 9"0 | 6"7
------+-------+-------++--------+------+------
| X | || 9"9 | 9"0 | 6"6
------+-------+-------++--------+------+------
| | X || 2'20"2 | 12"0 | 7"0
------+-------+-------++--------+------+------
| | || 21"0 | 13"0 | 7"0
The test was done with the same text modified as follows: justified or
left aligned, 1 or 2 columns, within a single block or split in 9
blocks of the same size.
I've attached the patch to be applied to trunk: to enable pruning you
can set the system property from the command line with -DtreeDepth=1
or any other number you choose for 'n'. If you don't define treeDepth
the pruning doesn't get enabled. I've also attached the test fo files
so you can check the resulting layout for the tests I reported above.
Dario
[1] http://mail-archives.apache.org/mod_mbox/xmlgraphics-fop-dev/200810.mbox/%3C236664AE-3F70-48F2-8D82-C26BA58BC92A@cs.unibo.it%3E
Re: Active node tree pruning in FOP trunk
Posted by Dario Laera <la...@cs.unibo.it>.
Il giorno 24/ott/08, alle ore 00:52, Dario Laera ha scritto:
> About left-aligned or justified: with the latter *sometimes* having
> threshold=1.0 is enough (I think because of stretchable glues) so
> obviously the number of active node is reduced, while the former
> will always fall in threshold=20.0 and in force mode (talking about
> my tests). Anyway, while I'm not sure short/long lines really makes
> difference, it's evident that non justified text produce a lot more
> of active nodes than justified ones.
The knuth list for a {left|right}-aligned paragraph is about twice the
one of a justified paragraph. If you look at the methods
addElementsFor* in TextLayoutManager class you can see that in some
cases, depending on the alignment, a different number of glues/
penalties can be added. This obviously makes the breaks possibilities
growing, as you can see in the graph attached that compare the SAME
xsl-fo except for alignment.
Dario
Re: Active node tree pruning in FOP trunk
Posted by Simon Pepping <sp...@leverkruid.eu>.
On Mon, Oct 27, 2008 at 06:00:06PM +0000, Vincent Hennebert wrote:
> Hi,
>
>
> [from another post]
> > A really strange thing: is it theoretically possible that the amount
> > of active nodes is greater than the number of knuth elements? As you
> > can see in the graph, for short lines there are >14000 active nodes
> > but only ~7000 knuth elements...
>
> Line breaking is a bin-packing problem [2], so the potential number of
> active nodes is exponential to the number of words you have in your
> paragraph. So, yes, it???s normal to have more active nodes than elements
> in the sequence.
Each feasible breakpoint can have 4 nodes, one for each line class. If
half of the Knuth elements are legal breakpoints (a simple sequence of
box - glue), then there could be at most 4 * 3500 nodes.
Note that you are using the term active node in the wrong sense,
viz. the set of nodes kept by the program. Active nodes are the subset
of those nodes that participate in the inner loop. Indeed, all nodes
were active at some point.
Regards, Simon
--
Simon Pepping
home page: http://www.leverkruid.eu
Re: Active node tree pruning in FOP trunk
Posted by Vincent Hennebert <vh...@gmail.com>.
Hi,
Dario Laera wrote:
> Hi Simon,
>
> thanks for your reply.
>
> Il giorno 23/ott/08, alle ore 21:43, Simon Pepping ha scritto:
>
>> Hi Dario,
>>
>> This is an interesting study. I need some more time to understand the
>> implications fully. At first sight you prove that for normal documents
>> the improvement is small. The paragraphs need to get long before your
>> strategy makes a difference. This is interesting, however, for long
>> chapters with many pages, as you mentioned in your earlier email.
>
> ATM I prefer to talk about paragraphs only: in the test I've done today
> I saw that for page breaking there is always just one active node. So
> it's clear why formatting the xsl-fo recommendation, that is over 400
> pages long but with short para, doesn't get faster. I need to
> investigate in this area.
>
>> It is clear why long paragraphs make a difference. Why does one- or
>> two-column layout make a large difference? Simply due to the twice
>> larger number of pages? I do not understand the left-aligned case. Is
>> this not just the same as a first-fit layout?
>
> Nice questions... I'm trying to understand this behavior too, the first
> time I've implemented the pruning on prototype was for another reason
> and I accidentally noticed the performance boost :)
> About one or two columns, or better, long or short lines: again, I don't
> know why, maybe it's just because the double number of breaks; I thing I
> noted is that for the same number of active node with shorter lines the
> gap between startLine and endLine is wider than with long lines. I don't
> know if this is meaningful.
In left-aligned mode this can be explained by looking at [1]: a line can
be cut if its natural length is between (line-width - 3 sp-width) and
line-width. So, at any break point in the paragraph, where the total
width is w, you can typeset the paragraph on a number of lines between
w / line-width (every line full) and w / (line-width - 3 sp-width)
(every line “empty”). This interval increases when the line width
decreases.
Example: sp-width = 0.1 cm, line-width = 17 cm, w = 1700 cm:
between 100 and 101 lines
with line-width = 8 cm (double column):
between 213 and 220 lines
Obviously the interval increases with the number of lines, but this
becomes unrealistic.
[1] http://wiki.apache.org/xmlgraphics-fop/LineBreaking
> About left-aligned or justified: with the latter *sometimes* having
> threshold=1.0 is enough (I think because of stretchable glues) so
> obviously the number of active node is reduced, while the former will
> always fall in threshold=20.0 and in force mode (talking about my
> tests). Anyway, while I'm not sure short/long lines really makes
> difference, it's evident that non justified text produce a lot more of
> active nodes than justified ones.
In justified mode, every line must fit the line width with quite a low
tolerance. In left-aligned mode the algorithm can be much more liberal,
and a rather big amount of blank space is allowed at the end of the line
in comparison to justify. Hence the higher number of active nodes for
ragged lines.
In justified mode, longer lines should lead to more break opportunities,
so more active nodes. Indeed, on every line there will be more spaces to
play with, giving the content more chance to have enough of
shrinkability or stretchability to fit on the line.
In left-aligned mode this is the other way around: spaces are not
stretchable so having more of them doesn’t help. However, at every break
opportunity a big stretchable space is added, that is likely to make the
content fit. The shorter the line, the more often that space is added,
the more break opportunities it results into.
<snip/>
[from another post]
> A really strange thing: is it theoretically possible that the amount
> of active nodes is greater than the number of knuth elements? As you
> can see in the graph, for short lines there are >14000 active nodes
> but only ~7000 knuth elements...
Line breaking is a bin-packing problem [2], so the potential number of
active nodes is exponential to the number of words you have in your
paragraph. So, yes, it’s normal to have more active nodes than elements
in the sequence.
[2] http://en.wikipedia.org/wiki/Bin_packing_problem
Vincent
Re: Active node tree pruning in FOP trunk
Posted by Andreas Delmelle <an...@telenet.be>.
On Oct 28, 2008, at 18:47, Dario Laera wrote:
> Hi Andreas!
>
> Il giorno 27/ott/08, alle ore 18:37, Andreas Delmelle ha scritto:
>
>> If I'm guessing correctly, a nice demonstration to see if there
>> are additional benefits to your proposal, would be to try pasting
>> the text of a short to medium-sized book into one single
>> monolithic fo:block. Don't use linefeed preservation, and plain
>> start-alignment. The number of break-possibilities the algorithm
>> has to consider becomes so large, that you easily need +500MB of
>> heap for about 40 pages. (I did this test some time ago, and then
>> I had to give the JVM at least 720MB of heap to render a block
>> with the content of Shakespeare's Hamlet.)
>>
>> Not a real-life use case, but always a very interesting test to
>> see whether the line-breaking algorithm has scaleability issues.
>
> I've put the "Pulp Fiction" scenario into a single block
> (Shakespeare, please, don't be offended :P)
Excellent choice... I'm sure he doesn't mind. :-)
> , tried with both start and justify alignment: it always fall down
> in forced mode and, without pruning, goes out of memory with a
> limit of 700MB (tried with both threshold=10|20). With pruning
> enabled (configured to be activated when there are more than 500
> active node) the maximum amount of memory is 70MB, the initial tree
> depth is 82 then reduced to 54. The resulting pdf is 69 pages long.
>
> I want to quote the thread regarding pruning in prototype as
> someone may have not read it: the pruning technique is a way to
> keep the active node set below a reasonable bound, but it's not the
> optimal solution. It is necessary for rendering pages asap in the
> prototype, but this is not the case in trunk.
Indeed. Page-rendering is obviously only triggered at the page-
breaking level, which in trunk is still performed after /all/ line-
breaking until a forced break, span change or end-of-page-sequence.
The scenario above, in trunk, currently produces excellent layout if
all pages are guaranteed to be the same width, but the results are
plain wrong when that width changes, say, due to a rotation. If you
insert a forced break before such a rotation, no problem.
FlowLM.getNextKnuthElements() will be called multiple times, with a
different ipd.
If not, then the inner (line-breaking) loop will simply continue,
accumulating possible lines with an incorrect base-width. The page-
breaking algorithm simply looks at the lines' height and never
questions the decisions made by the line-breaking algorithm, so
eventually just fills the pages with lines that are too long/short.
This is the key issue the prototype is meant to address/prove. The
jump from line- to page-breaking can occur more frequently, or IOW:
they can be more interleaved. Currently in trunk, this is limited to
the few exceptions named above: some event (forced break/span change/
end page-sequence) that enables to determine the total-fit page-
layout for all possible lines gathered from a preceding part, and
then resume for the remainder.
OTOH, there is always the plain fact that, at a certain point, the
line-breaking algorithm has yielded enough lines, so that a page-
break becomes unavoidable. At the moment, this simple fact is not
taken into account anywhere, IIRC. As long as none of the above
events occur, we simply keep asking for more lines/block elements.
> I developed it in trunk mainly to see whether this was working
> properly in the real world and to measure the performance gain. I
> think that a solution that can be enabled from the command line to
> improve performance in (not so) extreme cases would be a nice
> thing, but probably the pruning as it is now should be avoided.
Well, even if suboptimal at first, it has been a very interesting
experiment, so far. At least, it does point to some border-line
scenarios that could benefit from an approach in that direction.
> Another important reason is that it is totally unaware of fitness
> class: this is my fault, initially I didn't realized how fitness
> class was working and I ignored it. I need to study the argument to
> say if pruning can be adapted to work with fitness class.
Good luck!
Cheers
Andreas
Re: Active node tree pruning in FOP trunk
Posted by Dario Laera <la...@cs.unibo.it>.
Hi Andreas!
Il giorno 27/ott/08, alle ore 18:37, Andreas Delmelle ha scritto:
> If I'm guessing correctly, a nice demonstration to see if there are
> additional benefits to your proposal, would be to try pasting the
> text of a short to medium-sized book into one single monolithic
> fo:block. Don't use linefeed preservation, and plain start-
> alignment. The number of break-possibilities the algorithm has to
> consider becomes so large, that you easily need +500MB of heap for
> about 40 pages. (I did this test some time ago, and then I had to
> give the JVM at least 720MB of heap to render a block with the
> content of Shakespeare's Hamlet.)
>
> Not a real-life use case, but always a very interesting test to see
> whether the line-breaking algorithm has scaleability issues.
I've put the "Pulp Fiction" scenario into a single block (Shakespeare,
please, don't be offended :P), tried with both start and justify
alignment: it always fall down in forced mode and, without pruning,
goes out of memory with a limit of 700MB (tried with both threshold=10|
20). With pruning enabled (configured to be activated when there are
more than 500 active node) the maximum amount of memory is 70MB, the
initial tree depth is 82 then reduced to 54. The resulting pdf is 69
pages long.
I want to quote the thread regarding pruning in prototype as someone
may have not read it: the pruning technique is a way to keep the
active node set below a reasonable bound, but it's not the optimal
solution. It is necessary for rendering pages asap in the prototype,
but this is not the case in trunk. I developed it in trunk mainly to
see whether this was working properly in the real world and to measure
the performance gain. I think that a solution that can be enabled from
the command line to improve performance in (not so) extreme cases
would be a nice thing, but probably the pruning as it is now should be
avoided.
Another important reason is that it is totally unaware of fitness
class: this is my fault, initially I didn't realized how fitness class
was working and I ignored it. I need to study the argument to say if
pruning can be adapted to work with fitness class.
Dario
Re: Active node tree pruning in FOP trunk
Posted by Andreas Delmelle <an...@telenet.be>.
On Oct 24, 2008, at 17:34, Dario Laera wrote:
Hi Daerio,
(thought I'd finally chime in; I've been following your progress with
much interest, but did not feel I could contribute anything...)
> <snip />
> A really strange thing: is it theoretically possible that the
> amount of active nodes is greater than the number of knuth elements?
Yes, definitely. In the sense that a 'node' represents a (set of)
break-possibilit(y|ies), and without applying any pruning, all such
possibilities remain 'possible' the whole time, until the entire set
of actual breaks is known (= total-fit).
If I'm guessing correctly, a nice demonstration to see if there are
additional benefits to your proposal, would be to try pasting the
text of a short to medium-sized book into one single monolithic
fo:block. Don't use linefeed preservation, and plain start-alignment.
The number of break-possibilities the algorithm has to consider
becomes so large, that you easily need +500MB of heap for about 40
pages. (I did this test some time ago, and then I had to give the JVM
at least 720MB of heap to render a block with the content of
Shakespeare's Hamlet.)
Not a real-life use case, but always a very interesting test to see
whether the line-breaking algorithm has scaleability issues.
(in response to your earlier post)
> Initially I was setting TD to startLine, but then I noticed that in
> short line the pruning were activated when startLine was 5 and
> endLine was 44 (!), so I decided that the mean was a better choice.
> I can't explain how it's possible that the same text can be laid
> out in 5 short lines (I'm talking about 2 columns in A4) and in 44
> lines...
Yet another extreme case, but in the end, you can always put each
word in its own line, no? Or less strongly: there is bound to be a
possible layout that distributes the content over much more lines,
and still has good demerits, if you consider 'equal distribution of
content' to be a determining factor (which, IIC, holds for the
current implementation: ideally you will get lines/pages that are all
equally full).
I understand that it is strange to see, but if those possibilities
are kept 'active' until the definitive set of breaks has been
determined, then it would make sense you see something like that.
IIUC, it is only in the final phase that, if there are two layouts
(sets of break-possibilities) with equal demerits, then the one
yielding the least number of breaks is chosen.
(in response to a following post)
> The knuth list for a {left|right}-aligned paragraph is about twice
> the one of a justified paragraph. If you look at the methods
> addElementsFor* in TextLayoutManager class you can see that in some
> cases, depending on the alignment, a different number of glues/
> penalties can be added. This obviously makes the breaks
> possibilities growing, as you can see in the graph attached that
> compare the SAME xsl-fo except for alignment.
Yep, AFAIK, this is intended. Center-alignment should be slightly
worse even, since there, each possible line is preceded *and*
followed by a stretchable/shrinkable glue.
Cheers
Andreas
Re: Active node tree pruning in FOP trunk
Posted by Dario Laera <la...@cs.unibo.it>.
Il giorno 24/ott/08, alle ore 00:52, Dario Laera ha scritto:
>> It is clear why long paragraphs make a difference. Why does one- or
>> two-column layout make a large difference? Simply due to the twice
>> larger number of pages? I do not understand the left-aligned case. Is
>> this not just the same as a first-fit layout?
>
> Nice questions... I'm trying to understand this behavior too, the
> first time I've implemented the pruning on prototype was for another
> reason and I accidentally noticed the performance boost :)
> About one or two columns, or better, long or short lines: again, I
> don't know why, maybe it's just because the double number of breaks;
> I thing I noted is that for the same number of active node with
> shorter lines the gap between startLine and endLine is wider than
> with long lines. I don't know if this is meaningful.
I managed to get some graphs and now I'm more convinced that line
width matters. I've compared the file left-aligned, single block and
single column with the analogous file in two columns but with nearly
half of its words: in other words, they produce in the final layout
nearly the same number of breaks. The pruning was deactivated.
You can see the graph attached (startLine and endLine refers to the
left scale while activeNodeCount to the right scale): with the same
number of knuth elements (x axis) the short lines data grows much
faster than long lines data.
A really strange thing: is it theoretically possible that the amount
of active nodes is greater than the number of knuth elements? As you
can see in the graph, for short lines there are >14000 active nodes
but only ~7000 knuth elements...
Dario
Re: Active node tree pruning in FOP trunk
Posted by Dario Laera <la...@cs.unibo.it>.
Hi Simon,
thanks for your reply.
Il giorno 23/ott/08, alle ore 21:43, Simon Pepping ha scritto:
> Hi Dario,
>
> This is an interesting study. I need some more time to understand the
> implications fully. At first sight you prove that for normal documents
> the improvement is small. The paragraphs need to get long before your
> strategy makes a difference. This is interesting, however, for long
> chapters with many pages, as you mentioned in your earlier email.
ATM I prefer to talk about paragraphs only: in the test I've done
today I saw that for page breaking there is always just one active
node. So it's clear why formatting the xsl-fo recommendation, that is
over 400 pages long but with short para, doesn't get faster. I need to
investigate in this area.
> It is clear why long paragraphs make a difference. Why does one- or
> two-column layout make a large difference? Simply due to the twice
> larger number of pages? I do not understand the left-aligned case. Is
> this not just the same as a first-fit layout?
Nice questions... I'm trying to understand this behavior too, the
first time I've implemented the pruning on prototype was for another
reason and I accidentally noticed the performance boost :)
About one or two columns, or better, long or short lines: again, I
don't know why, maybe it's just because the double number of breaks; I
thing I noted is that for the same number of active node with shorter
lines the gap between startLine and endLine is wider than with long
lines. I don't know if this is meaningful.
About left-aligned or justified: with the latter *sometimes* having
threshold=1.0 is enough (I think because of stretchable glues) so
obviously the number of active node is reduced, while the former will
always fall in threshold=20.0 and in force mode (talking about my
tests). Anyway, while I'm not sure short/long lines really makes
difference, it's evident that non justified text produce a lot more of
active nodes than justified ones.
I hope to give you some decent answer in the next days. Precise
answers faster than mine would be also appreciated :P
> A more theoretical measurement would be the maximum number of active
> nodes.
In stat-nopruning.txt you find the maximum number of active nodes for
each paragraph without pruning (max value), th is threshold and lines
is the line count for the final layout. The last line for each test
file doesn't matter because is referred to page breaking.
Today I developed a kind of auto-activating/regulating pruning: when
the number of active nodes exceeds a threshold (I used 300) the
pruning get activated, and the treeDepth (TD) is chosen as the mean
between startLine and endLine. Initially I was setting TD to
startLine, but then I noticed that in short line the pruning were
activated when startLine was 5 and endLine was 44 (!), so I decided
that the mean was a better choice. I can't explain how it's possible
that the same text can be laid out in 5 short lines (I'm talking about
2 columns in A4) and in 44 lines...
You can find statistics from auto pruning in the other file attached.
I will try to produce accurate graphs that outlines the variables
trend, hoping that will help understanding some behaviors.
Dario
Re: Active node tree pruning in FOP trunk
Posted by Simon Pepping <sp...@leverkruid.eu>.
Hi Dario,
This is an interesting study. I need some more time to understand the
implications fully. At first sight you prove that for normal documents
the improvement is small. The paragraphs need to get long before your
strategy makes a difference. This is interesting, however, for long
chapters with many pages, as you mentioned in your earlier email.
It is clear why long paragraphs make a difference. Why does one- or
two-column layout make a large difference? Simply due to the twice
larger number of pages? I do not understand the left-aligned case. Is
this not just the same as a first-fit layout?
A more theoretical measurement would be the maximum number of active
nodes.
Regards, Simon
--
Simon Pepping
home page: http://www.leverkruid.eu