[PATCH] resource: Micro-tune resource hash computation

[Adam Jackson]

On Wed, 2011-01-12 at 12:04 -0800, Jamey Sharp wrote:
> If Hash is performance critical, is there a strong reason not to
> replace it with this?
> 
> return id & (clientTable[client].buckets - 1);
> 
> I'd be interested to see evidence justifying mixing higher-order bits
> into the hash.

I really doubt there's much basis for it.  It's not like this is a
string hash where you're trying to generate strong mixing, XIDs are just
sequentially allocated integers, they're going to distribute themselves
pretty evenly on their own.

If someone _really_ wanted to speed this up - and I'm definitely
trolling for volunteers here - my hunch is that we shouldn't do
ResourceRec as a linked list.  The allocations for each are going to
tend to be on different pages, which means TLB misses.  If instead we
did:

---
typedef struct _Resource {
    XID                 id;
    RESTYPE             type;
    pointer             value;
} ResourceRec, *ResourcePtr;

static const int resources_per_slab = 
    4096 / sizeof(ResourceRec);

typedef struct _ResourceSlab {
    struct ResourceRec   res[resources_per_slab];
} ResourceSlabRec, *ResourceSlabPtr;

typedef struct _ClientResource {
    ResourceSlabPtr *resources;
    /* ... */
} ClientResourceRec;
---

Then I suspect that'd be a win since you'd only take the TLB miss for
looking up the slab corresponding to your hash bucket, and since we're
not keeping next pointers anymore you should be able to fit more
resources in the same amount of memory so you should also win on
cacheline fill traffic.

It's a tradeoff though, you've made each bucket more expensive in memory
so you'd want to start with fewer buckets, you'd have to rewrite
RebuildTable pretty thoroughly, the current rebuild threshold of
4*buckets would probably want to be retuned since you can now fit at
least 256 resources per slab...

Who wants to implement this and see what we get?

> If the current hash is necessary, is there a typo in the 128 bucket
> case? That should be 14, not 13, right? Otherwise the same bit is
> getting mixed in twice.

Indeed.  Congratulations once again on finding a bug that's been present
since X11R1.

- ajax
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: This is a digitally signed message part
URL: <http://lists.x.org/archives/xorg-devel/attachments/20110113/4671cd65/attachment.pgp>