[RFC] Making talloc_parent faster
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
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
More information about the samba-technical