<<< Date Index >>>     <<< Thread Index >>>

Re: [patch] sorting efficiency

On Mon, Sep 08, 2008 at 10:56:13AM +0200, Thomas Roessler wrote:
> Out of curiosity, mind reposting that patch so we can see which
> one's better? ;-)

It's not really a question of which is better because they're both addressing
different parts of the code--aliases versus groups.  Attached is my tweaked
patch as originally posted.  The inlining patch (as mentioned in my original
message, but which is otherwise unrelated) reduced startup times on my
system by 15%.

>>> Dan
-- 
http://www.MoveAnnouncer.com              The web change of address service
          Let webmasters know that your web site has moved
--- Begin Message --- 
I've revisited the performance patch I sent and found a problem due to
an incorrect assumption.  Here's a new version that stores the group
addresses in a hash table instead of a linked list so group lookups can
be much faster.  I've split the original inlining portion of the patch
into a separate file also attached here.

mutt seems to be pretty lax with its memory management; there's lots on
the heap that never seems to be freed.  What I've seen it not that
big a deal--it's stuff allocated at initialization time and never freed,
as opposed to an unbounded leak.  This patch doesn't attempt to address
that.

>>> Dan
-- 
http://www.MoveAnnouncer.com              The web change of address service
          Let webmasters know that your web site has moved

diff -ru /tmp/mutt-1.5.17cvs/ascii.c /home/dan/src/mutt-1.5.17cvs/ascii.c
--- /tmp/mutt-1.5.17cvs/ascii.c Tue May 29 00:00:07 2007
+++ ./ascii.c   Thu Mar 27 16:12:36 2008
@@ -34,17 +34,17 @@
 #include <stdlib.h>
 #include "ascii.h"
 
-int ascii_isupper (int c)
+inline int ascii_isupper (int c)
 {
   return (c >= 'A') && (c <= 'Z');
 }
 
-int ascii_islower (int c)
+inline int ascii_islower (int c)
 {
   return (c >= 'a') && (c <= 'z');
 }
 
-int ascii_toupper (int c)
+inline int ascii_toupper (int c)
 {
   if (ascii_islower (c))
     return c & ~32;
@@ -52,7 +52,7 @@
   return c;
 }
 
-int ascii_tolower (int c)
+inline int ascii_tolower (int c)
 {
   if (ascii_isupper (c))
     return c | 32;

--- /tmp/mutt-1.5.17cvs/group.c Tue May 29 00:00:07 2007
+++ ./group.c   Fri Mar 28 22:33:03 2008
@@ -51,6 +51,7 @@
     dprint (2, (debugfile, "mutt_pattern_group: Creating group %s.\n", k));
     p = safe_calloc (1, sizeof (group_t));
     p->name = safe_strdup (k);
+    p->adr_hash = hash_create (1031);
     hash_insert (Groups, p->name, p, 0);
   }
   
@@ -79,21 +80,20 @@
   }
 }
 
+/* Adds the addresses in list a to the group g */
 void mutt_group_add_adrlist (group_t *g, ADDRESS *a)
 {
-  ADDRESS **p, *q;
+  ADDRESS *p, *q;
 
-  if (!g)
+  if (!g || !a)
     return;
-  if (!a)
-    return;
-  
-  for (p = &g->as; *p; p = &((*p)->next))
-    ;
   
   q = rfc822_cpy_adr (a);
-  q = mutt_remove_xrefs (g->as, q);
-  *p = q;
+  if (!q)
+    return;
+
+  for (p = q; p; p = p->next)
+    hash_insert(g->adr_hash, p->mailbox, p, 0);
 }
 
 int mutt_group_add_rx (group_t *g, const char *s, int flags, BUFFER *err)
@@ -117,18 +117,15 @@
   return rv;
 }
 
+/* Returns nonzero when the address s is found in the group g */
 int mutt_group_match (group_t *g, const char *s)
 {
-  ADDRESS *ap;
-  
-  if (s && g)
-  {
-    if (mutt_match_rx_list (s, g->rs))
-      return 1;
-    for (ap = g->as; ap; ap = ap->next)
-      if (ap->mailbox && !mutt_strcasecmp (s, ap->mailbox))
-       return 1;
-  }
-  return 0;
+  if (!s || !g)
+    return 0;
+
+  if (hash_find(g->adr_hash, s) != NULL)
+    return 1;
+
+  return mutt_match_rx_list (s, g->rs);
 }
 
--- /tmp/mutt-1.5.17cvs/mutt.h  Wed Aug 29 00:00:05 2007
+++ ./mutt.h    Fri Mar 28 22:21:36 2008
@@ -811,7 +811,7 @@
 
 typedef struct group_t
 {
-  ADDRESS *as;
+  HASH *adr_hash;
   RX_LIST *rs;
   char *name;
 } group_t;

--- End Message ---