[Xcb] a question about request and reply

[Jamey Sharp]

On Mon, Dec 19, 2005 at 09:14:10PM +0100, Vincent Torri wrote:
> On Mon, 19 Dec 2005, Jamey Sharp wrote:
> > I notice that you haven't implemented a queue, which is what I thought
> > you were going for. You've implemented a table of cookies instead, with
> > sequentially-allocated keys. This table isn't buying you any performance
> > or latency hiding. What were you trying for?
> 
> well, a queue is just a list, right ? here, it's an array i find it
> more convenient to use rather than lists.

No, a queue is a structure that you put things into and get them out
later in FIFO order. The distinction matters for X because the replies
come back in the same order that the requests were issued in, so for
maximum efficiency you should force cookies in the same order that you
made the requests in. Keeping a queue of pending cookies therefore makes
sense.

Actually, you want a priority queue, because the items should be sorted
by sequence number even if your application inserts them in some other
order. xcb_reply does this by keeping a sorted linked list, which is
very simple and has O(1) retrieval time but O(n) insertion time. Using a
sorted circular array would have the same asymptotic performance with
worse constants and more complicated code. On the other hand, an
array-based heap has O(lg n) complexity for both insertion and removal,
and would be the right data structure in the event that performance
turns out to matter here.

> my aim was to make the reply system independant to the reply functions
> (which is given when we send the request) as the replies might be called
> by a callback. It's then impossible to know wich reply functions we have
> to call.

If you don't know which reply function to call, you don't know what type
the reply is, and you can't do anything with it except throw it away --
and in that case why did you issue the request in the first place?

Notice the difference in xcb_reply's API: the registered callback
function is not the XCB*Reply function, it's whatever code wants to
process that reply. So you register a function that knows, "I'm going to
get an XCBGetGeometryRep," together with an XCBGetGeometryCookie. Then
xcb_reply promises to call your function as soon after the reply becomes
available as it can, giving you the best latency hiding.

--Jamey
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://lists.freedesktop.org/archives/xcb/attachments/20051219/225f3a80/attachment.pgp