[Date Prev][Date Next]
[Chronological]
[Thread]
[Top]
Re: (ITS#9001) try_read1msg() takes O(n) steps to lookup a matching request
- To: openldap-its@OpenLDAP.org
- Subject: Re: (ITS#9001) try_read1msg() takes O(n) steps to lookup a matching request
- From: ondra@mistotebe.net
- Date: Fri, 29 Mar 2019 13:50:17 +0000
- Auto-submitted: auto-generated (OpenLDAP-ITS)
On Fri, Mar 29, 2019 at 01:38:30PM +0000, ondra@openldap.org wrote:
> Full_Name: Ondrej Kuznik
> Version: re24/master
> OS:
> URL: https://github.com/mistotebe/openldap/tree/its9001
> Submission from: (NULL) (82.10.24.68)
>
>
> If a client has thousands or more requests in flight at the same time, it has to
> look up the right request every time it receives a response. As the requests are
> tracked in a doubly-linked list, lookup tends to take O(n) steps whichever
> direction we take and things generally get out of hand from there on.
>
> The linked branch puts them into a TAvl for quicker lookup, with another commit
> to let people test as (t)avl code is part of liblutil at the moment.
A trivial program to expose this behaviour is available at
ftp://ftp.openldap.org/incoming/searcher.c
The same program takes under a second to handle 100000 searches for
cn=monitor and children when linked to the patched libldap.
--
OndÅ?ej KuznÃk
Senior Software Engineer
Symas Corporation http://www.symas.com
Packaged, certified, and supported LDAP solutions powered by OpenLDAP