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


##########
# max = max value for activeNodeCount
# sl = startLine
# el = endLine
# line = line number of the node that has exceeded the activeNodeCount
# threshold
# td = the treeDepth to be used
#
########## Trasform fo/my_franklin_rep-1blk-2c-jus.fo without pruning
Active pruning max = 301        sl = 59 el = 93 line = 66       td = 76
REDUCE pruning max = 338        sl = 76 el = 117        line = 78       td = 50
findBreakinPoints max = 368     th = 20.0       lines = 544     forced
findBreakinPoints max = 1       th = 1.0        lines = 15      forced
       30.06 real         7.92 user         0.73 sys
****************************************************
########## Trasform fo/my_franklin_rep-1blk-2c.fo without pruning
Active pruning max = 301        sl = 5  el = 44 line = 24       td = 24
REDUCE pruning max = 301        sl = 30 el = 65 line = 56       td = 16
REDUCE pruning max = 302        sl = 30 el = 65 line = 57       td = 10
REDUCE pruning max = 301        sl = 35 el = 67 line = 63       td = 6
REDUCE pruning max = 302        sl = 35 el = 67 line = 64       td = 4
findBreakinPoints max = 1446    th = 20.0       lines = 561     forced
findBreakinPoints max = 1       th = 1.0        lines = 16      forced
       31.04 real         8.07 user         0.74 sys
****************************************************
########## Trasform fo/my_franklin_rep-1blk-jus.fo without pruning
findBreakinPoints max = 61      th = 1.0        lines = 240
findBreakinPoints max = 1       th = 1.0        lines = 7       forced
       28.88 real         7.05 user         0.72 sys
****************************************************
########## Trasform fo/my_franklin_rep-1blk.fo without pruning
Active pruning max = 301        sl = 12 el = 30 line = 29       td = 21
REDUCE pruning max = 301        sl = 57 el = 74 line = 59       td = 14
REDUCE pruning max = 301        sl = 69 el = 89 line = 83       td = 8
findBreakinPoints max = 499     th = 20.0       lines = 247     forced
findBreakinPoints max = 1       th = 1.0        lines = 7       forced
       31.29 real         7.83 user         0.75 sys
****************************************************
########## Trasform fo/my_franklin_rep-2c-jus.fo without pruning
findBreakinPoints max = 230     th = 20.0       lines = 37      forced
findBreakinPoints max = 288     th = 20.0       lines = 53      forced
Active pruning max = 301        sl = 58 el = 90 line = 83       td = 74
findBreakinPoints max = 365     th = 20.0       lines = 85      forced
findBreakinPoints max = 288     th = 20.0       lines = 53      forced
Active pruning max = 301        sl = 58 el = 90 line = 83       td = 74
findBreakinPoints max = 365     th = 20.0       lines = 85      forced
findBreakinPoints max = 288     th = 20.0       lines = 53      forced
Active pruning max = 301        sl = 58 el = 90 line = 83       td = 74
findBreakinPoints max = 365     th = 20.0       lines = 85      forced
findBreakinPoints max = 288     th = 20.0       lines = 53      forced
findBreakinPoints max = 246     th = 20.0       lines = 48      forced
findBreakinPoints max = 1       th = 1.0        lines = 15      forced
       34.08 real         8.48 user         0.78 sys
****************************************************
########## Trasform fo/my_franklin_rep-2c.fo without pruning
Active pruning max = 301        sl = 5  el = 44 line = 24       td = 24
REDUCE pruning max = 301        sl = 30 el = 65 line = 56       td = 16
REDUCE pruning max = 302        sl = 30 el = 65 line = 57       td = 10
REDUCE pruning max = 301        sl = 35 el = 67 line = 63       td = 6
REDUCE pruning max = 302        sl = 35 el = 67 line = 64       td = 4
findBreakinPoints max = 1446    th = 20.0       lines = 38      forced
Active pruning max = 301        sl = 6  el = 47 line = 44       td = 26
REDUCE pruning max = 301        sl = 32 el = 71 line = 50       td = 16
REDUCE pruning max = 302        sl = 32 el = 71 line = 51       td = 10
REDUCE pruning max = 303        sl = 32 el = 71 line = 52       td = 6
findBreakinPoints max = 1289    th = 20.0       lines = 54      forced
Active pruning max = 301        sl = 5  el = 42 line = 39       td = 23
REDUCE pruning max = 301        sl = 29 el = 70 line = 31       td = 14
REDUCE pruning max = 301        sl = 36 el = 77 line = 74       td = 8
REDUCE pruning max = 301        sl = 42 el = 79 line = 52       td = 4
findBreakinPoints max = 1307    th = 20.0       lines = 87      forced
Active pruning max = 301        sl = 6  el = 47 line = 44       td = 26
REDUCE pruning max = 301        sl = 32 el = 71 line = 50       td = 16
REDUCE pruning max = 302        sl = 32 el = 71 line = 51       td = 10
REDUCE pruning max = 303        sl = 32 el = 71 line = 52       td = 6
findBreakinPoints max = 1289    th = 20.0       lines = 54      forced
Active pruning max = 301        sl = 5  el = 42 line = 39       td = 23
REDUCE pruning max = 301        sl = 29 el = 70 line = 31       td = 14
REDUCE pruning max = 301        sl = 36 el = 77 line = 74       td = 8
REDUCE pruning max = 301        sl = 42 el = 79 line = 52       td = 4
findBreakinPoints max = 1307    th = 20.0       lines = 87      forced
Active pruning max = 301        sl = 6  el = 47 line = 44       td = 26
REDUCE pruning max = 301        sl = 32 el = 71 line = 50       td = 16
REDUCE pruning max = 302        sl = 32 el = 71 line = 51       td = 10
REDUCE pruning max = 303        sl = 32 el = 71 line = 52       td = 6
findBreakinPoints max = 1289    th = 20.0       lines = 54      forced
Active pruning max = 301        sl = 5  el = 42 line = 39       td = 23
REDUCE pruning max = 301        sl = 29 el = 70 line = 31       td = 14
REDUCE pruning max = 301        sl = 36 el = 77 line = 74       td = 8
REDUCE pruning max = 301        sl = 42 el = 79 line = 52       td = 4
findBreakinPoints max = 1307    th = 20.0       lines = 87      forced
Active pruning max = 301        sl = 6  el = 47 line = 44       td = 26
REDUCE pruning max = 301        sl = 32 el = 71 line = 50       td = 16
REDUCE pruning max = 302        sl = 32 el = 71 line = 51       td = 10
REDUCE pruning max = 303        sl = 32 el = 71 line = 52       td = 6
findBreakinPoints max = 1289    th = 20.0       lines = 54      forced
Active pruning max = 301        sl = 5  el = 42 line = 39       td = 23
REDUCE pruning max = 301        sl = 29 el = 70 line = 31       td = 14
REDUCE pruning max = 301        sl = 36 el = 77 line = 74       td = 8
REDUCE pruning max = 301        sl = 42 el = 79 line = 52       td = 4
findBreakinPoints max = 1307    th = 20.0       lines = 49      forced
findBreakinPoints max = 1       th = 1.0        lines = 16      forced
       39.50 real        10.32 user         0.78 sys
****************************************************
########## Trasform fo/my_franklin_rep-jus.fo without pruning
findBreakinPoints max = 7       th = 1.0        lines = 16
findBreakinPoints max = 7       th = 1.0        lines = 24
findBreakinPoints max = 18      th = 1.0        lines = 37
findBreakinPoints max = 7       th = 1.0        lines = 24
findBreakinPoints max = 18      th = 1.0        lines = 37
findBreakinPoints max = 7       th = 1.0        lines = 24
findBreakinPoints max = 18      th = 1.0        lines = 37
findBreakinPoints max = 7       th = 1.0        lines = 24
findBreakinPoints max = 9       th = 1.0        lines = 21
findBreakinPoints max = 1       th = 1.0        lines = 7       forced
       30.28 real         7.10 user         0.74 sys
****************************************************
########## Trasform fo/my_franklin_rep.fo without pruning
Active pruning max = 301        sl = 12 el = 30 line = 29       td = 21
findBreakinPoints max = 447     th = 20.0       lines = 17      forced
Active pruning max = 301        sl = 11 el = 29 line = 23       td = 20
findBreakinPoints max = 534     th = 20.0       lines = 24      forced
Active pruning max = 301        sl = 11 el = 28 line = 17       td = 19
findBreakinPoints max = 478     th = 20.0       lines = 38      forced
Active pruning max = 301        sl = 11 el = 29 line = 23       td = 20
findBreakinPoints max = 534     th = 20.0       lines = 24      forced
Active pruning max = 301        sl = 11 el = 28 line = 17       td = 19
findBreakinPoints max = 478     th = 20.0       lines = 38      forced
Active pruning max = 301        sl = 11 el = 29 line = 23       td = 20
findBreakinPoints max = 534     th = 20.0       lines = 24      forced
Active pruning max = 301        sl = 11 el = 28 line = 17       td = 19
findBreakinPoints max = 478     th = 20.0       lines = 38      forced
Active pruning max = 301        sl = 11 el = 29 line = 23       td = 20
findBreakinPoints max = 534     th = 20.0       lines = 24      forced
Active pruning max = 301        sl = 11 el = 28 line = 17       td = 19
findBreakinPoints max = 478     th = 20.0       lines = 22      forced
findBreakinPoints max = 1       th = 1.0        lines = 7       forced
       35.80 real         8.67 user         0.76 sys
****************************************************
########## Transform fo/my_franklin_rep-1blk-2c-jus.fo without pruning
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 2       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 3302    th = 20.0       lines = 544     forced
findBreakinPoints max = 1       th = 1.0        lines = 15      forced
       18.90 real        14.33 user         0.90 sys
****************************************************
########## Transform fo/my_franklin_rep-1blk-2c.fo without pruning
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 2       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 36400   th = 20.0       lines = 561     forced
findBreakinPoints max = 1       th = 1.0        lines = 16      forced
      214.97 real       142.12 user         5.03 sys
****************************************************
########## Transform fo/my_franklin_rep-1blk-jus.fo without pruning
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 61      th = 1.0        lines = 240
findBreakinPoints max = 1       th = 1.0        lines = 7       forced
       12.66 real         6.65 user         0.68 sys
****************************************************
########## Transform fo/my_franklin_rep-1blk.fo without pruning
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 2       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 7546    th = 20.0       lines = 247     forced
findBreakinPoints max = 1       th = 1.0        lines = 7       forced
       39.35 real        32.49 user         1.05 sys
****************************************************
########## Transform fo/my_franklin_rep-2c-jus.fo without pruning
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 2       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 230     th = 20.0       lines = 37      forced
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 288     th = 20.0       lines = 53      forced
findBreakinPoints max = 2       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 2       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 518     th = 20.0       lines = 85      forced
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 288     th = 20.0       lines = 53      forced
findBreakinPoints max = 2       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 2       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 518     th = 20.0       lines = 85      forced
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 288     th = 20.0       lines = 53      forced
findBreakinPoints max = 2       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 2       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 518     th = 20.0       lines = 85      forced
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 288     th = 20.0       lines = 53      forced
findBreakinPoints max = 2       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 2       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 246     th = 20.0       lines = 48      forced
findBreakinPoints max = 1       th = 1.0        lines = 15      forced
       12.42 real         7.94 user         0.67 sys
****************************************************
########## Transform fo/my_franklin_rep-2c.fo without pruning
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 2       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 2394    th = 20.0       lines = 39      forced
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 3159    th = 20.0       lines = 54      forced
findBreakinPoints max = 2       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 3       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 5721    th = 20.0       lines = 87      forced
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 3159    th = 20.0       lines = 54      forced
findBreakinPoints max = 2       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 3       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 5721    th = 20.0       lines = 87      forced
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 3159    th = 20.0       lines = 54      forced
findBreakinPoints max = 2       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 3       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 5721    th = 20.0       lines = 87      forced
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 3159    th = 20.0       lines = 54      forced
findBreakinPoints max = 2       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 3       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 2917    th = 20.0       lines = 49      forced
findBreakinPoints max = 1       th = 1.0        lines = 16      forced
       27.32 real        20.93 user         0.81 sys
****************************************************
########## Transform fo/my_franklin_rep-jus.fo without pruning
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 7       th = 1.0        lines = 16
findBreakinPoints max = 3       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 7       th = 1.0        lines = 24
findBreakinPoints max = 4       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 18      th = 1.0        lines = 37
findBreakinPoints max = 3       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 7       th = 1.0        lines = 24
findBreakinPoints max = 4       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 18      th = 1.0        lines = 37
findBreakinPoints max = 3       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 7       th = 1.0        lines = 24
findBreakinPoints max = 4       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 18      th = 1.0        lines = 37
findBreakinPoints max = 3       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 7       th = 1.0        lines = 24
findBreakinPoints max = 4       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 9       th = 1.0        lines = 21
findBreakinPoints max = 1       th = 1.0        lines = 7       forced
        9.98 real         6.63 user         0.63 sys
****************************************************
########## Transform fo/my_franklin_rep.fo without pruning
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 2       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 447     th = 20.0       lines = 17      forced
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 673     th = 20.0       lines = 24      forced
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 1105    th = 20.0       lines = 38      forced
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 673     th = 20.0       lines = 24      forced
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 1105    th = 20.0       lines = 38      forced
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 673     th = 20.0       lines = 24      forced
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 1105    th = 20.0       lines = 38      forced
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 673     th = 20.0       lines = 24      forced
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 1       th = 1.0        lines = //      RETRY!
findBreakinPoints max = 572     th = 20.0       lines = 22      forced
findBreakinPoints max = 1       th = 1.0        lines = 7       forced
       14.29 real         9.76 user         0.66 sys
****************************************************





Reply via email to