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