[RFC] Making talloc_parent faster

Kenneth Graunke kenneth at whitecape.org
Fri Jun 25 23:17:31 MDT 2010


I'm working on a project using talloc, and have run into a serious performance
issue.  We recently started using talloc_parent in a number of places to
create objects in the same context as an existing, related object---very
convenient.  Unfortunately, our project now runs many, many times slower, and
according to profiles, talloc_parent is responsible for most of our CPU time.

Upon reading the code, I was rather surprised to see that talloc_parent and
company are actually O(n) functions, having to perform a linked list traversal
to find the parent's talloc chunk.  Especially since each TC arleady has a
parent pointer.

The attached patch removes such traversals, making parent lookups O(1) - which
seems appropriate for seemingly simple lookup functions.  Each talloc chunk's 
parent pointer is now valid (non-NULL).  The tradeoff is that talloc_realloc
must now walk the list and update those parent pointers, so it will be slower.
This seems reasonable, however; I already expect reallocating to be a somewhat
expensive operation, especially if there are lots of children.

With this patch, our project runs very quickly.  I also ran "testsuite" with
and without ALWAYS_REALLOC, and everything passes.  I hope you will consider 
applying it.


More information about the samba-technical mailing list