On 17/09/2021 18:17, Ilya Maximets wrote:
> Current algorithm for ovsdb_datum_subtract looks like this:
>
> for-each atom in a:
> if atom in b:
> swap(atom, <last atom in 'a'>)
> destroy(atom)
> quicksort(a)
>
> Complexity:
>
> Na * log2(Nb) + (Na - Nb) * log2(Na - Nb)
> Search Comparisons for quicksort
>
> It's not optimal, especially because Nb << Na in a vast majority of
> cases.
>
> Reversing the search phase to look up atoms from 'b' in 'a', and
> closing gaps from deleted elements in 'a' by plain memory copy to
> avoid quicksort.
>
> Resulted complexity:
>
> Nb * log2(Na) + (Na - Nb)
> Search Memory copies
>
> Subtraction is heavily used while executing database transactions.
> For example, to remove one port from a logical switch in OVN.
> Complexity of such operation if original logical switch had 100 ports
> goes down from
>
> 100 * log2(1) = 100 comparisons for search and
> 99 * log2(99) = 656 comparisons for quicksort
> ------------------------------
> 756 comparisons in total
> to only
>
> 1 * log2(100) = 7 comparisons for search
> + memory copy of 99 * sizeof (union ovsdb_atom) bytes.
>
> We could use memmove to close the gaps after removing atoms, but
> it will lead to 2 memory copies inside the call, while we can perform
> only one to the temporary 'result' and swap pointers.
>
> Performance in cases, where sizes of 'a' and 'b' are comparable,
> should not change. Cases with Nb >> Na should not happen in practice.
It seems like we are optimizing for the more common case in which Na >>
Nb. Not sure if there are use cases in which the other case could bubble
up as a bottleneck. Could we try to assess which case we are in by
checking the size of the sets and then select the algorithm based on
that assessment? i.e. have two algorithms?
>
> All in all, this change allows ovsdb-server to perform several times
> more transactions, that removes elements from sets, per second.
>
> Signed-off-by: Ilya Maximets <i.maxim...@ovn.org>
> ---
> lib/ovsdb-data.c | 52 +++++++++++++++++++++++++++++++++++++-----------
> 1 file changed, 40 insertions(+), 12 deletions(-)
>
> diff --git a/lib/ovsdb-data.c b/lib/ovsdb-data.c
> index 11bf95fed..b6129d6ba 100644
> --- a/lib/ovsdb-data.c
> +++ b/lib/ovsdb-data.c
> @@ -2019,26 +2019,54 @@ ovsdb_datum_subtract(struct ovsdb_datum *a, const
> struct ovsdb_type *a_type,
> const struct ovsdb_datum *b,
> const struct ovsdb_type *b_type)
> {
> - bool changed = false;
> - size_t i;
> + size_t i, ai, bi, n_idx;
> + size_t *idx;
>
> ovs_assert(a_type->key.type == b_type->key.type);
> ovs_assert(a_type->value.type == b_type->value.type
> || b_type->value.type == OVSDB_TYPE_VOID);
>
> - /* XXX The big-O of this could easily be improved. */
> - for (i = 0; i < a->n; ) {
> - unsigned int idx = ovsdb_datum_find(a, i, b, b_type);
> - if (idx != UINT_MAX) {
> - changed = true;
> - ovsdb_datum_remove_unsafe(a, i, a_type);
> - } else {
> - i++;
> + idx = xmalloc(b->n * sizeof *idx);
> + n_idx = 0;
> + for (bi = 0; bi < b->n; bi++) {
> + ai = ovsdb_datum_find(b, bi, a, b_type);
> + if (ai == UINT_MAX || (n_idx && ai <= idx[n_idx - 1])) {
If b and a are always sorted, will we ever hit the second clause (n_idx
&& ai <= idx[n_idx - 1])? For example, if the following elements are
equivalent
b0 -> a0
b1 -> a1
..
..
bi is always > bi-1 therefore ai is always greater than ai-1. If there
is still a chance that we will hit it, could you add a more detailed
comment?
> + /* No such atom in 'a' or it's already marked for removal. */
> + continue;
> }
> + idx[n_idx++] = ai;
> }
> - if (changed) {
> - ovsdb_datum_sort_assert(a, a_type->key.type);
> + if (!n_idx) {
> + free(idx);
> + return;
> }
> +
> + struct ovsdb_datum result;
> +
> + ovsdb_datum_init_empty(&result);
> + ovsdb_datum_reallocate(&result, a_type, a->n - n_idx);
> +
> + for (i = 0; i < n_idx; i++) {
Why don't you destroy the atoms in-place in the loop above (bi = 0; bi <
b->n; bi++). Is it because you have to ovsdb_datum_find() each time? If
so, maybe add a comment.
> + ai = idx[i];
> +
> + /* Destroying atom. */
> + ovsdb_atom_destroy(&a->keys[ai], a_type->key.type);
> + if (a_type->value.type != OVSDB_TYPE_VOID) {
> + ovsdb_atom_destroy(&a->values[ai], a_type->value.type);
> + }
> +
> + /* Copy non-removed atoms from 'a' to result. */
> + unsigned int start_idx = (i > 0) ? idx[i - 1] + 1 : 0;
It won't save many cycles but could you initialize 'start_idx' to 0
outside the loop and set it to 'idx[i] + 1' after the statement below?
> + ovsdb_datum_push_unsafe(&result, a, start_idx, ai - start_idx,
> a_type);
> + }
> + /* Copying remaining atoms. */
> + ovsdb_datum_push_unsafe(&result, a, idx[n_idx - 1] + 1,
> + a->n - (idx[n_idx - 1] + 1), a_type);
You could also use 'start_idx' here ^ if you take my suggestion above
which would make the code a bit easier to read IMO.
> + a->n = 0;
> +
> + ovsdb_datum_swap(&result, a);
> + ovsdb_datum_destroy(&result, a_type);
> + free(idx);
> }
>
> struct ovsdb_symbol_table *
>
I also did some performance testing on this and it seems to show an
improvement! Good job!
_______________________________________________
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
