From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.emacs.gnus.general/74232 Path: news.gmane.org!not-for-mail From: Dan Christensen Newsgroups: gmane.emacs.gnus.general Subject: Re: Improving Gnus speed Date: Sun, 21 Nov 2010 15:42:44 -0500 Message-ID: <871v6el86z.fsf@uwo.ca> References: <87zktemkwl.fsf@uwo.ca> <87vd42mdci.fsf@uwo.ca> <87y68vhj3q.fsf@uwo.ca> <87sjz3h9zo.fsf@uwo.ca> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: dough.gmane.org 1290372222 4914 80.91.229.12 (21 Nov 2010 20:43:42 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Sun, 21 Nov 2010 20:43:42 +0000 (UTC) To: ding@gnus.org Original-X-From: ding-owner+M22597@lists.math.uh.edu Sun Nov 21 21:43:38 2010 Return-path: Envelope-to: ding-account@gmane.org Original-Received: from util0.math.uh.edu ([129.7.128.18]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1PKGl8-00029s-0q for ding-account@gmane.org; Sun, 21 Nov 2010 21:43:38 +0100 Original-Received: from localhost ([127.0.0.1] helo=lists.math.uh.edu) by util0.math.uh.edu with smtp (Exim 4.63) (envelope-from ) id 1PKGkc-00078e-0m; Sun, 21 Nov 2010 14:43:06 -0600 Original-Received: from mx2.math.uh.edu ([129.7.128.33]) by util0.math.uh.edu with esmtps (TLSv1:AES256-SHA:256) (Exim 4.63) (envelope-from ) id 1PKGkY-00078J-UD for ding@lists.math.uh.edu; Sun, 21 Nov 2010 14:43:02 -0600 Original-Received: from quimby.gnus.org ([80.91.231.51]) by mx2.math.uh.edu with esmtp (Exim 4.72) (envelope-from ) id 1PKGkT-0003jl-RG for ding@lists.math.uh.edu; Sun, 21 Nov 2010 14:43:02 -0600 Original-Received: from lo.gmane.org ([80.91.229.12]) by quimby.gnus.org with esmtp (Exim 3.36 #1 (Debian)) id 1PKGkT-0005pw-00 for ; Sun, 21 Nov 2010 21:42:57 +0100 Original-Received: from list by lo.gmane.org with local (Exim 4.69) (envelope-from ) id 1PKGkT-0001sN-2q for ding@gnus.org; Sun, 21 Nov 2010 21:42:57 +0100 Original-Received: from bas3-london14-1096787421.dsl.bell.ca ([65.95.165.221]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Sun, 21 Nov 2010 21:42:57 +0100 Original-Received: from jdc by bas3-london14-1096787421.dsl.bell.ca with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Sun, 21 Nov 2010 21:42:57 +0100 X-Injected-Via-Gmane: http://gmane.org/ Original-Lines: 60 Original-X-Complaints-To: usenet@dough.gmane.org X-Gmane-NNTP-Posting-Host: bas3-london14-1096787421.dsl.bell.ca User-Agent: Gnus/5.110011 (No Gnus v0.11) Emacs/23.1.50 (gnu/linux) Cancel-Lock: sha1:9zjhTg89o1Cn5xGR1eiRPbxmE5A= X-Spam-Score: -1.9 (-) List-ID: Precedence: bulk Xref: news.gmane.org gmane.emacs.gnus.general:74232 Archived-At: Lars Magne Ingebrigtsen writes: > Dan Christensen writes: > >> Separate from that low-level cache, the sorting function could >> probably annotate the thread tree and re-use that information >> for all of the recursive sorts. Or use a decorate-sort-undecorate >> pattern. > > It sounds possible, but peeking at the code, it doesn't seem trivial to > do generally, since the user can compose their own composited sorting > functions. So the cache would have to be per > article+sorting-function... hm... Re: caching: I think caching mainly makes sense for the functions which require traversing the thread tree: gnus-thread-sort-by-total-score and gnus-thread-sort-by-most-recent-number and -date. Are there any others? If these tucked away their result when called, I imagine there would be a big savings. Depending on the shape of the tree, this would reduce sort key computation time from somewhere between O(n log n) and O(n^2) to O(n). Re: decorate-sort-undecorate (DSU): Here for each article you create a key which is a list of the relevant values. For example, if the sort functions are '((not gnus-thread-sort-by-number) gnus-thread-sort-by-score)) then the key would be (-number score) [or maybe the reverse]. Then you replace the list of threads with a list of pairs (key thread) and sort on the keys. This avoids recomputing the key each time an article needs to be compared with another, which would reduce overhead a lot. After sorting, you make a pass through to extract the list of threads in sorted order. When computing the keys, if you traverse the threads from leaves to the root, you can compute the keys quickly without needing to implement the caching. But I don't know what to do if the user implements their own sorting function. It would be easier if the interface was changed: instead of providing a list of comparison functions, you provide a list of functions which compute key values which are then compared using the default emacs order. Then we could always use DSU. But maybe it's not worth changing the interface for this? Options: (a) Try caching, and see if it is good enough. (b) Use DSU when only built-in sort functions are used, and fall back to existing behaviour? (Complicates code to have a fall-back, and also would have to assume that the user didn't redefine the built-in functions.) (c) Change the interface so DSU can always be used? Dan