diff options
| author | Douglas Bagnall <douglas.bagnall@catalyst.net.nz> | 2017-02-24 11:58:33 +1300 |
|---|---|---|
| committer | Andrew Bartlett <abartlet@samba.org> | 2017-03-02 08:38:21 +0100 |
| commit | 70923b7521786d59b76e651d566bbd61fea024cc (patch) | |
| tree | 135804f414227a9a69e36c9c6b7c7326c2a07a40 /librpc/wscript_build | |
| parent | 4bd8e63165e180565bda5dcf978ee0d38d3fa13d (diff) | |
| download | samba-70923b7521786d59b76e651d566bbd61fea024cc.tar.gz | |
ndr: Use resizing array instead of linked lists (breaking ABI)
The ndr token code keeps a temporary store of tokens which are
referred to a small number of times (often once) before being
discarded. The access patterns are somewhat stack-like, with recently
placed tokens being accessed most often.
The old code kept these tokens in a linked list, which we replace with
a self-resizing array.
This keeps everything roughly the same in big-O terms, but makes it
all faster in practice by vastly reducing the amount of tallocing and
pointer-chasing.
The peak memory use is strictly reduced. On a 64 bit machine each core
token struct fits in 16 bytes (after padding) while the two pointers
used by the DLIST add another 16 bytes, so the overall list allocation
is the same as the peak 2n array allocation -- except in the list case
it is dwarfed by the talloc and malloc metadata overhead.
Before settling on the resized arrays, we tried red-black trees, which
are bound to be better for large ndr structures. As it happens, we
don't deal with large structures (the size of replication clumps is
limited to 400 objects) and the asymptotic benefits of the trees are
not realised in practice.
With luck you should find graphs comparing the performance of these
various techniques at:
https://www.samba.org/~dbagnall/perf-tests/ndr-token/
This necessarily breaks the ABI because the linked list implementation
was publicly exposed.
Signed-off-by: Douglas Bagnall <douglas.bagnall@catalyst.net.nz>
Reviewed-by: Andrew Bartlett <abartlet@samba.org>
Autobuild-User(master): Andrew Bartlett <abartlet@samba.org>
Autobuild-Date(master): Thu Mar 2 08:38:22 CET 2017 on sn-devel-144
Diffstat (limited to 'librpc/wscript_build')
| -rw-r--r-- | librpc/wscript_build | 2 |
1 files changed, 1 insertions, 1 deletions
diff --git a/librpc/wscript_build b/librpc/wscript_build index fdfe6413900..55a6f7ab684 100644 --- a/librpc/wscript_build +++ b/librpc/wscript_build @@ -715,7 +715,7 @@ bld.SAMBA_LIBRARY('ndr', public_deps='samba-errors talloc samba-util', public_headers='gen_ndr/misc.h gen_ndr/ndr_misc.h ndr/libndr.h:ndr.h', header_path= [('*gen_ndr*', 'gen_ndr')], - vnum='0.0.9', + vnum='0.1.0', abi_directory='ABI', abi_match='ndr_* GUID_*', ) |