From 20b718e416aaa44d1faa31b6370263affa4dc1df Mon Sep 17 00:00:00 2001 From: ken Date: Thu, 2 Mar 2017 00:28:28 -0800 Subject: [PATCH] dynamic hashtables optimized --- src/testston.c | 31 ++++--- ston/ston_ht.h | 215 ++++++++++++++++++++++--------------------------- 2 files changed, 111 insertions(+), 135 deletions(-) diff --git a/src/testston.c b/src/testston.c index 014a58c..0f0f1f9 100644 --- a/src/testston.c +++ b/src/testston.c @@ -27,6 +27,14 @@ else \ printf("ht_size: [units:%i][bytes:%li]\n",ston_ht_size(ht),ston_ht32_size(ht)); \ +#define check_dht(_HT) \ + if ((_HT) == NULL) \ + { fprintf(stderr,RED"Could not allocate dht32"CLRCN); \ + return -1; \ + } \ + else \ + printf("ht_size: [units:%i][bytes:%i]\n",ston_dht_units(_HT,_HT->header.start_depth),ston_dht_bytes(_HT,_HT->header.start_depth)); \ + int main(int argc, char* argv[]) { static ston_ht ht; @@ -159,10 +167,10 @@ int main(int argc, char* argv[]) printf("\n--------- DHT ----------\n\n"); ston_dht dht; - elements = 50; + elements = 500; columns = 6; - dht = ston_dht32_new(columns, elements, 0, malloc, free); - check_ht(dht); + dht = ston_dht32_new(columns, malloc, free); + check_dht(dht); elements = 50000; printf("Filling Dynamic hashtable with %i entries\n", (int)elements); for(key = 0xCEED; elements--; key *= 7) @@ -186,7 +194,7 @@ int main(int argc, char* argv[]) printf(RED"FAIL"CLRC"(%i)\n", fail); else printf(GREEN"PASS"CLRCN); - max_capacity = (ston_up2pow(50 << 1) * (ston_dht_pagemax(dht) - ston_dht_pagestart(dht))) - 50000; + max_capacity = 100000; cap = max_capacity; printf("Overfilling hashtable with %i entries\n", max_capacity); for(key = 0xCEED2; cap--; key *= 13) @@ -211,18 +219,7 @@ int main(int argc, char* argv[]) else printf(GREEN"PASS"CLRCN); - cap = 20; - printf("Post-capacity insertion of %i\n",cap); - for (key = 0xCEED3; cap--; key *= 23) - { val[0] = key; - for(i = 1; i < columns; i++) - val[i] = key * -i; - size_t count = ston_dht32_insertx(dht,key,val,0,columns); - printf("Insertion %2i wrote %i bytes: %s"CLRCN, (int)cap, (int) count, - (count == 0) ? GREEN"PASS" : RED"FAIL"); - } - - + max_capacity = 5000000; printf("Refilling hashtable with %i entries\n", max_capacity); cap = max_capacity; for(key = 0xCEED2; cap--; key *= 13) @@ -247,7 +244,7 @@ int main(int argc, char* argv[]) else printf(GREEN"PASS"CLRCN); - ston_dht32_free(dht); + ston_dht_free(dht); return 0; } diff --git a/ston/ston_ht.h b/ston/ston_ht.h index fb5d566..e97a589 100644 --- a/ston/ston_ht.h +++ b/ston/ston_ht.h @@ -64,14 +64,13 @@ typedef struct ston_ht_header_t { uint16_t ht_columns; uint8_t ht_2pow, ht_flags; }ston_ht_h,* ston_ht; -#define STON_HT_HEADERSIZE (sizeof(struct ston_ht_header_t)) STON_FUNC uint32_t ston_up2pow(uint32_t); STON_FUNC uint8_t ston_trailing0(uint32_t); STON_FUNC -ston_ht ston_ht32_create(struct ston_ht_header_t,void*(*)(size_t)); +ston_ht ston_ht32_create(uint16_t,uint8_t,uint8_t,void*(*)(size_t)); STON_FUNC uint32_t* ston_ht32_row(ston_ht,uint32_t); STON_FUNC @@ -79,7 +78,7 @@ uint32_t ston_ht32_insert(ston_ht,uint32_t,uint16_t,uint32_t); STON_FUNC size_t ston_ht32_insertx(ston_ht,uint32_t,uint32_t*,size_t,size_t); -#define ston_ht32_new(_COL,_N,_F,_FN) (ston_ht32_create((ston_ht_h){_COL,ston_trailing0(ston_up2pow(_N << 1)),_F},_FN)) +#define ston_ht32_new(_COL,_N,_F,_FN) (ston_ht32_create(_COL,ston_trailing0(ston_up2pow(_N << 1)),_F,_FN)) #define ston_ht32_entry(_HT,_KEY,_COL) (ston_ht32_row(_HT,_KEY) + _COL) #define ston_ht_size(_HT) ((_HT)->ht_columns << (_HT)->ht_2pow) #define ston_ht_rows(_HT) (0x1 << (_HT)->ht_2pow) @@ -129,13 +128,17 @@ uint8_t ston_trailing0 */ STON_FUNC ston_ht ston_ht32_create -( struct ston_ht_header_t ht_header, - void* (*alloc_fn)(size_t) +( uint16_t ht_columns, + uint8_t ht_2pow, + uint8_t ht_flags, + void* (*alloc_fn)(size_t) ) -{ size_t ht_bytes = ston_ht32_size(&ht_header); - ston_ht ht = (ston_ht) alloc_fn(STON_HT_HEADERSIZE + ht_bytes); +{ size_t ht_bytes = (ht_columns << ht_2pow) * sizeof(uint32_t); + ston_ht ht = (ston_ht) alloc_fn(sizeof(ston_ht_h) + ht_bytes); if (ht != NULL) - { memcpy(ht,&ht_header,STON_HT_HEADERSIZE); + { ht->ht_columns = ht_columns; + ht->ht_2pow = ht_2pow; + ht->ht_flags = ht_flags; memset(ht + 1, 0, ht_bytes); } return ht; @@ -266,61 +269,63 @@ ston_ht32_insertx external allocation. */ typedef struct ston_dht_header_t -{ uint16_t ht_columns; - uint8_t ht_2pow, ht_flags; - void* (*ht_alloc)(size_t); - void (*ht_free)(void*); - void** page_head; -}ston_dht_h,* ston_dht; -#define STON_DHT_HEADERSIZE (sizeof(struct ston_dht_header_t)) +{ uint16_t columns; + uint8_t unit_bytes; + uint8_t start_depth; +}ston_dht_h; + +typedef struct ston_dht_t +{ ston_dht_h header; + void* pages[sizeof(void*) * 8]; + void* (*ht_alloc)(size_t); + void (*ht_free)(void*); +}* ston_dht; STON_FUNC -ston_dht ston_dht32_create(struct ston_ht_header_t,void*(*)(size_t),void(*)(void*)); +ston_dht ston_dht_create(uint16_t,uint8_t,uint8_t,void*(*)(size_t),void(*)(void*)); STON_FUNC uint32_t* ston_dht32_row(ston_dht,uint32_t); STON_FUNC uint32_t ston_dht32_insert(ston_dht,uint32_t,uint16_t,uint32_t); STON_FUNC -size_t ston_dht32_insertx(ston_dht,uint32_t,uint32_t*,size_t,size_t); +size_t ston_dht32_insertx(ston_dht,uint32_t,uint32_t*,uint16_t,size_t); STON_FUNC -ston_dht ston_dht32_free(ston_dht); +ston_dht ston_dht_free(ston_dht); + +#define ston_dht_units(_HT,_DEPTH) ((_HT)->header.columns << _DEPTH) +#define ston_dht_bytes(_HT,_DEPTH) (ston_dht_units(_HT,_DEPTH) * (_HT)->header.unit_bytes) +#define ston_dht_new(_COL,_ALOC,_FRE) (ston_dht_create(_COL,3,sizeof(int),_ALOC,_FRE)) +#define ston_dht_sized(_COL,_N,_ALOC,_FRE) (ston_dht_create(_COL,ston_trailing0(ston_up2pow(_N),sizeof(int),_ALOC,_FRE))) +#define ston_dht32_entry(_HT,_KEY,_COL) (ston_dht32_row(_HT,_KEY) + _COL) +#define ston_dht32_new(_COL,_ALOC,_FRE) (ston_dht_create(_COL,0,sizeof(uint32_t),_ALOC,_FRE)) +#define ston_dht32_sized(_COL,_N,_ALOC,_FRE) (ston_dht_create(_COL,ston_trailing0(ston_up2pow(_N)),sizeof(uint32_t),_ALOC,_FRE)) -#define ston_dht32_new(_COL,_N,_F,_ALLOC,_FREE) (ston_dht32_create((ston_ht_h){_COL,ston_trailing0(ston_up2pow(_N << 1)),_F},_ALLOC,_FREE)) -#define ston_dht32_entry(_HT,_KEY,_COL) (ston_dht32_row(_HT,_KEY) + _COL) -#define ston_dht_size(_HT) (ston_ht_size(_HT)) -#define ston_dht_rows(_HT) (ston_ht_rows(_HT)) -#define ston_dht_cols(_HT) (ston_ht_cols(_HT)) -#define ston_dht_keyrow(_HT,_KEY) (ston_ht_keyrow(_HT,_KEY)) -#define ston_dht_pagestart(_HT) ((void**)(((uint8_t*)(_HT)) + STON_DHT_HEADERSIZE)) -#define ston_dht_pagehead(_HT) ((_HT)->page_head) -#define ston_dht_pagemax(_HT) ((void**)((uint8_t*)(_HT) + STON_DHT_SIZE - sizeof(void**))) -#define ston_dht_start(_HT,_DEPTH) ((uint8_t*)*(ston_dht_pagestart(_HT) + _DEPTH)) -#define ston_dht32_start(_HT,_DEPTH) ((uint32_t*)ston_dht_start(_HT,_DEPTH)) -#define ston_dht32_end(_HT,_DEPTH) (ston_ht32_start(_HT,_DEPTH) + ston_ht_size(_HT)) -#define ston_dht32_size(_HT) (ston_dht_size(_HT) * sizeof(uint32_t)) -#define ston_dht32_pagepush(_HT) ((*(++((_HT)->page_head)) = (_HT)->ht_alloc(ston_dht32_size(_HT)))) -#define ston_dht32_pagepop(_HT) ((_HT)->ht_free((_HT)->page_head--)) /* Creates a new bucketted hash table, provided a memory allocation function that takes a single size_t bytes, a memory free function, a column count, and a row count which determines the size of the buckets. */ STON_FUNC -ston_dht ston_dht32_create -( struct ston_ht_header_t ht_header, - void* (*ht_alloc)(size_t), - void (*ht_free)(void*) +ston_dht ston_dht_create +( uint16_t columns, + uint8_t start_depth, + uint8_t unit_bytes, + void* (*ht_alloc)(size_t), + void (*ht_free)(void*) ) -{ size_t ht_bytes = ston_dht32_size(&ht_header); - ston_dht ht = (ston_dht) ht_alloc(STON_DHT_SIZE); +{ ston_dht ht = (ston_dht) ht_alloc(sizeof(struct ston_dht_t)); if (ht != NULL) - { memcpy(ht, &ht_header, sizeof(ht_header)); + { ht->header.columns = columns; + ht->header.start_depth = start_depth; + ht->header.unit_bytes = unit_bytes; + memset(ht->pages, 0, sizeof(void*) * sizeof(void*) * 8); + ht->pages[start_depth] = ht_alloc(ston_dht_bytes(ht, start_depth)); ht->ht_alloc = ht_alloc; ht->ht_free = ht_free; - ht->page_head = ston_dht_pagestart(ht); - if ((*(ht->page_head) = ht->ht_alloc(ht_bytes)) == NULL) - if (ht_free != NULL) - ht_free(ht); + if (ht->pages[start_depth] == NULL && ht_free != NULL) + ht_free(ht); + else + memset(ht->pages[start_depth], 0, ston_dht_bytes(ht, start_depth)); } return ht; } @@ -330,68 +335,42 @@ ston_dht ston_dht32_create */ STON_FUNC uint32_t* ston_dht32_row -( struct ston_dht_header_t* ht, - uint32_t key +( struct ston_dht_t* ht, + uint32_t key ) -{ uint16_t ht_cols = ston_dht_cols(ht); - size_t row_number = ston_dht_keyrow(ht,key); - uint32_t** page = (uint32_t**)ston_dht_pagestart(ht); - uint32_t** pagemax = (uint32_t**)ston_dht_pagemax(ht); - uint8_t loop_x = 0; - uint8_t loop_y = 0; - uint32_t* row,* row_end; +{ uint16_t columns = ht->header.columns; + uint8_t depth = ht->header.start_depth; + uint32_t mask = ((0x1 << depth) - 1) >> 1; + void* page; + uint32_t* row; + uint32_t row_key; next_page: - row = *page + (row_number * ht_cols); - row_end = *page + (ston_dht_size(ht) - 1); - next_row: - if (row[0] != 0) - goto populated; - write_position: - row[0] = key; - return row; - populated: - if (row[0] == key) - goto write_position; - if (!loop_x) - { if (page < pagemax) - { if (page == (uint32_t**)ston_dht_pagehead(ht)) - if (ston_dht32_pagepush(ht) == NULL) - { ston_dht32_free(ht); - return NULL; - } - ++page; - goto next_row; - } - loop_x = 1; - row_number = (row_number + 1) % ston_dht_rows(ht); - page = (uint32_t**)ston_dht_pagestart(ht); - goto next_row; - } - if (row + ht_cols < row_end) - { row += ht_cols; - goto next_row; - } - else if (!loop_y) - { loop_y = 1; - row = *page; - goto next_row; + if (ht->pages[depth] == NULL) + { ht->pages[depth] = ht->ht_alloc(ston_dht_bytes(ht, depth)); + if (ht->pages[depth] == NULL) + return NULL; + memset(ht->pages[depth], 0, ston_dht_bytes(ht, depth)); } - if (page < pagemax) - { loop_y = 0; - page++; - goto next_page; + page = ht->pages[depth]; + row = (uint32_t*)page + ((key & mask) * columns); + row_key = *row; + if (row_key == key || row_key == 0) + { row[0] = key; + return row; } - return NULL; + depth++; + mask = (mask << 1) | 0x1; + goto next_page; } /* Inserts a value into a hashtable at the specified column, returning the previous value */ STON_FUNC uint32_t ston_dht32_insert -( struct ston_dht_header_t* ht, - uint32_t key, - uint16_t column, - uint32_t value +( struct ston_dht_t* ht, + uint32_t key, + uint16_t column, + uint32_t value ) { uint32_t* value_location, old_value; value_location = ston_dht32_entry(ht,key,column); @@ -400,34 +379,18 @@ uint32_t ston_dht32_insert return old_value; } -/* Free the dynamic hash table */ -STON_FUNC -struct ston_dht_header_t* ston_dht32_free -( struct ston_dht_header_t* ht ) -{ void (*ht_free)(void*) = ht->ht_free; - if (ht_free != NULL) - { while (ht->page_head >= ston_dht_pagestart(ht)) - { ht_free(*(ht->page_head)); - ht->page_head--; - } - ht_free(ht); - return NULL; - } - return ht; -} - /* Insert multiple values, returning the number of bytes written */ STON_FUNC size_t ston_dht32_insertx -( struct ston_dht_header_t* ht, - uint32_t key, - uint32_t* data_src, - size_t start_column, - size_t units +( struct ston_dht_t* ht, + uint32_t key, + uint32_t* data_src, + uint16_t start_column, + size_t units ) { uint32_t* data_row = ston_dht32_row(ht,key); - uint32_t* data_limit = data_row + ston_dht_cols(ht); + uint32_t* data_limit = data_row + ht->header.columns; uint32_t* data_trg = data_row + start_column; if (data_row == NULL) return 0; @@ -436,5 +399,21 @@ ston_dht32_insertx return (size_t)(data_trg - data_row); } +/* Free the dynamic hash table */ +STON_FUNC +struct ston_dht_t* ston_dht_free +( struct ston_dht_t* ht ) +{ void (*ht_free)(void*) = ht->ht_free; + uint8_t depth = ht->header.start_depth; + void** pages = ht->pages; + if (ht_free != NULL) + { while (pages[depth] != NULL) + ht_free(pages[depth++]); + ht_free(ht); + return NULL; + } + return ht; +} + #endif //_STON_HT_H_ -- 2.18.0