xmlgraphics-fop-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Andreas Delmelle <andreas.delme...@telenet.be>
Subject Re: Active node tree pruning in FOP trunk
Date Mon, 27 Oct 2008 17:37:56 GMT
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.



View raw message