[pkg-fetchmail-maint] Bug#798803: fetchmail: Slowness when .fetchids file grows large

[Mark Triggs]

Package: fetchmail
Version: 6.3.26-1+b1
Severity: normal
Tags: patch upstream

Dear Maintainer,

Recently I've noticed that running 'fetchmail' to awake my background
fetchmail daemon is quite slow.  It takes around 5 seconds to return,
where previously it was pretty much instantaneous.

I ran fetchmail under callgrind and found that it was spending all of
its time loading my (large) .fetchids file into a linked list.  I've
got a POP3 server with all messages kept on it, and my .fetchids file
contains around 50,000 entries (I should probably switch to IMAP ;)

>From what I can see, the issue is that each ID from .fetchids is
appended to a linked list (by initialize_saved_lists() in uid.c), but
the append operation (save_str) has to scan the entire linked list
from head to tail on every append operation.  As a result, the process
of reading the file is O(N^2) instead of O(N).

There's a struct member on 'struct query' called 'oldsavedend' that
was unused and seemed like it might have been intended to track the
end of the linked list, so I've modified uid.c to use that
variable--keeping track of the last node in the linked list and
avoiding the full scan.  I've attached a patch for that, and
performance is back to instantaneous in my testing.

It's a pretty minor thing, but easy enough to fix so I thought I'd
report it.

Cheers,

Mark

-- System Information:
Debian Release: 8.1
  APT prefers stable
  APT policy: (500, 'stable')
Architecture: amd64 (x86_64)
Foreign Architectures: i386

Kernel: Linux 3.16.0-4-amd64 (SMP w/8 CPU cores)
Locale: LANG=en_AU.UTF-8, LC_CTYPE=en_AU.UTF-8 (charmap=UTF-8) (ignored: LC_ALL set to en_AU.UTF-8)
Shell: /bin/sh linked to /bin/dash
Init: systemd (via /run/systemd/system)

Versions of packages fetchmail depends on:
ii  adduser           3.113+nmu3
ii  debianutils       4.4+b1
ii  libc6             2.19-18
ii  libcomerr2        1.42.12-1.1
ii  libgssapi-krb5-2  1.12.1+dfsg-19
ii  libkrb5-3         1.12.1+dfsg-19
ii  libssl1.0.0       1.0.1k-3+deb8u1
ii  lsb-base          4.1+Debian13+nmu1

Versions of packages fetchmail recommends:
ii  ca-certificates  20141019

Versions of packages fetchmail suggests:
pn  fetchmailconf                 <none>
pn  resolvconf                    <none>
ii  ssmtp [mail-transport-agent]  2.64-8

-- no debconf information
-------------- next part --------------
A non-text attachment was scrubbed...
Name: idlist-performance.diff
Type: text/x-diff
Size: 1629 bytes
Desc: not available
URL: <http://lists.alioth.debian.org/pipermail/pkg-fetchmail-maint/attachments/20150913/c04fbb5d/attachment.diff>