Re: (ITS#6301) PATCH - used red-black tree for response messages

[bduncan@apple.com]

On Sep 22, 2009, at 5:07 PM, Howard Chu wrote:

> bduncan@apple.com wrote:
>> Full_Name: Bryan Duncan
>> Version: 2.4.16
>> OS: Mac OS X 10.6
>> URL: ftp://ftp.openldap.org/incoming/bryan-duncan-rbtree-090922.patch
>> Submission from: (NULL) (17.224.21.109)
>>
>>
>> Uploaded patch that replaces the linked-list of response messages  
>> with a
>> red-black tree.  This improves performance since random access to  
>> the response
>> messages is needed.
>>
> Hmm, there is no such file at the above URL.

Hmmm... there's some issue ftp'ing it up.  New URL: http://public.me.com/bryan.duncan/bryan-duncan-rbtree.090922.patch

>
> Also, while I don't doubt that a tree structure beats a linked list  
> for performance, could you please describe the analysis that led you  
> to writing this patch? What problem were you tracking, and what  
> situation caused it?

When running performance benchmarks we noticed one process was  
consuming huge amount (75%) of the CPU.  Further analysis revealed two  
problems:  1) the vast majority of those cycles were spent in  
ldap_msgdelete(), walking the response message linked-list.  2) There  
was a lot of contention for the thread mutex that's held while the  
message list is walked.  Thus we needed to reduce the time spent  
walking the list in order to achieve the desired performance.

After switching to the red-black tree we saw CPU utilization for the  
process was down in the noise.

>
> Why did you use a red-black tree, rather than just using the AVL  
> code that's already in the source?

I had a red-black tree implementation I knew had been tuned for  
performance and has been in shipping software.  I'm not saying the  
OpenLDAP AVL code couldn't handle it.  I could only implement one or  
the other, so I chose the one I was familiar with.

>
> In the future it would be a good idea to raise these topics on the  
> openldap-devel mailing list before diving in, since this is core  
> functionality and performance-related. Performance patches don't get  
> committed without test results showing a clear before/after gain.

Yes, that's a good idea.  My apologies for not raising the issue sooner.

>
> -- 
>  -- Howard Chu
>  CTO, Symas Corp.           http://www.symas.com
>  Director, Highland Sun     http://highlandsun.com/hyc/
>  Chief Architect, OpenLDAP  http://www.openldap.org/project/



Bryan Duncan
Apple