Re: [Dovecot] Better APPEND performance
What can be done to make maildir_uidlist_refresh_fast_init() choose the fast path more often? Pretty simple bug. Fixed: http://hg.dovecot.org/dovecot-1.2/rev/ebdba086e3b1 This makes the performance pretty good when appending to maildirs with large number of messages. Sure does! Thanks, that fixes it!
Re: [Dovecot] Better APPEND performance
On Wed, 2009-10-14 at 12:48 -0400, Timo Sirainen wrote: > On Wed, 2009-10-07 at 17:53 -0500, Mike Abbott wrote: > > What can be done to make maildir_uidlist_refresh_fast_init() choose > > the fast path more often? > > Pretty simple bug. Fixed: > http://hg.dovecot.org/dovecot-1.2/rev/ebdba086e3b1 > > This makes the performance pretty good when appending to maildirs with > large number of messages. In my desktop the append speed stays pretty > constant at ~500 msgs/sec after 20k messages, while without the patch it > crawls at ~30-40 msgs/sec. This is also useful for maildir_very_dirty_syncs=yes, otherwise dovecot-uidlist never shrinks: http://hg.dovecot.org/dovecot-1.2/rev/7956cc1086e1 signature.asc Description: This is a digitally signed message part
Re: [Dovecot] Better APPEND performance
On Wed, 2009-10-07 at 17:53 -0500, Mike Abbott wrote: > What can be done to make maildir_uidlist_refresh_fast_init() choose > the fast path more often? Pretty simple bug. Fixed: http://hg.dovecot.org/dovecot-1.2/rev/ebdba086e3b1 This makes the performance pretty good when appending to maildirs with large number of messages. In my desktop the append speed stays pretty constant at ~500 msgs/sec after 20k messages, while without the patch it crawls at ~30-40 msgs/sec. signature.asc Description: This is a digitally signed message part
Re: [Dovecot] Better APPEND performance
Timo Sirainen wrote: On Wed, 2009-10-07 at 17:53 -0500, Mike Abbott wrote: 1. For every other APPENDed message, dovecot appends the new UID to the list quickly. No problem here, this is fast. 2. For every other other APPENDed message, dovecot scans the entire UID list. This is an O(n) algorithm. Since it happens every n/2 times it causes O(n^2) behavior across n consecutive APPENDs. I'll look at this more closely later, but did you already try maildir_very_dirty_syncs=yes? Does this behavior happen also with it? Hello Timo, Also i have observed this behaviour. Although i think it's not the most urgent matter, it would really be nice if you could speed up massive message imports. In our case, we don't use it that much for migration, but sometimes some POP users like to be able to backup their messages in the IMAP server. Thanks in advance, Hugo Monteiro. -- ci.fct.unl.pt:~# cat .signature Hugo Monteiro Email: hugo.monte...@fct.unl.pt Telefone : +351 212948300 Ext.15307 Web : http://hmonteiro.net Centro de Informática Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa Quinta da Torre 2829-516 Caparica Portugal Telefone: +351 212948596 Fax: +351 212948548 www.ci.fct.unl.pt ap...@fct.unl.pt ci.fct.unl.pt:~# _
Re: [Dovecot] Better APPEND performance
did you already try maildir_very_dirty_syncs=yes Yes. It has no effect on the behavior I observe.
Re: [Dovecot] Better APPEND performance
On Wed, 2009-10-07 at 17:53 -0500, Mike Abbott wrote: > 1. For every other APPENDed message, dovecot appends the new UID to > the list quickly. No problem here, this is fast. > 2. For every other other APPENDed message, dovecot scans the entire > UID list. This is an O(n) algorithm. Since it happens every n/2 > times it causes O(n^2) behavior across n consecutive APPENDs. I'll look at this more closely later, but did you already try maildir_very_dirty_syncs=yes? Does this behavior happen also with it? signature.asc Description: This is a digitally signed message part
[Dovecot] Better APPEND performance
Moving a large number of messages into an IMAP folder on a dovecot server takes quite a long time. This is a popular operation for users migrating their stored messages from their old mail servers through a mail user agent, and it causes a poor first impression of dovecot. I'd like your help to speed this up. I have studied this problem in recent versions, including 1.1.[17-19] and 1.2.[4-6] but I'll focus on 1.2.6, using Maildir++. It seems to be caused by O(n^2) behavior in maintaining the UID list, where n is the number of messages. The client selects a folder then sends thousands of individual APPEND commands (no use of multiappend unfortunately). These cause dovecot to behave as follows: 1. For every other APPENDed message, dovecot appends the new UID to the list quickly. No problem here, this is fast. 2. For every other other APPENDed message, dovecot scans the entire UID list. This is an O(n) algorithm. Since it happens every n/2 times it causes O(n^2) behavior across n consecutive APPENDs. More specifically, 1. APPEND a message to a folder that already contains 30,000 messages. maildir_uidlist_refresh_fast_init() takes the fast path. 2. APPEND a second message to the same folder. maildir_uidlist_refresh_fast_init() takes the slow path: it populates the uidlist->files hash table with all the UIDs, checking for duplicates. At the end of the command maildir_uidlist_deinit() destroys the hash table. Note how this APPEND takes much longer than #1. 3. APPEND a third message to the same folder. Just like #1. 4. APPEND a fourth message to the same folder. Just like #2, and since #2 destroyed the hash, it has to do all that work over again. 5. And so on. What can be done to make maildir_uidlist_refresh_fast_init() choose the fast path more often?
