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.