Performance issue related to implementation of slap_op_add

[Arnaud Sahuguet <sahuguet@gradient.cis.upenn.edu>]

Hi,

First a quick intro.
I am a PhD student from Univ. of Pennsylvania, working on databases. I
am using openLDAP as a backend storage to query XML. Any XML document
can be encoded in LDAP and a query against the document is translated
into a series of LDAP queries. (There is a nice paper about this:
http://db.cis.upenn.edu/FAQ/cache/49.html).

My problem is that read and write operations are not fast enough. I have
been looking at the source code and I think I have identified a possible
improvement. This was pointed out by the authors of the paper mentioned
above. They also mention other performance improvements.

My understanding is that client requests are handled by a queue (FIFO),
implemented in openldap-2.0.11/servers/slapd/operations.c .

Usually a queue offers constant time operations for pushing a new item
into the queue and popping the head of the queue.

In the code (see below), pushing a new item to the queue is not constant
but linear. If the queue is big, this can make a big difference. This
can be fixed by using a double-linked list and keeping a pointer to the
head and tail of the queue.

I have spent only a few hours browsing through the 2.x code, and maybe I
am missing something.

Regards,

Arnaud

<copy-of-the-code>
int slap_op_add(
    Operation           **olist,
        Operation               *op
)
{
        Operation       **tmp;

        for ( tmp = olist; *tmp != NULL; tmp = &(*tmp)->o_next )
                ;       /* NULL */

        *tmp = op;

        return 0;
}                 
</copy-of-the-code>