From d4a462d10af143d17a574e8fe0a1280875e8ca41 Mon Sep 17 00:00:00 2001 From: Costa Tsaousis Date: Fri, 6 May 2016 01:41:52 +0300 Subject: [PATCH 1/1] finalized dictionary.c --- profile/benchmark-dictionary.c | 132 +++++++++++++++++++++++++ src/appconfig.c | 2 + src/dictionary.c | 173 +++++++++++++++++++++------------ src/dictionary.h | 23 +++-- src/plugin_tc.c | 4 + 5 files changed, 266 insertions(+), 68 deletions(-) create mode 100644 profile/benchmark-dictionary.c diff --git a/profile/benchmark-dictionary.c b/profile/benchmark-dictionary.c new file mode 100644 index 00000000..163f4425 --- /dev/null +++ b/profile/benchmark-dictionary.c @@ -0,0 +1,132 @@ + +/* + * 1. build netdata (as normally) + * 2. cd profile/ + * 3. compile with: + * gcc -O3 -Wall -Wextra -I ../src/ -I ../ -o benchmark-dictionary benchmark-dictionary.c ../src/dictionary.o ../src/log.o ../src/avl.o ../src/common.o -pthread + * + */ + +#include +#include + +#include "dictionary.h" +#include "main.h" +#include "log.h" +#include "common.h" + +struct myvalue { + int i; +}; + +int main(int argc, char **argv) { + if(argc || argv) {;} + + DICTIONARY *dict = dictionary_create(DICTIONARY_FLAG_SINGLE_THREADED); + if(!dict) fatal("Cannot create dictionary."); + + struct rusage start, end; + unsigned long long dt; + char buf[100 + 1]; + struct myvalue value, *v; + int i, max = 1000000, max2; + + // ------------------------------------------------------------------------ + + getrusage(RUSAGE_SELF, &start); + dict->inserts = dict->deletes = dict->searches = 0ULL; + fprintf(stderr, "Inserting %d entries in the dictionary\n", max); + for(i = 0; i < max; i++) { + value.i = i; + snprintf(buf, 100, "%d", i); + + dictionary_set(dict, buf, &value, sizeof(struct myvalue)); + } + getrusage(RUSAGE_SELF, &end); + dt = (end.ru_utime.tv_sec * 1000000ULL + end.ru_utime.tv_usec) - (start.ru_utime.tv_sec * 1000000ULL + start.ru_utime.tv_usec); + fprintf(stderr, "Added %d entries in %llu nanoseconds: %llu inserts per second\n", max, dt, max * 1000000ULL / dt); + fprintf(stderr, " > Dictionary: %llu inserts, %llu deletes, %llu searches\n\n", dict->inserts, dict->deletes, dict->searches); + + // ------------------------------------------------------------------------ + + getrusage(RUSAGE_SELF, &start); + dict->inserts = dict->deletes = dict->searches = 0ULL; + fprintf(stderr, "Retrieving %d entries from the dictionary\n", max); + for(i = 0; i < max; i++) { + value.i = i; + snprintf(buf, 100, "%d", i); + + v = dictionary_get(dict, buf); + if(!v) + fprintf(stderr, "ERROR: cannot get value %d from the dictionary\n", i); + else if(v->i != i) + fprintf(stderr, "ERROR: expected %d but got %d\n", i, v->i); + } + getrusage(RUSAGE_SELF, &end); + dt = (end.ru_utime.tv_sec * 1000000ULL + end.ru_utime.tv_usec) - (start.ru_utime.tv_sec * 1000000ULL + start.ru_utime.tv_usec); + fprintf(stderr, "Read %d entries in %llu nanoseconds: %llu searches per second\n", max, dt, max * 1000000ULL / dt); + fprintf(stderr, " > Dictionary: %llu inserts, %llu deletes, %llu searches\n\n", dict->inserts, dict->deletes, dict->searches); + + // ------------------------------------------------------------------------ + + getrusage(RUSAGE_SELF, &start); + dict->inserts = dict->deletes = dict->searches = 0ULL; + fprintf(stderr, "Resetting %d entries in the dictionary\n", max); + for(i = 0; i < max; i++) { + value.i = i; + snprintf(buf, 100, "%d", i); + + dictionary_set(dict, buf, &value, sizeof(struct myvalue)); + } + getrusage(RUSAGE_SELF, &end); + dt = (end.ru_utime.tv_sec * 1000000ULL + end.ru_utime.tv_usec) - (start.ru_utime.tv_sec * 1000000ULL + start.ru_utime.tv_usec); + fprintf(stderr, "Reset %d entries in %llu nanoseconds: %llu inserts per second\n", max, dt, max * 1000000ULL / dt); + fprintf(stderr, " > Dictionary: %llu inserts, %llu deletes, %llu searches\n\n", dict->inserts, dict->deletes, dict->searches); + + // ------------------------------------------------------------------------ + + getrusage(RUSAGE_SELF, &start); + dict->inserts = dict->deletes = dict->searches = 0ULL; + fprintf(stderr, "Searching %d non-existing entries in the dictionary\n", max); + max2 = max * 2; + for(i = max; i < max2; i++) { + value.i = i; + snprintf(buf, 100, "%d", i); + + v = dictionary_get(dict, buf); + if(v) + fprintf(stderr, "ERROR: cannot got non-existing value %d from the dictionary\n", i); + } + getrusage(RUSAGE_SELF, &end); + dt = (end.ru_utime.tv_sec * 1000000ULL + end.ru_utime.tv_usec) - (start.ru_utime.tv_sec * 1000000ULL + start.ru_utime.tv_usec); + fprintf(stderr, "Searched %d non-existing entries in %llu nanoseconds: %llu searches per second\n", max, dt, max * 1000000ULL / dt); + fprintf(stderr, " > Dictionary: %llu inserts, %llu deletes, %llu searches\n\n", dict->inserts, dict->deletes, dict->searches); + + // ------------------------------------------------------------------------ + + getrusage(RUSAGE_SELF, &start); + dict->inserts = dict->deletes = dict->searches = 0ULL; + fprintf(stderr, "Deleting %d entries from the dictionary\n", max); + for(i = 0; i < max; i++) { + value.i = i; + snprintf(buf, 100, "%d", i); + + dictionary_del(dict, buf); + } + getrusage(RUSAGE_SELF, &end); + dt = (end.ru_utime.tv_sec * 1000000ULL + end.ru_utime.tv_usec) - (start.ru_utime.tv_sec * 1000000ULL + start.ru_utime.tv_usec); + fprintf(stderr, "Deleted %d entries in %llu nanoseconds: %llu deletes per second\n", max, dt, max * 1000000ULL / dt); + fprintf(stderr, " > Dictionary: %llu inserts, %llu deletes, %llu searches\n\n", dict->inserts, dict->deletes, dict->searches); + + // ------------------------------------------------------------------------ + + getrusage(RUSAGE_SELF, &start); + dict->inserts = dict->deletes = dict->searches = 0ULL; + fprintf(stderr, "Destroying dictionary\n"); + dictionary_destroy(dict); + getrusage(RUSAGE_SELF, &end); + dt = (end.ru_utime.tv_sec * 1000000ULL + end.ru_utime.tv_usec) - (start.ru_utime.tv_sec * 1000000ULL + start.ru_utime.tv_usec); + fprintf(stderr, "Destroyed in %llu nanoseconds\n", dt); + + return 0; +} diff --git a/src/appconfig.c b/src/appconfig.c index 73b94650..770f315e 100644 --- a/src/appconfig.c +++ b/src/appconfig.c @@ -90,11 +90,13 @@ static int config_compare(void* a, void* b) { avl_tree config_root_index = { NULL, config_compare, +#ifndef AVL_WITHOUT_PTHREADS #ifdef AVL_LOCK_WITH_MUTEX PTHREAD_MUTEX_INITIALIZER #else PTHREAD_RWLOCK_INITIALIZER #endif +#endif }; #define config_index_add(cfg) avl_insert(&config_root_index, (avl *)(cfg)) diff --git a/src/dictionary.c b/src/dictionary.c index 31f4d52e..7c6a8342 100644 --- a/src/dictionary.c +++ b/src/dictionary.c @@ -22,93 +22,110 @@ static int name_value_compare(void* a, void* b) { else return strcmp(((NAME_VALUE *)a)->name, ((NAME_VALUE *)b)->name); } -#define name_value_index_add(dict, cv) avl_insert(&((dict)->values_index), (avl *)(cv)) -#define name_value_index_del(dict, cv) avl_remove(&((dict)->values_index), (avl *)(cv)) +#define dictionary_name_value_index_add_nolock(dict, nv) do { (dict)->inserts++; avl_insert(&((dict)->values_index), (avl *)(nv)); } while(0) +#define dictionary_name_value_index_del_nolock(dict, nv) do { (dict)->deletes++; avl_remove(&(dict->values_index), (avl *)(nv)); } while(0) -static NAME_VALUE *dictionary_name_value_index_find(DICTIONARY *dict, const char *name, uint32_t hash) { +static inline NAME_VALUE *dictionary_name_value_index_find_nolock(DICTIONARY *dict, const char *name, uint32_t hash) { NAME_VALUE *result = NULL, tmp; tmp.hash = (hash)?hash:simple_hash(name); tmp.name = (char *)name; + dict->searches++; avl_search(&(dict->values_index), (avl *)&tmp, name_value_iterator, (avl **)&result); return result; } +static void dictionary_read_lock(DICTIONARY *dict) { + if(likely(!(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED))) + pthread_rwlock_rdlock(&dict->rwlock); +} + +static void dictionary_write_lock(DICTIONARY *dict) { + if(likely(!(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED))) + pthread_rwlock_wrlock(&dict->rwlock); +} + +static void dictionary_unlock(DICTIONARY *dict) { + if(likely(!(dict->flags & DICTIONARY_FLAG_SINGLE_THREADED))) + pthread_rwlock_unlock(&dict->rwlock); +} + // ---------------------------------------------------------------------------- -static NAME_VALUE *dictionary_name_value_create(DICTIONARY *dict, const char *name, void *value, size_t value_len) { +static NAME_VALUE *dictionary_name_value_create_nolock(DICTIONARY *dict, const char *name, void *value, size_t value_len, uint32_t hash) { debug(D_DICTIONARY, "Creating name value entry for name '%s', value '%s'.", name, value); NAME_VALUE *nv = calloc(1, sizeof(NAME_VALUE)); - if(!nv) { - fatal("Cannot allocate name_value of size %z", sizeof(NAME_VALUE)); - exit(1); - } + if(unlikely(!nv)) fatal("Cannot allocate name_value of size %z", sizeof(NAME_VALUE)); nv->name = strdup(name); - if(!nv->name) fatal("Cannot allocate name_value.name of size %z", strlen(name)); - nv->hash = simple_hash(nv->name); + if(unlikely(!nv->name)) + fatal("Cannot allocate name_value.name of size %z", strlen(name)); - nv->value = malloc(value_len); - if(!nv->value) fatal("Cannot allocate name_value.value of size %z", value_len); - memcpy(nv->value, value, value_len); + nv->hash = (hash)?hash:simple_hash(nv->name); - // link it - pthread_rwlock_wrlock(&dict->rwlock); - nv->next = dict->values; - dict->values = nv; - pthread_rwlock_unlock(&dict->rwlock); + if(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE) + nv->value = value; + else { + nv->value = malloc(value_len); + if (unlikely(!nv->value)) + fatal("Cannot allocate name_value.value of size %z", value_len); + + memcpy(nv->value, value, value_len); + } + + dictionary_write_lock(dict); // index it - name_value_index_add(dict, nv); + dictionary_name_value_index_add_nolock(dict, nv); + + dict->entries++; + + dictionary_unlock(dict); return nv; } -static void dictionary_name_value_destroy(DICTIONARY *dict, NAME_VALUE *nv) { +static void dictionary_name_value_destroy_nolock(DICTIONARY *dict, NAME_VALUE *nv) { debug(D_DICTIONARY, "Destroying name value entry for name '%s'.", nv->name); - pthread_rwlock_wrlock(&dict->rwlock); - if(dict->values == nv) dict->values = nv->next; - else { - NAME_VALUE *n = dict->values; - while(n && n->next && n->next != nv) nv = nv->next; - if(!n || n->next != nv) { - fatal("Cannot find name_value with name '%s' in dictionary.", nv->name); - exit(1); - } - n->next = nv->next; - nv->next = NULL; - } - pthread_rwlock_unlock(&dict->rwlock); + dictionary_name_value_index_del_nolock(dict, nv); + + dict->entries--; + + free(nv->name); + + if(!(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE)) + free(nv->value); - free(nv->value); free(nv); } // ---------------------------------------------------------------------------- -DICTIONARY *dictionary_create(void) { +DICTIONARY *dictionary_create(uint32_t flags) { debug(D_DICTIONARY, "Creating dictionary."); DICTIONARY *dict = calloc(1, sizeof(DICTIONARY)); - if(!dict) { - fatal("Cannot allocate DICTIONARY"); - exit(1); - } + if(unlikely(!dict)) fatal("Cannot allocate DICTIONARY"); avl_init(&dict->values_index, name_value_compare); pthread_rwlock_init(&dict->rwlock, NULL); + dict->flags = flags; + return dict; } void dictionary_destroy(DICTIONARY *dict) { debug(D_DICTIONARY, "Destroying dictionary."); - pthread_rwlock_wrlock(&dict->rwlock); - while(dict->values) dictionary_name_value_destroy(dict, dict->values); - pthread_rwlock_unlock(&dict->rwlock); + dictionary_write_lock(dict); + + while(dict->values_index.root) + dictionary_name_value_destroy_nolock(dict, (NAME_VALUE *)dict->values_index.root); + + dictionary_unlock(dict); free(dict); } @@ -118,27 +135,40 @@ void dictionary_destroy(DICTIONARY *dict) { void *dictionary_set(DICTIONARY *dict, const char *name, void *value, size_t value_len) { debug(D_DICTIONARY, "SET dictionary entry with name '%s'.", name); - pthread_rwlock_rdlock(&dict->rwlock); - NAME_VALUE *nv = dictionary_name_value_index_find(dict, name, 0); - pthread_rwlock_unlock(&dict->rwlock); - if(!nv) { + uint32_t hash = simple_hash(name); + + dictionary_read_lock(dict); + NAME_VALUE *nv = dictionary_name_value_index_find_nolock(dict, name, hash); + dictionary_unlock(dict); + + if(unlikely(!nv)) { debug(D_DICTIONARY, "Dictionary entry with name '%s' not found. Creating a new one.", name); - nv = dictionary_name_value_create(dict, name, value, value_len); - if(!nv) { + + pthread_rwlock_wrlock(&dict->rwlock); + nv = dictionary_name_value_create_nolock(dict, name, value, value_len, hash); + + if(unlikely(!nv)) fatal("Cannot create name_value."); - exit(1); - } - return nv->value; + + dictionary_unlock(dict); } else { debug(D_DICTIONARY, "Dictionary entry with name '%s' found. Changing its value.", name); - pthread_rwlock_wrlock(&dict->rwlock); - void *old = nv->value; - nv->value = malloc(value_len); - if(!nv->value) fatal("Cannot allocate value of size %z", value_len); - memcpy(nv->value, value, value_len); - pthread_rwlock_unlock(&dict->rwlock); - free(old); + + if(dict->flags & DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE) + nv->value = value; + else { + void *value = malloc(value_len), + *old = nv->value; + + if(unlikely(!nv->value)) + fatal("Cannot allocate value of size %z", value_len); + + memcpy(value, value, value_len); + nv->value = value; + + free(old); + } } return nv->value; @@ -147,10 +177,11 @@ void *dictionary_set(DICTIONARY *dict, const char *name, void *value, size_t val void *dictionary_get(DICTIONARY *dict, const char *name) { debug(D_DICTIONARY, "GET dictionary entry with name '%s'.", name); - pthread_rwlock_rdlock(&dict->rwlock); - NAME_VALUE *nv = dictionary_name_value_index_find(dict, name, 0); - pthread_rwlock_unlock(&dict->rwlock); - if(!nv) { + dictionary_read_lock(dict); + NAME_VALUE *nv = dictionary_name_value_index_find_nolock(dict, name, 0); + dictionary_unlock(dict); + + if(unlikely(!nv)) { debug(D_DICTIONARY, "Not found dictionary entry with name '%s'.", name); return NULL; } @@ -158,3 +189,21 @@ void *dictionary_get(DICTIONARY *dict, const char *name) { debug(D_DICTIONARY, "Found dictionary entry with name '%s'.", name); return nv->value; } + +void dictionary_del(DICTIONARY *dict, const char *name) { + debug(D_DICTIONARY, "DEL dictionary entry with name '%s'.", name); + + dictionary_read_lock(dict); + NAME_VALUE *nv = dictionary_name_value_index_find_nolock(dict, name, 0); + dictionary_unlock(dict); + + if(unlikely(!nv)) { + debug(D_DICTIONARY, "Not found dictionary entry with name '%s'.", name); + return; + } + + debug(D_DICTIONARY, "Found dictionary entry with name '%s'.", name); + pthread_rwlock_wrlock(&dict->rwlock); + dictionary_name_value_destroy_nolock(dict, nv); + dictionary_unlock(dict); +} diff --git a/src/dictionary.h b/src/dictionary.h index 9822b23c..e9edab4c 100644 --- a/src/dictionary.h +++ b/src/dictionary.h @@ -1,4 +1,7 @@ +#include + #include "web_buffer.h" +#include "avl.h" #ifndef NETDATA_DICTIONARY_H #define NETDATA_DICTIONARY_H 1 @@ -8,22 +11,30 @@ typedef struct name_value { uint32_t hash; // a simple hash to speed up searching // we first compare hashes, and only if the hashes are equal we do string comparisons - char *name; - char *value; - - struct name_value *next; + void *value; } NAME_VALUE; typedef struct dictionary { - NAME_VALUE *values; + uint32_t flags; + + unsigned long long inserts; + unsigned long long deletes; + unsigned long long searches; + unsigned long long entries; + avl_tree values_index; pthread_rwlock_t rwlock; } DICTIONARY; -extern DICTIONARY *dictionary_create(void); +#define DICTIONARY_FLAG_DEFAULT 0x00000000 +#define DICTIONARY_FLAG_SINGLE_THREADED 0x00000001 +#define DICTIONARY_FLAG_VALUE_LINK_DONT_CLONE 0x00000002 + +extern DICTIONARY *dictionary_create(uint32_t flags); extern void dictionary_destroy(DICTIONARY *dict); extern void *dictionary_set(DICTIONARY *dict, const char *name, void *value, size_t value_len); extern void *dictionary_get(DICTIONARY *dict, const char *name); +extern void dictionary_del(DICTIONARY *dict, const char *name); #endif /* NETDATA_DICTIONARY_H */ diff --git a/src/plugin_tc.c b/src/plugin_tc.c index 2c7a55ce..d70f5265 100644 --- a/src/plugin_tc.c +++ b/src/plugin_tc.c @@ -94,11 +94,13 @@ static int tc_device_compare(void* a, void* b) { avl_tree tc_device_root_index = { NULL, tc_device_compare, +#ifndef AVL_WITHOUT_PTHREADS #ifdef AVL_LOCK_WITH_MUTEX PTHREAD_MUTEX_INITIALIZER #else PTHREAD_RWLOCK_INITIALIZER #endif +#endif }; #define tc_device_index_add(st) avl_insert(&tc_device_root_index, (avl *)(st)) @@ -349,10 +351,12 @@ static struct tc_device *tc_device_create(char *id) d->classes_index.compar = tc_class_compare; int lock; +#ifndef AVL_WITHOUT_PTHREADS #ifdef AVL_LOCK_WITH_MUTEX lock = pthread_mutex_init(&d->classes_index.mutex, NULL); #else lock = pthread_rwlock_init(&d->classes_index.rwlock, NULL); +#endif #endif if(lock != 0) fatal("Failed to initialize plugin_tc mutex/rwlock, return code %d.", lock); -- 2.39.2