Oscillation

[PaulRambags]

In the process of generating volumes, the formatter uses iterations to come to a stable state where nothing is dirty anymore. This process of trying again may end up oscillating, that is, iteration n is doing exactly the same as iteration n - 2 for some n > 0.
This should be changed so that the volume generating process always ends successfully.

Currently I only have a very large example where this happens.
@todo: Provide a small example.

[bertfrees]

It is important to distinguish two things. First there is the computation of an optimal volume splitting, which is an iterative process that uses the result of one iteration to adapt the splitting of the next iteration.

Then there is the CrossReferenceHandler which keeps information about the previous iteration in order to do two things:

• use this information to generate content in the next iteration because up to date information is not available (think forward page references etc.), and
• compare two iterations in order to check whether the process has stabilized.

The two processes happen at the same time but are not really related. The "dirty" state only concerns the CrossReferenceHandler part and has not so much to do with the volume optimization (except for the information about the volume count and volume sizes which is also stored in the CRH).

The volume optimization has some kind of guard against oscillations build in. The CRH parts doesn't so it's more likely this is where the problem lies.

On the other hand the fact that you end up with an oscillation only as of the 140th iteration, as you mentioned on the call, is more likely to be due to a slow convergence in the volume splitting algorithm.

[joeha480]

@PaulRambags

The statement that the CRH doesn't have an oscillation guard doesn't make any sense. Oscillation occurs when the algorithm keeps trying the same solutions over and over. The CRH simply detects that the solutions are faulty.

However, I doubt that it's correct that the CRH is clean when oscillation occurs.

[bertfrees]

I'm looking at the seemingly simple example from Paul that takes more than 50 iterations.

I've gathered this trace info. It seems to me that the estimation of the split is reasonable, but the actual splitter does something unexpected, which results in ever more volumes being added but there are never enough.

         estim.   estim.   actual                                             actual   sheets   total    next     next    
         sheets   volumes  split                                              sheets   remain.  sheets   offset   splitter
------   ------   ------   ------                                             ------   ------   ------   ------   ------  
1        78       39       [1, 2, 2 (+36 more)]                               77       2        79       0        [2, 2 (+37 more), 1]
2        79       40       [1, 2, 1, 2, 2 (+34 more), 1]                      77       19       96       1        [2, 2 (+45 more), 1, 1]
3        96       49       [1, 2, 1, 2, 2 (+42 more), 1, 1]                   94       6        100      1        [2, 2 (+47 more), 1, 1]
4        100      51       [1, 2, 1, 2, 2 (+44 more), 1, 1]                   98       3        101      1        [2, 2 (+47 more), 1, 1, 1]
5        101      52       [1, 2, 1, 2, 2 (+44 more), 1, 1, 1]                99       2        101      2        [2, 2 (+46 more), 1, 1 (+3 more)]
6        101      53       [1, 2, 1, 2, 2 (+43 more), 1, 1 (+3 more)]         99       2        101      3        [2, 2 (+45 more), 1, 1 (+5 more)]
7        101      54       [1, 2, 1, 2, 2 (+42 more), 1, 1 (+5 more)]         99       2        101      4        [2, 2 (+44 more), 1, 1 (+7 more)]
8        101      55       [1, 2, 1, 2, 2 (+41 more), 1, 1 (+7 more)]         99       2        101      5        [2, 2 (+43 more), 1, 1 (+9 more)]
9        101      56       [1, 2, 1, 2, 2 (+40 more), 1, 1 (+9 more)]         99       2        101      6        [2, 2 (+42 more), 1, 1 (+11 more)]
10       101      57       [1, 2, 1, 2, 2 (+39 more), 1, 1 (+11 more)]        99       2        101      7        [2, 2 (+41 more), 1, 1 (+13 more)]
11       101      58       [1, 2, 1, 2, 2 (+38 more), 1, 1 (+13 more)]        99       2        101      8        [2, 2 (+40 more), 1, 1 (+15 more)]
12       101      59       [1, 2, 1, 2, 2 (+37 more), 1, 1 (+15 more)]        99       2        101      9        [2, 2 (+39 more), 1, 1 (+17 more)]
13       101      60       [1, 2, 1, 2, 2 (+36 more), 1, 1 (+17 more)]        99       2        101      10       [2, 2 (+38 more), 1, 1 (+19 more)]
14       101      61       [1, 2, 1, 2, 2 (+35 more), 1, 1 (+19 more)]        99       2        101      11       [2, 2 (+37 more), 1, 1 (+21 more)]
15       101      62       [1, 2, 1, 2, 2 (+34 more), 1, 1 (+21 more)]        99       2        101      12       [2, 2 (+36 more), 1, 1 (+23 more)]
16       101      63       [1, 2, 1, 2, 2 (+33 more), 1, 1 (+23 more)]        99       2        101      13       [2, 2 (+35 more), 1, 1 (+25 more)]
17       101      64       [1, 2, 1, 2, 2 (+32 more), 1, 1 (+25 more)]        99       2        101      14       [2, 2 (+34 more), 1, 1 (+27 more)]
18       101      65       [1, 2, 1, 2, 2 (+31 more), 1, 1 (+27 more)]        99       2        101      15       [2, 2 (+33 more), 1, 1 (+29 more)]
19       101      66       [1, 2, 1, 2, 2 (+30 more), 1, 1 (+29 more)]        99       2        101      16       [2, 2 (+32 more), 1, 1 (+31 more)]
20       101      67       [1, 2, 1, 2, 2 (+29 more), 1, 1 (+31 more)]        99       2        101      17       [2, 2 (+31 more), 1, 1 (+33 more)]
21       101      68       [1, 2, 1, 2, 2 (+28 more), 1, 1 (+33 more)]        99       2        101      18       [2, 2 (+30 more), 1, 1 (+35 more)]
22       101      69       [1, 2, 1, 2, 2 (+27 more), 1, 1 (+35 more)]        99       2        101      19       [2, 2 (+29 more), 1, 1 (+37 more)]
23       101      70       [1, 2, 1, 2, 2 (+26 more), 1, 1 (+37 more)]        99       2        101      20       [2, 2 (+28 more), 1, 1 (+39 more)]
24       101      71       [1, 2, 1, 2, 2 (+25 more), 1, 1 (+39 more)]        99       2        101      21       [2, 2 (+27 more), 1, 1 (+41 more)]
25       101      72       [1, 2, 1, 2, 2 (+24 more), 1, 1 (+41 more)]        99       2        101      22       [2, 2 (+26 more), 1, 1 (+43 more)]
26       101      73       [1, 2, 1, 2, 2 (+23 more), 1, 1 (+43 more)]        99       2        101      23       [2, 2 (+25 more), 1, 1 (+45 more)]
27       101      74       [1, 2, 1, 2, 2 (+22 more), 1, 1 (+45 more)]        99       2        101      24       [2, 2 (+24 more), 1, 1 (+47 more)]
28       101      75       [1, 2, 1, 2, 2 (+21 more), 1, 1 (+47 more)]        99       2        101      25       [2, 2 (+23 more), 1, 1 (+49 more)]
29       101      76       [1, 2, 1, 2, 2 (+20 more), 1, 1 (+49 more)]        99       2        101      26       [2, 2 (+22 more), 1, 1 (+51 more)]
30       101      77       [1, 2, 1, 2, 2 (+19 more), 1, 1 (+51 more)]        99       2        101      27       [2, 2 (+21 more), 1, 1 (+53 more)]
31       101      78       [1, 2, 1, 2, 2 (+18 more), 1, 1 (+53 more)]        99       2        101      28       [2, 2 (+20 more), 1, 1 (+55 more)]
32       101      79       [1, 2, 1, 2, 2 (+17 more), 1, 1 (+55 more)]        99       2        101      29       [2, 2 (+19 more), 1, 1 (+57 more)]
33       101      80       [1, 2, 1, 2, 2 (+16 more), 1, 1 (+57 more)]        99       2        101      30       [2, 2 (+18 more), 1, 1 (+59 more)]
34       101      81       [1, 2, 1, 2, 2 (+15 more), 1, 1 (+59 more)]        99       2        101      31       [2, 2 (+17 more), 1, 1 (+61 more)]
35       101      82       [1, 2, 1, 2, 2 (+14 more), 1, 1 (+61 more)]        99       2        101      32       [2, 2 (+16 more), 1, 1 (+63 more)]
36       101      83       [1, 2, 1, 2, 2 (+13 more), 1, 1 (+63 more)]        99       2        101      33       [2, 2 (+15 more), 1, 1 (+65 more)]
37       101      84       [1, 2, 1, 2, 2 (+12 more), 1, 1 (+65 more)]        99       2        101      34       [2, 2 (+14 more), 1, 1 (+67 more)]
38       101      85       [1, 2, 1, 2, 2 (+11 more), 1, 1 (+67 more)]        99       2        101      35       [2, 2 (+13 more), 1, 1 (+69 more)]
39       101      86       [1, 2, 1, 2, 2 (+10 more), 1, 1 (+69 more)]        99       2        101      36       [2, 2 (+12 more), 1, 1 (+71 more)]
40       101      87       [1, 2, 1, 2, 2 (+9 more), 1, 1 (+71 more)]         99       2        101      37       [2, 2 (+11 more), 1, 1 (+73 more)]
41       101      88       [1, 2, 1, 2, 2 (+8 more), 1, 1 (+73 more)]         99       2        101      38       [2, 2 (+10 more), 1, 1 (+75 more)]
42       101      89       [1, 2, 1, 2, 2 (+7 more), 1, 1 (+75 more)]         99       2        101      39       [2, 2 (+9 more), 1, 1 (+77 more)]
43       101      90       [1, 2, 1, 2, 2 (+6 more), 1, 1 (+77 more)]         99       2        101      40       [2, 2 (+8 more), 1, 1 (+79 more)]
44       101      91       [1, 2, 1, 2, 2 (+5 more), 1, 1 (+79 more)]         99       2        101      41       [2, 2 (+7 more), 1, 1 (+81 more)]
45       101      92       [1, 2, 1, 2, 2 (+4 more), 1, 1 (+81 more)]         99       2        101      42       [2, 2 (+6 more), 1, 1 (+83 more)]
46       101      93       [1, 2, 1, 2, 2 (+3 more), 1, 1 (+83 more)]         99       2        101      43       [2, 2 (+5 more), 1, 1 (+85 more)]
47       101      94       [1, 2, 1, 2, 2 (+2 more), 1, 1 (+85 more)]         99       2        101      44       [2, 2 (+4 more), 1, 1 (+87 more)]
48       101      95       [1, 2, 1, 2, 2, 2, 1, 1 (+87 more)]                99       3        102      46       [2, 2 (+3 more), 1, 1 (+90 more)]
49       102      97       [1, 2, 1, 2, 2, 1, 2, 1, 1 (+87 more), 2]          102      0        102      45       [2, 2 (+4 more), 1, 1 (+88 more)]
50       102      96       [1, 2, 1, 2, 2, 2, 1, 1 (+88 more)]                100      2        102      46       [2, 2 (+3 more), 1, 1 (+90 more)]

[bertfrees]

The fact that these block can not possibly fit on a page has something to do with it (page is 8 wide and 5 high):

<block keep="page">
  ⠉⠉⠉⠉⠉ ⠉⠉⠉⠉⠉ ⠉⠉⠉⠉⠉ ⠉⠉⠉⠉⠉ ⠉⠉⠉⠉⠉ ⠉⠉⠉⠉⠉
</block>

[bertfrees]

I'm working on this branch, in case you want to follow along. You can see I further simplified the test. Both the volume-transition element and the keep="page" are relevant.

[bertfrees]

Without the keep="page", the splitting algorithm finishes in 30 iterations, but the formatter keeps going until transitionProperties settles in iteration 71. These are the changes that happen to transitionProperties between iterations 30 and 71:

PageId[27] : TransitionProperties[hasBlockBoundary=true -> false]
PageId[28] : TransitionProperties[hasBlockBoundary=false -> true]

PageId[30] : TransitionProperties[hasBlockBoundary=false -> true]
PageId[29] : TransitionProperties[hasBlockBoundary=true -> false]

PageId[31] : TransitionProperties[hasBlockBoundary=true -> false]
PageId[32] : TransitionProperties[hasBlockBoundary=false -> true]

PageId[34] : TransitionProperties[hasBlockBoundary=false -> true]
PageId[33] : TransitionProperties[hasBlockBoundary=true -> false]

...

PageId[103] : TransitionProperties[hasBlockBoundary=true -> false]
PageId[104] : TransitionProperties[hasBlockBoundary=false -> true]

@joeha480 Can you make sense of this?

[bertfrees]

It seems to me that the estimation of the split is reasonable, but the actual splitter does something unexpected, which results in ever more volumes being added but there are never enough.

On second thought, the EvenSizeVolumeSplitter does not work well! It keeps adding extra volumes instead of just increasing the sizes of existing volumes. Because for every iteration the total number of sheets increases, this is a never ending circle.

[bertfrees]

I'm going to try to improve the algorithm a bit now, but in the long run I want to get rid of EvenSizeVolumeSplitter altogether, like I suggested in #50 (comment).

[bertfrees]

The oscillation is a different and AFAICS unrelated part of the problem. It looks like the oscillation is caused by the feedback of hasBlockBoundary between the previous iteration and the current one. The previous hasBlockBoundary influences the decision whether to break after a right-hand page or not, and the computation of the new hasBlockBoundary depends on where the volume is broken. If I remove the effect of hasBlockBoundary the oscillation goes away:

 	TransitionProperties st = rcontext.getRefs().getTransitionProperties(thisPageId);
-	double v1 = st.getVolumeKeepPriority().orElse(10) + (st.hasBlockBoundary()?0.5:0);
+	double v1 = st.getVolumeKeepPriority().orElse(10) + (st.hasBlockBoundary()?0:0);
 	st = rcontext.getRefs().getTransitionProperties(next.get().getPageId());
-	double v2 = st.getVolumeKeepPriority().orElse(10) + (st.hasBlockBoundary()?0.5:0);
+	double v2 = st.getVolumeKeepPriority().orElse(10) + (st.hasBlockBoundary()?0:0);
 	if (v1>v2) {

Maybe it would be better if we could use the up to date value of hasBlockBoundary? I don't know.

@joeha480 Would you mind having a look?

@PaulRambags If not taking into account hasBlockBoundary, at least for the time being, is acceptable for you, we could already use this as a temporary solution. Basically what hasBlockBoundary does, if I understand this correctly, is to make sure that if a big block starts on the right-hand page right before a volume split and does not fit within the sheet, the volume split is more likely do be done after the right-hand page.

[bertfrees]

Note that when there are volume-keep-priority attributes on your paragraphs, it should not matter whether you take hasBlockBoundary into account or not. Right Joel? I have done some testing that confirms this.