s4:dsdb/descriptor: sort descriptor_changes tree based
For the hot code path, e.g. the commit after the initial replication,
we typically have one descriptor_changes for each object in the
database.
It means that we most likely have 5 naming contexts/partitions.
Except of their head/root object have a valid parent_guid,
so can move all of them into the tree structure.
Now we start the processing at the partition root objects,
which means that we also process all child objects in
the same run. While processing these objects we are most
likely able to mark their related descriptor_changes structure
as done removing it from the hierarchy.
With the 22000 object domain it reduces the time spend in
the commit stage from 3m 20s down to 2m 50s.
The statistics are changed from:
descriptor_prepare_commit: changes: num_registrations=50000
descriptor_prepare_commit: changes: num_registered=22000
descriptor_prepare_commit: changes: num_processed=22000
descriptor_prepare_commit: objects: num_processed=80800
to:
descriptor_prepare_commit: changes: num_registrations=50000
descriptor_prepare_commit: changes: num_registered=22000
descriptor_prepare_commit: changes: num_toplevel=5
descriptor_prepare_commit: changes: num_processed=5200
descriptor_prepare_commit: objects: num_processed=68800
Signed-off-by: Stefan Metzmacher <metze@samba.org>
Reviewed-by: Andrew Bartlett <abartlet@samba.org>