Why article numbers?

Why article numbers?

[Kai Großjohann]

Now that I'm thinking about it again, maybe it is possible to migrate
all of Gnus away from article numbers as identifiers, towards some
opaque data type?  That would facilitate some new features (such as
offline message moving).

One could implement a data type for the article "numbers", then use
that data type throughout.  Then one could change the implementation
of that data type to something incompatible with article numbers to
ensure that it is used everywhere.  Then various backends could use
whatever they liked.

It would destroy using ranges.  Are ranges important in Gnus?  How
could bad side effects be avoided on the transition to, say, message
ids?

Maybe the most difficult part is the "marked as read" thing: how do
you use message ids to store the fact that articles 1 through 50,000,
say, have been read by the user or disappeared altogether?  If you
store the first message id that has been read, and then that message
is moved to another group or canceled...  Whee.

Thoughts?
-- 
A turnip curses Elvis

Re: Why article numbers?

[Lars Magne Ingebrigtsen]

kai.grossjohann@uni-duisburg.de (Kai Großjohann) writes:

> Now that I'm thinking about it again, maybe it is possible to migrate
> all of Gnus away from article numbers as identifiers, towards some
> opaque data type? 

I think that's impossible.  Gnus deals with groups that commonly have
hundreds of thousands of articles in them.  Doing anything but
integers will be too slow.

(That is, until we get 45THz CPUs and 1PB RAM.)

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

Re: Why article numbers?

[Paul Jarc]

Lars Magne Ingebrigtsen <larsi@gnus.org> wrote:
> Gnus deals with groups that commonly have hundreds of thousands of
> articles in them.  Doing anything but integers will be too slow.

If we only allow symbols, we can still use eq, assq, etc., but we
still get all the benefits of using arbitrary objects as identifiers.
I think the only advantage of integers over symbols is in representing
large contiguous ranges.  Can you give us some examples of places
where compact representations are really essential?


paul

Re: Why article numbers?

[Lars Magne Ingebrigtsen]

prj@po.cwru.edu (Paul Jarc) writes:

> I think the only advantage of integers over symbols is in representing
> large contiguous ranges.  Can you give us some examples of places
> where compact representations are really essential?

Well, anywhere, basically.

You enter a group.  The server says that the available articles are
50000-60000.  You have a list of, er, ids.  How many articles should
you fetch if the user wants all unread articles?

You want to mark the unseen messages as unseen.  Keep a list of all
seen ids?

Etc.  Integers are small and collapsible.  IDs are not.

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

Re: Why article numbers?

[Kai Großjohann]

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

> prj@po.cwru.edu (Paul Jarc) writes:
>
>> I think the only advantage of integers over symbols is in representing
>> large contiguous ranges.  Can you give us some examples of places
>> where compact representations are really essential?
>
> Well, anywhere, basically.
>
> You enter a group.  The server says that the available articles are
> 50000-60000.  You have a list of, er, ids.  How many articles should
> you fetch if the user wants all unread articles?

This could be worked around by storing the numbers together with the
msg ids.  Hm.  Ugly.

> You want to mark the unseen messages as unseen.  Keep a list of all
> seen ids?

Keep a list of unseen ids :-)


But there are problems with using the numbers, too, so I think it
would be useful to get a list of pros/cons or a discussion or
something like this so that somebody might have a bright insight how
to combine the advantages of both.
-- 
A turnip curses Elvis

Re: Why article numbers?

[Paul Jarc]

Lars Magne Ingebrigtsen <larsi@gnus.org> wrote:
> You enter a group.  The server says that the available articles are
> 50000-60000.  You have a list of, er, ids.  How many articles should
> you fetch if the user wants all unread articles?

Don't ask for a particular number of articles.  Ask for "all unread
articles".  Require backends to store marks, so they can figure out
which articles are unread.

Also note that numbers are still very natural article identifiers for
some backends, like nntp.  Those backends could continue to use
numbers, and could do range compression in their storage.  We would
only *allow* identifiers to be non-numeric, not require it.  The only
requirement would be that identifiers must satisfy eq if they are
supposed to identify the same article.  Then the code that takes
advantage of numeric identifiers can be pushed to the other side of
the backend interface.  It would be a lot of work, but I don't think
there any any inherent problems beyond that.

> You want to mark the unseen messages as unseen.  Keep a list of all
> seen ids?

nnmaildir already keeps a list of all 'read articles, and would do the
same for 'seen if those were passed to the backend (as I think they
should be).


paul

Re: Why article numbers?

[Lars Magne Ingebrigtsen]

prj@po.cwru.edu (Paul Jarc) writes:

> Don't ask for a particular number of articles.  Ask for "all unread
> articles".

That's not what the user asks for.  The user may ask for "the last
200 articles, whether read or unread", or "the last 5 read articles". 

> Also note that numbers are still very natural article identifiers for
> some backends, like nntp.  Those backends could continue to use
> numbers, and could do range compression in their storage.  We would
> only *allow* identifiers to be non-numeric, not require it.  The only
> requirement would be that identifiers must satisfy eq if they are
> supposed to identify the same article.  Then the code that takes
> advantage of numeric identifiers can be pushed to the other side of
> the backend interface.  It would be a lot of work, but I don't think
> there any any inherent problems beyond that.

"A lot of work" is an understatement, but what would the advantages
be?  (Other than making hard disk and ram manufacturers happy, that
is.)

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

Re: Why article numbers?

[Kai Großjohann]

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

> "A lot of work" is an understatement, but what would the advantages
> be?  (Other than making hard disk and ram manufacturers happy, that
> is.)

If Gnus stored marks for message ids instead of article numbers:

* you could move from one news server to another without losing your
  marks, and without gnus-move-to-another-server, or what is it
  called;

* nnimap could store marks that survive uidvalidity changes;

* you could mark articles that were retrieved via `^';

* the cache would survive server-side renumbering, as would the agent.

I'm sure there are others.
-- 
A preposition is not a good thing to end a sentence with.

Re: Why article numbers?

[Lars Magne Ingebrigtsen]

kai.grossjohann@uni-duisburg.de (Kai Großjohann) writes:

> If Gnus stored marks for message ids instead of article numbers:
>
> * you could move from one news server to another without losing your
>   marks, and without gnus-move-to-another-server, or what is it
>   called;

Uhm...  no, I don't think so.  For that to work, nntp.el would have to
maintain a complete mapping between article numbers and Message-IDs
for all articles on both servers (ok, for all the groups you're
reading), which just isn't quite practical.

> * you could mark articles that were retrieved via `^';

That's already possible assuming the nntp server is sane.

> * the cache would survive server-side renumbering, as would the agent.

That's true.

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

Re: Why article numbers?

[Kai Großjohann]

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

> kai.grossjohann@uni-duisburg.de (Kai Großjohann) writes:
>
>> If Gnus stored marks for message ids instead of article numbers:
>>
>> * you could move from one news server to another without losing your
>>   marks, and without gnus-move-to-another-server, or what is it
>>   called;
>
> Uhm...  no, I don't think so.  For that to work, nntp.el would have to
> maintain a complete mapping between article numbers and Message-IDs
> for all articles on both servers (ok, for all the groups you're
> reading), which just isn't quite practical.

Why does nntp.el need the article numbers?
-- 
A preposition is not a good thing to end a sentence with.

Re: Why article numbers?

[Lars Magne Ingebrigtsen]

kai.grossjohann@uni-duisburg.de (Kai Großjohann) writes:

> Why does nntp.el need the article numbers?

Because that's what nntp.el needs to feed to the nntp server.

Upon group entry, nntp.el will issue commands like "XOVER 23-42".

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

Re: Why article numbers?

[Kai Großjohann]

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

> kai.grossjohann@uni-duisburg.de (Kai Großjohann) writes:
>
>> Why does nntp.el need the article numbers?
>
> Because that's what nntp.el needs to feed to the nntp server.

Hm.  Bad server!
-- 
A preposition is not a good thing to end a sentence with.

Re: Why article numbers?

[Simon Josefsson]

kai.grossjohann@uni-duisburg.de (Kai Großjohann) writes:

> Lars Magne Ingebrigtsen <larsi@gnus.org> writes:
>
>> "A lot of work" is an understatement, but what would the advantages
>> be?  (Other than making hard disk and ram manufacturers happy, that
>> is.)
>
> If Gnus stored marks for message ids instead of article numbers:
>
> * you could move from one news server to another without losing your
>   marks, and without gnus-move-to-another-server, or what is it
>   called;
>
> * nnimap could store marks that survive uidvalidity changes;
>
> * you could mark articles that were retrieved via `^';
>
> * the cache would survive server-side renumbering, as would the agent.

How would you handle two messages with the same message-id?  Or no
message-id (think drafts)?  Since it is possible to create that
scenario, Gnus should IMHO handle it.  I think an abstract data type
separated from the message itself is more flexible.  I see two
problems with the use of integers today: handling sets of integers can
be slow, and the integer limit in emacs is too small.

Regarding the nnimap issue, a better solution would IMHO be to fix it
to do proper re-syncing on UIDVALIDITY changes, which it probably
would have to do even if message-id's are used to index articles since
IMAP uses integers to retrieve articles anyway.

Re: Why article numbers?

[Kai Großjohann]

Simon Josefsson <jas@extundo.com> writes:

> How would you handle two messages with the same message-id?  Or no
> message-id (think drafts)?  Since it is possible to create that
> scenario, Gnus should IMHO handle it.  I think an abstract data type
> separated from the message itself is more flexible.  I see two
> problems with the use of integers today: handling sets of integers can
> be slow, and the integer limit in emacs is too small.

Do you think dealing with a set of 1,000,000 integers is slower than
dealing with a set of 1,000,000 strings, say?

For the integer limit, well, err, somebody should do bignums in Emacs
Lisp :-)

> Regarding the nnimap issue, a better solution would IMHO be to fix it
> to do proper re-syncing on UIDVALIDITY changes, which it probably
> would have to do even if message-id's are used to index articles since
> IMAP uses integers to retrieve articles anyway.

Is this possible?
-- 
A preposition is not a good thing to end a sentence with.

Re: Why article numbers?

[Simon Josefsson]

kai.grossjohann@uni-duisburg.de (Kai Großjohann) writes:

> Simon Josefsson <jas@extundo.com> writes:
>
>> How would you handle two messages with the same message-id?  Or no
>> message-id (think drafts)?  Since it is possible to create that
>> scenario, Gnus should IMHO handle it.  I think an abstract data type
>> separated from the message itself is more flexible.  I see two
>> problems with the use of integers today: handling sets of integers can
>> be slow, and the integer limit in emacs is too small.
>
> Do you think dealing with a set of 1,000,000 integers is slower than
> dealing with a set of 1,000,000 strings, say?

I don't know, but I suspect not.

> For the integer limit, well, err, somebody should do bignums in Emacs
> Lisp :-)

Yes, please. :-)

>> Regarding the nnimap issue, a better solution would IMHO be to fix it
>> to do proper re-syncing on UIDVALIDITY changes, which it probably
>> would have to do even if message-id's are used to index articles since
>> IMAP uses integers to retrieve articles anyway.
>
> Is this possible?

To fix it?  The situation is detected now (but ignored).  What would
be required to make it work, would be to wipe out the gnus info for
that group and replace it with new data from the server.  If the agent
is used, the NOV cache and .agentview and cached articles must be
removed too.  As for cached articles, I'm not sure to handle them --
removing locally cached articles might be a bad idea since the user
might want to keep them.  Gnus-specific flags (i.e., bookmarks) simply
would have to be dropped unless some more information (like
message-id) about the marked articles were available to search for its
new article number.  It is a lot of work, and no backend interface to
do it so nnimap would have to contain even more Gnus internal
knowledge.  Fortunately, people rarely send bug reports about this (I
can rememeber <5 times this was the real cause of a problem) so either
it isn't that important or people give up Gnus for some other client
and doesn't tell us.

Re: Why article numbers?

[Kai Großjohann]

Simon Josefsson <jas@extundo.com> writes:

> kai.grossjohann@uni-duisburg.de (Kai Großjohann) writes:
>
>> Simon Josefsson <jas@extundo.com> writes:
>>
>>> Regarding the nnimap issue, a better solution would IMHO be to fix it
>>> to do proper re-syncing on UIDVALIDITY changes, which it probably
>>> would have to do even if message-id's are used to index articles since
>>> IMAP uses integers to retrieve articles anyway.
>>
>> Is this possible?
>
> To fix it?  The situation is detected now (but ignored).  What would
> be required to make it work, would be to wipe out the gnus info for
> that group and replace it with new data from the server.  If the agent
> is used, the NOV cache and .agentview and cached articles must be
> removed too.  As for cached articles, I'm not sure to handle them --
> removing locally cached articles might be a bad idea since the user
> might want to keep them.  Gnus-specific flags (i.e., bookmarks) simply
> would have to be dropped unless some more information (like
> message-id) about the marked articles were available to search for its
> new article number.  It is a lot of work, and no backend interface to
> do it so nnimap would have to contain even more Gnus internal
> knowledge.  Fortunately, people rarely send bug reports about this (I
> can rememeber <5 times this was the real cause of a problem) so either
> it isn't that important or people give up Gnus for some other client
> and doesn't tell us.

Yeah.  What I think should happen is a renumbering.  For the cache,
renumbering is actually easier, most of the time: just renumber the
cached articles to start at 1, and you'll be fine in most cases.

The copies in the agent are a thornier issue.  I think it would not
be good to just delete them: they will then be fetched again from the
server, which is a waste of bandwidth that we wanted to avoid by
using the agent in the first place...

If you have an index of the local copies by message id, then you
could just ask the server for the headers (NOV) and then search for
articles mentioned there by message id.  That tells you which number
to use locally, and then there could be some articles that aren't
found on the server -- we want to delete them I think.

Hm.

Maybe the cache should be treated a little bit like a separate
backend, kind of like nnvirtual does it, at least conceptually.  I
think it would be best to just decouple the numbers used in the cache
totally from the numbers used on the server.  This leads to problems
when the cached articles are still on the server, but oh, well.

For the agent, the renumbering approach appears to be best.  (`Lost'
articles could be moved from the agent to the cache instead of
deleting them, now that I think about it.)

-- 
A preposition is not a good thing to end a sentence with.

Re: Why article numbers?

[Simon Josefsson]

kai.grossjohann@uni-duisburg.de (Kai Großjohann) writes:

> Yeah.  What I think should happen is a renumbering.  For the cache,
> renumbering is actually easier, most of the time: just renumber the
> cached articles to start at 1, and you'll be fine in most cases.

What if there is an article with number 1 on the server?  (But see
below too.)

> The copies in the agent are a thornier issue.  I think it would not
> be good to just delete them: they will then be fetched again from the
> server, which is a waste of bandwidth that we wanted to avoid by
> using the agent in the first place...

Yes, although that is an optimization.  Deleting them would at least
make things correct.

> If you have an index of the local copies by message id, then you
> could just ask the server for the headers (NOV) and then search for
> articles mentioned there by message id.  That tells you which number
> to use locally, and then there could be some articles that aren't
> found on the server -- we want to delete them I think.

Yes.

> Maybe the cache should be treated a little bit like a separate
> backend, kind of like nnvirtual does it, at least conceptually.  I
> think it would be best to just decouple the numbers used in the cache
> totally from the numbers used on the server.  This leads to problems
> when the cached articles are still on the server, but oh, well.

This sounds like a good idea.  So conceptually there is a nncache
which contains the articles you put into it with `*', and the nncache
groups mirror all your normal groups.  And when you enter a group it
is like entering a nnvirtual that contains the nncache group and the
real group.

OTOH it sounds like work, and might expose other unwanted behaviour,
so I'm not sure if it is worth the time to really implement it like
this...

Re: Why article numbers?

[Kai Großjohann]

Simon Josefsson <jas@extundo.com> writes:

> kai.grossjohann@uni-duisburg.de (Kai Großjohann) writes:
>
>> Yeah.  What I think should happen is a renumbering.  For the cache,
>> renumbering is actually easier, most of the time: just renumber the
>> cached articles to start at 1, and you'll be fine in most cases.
>
> What if there is an article with number 1 on the server?  (But see
> below too.)

That's why I said `in most cases'.  Hm.

Gnus could offset all numbers by the number of cached articles in the
group -- then the backend would have to know about it and it would
have to treat all incoming article numbers appropriately.  Whee...

>> The copies in the agent are a thornier issue.  I think it would not
>> be good to just delete them: they will then be fetched again from the
>> server, which is a waste of bandwidth that we wanted to avoid by
>> using the agent in the first place...
>
> Yes, although that is an optimization.  Deleting them would at least
> make things correct.

Yes.  Hm.  Yeah, why not make it correct and slow first.

One possible optimization would be to find out if the uidvalidity
change actually resulted in different article numbers being used.  I
have the impression that this is often not the case.

>> Maybe the cache should be treated a little bit like a separate
>> backend, kind of like nnvirtual does it, at least conceptually.  I
>> think it would be best to just decouple the numbers used in the cache
>> totally from the numbers used on the server.  This leads to problems
>> when the cached articles are still on the server, but oh, well.
>
> This sounds like a good idea.  So conceptually there is a nncache
> which contains the articles you put into it with `*', and the nncache
> groups mirror all your normal groups.  And when you enter a group it
> is like entering a nnvirtual that contains the nncache group and the
> real group.

That was my idea.

> OTOH it sounds like work, and might expose other unwanted behaviour,
> so I'm not sure if it is worth the time to really implement it like
> this...

Hah, if it wasn't work it'd be implemented already ;-)

-- 
A preposition is not a good thing to end a sentence with.

Re: Why article numbers?

[Lars Magne Ingebrigtsen]

kai.grossjohann@uni-duisburg.de (Kai Großjohann) writes:

> For the integer limit, well, err, somebody should do bignums in Emacs
> Lisp :-)

I'd be happy with 32-bit integers in Emacs, even.  :-)

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

Re: Why article numbers?

[Michael Shields]

In article <84n0kn9vdh.fsf@lucy.is.informatik.uni-duisburg.de>,
kai.grossjohann@uni-duisburg.de (Kai Großjohann) wrote:
> For the integer limit, well, err, somebody should do bignums in Emacs
> Lisp :-)

Calc has code for this, although it's probably not very fast.
-- 
Shields.

Re: Why article numbers?

[Paul Jarc]

I think I should point out that Kai and I seem to be advocating
slightly different things.  Kai's suggestion, AIUI, is to use
Message-ID header fields as article IDs everywhere.  My suggestion is
to let backends decide how to identify articles, with the only
requirement being that identifiers should be eq if they are supposed
to identify the same article.  (This includes the possibility of
symbols whose names are Message-IDs, but does not require that.)

Lars Magne Ingebrigtsen <larsi@gnus.org> wrote:
> prj@po.cwru.edu (Paul Jarc) writes:
>> Don't ask for a particular number of articles.  Ask for "all unread
>> articles".
>
> That's not what the user asks for.  The user may ask for "the last
> 200 articles, whether read or unread", or "the last 5 read articles".

You're changing the question.  Originally you said:

>>> How many articles should you fetch if the user wants all unread
>>> articles?

If the user asks for "all unread articles", then Gnus can ask the
backend for "all unread articles".  If the user asks for "the last 200
articles, whether read or unread", then Gnus can ask the backend for
"the last 200 articles, whether read or unread".  If the user asks for
"the last 5 read articles", then Gnus can ask the backend for "the
last 5 read articles".

The point is that the work that benefits from knowing that article IDs
are integers does not have to be abandoned; it can simply be pushed
inside the backend.  So for backends that naturally use integers as
identifiers, there would just be a restructuring of the existing code,
with approximately zero change in performance.  Backends that have to
do extra work to assign numbers to articles would have the opportunity
to try using other types of objects as IDs, but if that strategy turns
out to be worse for whatever reason, then they can still go back to
using integers.

> "A lot of work" is an understatement

I won't argue with that.  It might even be so much work that it will
never happen, unfortunately.  But my claim is that it is possible, and
if done right, would not cause performance hits.


paul

Re: Why article numbers?

[Michael Shields]

In article <m3lm08xa74.fsf@multivac.cwru.edu>,
prj@po.cwru.edu (Paul Jarc) wrote:
> I think I should point out that Kai and I seem to be advocating
> slightly different things.  Kai's suggestion, AIUI, is to use
> Message-ID header fields as article IDs everywhere.

One wrinkle with this is that it's possible for messages to have no
message-ID.  This never happens in news or with most MTAs, but it's
legal in mail.  One way it can happen is when using `G f' to read an
mbox-format archive that has incomplete headers.

It's also possible, and not uncommon, for the same mail message to be
delivered twice -- because you receive it both directly and via a
mailing list, or theoretically because an SMTP connection was dropped
after the "." but before the acknowledgment.

> My suggestion is
> to let backends decide how to identify articles, with the only
> requirement being that identifiers should be eq if they are supposed
> to identify the same article.  (This includes the possibility of
> symbols whose names are Message-IDs, but does not require that.)

That seems reasonable, especially sine it lets the conversion be done
one backend at a time, or not at all for some backends.

For mail with no message-ID, fake ones could be generated; I seem to
remember VM doing this (with "@toto.iv").  I'm not sure what is the
best way to handle duplicates.

Message-IDs are fine identifiers for news.
-- 
Shields.

Re: Why article numbers?

[Kai Großjohann]

prj@po.cwru.edu (Paul Jarc) writes:

> I think I should point out that Kai and I seem to be advocating
> slightly different things.  Kai's suggestion, AIUI, is to use
> Message-ID header fields as article IDs everywhere.  My suggestion is
> to let backends decide how to identify articles, with the only
> requirement being that identifiers should be eq if they are supposed
> to identify the same article.  (This includes the possibility of
> symbols whose names are Message-IDs, but does not require that.)

Actually, I should be advocating the same as you are, even though
what I said doesn't match this.

Article identifiers should be an opaque object, an abstract data
type.
-- 
A preposition is not a good thing to end a sentence with.

Re: Why article numbers?

[Lars Magne Ingebrigtsen]

prj@po.cwru.edu (Paul Jarc) writes:

> If the user asks for "all unread articles", then Gnus can ask the
> backend for "all unread articles".  If the user asks for "the last 200
> articles, whether read or unread", then Gnus can ask the backend for
> "the last 200 articles, whether read or unread".  If the user asks for
> "the last 5 read articles", then Gnus can ask the backend for "the
> last 5 read articles".

That means that the backend must have intimate knowledge of all these
things.  That's certainly not the case now -- nntp.el, for instance,
has no knowledge what-so-ever about these things.  (nnml.el is
getting to know more about these things, but the volume in nnml
versus nntp is on a different plane.  And Gnus is a news reader.  :-)

> I won't argue with that.  It might even be so much work that it will
> never happen, unfortunately.  But my claim is that it is possible, and
> if done right, would not cause performance hits.

This kind of added complexity almost invariably causes performance
hits, in my experience.

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