From da76459dc21b5af2449af2d36eb95226cb186ce2 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 28 Apr 2024 11:35:11 +0200 Subject: Adding upstream version 2.6.12. Signed-off-by: Daniel Baumann --- tests/exp/blocksig.c | 16 ++ tests/exp/filltab25.c | 399 ++++++++++++++++++++++++++++++ tests/exp/hash_results.txt | 218 ++++++++++++++++ tests/exp/hashing-results.txt | 314 ++++++++++++++++++++++++ tests/exp/io_limits.txt | 116 +++++++++ tests/exp/ip-hash.c | 202 +++++++++++++++ tests/exp/test_hashes.c | 559 ++++++++++++++++++++++++++++++++++++++++++ tests/exp/testinet.c | 28 +++ tests/exp/uri_hash.c | 377 ++++++++++++++++++++++++++++ 9 files changed, 2229 insertions(+) create mode 100644 tests/exp/blocksig.c create mode 100644 tests/exp/filltab25.c create mode 100644 tests/exp/hash_results.txt create mode 100644 tests/exp/hashing-results.txt create mode 100644 tests/exp/io_limits.txt create mode 100644 tests/exp/ip-hash.c create mode 100644 tests/exp/test_hashes.c create mode 100644 tests/exp/testinet.c create mode 100644 tests/exp/uri_hash.c (limited to 'tests/exp') diff --git a/tests/exp/blocksig.c b/tests/exp/blocksig.c new file mode 100644 index 0000000..13b55e7 --- /dev/null +++ b/tests/exp/blocksig.c @@ -0,0 +1,16 @@ +#include +#include +#include + +int main(int argc, char **argv) +{ + sigset_t new_sig, old_sig; + + sigfillset(&new_sig); + sigprocmask(SIG_SETMASK, &new_sig, &old_sig); + printf("old_sig: %16Lx\n", *(unsigned long long*)&old_sig); + printf("new_sig: %16Lx\n", *(unsigned long long*)&new_sig); + + argc--; argv++; + return argc ? execvp(*argv, argv) : 0; +} diff --git a/tests/exp/filltab25.c b/tests/exp/filltab25.c new file mode 100644 index 0000000..1197143 --- /dev/null +++ b/tests/exp/filltab25.c @@ -0,0 +1,399 @@ +/* + * experimental weighted round robin scheduler - (c) 2007 willy tarreau. + * + * This filling algorithm is excellent at spreading the servers, as it also + * takes care of keeping the most uniform distance between occurrences of each + * server, by maximizing this distance. It reduces the number of variables + * and expensive operations. + */ + +#include +#include +#include + +struct srv { + struct eb32_node node; + struct eb_root *tree; // we want to know where the server is + int num; + int w; /* weight */ + int next, last; + int rem; +} *srv; + +/* those trees represent a sliding window of 3 time frames */ +struct eb_root tree_0 = EB_ROOT; +struct eb_root tree_1 = EB_ROOT; +struct eb_root tree_2 = EB_ROOT; + +struct eb_root *init_tree; /* receives positions 0..sw-1 */ +struct eb_root *next_tree; /* receives positions >= 2sw */ + +int nsrv; /* # of servers */ +int nsw, sw; /* sum of weights */ +int p; /* current position, between sw..2sw-1 */ + +/* queue a server in the weights tree */ +void queue_by_weight(struct eb_root *root, struct srv *s) { + s->node.key = 255 - s->w; + eb32_insert(root, &s->node); + s->tree = root; +} + +/* queue a server in the weight tree , except if its weight is 0 */ +void queue_by_weight_0(struct eb_root *root, struct srv *s) { + if (s->w) { + s->node.key = 255 - s->w; + eb32_insert(root, &s->node); + s->tree = root; + } else { + s->tree = NULL; + } +} + +static inline void dequeue_srv(struct srv *s) { + eb32_delete(&s->node); +} + +/* queues a server into the correct tree depending on ->next */ +void put_srv(struct srv *s) { + if (s->w <= 0 || + s->next >= 2*sw || /* delay everything which does not fit into the window */ + s->next >= sw+nsw) { /* and everything which does not fit into the theoretical new window */ + /* put into next tree */ + s->next -= sw; // readjust next in case we could finally take this back to current. + queue_by_weight_0(next_tree, s); + } else { + // The overflow problem is caused by the scale we want to apply to user weight + // to turn it into effective weight. Since this is only used to provide a smooth + // slowstart on very low weights (1), it is a pure waste. Thus, we just have to + // apply a small scaling factor and warn the user that slowstart is not very smooth + // on low weights. + // The max key is about ((scale*maxw)*(scale*maxw)*nbsrv)/ratio (where the ratio is + // the arbitrary divide we perform in the examples above). Assuming that ratio==scale, + // this translates to maxkey=scale*maxw^2*nbsrv, so + // max_nbsrv=2^32/255^2/scale ~= 66051/scale + // Using a scale of 16 is enough to support 4000 servers without overflow, providing + // 6% steps during slowstart. + + s->node.key = 256 * s->next + (16*255 + s->rem - s->w) / 16; + + /* check for overflows */ + if ((int)s->node.key < 0) + printf(" OV: srv=%p w=%d rem=%d next=%d key=%d", s, s->w, s->rem, s->next, s->node.key); + eb32_insert(&tree_0, &s->node); + s->tree = &tree_0; + } +} + +/* prepares a server when extracting it from the init tree */ +static inline void get_srv_init(struct srv *s) { + s->next = s->rem = 0; +} + +/* prepares a server when extracting it from the next tree */ +static inline void get_srv_next(struct srv *s) { + s->next += sw; +} + +/* prepares a server when extracting it from the next tree */ +static inline void get_srv_down(struct srv *s) { + s->next = p; +} + +/* prepares a server when extracting it from its tree */ +void get_srv(struct srv *s) { + if (s->tree == init_tree) { + get_srv_init(s); + } + else if (s->tree == next_tree) { + get_srv_next(s); + } + else if (s->tree == NULL) { + get_srv_down(s); + } +} + + +/* return next server from the current tree, or a server from the init tree + * if appropriate. If both trees are empty, return NULL. + */ +struct srv *get_next_server() { + struct eb32_node *node; + struct srv *s; + + node = eb32_first(&tree_0); + s = eb32_entry(node, struct srv, node); + + if (!node || s->next > p) { + /* either we have no server left, or we have a hole */ + struct eb32_node *node2; + node2 = eb32_first(init_tree); + if (node2) { + node = node2; + s = eb32_entry(node, struct srv, node); + get_srv_init(s); + if (s->w == 0) + node = NULL; + s->node.key = 0; // do not display random values + } + } + if (node) + return s; + else + return NULL; +} + +void update_position(struct srv *s) { + //if (s->tree == init_tree) { + if (!s->next) { + // first time ever for this server + s->last = p; + s->next = p + nsw / s->w; + s->rem += nsw % s->w; + + if (s->rem >= s->w) { + s->rem -= s->w; + s->next++; + } + } else { + s->last = s->next; // or p ? + //s->next += sw / s->w; + //s->rem += sw % s->w; + s->next += nsw / s->w; + s->rem += nsw % s->w; + + if (s->rem >= s->w) { + s->rem -= s->w; + s->next++; + } + } +} + + +/* switches trees init_tree and next_tree. init_tree should be empty when + * this happens, and next_tree filled with servers sorted by weights. + */ +void switch_trees() { + struct eb_root *swap; + swap = init_tree; + init_tree = next_tree; + next_tree = swap; + sw = nsw; + p = sw; +} + +main(int argc, char **argv) { + int conns; + int i; + + struct srv *s; + + argc--; argv++; + nsrv = argc; + + if (!nsrv) + exit(1); + + srv = calloc(nsrv, sizeof(struct srv)); + + sw = 0; + for (i = 0; i < nsrv; i++) { + s = &srv[i]; + s->num = i; + s->w = atol(argv[i]); + sw += s->w; + } + + nsw = sw; + + init_tree = &tree_1; + next_tree = &tree_2; + + /* and insert all the servers in the PREV tree */ + /* note that it is required to insert them according to + * the reverse order of their weights. + */ + printf("---------------:"); + for (i = 0; i < nsrv; i++) { + s = &srv[i]; + queue_by_weight_0(init_tree, s); + printf("%2d", s->w); + } + printf("\n"); + + p = sw; // time base of current tree + conns = 0; + while (1) { + struct eb32_node *node; + + printf("%08d|%06d: ", conns, p); + + /* if we have en empty tree, let's first try to collect weights + * which might have changed. + */ + if (!sw) { + if (nsw) { + sw = nsw; + p = sw; + /* do not switch trees, otherwise new servers (from init) + * would end up in next. + */ + //switch_trees(); + //printf("bla\n"); + } + else + goto next_iteration; + } + + s = get_next_server(); + if (!s) { + printf("----------- switch (empty) -- sw=%d -> %d ---------\n", sw, nsw); + switch_trees(); + s = get_next_server(); + printf("%08d|%06d: ", conns, p); + + if (!s) + goto next_iteration; + } + else if (s->next >= 2*sw) { + printf("ARGGGGG! s[%d].next=%d, max=%d\n", s->num, s->next, 2*sw-1); + } + + /* now we have THE server we want to put at this position */ + for (i = 0; i < s->num; i++) { + if (srv[i].w > 0) + printf(". "); + else + printf("_ "); + } + printf("# "); + for (i = s->num + 1; i < nsrv; i++) { + if (srv[i].w > 0) + printf(". "); + else + printf("_ "); + } + printf(" : "); + + printf("s=%02d v=%04d w=%03d n=%03d r=%03d ", + s->num, s->node.key, s->w, s->next, s->rem); + + update_position(s); + printf(" | next=%03d, rem=%03d ", s->next, s->rem); + + if (s->next >= sw * 2) { + dequeue_srv(s); + //queue_by_weight(next_tree, s); + put_srv(s); + printf(" => next (w=%d, n=%d) ", s->w, s->next); + } + else { + printf(" => curr "); + + //s->node.key = s->next; + /* we want to ensure that in case of conflicts, servers with + * the highest weights will get served first. Also, we still + * have the remainder to see where the entry expected to be + * inserted. + */ + //s->node.key = 256 * s->next + 255 - s->w; + //s->node.key = sw * s->next + sw / s->w; + //s->node.key = sw * s->next + s->rem; /// seems best (check with filltab15) ! + + //s->node.key = (2 * sw * s->next) + s->rem + sw / s->w; + + /* FIXME: must be optimized */ + dequeue_srv(s); + put_srv(s); + //eb32i_insert(&tree_0, &s->node); + //s->tree = &tree_0; + } + + next_iteration: + p++; + conns++; + if (/*conns == 30*/ /**/random()%100 == 0/**/) { + int w = /*20*//**/random()%4096/**/; + int num = /*1*//**/random()%nsrv/**/; + struct srv *s = &srv[num]; + + nsw = nsw - s->w + w; + //sw=nsw; + + if (s->tree == init_tree) { + printf(" -- chgwght1(%d): %d->%d, n=%d --", s->num, s->w, w, s->next); + printf("(init)"); + s->w = w; + dequeue_srv(s); + queue_by_weight_0(s->tree, s); + } + else if (s->tree == NULL) { + printf(" -- chgwght2(%d): %d->%d, n=%d --", s->num, s->w, w, s->next); + printf("(down)"); + s->w = w; + dequeue_srv(s); + //queue_by_weight_0(init_tree, s); + get_srv(s); + s->next = p + (nsw + sw - p) / s->w; + put_srv(s); + } + else { + int oldnext; + + /* the server is either active or in the next queue */ + get_srv(s); + printf(" -- chgwght3(%d): %d->%d, n=%d, sw=%d, nsw=%d --", s->num, s->w, w, s->next, sw, nsw); + + oldnext = s->next; + s->w = w; + + /* we must measure how far we are from the end of the current window + * and try to fit their as many entries as should theoretically be. + */ + + //s->w = s->w * (2*sw - p) / sw; + if (s->w > 0) { + int step = (nsw /*+ sw - p*/) / s->w; + s->next = s->last + step; + s->rem = 0; + if (s->next > oldnext) { + s->next = oldnext; + printf(" aaaaaaa "); + } + + if (s->next < p + 2) { + s->next = p + step; + printf(" bbbbbb "); + } + } else { + printf(" push -- "); + /* push it into the next tree */ + s->w = 0; + s->next = p + sw; + } + + + dequeue_srv(s); + printf(" n=%d", s->next); + put_srv(s); + } + } + + printf("\n"); + + if (0 && conns % 50000 == 0) { + printf("-------- %-5d : changing all weights ----\n", conns); + + for (i = 0; i < nsrv; i++) { + int w = i + 1; + s = &srv[i]; + nsw = nsw - s->w + w; + s->w = w; + dequeue_srv(s); + queue_by_weight_0(next_tree, s); // or init_tree ? + } + } + + } +} + diff --git a/tests/exp/hash_results.txt b/tests/exp/hash_results.txt new file mode 100644 index 0000000..0f14ec9 --- /dev/null +++ b/tests/exp/hash_results.txt @@ -0,0 +1,218 @@ +Test: ./test_hashes | sort -k 3 -r + +Note: haproxy_server_hash should be avoided as it's just a 32 bit XOR. + +Athlon @ 1533 MHz, gcc-3.4 -march=i686 : + haproxy_server_hash : 18477000 run/sec + SuperFastHash : 6983511 run/sec + hash_djbx33 : 4164334 run/sec + bernstein : 3371838 run/sec + kr_hash : 3257684 run/sec + sax_hash : 3027567 run/sec + fnv_hash : 2818374 run/sec + haproxy_uri_hash : 2108346 run/sec + oat_hash : 2106181 run/sec + hashword : 1936973 run/sec + hashpjw : 1803475 run/sec + fnv_32a_str : 1499198 run/sec + +Pentium-M @1700 MHz, gcc-3.4 -march=i686 : + haproxy_server_hash : 15471737 run/sec + SuperFastHash : 8155706 run/sec + hash_djbx33 : 4520191 run/sec + bernstein : 3956142 run/sec + kr_hash : 3725125 run/sec + fnv_hash : 3155413 run/sec + sax_hash : 2688323 run/sec + oat_hash : 2452789 run/sec + haproxy_uri_hash : 2010853 run/sec + hashword : 1831441 run/sec + hashpjw : 1737000 run/sec + fnv_32a_str : 1643737 run/sec + +Athlon @ 1533 MHz, gcc-4.1 -march=i686 : + haproxy_server_hash : 13592089 run/sec + SuperFastHash2 : 8687957 run/sec + SuperFastHash : 7361242 run/sec + hash_djbx33 : 5741546 run/sec + bernstein : 3368909 run/sec + sax_hash : 3339880 run/sec + kr_hash : 3277230 run/sec + fnv_hash : 2832402 run/sec + hashword : 2500317 run/sec + haproxy_uri_hash : 2433241 run/sec + oat_hash : 2403118 run/sec + hashpjw : 1881229 run/sec + fnv_32a_str : 1815709 run/sec + +Pentium-M @1700 MHz, gcc-4.1 -march=i686 : + haproxy_server_hash : 14128788 run/sec + SuperFastHash2 : 8157119 run/sec + SuperFastHash : 7481027 run/sec + hash_djbx33 : 5660711 run/sec + bernstein : 3961493 run/sec + fnv_hash : 3590727 run/sec + kr_hash : 3389393 run/sec + sax_hash : 2667227 run/sec + oat_hash : 2348211 run/sec + hashword : 2278856 run/sec + haproxy_uri_hash : 2098022 run/sec + hashpjw : 1846583 run/sec + fnv_32a_str : 1661219 run/sec + +Pentium-M @600 MHz, gcc-4.1 -march=i686 : + haproxy_server_hash : 5318468 run/sec + SuperFastHash2 : 3126165 run/sec + SuperFastHash : 2729981 run/sec + hash_djbx33 : 2042181 run/sec + bernstein : 1422927 run/sec + fnv_hash : 1287736 run/sec + kr_hash : 1217924 run/sec + sax_hash : 949694 run/sec + oat_hash : 837279 run/sec + hashword : 812868 run/sec + haproxy_uri_hash : 747611 run/sec + hashpjw : 659890 run/sec + fnv_32a_str : 590895 run/sec + +athlon @ 1.5 GHz, gcc-2.95 -march=i686 : + haproxy_server_hash : 13592864 run/sec + SuperFastHash : 6931251 run/sec + bernstein : 4105179 run/sec + hash_djbx33 : 3920059 run/sec + kr_hash : 2985794 run/sec + fnv_hash : 2815457 run/sec + sax_hash : 2791358 run/sec + haproxy_uri_hash : 2786663 run/sec + oat_hash : 2237859 run/sec + hashword : 1985740 run/sec + hashpjw : 1757733 run/sec + fnv_32a_str : 1697299 run/sec + +Pentium-M @ 600 MHz, gcc-2.95 -march=i686 : + SuperFastHash : 2934387 run/sec + haproxy_server_hash : 2864668 run/sec + hash_djbx33 : 1498043 run/sec + bernstein : 1414993 run/sec + kr_hash : 1297907 run/sec + fnv_hash : 1260343 run/sec + sax_hash : 924764 run/sec + oat_hash : 854545 run/sec + haproxy_uri_hash : 790040 run/sec + hashword : 693501 run/sec + hashpjw : 647346 run/sec + fnv_32a_str : 579691 run/sec + +Pentium-M @ 1700 MHz, gcc-2.95 -march=i686 : + SuperFastHash : 8006127 run/sec + haproxy_server_hash : 7834162 run/sec + hash_djbx33 : 4186025 run/sec + bernstein : 3941492 run/sec + kr_hash : 3630713 run/sec + fnv_hash : 3507488 run/sec + sax_hash : 2528128 run/sec + oat_hash : 2395188 run/sec + haproxy_uri_hash : 2158924 run/sec + hashword : 1910992 run/sec + hashpjw : 1819894 run/sec + fnv_32a_str : 1629844 run/sec + +UltraSparc @ 400 MHz, gcc-3.4.3 : + haproxy_server_hash : 5573220 run/sec + SuperFastHash : 1372714 run/sec + bernstein : 1361733 run/sec + hash_djbx33 : 1090373 run/sec + sax_hash : 872499 run/sec + oat_hash : 730354 run/sec + kr_hash : 645431 run/sec + haproxy_uri_hash : 541157 run/sec + fnv_32a_str : 442608 run/sec + hashpjw : 434858 run/sec + fnv_hash : 401945 run/sec + hashword : 340594 run/sec + +UltraSparc @ 400 MHz, gcc-3.4.3 -mcpu=v9 : + haproxy_server_hash : 5671183 run/sec + bernstein : 1437122 run/sec + hash_djbx33 : 1376294 run/sec + SuperFastHash : 1306634 run/sec + sax_hash : 873650 run/sec + kr_hash : 801439 run/sec + oat_hash : 729920 run/sec + haproxy_uri_hash : 545341 run/sec + hashpjw : 472190 run/sec + fnv_32a_str : 443668 run/sec + hashword : 357295 run/sec + fnv_hash : 208823 run/sec + + +Alpha EV6 @ 466 MHz, gcc-3.3 : + haproxy_server_hash : 2495928 run/sec + SuperFastHash : 2037208 run/sec + hash_djbx33 : 1625092 run/sec + kr_hash : 1532206 run/sec + bernstein : 1256746 run/sec + haproxy_uri_hash : 999106 run/sec + oat_hash : 841943 run/sec + sax_hash : 737447 run/sec + hashpjw : 676170 run/sec + fnv_hash : 644054 run/sec + fnv_32a_str : 638526 run/sec + hashword : 421777 run/sec + +VIA EPIA @ 533 MHz, gcc-2.95 -march=i586 : + haproxy_server_hash : 1391374 run/sec + SuperFastHash : 912397 run/sec + hash_djbx33 : 589868 run/sec + kr_hash : 453706 run/sec + bernstein : 437318 run/sec + sax_hash : 334456 run/sec + hashpjw : 316670 run/sec + hashword : 315476 run/sec + haproxy_uri_hash : 311112 run/sec + oat_hash : 259127 run/sec + fnv_32a_str : 229485 run/sec + fnv_hash : 151620 run/sec + +VIA EPIA @ 533 MHz, gcc-3.4 -march=i586 : + haproxy_server_hash : 1660407 run/sec + SuperFastHash : 791981 run/sec + hash_djbx33 : 680498 run/sec + kr_hash : 384076 run/sec + bernstein : 377247 run/sec + sax_hash : 355183 run/sec + hashpjw : 298879 run/sec + haproxy_uri_hash : 296748 run/sec + oat_hash : 283932 run/sec + hashword : 269429 run/sec + fnv_32a_str : 204776 run/sec + fnv_hash : 155301 run/sec + +Pentium @ 133 MHz, gcc-3.4 -march=i586 : + haproxy_server_hash : 930788 run/sec + SuperFastHash : 344988 run/sec + hash_djbx33 : 278996 run/sec + bernstein : 211545 run/sec + sax_hash : 185225 run/sec + kr_hash : 156603 run/sec + oat_hash : 135163 run/sec + hashword : 128518 run/sec + fnv_hash : 107024 run/sec + haproxy_uri_hash : 105523 run/sec + fnv_32a_str : 99913 run/sec + hashpjw : 97860 run/sec + +VAX VLC4000 @30 MHz, gcc-2.95 : + haproxy_server_hash : 13208 run/sec + hash_djbx33 : 12963 run/sec + fnv_hash : 12150 run/sec + SuperFastHash : 12037 run/sec + bernstein : 11765 run/sec + kr_hash : 11111 run/sec + sax_hash : 7273 run/sec + hashword : 7143 run/sec + oat_hash : 6931 run/sec + hashpjw : 6667 run/sec + haproxy_uri_hash : 5714 run/sec + fnv_32a_str : 4800 run/sec + diff --git a/tests/exp/hashing-results.txt b/tests/exp/hashing-results.txt new file mode 100644 index 0000000..d2dbf59 --- /dev/null +++ b/tests/exp/hashing-results.txt @@ -0,0 +1,314 @@ +These are the result of tests conducted to determine efficacy of hashing +algorithms and avalache application in haproxy. All results below were +generated using version 1.5. See the document on hashing under internal docs +for a detailed description on the tests the methodology and interpretation +of the results. + +The following was the set up used + +(a) hash-type consistent/map-bases +(b) avalanche on/off +(c) balanche host(hdr) +(d) 3 criteria for inputs + - ~ 10K requests, including duplicates + - ~ 46K requests, unique requests from 1 MM requests were obtained + - ~ 250K requests, including duplicates +(e) 17 servers in backend, all servers were assigned the same weight + +The results can be interpreted across 3 dimensions corresponding to input +criteria (a)/(b) and (d) above + +== 10 K requests == + +=== Consistent with avalanche === + +Servers SDBM DJB2 WT6 +----------------------------- +1 576 637 592 +2 552 608 600 +3 539 559 551 +4 578 586 493 +5 534 555 549 +6 614 607 576 +7 519 556 554 +8 591 565 607 +9 529 604 575 +10 642 550 678 +11 537 591 506 +12 568 571 567 +13 589 606 572 +14 648 568 711 +15 645 557 603 +16 583 627 591 +17 699 596 618 +----------------------------- +Std Dev 48.95 26.29 51.75 + +=== Consistent without avalanche === + +Servers SDBM DJB2 WT6 +----------------------------- +1 612 627 579 +2 631 607 563 +3 585 605 604 +4 594 502 518 +5 583 526 602 +6 589 594 555 +7 591 602 511 +8 518 540 623 +9 550 519 523 +10 600 637 647 +11 568 536 550 +12 552 605 645 +13 547 556 564 +14 615 674 635 +15 642 624 618 +16 575 585 609 +17 591 604 597 +----------------------------- +Std Dev 30.71 45.97 42.52 + +=== Map based without avalanche === + +Servers SDBM DJB2 WT6 +----------------------------- +1 602 560 598 +2 576 583 583 +3 579 624 593 +4 608 587 551 +5 579 549 588 +6 582 560 590 +7 553 616 562 +8 568 600 551 +9 594 607 620 +10 574 611 635 +11 578 607 603 +12 563 581 547 +13 604 531 572 +14 621 606 618 +15 600 561 602 +16 555 570 585 +17 607 590 545 +----------------------------- +Std Dev 19.24 25.56 26.29 + +=== Map based with avalanche === + +Servers SDBM DJB2 WT6 +----------------------------- +Servers SDBM DJB2 WT6 +1 548 641 597 +2 612 563 655 +3 596 536 595 +4 609 574 537 +5 586 610 570 +6 600 568 562 +7 589 573 578 +8 584 549 573 +9 561 636 603 +10 607 553 603 +11 554 602 616 +12 560 577 568 +13 597 534 570 +14 597 647 570 +15 563 581 647 +16 575 647 565 +17 605 552 534 +----------------------------- +Std Dev 20.23 37.47 32.16 + +== Uniques in 1 MM == + +=== Consistent with avalanche === + +Servers SDBM DJB2 WT6 +----------------------------- +1 2891 2963 2947 +2 2802 2849 2771 +3 2824 2854 2904 +4 2704 2740 2763 +5 2664 2699 2646 +6 2902 2876 2935 +7 2829 2745 2730 +8 2648 2768 2800 +9 2710 2741 2689 +10 3070 3111 3106 +11 2733 2638 2589 +12 2828 2866 2885 +13 2876 2961 2870 +14 3090 2997 3044 +15 2871 2879 2827 +16 2881 2727 2921 +17 2936 2845 2832 +----------------------------- +Std Dev 121.66 118.59 131.61 + +=== Consistent without avalanche === + +Servers SDBM DJB2 WT6 +----------------------------- +1 2879 2930 2863 +2 2835 2856 2853 +3 2875 2741 2899 +4 2720 2718 2761 +5 2703 2754 2689 +6 2848 2901 2925 +7 2829 2756 2838 +8 2761 2779 2805 +9 2719 2671 2746 +10 3015 3176 3079 +11 2620 2661 2656 +12 2879 2773 2713 +13 2829 2844 2925 +14 3064 2951 3041 +15 2898 2928 2877 +16 2880 2867 2791 +17 2905 2953 2798 +----------------------------- +Std Dev 107.65 125.2 111.34 + +=== Map based without avalanche === + +Servers SDBM DJB2 WT6 +----------------------------- +1 2863 2837 2923 +2 2966 2829 2847 +3 2865 2803 2808 +4 2682 2816 2787 +5 2847 2782 2815 +6 2910 2862 2862 +7 2821 2784 2793 +8 2837 2834 2796 +9 2857 2891 2859 +10 2829 2906 2873 +11 2742 2851 2841 +12 2790 2837 2870 +13 2765 2902 2794 +14 2870 2732 2900 +15 2898 2891 2759 +16 2877 2860 2863 +17 2840 2842 2869 +----------------------------- +Std Dev 64.65 45.16 43.38 + +=== Map based with avalanche === + +Servers SDBM DJB2 WT6 +----------------------------- +1 2816 2859 2895 +2 2841 2739 2789 +3 2846 2903 2888 +4 2817 2878 2812 +5 2750 2794 2852 +6 2816 2917 2847 +7 2792 2782 2786 +8 2800 2814 2868 +9 2854 2883 2842 +10 2770 2854 2855 +11 2851 2854 2837 +12 2910 2846 2776 +13 2904 2792 2882 +14 2984 2767 2854 +15 2766 2863 2823 +16 2902 2797 2907 +17 2840 2917 2746 +----------------------------- +Std Dev 58.39 52.16 43.72 + +== 250K requests == + +=== Consistent with avalanche === + +Servers SDBM DJB2 WT6 +----------------------------- +1 14182 12996 20924 +2 14881 18376 8901 +3 13537 17935 13639 +4 11031 12582 19758 +5 15429 10084 12112 +6 18712 12574 14052 +7 14271 11257 14538 +8 12048 18582 16653 +9 10570 10283 13949 +10 11683 13081 23530 +11 9288 14828 10818 +12 10775 13607 19844 +13 10036 19138 15413 +14 31903 15222 11824 +15 21276 11963 10405 +16 17233 23116 11316 +17 11437 12668 10616 +----------------------------- +Std Dev 5355.95 3512.39 4096.65 + +=== Consistent without avalanche === + +Servers SDBM DJB2 WT6 +----------------------------- +1 12411 17833 11831 +2 14213 11165 14833 +3 11431 10241 11671 +4 14080 13913 20224 +5 10886 12101 14272 +6 15168 12470 14641 +7 18802 12211 10164 +8 18678 11852 12421 +9 17468 10865 17655 +10 19801 28493 13221 +11 10885 20201 13507 +12 20419 11660 14078 +13 12591 18616 13906 +14 12798 18200 24152 +15 13338 10532 14111 +16 11715 10478 14759 +17 13608 17461 12846 +----------------------------- +Std Dev 3113.33 4749.97 3256.04 + +=== Map based without avalanche === + +Servers SDBM DJB2 WT6 +----------------------------- +1 14660 12483 11472 +2 11118 11552 12146 +3 15407 19952 11032 +4 15444 12218 14572 +5 22091 11434 13738 +6 18273 17587 21337 +7 10527 16784 15118 +8 13013 12010 17195 +9 15754 9886 14611 +10 13758 11613 14844 +11 19564 16453 17403 +12 9692 17246 14469 +13 13905 11885 20024 +14 19401 15350 10611 +15 11889 25485 11172 +16 13846 13928 12109 +17 9950 12426 16439 +----------------------------- +Std Dev 3481.45 3847.74 3031.93 + +=== Map based with avalanche === + +Servers SDBM DJB2 WT6 +----------------------------- +1 15546 11454 12871 +2 15388 11464 17587 +3 11767 15527 14785 +4 15843 13214 11420 +5 11129 12192 15083 +6 15647 17875 11051 +7 18723 13629 23006 +8 10938 11295 11223 +9 12653 17202 23347 +10 10108 12867 14178 +11 12116 11190 20523 +12 14982 12341 11881 +13 13221 13929 11828 +14 17642 19621 15320 +15 12410 26171 11721 +16 25075 14764 13544 +17 15104 13557 8924 +----------------------------- +Std Dev 3521.83 3742.21 4101.2 diff --git a/tests/exp/io_limits.txt b/tests/exp/io_limits.txt new file mode 100644 index 0000000..03399bc --- /dev/null +++ b/tests/exp/io_limits.txt @@ -0,0 +1,116 @@ +---------- epoll without limits -------- +% time seconds usecs/call calls errors syscall +------ ----------- ----------- --------- --------- ---------------- + 47.19 2.671077 56 48093 22397 recv + 47.15 2.668840 106 25060 4858 send + 2.19 0.124020 10 12150 epoll_ctl + 1.96 0.110904 286 388 epoll_wait + 0.56 0.031565 47 670 close + 0.19 0.010481 28 380 350 connect + 0.15 0.008650 25 350 socket + 0.14 0.008204 26 320 shutdown + 0.14 0.007655 22 355 35 accept + 0.12 0.006871 10 670 setsockopt + 0.11 0.006194 9 670 fcntl64 + 0.07 0.004148 12 355 brk + 0.04 0.002055 5 389 gettimeofday +------ ----------- ----------- --------- --------- ---------------- +100.00 5.660664 89850 27640 total + + +---------- sepoll without limit -------- +% time seconds usecs/call calls errors syscall +------ ----------- ----------- --------- --------- ---------------- + 49.43 2.770682 97 28486 3861 send + 46.48 2.605336 53 49317 23434 recv + 2.00 0.111916 206 542 epoll_wait + 0.65 0.036325 12 3030 epoll_ctl + 0.45 0.025282 38 670 close + 0.24 0.013247 34 388 358 connect + 0.17 0.009544 27 350 socket + 0.16 0.008734 27 320 shutdown + 0.11 0.006432 18 357 37 accept + 0.10 0.005699 9 670 setsockopt + 0.08 0.004724 7 670 fcntl64 + 0.08 0.004568 6 767 gettimeofday + 0.06 0.003127 9 356 brk +------ ----------- ----------- --------- --------- ---------------- +100.00 5.605616 85923 27690 total + + +---------- sepoll with send limit only -------- +% time seconds usecs/call calls errors syscall +------ ----------- ----------- --------- --------- ---------------- + 49.21 2.779349 109 25417 418 send + 46.94 2.651058 54 49150 23368 recv + 1.77 0.099863 264 378 epoll_wait + 0.57 0.032141 14 2351 epoll_ctl + 0.46 0.025822 39 670 close + 0.25 0.014300 37 387 357 connect + 0.19 0.010530 30 350 socket + 0.15 0.008656 27 320 shutdown + 0.14 0.008008 23 354 34 accept + 0.11 0.006051 9 670 setsockopt + 0.10 0.005461 8 670 fcntl64 + 0.07 0.003842 6 604 gettimeofday + 0.06 0.003120 9 358 brk +------ ----------- ----------- --------- --------- ---------------- +100.00 5.648201 81679 24177 total + + +---------- sepoll with send + recv limits -------- +Process 3173 attached - interrupt to quit +Process 3173 detached +% time seconds usecs/call calls errors syscall +------ ----------- ----------- --------- --------- ---------------- + 49.09 2.802918 105 26771 596 send + 47.72 2.724651 89 30761 728 recv + 1.12 0.063952 55 1169 epoll_wait + 0.47 0.026810 40 676 close + 0.44 0.025358 11 2329 epoll_ctl + 0.21 0.012255 30 403 367 connect + 0.20 0.011135 35 320 shutdown + 0.18 0.010313 29 356 socket + 0.15 0.008614 6 1351 gettimeofday + 0.13 0.007678 21 360 40 accept + 0.13 0.007218 11 676 setsockopt + 0.10 0.005559 8 676 fcntl64 + 0.05 0.002882 9 327 brk +------ ----------- ----------- --------- --------- ---------------- +100.00 5.709343 66175 1731 total + +---------- epoll with send+recv limits ----------- +Process 3271 attached - interrupt to quit +Process 3271 detached +% time seconds usecs/call calls errors syscall +------ ----------- ----------- --------- --------- ---------------- + 46.96 2.742476 124 22193 send + 46.55 2.718027 98 27730 recv + 2.58 0.150701 11 13331 epoll_ctl + 2.30 0.134350 135 998 epoll_wait + 0.52 0.030520 45 673 close + 0.23 0.013422 42 320 shutdown + 0.19 0.011282 29 386 353 connect + 0.19 0.011063 31 353 socket + 0.12 0.007039 20 359 39 accept + 0.11 0.006629 10 673 fcntl64 + 0.10 0.005920 9 673 setsockopt + 0.09 0.005157 5 999 gettimeofday + 0.05 0.002885 9 335 brk +------ ----------- ----------- --------- --------- ---------------- +100.00 5.839471 69023 392 total + + +Conclusion +---------- +epoll = 89850 syscalls +sepoll = 85923 syscalls +epoll+limits = 69023 syscalls +sepoll+limits = 66175 syscalls + +=> limits reduce the number of syscalls by 23% +=> sepoll reduces the number of syscalls by 4% +=> sepoll reduces the number of epoll_ctl by 83% +=> limits reduce the number of epoll_ctl by 24% +=> limits increase the number of epoll_wait by 115% + diff --git a/tests/exp/ip-hash.c b/tests/exp/ip-hash.c new file mode 100644 index 0000000..8bb2d48 --- /dev/null +++ b/tests/exp/ip-hash.c @@ -0,0 +1,202 @@ +/* + * Integer hashing tests. These functions work with 32-bit integers, so are + * perfectly suited for IPv4 addresses. A few tests show that they may also + * be chained for larger keys (eg: IPv6), this way : + * f(x[0-3]) = f(f(f(f(x[0])^x[1])^x[2])^x[3]) + * + * See also bob jenkin's site for more info on hashing, and check perfect + * hashing for constants (eg: header names). + */ + +#include +#include +#include +#include + +#define NSERV 8 +#define MAXLINE 1000 + + +int counts_id[NSERV][NSERV]; +uint32_t hash_id( uint32_t a) +{ + return a; +} + +/* Full-avalanche integer hashing function from Thomas Wang, suitable for use + * with a modulo. See below, worth a read ! + * http://www.concentric.net/~Ttwang/tech/inthash.htm + * + * See also tests performed by Bob Jenkins (says it's faster than his) : + * http://burtleburtle.net/bob/hash/integer.html + * + * This function is small and fast. It does not seem as smooth as bj6 though. + * About 0x40 bytes, 6 shifts. + */ +int counts_tw1[NSERV][NSERV]; +uint32_t hash_tw1(uint32_t a) +{ + a += ~(a<<15); + a ^= (a>>10); + a += (a<<3); + a ^= (a>>6); + a += ~(a<<11); + a ^= (a>>16); + return a; +} + +/* Thomas Wang's mix function. The multiply is optimized away by the compiler + * on most platforms. + * It is about equivalent to the one above. + */ +int counts_tw2[NSERV][NSERV]; +uint32_t hash_tw2(uint32_t a) +{ + a = ~a + (a << 15); + a = a ^ (a >> 12); + a = a + (a << 2); + a = a ^ (a >> 4); + a = a * 2057; + a = a ^ (a >> 16); + return a; +} + +/* Thomas Wang's multiplicative hash function. About 0x30 bytes, and it is + * extremely fast on recent processors with a fast multiply. However, it + * must not be used on low bits only, as multiples of 0x00100010 only return + * even values ! + */ +int counts_tw3[NSERV][NSERV]; +uint32_t hash_tw3(uint32_t a) +{ + a = (a ^ 61) ^ (a >> 16); + a = a + (a << 3); + a = a ^ (a >> 4); + a = a * 0x27d4eb2d; + a = a ^ (a >> 15); + return a; +} + + +/* Full-avalanche integer hashing function from Bob Jenkins, suitable for use + * with a modulo. It has a very smooth distribution. + * http://burtleburtle.net/bob/hash/integer.html + * About 0x50 bytes, 6 shifts. + */ +int counts_bj6[NSERV][NSERV]; +int counts_bj6x[NSERV][NSERV]; +uint32_t hash_bj6(uint32_t a) +{ + a = (a+0x7ed55d16) + (a<<12); + a = (a^0xc761c23c) ^ (a>>19); + a = (a+0x165667b1) + (a<<5); + a = (a+0xd3a2646c) ^ (a<<9); + a = (a+0xfd7046c5) + (a<<3); + a = (a^0xb55a4f09) ^ (a>>16); + return a; +} + +/* Similar function with one more shift and no magic number. It is slightly + * slower but provides the overall smoothest distribution. + * About 0x40 bytes, 7 shifts. + */ +int counts_bj7[NSERV][NSERV]; +int counts_bj7x[NSERV][NSERV]; +uint32_t hash_bj7(uint32_t a) +{ + a -= (a<<6); + a ^= (a>>17); + a -= (a<<9); + a ^= (a<<4); + a -= (a<<3); + a ^= (a<<10); + a ^= (a>>15); + return a; +} + + +void count_hash_results(unsigned long hash, int counts[NSERV][NSERV]) { + int srv, nsrv; + + for (nsrv = 0; nsrv < NSERV; nsrv++) { + srv = hash % (nsrv + 1); + counts[nsrv][srv]++; + } +} + +void dump_hash_results(char *name, int counts[NSERV][NSERV]) { + int srv, nsrv; + double err, total_err, max_err; + + printf("%s:\n", name); + for (nsrv = 0; nsrv < NSERV; nsrv++) { + total_err = 0.0; + max_err = 0.0; + printf("%02d srv: ", nsrv+1); + for (srv = 0; srv <= nsrv; srv++) { + err = 100.0*(counts[nsrv][srv] - (double)counts[0][0]/(nsrv+1)) / (double)counts[0][0]; + //printf("%6d ", counts[nsrv][srv]); + printf("% 3.1f%%%c ", err, + counts[nsrv][srv]?' ':'*'); /* display '*' when a server is never selected */ + err = fabs(err); + total_err += err; + if (err > max_err) + max_err = err; + } + total_err /= (double)(nsrv+1); + for (srv = nsrv+1; srv < NSERV; srv++) + printf(" "); + printf(" avg_err=%3.1f, max_err=%3.1f\n", total_err, max_err); + } + printf("\n"); +} + +int main() { + int nr; + unsigned int address = 0; + unsigned int mask = ~0; + + memset(counts_id, 0, sizeof(counts_id)); + memset(counts_tw1, 0, sizeof(counts_tw1)); + memset(counts_tw2, 0, sizeof(counts_tw2)); + memset(counts_tw3, 0, sizeof(counts_tw3)); + memset(counts_bj6, 0, sizeof(counts_bj6)); + memset(counts_bj7, 0, sizeof(counts_bj7)); + + address = 0x10000000; + mask = 0xffffff00; // user mask to apply to addresses + for (nr = 0; nr < 0x10; nr++) { + //address += ~nr; // semi-random addresses. + //address += 1; + address += 0x00000100; + //address += 0x11111111; + //address += 7; + //address += 8; + //address += 256; + //address += 65536; + //address += 131072; + //address += 0x00100010; // this increment kills tw3 ! + count_hash_results(hash_id (address & mask), counts_id); // 0.69s / 100M + count_hash_results(hash_tw1(address & mask), counts_tw1); // 1.04s / 100M + count_hash_results(hash_tw2(address & mask), counts_tw2); // 1.13s / 100M + count_hash_results(hash_tw3(address & mask), counts_tw3); // 1.01s / 100M + count_hash_results(hash_bj6(address & mask), counts_bj6); // 1.07s / 100M + count_hash_results(hash_bj7(address & mask), counts_bj7); // 1.20s / 100M + /* adding the original address after the hash reduces the error + * rate in in presence of very small data sets (eg: 16 source + * addresses for 8 servers). In this case, bj7 is very good. + */ + count_hash_results(hash_bj6(address & mask)+(address&mask), counts_bj6x); // 1.07s / 100M + count_hash_results(hash_bj7(address & mask)+(address&mask), counts_bj7x); // 1.20s / 100M + } + + dump_hash_results("hash_id", counts_id); + dump_hash_results("hash_tw1", counts_tw1); + dump_hash_results("hash_tw2", counts_tw2); + dump_hash_results("hash_tw3", counts_tw3); + dump_hash_results("hash_bj6", counts_bj6); + dump_hash_results("hash_bj6x", counts_bj6x); + dump_hash_results("hash_bj7", counts_bj7); + dump_hash_results("hash_bj7x", counts_bj7x); + return 0; +} diff --git a/tests/exp/test_hashes.c b/tests/exp/test_hashes.c new file mode 100644 index 0000000..39cb965 --- /dev/null +++ b/tests/exp/test_hashes.c @@ -0,0 +1,559 @@ +/* + This file only show how many operations a hash is able to handle. + It don't show the distribution nor collisions. + + gcc -Wall -O3 -o test_hashes test_hashes.c + ./test_hashes |sort -k 3 -r + */ +#include +#include +#include +#include +#include +#include +//#include + + +static struct timeval timeval_current(void) +{ + struct timeval tv; + gettimeofday(&tv, NULL); + return tv; +} + +static double timeval_elapsed(struct timeval *tv) +{ + struct timeval tv2 = timeval_current(); + return (tv2.tv_sec - tv->tv_sec) + + (tv2.tv_usec - tv->tv_usec)*1.0e-6; +} + +#define HAPROXY_BACKENDS 4 + +unsigned long haproxy_uri_hash(char *uri, int uri_len){ + + unsigned long hash = 0; + int c; + + while (uri_len--) { + c = *uri++; + if (c == '?') + break; + hash = c + (hash << 6) + (hash << 16) - hash; + } + + return hash%HAPROXY_BACKENDS; /* I assume 4 active backends */ +} /* end haproxy_hash() */ + +/* + * http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx + */ +unsigned sax_hash ( void *key, int len ) +{ + unsigned char *p = key; + unsigned h = 0; + int i; + + for ( i = 0; i < len; i++ ) + h ^= ( h << 5 ) + ( h >> 2 ) + p[i]; + + return h; +} + +#include +/* len 4 for ipv4 and 16 for ipv6 */ +unsigned int haproxy_server_hash(const char *addr, int len){ + unsigned int h, l; + l = h = 0; + + while ((l + sizeof (int)) <= len) { + h ^= ntohl(*(unsigned int *)(&addr[l])); + l += sizeof (int); + } + return h %= HAPROXY_BACKENDS; +}/* end haproxy_server_hash() */ + + +int hashpjw(const void *key) { + + const char *ptr; + unsigned int val; + /********************************************************************* + * * + * Hash the key by performing a number of bit operations on it. * + * * + *********************************************************************/ + + val = 0; + ptr = key; + + while (*ptr != '\0') { + + int tmp; + + val = (val << 4) + (*ptr); + + if((tmp = (val & 0xf0000000))) { + val = val ^ (tmp >> 24); + val = val ^ tmp; + } + ptr++; + }/* end while */ + + return val; +}/* end hashpjw */ + +static unsigned long +hash_djbx33( + register unsigned char *key, + register size_t len) +{ + register unsigned long hash = 5381; + + /* the hash unrolled eight times */ + for (; len >= 8; len -= 8) { + hash = ((hash << 5) + hash) + *key++; + hash = ((hash << 5) + hash) + *key++; + hash = ((hash << 5) + hash) + *key++; + hash = ((hash << 5) + hash) + *key++; + hash = ((hash << 5) + hash) + *key++; + hash = ((hash << 5) + hash) + *key++; + hash = ((hash << 5) + hash) + *key++; + hash = ((hash << 5) + hash) + *key++; + } + switch (len) { + case 7: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */ + case 6: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */ + case 5: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */ + case 4: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */ + case 3: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */ + case 2: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */ + case 1: hash = ((hash << 5) + hash) + *key++; break; + default: /* case 0: */ break; + } + return hash; +} + +typedef unsigned long int ub4; /* unsigned 4-byte quantities */ +typedef unsigned char ub1; /* unsigned 1-byte quantities */ + +ub4 bernstein(ub1 *key, ub4 len, ub4 level){ + ub4 hash = level; + ub4 i; + for (i=0; i>= 2; + + /* Main loop */ + for (;len > 0; len--) { + hash += get16bits (data); + tmp = (get16bits (data+2) << 11) ^ hash; + hash = (hash << 16) ^ tmp; + data += 2*sizeof (uint16_t); + hash += hash >> 11; + } + + /* Handle end cases */ + switch (rem) { + case 3: hash += get16bits (data); + hash ^= hash << 16; + hash ^= data[sizeof (uint16_t)] << 18; + hash += hash >> 11; + break; + case 2: hash += get16bits (data); + hash ^= hash << 11; + hash += hash >> 17; + break; + case 1: hash += *data; + hash ^= hash << 10; + hash += hash >> 1; + } + + /* Force "avalanching" of final 127 bits */ + hash ^= hash << 3; + hash += hash >> 5; + hash ^= hash << 4; + hash += hash >> 17; + hash ^= hash << 25; + hash += hash >> 6; + + return hash; +} + +/* + * This variant is about 15% faster. + */ +uint32_t SuperFastHash2 (const char * data, int len) { +uint32_t hash = len, tmp; +int rem; + + if (len <= 0 || data == NULL) return 0; + + rem = len & 3; + len >>= 2; + + /* Main loop */ + for (;len > 0; len--) { + register uint32_t next; + next = get16bits(data+2); + hash += get16bits(data); + tmp = (next << 11) ^ hash; + hash = (hash << 16) ^ tmp; + data += 2*sizeof (uint16_t); + hash += hash >> 11; + } + + /* Handle end cases */ + switch (rem) { + case 3: hash += get16bits (data); + hash ^= hash << 16; + hash ^= data[sizeof (uint16_t)] << 18; + hash += hash >> 11; + break; + case 2: hash += get16bits (data); + hash ^= hash << 11; + hash += hash >> 17; + break; + case 1: hash += *data; + hash ^= hash << 10; + hash += hash >> 1; + } + + /* Force "avalanching" of final 127 bits */ + hash ^= hash << 3; + hash += hash >> 5; + hash ^= hash << 4; + hash += hash >> 17; + hash ^= hash << 25; + hash += hash >> 6; + + return hash; +} + +/* + * 32 bit FNV-0 hash type + */ +typedef unsigned long Fnv32_t; + +/* + * fnv_32a_str - perform a 32 bit Fowler/Noll/Vo FNV-1a hash on a string + * + * input: + * str - string to hash + * hval - previous hash value or 0 if first call + * + * returns: + * 32 bit hash as a static hash type + * + * NOTE: To use the recommended 32 bit FNV-1a hash, use FNV1_32A_INIT as the + * hval arg on the first call to either fnv_32a_buf() or fnv_32a_str(). + */ +Fnv32_t +fnv_32a_str(char *str, Fnv32_t hval) +{ + unsigned char *s = (unsigned char *)str; /* unsigned string */ + + /* + * FNV-1a hash each octet in the buffer + */ + while (*s) { + + /* xor the bottom with the current octet */ + hval ^= (Fnv32_t)*s++; + +/* #define NO_FNV_GCC_OPTIMIZATION */ + /* multiply by the 32 bit FNV magic prime mod 2^32 */ +#if defined(NO_FNV_GCC_OPTIMIZATION) + /* + * 32 bit magic FNV-1a prime + */ +#define FNV_32_PRIME ((Fnv32_t)0x01000193) + hval *= FNV_32_PRIME; +#else + hval += (hval<<1) + (hval<<4) + (hval<<7) + (hval<<8) + (hval<<24); +#endif + } + + /* return our new hash value */ + return hval; +} + +/* + * from lookup3.c, by Bob Jenkins, May 2006, Public Domain. + */ + +#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) + +/* +------------------------------------------------------------------------------- +mix -- mix 3 32-bit values reversibly. + +This is reversible, so any information in (a,b,c) before mix() is +still in (a,b,c) after mix(). + +If four pairs of (a,b,c) inputs are run through mix(), or through +mix() in reverse, there are at least 32 bits of the output that +are sometimes the same for one pair and different for another pair. +This was tested for: +* pairs that differed by one bit, by two bits, in any combination + of top bits of (a,b,c), or in any combination of bottom bits of + (a,b,c). +* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed + the output delta to a Gray code (a^(a>>1)) so a string of 1's (as + is commonly produced by subtraction) look like a single 1-bit + difference. +* the base values were pseudorandom, all zero but one bit set, or + all zero plus a counter that starts at zero. + +Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that +satisfy this are + 4 6 8 16 19 4 + 9 15 3 18 27 15 + 14 9 3 7 17 3 +Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing +for "differ" defined as + with a one-bit base and a two-bit delta. I +used http://burtleburtle.net/bob/hash/avalanche.html to choose +the operations, constants, and arrangements of the variables. + +This does not achieve avalanche. There are input bits of (a,b,c) +that fail to affect some output bits of (a,b,c), especially of a. The +most thoroughly mixed value is c, but it doesn't really even achieve +avalanche in c. + +This allows some parallelism. Read-after-writes are good at doubling +the number of bits affected, so the goal of mixing pulls in the opposite +direction as the goal of parallelism. I did what I could. Rotates +seem to cost as much as shifts on every machine I could lay my hands +on, and rotates are much kinder to the top and bottom bits, so I used +rotates. +------------------------------------------------------------------------------- +*/ +#define mix(a,b,c) \ +{ \ + a -= c; a ^= rot(c, 4); c += b; \ + b -= a; b ^= rot(a, 6); a += c; \ + c -= b; c ^= rot(b, 8); b += a; \ + a -= c; a ^= rot(c,16); c += b; \ + b -= a; b ^= rot(a,19); a += c; \ + c -= b; c ^= rot(b, 4); b += a; \ +} + +/* +------------------------------------------------------------------------------- +final -- final mixing of 3 32-bit values (a,b,c) into c + +Pairs of (a,b,c) values differing in only a few bits will usually +produce values of c that look totally different. This was tested for +* pairs that differed by one bit, by two bits, in any combination + of top bits of (a,b,c), or in any combination of bottom bits of + (a,b,c). +* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed + the output delta to a Gray code (a^(a>>1)) so a string of 1's (as + is commonly produced by subtraction) look like a single 1-bit + difference. +* the base values were pseudorandom, all zero but one bit set, or + all zero plus a counter that starts at zero. + +These constants passed: + 14 11 25 16 4 14 24 + 12 14 25 16 4 14 24 +and these came close: + 4 8 15 26 3 22 24 + 10 8 15 26 3 22 24 + 11 8 15 26 3 22 24 +------------------------------------------------------------------------------- +*/ +#define final(a,b,c) \ +{ \ + c ^= b; c -= rot(b,14); \ + a ^= c; a -= rot(c,11); \ + b ^= a; b -= rot(a,25); \ + c ^= b; c -= rot(b,16); \ + a ^= c; a -= rot(c,4); \ + b ^= a; b -= rot(a,14); \ + c ^= b; c -= rot(b,24); \ +} + +/* +-------------------------------------------------------------------- + This works on all machines. To be useful, it requires + -- that the key be an array of uint32_t's, and + -- that the length be the number of uint32_t's in the key + + The function hashword() is identical to hashlittle() on little-endian + machines, and identical to hashbig() on big-endian machines, + except that the length has to be measured in uint32_ts rather than in + bytes. hashlittle() is more complicated than hashword() only because + hashlittle() has to dance around fitting the key bytes into registers. +-------------------------------------------------------------------- +*/ +uint32_t hashword( +const uint32_t *k, /* the key, an array of uint32_t values */ +size_t length, /* the length of the key, in uint32_ts */ +uint32_t initval) /* the previous hash, or an arbitrary value */ +{ + uint32_t a,b,c; + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval; + + /*------------------------------------------------- handle most of the key */ + while (length > 3) + { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a,b,c); + length -= 3; + k += 3; + } + + /*------------------------------------------- handle the last 3 uint32_t's */ + switch(length) /* all the case statements fall through */ + { + case 3 : c+=k[2]; + case 2 : b+=k[1]; + case 1 : a+=k[0]; + final(a,b,c); + case 0: /* case 0: nothing left to add */ + break; + } + /*------------------------------------------------------ report the result */ + return c; +} + +/* from K&R book site 139 */ +#define HASHSIZE 101 + +unsigned kr_hash(char *s){ + unsigned hashval; + + for(hashval = 0; *s != '\0';s++) + hashval = *s + 31 * hashval; + + return hashval % HASHSIZE; + +} /* end kr_hash() */ + +unsigned fnv_hash ( void *key, int len ) +{ + unsigned char *p = key; + unsigned h = 2166136261; + int i; + + for ( i = 0; i < len; i++ ) + h = ( h * 16777619 ) ^ p[i]; + + return h; +} + +unsigned oat_hash ( void *key, int len ) +{ + unsigned char *p = key; + unsigned h = 0; + int i; + + for ( i = 0; i < len; i++ ) { + h += p[i]; + h += ( h << 10 ); + h ^= ( h >> 6 ); + } + + h += ( h << 3 ); + h ^= ( h >> 11 ); + h += ( h << 15 ); + + return h; +} + +unsigned wt_hash ( void *key, int len ) +{ + unsigned char *p = key; + unsigned h = 0x783c965aUL; + unsigned step = 16; + + for (; len > 0; len--) { + h ^= *p * 9; + p++; + h = (h << step) | (h >> (32-step)); + step ^= h; + step &= 0x1F; + } + + return h; +} + + +#define run_test(fct, args) { \ + unsigned long loop, count; \ + volatile unsigned long result; \ + double delta; \ + struct timeval tv; \ + fprintf(stderr, "Starting %s\n", #fct); \ + tv = timeval_current(); \ + count = 0; \ + do { \ + delta = timeval_elapsed(&tv); \ + for (loop = 0; loop < 1000; loop++) { \ + result = fct args; \ + count++; \ + } \ + } while (delta < 1.0); \ + fprintf(stdout, "%-20s : %10.0f run/sec\n", #fct, count/delta); \ + fflush(stdout); \ +} + +int main(){ + + char **start; + int len; + + char *urls[] = { + "http://www.microsoft.com/shared/core/1/webservice/navigation.asmx/DisplayDownlevelNavHtml", + NULL + }; + + start = urls; + len = strlen(*urls); + + run_test(wt_hash, (*urls, len)); + run_test(SuperFastHash2, (*urls, len)); + run_test(SuperFastHash, (*urls, len)); + run_test(haproxy_uri_hash, (*urls, len)); + run_test(haproxy_server_hash, (*urls, len)); + run_test(hashpjw, (*urls)); + run_test(hash_djbx33, ((unsigned char *)*urls, len)); + run_test(bernstein, ((unsigned char *)*urls, len, 4)); + run_test(fnv_32a_str, (*urls, 0)); + run_test(hashword, ((const uint32_t *)*urls,strlen(*urls),0)); + run_test(kr_hash, (*urls)); + run_test(sax_hash, (*urls, len)); + run_test(fnv_hash, (*urls, len)); + run_test(oat_hash, (*urls, len)); + + return 0; + +}/* end main() */ diff --git a/tests/exp/testinet.c b/tests/exp/testinet.c new file mode 100644 index 0000000..0eb87e9 --- /dev/null +++ b/tests/exp/testinet.c @@ -0,0 +1,28 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + + +int main() { + printf("sizeof sockaddr=%d\n", sizeof(struct sockaddr)); + printf("sizeof sockaddr_in=%d\n", sizeof(struct sockaddr_in)); + printf("sizeof sockaddr_in6=%d\n", sizeof(struct sockaddr_in6)); + return 0; +} diff --git a/tests/exp/uri_hash.c b/tests/exp/uri_hash.c new file mode 100644 index 0000000..0b5d755 --- /dev/null +++ b/tests/exp/uri_hash.c @@ -0,0 +1,377 @@ +#include +#include +#include + +#define NSERV 10 +#define MAXLINE 1000 + +char line[MAXLINE]; + +int counts_gd1[NSERV][NSERV]; +static unsigned long hash_gd1(char *uri) +{ + unsigned long hash = 0; + int c; + + while ((c = *uri++)) + hash = c + (hash << 6) + (hash << 16) - hash; + + return hash; +} + +int counts_gd2[NSERV][NSERV]; +static unsigned long hash_gd2(char *uri) +{ + unsigned long hash = 0; + int c; + + while ((c = *uri++)) { + if (c == '?' || c == '\n') + break; + hash = c + (hash << 6) + (hash << 16) - hash; + } + + return hash; +} + + +int counts_gd3[NSERV][NSERV]; +static unsigned long hash_gd3(char *uri) +{ + unsigned long hash = 0; + int c; + + while ((c = *uri++)) { + if (c == '?' || c == '\n') + break; + hash = c - (hash << 3) + (hash << 15) - hash; + } + + return hash; +} + + +int counts_gd4[NSERV][NSERV]; +static unsigned long hash_gd4(char *uri) +{ + unsigned long hash = 0; + int c; + + while ((c = *uri++)) { + if (c == '?' || c == '\n') + break; + hash = hash + (hash << 6) - (hash << 15) - c; + } + + return hash; +} + + +int counts_gd5[NSERV][NSERV]; +static unsigned long hash_gd5(char *uri) +{ + unsigned long hash = 0; + int c; + + while ((c = *uri++)) { + if (c == '?' || c == '\n') + break; + hash = hash + (hash << 2) - (hash << 19) - c; + } + + return hash; +} + + +int counts_gd6[NSERV][NSERV]; +static unsigned long hash_gd6(char *uri) +{ + unsigned long hash = 0; + int c; + + while ((c = *uri++)) { + if (c == '?' || c == '\n') + break; + hash = hash + (hash << 2) - (hash << 22) - c; + } + + return hash; +} + + +int counts_wt1[NSERV][NSERV]; +static unsigned long hash_wt1(int hsize, char *string) { + int bits; + unsigned long data, val; + + bits = val = data = 0; + while (*string) { + if (*string == '?' || *string == '\n') + break; + data |= ((unsigned long)(unsigned char)*string) << bits; + bits += 8; + while (bits >= hsize) { + val ^= data - (val >> hsize); + bits -= hsize; + data >>= hsize; + } + string++; + } + val ^= data; + while (val > ((1 << hsize) - 1)) { + val = (val & ((1 << hsize) - 1)) ^ (val >> hsize); + } + return val; +} + +/* + * efficient hash : no duplicate on the first 65536 values of 2 bytes. + * less than 0.1% duplicates for the first 1.6 M values of 3 bytes. + */ +int counts_wt2[NSERV][NSERV]; +typedef unsigned int u_int32_t; + +static inline u_int32_t shl32(u_int32_t i, int count) { + if (count == 32) + return 0; + return i << count; +} + +static inline u_int32_t shr32(u_int32_t i, int count) { + if (count == 32) + return 0; + return i >> count; +} + +static unsigned int rev32(unsigned int c) { + c = ((c & 0x0000FFFF) << 16)| ((c & 0xFFFF0000) >> 16); + c = ((c & 0x00FF00FF) << 8) | ((c & 0xFF00FF00) >> 8); + c = ((c & 0x0F0F0F0F) << 4) | ((c & 0xF0F0F0F0) >> 4); + c = ((c & 0x33333333) << 2) | ((c & 0xCCCCCCCC) >> 2); + c = ((c & 0x55555555) << 1) | ((c & 0xAAAAAAAA) >> 1); + return c; +} + +int hash_wt2(const char *src, int len) { + unsigned int i = 0x3C964BA5; /* as many ones as zeroes */ + unsigned int j; + unsigned int ih, il; + int bit; + + while (len--) { + j = (unsigned char)*src++; + if (j == '?' || j == '\n') + break; + bit = rev32(j - i); + bit = bit - (bit >> 3) + (bit >> 16) - j; + + bit &= 0x1f; + ih = shr32(i, bit); + il = i & (shl32(1, bit) - 1); + i = shl32(il, 32-bit) - ih - ~j; + } + return i; +} + + +//typedef unsigned int uint32_t; +//typedef unsigned short uint8_t; +//typedef unsigned char uint16_t; + +/* + * http://www.azillionmonkeys.com/qed/hash.html + */ +#undef get16bits +#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \ + || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__) +#define get16bits(d) (*((const uint16_t *) (d))) +#endif + +#if !defined (get16bits) +#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\ + +(uint32_t)(((const uint8_t *)(d))[0]) ) +#endif + +/* + * This function has a hole of 11 unused bits in bytes 2 and 3 of each block of + * 32 bits. + */ +int counts_SuperFastHash[NSERV][NSERV]; + +uint32_t SuperFastHash (const char * data, int len) { +uint32_t hash = len, tmp; +int rem; + + if (len <= 0 || data == NULL) return 0; + + rem = len & 3; + len >>= 2; + + /* Main loop */ + for (;len > 0; len--) { + hash += get16bits (data); + tmp = (get16bits (data+2) << 11) ^ hash; + hash = (hash << 16) ^ tmp; + data += 2*sizeof (uint16_t); + hash += hash >> 11; + } + + /* Handle end cases */ + switch (rem) { + case 3: hash += get16bits (data); + hash ^= hash << 16; + hash ^= data[sizeof (uint16_t)] << 18; + hash += hash >> 11; + break; + case 2: hash += get16bits (data); + hash ^= hash << 11; + hash += hash >> 17; + break; + case 1: hash += *data; + hash ^= hash << 10; + hash += hash >> 1; + } + + /* Force "avalanching" of final 127 bits */ + hash ^= hash << 3; + hash += hash >> 5; + hash ^= hash << 4; + hash += hash >> 17; + hash ^= hash << 25; + hash += hash >> 6; + + return hash; +} + +/* + * This variant uses all bits from the input block, and is about 15% faster. + */ +int counts_SuperFastHash2[NSERV][NSERV]; +uint32_t SuperFastHash2 (const char * data, int len) { +uint32_t hash = len, tmp; +int rem; + + if (len <= 0 || data == NULL) return 0; + + rem = len & 3; + len >>= 2; + + /* Main loop */ + for (;len > 0; len--) { + register uint32_t next; + next = get16bits(data+2); + hash += get16bits(data); + tmp = ((next << 11) | (next >> 21)) ^ hash; + hash = (hash << 16) ^ tmp; + data += 2*sizeof (uint16_t); + hash += hash >> 11; + } + + /* Handle end cases */ + switch (rem) { + case 3: hash += get16bits (data); + hash ^= hash << 16; + hash ^= data[sizeof (uint16_t)] << 18; + hash += hash >> 11; + break; + case 2: hash += get16bits (data); + hash ^= hash << 11; + hash += hash >> 17; + break; + case 1: hash += *data; + hash ^= hash << 10; + hash += hash >> 1; + } + + /* Force "avalanching" of final 127 bits */ + hash ^= hash << 3; + hash += hash >> 5; + hash ^= hash << 4; + hash += hash >> 17; + hash ^= hash << 25; + hash += hash >> 6; + + return hash; +} + +/* len 4 for ipv4 and 16 for ipv6 */ +int counts_srv[NSERV][NSERV]; +unsigned int haproxy_server_hash(const char *addr, int len){ + unsigned int h, l; + l = h = 0; + + while ((l + sizeof (int)) <= len) { + h ^= ntohl(*(unsigned int *)(&addr[l])); + l += sizeof (int); + } + return h; +}/* end haproxy_server_hash() */ + + + +void count_hash_results(unsigned long hash, int counts[NSERV][NSERV]) { + int srv, nsrv; + + for (nsrv = 0; nsrv < NSERV; nsrv++) { + srv = hash % (nsrv + 1); + counts[nsrv][srv]++; + } +} + +void dump_hash_results(char *name, int counts[NSERV][NSERV]) { + int srv, nsrv; + + printf("%s:\n", name); + for (nsrv = 0; nsrv < NSERV; nsrv++) { + printf("%02d srv: ", nsrv+1); + for (srv = 0; srv <= nsrv; srv++) { + //printf("%6d ", counts[nsrv][srv]); + //printf("%3.1f ", (100.0*counts[nsrv][srv]) / (double)counts[0][0]); + printf("%3.1f ", 100.0*(counts[nsrv][srv] - (double)counts[0][0]/(nsrv+1)) / (double)counts[0][0]); + } + printf("\n"); + } + printf("\n"); +} + +int main() { + memset(counts_gd1, 0, sizeof(counts_gd1)); + memset(counts_gd2, 0, sizeof(counts_gd2)); + memset(counts_gd3, 0, sizeof(counts_gd3)); + memset(counts_gd4, 0, sizeof(counts_gd4)); + memset(counts_gd5, 0, sizeof(counts_gd5)); + memset(counts_gd6, 0, sizeof(counts_gd6)); + memset(counts_wt1, 0, sizeof(counts_wt1)); + memset(counts_wt2, 0, sizeof(counts_wt2)); + memset(counts_srv, 0, sizeof(counts_srv)); + memset(counts_SuperFastHash, 0, sizeof(counts_SuperFastHash)); + memset(counts_SuperFastHash2, 0, sizeof(counts_SuperFastHash2)); + + while (fgets(line, MAXLINE, stdin) != NULL) { + count_hash_results(hash_gd1(line), counts_gd1); + count_hash_results(hash_gd2(line), counts_gd2); + count_hash_results(hash_gd3(line), counts_gd3); + count_hash_results(hash_gd4(line), counts_gd4); + count_hash_results(hash_gd5(line), counts_gd5); + count_hash_results(hash_gd6(line), counts_gd6); + count_hash_results(hash_wt1(31, line), counts_wt1); + count_hash_results(hash_wt2(line, strlen(line)), counts_wt2); + count_hash_results(haproxy_server_hash(line, strlen(line)), counts_srv); + count_hash_results(SuperFastHash(line, strlen(line)), counts_SuperFastHash); + count_hash_results(SuperFastHash2(line, strlen(line)), counts_SuperFastHash2); + } + + dump_hash_results("hash_gd1", counts_gd1); + dump_hash_results("hash_gd2", counts_gd2); + dump_hash_results("hash_gd3", counts_gd3); + dump_hash_results("hash_gd4", counts_gd4); + dump_hash_results("hash_gd5", counts_gd5); + dump_hash_results("hash_gd6", counts_gd6); + dump_hash_results("hash_wt1", counts_wt1); + dump_hash_results("hash_wt2", counts_wt2); + dump_hash_results("haproxy_server_hash", counts_srv); + dump_hash_results("SuperFastHash", counts_SuperFastHash); + dump_hash_results("SuperFastHash2", counts_SuperFastHash2); + + return 0; +} -- cgit v1.2.3