Viewing Development/6301
Full headers

Major security issue: yes  no

Notes:

Notification:

Date: Tue, 22 Sep 2009 19:16:03 +0000
From: bduncan@apple.com
To: openldap-its@OpenLDAP.org
Subject: PATCH - used red-black tree for response messages

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.

Followup 1

Date: Tue, 22 Sep 2009 17:07:46 -0700
From: Howard Chu <hyc@symas.com>
To: bduncan@apple.com
CC: openldap-its@openldap.org
Subject: Re: (ITS#6301) PATCH - used red-black tree for response messages

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.

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?

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

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.

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

Followup 2

Subject: Re: (ITS#6301) PATCH - used red-black tree for response messages
From: Bryan Duncan <bduncan@apple.com>
Date: Wed, 23 Sep 2009 15:29:48 -0700
Cc: openldap-its@openldap.org
To: Howard Chu <hyc@symas.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