This is an automated email from the git hooks/post-receive script.
firstyear pushed a change to branch master in repository 389-ds-base.
from c9151c2 Ticket 49284 - resolve crash in memberof when deleting attrs new 043b3c9 Ticket 49297 - improve search perf in bpt by removing a deref
The 1 revisions listed above as "new" are entirely new to this repository and will be described in separate emails. The revisions listed as "adds" were already present in the repository and have only been added to this reference.
Summary of changes: src/libsds/sds/bpt/bpt.c | 6 +++--- src/libsds/sds/bpt/bpt.h | 8 ++++---- src/libsds/sds/bpt/common.c | 22 +++++++++++----------- src/libsds/sds/bpt/search.c | 5 +++-- src/libsds/sds/bpt/set.c | 27 +++++++++++++++------------ src/libsds/sds/bpt_cow/bpt_cow.c | 6 +++--- src/libsds/sds/bpt_cow/node.c | 2 +- src/libsds/sds/bpt_cow/search.c | 3 ++- 8 files changed, 42 insertions(+), 37 deletions(-)
This is an automated email from the git hooks/post-receive script.
firstyear pushed a commit to branch master in repository 389-ds-base.
commit 043b3c9d656d6f134a2860dfc85b535047d274b5 Author: William Brown firstyear@redhat.com Date: Wed Jun 21 14:10:50 2017 +1000
Ticket 49297 - improve search perf in bpt by removing a deref
Bug Description: improve search perf in bpt by removing the derefence of the key cmp fn, instead we pass the fn ptr to the functions.
Fix Description: Pass the fn pointer to the search and lookup functions.
https://pagure.io/389-ds-base/issue/49297
Author: wibrown
Review by: mreynolds (Thanks!) --- src/libsds/sds/bpt/bpt.c | 6 +++--- src/libsds/sds/bpt/bpt.h | 8 ++++---- src/libsds/sds/bpt/common.c | 22 +++++++++++----------- src/libsds/sds/bpt/search.c | 5 +++-- src/libsds/sds/bpt/set.c | 27 +++++++++++++++------------ src/libsds/sds/bpt_cow/bpt_cow.c | 6 +++--- src/libsds/sds/bpt_cow/node.c | 2 +- src/libsds/sds/bpt_cow/search.c | 3 ++- 8 files changed, 42 insertions(+), 37 deletions(-)
diff --git a/src/libsds/sds/bpt/bpt.c b/src/libsds/sds/bpt/bpt.c index b6b283e..3a0b259 100644 --- a/src/libsds/sds/bpt/bpt.c +++ b/src/libsds/sds/bpt/bpt.c @@ -93,7 +93,7 @@ sds_bptree_insert(sds_bptree_instance *binst, void *key, void *value) { }
/* CHECK FOR DUPLICATE KEY HERE. */ - if (sds_bptree_node_contains_key(binst, target_node, key) == SDS_KEY_PRESENT) { + if (sds_bptree_node_contains_key(binst->key_cmp_fn, target_node, key) == SDS_KEY_PRESENT) { return SDS_DUPLICATE_KEY; }
@@ -151,7 +151,7 @@ sds_bptree_delete(sds_bptree_instance *binst, void *key) { }
/* CHECK FOR DUPLICATE KEY HERE. */ - result = sds_bptree_node_contains_key(binst, target_node, key); + result = sds_bptree_node_contains_key(binst->key_cmp_fn, target_node, key); if (result != SDS_KEY_PRESENT) { return result; } @@ -237,7 +237,7 @@ sds_bptree_delete(sds_bptree_instance *binst, void *key) { sds_bptree_leaf_compact(binst, left, next_node); deleted_node = next_node; } else { - /* Mate, if you get here you are fucked. */ + /* Mate, if you get here you are in a lot of trouble. */ return SDS_INVALID_NODE; }
diff --git a/src/libsds/sds/bpt/bpt.h b/src/libsds/sds/bpt/bpt.h index 712213b..0ea130e 100644 --- a/src/libsds/sds/bpt/bpt.h +++ b/src/libsds/sds/bpt/bpt.h @@ -29,11 +29,11 @@ sds_bptree_node *sds_bptree_arrays_to_node_list(void **keys, void **values, size sds_result sds_bptree_node_list_to_tree(sds_bptree_instance *binst, sds_bptree_node *node); sds_bptree_node * sds_bptree_node_create(void); sds_result sds_bptree_node_destroy(sds_bptree_instance *binst, sds_bptree_node *node); -sds_result sds_bptree_node_contains_key(sds_bptree_instance *binst, sds_bptree_node *node, void *key); -size_t sds_bptree_node_key_eq_index(sds_bptree_instance *binst, sds_bptree_node *node, void *key); -size_t sds_bptree_node_key_lt_index(sds_bptree_instance *binst, sds_bptree_node *node, void *key); +sds_result sds_bptree_node_contains_key(int64_t (*key_cmp_fn)(void *a, void *b), sds_bptree_node *node, void *key); +size_t sds_bptree_node_key_eq_index(int64_t (*key_cmp_fn)(void *a, void *b), sds_bptree_node *node, void *key); +size_t sds_bptree_node_key_lt_index(int64_t (*key_cmp_fn)(void *a, void *b), sds_bptree_node *node, void *key); void sds_bptree_node_siblings(sds_bptree_node *target, sds_bptree_node **left, sds_bptree_node **right); -sds_result sds_bptree_node_retrieve_key(sds_bptree_instance *binst, sds_bptree_node *node, void *key, void **target); +sds_result sds_bptree_node_retrieve_key(int64_t (*key_cmp_fn)(void *a, void *b), sds_bptree_node *node, void *key, void **target); void sds_bptree_node_node_replace(sds_bptree_node *target_node, sds_bptree_node *origin_node, sds_bptree_node *replace_node); /* sds_result sds_bptree_value_create(struct sds_bptree_instance *binst, void *value, size_t value_size, struct sds_bptree_value **new_value); diff --git a/src/libsds/sds/bpt/common.c b/src/libsds/sds/bpt/common.c index dcfecae..9560d2c 100644 --- a/src/libsds/sds/bpt/common.c +++ b/src/libsds/sds/bpt/common.c @@ -55,11 +55,11 @@ sds_bptree_node_destroy(sds_bptree_instance *binst, sds_bptree_node *node) { }
size_t -sds_bptree_node_key_lt_index(sds_bptree_instance *binst, sds_bptree_node *node, void *key) { +sds_bptree_node_key_lt_index(int64_t (*key_cmp_fn)(void *a, void *b), sds_bptree_node *node, void *key) { /* This is a very busy part of the code. */ size_t index = 0; for (;index < node->item_count; index++) { - if (binst->key_cmp_fn(key, node->keys[index]) < 0) { + if (key_cmp_fn(key, node->keys[index]) < 0) { return index; } } @@ -67,11 +67,11 @@ sds_bptree_node_key_lt_index(sds_bptree_instance *binst, sds_bptree_node *node, }
size_t -sds_bptree_node_key_eq_index(sds_bptree_instance *binst, sds_bptree_node *node, void *key) { +sds_bptree_node_key_eq_index(int64_t (*key_cmp_fn)(void *a, void *b), sds_bptree_node *node, void *key) { size_t index = 0; int64_t result = 0; for (;index < node->item_count; index++) { - result = binst->key_cmp_fn(key, node->keys[index]); + result = key_cmp_fn(key, node->keys[index]); if (result == 0) { return index; } else if (result < 0) { @@ -115,17 +115,17 @@ sds_bptree_node_leftmost_child_key(sds_bptree_node *parent) { }
sds_result -sds_bptree_node_contains_key(sds_bptree_instance *binst, sds_bptree_node *node, void *key) { +sds_bptree_node_contains_key(int64_t (*key_cmp_fn)(void *a, void *b), sds_bptree_node *node, void *key) { /* Very busy part of the code. Could be improved? */ - if (sds_bptree_node_key_eq_index(binst, node, key) != node->item_count) { + if (sds_bptree_node_key_eq_index(key_cmp_fn, node, key) != node->item_count) { return SDS_KEY_PRESENT; } return SDS_KEY_NOT_PRESENT; }
sds_result -sds_bptree_node_retrieve_key(sds_bptree_instance *binst, sds_bptree_node *node, void *key, void **target) { - size_t index = sds_bptree_node_key_eq_index(binst, node, key); +sds_bptree_node_retrieve_key(int64_t (*key_cmp_fn)(void *a, void *b), sds_bptree_node *node, void *key, void **target) { + size_t index = sds_bptree_node_key_eq_index(key_cmp_fn, node, key);
if (index == node->item_count) { return SDS_KEY_NOT_PRESENT; @@ -204,7 +204,7 @@ sds_bptree_leaf_insert(sds_bptree_instance *binst, sds_bptree_node *node, void * #ifdef DEBUG sds_log("sds_bptree_leaf_insert", "node_%p key %" PRIu64 " ", node, key); #endif - size_t index = sds_bptree_node_key_lt_index(binst, node, key); + size_t index = sds_bptree_node_key_lt_index(binst->key_cmp_fn, node, key); // Move everything else to the right if (node->item_count > 0) { for (size_t i = node->item_count; i > index; i--) { @@ -312,7 +312,7 @@ sds_bptree_branch_insert(sds_bptree_instance *binst, sds_bptree_node *node, void * If we are inserting 10, we need to put the new_node to the *RIGHT*. * If our key is LESS, then we insert to the LEFT. */ - size_t index = sds_bptree_node_key_lt_index(binst, node, key); + size_t index = sds_bptree_node_key_lt_index(binst->key_cmp_fn, node, key);
// If index == node->item_count, nothing will move. if (node->item_count > 0) { @@ -502,7 +502,7 @@ sds_bptree_leaf_delete(sds_bptree_instance *binst, sds_bptree_node *node, void * sds_log("sds_bptree_leaf_delete", "deleting %d from %p", key, node); #endif /* Find the value */ - size_t index = sds_bptree_node_key_eq_index(binst, node, key); + size_t index = sds_bptree_node_key_eq_index(binst->key_cmp_fn, node, key);
/* extract the contents (if any) */ void *value = node->values[index]; diff --git a/src/libsds/sds/bpt/search.c b/src/libsds/sds/bpt/search.c index e60f259..2ee7ccc 100644 --- a/src/libsds/sds/bpt/search.c +++ b/src/libsds/sds/bpt/search.c @@ -18,6 +18,7 @@ sds_result sds_bptree_search_node(sds_bptree_instance *binst, sds_bptree_node *root, void *key, sds_bptree_node **target_out_node) { sds_bptree_node *target_node = root; uint64_t i = 0; + int64_t (*key_cmp_fn)(void *a, void *b) = binst->key_cmp_fn;
/* We do this first, as we need the node to pass before we access it! */ #ifdef DEBUG @@ -36,7 +37,7 @@ sds_bptree_search_node(sds_bptree_instance *binst, sds_bptree_node *root, void * branch_loop: while (target_node->level > 0) { while (i < target_node->item_count) { - if (binst->key_cmp_fn(key, (target_node)->keys[i]) < 0) { + if (key_cmp_fn(key, (target_node)->keys[i]) < 0) { target_node = (sds_bptree_node *)target_node->values[i]; #ifdef DEBUG if (binst->search_checksumming) { @@ -122,7 +123,7 @@ sds_bptree_retrieve_internal(sds_bptree_instance *binst, sds_bptree_node *root, #ifdef DEBUG sds_log("sds_bptree_retrieve_internal", "==> Completing retrieve of %d", key); #endif - return sds_bptree_node_retrieve_key(binst, target_node, key, target); + return sds_bptree_node_retrieve_key(binst->key_cmp_fn, target_node, key, target); }
diff --git a/src/libsds/sds/bpt/set.c b/src/libsds/sds/bpt/set.c index 2319ac4..1911ce1 100644 --- a/src/libsds/sds/bpt/set.c +++ b/src/libsds/sds/bpt/set.c @@ -125,6 +125,9 @@ sds_bptree_set_operation(sds_bptree_instance *binst_a, sds_bptree_instance *bins return result; }
+ int64_t (*key_cmp_fn)(void *a, void *b) = binst_a->key_cmp_fn; + void *(*key_dup_fn)(void *key) = binst_a->key_dup_fn; + /* Need a pointer to track node_a and index_a, vs node_b and index_b */ sds_bptree_node *node_a = sds_bptree_node_min(binst_a); size_t index_a = 0; @@ -154,11 +157,11 @@ sds_bptree_set_operation(sds_bptree_instance *binst_a, sds_bptree_instance *bins
/* Now iterate over the values. */ while (result_a == SDS_SUCCESS && result_b == SDS_SUCCESS) { - int64_t cmp = binst_a->key_cmp_fn(node_a->keys[index_a], node_b->keys[index_b]); + int64_t cmp = key_cmp_fn(node_a->keys[index_a], node_b->keys[index_b]); if (cmp == 0) { /* These values are the same, advance! */ if (both) { - void *key = binst_a->key_dup_fn(node_a->keys[index_a]); + void *key = key_dup_fn(node_a->keys[index_a]); sds_bptree_node_list_append(&result_ptr, key, NULL); } result_a = sds_bptree_list_advance(&node_a, &index_a); @@ -167,14 +170,14 @@ sds_bptree_set_operation(sds_bptree_instance *binst_a, sds_bptree_instance *bins /* If A is smaller, we advance a, and include the value */ /* !! WHAT ABOUT VALUE DUPLICATION!!! */ if (diff || alist) { - void *key = binst_a->key_dup_fn(node_a->keys[index_a]); + void *key = key_dup_fn(node_a->keys[index_a]); sds_bptree_node_list_append(&result_ptr, key, NULL); } result_a = sds_bptree_list_advance(&node_a, &index_a); } else { /* !! WHAT ABOUT VALUE DUPLICATION!!! */ if (diff) { - void *key = binst_b->key_dup_fn(node_b->keys[index_b]); + void *key = key_dup_fn(node_b->keys[index_b]); sds_bptree_node_list_append(&result_ptr, key, NULL); } result_b = sds_bptree_list_advance(&node_b, &index_b); @@ -183,17 +186,17 @@ sds_bptree_set_operation(sds_bptree_instance *binst_a, sds_bptree_instance *bins
/* We have now exhausted a list. Which one? */ while (result_a == SDS_SUCCESS) { - int64_t cmp = binst_a->key_cmp_fn(node_a->keys[index_a], node_b->keys[index_b]); + int64_t cmp = key_cmp_fn(node_a->keys[index_a], node_b->keys[index_b]); /* We have exhausted B. Finish iterating */ if (cmp == 0) { if (both) { - void *key = binst_a->key_dup_fn(node_a->keys[index_a]); + void *key = key_dup_fn(node_a->keys[index_a]); /* !! WHAT ABOUT VALUE DUPLICATION!!! */ sds_bptree_node_list_append(&result_ptr, key, NULL); } } else if (cmp != 0) { if (diff || alist) { - void *key = binst_a->key_dup_fn(node_a->keys[index_a]); + void *key = key_dup_fn(node_a->keys[index_a]); /* !! WHAT ABOUT VALUE DUPLICATION!!! */ sds_bptree_node_list_append(&result_ptr, key, NULL); } @@ -202,16 +205,16 @@ sds_bptree_set_operation(sds_bptree_instance *binst_a, sds_bptree_instance *bins }
while (result_b == SDS_SUCCESS) { - int64_t cmp = binst_a->key_cmp_fn(node_a->keys[index_a], node_b->keys[index_b]); + int64_t cmp = key_cmp_fn(node_a->keys[index_a], node_b->keys[index_b]); if (cmp == 0) { if (both) { - void *key = binst_a->key_dup_fn(node_b->keys[index_b]); + void *key = key_dup_fn(node_b->keys[index_b]); /* !! WHAT ABOUT VALUE DUPLICATION!!! */ sds_bptree_node_list_append(&result_ptr, key, NULL); } } else if (cmp != 0) { if (diff) { - void *key = binst_a->key_dup_fn(node_b->keys[index_b]); + void *key = key_dup_fn(node_b->keys[index_b]); /* !! WHAT ABOUT VALUE DUPLICATION!!! */ sds_bptree_node_list_append(&result_ptr, key, NULL); } @@ -226,7 +229,7 @@ sds_bptree_set_operation(sds_bptree_instance *binst_a, sds_bptree_instance *bins while (result_a == SDS_SUCCESS) { /* We have exhausted B. Finish iterating */ if (diff || alist) { - void *key = binst_a->key_dup_fn(node_a->keys[index_a]); + void *key = key_dup_fn(node_a->keys[index_a]); /* !! WHAT ABOUT VALUE DUPLICATION!!! */ sds_bptree_node_list_append(&result_ptr, key, NULL); } @@ -235,7 +238,7 @@ sds_bptree_set_operation(sds_bptree_instance *binst_a, sds_bptree_instance *bins
while (result_b == SDS_SUCCESS) { if (diff) { - void *key = binst_a->key_dup_fn(node_b->keys[index_b]); + void *key = key_dup_fn(node_b->keys[index_b]); /* !! WHAT ABOUT VALUE DUPLICATION!!! */ sds_bptree_node_list_append(&result_ptr, key, NULL); } diff --git a/src/libsds/sds/bpt_cow/bpt_cow.c b/src/libsds/sds/bpt_cow/bpt_cow.c index 7120efc..c88d879 100644 --- a/src/libsds/sds/bpt_cow/bpt_cow.c +++ b/src/libsds/sds/bpt_cow/bpt_cow.c @@ -147,7 +147,7 @@ sds_result sds_bptree_cow_delete(sds_bptree_transaction *btxn, void *key) { }
// Check the key exists - result = sds_bptree_node_contains_key(btxn->bi, target_node, key); + result = sds_bptree_node_contains_key(btxn->bi->key_cmp_fn, target_node, key); if (result != SDS_KEY_PRESENT) { return result; } @@ -383,7 +383,7 @@ sds_result sds_bptree_cow_insert(sds_bptree_transaction *btxn, void *key, void * return result; }
- if (sds_bptree_node_contains_key(btxn->bi, target_node, key) == SDS_KEY_PRESENT) { + if (sds_bptree_node_contains_key(btxn->bi->key_cmp_fn, target_node, key) == SDS_KEY_PRESENT) { // sds_bptree_node_list_release(&target_path); return SDS_DUPLICATE_KEY; } @@ -437,7 +437,7 @@ sds_result sds_bptree_cow_update(sds_bptree_transaction *btxn, void *key, void * return result; }
- if (sds_bptree_node_contains_key(btxn->bi, target_node, key) == SDS_KEY_NOT_PRESENT) { + if (sds_bptree_node_contains_key(btxn->bi->key_cmp_fn, target_node, key) == SDS_KEY_NOT_PRESENT) { // Call insert instead! sds_bptree_cow_insert(btxn, key, value); } else { diff --git a/src/libsds/sds/bpt_cow/node.c b/src/libsds/sds/bpt_cow/node.c index 648f6ea..c3eeb55 100644 --- a/src/libsds/sds/bpt_cow/node.c +++ b/src/libsds/sds/bpt_cow/node.c @@ -232,7 +232,7 @@ sds_bptree_cow_node_create(sds_bptree_transaction *btxn) { void sds_bptree_cow_node_update(sds_bptree_transaction *btxn, sds_bptree_node *node, void *key, void *value) { // find the key index. - size_t index = sds_bptree_node_key_eq_index(btxn->bi, node, key); + size_t index = sds_bptree_node_key_eq_index(btxn->bi->key_cmp_fn, node, key); // value free btxn->bi->value_free_fn(node->values[index]); // insert. diff --git a/src/libsds/sds/bpt_cow/search.c b/src/libsds/sds/bpt_cow/search.c index 0b315fb..0327729 100644 --- a/src/libsds/sds/bpt_cow/search.c +++ b/src/libsds/sds/bpt_cow/search.c @@ -19,6 +19,7 @@ sds_bptree_search_node_path(sds_bptree_transaction *btxn, void *key, sds_bptree_ sds_bptree_node *parent_node = NULL; sds_bptree_node *target_node = btxn->root; size_t i = 0; + int64_t (*key_cmp_fn)(void *a, void *b) = btxn->bi->key_cmp_fn;
/* We do this first, as we need the node to pass before we access it! */ #ifdef DEBUG @@ -47,7 +48,7 @@ branch_loop: } #endif while (i < target_node->item_count) { - if (btxn->bi->key_cmp_fn(key, (target_node)->keys[i]) < 0) { + if (key_cmp_fn(key, (target_node)->keys[i]) < 0) { parent_node = target_node; target_node = (sds_bptree_node *)target_node->values[i]; i = 0;
389-commits@lists.fedoraproject.org