Re: [PATCH 02/11] libports: use a single hash table

[Samuel Thibault]

Justus Winter, le Tue 13 May 2014 12:48:46 +0200, a écrit :
> Quoting Samuel Thibault (2014-05-13 01:00:30)
> > Justus Winter, le Mon 12 May 2014 12:05:40 +0200, a écrit :
> > > Previously, libports used a hash table per port bucket.  This makes
> > > looking up a port difficult if one does not know the port bucket, as
> > > one has to iterate over all buckets and do a hash table lookup each.
> > 
> > But conversely, this makes having to iterate over all ports while one
> > may want to just iterate over one bucket.  I'd rather not drop that
> > feature.
> 
> This feature is not lost.  ports_bucket_iterate (b, ..) iterates over
> all ports in bucket b as before.

But not in an efficient way, it'll iterate over the whole global
hashtable, not only the per-bucket hash table.

> Also, looking up a port is often done.  Iterating over the ports is
> done much less often.  It seems to me that optimizing the former is
> more important.
> 
> > _ports_bucket_class_iterate is clearly bogus ATM, so we at least need
> > something.  Would it be too costly to maintain both a global and a
> > per-bucket hash table?  It would at the very worse be only twice as
> > expensive as only the global hash table, while still allowing the
> > performance gain of iterating over only one bucket.
> 
> Having more than one hash table is totally pointless imho.  Since the
> port namespace is per-process, and libports is "per-process", having a
> hash table per bucket means that all per-bucket hash tables are
> disjoint.

Well, yes, indeed, of course.  But that's my whole point: keeping the
per-bucket hash table too allows to iterate over a bucket efficiently.

Samuel