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/09 16:29:31 UTC
Layouts tree pruning for the prototype
Hi Vincent,
I wrote a new patch that implements a kind of ?-fit algorithm at page-
level. Let N be the page number for the last page layout obtained and
X a variable representing the depth of the layout tree I want to keep:
each time N gets increased (and its value is greater than X) I perform
a pruning of the layout tree choosing as new root the best layout for
the page with index N-X. Here is an example: the two graphs below
represents the trees of possible page layouts, in the first tree we
have N=4. If X was set to 3, it's time to prune the tree by choosing
the best subtree with a page-1 layout as root. In the example I
suppose that 1a has lower demerits than 1b, so I prune the tree from
1a. Alternatively I can choose the page-1 layout that has the best
leaf as child (actually not implemented).
____0____
/ \
*1a* 1b
/ \ |
/ \ |
2a 2b 2c
/ \ / \ / \
3a 3b 3c 3d 3e 3f
|
4a
1a
/ \
/ \
2a 2b
/ \ / \
3a 3b 3c 3d
|
4a
The X value determine the trade off between good aesthetic results and
time/memory performance: an high value should obtain results similar
to total-fit, a low value, say 1, should obtain the fastest performance.
This approach would allow to finalize (create the areas, render) the
page that has been chosen as new root and, if possible, to free memory
that is no more necessary (also FO-tree object and relative LM). This
possibility apart, it seems to me that in general the new prototype
can benefit from this approach.
The implementation adds a low overhead in terms of memory and
computation that is largely countervailed by the effect of pruning.
Each LM has a new pointer (prevPage, pointing to the previous page
layout in the path to the root) and the pageLM has three int for
determining the time of pruning (N-X). The PageLM updates this
integers each time a completedPart() is called. After calling the
completedPart a LM ask the PageLM if it's time to prune; if so it
performs the following operation on each active layout (AL):
* extract the N-X page by walking down the prevPage links (only X
step, not all layouts in this branch);
* if it is the best page layout found until now, create a new
ActiveLayouts object (eventually replacing the old one) and add to it
the AL;
* if it is the same best page layout, simply add the AL to the
ActiveLayouts object previously created;
* otherwise do nothing, this AL will be discarded.
Finally the new ActiveLayouts will replace the previous layout tree.
Comments are very welcome.
Dario
Re: Layouts tree pruning for the prototype
Posted by Vincent Hennebert <vh...@gmail.com>.
Hi Dario,
Just a short note to say that I haven’t forgotten your message, but that
it is still marked unread in my mail box...
As you will see in my other e-mail I’ve been quite busy lately, working
on tables and preparing documentation for community review. I’ll try to
have a look at your patch next week.
Thanks,
Vincent
Re: Layouts tree pruning for the prototype
Posted by Dario Laera <la...@cs.unibo.it>.
Hey, I was not criticizing the FOP team! I'm not frustrated and I
thought that you were not interested because I guessed that your
customers were pushing FOP in another direction (what if quality and
streaming are incompatible?), I realize that my goal is ambitious and
require lots o work, while most of you are volunteers that devote its
free time to FOP. I'm making some attempts, my knowledge is growing
but still far from being enough so any kind of comment is more than
welcome.
Unfortunately, from the next january I will have much less time to
work on FOP but I hope to continue contributing.
Dario
Il giorno 28/ott/08, alle ore 16:08, Jeremias Maerki ha scritto:
> Dario,
>
> we do care. The Bugzilla entry with the lowest ID that is still open
> is
> https://issues.apache.org/bugzilla/show_bug.cgi?id=1063 and actually
> targets exactly that topic. What Vincent and Simon are working on goes
> exactly into this direction (although implementing changing available
> IPD is the immediate front goal). I'm not sure what makes you think we
> are not interested in this. But you also need to see where we stand:
> Most funding for FOP comes from companies doing business-style
> documents
> (not more an a couple of dozen pages per page-sequence). Those not
> backed by some company probably just have too little free time to
> make a
> difference since this is such a huge task to get right. And then we're
> not a dozen active people anymore who can throw in huge amounts of
> time.
> People come and go. FOP desperately needs people like you who are not
> afraid to dive in and help. Dario, please don't get frustrated about
> the
> current state of FOP. Layout is a complex beast and implementating a
> highly complex specification like XSL-FO is not easy. Yes, there are
> different priorities. But that doesn't mean you cannot bring in yours
> and make a difference. The ASF is about collaboration. I very much
> like
> to see you working together with Vincent and Simon towards a better
> layout engine (like you already did during recent time).
> Unfortunately,
> I don't have enough time and energy to help out. I'm trying to keep up
> as best as I can and will offer constructive suggestions if I have
> any.
Re: Layouts tree pruning for the prototype
Posted by Jeremias Maerki <de...@jeremias-maerki.ch>.
Dario,
we do care. The Bugzilla entry with the lowest ID that is still open is
https://issues.apache.org/bugzilla/show_bug.cgi?id=1063 and actually
targets exactly that topic. What Vincent and Simon are working on goes
exactly into this direction (although implementing changing available
IPD is the immediate front goal). I'm not sure what makes you think we
are not interested in this. But you also need to see where we stand:
Most funding for FOP comes from companies doing business-style documents
(not more an a couple of dozen pages per page-sequence). Those not
backed by some company probably just have too little free time to make a
difference since this is such a huge task to get right. And then we're
not a dozen active people anymore who can throw in huge amounts of time.
People come and go. FOP desperately needs people like you who are not
afraid to dive in and help. Dario, please don't get frustrated about the
current state of FOP. Layout is a complex beast and implementating a
highly complex specification like XSL-FO is not easy. Yes, there are
different priorities. But that doesn't mean you cannot bring in yours
and make a difference. The ASF is about collaboration. I very much like
to see you working together with Vincent and Simon towards a better
layout engine (like you already did during recent time). Unfortunately,
I don't have enough time and energy to help out. I'm trying to keep up
as best as I can and will offer constructive suggestions if I have any.
On 28.10.2008 16:03:58 Dario Laera wrote:
<snip/>
> About my main goal (start imaging violins playing a moving song): I
> dream of a fo processor that can process document in "streaming" using
> a constant amount of memory regardless the size of the input document
> (stop imaging... :P). Probably some nice features needs to be dropped,
> or it's simply not possible, but I think that this is an interesting
> challenge. Anyway I'm far from reaching this goal.
>
> Why a streaming memory-efficient processor? Because industry need it:
> XML and related are beautiful technologies but sometimes too much
> academics and not production oriented. My company need it (I hope they
> will allow me to continue working on this...). A prove of the market
> interest in this sense is XF Ultrascale, a commercial fo processor
> that is claiming very low memory footprint [1]. It managed to obtain
> impressing results in some test, but it fails rendering my company
> test going out of memory. So it seems that a streaming processor still
> doesn't exists, even in commercial products.
> Obviously, you (and the FOP team) may consider streaming processing
> not interesting or a very low priority goal. You probably have targets
> different from mine. Let's consider pruning from the two points of view.
>
> Do you care about streaming processing?
> Pruning is *necessary* (along with mixed line/page breaking) if you
> want to render pages before the end of the document is reached while
> keeping output quality better than best fit.
>
> Don't you care about streaming processing?
> Pruning is a way of improving performance, surely not the more
> efficient. Keeping the amount of active nodes (with pruning or other
> solutions) is not necessary and maybe its benefits in the real life
> use make it not so desirable.
>
> I expect you and the FOP team don't care, at least ATM, about
> streaming processing. Anyway thank you for your feedback, you spent
> time for it.
>
>
> Dario
>
>
> [1] http://www.ecrion.com/Products/XFUltrascale/PerformanceComparisonGraph.aspx
>
Jeremias Maerki
Re: Layouts tree pruning for the prototype
Posted by Dario Laera <la...@cs.unibo.it>.
Il giorno 30/ott/08, alle ore 12:45, Vincent Hennebert ha scritto:
> Let me re-phrase your words to be sure I understand you correctly:
> once
> all of the layouts for line X have been found, you choose the best of
> ethem, select its corresponding ancestor layout for line 1, and
> discard
> all the other layouts for line 1, along with their descendants. Is
> that
> right?
Yes, it's right.
> It would be great if you could find a similar image to illustrate your
> heuristic. It’s important to ‘feel’ why it’s going to work.
Yes, it would be very nice, unfortunately ATM I don't have such an
image.
>
>
>
>>> I’m not sure there’s a real-life use case for such an optimization:
>>> people wanting speed will still be less happy than with plain best-
>>> fit,
>>> people wanting quality are ready to pay the price for it anyway.
>>
>> This is correct, but the total-total fit (document and paragraph)
>> algorithm the prototype is actually implementing may be very hungry
>> for
>> resource; in the document you recently wrote you mention a paragraph
>> that can be laid out in 4, 5 and 6 lines, but what if the document
>> contains many paragraphs like those I used to test the pruning in
>> trunk?
>> With pruning (that can easily turned on/off) you may partially keep
>> the
>> advantages of total total fit.
>
> Not if you apply the pruning method at the line level: indeed the
> first
> line is unlikely to be the same in, say, the 4-line version of
> a paragraph, as in its 5-line version. Since you’ll be keeping only
> one
> first line, it’s going to be the line belonging to the optimal final
> layout (say, the 5-line version).
>
> You might partially keep the advantages of total-total-fit if you
> apply
> pruning only at the page level, but that doesn’t sound right to me: if
> you apply pruning, that means that you are ready to make a
> compromise on
> quality in the interest of performance. But then you don’t need that
> level of detail brought by the several layout possibilities of
> a paragraph. Actually I expect that to be enabled only by people
> wanting
> quality at any price.
>
>
>>> A thing that might be interesting is to regularly cut down with the
>>> number of active nodes, every x lines: once all of the layouts for
>>> line x have been found, select the best active node and discard
>>> all the
>>> other ones. Then do that again for line x + x, 3x, 4x, etc. While
>>> similar, it has the advantage that every bunch of x lines will
>>> have been
>>> determined by a local total-fit method. In fact the paragraph will
>>> be
>>> made of a sum of local optimums, that may actually correspond to the
>>> global optimum or not. But even in that case, I’m not sure this is
>>> worth
>>> the additional complexity to a piece of code that’s already well
>>> complicated enough.
>>>
>>>
>>> Another option might be to set a limit to the amount of consumed
>>> memory
>>> (the number of active nodes, which in turn will have an effect on
>>> the
>>> processing time). Once the maximal number of active nodes is
>>> reached,
>>> start discarding the nodes with highest demerits. But it remains
>>> to see
>>> if such a heuristic proves to be efficient, and what limit to set
>>> up. As
>>> we can see in your other message, figures may change radically
>>> from one
>>> document to the other.
>>
>> I think that pruning provide a good trade off output-quality/
>> performance
>> without messing up so much the code (look at the patch for pruning in
>> trunk, it's trivial). Anyway pruning isn't the best way to cut down
>> the
>> number of active layouts, the solutions you propose are more
>> efficient,
>> but I wrote the pruning for another reason (more later) and here we
>> are
>> talking about its (positive) side effect.
>>
>>> In the end, I would be more inclined to implement a gradation in the
>>> layout quality (best fit, total fit over page sequence, total fit
>>> over
>>> document, total fit over document + paragraph line numbers, etc.),
>>> rather than one or several pruning method. I think it should be
>>> easier
>>> to implement yet provide enough flexibility to satisfy all kinds of
>>> users.
>>>
>>> Sorry if that sounds a bit negative. Since this is all but a simple
>>> topic, I may well have missed the interest of your approach. At
>>> any rate
>>> good ideas sometimes emerge from the oddest experiments, so feel
>>> free to
>>> continue your investigations...
>>
>> About my main goal (start imaging violins playing a moving song): I
>> dream of a fo processor that can process document in "streaming"
>> using a
>> constant amount of memory regardless the size of the input document
>> (stop imaging... :P). Probably some nice features needs to be
>> dropped,
>> or it's simply not possible, but I think that this is an interesting
>> challenge. Anyway I'm far from reaching this goal.
>>
>> Why a streaming memory-efficient processor? Because industry need it:
>> XML and related are beautiful technologies but sometimes too much
>> academics and not production oriented. My company need it (I hope
>> they
>> will allow me to continue working on this...). A prove of the market
>> interest in this sense is XF Ultrascale, a commercial fo processor
>> that
>> is claiming very low memory footprint [1]. It managed to obtain
>> impressing results in some test, but it fails rendering my company
>> test
>> going out of memory. So it seems that a streaming processor still
>> doesn't exists, even in commercial products.
>
> Hmmm, there are two different points then IMO:
> - rendering pages as soon as possible; I suddenly see the point of
> your
> pruning approach. However, for that case I believe best-fit is the way
> to go.
> - limiting memory consumption. This is a different issue IMO. I’d go
> for
> setting a maximum number of nodes and regularly discarding the nodes
> with highest demerits. The rationale being that, at the point where
> there are so many active nodes, it’s unlikely that the ones with
> highest demerits will actually lead to the final solution. Unless the
> content that’s following really is tricky (big unbreakable blocks or
> whatever).
It's not only a question of active nodes for memory consumption: how
big is the in memory representation of the FO tree of a 500MB
document? Three, four, five times the original size? And what about
all its LMs? Rendering pages ASAP (or at least building the area tree)
is necessary if you want minimize this footprint by freeing no more
necessary information. In that case the active node reduction is the
least of the benefit. The idea of applying pruning was born with this
in mind, and that's why I think pruning is good.
> Well, my hope is to find an approach that makes everyone happy, those
> wanting speed as well as those wanting quality, with a series of
> intermediate steps providing different trade-offs. The difference
> would
> be in the number of times the tree is pruned, but the pruning itself
> would always be the same: when the end of an object is reached (block,
> page-sequence, flow), select the best layout so far and discard the
> other ones. I believe this method will better integrate into the big
> picture.
>
> Now, the definitive way to compare approaches is to run them on
> a representative set of documents, and for each one record the
> processing time, memory consumption and demerits of the final layout.
> I’d be curious to see the difference between best-fit and the pruning
> approach then, but I’m not convinced it’s going to be that much.
>
>
>> Do you care about streaming processing?
>> Pruning is *necessary* (along with mixed line/page breaking) if you
>> want
>> to render pages before the end of the document is reached while
>> keeping
>> output quality better than best fit.
>>
>> Don't you care about streaming processing?
>> Pruning is a way of improving performance, surely not the more
>> efficient. Keeping the amount of active nodes (with pruning or other
>> solutions) is not necessary and maybe its benefits in the real life
>> use
>> make it not so desirable.
>>
>> I expect you and the FOP team don't care, at least ATM, about
>> streaming
>> processing. Anyway thank you for your feedback, you spent time for
>> it.
>
> So far, our answer to the streaming problem has simply been best-fit.
> Now, there may be two other solutions: your pruning approach, and my
> proposal of local total-fits (keeping the best layout every
> x lines/pages). It remains to see if the quality brought by those
> latter
> two methods is higher enough than best-fit to justify the additional
> processing resources (and code).
Best fit obviously would work, but I have the *feeling* that pruning
or local total fit would achieve better results. I need to prove it,
the demerits comparison you mentioned above would be very interesting
in this sense. I also have the feeling that pruning should work better
than local total fit in some cases: think if you do local total fit in
X lines in a paragraph that is X + 2 lines long: these last two lines
may be forced to high demerits. But, again, tests are needed to prove
the feelings.
Dario
Re: Layouts tree pruning for the prototype
Posted by Vincent Hennebert <vh...@gmail.com>.
Hi Dario,
Dario Laera wrote:
> Hi Vincent!
>
> Except for one concept, I may agree with you: it's all about points of
> view, what you are interested in. Read inline comments.
>
> Il giorno 27/ott/08, alle ore 18:01, Vincent Hennebert ha scritto:
>> I’ve finally had the time to look at your patch. IIUC your idea is to do
>> best-fit on the N but X lines, and total-fit on the final X lines.
>
> That's what the patch I wrote actually do, but it's not what I was
> intending. I fixed this problem in the pruning code I wrote for trunk by
> choosing the first node that have the best leaf as child. This is nor
> best fit, neither total fit: it's a step forward than best fit and a
> step backward than total fit.
Let me re-phrase your words to be sure I understand you correctly: once
all of the layouts for line X have been found, you choose the best of
them, select its corresponding ancestor layout for line 1, and discard
all the other layouts for line 1, along with their descendants. Is that
right?
> If X is big enough there's an high probability that the first line
> layout won't lead to bad layout for the immediate following lines:
> again, this is not best fit. And the last X lines are laid out in total
> fit. Do you agree?
Hmmm, I think I’m starting to see what you’re trying to achieve. Giving
your rationale below helped anyway. Let me re-phrase again: since the
best layout for line X is made of this particular first line, there’s
a reasonable chance that that first line won’t lead to a bad final
layout. That seems to make sense. But since starting from line X you’re
doing this pruning every line, I’m not really sure this heuristic can
actually be explained like this.
The problem if we can’t find a good image to explain a heuristic, is
that it becomes difficult to convince ourselves that this heuristic does
the job (here, limiting memory consumption while having a better layout
quality than best-fit). First-fit and best-fit are easily illustrated:
imagine you have to go from city A to city B, making night breaks in
hotels, driving between 8 and 10 hours a day.
First-fit is: stop at the first hotel you can find that fits within that
hours of driving interval. On the next day, same. And so on, until B is
reached.
Best-fit is: find all of the hotels that fit in the interval; select the
one whose corresponding journey lowers petrol consumption (that’s
important these days ;-) ). Next day, same, etc.
Total-fit is: ok, on the first two days we’ll have to cross that huge
mountain chain, it’s gonna be slow, painful, tiring and petrol-
consuming. But after that it’s all brand new empty flat motorway until
the end. Piece of cake.
It would be great if you could find a similar image to illustrate your
heuristic. It’s important to ‘feel’ why it’s going to work.
>> I’m not sure there’s a real-life use case for such an optimization:
>> people wanting speed will still be less happy than with plain best-fit,
>> people wanting quality are ready to pay the price for it anyway.
>
> This is correct, but the total-total fit (document and paragraph)
> algorithm the prototype is actually implementing may be very hungry for
> resource; in the document you recently wrote you mention a paragraph
> that can be laid out in 4, 5 and 6 lines, but what if the document
> contains many paragraphs like those I used to test the pruning in trunk?
> With pruning (that can easily turned on/off) you may partially keep the
> advantages of total total fit.
Not if you apply the pruning method at the line level: indeed the first
line is unlikely to be the same in, say, the 4-line version of
a paragraph, as in its 5-line version. Since you’ll be keeping only one
first line, it’s going to be the line belonging to the optimal final
layout (say, the 5-line version).
You might partially keep the advantages of total-total-fit if you apply
pruning only at the page level, but that doesn’t sound right to me: if
you apply pruning, that means that you are ready to make a compromise on
quality in the interest of performance. But then you don’t need that
level of detail brought by the several layout possibilities of
a paragraph. Actually I expect that to be enabled only by people wanting
quality at any price.
>> A thing that might be interesting is to regularly cut down with the
>> number of active nodes, every x lines: once all of the layouts for
>> line x have been found, select the best active node and discard all the
>> other ones. Then do that again for line x + x, 3x, 4x, etc. While
>> similar, it has the advantage that every bunch of x lines will have been
>> determined by a local total-fit method. In fact the paragraph will be
>> made of a sum of local optimums, that may actually correspond to the
>> global optimum or not. But even in that case, I’m not sure this is worth
>> the additional complexity to a piece of code that’s already well
>> complicated enough.
>>
>>
>> Another option might be to set a limit to the amount of consumed memory
>> (the number of active nodes, which in turn will have an effect on the
>> processing time). Once the maximal number of active nodes is reached,
>> start discarding the nodes with highest demerits. But it remains to see
>> if such a heuristic proves to be efficient, and what limit to set up. As
>> we can see in your other message, figures may change radically from one
>> document to the other.
>
> I think that pruning provide a good trade off output-quality/performance
> without messing up so much the code (look at the patch for pruning in
> trunk, it's trivial). Anyway pruning isn't the best way to cut down the
> number of active layouts, the solutions you propose are more efficient,
> but I wrote the pruning for another reason (more later) and here we are
> talking about its (positive) side effect.
>
>> In the end, I would be more inclined to implement a gradation in the
>> layout quality (best fit, total fit over page sequence, total fit over
>> document, total fit over document + paragraph line numbers, etc.),
>> rather than one or several pruning method. I think it should be easier
>> to implement yet provide enough flexibility to satisfy all kinds of
>> users.
>>
>> Sorry if that sounds a bit negative. Since this is all but a simple
>> topic, I may well have missed the interest of your approach. At any rate
>> good ideas sometimes emerge from the oddest experiments, so feel free to
>> continue your investigations...
>
> About my main goal (start imaging violins playing a moving song): I
> dream of a fo processor that can process document in "streaming" using a
> constant amount of memory regardless the size of the input document
> (stop imaging... :P). Probably some nice features needs to be dropped,
> or it's simply not possible, but I think that this is an interesting
> challenge. Anyway I'm far from reaching this goal.
>
> Why a streaming memory-efficient processor? Because industry need it:
> XML and related are beautiful technologies but sometimes too much
> academics and not production oriented. My company need it (I hope they
> will allow me to continue working on this...). A prove of the market
> interest in this sense is XF Ultrascale, a commercial fo processor that
> is claiming very low memory footprint [1]. It managed to obtain
> impressing results in some test, but it fails rendering my company test
> going out of memory. So it seems that a streaming processor still
> doesn't exists, even in commercial products.
Hmmm, there are two different points then IMO:
- rendering pages as soon as possible; I suddenly see the point of your
pruning approach. However, for that case I believe best-fit is the way
to go.
- limiting memory consumption. This is a different issue IMO. I’d go for
setting a maximum number of nodes and regularly discarding the nodes
with highest demerits. The rationale being that, at the point where
there are so many active nodes, it’s unlikely that the ones with
highest demerits will actually lead to the final solution. Unless the
content that’s following really is tricky (big unbreakable blocks or
whatever).
> Obviously, you (and the FOP team) may consider streaming processing not
> interesting or a very low priority goal. You probably have targets
> different from mine. Let's consider pruning from the two points of view.
Well, my hope is to find an approach that makes everyone happy, those
wanting speed as well as those wanting quality, with a series of
intermediate steps providing different trade-offs. The difference would
be in the number of times the tree is pruned, but the pruning itself
would always be the same: when the end of an object is reached (block,
page-sequence, flow), select the best layout so far and discard the
other ones. I believe this method will better integrate into the big
picture.
Now, the definitive way to compare approaches is to run them on
a representative set of documents, and for each one record the
processing time, memory consumption and demerits of the final layout.
I’d be curious to see the difference between best-fit and the pruning
approach then, but I’m not convinced it’s going to be that much.
> Do you care about streaming processing?
> Pruning is *necessary* (along with mixed line/page breaking) if you want
> to render pages before the end of the document is reached while keeping
> output quality better than best fit.
>
> Don't you care about streaming processing?
> Pruning is a way of improving performance, surely not the more
> efficient. Keeping the amount of active nodes (with pruning or other
> solutions) is not necessary and maybe its benefits in the real life use
> make it not so desirable.
>
> I expect you and the FOP team don't care, at least ATM, about streaming
> processing. Anyway thank you for your feedback, you spent time for it.
So far, our answer to the streaming problem has simply been best-fit.
Now, there may be two other solutions: your pruning approach, and my
proposal of local total-fits (keeping the best layout every
x lines/pages). It remains to see if the quality brought by those latter
two methods is higher enough than best-fit to justify the additional
processing resources (and code).
Vincent
Re: Layouts tree pruning for the prototype
Posted by Dario Laera <la...@cs.unibo.it>.
Hi Vincent!
Except for one concept, I may agree with you: it's all about points of
view, what you are interested in. Read inline comments.
Il giorno 27/ott/08, alle ore 18:01, Vincent Hennebert ha scritto:
> I’ve finally had the time to look at your patch. IIUC your idea is
> to do
> best-fit on the N but X lines, and total-fit on the final X lines.
That's what the patch I wrote actually do, but it's not what I was
intending. I fixed this problem in the pruning code I wrote for trunk
by choosing the first node that have the best leaf as child. This is
nor best fit, neither total fit: it's a step forward than best fit and
a step backward than total fit.
If X is big enough there's an high probability that the first line
layout won't lead to bad layout for the immediate following lines:
again, this is not best fit. And the last X lines are laid out in
total fit. Do you agree?
> I’m not sure there’s a real-life use case for such an optimization:
> people wanting speed will still be less happy than with plain best-
> fit,
> people wanting quality are ready to pay the price for it anyway.
This is correct, but the total-total fit (document and paragraph)
algorithm the prototype is actually implementing may be very hungry
for resource; in the document you recently wrote you mention a
paragraph that can be laid out in 4, 5 and 6 lines, but what if the
document contains many paragraphs like those I used to test the
pruning in trunk? With pruning (that can easily turned on/off) you may
partially keep the advantages of total total fit.
> A thing that might be interesting is to regularly cut down with the
> number of active nodes, every x lines: once all of the layouts for
> line x have been found, select the best active node and discard all
> the
> other ones. Then do that again for line x + x, 3x, 4x, etc. While
> similar, it has the advantage that every bunch of x lines will have
> been
> determined by a local total-fit method. In fact the paragraph will be
> made of a sum of local optimums, that may actually correspond to the
> global optimum or not. But even in that case, I’m not sure this is
> worth
> the additional complexity to a piece of code that’s already well
> complicated enough.
>
>
> Another option might be to set a limit to the amount of consumed
> memory
> (the number of active nodes, which in turn will have an effect on the
> processing time). Once the maximal number of active nodes is reached,
> start discarding the nodes with highest demerits. But it remains to
> see
> if such a heuristic proves to be efficient, and what limit to set
> up. As
> we can see in your other message, figures may change radically from
> one
> document to the other.
I think that pruning provide a good trade off output-quality/
performance without messing up so much the code (look at the patch for
pruning in trunk, it's trivial). Anyway pruning isn't the best way to
cut down the number of active layouts, the solutions you propose are
more efficient, but I wrote the pruning for another reason (more
later) and here we are talking about its (positive) side effect.
> In the end, I would be more inclined to implement a gradation in the
> layout quality (best fit, total fit over page sequence, total fit over
> document, total fit over document + paragraph line numbers, etc.),
> rather than one or several pruning method. I think it should be easier
> to implement yet provide enough flexibility to satisfy all kinds of
> users.
>
> Sorry if that sounds a bit negative. Since this is all but a simple
> topic, I may well have missed the interest of your approach. At any
> rate
> good ideas sometimes emerge from the oddest experiments, so feel
> free to
> continue your investigations...
About my main goal (start imaging violins playing a moving song): I
dream of a fo processor that can process document in "streaming" using
a constant amount of memory regardless the size of the input document
(stop imaging... :P). Probably some nice features needs to be dropped,
or it's simply not possible, but I think that this is an interesting
challenge. Anyway I'm far from reaching this goal.
Why a streaming memory-efficient processor? Because industry need it:
XML and related are beautiful technologies but sometimes too much
academics and not production oriented. My company need it (I hope they
will allow me to continue working on this...). A prove of the market
interest in this sense is XF Ultrascale, a commercial fo processor
that is claiming very low memory footprint [1]. It managed to obtain
impressing results in some test, but it fails rendering my company
test going out of memory. So it seems that a streaming processor still
doesn't exists, even in commercial products.
Obviously, you (and the FOP team) may consider streaming processing
not interesting or a very low priority goal. You probably have targets
different from mine. Let's consider pruning from the two points of view.
Do you care about streaming processing?
Pruning is *necessary* (along with mixed line/page breaking) if you
want to render pages before the end of the document is reached while
keeping output quality better than best fit.
Don't you care about streaming processing?
Pruning is a way of improving performance, surely not the more
efficient. Keeping the amount of active nodes (with pruning or other
solutions) is not necessary and maybe its benefits in the real life
use make it not so desirable.
I expect you and the FOP team don't care, at least ATM, about
streaming processing. Anyway thank you for your feedback, you spent
time for it.
Dario
[1] http://www.ecrion.com/Products/XFUltrascale/PerformanceComparisonGraph.aspx
Re: Layouts tree pruning for the prototype
Posted by Vincent Hennebert <vh...@gmail.com>.
Hi Dario,
I’ve finally had the time to look at your patch. IIUC your idea is to do
best-fit on the N but X lines, and total-fit on the final X lines.
I have to say, I’m a bit doubtful of the interest of this approach in
terms of performance and quality, compared to a plain best-fit version
(see below):
Dario Laera wrote:
> Hi Vincent,
>
> I wrote a new patch that implements a kind of ?-fit algorithm at
> page-level. Let N be the page number for the last page layout obtained
> and X a variable representing the depth of the layout tree I want to
> keep: each time N gets increased (and its value is greater than X) I
> perform a pruning of the layout tree choosing as new root the best
> layout for the page with index N-X. Here is an example: the two graphs
> below represents the trees of possible page layouts, in the first tree
> we have N=4. If X was set to 3, it's time to prune the tree by choosing
> the best subtree with a page-1 layout as root. In the example I suppose
> that 1a has lower demerits than 1b, so I prune the tree from 1a.
> Alternatively I can choose the page-1 layout that has the best leaf as
> child (actually not implemented).
>
> ____0____
> / \
> *1a* 1b
> / \ |
> / \ |
> 2a 2b 2c
> / \ / \ / \
> 3a 3b 3c 3d 3e 3f
> |
> 4a
>
> 1a
> / \
> / \
> 2a 2b
> / \ / \
> 3a 3b 3c 3d
> |
> 4a
In this example (X = 3), total-fit is performed until a first layout for
line 4 is found. Then the best first line is chosen and the tree is cut
accordingly (1b and descendants). When a first layout for line 5 is
found, same again: total-fit is performed on lines 2 to 5, giving the
tree that has 1a as root, then the best second line is chosen and the
rest is cut off (say, 2a and descendants). And so on and so on.
So, roughly speaking, given a paragraph of n lines, you’re doing (n - x)
“local”, x line wide total fits, along with (n - x) best fits. In the
end result, (n - x) lines will have been chosen using the best-fit
method (despite the total fits running in parallel), and the final
x lines using a total fit using line (n - x - 1) as the root.
This sounds like a lot of work for a result that in the end may not look
much better than best-fit. Also, the visual result might look strange,
with the final lines looking more “even” than the starting ones (but
this has to be confirmed on real testcases).
I’m not sure there’s a real-life use case for such an optimization:
people wanting speed will still be less happy than with plain best-fit,
people wanting quality are ready to pay the price for it anyway.
A thing that might be interesting is to regularly cut down with the
number of active nodes, every x lines: once all of the layouts for
line x have been found, select the best active node and discard all the
other ones. Then do that again for line x + x, 3x, 4x, etc. While
similar, it has the advantage that every bunch of x lines will have been
determined by a local total-fit method. In fact the paragraph will be
made of a sum of local optimums, that may actually correspond to the
global optimum or not. But even in that case, I’m not sure this is worth
the additional complexity to a piece of code that’s already well
complicated enough.
Another option might be to set a limit to the amount of consumed memory
(the number of active nodes, which in turn will have an effect on the
processing time). Once the maximal number of active nodes is reached,
start discarding the nodes with highest demerits. But it remains to see
if such a heuristic proves to be efficient, and what limit to set up. As
we can see in your other message, figures may change radically from one
document to the other.
In the end, I would be more inclined to implement a gradation in the
layout quality (best fit, total fit over page sequence, total fit over
document, total fit over document + paragraph line numbers, etc.),
rather than one or several pruning method. I think it should be easier
to implement yet provide enough flexibility to satisfy all kinds of
users.
Sorry if that sounds a bit negative. Since this is all but a simple
topic, I may well have missed the interest of your approach. At any rate
good ideas sometimes emerge from the oddest experiments, so feel free to
continue your investigations...
> The X value determine the trade off between good aesthetic results and
> time/memory performance: an high value should obtain results similar to
> total-fit, a low value, say 1, should obtain the fastest performance.
>
> This approach would allow to finalize (create the areas, render) the
> page that has been chosen as new root and, if possible, to free memory
> that is no more necessary (also FO-tree object and relative LM). This
> possibility apart, it seems to me that in general the new prototype can
> benefit from this approach.
>
> The implementation adds a low overhead in terms of memory and
> computation that is largely countervailed by the effect of pruning. Each
> LM has a new pointer (prevPage, pointing to the previous page layout in
> the path to the root) and the pageLM has three int for determining the
> time of pruning (N-X). The PageLM updates this integers each time a
> completedPart() is called. After calling the completedPart a LM ask the
> PageLM if it's time to prune; if so it performs the following operation
> on each active layout (AL):
>
> * extract the N-X page by walking down the prevPage links (only X step,
> not all layouts in this branch);
> * if it is the best page layout found until now, create a new
> ActiveLayouts object (eventually replacing the old one) and add to it
> the AL;
> * if it is the same best page layout, simply add the AL to the
> ActiveLayouts object previously created;
> * otherwise do nothing, this AL will be discarded.
>
> Finally the new ActiveLayouts will replace the previous layout tree.
>
>
> Comments are very welcome.
> Dario
Vincent