> I compiled dbmail and glib with profiling and gprof shows almost all
> time being spent in IA__g_list_last. (Note the CPU time reported by
> time was 277.17s -- the rest is probably in glibc and mysql libs..)
>
> time seconds seconds calls s/call s/call name
> 99.35 272.99 272.99 344704 0.00 0.00 IA__g_list_last
> 0.20 273.54 0.55 18702183 0.00 0.00 ucmp
> 0.10 273.82 0.28 344681 0.00 0.00 g_tree_node_insert
> 0.06 273.99 0.17 860545 0.00 0.00 g_tree_node_lookup
> 0.05 274.12 0.13 344771 0.00 0.00 _g_list_alloc
> 0.03 274.20 0.08 14 0.01 0.01 db_getmailbox
> (full profile log attached)
OK -- O(n^2) behavior is bad. The traverse_tree_{keys, values, merge}
functions all ended up appending message pointers to the end of a linked
list. When you do this for 80,000 messages, you end up following about
3.2 billion pointers.. Yuck.
Attached patch created copies of these functions (traverse_tree_keys_rev
etc) which prepends list items and then uses a g_list_reverse to sort
out the mess. It seems to work for me but I've given it minimal
testing.
There are better ways of doing this, but for me this reduces the above
mailbox query from 272cpusec to 5.1cpusec, for a tidy 50x speedup.
Matt
diff -ur dbmail-2.1.5/dbmail-mailbox.c dbmail-2.1.5-new/dbmail-mailbox.c
--- dbmail-2.1.5/dbmail-mailbox.c 2006-02-12 10:08:02.000000000 -0600
+++ dbmail-2.1.5-new/dbmail-mailbox.c 2006-03-06 21:34:48.000000000 -0600
@@ -999,8 +999,9 @@
id = g_new0(u64_t,1);
*id = db_get_result_u64(i,0);
if (g_tree_lookup(self->ids,id))
- self->sorted = g_list_append(self->sorted,id);
+ self->sorted = g_list_prepend(self->sorted,id);
}
+ g_list_reverse(self->sorted);
g_string_free(q,TRUE);
db_free_result();
diff -ur dbmail-2.1.5/list.c dbmail-2.1.5-new/list.c
--- dbmail-2.1.5/list.c 2005-10-03 05:19:40.000000000 -0500
+++ dbmail-2.1.5-new/list.c 2006-03-03 11:22:17.000000000 -0600
@@ -36,6 +36,9 @@
*/
void dm_list_free(struct element **start)
{
+ if (!start || !(*start))
+ return;
+
if (!(*start))
return;
diff -ur dbmail-2.1.5/misc.c dbmail-2.1.5-new/misc.c
--- dbmail-2.1.5/misc.c 2006-02-28 14:59:51.000000000 -0600
+++ dbmail-2.1.5-new/misc.c 2006-03-06 21:47:01.000000000 -0600
@@ -1279,22 +1279,39 @@
*(GList **)l = g_list_append(*(GList **)l, key);
return FALSE;
}
+
+static gboolean traverse_tree_keys_rev(gpointer key, gpointer value UNUSED,
GList **l)
+{
+ *(GList **)l = g_list_prepend(*(GList **)l, key);
+ return FALSE;
+}
+
static gboolean traverse_tree_values(gpointer key UNUSED, gpointer value,
GList **l)
{
*(GList **)l = g_list_append(*(GList **)l, value);
return FALSE;
}
+static gboolean traverse_tree_values_rev(gpointer key UNUSED, gpointer value,
GList **l)
+{
+ *(GList **)l = g_list_prepend(*(GList **)l, value);
+ return FALSE;
+}
+
+
+
GList * g_tree_keys(GTree *tree)
{
GList *l = NULL;
- g_tree_foreach(tree, (GTraverseFunc)traverse_tree_keys, &l);
+ g_tree_foreach(tree, (GTraverseFunc)traverse_tree_keys_rev, &l);
+ g_list_reverse(l);
return g_list_first(l);
}
GList * g_tree_values(GTree *tree)
{
GList *l = NULL;
- g_tree_foreach(tree, (GTraverseFunc)traverse_tree_values, &l);
+ g_tree_foreach(tree, (GTraverseFunc)traverse_tree_values_rev, &l);
+ g_list_reverse(l);
return g_list_first(l);
}
@@ -1347,6 +1364,28 @@
return FALSE;
}
+static gboolean traverse_tree_merger_rev(gpointer key, gpointer value UNUSED,
tree_merger_t **merger)
+{
+ tree_merger_t *t = *(tree_merger_t **)merger;
+ GTree *tree = t->tree;
+ int condition = t->condition;
+
+ switch(condition) {
+ case IST_SUBSEARCH_NOT:
+ break;
+
+ default:
+ case IST_SUBSEARCH_OR:
+ case IST_SUBSEARCH_AND:
+ if (! g_tree_lookup(tree,key))
+ (*(tree_merger_t **)merger)->list =
g_list_prepend((*(tree_merger_t **)merger)->list,key);
+ break;
+ }
+
+ return FALSE;
+}
+
+
int g_tree_merge(GTree *a, GTree *b, int condition)
{
@@ -1370,7 +1409,8 @@
/* delete from A all keys not in B */
merger->tree = b;
merger->condition = IST_SUBSEARCH_AND;
- g_tree_foreach(a,(GTraverseFunc)traverse_tree_merger,
&merger);
+
g_tree_foreach(a,(GTraverseFunc)traverse_tree_merger_rev, &merger);
+ g_list_reverse(merger->list);
keys = g_list_first(merger->list);
if (! g_list_length(keys))
@@ -1393,7 +1433,8 @@
merger->tree = a;
merger->condition = IST_SUBSEARCH_OR;
- g_tree_foreach(b,(GTraverseFunc)traverse_tree_merger,
&merger);
+
g_tree_foreach(b,(GTraverseFunc)traverse_tree_merger_rev, &merger);
+ g_list_reverse(merger->list);
keys = g_list_first(merger->list);
/* add to A all keys in B */
