[PATCH] ndr: use resized array for ndr tokens

Douglas Bagnall douglas.bagnall at catalyst.net.nz
Fri Feb 24 01:49:07 UTC 2017


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:


The fourth commit ("ndr: delete exchange") is the one contained in
the attached patch. The other commits are slight variations on the

There look to be quite a few places where we could do similar things
for similar gains. Talloc is one.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: ndr.patch
Type: text/x-diff
Size: 237508 bytes
Desc: not available
URL: <http://lists.samba.org/pipermail/samba-technical/attachments/20170224/d4e5840d/ndr-0001.diff>

More information about the samba-technical mailing list