RE: Performance issue related to implementation of slap_op_add

[Glen Coakley <gcoakley@mqsoftware.com>]

If this condition is indeed the case, all that is needed to make it the code
constant time is to save a pointer to the tail of the list. A double linked
list is only needed if you need to traverse a list forwards and backwards.

________________________________
Glen Coakley, Sr. Software Engineer
MQSoftware Inc., (763) 543-4845
"Tinkero ergo sum." -- Chuck Murcko


> -----Original Message-----
> From: Arnaud Sahuguet [mailto:sahuguet@gradient.cis.upenn.edu]
> Sent: Friday, June 22, 2001 1:23 PM
> To: openldap-devel@OpenLDAP.org
> Subject: Performance issue related to implementation of slap_op_add
> 
> 
> 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>
>