From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.emacs.gnus.general/5548 Path: main.gmane.org!not-for-mail From: gsstark@MIT.EDU (Greg Stark) Newsgroups: gmane.emacs.gnus.general Subject: performance respooling articles in nnmbox or nnbabyl Date: 15 Mar 1996 20:30:53 -0500 Organization: Massachvsetts Institvte of Technology Sender: gsstark@fierce-bad-rabbit.MIT.EDU Message-ID: NNTP-Posting-Host: coloc-standby.netfonds.no X-Trace: main.gmane.org 1035146136 677 80.91.224.250 (20 Oct 2002 20:35:36 GMT) X-Complaints-To: usenet@main.gmane.org NNTP-Posting-Date: Sun, 20 Oct 2002 20:35:36 +0000 (UTC) Return-Path: ding-request@ifi.uio.no Original-Received: from ifi.uio.no (ifi.uio.no [129.240.64.2]) by deanna.miranova.com (8.7.3/8.6.9) with SMTP id SAA01521 for ; Fri, 15 Mar 1996 18:21:18 -0800 Original-Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU [18.69.0.28]) by ifi.uio.no with SMTP (8.6.11/ifi2.4) id for ; Sat, 16 Mar 1996 02:31:02 +0100 Original-Received: from FIERCE-BAD-RABBIT.MIT.EDU by MIT.EDU with SMTP id AA05251; Fri, 15 Mar 96 20:30:15 EST Original-Received: by fierce-bad-rabbit.MIT.EDU (5.57/4.7) id AA08687; Fri, 15 Mar 96 20:30:59 -0500 Original-To: ding@ifi.uio.no Original-Lines: 41 X-Mailer: September Gnus v0.51/Emacs 19.30 Xref: main.gmane.org gmane.emacs.gnus.general:5548 X-Report-Spam: http://spam.gmane.org/gmane.emacs.gnus.general:5548 Hypothetically speaking, i was helping set up a new user who wanted to use nnmbox as his backend. He had everything set up fine and it came time to set up a nnmail-split-method. After setting up an nnmail-split method he would just bave to use Br to respool all the articles into groups, right? The problem is that nnmbox and nnbabyl use a single file for all the groups and use the Gnus-* headers to indicate which group an article is in. To refile an article, all that's necessary is to change the header, in theory. In practice Gnus deletes the old message inserts the message in a new buffer, edits the text there, then inserts that text at the other end of the buffer. Think about how the buffer gap has to move to accomplish this when respooling the entire nnmbox; the behaviour is absolutely pessimized. The buffer gap has to move back and forth across the entire nnmbox file for each delete and insert, meaning emacs has to do the equivalent of an memmove of the entire nnmbox file in memory twice for each respool. Since each movement has to cover N articles, and it has to do 2N movemements, this respooling algorithm should run in N^2 time. I'm not 100% emacs 19.30 still has to do this, there are a lot of obvious optimizations emacs could do for operations at the end of buffers, but i'm pretty sure the multiple gap code never made it into the mainline source. But there's no real reason such a simple operation doing so much work anyways. If it just went through and editted the headers for each article it would only have to move the gap over each article once in sequence, the equivalent of a single movement over the entire buffer. In other words it should run in order N time. If there's no clean way to get this behaviour without breaking the abstraction barriers (it looks like it shouldn't be too hard to me) then another order N algorithm would be to process all the deletions first then insert all of them at the end. I think this algorithm would still be doing more work than the header editting one, though i can't be sure. I hope the optimization splurge continues even after this release, and i hope you pay attention to algorithmic optimizations and not just minor tweaks like choosing which primitives to use. I suspect there are still a lot of N^2 algorithms lying around even after that patch in gnu.emacs.gnus that changed a lot of them. In particular, killing lots newsgroups still seems slow. greg