Rockbox.org home
release
dev builds
extras
themes manual
wiki
device status forums
mailing lists
IRC bugs
patches
dev guide



Rockbox mail archive

Subject: Another list optimization

Another list optimization

From: <postmaster_at_diffenbach.org>
Date: 2006-06-25

In my last email to you, Abigail, I announced a patch to optimize
gui_list scrolling when the first item on a page remains the same.
That worked by only updating the two lines that changes, the line the
cursor left and the line the cursor arrived at.

I've now implemented another optimization, used when items "move off"
the top or bottom of the list. The implementation just copies the
framebuffer over itself, to move the unchanged items up or down in the
viewport.

This results in a time cost about 1/3 of that of the standard
implementation, when using a font that allows 16 lines per screen.
Timings include the setup time, and time to discover which
optimization to use. (See data at the end of this email.)

However, it works badly with backgrounds, as it copies the background
along with the list item text.

Frankly, while Minty is lovely, I'm not a big fan of backgrounds. I
suppose the work-around is to have three framebuffers, one for the
text, one for a text mask, and one for the background, and combine
them when actually writing the screen.

Probably there's a clever way to make the text framebuffer and the
mask the same, given that no font is antialiased.

Any thoughts on this?

Data below.
Key:
n = normal, cvs implementation, used when the list wasn't previously
on the screen;
o = optimization when the list items in the virewport don't change,
and only the cursor moves, already released as a patch;
1 = scroll forward optimization when a new item appears at the bottom
of the viewport and an item disappears from the top;
2 = scroll backward optimization when a new item appears at the top of
the viewport and an item disappears from the bottom (higher cost than
1 is because the 2 loop isn't unrolled and the 1 loop is);
ld = just a meaningless notation indicating where in the program the
debug line is.
Times are in microseconds elapsed.

Three things about the data are noteworthy: absent paged scrolling or
page down, most list scrolling uses the optimizations, mostly that'll
be the new (1 or 2) optimizations, and optimized scrolling is
significantly faster than normal scrolling.

ld 2 51771
ld 2 53730
ld 2 50914
ld 2 49914
ld 2 48428
ld 2 47719
ld 2 46309
ld 2 46240
ld 2 48130
ld 2 51151
ld 2 52548
ld 2 48876
ld 2 47208
ld 2 47032
ld 2 47612
ld 2 46483
ld 2 46710
ld 2 46309
ld 2 46165
ld 2 46558
ld 2 46499
ld 2 46872
ld 2 47522
ld 2 47861
ld 2 47856
ld 2 47214
ld 2 46933
ld 2 47445
ld 2 47647
ld 2 47567
ld 2 48938
ld 2 48928
ld 2 48304
ld 2 46305
ld 2 46304
ld 2 46297
ld 2 45906
ld 2 46451
ld 2 46432
ld 2 46813
ld 2 47434
ld o 9982
ld o 10597
ld o 10143
ld o 9506
ld o 10039
ld o 10061
ld o 9827
ld o 9974
ld o 12676
ld o 11942
ld o 10584
ld o 11238
ld o 10541
ld 1 34727
ld 1 34284
ld 1 35432
ld 1 34951
ld 1 35006
ld 1 35017
ld 1 33601
ld 1 33726
ld 1 33583
ld 1 33174
ld 1 33944
ld 1 33748
ld 1 34642
ld 1 34639
ld 1 34196
ld 1 37057
ld 1 39559
ld 1 38287
ld n 118132
ld n 147749
ld o 10505
ld o 11510
ld o 11800
ld o 11817
ld o 10791
ld o 9430
ld o 9720
ld o 10012
ld o 10003
ld o 10132
ld o 10421
ld o 11287
ld o 10399
ld o 9403
ld 1 33172
ld 1 34202
ld 1 34900
ld 1 36820
ld 1 40689
ld 1 40452
ld 1 37795
ld 1 36478
ld 1 34104
ld 1 34093
ld 1 35170
ld 1 34801
ld 1 35988
ld 1 35697
ld 1 35302
ld 1 36918
ld 1 36503
ld 1 36242
ld 1 36327
ld 1 36010
ld 1 38594
ld 1 38096
ld 1 37702
ld 1 38491
ld 1 38573
ld 1 37015
ld 1 37670
ld 1 34842
ld 1 36802
ld 1 38927
ld 1 36555
ld 1 36769
ld 1 33987
ld 1 34942
ld 1 35610
ld 1 34553
ld 1 34713
ld 1 33662
ld 1 35516
ld 1 36218
ld 1 35821
ld 1 36547
ld 1 34580
ld 1 36683
ld 1 38407
ld 1 37851
ld 1 38507
ld n 75585
ld n 153621
ld n 75486
ld n 153606
ld n 154244
ld o 10621
ld o 9586
ld o 9527
ld o 9506
ld n 75901
ld n 150194
ld n 151686
ld 2 48171
ld 2 49741
ld 2 50664
ld 2 50137
ld 2 49423
ld 2 47424
ld 2 47488
ld 2 48236
ld 2 49301
ld 2 48551
ld 2 46532
ld 2 45867
ld 2 47896
ld 2 48188
ld 2 47929
ld 2 46003
ld 2 47243
ld 2 49236
ld o 10694
ld o 10062
ld o 9793
ld o 11973
ld o 11714
ld o 9630
ld o 9544
ld o 10364
ld o 13044
ld o 11800
ld o 9971
ld o 11297
ld o 11250
ld 1 38438
ld 1 38109
ld 1 38696
ld 1 36842
ld 1 35279
ld 1 33679
ld 1 35460
ld 1 39334
ld 1 39947
ld 1 39267
ld 1 38118
ld 1 35673
ld 1 34923
ld 1 34533
ld 1 33021
ld 1 33102
ld 1 33600
ld 1 33512
ld 1 33438
ld 1 34789
ld 1 34801
ld 1 36598
ld 1 36946
ld 1 36167
ld 1 36326
ld 1 34871
ld 1 34379
ld 1 33493
ld 1 34384
ld 1 33522
ld 1 33626
ld 1 35437
ld 1 34991
ld 1 35374
ld o 12114
ld o 11665
ld o 9371
ld o 10295
ld o 10703
ld o 9679
ld o 10104
ld o 10471
ld o 10797
ld o 10747
ld n 105116
ld o 10239
ld o 10212
ld o 10342
ld o 10141
ld o 10215
ld o 10162
ld o 9534
ld o 4464
ld o 4484
ld o 4455
ld o 4517
ld o 4454
ld n 80256
ld n 80728
ld o 9957
ld o 5345
ld o 5254
ld o 5331
ld n 134225
ld n 134887
ld o 10058
ld o 10046
ld o 9785
ld o 9755
ld o 9982
ld o 10112
ld o 10350
ld o 10539
ld o 10543
ld o 10134
ld o 9323
ld o 9199
ld o 4741
Received on Sun Jun 25 11:23:22 2006


Page was last modified "Jan 10 2012" The Rockbox Crew
aaa