7:43 p.m.
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(a)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;
--
To stop receiving notification emails like this one, please contact
the administrator of this repository.