Re: [PATCH] libports: reduce malloc overhead in _ports_bucket_class_iterate

[Samuel Thibault]

Justus Winter, le Tue 29 Apr 2014 13:32:09 +0200, a écrit :
> _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.

Ack.

> * 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
> 

-- 
Samuel
Q:      How do you play religious roulette?
A:      You stand around in a circle and blaspheme and see who gets struck by 
lightning first.