Slow documents for profiling #277

Frenzie · 2019-03-29T15:16:51Z

By coincidence I came across this book, which seems to take a small eternity to change pages. (Okay, just a second, but that's a really long time.)

https://www.smashwords.com/books/view/631261

Anyway, so I figured I'd profile it. I'm not sure if that's helpful in this case but there you have it. ;-)

callgrind.out.12948.tar.gz

Same file as posted over at 8f15e01#r32965759

Btw, general remark, you can get the machine code with --dump-instr=yes, as in valgrind --tool=callgrind --dump-instr=yes ./reader.lua.

The text was updated successfully, but these errors were encountered:

poire-z · 2019-03-29T15:50:14Z

Not noticing much slowness on the emulator :)

But this book is a bit different from most in that there are thousands of  in a <body>, each line is in its own , and you have many such  on a page.
So, many many rects, compared to book with larger paragraphs where only the paragraph is a rect.
So, as crengine check each container top y and bottom y if it overlaps the page, and the go look at this contained children to find those that overlap, once it has found the BODY, it needs to check each and all  - and the same when on a page, and you're tapping, it needs to check if you tapped on a link, and I think it has to go thru all the  to find those on the page, and if they happen to be where you tapped.
And even more of the same work if you have some highlights, to get the Rects to highlights.

969 323 / 21 could indicate there are 46142  :) DrawDocument is called and itself checks if the node is in or out of page.
21 taps(?), 21 body to check, 46142 P in the current BODY.
I guess it all happens there:

crengine/crengine/src/lvrend.cpp

Lines 3916 to 3948 in 621dee0

    
           // Recursively called as children nodes are walked. 
        
           // x0, y0 are coordinates of top left point to draw to in buffer 
        
           // dx, dy are width and height to draw to in buffer 
        
           // doc_x, doc_y are offset coordinates in document: 
        
           //   doc_x is initially 0, and doc_y is set to a negative 
        
           //   value (- page.start) from the y of the top of the page 
        
           //   (in the whole book height) we want to start showing 
        
           void DrawDocument( LVDrawBuf & drawbuf, ldomNode * enode, int x0, int y0, int dx, int dy, int doc_x, int doc_y, int page_height, ldomMarkedRangeList * marks, 
        
                              ldomMarkedRangeList *bookmarks) 
        
           { 
        
               if ( enode->isElement() ) 
        
               { 
        
                   RenderRectAccessor fmt( enode ); 
        
                   doc_x += fmt.getX(); 
        
                   doc_y += fmt.getY(); 
        
                   lvdom_element_render_method rm = enode->getRendMethod(); 
        
                   // A few things differ when done for TR, THEAD, TBODY and TFOOT 
        
                   bool isTableRowLike = rm == erm_table_row || rm == erm_table_row_group || 
        
                                         rm == erm_table_header_group || rm == erm_table_footer_group; 
        
                   int em = enode->getFont()->getSize(); 
        
                   int width = fmt.getWidth(); 
        
                   int height = fmt.getHeight(); 
        
                   bool draw_padding_bg = true; //( enode->getRendMethod()==erm_final ); 
        
                   int padding_left = !draw_padding_bg ? 0 : lengthToPx( enode->getStyle()->padding[0], width, em ) + DEBUG_TREE_DRAW+measureBorder(enode,3); 
        
                   int padding_right = !draw_padding_bg ? 0 : lengthToPx( enode->getStyle()->padding[1], width, em ) + DEBUG_TREE_DRAW+measureBorder(enode,1); 
        
                   int padding_top = !draw_padding_bg ? 0 : lengthToPx( enode->getStyle()->padding[2], width, em ) + DEBUG_TREE_DRAW+measureBorder(enode,0); 
        
                   //int padding_bottom = !draw_padding_bg ? 0 : lengthToPx( enode->getStyle()->padding[3], width, em ) + DEBUG_TREE_DRAW; 
        
                   if ( (doc_y + height <= 0 || doc_y > 0 + dy) && !isTableRowLike ) { 
        
                       // TR may have cells with rowspan>1, and even though this TR 
        
                       // is out of range, it must draw a rowspan>1 cell, so it it 
        
                       // not empty when a next TR (not out of range) is drawn. 
        
                       return; // out of range 
        
                   }

I guess just moving all the lines from int em to int padding_top AFTER the if ( (doc_y + height <= 0 ... return; could help a lot, as we don't need all that that early if we return.

Can you check and time it ?:)

poire-z · 2019-03-29T15:52:41Z

Except int height, that is needed. So:

--- a/crengine/src/lvrend.cpp
+++ b/crengine/src/lvrend.cpp
@@ -3932,20 +3932,20 @@ void DrawDocument( LVDrawBuf & drawbuf, ldomNode * enode, int x0, int y0, int dx
         // A few things differ when done for TR, THEAD, TBODY and TFOOT
         bool isTableRowLike = rm == erm_table_row || rm == erm_table_row_group ||
                               rm == erm_table_header_group || rm == erm_table_footer_group;
-        int em = enode->getFont()->getSize();
-        int width = fmt.getWidth();
         int height = fmt.getHeight();
-        bool draw_padding_bg = true; //( enode->getRendMethod()==erm_final );
-        int padding_left = !draw_padding_bg ? 0 : lengthToPx( enode->getStyle()->padding[0], width, em ) + DEBUG_TREE_DRAW+measureBorder(enode,3);
-        int padding_right = !draw_padding_bg ? 0 : lengthToPx( enode->getStyle()->padding[1], width, em ) + DEBUG_TREE_DRAW+measureBorder(enode,1);
-        int padding_top = !draw_padding_bg ? 0 : lengthToPx( enode->getStyle()->padding[2], width, em ) + DEBUG_TREE_DRAW+measureBorder(enode,0);
-        //int padding_bottom = !draw_padding_bg ? 0 : lengthToPx( enode->getStyle()->padding[3], width, em ) + DEBUG_TREE_DRAW;
         if ( (doc_y + height <= 0 || doc_y > 0 + dy) && !isTableRowLike ) {
             // TR may have cells with rowspan>1, and even though this TR
             // is out of range, it must draw a rowspan>1 cell, so it it
             // not empty when a next TR (not out of range) is drawn.
             return; // out of range
         }
+        int em = enode->getFont()->getSize();
+        int width = fmt.getWidth();
+        bool draw_padding_bg = true; //( enode->getRendMethod()==erm_final );
+        int padding_left = !draw_padding_bg ? 0 : lengthToPx( enode->getStyle()->padding[0], width, em ) + DEBUG_TREE_DRAW+measureBorder(enode,3);
+        int padding_right = !draw_padding_bg ? 0 : lengthToPx( enode->getStyle()->padding[1], width, em ) + DEBUG_TREE_DRAW+measureBorder(enode,1);
+        int padding_top = !draw_padding_bg ? 0 : lengthToPx( enode->getStyle()->padding[2], width, em ) + DEBUG_TREE_DRAW+measureBorder(enode,0);
+        //int padding_bottom = !draw_padding_bg ? 0 : lengthToPx( enode->getStyle()->padding[3], width, em ) + DEBUG_TREE_DRAW;
         css_length_t bg = enode->getStyle()->background_color;
         lUInt32 oldColor = 0;
         // Don't draw background color for TR and THEAD/TFOOT/TBODY as it could

poire-z · 2019-03-29T16:14:48Z

The path on the left of your image is there:

crengine/crengine/src/lvtinydom.cpp

Lines 12071 to 12102 in 621dee0

    
           /// find node by coordinates of point in formatted document 
        
           ldomNode * ldomNode::elementFromPoint( lvPoint pt, int direction ) 
        
           { 
        
               ASSERT_NODE_NOT_NULL; 
        
               if ( !isElement() ) 
        
                   return NULL; 
        
               ldomNode * enode = this; 
        
               lvdom_element_render_method rm = enode->getRendMethod(); 
        
               RenderRectAccessor fmt( this ); 
        
               int top_margin = lengthToPx(enode->getStyle()->margin[2], fmt.getWidth(), enode->getFont()->getSize()); 
        
               int bottom_margin = lengthToPx(enode->getStyle()->margin[3], fmt.getWidth(), enode->getFont()->getSize()); 
        
               if ( rm == erm_table_row || rm == erm_table_row_group || rm == erm_table_header_group || rm == erm_table_footer_group ) { 
        
                   // Styles margins set on <TR>, <THEAD> and the like are ignored 
        
                   // by table layout algorithm (as per CSS specs) 
        
                   top_margin = 0; 
        
                   bottom_margin = 0; 
        
               } 
        
               if ( rm == erm_invisible ) { 
        
                   return NULL; 
        
               } 
        
               if ( pt.y < fmt.getY() - top_margin) { 
        
                   if ( direction>0 && (rm == erm_final || rm == erm_list_item || rm == erm_table_caption) ) 
        
                       return this; 
        
                   return NULL; 
        
               } 
        
               if ( pt.y >= fmt.getY() + fmt.getHeight() + bottom_margin ) { 
        
                   if ( direction<0 && (rm == erm_final || rm == erm_list_item || rm == erm_table_caption) ) 
        
                       return this; 
        
                   return NULL; 
        
               }

Same issue - top_margin & bottom_margin computed early - but less obvious to fix as these are used to decide about pt.y and return early.
May be some assumption than a margin can't be more than a page height (but it can) to check for that early and return and discard most - and next do a more precise check with the top and bottom margin computer...

Frenzie · 2019-03-29T17:30:21Z

@poire-z Oh drat, so I didn't profile correctly!

I noticed the slowness while tapping, but I didn't recreate the conditions properly by using page up/down for the profiling. Which isn't actually very slow. Except that slightly misleadingly, in Valgrind it is.

Frenzie · 2019-03-29T17:36:31Z

No profiling yet, but your suggested changes do feel slightly more responsive.

poire-z · 2019-03-29T17:45:07Z

I'll probably PR the first one and include it in the coming crengine bump as it looks super safe.
Will give some thoughts to the second one this evening, some small optimisation looks possible.

But all that could be furthermore optimised by caching many stuff in credocument (the buffer, the rects for links, the rects for highlights) so we don't request them from crengine when playing with the menu, dict lookup...
I had some try in the past, the gain was noticable, but the crengine times were so below the blitting times that it wasn't worth complexifying credocument.lua. But now that @NiLuJe has speed up the blitting...

Frenzie · 2019-03-29T19:25:29Z

Proper profile of the current code for potential future reference. Incidentally, on my desktop it's practically faster in Valgrind than on my laptop without. Quite sad. :-)

callgrind.out.8576.tar.gz

And here it is with the changes:

callgrind.out.25914.tar.gz

poire-z · 2019-03-29T19:51:10Z

Looked at them, so a big rectangle on the left disappeared, and make all the other get bigger. So, I guess it's good :)
Tested on my Kobo, and it indeed feels smoother.
Anyway, PR'ing safe changes.

Frenzie · 2019-07-22T19:20:18Z

Here's one that could potentially be worth a look.

nwt_E.epub.zip

Via https://www.mobileread.com/forums/showthread.php?p=3870059#post3870059

poire-z · 2021-10-08T12:04:08Z

Just a quick note, for info and "good to know":

I'm reading a 67 KB small EPUB which results in 110 pages.
I have some tuning in cr3.ini to have crengine use a cache for books smaller than our default.
I noticed that re-opening this book was taking 2s, even though a cache is made and used - so a longer time than most other larger books :/

It turns out this book (by Thomas Bernhard, dunno if he is known for that) is a single 110-pages paragraph - so crengine has to format this whole paragraph for drawing slices of it, which makes the re-opening as long as a re-rendering (after this opening, this formatting is cached in memory, so everything then is quick).

poire-z mentioned this issue Mar 29, 2019

Delay some style computations until needed #278

Merged

poire-z mentioned this issue Feb 10, 2020

Support vertical-align: baseline in tables, various other fixes #327

Merged

poire-z mentioned this issue Feb 23, 2020

Normalized xpointers, complete incomplete tables #328

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Slow documents for profiling #277

Slow documents for profiling #277

Frenzie commented Mar 29, 2019 •

edited

Loading

poire-z commented Mar 29, 2019

poire-z commented Mar 29, 2019

poire-z commented Mar 29, 2019

Frenzie commented Mar 29, 2019

Frenzie commented Mar 29, 2019

poire-z commented Mar 29, 2019

Frenzie commented Mar 29, 2019

poire-z commented Mar 29, 2019

Frenzie commented Jul 22, 2019

poire-z commented Oct 8, 2021

Slow documents for profiling #277

Slow documents for profiling #277

Comments

Frenzie commented Mar 29, 2019 • edited Loading

poire-z commented Mar 29, 2019

poire-z commented Mar 29, 2019

poire-z commented Mar 29, 2019

Frenzie commented Mar 29, 2019

Frenzie commented Mar 29, 2019

poire-z commented Mar 29, 2019

Frenzie commented Mar 29, 2019

poire-z commented Mar 29, 2019

Frenzie commented Jul 22, 2019

poire-z commented Oct 8, 2021

Frenzie commented Mar 29, 2019 •

edited

Loading