[PATCH] ndr: use resized array for ndr tokens

[Douglas Bagnall]

OK, I see what you and Volker mean about talloc_array_length().

On 24/02/17 21:09, Stefan Metzmacher wrote:
> 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()
> }

Yes, though there would be some slightly horrible casting involved.
The full current struct is 

struct ndr_token_list {
	struct ndr_token_list *next, *prev;
 	const void *key;
 	uint32_t value;
};

but what we want is an array of the key value pairs:

struct ndr_token {
 	const void *key;
 	uint32_t value;
 };

so with this one

struct ndr_token_list {
 	struct ndr_token_list *array, *next_free;
 	const void *key;
 	uint32_t value;
};

we'd either be always casting array and next_free, or we'd be storing
arrays full of useless pointers. The casting should not be arduous.

It comes back to your "if we want" caveat. Does the ndr ABI matter? I
don't know.

Douglas


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