[PATCH] ndr: use resized array for ndr tokens

[Stefan Metzmacher]

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;
};

into

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.

metze

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>