[PATCH] ndr: use resized array for ndr tokens

Stefan Metzmacher metze at samba.org
Fri Feb 24 08:09:53 UTC 2017

Hi Douglas,

I think if we want, we can keep that ABI.

We could change

struct ndr_token_list {
	struct ndr_token_list *prev, *next;


struct ndr_token_list {
	struct ndr_token_list *array, *next_free;

The 'count' can calculated as

if (list->next_free != NULL) {
	count = some pointer diff magic
} else {
	count = talloc_array_length()

alloc_count is always talloc_array_length()

And allocating a struct ndr_token_list structure
at the first usage should also be no big problem.


Am 24.02.2017 um 04:03 schrieb Douglas Bagnall:
> sigh.
> So, in trying to get this out before the weekend, I skipped a little bit
> of testing, and after sending the email I discovered I had missed the "
> == 0" in "if (_cmp_fn(tokens[i].key, key) == 0) {" for the nbt and dns
> cases.
> This one should work better.
> Douglas
> On 24/02/17 14:49, Douglas Bagnall wrote:
>> hi
>> When we are packing and unpacking ndr structures, we currently use a
>> linked list as a temporary store. This ends up taking a few percent of
>> the time in many common AD operations, which is hardly surprising as
>> linked lists are known to be suboptimal data structures for just about
>> everything on modern hardware.
>> We tried replacing them with red-black trees, which only made things
>> worse. Most ndr structures are small and the overhead of the fiddly
>> tree outweighs the asymptotic gain. So we switched to self-resizing
>> arrays which have roughly the same time complexity as linked lists but
>> which are much much faster in reality because they avoid a whole lot
>> of tallocing and pointer chasing. They also use less memory.
>> In our tests the new code can pack and unpack a security descriptor in
>> half the time. Large ndr chunks from replication are processed around
>> 10% faster. Searches are up to 20% faster.
>> The bad thing about this patch is it breaks ABI, because libndr.h
>> keeps nothing private.
>> There are graphs here that show the effects:
>> https://www.samba.org/~dbagnall/perf-tests/ndr-token/
>> The fourth commit ("ndr: delete exchange") is the one contained in
>> the attached patch. The other commits are slight variations on the
>> idea.
>> There look to be quite a few places where we could do similar things
>> for similar gains. Talloc is one.
>> cheers,
>> Douglas

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: OpenPGP digital signature
URL: <http://lists.samba.org/pipermail/samba-technical/attachments/20170224/cb99aa92/signature.sig>

More information about the samba-technical mailing list