fast list

fast list

[James Cloos]

I fixed my modification of dbmail-2.2 to need only a single sql SELECT
to do an IMAP LIST/LSUB.  Previously it grabbed the UIDVALIDITY values
for the to-be-listed-groups in one SELECT, then iterated through that
list SELECTing the info required for LIST.

Now that latter data is returned as part of the initial SELECT.

That improved LIST from ~1k seconds for ~20k groups to about 1/2 second.

Nice.

But gnus still needs to do an EXAMINE Or STATUS or SELECT on each
returned group, and that is slow.

Ir turns out that the IMAP working group already thought of that,
though.

RFC 5819 defines an extension to LIST which returns STATUS replies
interleaved with the normal LIST replies.  Using that should speed
gnus startup considerably.

Gnus needs to note the LIST-STATUS capability; when it exists gnus
should send commands akin to:

   C: A01 LIST "" % RETURN (STATUS (MESSAGES UNSEEN))

specifying what status info it wants for each group.

 RETURN (STATUS (MESSAGES RECENT UIDNEXT UIDVALIDITY UNSEEN))

would be OK here.

The reply includes w/in the untagged part of the reply status info after
each line of the list info, specifying the status info for that mailbox.

With that my startup time should get down to something which doesn't
involve stepping away for a pot of tea.  Or three. :-/

I expect to have the dbmail side of LIST-STATUS done tomorrow (it
doesn't look too difficult; at least not after I just finished a dbmail
hacking session) and should be able to test out any gnus support.

-JimC
-- 
James Cloos <cloos@jhcloos.com>         OpenPGP: 1024D/ED7DAEA6

Re: fast list

[Lars Magne Ingebrigtsen]

James Cloos <cloos@jhcloos.com> writes:

> RFC 5819 defines an extension to LIST which returns STATUS replies
> interleaved with the normal LIST replies.  Using that should speed
> gnus startup considerably.
>
> Gnus needs to note the LIST-STATUS capability; when it exists gnus
> should send commands akin to:
>
>    C: A01 LIST "" % RETURN (STATUS (MESSAGES UNSEEN))
>
> specifying what status info it wants for each group.
>
>  RETURN (STATUS (MESSAGES RECENT UIDNEXT UIDVALIDITY UNSEEN))
>
> would be OK here.

That doesn't really help Gnus all that much, since Gnus needs to do a
marks resync, and getting the numbers of each of these won't give Gnus
the data it needs.

If they'd implemented LIST RETURN QRESYNC instead, that would have been
awesome.

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@gnus.org * Lars Magne Ingebrigtsen

Re: fast list

[James Cloos]

>>>>> "LMI" == Lars Magne Ingebrigtsen <larsi@gnus.org> writes:

JC> RETURN (STATUS (MESSAGES RECENT UIDNEXT UIDVALIDITY UNSEEN))

LMI> That doesn't really help Gnus all that much, since Gnus needs to do a
LMI> marks resync, and getting the numbers of each of these won't give Gnus
LMI> the data it needs.

LMI> If they'd implemented LIST RETURN QRESYNC instead, that would have been
LMI> awesome.

What, exactly, does gnus need for each group?

DBmail doesn't store arbitrary marks, so I don't need mark syncing for
gnus' internal marks.

I don't have a recent packet trace, but doesn't it just do a LIST
followed by either EXAMINE or STATUS?  LIST-STATUS does that pair
of ops in a single op.  And that has to speed startup.

I expect that:

  LIST "" "%" RETURN (STATUS (MESSAGES RECENT UIDNEXT UIDVALIDITY UNSEEN))

will take less than one second whereas running STATUS or EXAMINE on
every group returned by LIST takes about fifteen minutes.

I can ensure that my patches to dbmail support more than just messages,
recent, uidnext, uidvalidity and unseen if that helps.

BTW, based on:

  http://permalink.gmane.org/gmane.mail.imap.dovecot/51621

it looks like dovecot 2.0 also supports LIST-STATUS.

-JimC
-- 
James Cloos <cloos@jhcloos.com>         OpenPGP: 1024D/ED7DAEA6

Re: fast list

[Lars Magne Ingebrigtsen]

James Cloos <cloos@jhcloos.com> writes:

> LMI> If they'd implemented LIST RETURN QRESYNC instead, that would have been
> LMI> awesome.
>
> What, exactly, does gnus need for each group?

To update the group infos, Gnus needs all the article data, really.
If you have no UNSEE, but 3 \Flagged articles, Gnus displays that (by
default) as "*    0: group.name", and that info isn't available just by

>   LIST "" "%" RETURN (STATUS (MESSAGES RECENT UIDNEXT UIDVALIDITY UNSEEN))

And, of course, other people have customised *Group* displays that needs
a lot of the rest of the group data.  However, it's possible to imagine
that Gnus would just use UNSEEN and nothing else for the group display,
but it'd be a departure from how all other groups are displayed.

But as it stands, I don't really see how Gnus would use "LIST STATUS" at
all.

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@gnus.org * Lars Magne Ingebrigtsen

Re: fast list

[James Cloos]

>>>>> "LMI" == Lars Magne Ingebrigtsen <larsi@gnus.org> writes:

>> What, exactly, does gnus need for each group?

LMI> To update the group infos, Gnus needs all the article data, really.
LMI> If you have no UNSEEN, but 3 \Flagged articles, Gnus displays that (by
LMI> default) as "*    0: group.name", and that info isn't available just by

OK.

I restart gnus again last night, with strace attached.  It sent:

  LIST                           # *fast*, now
  EXAMINE for each group         # took ~20 min
  # worked internally for ~20 min
  LIST                           # again?
  EXAMINE/UID FETCH FLAGS tuple  # another ~20 min

>> LIST "" "%" RETURN (STATUS (MESSAGES RECENT UIDNEXT UIDVALIDITY UNSEEN))

It seems like an extended LIST which returns STATUS and FLAGS would do
the same as the UID FETCH FLAGS for every group, yes?

At the very least LIST-STATUS should avoid the need to EXAMINE each
group twice, yes?

If I get an i-d written up to support a FLAGS return type for LIST,
would you be willing to add support for that to nnimap?

-JimC
-- 
James Cloos <cloos@jhcloos.com>         OpenPGP: 1024D/ED7DAEA6

Re: fast list

[Lars Magne Ingebrigtsen]

James Cloos <cloos@jhcloos.com> writes:

> I restart gnus again last night, with strace attached.  It sent:
>
>   LIST                           # *fast*, now
>   EXAMINE for each group         # took ~20 min
>   # worked internally for ~20 min
>   LIST                           # again?
>   EXAMINE/UID FETCH FLAGS tuple  # another ~20 min

That's odd.  There should only be one EXAMINE run.  And that's what I
get if I push `g'.

>>> LIST "" "%" RETURN (STATUS (MESSAGES RECENT UIDNEXT UIDVALIDITY UNSEEN))
>
> It seems like an extended LIST which returns STATUS and FLAGS would do
> the same as the UID FETCH FLAGS for every group, yes?
>
> At the very least LIST-STATUS should avoid the need to EXAMINE each
> group twice, yes?

Well, if you issue FETCH FLAGS, then you have to issue EXAMINE, too.

> If I get an i-d written up to support a FLAGS return type for LIST,
> would you be willing to add support for that to nnimap?

Returning the FLAGS for all the groups will be so much data that's it's
not generally useful.  However, a global QRESYNC would be excellent.
QRESYNC works by outputting all the flags that have changed since
<SEQUENCE>.  So if you said

LIST "" "%" RETURN (STATUS QRESYNC 43488328)

(or something) to return all the changed flags since that sequence
number, that would allow a really fast and comprehensive server->client
flag sync-up.

Have a look at RFC5162 for the QRESYNC description, but there it's only
a parameter to EXAMINE/SELECT, so you still need to EXAMINE all the mail
boxes, annoyingly enough.

But here's a thought: nnimap could have a "sloppy" mode.  In the sloppy
mode, it doesn't care about syncing flags that comprehensively, and
instead deferring that to when you enter the group.  The sloppy mode
could work with the LIST RETURN command, for instance, or an EXAMINE run
(with no FETCH FLAGS).  It would just look at UNSEEN and UIDNEXT, and
just say "if UNSEEN is 5, and UIDNEXT is 242, then we say that all
messages between 1-236 are read, and the last five are unread".  When
the group is entered, it issues a "FETCH FLAGS" and gets things right.

But this could be result in pretty brittle behaviour if everything isn't
done just right...

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@gnus.org * Lars Magne Ingebrigtsen

Re: fast list

[James Cloos]

>>>>> "LMI" == Lars Magne Ingebrigtsen <larsi@gnus.org> writes:

LMI> Well, if you issue FETCH FLAGS, then you have to issue EXAMINE, too.

LMI> Returning the FLAGS for all the groups will be so much data that's it's
LMI> not generally useful. 

Why not?  It is what gnus does now, just one group at a time instead of
all in one go.

LMI> However, a global QRESYNC would be excellent.  QRESYNC works by
LMI> outputting all the flags that have changed since <SEQUENCE>.  So if
LMI> you said

LMI> LIST "" "%" RETURN (STATUS QRESYNC 43488328)

LMI> (or something) to return all the changed flags since that sequence
LMI> number, that would allow a really fast and comprehensive
LMI> server->client flag sync-up.

True, but adding QRESYNC requires adding CONDSTORE, and the latter is a
big project.  I'd expect several days to get it right.

LMI> Have a look at RFC5162 for the QRESYNC description, but there it's only
LMI> a parameter to EXAMINE/SELECT, so you still need to EXAMINE all the mail
LMI> boxes, annoyingly enough.

Yeah, we'd need to do an i-d to register another extended list option.

LMI> But here's a thought: nnimap could have a "sloppy" mode.  In the sloppy
LMI> mode, it doesn't care about syncing flags that comprehensively, and
LMI> instead deferring that to when you enter the group.  The sloppy mode
LMI> could work with the LIST RETURN command, for instance, or an EXAMINE run
LMI> (with no FETCH FLAGS).  It would just look at UNSEEN and UIDNEXT, and
LMI> just say "if UNSEEN is 5, and UIDNEXT is 242, then we say that all
LMI> messages between 1-236 are read, and the last five are unread".  When
LMI> the group is entered, it issues a "FETCH FLAGS" and gets things right.

LMI> But this could be result in pretty brittle behaviour if everything isn't
LMI> done just right...

That would be closer to the way other clients tend to work, I'd imagine.
If it did that for startup and g, then M-g could continue to work like now.

The equivilent of UID FETCH FLAGS for every group, if done as a single
command, takes about one or two seconds, vs 20 minutes iterating through
one group at a time.  I am eager to fix that.

-JimC
-- 
James Cloos <cloos@jhcloos.com>         OpenPGP: 1024D/ED7DAEA6

Re: fast list

[Lars Magne Ingebrigtsen]

James Cloos <cloos@jhcloos.com> writes:

> Why not?  It is what gnus does now, just one group at a time instead of
> all in one go.

Gnus doesn't request all the flags not.  Only the last 100 or so.

> That would be closer to the way other clients tend to work, I'd imagine.
> If it did that for startup and g, then M-g could continue to work like now.

Other clients seem to do a LIST first, and then just do all the
EXAMINE/FETCH FLAGS things in the background in a separate thread.

> The equivilent of UID FETCH FLAGS for every group, if done as a single
> command, takes about one or two seconds, vs 20 minutes iterating through
> one group at a time.  I am eager to fix that.

Doing it as a single command will be faster, sure, but not that much
faster.  The requests aren't done in lock-step -- nnimap just spews out
all the requests, and then sits waiting at the end.  

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@gnus.org * Lars Magne Ingebrigtsen

Re: fast list

[Steinar Bang]

>>>>> Lars Magne Ingebrigtsen <larsi@gnus.org>:

> Returning the FLAGS for all the groups will be so much data that's
> it's not generally useful.  However, a global QRESYNC would be
> excellent.  QRESYNC works by outputting all the flags that have
> changed since <SEQUENCE>.  So if you said

That's why you need to M-g to sync up nnimap groups in different,
.newsrc.eld, so that they would have the right <SEQUENCE>?

But... if you read something on one gnus, and then go to a different
gnus, won't that different gnus have its old <SEQUENCE> and thus show
unread articles on the group(s)?

Obviously something I don't understand, because it does seem to
work... at least most of the time...:-)

Re: fast list

[James Cloos]

>>>>> "LMI" == Lars Magne Ingebrigtsen <larsi@gnus.org> writes:

LMI> Doing it as a single command will be faster, sure, but not that much
LMI> faster.  The requests aren't done in lock-step -- nnimap just spews
LMI> out all the requests, and then sits waiting at the end.  

No, it is wildly faster.  From the imap middleware point of view, it
replaces a quadratic (or worse?) algo with a linear algo.  Ie, one
sequential scan through the table rather than one scan per group.

(From the db manager's pov things are obviously more complicated than
just quadratic vs linear, but the speedup is still on the order of
super-linear -> linear.)

It doesn't matter much for a dozen groups.  Or even a couple of score.
But it is very significant when one splits busy lists like gnome-bugs,
gnome-commits, debian-bugs, et al into per-project groups.  (Those
make up 3/4 of my groups.)

-JimC
-- 
James Cloos <cloos@jhcloos.com>         OpenPGP: 1024D/ED7DAEA6

Re: fast list

[Steinar Bang]

>>>>> James Cloos <cloos@jhcloos.com>:

> It doesn't matter much for a dozen groups.  Or even a couple of score.
> But it is very significant when one splits busy lists like gnome-bugs,
> gnome-commits, debian-bugs, et al into per-project groups.  (Those
> make up 3/4 of my groups.)

Hm... many of those are possibly available as NNTP groups on
http://gmane.org ...?

(On the other hand it's good for nnimap to be excercised by extreme
cases...)

Re: fast list

[Lars Magne Ingebrigtsen]

Steinar Bang <sb@dod.no> writes:

> That's why you need to M-g to sync up nnimap groups in different,
> .newsrc.eld, so that they would have the right <SEQUENCE>?

If something had messed up something earlier, `M-g' should fix it, since
it does a complete clean sweep.

> But... if you read something on one gnus, and then go to a different
> gnus, won't that different gnus have its old <SEQUENCE> and thus show
> unread articles on the group(s)?

When you hit `g' in the old Gnus, it'll use the old <SEQUENCE> to get
data on all new flags and messages.

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@gnus.org * Lars Magne Ingebrigtsen

Re: fast list

[Lars Magne Ingebrigtsen]

James Cloos <cloos@jhcloos.com> writes:

> No, it is wildly faster.  From the imap middleware point of view, it
> replaces a quadratic (or worse?) algo with a linear algo.  Ie, one
> sequential scan through the table rather than one scan per group.

Why is that quadratic?  It should just be a linear scan over a smaller
subset, shouldn't it?

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@gnus.org * Lars Magne Ingebrigtsen

Re: fast list

[Lars Magne Ingebrigtsen]

Steinar Bang <sb@dod.no> writes:

> (On the other hand it's good for nnimap to be excercised by extreme
> cases...)

Yes.  :-)

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@gnus.org * Lars Magne Ingebrigtsen

Re: fast list

[James Cloos]

>>>>> "SB" == Steinar Bang <sb@dod.no> writes:

SB> Hm... many of those are possibly available as NNTP groups on
SB> http://gmane.org ...?

Posting isn't always reliable and my bw is often quite limited and I
often read when completely offline; it is much better to background-
poll for batches than to have to interactively use precious bw.

Plus, gmane doesn't split those groups.

SB> (On the other hand it's good for nnimap to be excercised by
SB> extreme cases...)

And it works better than anything else.  Startup and g are slow
because IMAP (the protocol itself) lacks a command to get all of
the data gnus wants in one go, and because elisp can be slow when
parsing LARGE buffers of retrieved data.  (I hope Stefan's recent
patch to use unibyte buffers for the protocol streams might help
reduce that memory pressure.)

Long term I should skip the imap middleware and connect Emacs to
the db directly.  It looks like the new nnimap may be an easier
model to follow when writing such a gnus backend.  But for now...

-JimC
-- 
James Cloos <cloos@jhcloos.com>         OpenPGP: 1024D/ED7DAEA6

Re: fast list

[James Cloos]

>>>>> "LMI" == Lars Magne Ingebrigtsen <larsi@gnus.org> writes:

JC> No, it is wildly faster.  From the imap middleware point of view, it
JC> replaces a quadratic (or worse?) algo with a linear algo.  Ie, one
JC> sequential scan through the table rather than one scan per group.

LMI> Why is that quadratic?  It should just be a linear scan over a smaller
LMI> subset, shouldn't it?

It takes about as long to grab the EXAMINE and UID FETCH FLAGS data for
one group as it does for a set of groups.

I suppose that it is possible that it is not actually quadratic, but it
is definatly super-linear.  20k is a *lot* slower than 2k.

-JimC
-- 
James Cloos <cloos@jhcloos.com>         OpenPGP: 1024D/ED7DAEA6

Re: fast list

[Lars Magne Ingebrigtsen]

James Cloos <cloos@jhcloos.com> writes:

> I suppose that it is possible that it is not actually quadratic, but it
> is definatly super-linear.  20k is a *lot* slower than 2k.

What do you mean by "20k vs 2k"?  The amount of data returned would be
the same, anyway, wouldn't it?

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@gnus.org * Lars Magne Ingebrigtsen

Re: fast list

[James Cloos]

>>>>> "LMI" == Lars Magne Ingebrigtsen <larsi@gnus.org> writes:

LMI> What do you mean by "20k vs 2k"?  The amount of data returned would be
LMI> the same, anyway, wouldn't it?

20000 groups vs 2000 groups.

The amount of data is the same, it just takes longer to grab it one
group at a time than all at once.  Part of the extra delay is the extra
round trips.  Part of it is that scanning the tables and indices for
one group takes nearly as long as scanning them for all of the groups.

Even if I create a sql fucntion which grabs the list of groups (the
UIDVALIDITY values in IMAP) and then iterates through that list one
UIDVALIDITY at a time, grabbing that groups data, it still takes on
the order of 20ms per group.  But grabbing all of that data at once
takes something like 25µs per group.

I did get working list-status support added to my dbmail.  I now want
to add a TAGS return type to list all of the tags, too.

I think I can follow you new nnimap well enough to propose a patch to
use list-status and list-tags.  (I prefer C or Perl, am far from
illiterate in lisp, but the old nnimap.el/imap.el bested me when I
tried to debug the two or three non-speed-related bugs which I hit.)

-JimC
-- 
James Cloos <cloos@jhcloos.com>         OpenPGP: 1024D/ED7DAEA6

Re: fast list

[Lars Magne Ingebrigtsen]

James Cloos <cloos@jhcloos.com> writes:

> The amount of data is the same, it just takes longer to grab it one
> group at a time than all at once.  Part of the extra delay is the extra
> round trips.

There are no extra round trips between Gnus and the IMAP server.  The
data is streamed.

> Part of it is that scanning the tables and indices for
> one group takes nearly as long as scanning them for all of the groups.

Yeah, that would explain the slow-down.  But I don't think that's
something that's true for most IMAP servers.

> I think I can follow you new nnimap well enough to propose a patch to
> use list-status and list-tags.  (I prefer C or Perl, am far from
> illiterate in lisp, but the old nnimap.el/imap.el bested me when I
> tried to debug the two or three non-speed-related bugs which I hit.)

Yes, it was kinda abstract.  :-)

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@gnus.org * Lars Magne Ingebrigtsen

Re: fast list

[James Cloos]

>>>>> "LMI" == Lars Magne Ingebrigtsen <larsi@gnus.org> writes:

LMI> James Cloos <cloos@jhcloos.com> writes:
>> The amount of data is the same, it just takes longer to grab it one
>> group at a time than all at once.  Part of the extra delay is the extra
>> round trips.

LMI> There are no extra round trips between Gnus and the IMAP server.  The
LMI> data is streamed.

But there is between the imapd and the sql server when using something
like dbmail, archivopterix or similar.

>> Part of it is that scanning the tables and indices for
>> one group takes nearly as long as scanning them for all of the groups.

LMI> Yeah, that would explain the slow-down.  But I don't think that's
LMI> something that's true for most IMAP servers.

Even those which do not have the imapd as a middleware can benefit from
streaming the disk accesses.

-JimC
-- 
James Cloos <cloos@jhcloos.com>         OpenPGP: 1024D/ED7DAEA6

Re: fast list

[Lars Magne Ingebrigtsen]

James Cloos <cloos@jhcloos.com> writes:

> But there is between the imapd and the sql server when using something
> like dbmail, archivopterix or similar.

Ah, right.

-- 
(domestic pets only, the antidote for overdose, milk.)
  larsi@gnus.org * Lars Magne Ingebrigtsen