[Date Prev][Date Next]
Re: (ITS#6301) PATCH - used red-black tree for response messages
On Sep 22, 2009, at 5:07 PM, Howard Chu wrote:
> firstname.lastname@example.org 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) (188.8.131.52)
>> 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/