[PATCH] ndr: use resized array for ndr tokens

[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: ndr.patch
Type: text/x-diff
Size: 237513 bytes
Desc: not available
URL: <http://lists.samba.org/pipermail/samba-technical/attachments/20170224/7168d74a/ndr-0001.diff>