I've been doing some work with large mailboxes using the php imap module
and I uncovered a pretty severe efficiency bug that results in monstrous
amounts of silly computation.
Basically, what is happening is each call to mm_searched() is resulting in
a traversal of the entire linked list so far. I believe this results in
something like O(nlog(n)) performance on what should be an O(1) operation.
The addition of a tail pointer to the list fixes this problem. I also
made the free function non-recursive, which is somthing that could
probabally be applied to most of the list-freeing functions in php_imap.c
I'd like to see this in 4.0.7 if possible.
Please give comments / let me know when its committed.
Thanks,
-Rob
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Rob Siemborski | W3VC President * Scotch & Soda Technical Coordinator
Andrew Systems Group * Cyert Hall 235 * 412-CMU-TREK | ABTech Exec
-----BEGIN GEEK CODE BLOCK----
Version: 3.12
GCS/IT/CM/CC/PA d- s+: a-- C++++$ UBLS++++$ P+++$ L++(+++) E W- N- o?
K- w O- M-- V-- PS+ PE++ Y+ PGP+ t+@ 5+++ R@ tv-- b+ DI+++ G e h r y?
------END GEEK CODE BLOCK-----
--- php_imap.c.dist Thu Aug 16 15:28:43 2001
+++ php_imap.c Thu Aug 16 15:31:54 2001
@@ -347,12 +347,17 @@
* Accepts: pointer to MESSAGELIST pointer
* Author: CJH
*/
-void mail_free_messagelist(MESSAGELIST **msglist)
+void mail_free_messagelist(MESSAGELIST **msglist, MESSAGELIST **tail)
{
- if (*msglist) { /* only free if exists */
- mail_free_messagelist (&(*msglist)->next);
- fs_give ((void **) msglist); /* return string to free storage */
- }
+ MESSAGELIST *cur, *next;
+
+ for(cur=*msglist, next=cur->next; cur; cur=next) {
+ next=cur->next;
+ fs_give((void **)&cur);
+ }
+
+ *tail = NIL;
+ *msglist = NIL;
}
/* }}} */
@@ -388,6 +393,7 @@
imap_globals->imap_alertstack=NIL;
imap_globals->imap_errorstack=NIL;
imap_globals->imap_messages=NIL;
+ imap_globals->imap_messages_tail=NIL;
imap_globals->imap_folder_objects=NIL;
imap_globals->imap_sfolder_objects=NIL;
imap_globals->folderlist_style = FLIST_ARRAY;
@@ -3357,7 +3363,7 @@
flags = Z_LVAL_PP(search_flags);
}
- IMAPG(imap_messages) = NIL;
+ IMAPG(imap_messages) = IMAPG(imap_messages_tail) = NIL;
mail_search_full(imap_le_struct->imap_stream, NIL,
mail_criteria(search_criteria), flags);
if (IMAPG(imap_messages) == NIL) {
efree(search_criteria);
@@ -3371,7 +3377,7 @@
add_next_index_long(return_value, cur->msgid);
cur = cur->next;
}
- mail_free_messagelist(&IMAPG(imap_messages));
+ mail_free_messagelist(&IMAPG(imap_messages), &IMAPG(imap_messages_tail));
efree(search_criteria);
}
/* }}} */
@@ -3895,20 +3901,19 @@
{
MESSAGELIST *cur = NIL;
TSRMLS_FETCH();
-
+
if (IMAPG(imap_messages) == NIL) {
IMAPG(imap_messages) = mail_newmessagelist();
IMAPG(imap_messages)->msgid = number;
IMAPG(imap_messages)->next = NIL;
+ IMAPG(imap_messages_tail) = IMAPG(imap_messages);
} else {
- cur = IMAPG(imap_messages);
- while (cur->next != NIL) {
- cur = cur->next;
- }
+ cur = IMAPG(imap_messages_tail);
cur->next = mail_newmessagelist();
cur = cur->next;
cur->msgid = number;
cur->next = NIL;
+ IMAPG(imap_messages_tail) = cur;
}
}
--- php_imap.h.dist Thu Aug 16 15:28:38 2001
+++ php_imap.h Thu Aug 16 15:29:15 2001
@@ -190,6 +190,7 @@
STRINGLIST *imap_alertstack;
ERRORLIST *imap_errorstack;
MESSAGELIST *imap_messages;
+ MESSAGELIST *imap_messages_tail;
FOBJECTLIST *imap_folder_objects;
FOBJECTLIST *imap_sfolder_objects;
folderlist_style_t folderlist_style;
--
PHP Development Mailing List <http://www.php.net/>
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
To contact the list administrators, e-mail: [EMAIL PROTECTED]
