Optimisation by killing O(n^2) algorithms
Monday, May 29th, 2006Sometimes optimising means shaving milliseconds after spending lots of time on subtle algorithms… And sometimes it just means discovering huge counter-performant parts in your fast mail user agent. The advantage of the latter is that, for similar amounts of work, you get much more results.
O(n^2) algorithms are algorithms which execution time is proportional to the square of the number of elements to be processed. Meanwhile, O(N) algos are directly proportional to the number of elements, and O(1) is as fast given any number of elements. Every hacker would love to see only O(1) algorithms everywhere, but failing that, none of them like O(n^2). You can read more about this on Wikipedia.
Recently that’s what I’ve been doing on Sylpheed-Claws. Investigating why Claws can take huge amounts of time doing normal stuff has proven to be interesting work with a nice reward, just using tools like gprof, callgrind and gdb.
(results are at the end)
Symptom: Sylpheed-Claws takes too much time to open a folder
Fix: GtkCTree’s sorting functions uses gtk_ctree_link and gtk_ctree_unlink to build the tree, and these functions uselessly (in this case) use g_list_position on the rows list. Which means that building a 10k mail tree calls g_list_position 10000 times, which walks the whole list using a loop that runs for 1, then 2, then… then 10000 iterations. Reimplement gtk_ctree_insert_gnode and their called static functions.
Symptom: “Mark all read” and other mass flag changes takes too much time in current folder
Fix: Disconnect the GUI message update callback during flags unsetting, and update all at once instead of 10000 times.
Symptom: Copy and Move takes too much time
Fix: Use g_slist_prepend instead of g_slist_append to build the list of mails to copy/move, and save 10000 complete walks of the list.In addition to that, don’t take the pain of fetching and parsing the whole messages if this isn’t necessary. Finally, implement a progress bar for the psychological value of not facing a frozen app.
Symptom: Deleting or moving mails is slow
Fix: Before executing a move or deletion, we have to unthread the mail list, because removing a node removes its children even if they aren’t planned to be moved/deleted. Instead of unthreading everything recursively, just unthread child nodes of deleted/moved mails if they, themselves aren’t planned to be deleted/moved.
Symptom: Shift-selecting thousands of mails is slow
Fix: shift-selection is done by calling the select function N times with the ‘range’ mode, and add the rows using gtk_clist_select_row(). This function performs a g_list_nth() on the rows list to figure the node from the position, which makes it an O(n^2) algorithm. Replace that by getting the node once for the lower bound of the selection, and selecting the rest of the rows manually, just shifting in the rows list.
Symptom: Unselecting tons of mails is slow
Fix: freeze/thaw the list before unselecting everything, and avoid N repaints and check for repaints.
End result:
wwp has been kind enough to compare timings between 2.2.0 and latest CVS. He used a really big folder, 80000 messages, and his results are astonishing:
| system: FC5 on a D810 laptop, P4 2GHz, 1GB, SATA 80GB ext3 (no noatime) 5400rpm/sec (32MB/sec), gtk+ 2.8.17 glib 2.10.2 | ||
| folder: 80000 messages, all read and no specific flag, mostly threads (mailing-lists) | ||
| 2.2.0 | 2.2.0cvs61 | |
| enter (threaded)*: | 3min54sec (3min4sec) | 8sec |
| turn off threads: | 7sec | 5sec |
| turn on threads*: | 3min49sec (3min) | 7sec |
| select all (shift+click): | 4min4sec | 1sec |
| mark all unread: | 9min20sec | 4sec |
| mark all unread again: | 8min30 | 2sec |
| select all (ctrl+a): | 1sec | 1sec |
| mark read: | 18min | 3sec |
| move**: | more than 70min | 1min15sec(7sec) |
| copy**: | more than I can afford! | 2min15sec(1min30sec) |
| delete: | 43min | 19sec |
| *total-time(sorting time) **total-time(copy/move time, the rest being cache update) |
||
These results are almost embarrassing. But like all O(n^2) algorithms, operation on common sizes of folders,0-5000 mails, was fast enough. The bigger the folder, the bigger the gain!
