On 9/16/21 22:19, Ilya Maximets wrote: > Current algorithm of ovsdb_datum_union looks like this: > > for-each atom in b: > if not bin_search(a, atom): > a[n++] = clone(atom) > quicksort(a) > > So, the complexity looks like this: > > Nb * log2(Na) + Nb + (Na + Nb) * log2(Na + Nb) > Comparisons clones Comparisons for quicksort > for search > > ovsdb_datum_union() is heavily used in database transactions while > new element is added to a set. For example, if new logical switch > port is added to a logical switch in OVN. This is a very common > use case where CMS adds one new port to an existing switch that > already has, let's say, 100 ports. For this case ovsdb-server will > have to perform: > > 1 * log2(100) + 1 clone + 101 * log2(101) > Comparisons Comparisons for > for search quicksort. > ~7 1 ~707 > Roughly 714 comparisons of atoms and 1 clone. > > Since binary search can give us position, where new atom should go > (it's the 'low' index after the search completion) for free, the > logic can be re-worked like this: > > copied = 0 > for-each atom in b: > desired_position = bin_search(a, atom) > push(result, a[ copied : desired_position - 1 ]) > copied = desired_position > result[n++] = clone(atom) > swap(a, result) > > Complexity of this schema: > > Nb * log2(Na) + Nb + Na > Comparisons clones memory copy on push > for search > > 'swap' is just a swap of a few pointers. 'push' is not a 'clone', > but a simple memory copy of 'union ovsdb_atom'. > > In general, this schema substitutes complexity of a quicksort > with complexity of a memory copy of Na atom structures, where we're > not even copying strings that these atoms are pointing to. > > Complexity in the example above goes down from 714 comparisons > to 7 comparisons and memcpy of 100 * sizeof (union ovsdb_atom) bytes. > > General complexity of a memory copy should always be lower than > complexity of a quicksort, especially because these copies usually > performed in bulk, so this new schema should work faster for any input. > > All in all, this change allows to execute several times more > transactions per second for transactions that adds new entries to sets. > > Alternatively, union can be implemented as a linear merge of two > sorted arrays, but this will result in O(Na) comparisons, which > is more than Nb * log2(Na) in common case, since Na is usually > far bigger than Nb. Linear merge will also mean per-atom memory > copies instead of copying in bulk. > > 'replace' functionality of ovsdb_datum_union() had no users, so it > just removed. But it can easily be added back if needed in the future. > > Signed-off-by: Ilya Maximets <i.maxim...@ovn.org> > --- > lib/db-ctl-base.c | 10 +++--- > lib/ovsdb-data.c | 84 ++++++++++++++++++++++++++++++++--------------- > lib/ovsdb-data.h | 6 ++-- > lib/ovsdb-idl.c | 8 ++--- > ovsdb/mutation.c | 2 +- > vswitchd/bridge.c | 9 +++-- > 6 files changed, 77 insertions(+), 42 deletions(-)
Re-sent as part of a patch set: https://patchwork.ozlabs.org/project/openvswitch/list/?series=262864&state=* Best regards, Ilya Maximets. _______________________________________________ dev mailing list d...@openvswitch.org https://mail.openvswitch.org/mailman/listinfo/ovs-dev
