Annouce: patch to speed up SOME list scrolling by a factor of ~12

[TP Diffenbach]

This patch optimizes apps/gui/list.c, function gui_list_draw.

Previously, all lists were always redrawn in their entirety. With this patch, when the list's start position (the item at the top of the list) hasn't changed, only the /lines/ changed are updated. In almost all cases, that means only two lines are updated, the line the cursor is leaving and the line to cursor is moving to. When a list's start position changes, or when a new list is shown, the whole list is re-drawn using the original cvs code.

Provision is made to handle the "pointer" cursor as well as the standard inverted bar cursor.

The speed increase depends on the font used; the smaller the font, the more lines have to be drawn to fill the screen, and so the greater the speed savings. Here's a non-controlled sample of the average speeds of the regular and the optimized list redrawing, in microseconds, for several font sizes, on my Ipod Video (G5, 60GB, using only 32MB of memory, that is, build 15):


Font Height    Average Unoptimized   Average Optimized  Ratio of Unoptimized/Optimized
 5             123039.71              4555.51           27.01
 7             128322.65             15404.24            8.33
14             116112.13              7363.98           15.77
16             128704.18              8046.00           16.00
24             130604.73             20603.50            6.34

For ipods, there's an often mentioned problem of music play stopping when lists are scrolled. This will not fix the problem, but will alleviate it quite a bit.

Please perform the following experiment before using this patch in a build. Using your current build, play a song, then go to the menu and rapidly scroll up and down the list until the music stops playing. Then try the same using a build with this patch. Then do a logfdump (Menu|Info|Debug|logfdump), and mail the file logf.txt in your device's .rockbox directory to:
rockbox_gui_list_opt AT diffenbach.org

Thanks.

The patch can be found here:
http://www.rockbox.org/tracker/task/5591

[TP Diffenbach]

Dave Chapman (linuxstb) notes that the original patch will work only on PP5020 ipods, and only on builds with logf support.

For all other builds, or if you're unsure your build supports the original patch, use this second patch, gui_list.unpaged.optimization.2.patch

Jens Arnold (amiconn) suggests using the patch with paged scrolling on.

Thanks to both!

With or without paged scrolling, I CANNOT on my ipod G5 scroll fast enough to make music skip, even listening to a 320 CBR mp3, so long as the scrolling is WITHIN a page and thus optimized.

[Mr. Brownstone]

I get a hunk-failed error when applying the patch, but it can be safely ignored:

Code: [Select]

***************
*** 29,35 ****
  #include "list.h"
  #include "scrollbar.h"
  #include "statusbar.h"
- #include "textarea.h"
 
  #ifdef HAVE_LCD_CHARCELLS
  #define SCROLL_LIMIT 1
--- 29,35 ----
  #include "list.h"
  #include "scrollbar.h"
  #include "statusbar.h"
+ #include "textarea.h"

 
  #ifdef HAVE_LCD_CHARCELLS
  #define SCROLL_LIMIT 1

The only difference between the two lines is a single trailing space.

[aegis]

Nice patch. It proves that actually some people are taking a look into the source and try to improve it a bit.

Thanks for the authors and hope to seeing from you soon. I hope as well that the best solution will be after some verification included in CVS as soon as possible...

[TiMiD]

I didn't applied the patch, but just looking at the source code makes me think this doesn't work for 2 screens devices because of the way you test if a list has to be completely redrawn or just partially (in the case of 2 screens devices, the list will be redrawn each time).

Of course this can be solved easily (maybe an approach where the calling program decides wether it should be completely redrawn or not would offer more flexibility)

Else nice patch

[TP Diffenbach]

I didn't applied the patch, but just looking at the source code makes me think this doesn't work for 2 screens devices because of the way you test if a list has to be completely redrawn or just partially (in the case of 2 screens devices, the list will be redrawn each time).

Yes, you're quite right. Thanks for catching that.

Just as screens is a global array of displays, we need to save last_gui_list into an array as long as the screens array (that is, either one or two elements), and index the array using the screen value passed to the gui_synclinst functions.

Or! Better, we could make just last_gui_list a member of struct screen. Since a gui_list hold a pointer to its screen we could have

if( list == list->screen.last_list ) // this list is still displayed on this screen

This gets rid of the file scope last_gui_list, so the default case in gui_synclist_do_button would the be:

default: { // brackets because we're going to declare an automatic variable
 int I ;
 FOR_NB_SCREENS(I) // same code as in all gui_synclist functions
   screens[ i ].last_gui_list = 0 ;
}

 
And it's always nice to get rid of globals and file scope variables precisely because they don't accommodate having two of anything.

[TiMiD]

I think an additionnal parameter to the draw function is the way to go.
a program could call the draw function to redraw completely the screen without creating a new list

oh and btw with all my respect, I think it's a really bad idea to use the screen struct to put things like this without any relationship; ideally this one should hold only informations about the low level access to the screen.

[TP Diffenbach]

I think an additional parameter to the draw function is the way to go.
a program could call the draw function to redraw completely the screen without creating a new list

Ok, but how does the caller  know when to redraw or not? The only way to know that is to monitor changes to the struct gui_list, which we can do in the list_draw function. 

It might seem that the caller could know this without looking at the current list item, but that's not the case. Consider:

#ifdef LIST_PGUP
        case LIST_PGUP:
            gui_synclist_limit_scroll(lists, false);
        case LIST_PGUP | BUTTON_REPEAT:
            gui_synclist_select_previous_page(lists, SCREEN_MAIN);
            gui_synclist_draw(lists);
            yield();
            return LIST_NEXT;
#endif


A previous page should mean that every line has changed, so it's pointless to optimize. And that'll be true if the key isn't repeating, because gui_synclist_limit_scroll won't be called. But if the key is repeating, and we reach the end of the list, we might have some lines we can reuse. The only way to tell would be to find if gui_list->start_item - last_displayed_start_item < screen->nb_lines.

And it's duplicative to do that in several callers when we can do it in one called function.


The bottom line is, regardless of the caller, if we can save time by not reprinting a line, we want to do it.

oh and btw with all my respect, I think it's a really bad idea to use the screen struct to put things like this without any relationship; ideally this one should hold only informations about the low level access to the screen.

I see your point, but knowing what last used the screen (which list or no list at all) seems like a good candidate for low level screen information. No, it's not as "purely low level" as width or height, but neither are char_width or char_height, which are members of struct screen even though their values depend on the current font.

We /should/ strive to be purists, but we shouldn't contort ourselves doing so.

[Zoide]

Witch of the two patches do we use for the 5G iPod?  The iPodLinux Generations page (http://ipodlinux.org/Generations) lists its processor as "PP5021C-TDF (like PP5020)", so I'm not sure whether that counts as PP5020 or not.

[TP Diffenbach]

Witch of the two patches do we use for the 5G iPod?  The iPodLinux Generations page (http://ipodlinux.org/Generations) lists its processor as "PP5021C-TDF (like PP5020)", so I'm not sure whether that counts as PP5020 or not.

If you're asking about versions of this  patch: Patch one, if your build includes logf, patch two if it doesn't. If you're not sure, patch two.

If you're asking about this patch and the /other/ list optimization patch: this one. The other one will give you a speed increase but make your background  images look terrible. (Of course, if you don't use a background image, or use one like brushed metal that doesn't change much from top to bottom, then you can use both patches.)

If you want this list optimization and my scrolling accel (which is still half-baked), then use this patch: http://www.rockbox.org/tracker/task/5594

If you have an ipod 5G, and ONLY an ipod 5G, definitely get the lcd patch too -- it breaks nothing and it increases your framerate by 5%, so there's no reason not to get it:
http://www.rockbox.org/tracker/task/5432

(It won't break other platforms, but it won't do anything for them either.)

[TiMiD]

The caller knows when to force redraw simply because it's it that changed the list / redraw something above it etc ...
in the case of the tree view, it would be for example when switching from menu /wps/plugin to tree or when changing folder