bug-hurd
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[PATCH] libports: reduce malloc overhead in _ports_bucket_class_iterate


From: Justus Winter
Subject: [PATCH] libports: reduce malloc overhead in _ports_bucket_class_iterate
Date: Tue, 29 Apr 2014 13:32:09 +0200

_ports_bucket_class_iterate creates a snapshot of the buckets hash
table.  This is done so that the lock protecting the hash table can be
released while we iterate over the snapshot.

Formerly, a linked list was used to store the snapshot.  As the
maximal number of items is known, using an array is much simpler.

_ports_bucket_class_iterate implements both ports_bucket_iterate and
ports_class_iterate.  For this change might make ports_class_iterate
less efficient memory-wise if the number of ports belonging to the
class is low with respect to the number of ports in the bucket.  If
this happens, we allocate too much.  Alleviate this by releasing
unused memory.

On the other hand, the array representation is more compact.
Furthermore a survey of the Hurd code revealed that
ports_class_iterate is rarely used, while ports_bucket_iterate is used
more often, most prominently in paging code.

* libports/bucket-iterate.c (_ports_bucket_class_iterate): Use an
array instead of a linked list.
---
 libports/bucket-iterate.c | 46 ++++++++++++++++++++++++++++++----------------
 1 file changed, 30 insertions(+), 16 deletions(-)

diff --git a/libports/bucket-iterate.c b/libports/bucket-iterate.c
index dc1c7b1..498cf13 100644
--- a/libports/bucket-iterate.c
+++ b/libports/bucket-iterate.c
@@ -31,40 +31,54 @@ _ports_bucket_class_iterate (struct port_bucket *bucket,
 {
   /* This is obscenely ineffecient.  ihash and ports need to cooperate
      more closely to do it efficiently. */
-  struct item
-    {
-      struct item *next;
-      void *p;
-    } *list = 0;
-  struct item *i, *nxt;
+  void **p;
+  size_t i, n, nr_items;
   error_t err;
 
   pthread_mutex_lock (&_ports_lock);
+
+  if (bucket->htable.nr_items == 0)
+    {
+      pthread_mutex_unlock (&_ports_lock);
+      return 0;
+    }
+
+  nr_items = bucket->htable.nr_items;
+  p = malloc (nr_items * sizeof *p);
+  if (p == NULL)
+    return ENOMEM;
+
+  n = 0;
   HURD_IHASH_ITERATE (&bucket->htable, arg)
     {
       struct port_info *const pi = arg;
-      struct item *j;
 
       if (class == 0 || pi->class == class)
        {
-         j = malloc (sizeof (struct item));
-         j->next = list;
-         j->p = pi;
-         list = j;
          pi->refcnt++;
+         p[n] = pi;
+         n++;
        }
     }
   pthread_mutex_unlock (&_ports_lock);
 
+  if (n != nr_items)
+    {
+      /* We allocated too much.  Release unused memory.  */
+      void **new = realloc (p, n * sizeof *p);
+      if (new)
+        p = new;
+    }
+
   err = 0;
-  for (i = list; i; i = nxt)
+  for (i = 0; i < n; i++)
     {
       if (!err)
-       err = (*fun)(i->p);
-      ports_port_deref (i->p);
-      nxt = i->next;
-      free (i);
+       err = (*fun)(p[i]);
+      ports_port_deref (p[i]);
     }
+
+  free (p);
   return err;
 }
 
-- 
1.9.2




reply via email to

[Prev in Thread] Current Thread [Next in Thread]