[RFC][PATCH] Make GetXIDRange O(1) instead of O(N^2)

[Keith Packard]

Roberto Ragusa <mail at robertoragusa.it> writes:

> The basic problem is that when a client (xcb?) asks for free ids, the
> code makes a lot of inefficient guesses and spends an awful amount of time
> in identifying range of elements NOT present in its data structures
> (hashes).

The core protocol has no mechanism for discovering free ID ranges;
support for this was added in the XC-MISC extension around 1993 to deal
with long-running applications (typically window managers). As such, the
internal X server data structure wasn't touched when this extension was
implemented and so the operation to find unused ranges of XIDs is pretty
inefficient.

> This patch, in addition to raising the max hash size from 2^11 to 2^16 (2^11 was
> decided in 1994, or maybe even 1987), adds explicit tracking of free ids.
> The data structure I've chosen is an rb-tree of free extents.

I'm not excited at the notion of adding another data structure solely to
speed this fairly uncommon operation.

Given that we can extract the necessary information from the existing
data structure, here are a couple of brief ideas:

 1) Cache just a few free XID ranges; when XIDs are freed, you can
    extend or merge them together. This would make the operations
    cheaper at least, and might cover the bulk of the performance
    problems you found.

 2) Delay constructing the new data structure until the application
    actually runs out of IDs. Once that happens, you could turn on the
    free ID tracking. I can imagine building this incrementally by
    finding two free ranges each time the client asks for one and adding
    them both to the new data structure until you fail to find any more.

 3) Create an entirely new data structure for the whole resource DB that
    would make finding free extents less expensive. I'd suggest a
    skip-list as that makes in-order traversal really cheap (to find a
    free extent) while also reducing the average per-node cost down
    close to one pointer.

In any case, what we really need is credible performance data to use to
compare the old and new implementation. I think we need data that shows:

 1) 'real' application performance. The cairo performance stuff using
    Render is probably a good way to measure this.

 2) Memory usage. How much additional memory does this use, and,
    ideally, how much additional memory is getting traversed when
    manipulating the resource data base. Measuring the X server memory
    usage in a couple of situations with and without the changes should
    suffice.

 3) Performance of applications running out of XIDs to know whether
    the change actually fixes the problem. Have you already constructed
    some way of measuring this?

> - clients sometime "add" resources with already used IDs; it looks like the newer
> resource is returned by "get", and that all of them are deleted by "free";
> is this a bug in the applications? I decided to not change the external behavior of the
> code in these circumstances (see the functions containing "maybe" in
> their names)

Are you saying that you're seeing XIDs come over the wire that are
duplicates of those already in the resource database? If so, that would
be a bug in both the client side library and the X server. Every new ID
received should be checked with LEGAL_NEW_RESOURCE which makes sure that
the ID is unique.

However, while the protocol requires that IDs be unique across all
resource types, the server implementation does not. This allows the X
server to associate other data with specific IDs and have that freed
automatically. Looking up IDs always involves the type or class of the
ID, so code can be assured of getting the right data structure back.

Before I added the devPrivates infrastructure, this was the only way for
drivers and extensions to attach data to core X server objects.

I haven't used this "feature" of the server resource data base in
probably twenty years. However, the DRI2 extension *does* do this, so
you will need to handle it correctly.

-- 
keith.packard at intel.com
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 827 bytes
Desc: not available
URL: <http://lists.x.org/archives/xorg-devel/attachments/20130528/dc61956a/attachment.pgp>