[RFC] [PATCH] talloc: Look up parents in O(1) time instead of O(n).

[Carl Worth]

On Sun, 27 Jun 2010 10:51:11 +1000, "tridge at samba.org" <tridge at samba.org> wrote:
> In Samba talloc_parent() is much less common than talloc_realloc(),
> which is why I chose to make talloc_realloc() avoid the list traversal
> and talloc_parent() to do it.

Hi Tridge,

Thanks for the quick feedback. The above does make sense, but it ends up
being awfully inconvenient for our current project, (which Ken is
working on with me). We're trying to convert a project gradually from
malloc to talloc, and trying to avoid adding new parameters all through
the call tree if unnecessary.

This leads to a common use case of a single top-level talloc context
acting as a "main memory pool", (think, an extremely wide and shallow
hierarchy), and talloc_parent() commonly used to find it based on a
neighboring object.

It doesn't seem an entirely unreasonable thing to do given the current
talloc API, but wow, is it painful at runtime. :-)

> It may be that the patch is OK anyway, as talloc_realloc() is probably
> called mostly on contexts with no children. Before we apply this patch
> we'd need to instrument talloc_realloc() and see how often it is
> called with large numbers of children in Samba.

We'd love to help with this. It seems simple enough to instrument
talloc_realloc to construct a histogram of numbers-of-children at each
call. What would you recommend as the workload to run through this?

[Note: I have no experience with the Samba code base---maybe there's
some obvious test suite to run here---I would just need a pointer to
that.]

> I also think you may have missed some changes, although I haven't
> looked at it really carefully.

Ken and I will take another look here...

> I'm a bit surprised the test suite didn't pick this one up. That
> may indicate a problem in the test suite, or maybe it works anyway for
> some reason I can't see right now.

...and if we find anything, perhaps we can augment the test suite.

Thanks again,

-Carl

-- 
carl.d.worth at intel.com
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: <http://lists.samba.org/pipermail/samba-technical/attachments/20100628/b16faf74/attachment.pgp>