[hurd] 25/61: libports: reduce malloc overhead in _ports_bucket_class_iterate

[Samuel Thibault]

This is an automated email from the git hooks/post-receive script.

sthibault pushed a commit to branch upstream
in repository hurd.

commit 97737d1ee3ce95e45a1a4aa636cc2e11a106a9f5
Author: Justus Winter <address@hidden>
Date:   Sat Apr 26 12:20:20 2014 +0200

    libports: reduce malloc overhead in _ports_bucket_class_iterate
    
    _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;
 }
 

-- 
Alioth's /usr/local/bin/git-commit-notice on 
/srv/git.debian.org/git/pkg-hurd/hurd.git