diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-03-09 13:19:48 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-03-09 13:20:02 +0000 |
commit | 58daab21cd043e1dc37024a7f99b396788372918 (patch) | |
tree | 96771e43bb69f7c1c2b0b4f7374cb74d7866d0cb /web/server/h2o/libh2o/deps/klib/test | |
parent | Releasing debian version 1.43.2-1. (diff) | |
download | netdata-58daab21cd043e1dc37024a7f99b396788372918.tar.xz netdata-58daab21cd043e1dc37024a7f99b396788372918.zip |
Merging upstream version 1.44.3.
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'web/server/h2o/libh2o/deps/klib/test')
20 files changed, 2335 insertions, 0 deletions
diff --git a/web/server/h2o/libh2o/deps/klib/test/Makefile b/web/server/h2o/libh2o/deps/klib/test/Makefile new file mode 100644 index 000000000..a392c8ed4 --- /dev/null +++ b/web/server/h2o/libh2o/deps/klib/test/Makefile @@ -0,0 +1,60 @@ +CC=gcc +CXX=g++ +CFLAGS=-g -Wall -O2 -I.. +CXXFLAGS=$(CFLAGS) +PROGS=kbtree_test khash_keith khash_keith2 khash_test klist_test kseq_test kseq_bench \ + kseq_bench2 ksort_test ksort_test-stl kvec_test kmin_test kstring_bench kstring_bench2 kstring_test \ + kthread_test + +all:$(PROGS) + +clean: + rm -fr $(PROGS) *.dSYM a.out + +kbtree_test:kbtree_test.c ../kbtree.h + $(CC) $(CFLAGS) -o $@ kbtree_test.c + +khash_keith:khash_keith.c ../khash.h + $(CC) $(CFLAGS) -o $@ khash_keith.c + +khash_keith2:khash_keith2.c ../khash.h + $(CC) $(CFLAGS) -o $@ khash_keith2.c + +khash_test:khash_test.c ../khash.h + $(CC) $(CFLAGS) -o $@ khash_test.c + +klist_test:klist_test.c ../klist.h + $(CC) $(CFLAGS) -o $@ klist_test.c + +kseq_test:kseq_test.c ../kseq.h + $(CC) $(CFLAGS) -o $@ kseq_test.c -lz + +kseq_bench:kseq_bench.c ../kseq.h + $(CC) $(CFLAGS) -o $@ kseq_bench.c -lz + +kseq_bench2:kseq_bench2.c ../kseq.h + $(CC) $(CFLAGS) -o $@ kseq_bench2.c -lz + +ksort_test:ksort_test.c ../ksort.h + $(CC) $(CFLAGS) -o $@ ksort_test.c + +ksort_test-stl:ksort_test.cc ../ksort.h + $(CXX) $(CXXFLAGS) -o $@ ksort_test.cc + +kvec_test:kvec_test.cc ../kvec.h + $(CXX) $(CXXFLAGS) -o $@ kvec_test.cc + +kmin_test:kmin_test.c ../kmath.h ../kmath.c + $(CC) $(CFLAGS) -o $@ kmin_test.c ../kmath.c + +kstring_bench:kstring_bench.c ../kstring.h ../kstring.c + $(CC) $(CFLAGS) -o $@ kstring_bench.c ../kstring.c + +kstring_bench2:kstring_bench2.c ../kstring.h ../kstring.c + $(CC) $(CFLAGS) -o $@ kstring_bench2.c ../kstring.c + +kstring_test:kstring_test.c ../kstring.h ../kstring.c + $(CC) $(CFLAGS) -o $@ kstring_test.c ../kstring.c + +kthread_test:kthread_test.c ../kthread.c + $(CC) $(CFLAGS) -fopenmp -o $@ kthread_test.c ../kthread.c diff --git a/web/server/h2o/libh2o/deps/klib/test/kbit_test.c b/web/server/h2o/libh2o/deps/klib/test/kbit_test.c new file mode 100644 index 000000000..3ae3bd309 --- /dev/null +++ b/web/server/h2o/libh2o/deps/klib/test/kbit_test.c @@ -0,0 +1,137 @@ +#include <stdlib.h> +#include <stdio.h> +#include <time.h> +#include <emmintrin.h> +#include "kbit.h" + +// from bowtie-0.9.8.1 +inline static int bt1_pop64(uint64_t x) // the kbi_popcount64() equivalence; similar to popcount_2() in wiki +{ + x -= ((x >> 1) & 0x5555555555555555llu); + x = (x & 0x3333333333333333llu) + ((x >> 2) & 0x3333333333333333llu); + x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0Fllu; + x = x + (x >> 8); + x = x + (x >> 16); + x = x + (x >> 32); + return x & 0x3F; +} + +inline static int bt1_countInU64(uint64_t dw, int c) // the kbi_DNAcount64() equivalence +{ + uint64_t dwA = dw & 0xAAAAAAAAAAAAAAAAllu; + uint64_t dwNA = dw & ~0xAAAAAAAAAAAAAAAAllu; + uint64_t tmp; + switch (c) { + case 0: tmp = (dwA >> 1) | dwNA; break; + case 1: tmp = ~(dwA >> 1) & dwNA; break; + case 2: tmp = (dwA >> 1) & ~dwNA; break; + default: tmp = (dwA >> 1) & dwNA; + } + tmp = bt1_pop64(tmp); + if (c == 0) tmp = 32 - tmp; + return (int)tmp; +} + +// from bigmagic +static uint32_t sse2_bit_count32(const __m128i* block, const __m128i* block_end) +{ + const unsigned mu1 = 0x55555555; + const unsigned mu2 = 0x33333333; + const unsigned mu3 = 0x0F0F0F0F; + const unsigned mu4 = 0x0000003F; + + uint32_t tcnt[4]; + + // Loading masks + __m128i m1 = _mm_set_epi32 (mu1, mu1, mu1, mu1); + __m128i m2 = _mm_set_epi32 (mu2, mu2, mu2, mu2); + __m128i m3 = _mm_set_epi32 (mu3, mu3, mu3, mu3); + __m128i m4 = _mm_set_epi32 (mu4, mu4, mu4, mu4); + __m128i mcnt; + mcnt = _mm_xor_si128(m1, m1); // cnt = 0 + + __m128i tmp1, tmp2; + do + { + __m128i b = _mm_load_si128(block); + ++block; + + // b = (b & 0x55555555) + (b >> 1 & 0x55555555); + tmp1 = _mm_srli_epi32(b, 1); // tmp1 = (b >> 1 & 0x55555555) + tmp1 = _mm_and_si128(tmp1, m1); + tmp2 = _mm_and_si128(b, m1); // tmp2 = (b & 0x55555555) + b = _mm_add_epi32(tmp1, tmp2); // b = tmp1 + tmp2 + + // b = (b & 0x33333333) + (b >> 2 & 0x33333333); + tmp1 = _mm_srli_epi32(b, 2); // (b >> 2 & 0x33333333) + tmp1 = _mm_and_si128(tmp1, m2); + tmp2 = _mm_and_si128(b, m2); // (b & 0x33333333) + b = _mm_add_epi32(tmp1, tmp2); // b = tmp1 + tmp2 + + // b = (b + (b >> 4)) & 0x0F0F0F0F; + tmp1 = _mm_srli_epi32(b, 4); // tmp1 = b >> 4 + b = _mm_add_epi32(b, tmp1); // b = b + (b >> 4) + b = _mm_and_si128(b, m3); // & 0x0F0F0F0F + + // b = b + (b >> 8); + tmp1 = _mm_srli_epi32 (b, 8); // tmp1 = b >> 8 + b = _mm_add_epi32(b, tmp1); // b = b + (b >> 8) + + // b = (b + (b >> 16)) & 0x0000003F; + tmp1 = _mm_srli_epi32 (b, 16); // b >> 16 + b = _mm_add_epi32(b, tmp1); // b + (b >> 16) + b = _mm_and_si128(b, m4); // (b >> 16) & 0x0000003F; + + mcnt = _mm_add_epi32(mcnt, b); // mcnt += b + + } while (block < block_end); + + _mm_store_si128((__m128i*)tcnt, mcnt); + + return tcnt[0] + tcnt[1] + tcnt[2] + tcnt[3]; +} + +int main(void) +{ + int i, N = 100000000; + uint64_t *x, cnt; + clock_t t; + int c = 1; + + x = (uint64_t*)calloc(N, 8); + srand48(11); + for (i = 0; i < N; ++i) + x[i] = (uint64_t)lrand48() << 32 ^ lrand48(); + + fprintf(stderr, "\n===> Calculate # of 1 in an integer (popcount) <===\n"); + + t = clock(); cnt = 0; + for (i = 0; i < N; ++i) cnt += kbi_popcount64(x[i]); + fprintf(stderr, "%20s\t%20ld\t%10.6f\n", "kbit", (long)cnt, (double)(clock() - t) / CLOCKS_PER_SEC); + + t = clock(); cnt = 0; + for (i = 0; i < N; ++i) cnt += bt1_pop64(x[i]); + fprintf(stderr, "%20s\t%20ld\t%10.6f\n", "wiki-popcount_2", (long)cnt, (double)(clock() - t) / CLOCKS_PER_SEC); + + t = clock(); cnt = 0; + for (i = 0; i < N; ++i) cnt += __builtin_popcountl(x[i]); + fprintf(stderr, "%20s\t%20ld\t%10.6f\n", "__builtin_popcountl", (long)cnt, (double)(clock() - t) / CLOCKS_PER_SEC); + + t = clock(); cnt = 0; + cnt += sse2_bit_count32((__m128i*)x, (__m128i*)(x+N)); + fprintf(stderr, "%20s\t%20ld\t%10.6f\n", "SSE2-32bit", (long)cnt, (double)(clock() - t) / CLOCKS_PER_SEC); + + fprintf(stderr, "\n===> Count '%c' in 2-bit encoded integers <===\n", "ACGT"[c]); + + t = clock(); cnt = 0; + for (i = 0; i < N; ++i) cnt += kbi_DNAcount64(x[i], c); + fprintf(stderr, "%20s\t%20ld\t%10.6f\n", "kbit", (long)cnt, (double)(clock() - t) / CLOCKS_PER_SEC); + + t = clock(); cnt = 0; + for (i = 0; i < N; ++i) cnt += bt1_countInU64(x[i], c); + fprintf(stderr, "%20s\t%20ld\t%10.6f\n", "bowtie1", (long)cnt, (double)(clock() - t) / CLOCKS_PER_SEC); + + fprintf(stderr, "\n"); + free(x); + return 0; +} diff --git a/web/server/h2o/libh2o/deps/klib/test/kbtree_test.c b/web/server/h2o/libh2o/deps/klib/test/kbtree_test.c new file mode 100644 index 000000000..8e1068767 --- /dev/null +++ b/web/server/h2o/libh2o/deps/klib/test/kbtree_test.c @@ -0,0 +1,94 @@ +#include <stdio.h> +#include <assert.h> +#include <time.h> +#include <stdlib.h> +#include <stdint.h> +#include <string.h> + +typedef const char *str_t; + +#include "kbtree.h" +KBTREE_INIT(int, uint32_t, kb_generic_cmp) +KBTREE_INIT(str, str_t, kb_str_cmp) + +static int data_size = 5000000; +static unsigned *int_data; +static char **str_data; + +void ht_init_data() +{ + int i; + char buf[256]; + printf("--- generating data... "); + srand48(11); + int_data = (unsigned*)calloc(data_size, sizeof(unsigned)); + str_data = (char**)calloc(data_size, sizeof(char*)); + for (i = 0; i < data_size; ++i) { + int_data[i] = (unsigned)(data_size * drand48() / 4) * 271828183u; + sprintf(buf, "%x", int_data[i]); + str_data[i] = strdup(buf); + } + printf("done!\n"); +} +void ht_destroy_data() +{ + int i; + for (i = 0; i < data_size; ++i) free(str_data[i]); + free(str_data); free(int_data); +} + +void ht_khash_int() +{ + int i; + unsigned *data = int_data; + uint32_t *l, *u; + kbtree_t(int) *h; + + h = kb_init(int, KB_DEFAULT_SIZE); + for (i = 0; i < data_size; ++i) { + if (kb_get(int, h, data[i]) == 0) kb_put(int, h, data[i]); + else kb_del(int, h, data[i]); + } + printf("[ht_khash_int] size: %d\n", kb_size(h)); + if (1) { + int cnt = 0; + uint32_t x, y; + kb_interval(int, h, 2174625464u, &l, &u); + printf("interval for 2174625464: (%u, %u)\n", l? *l : 0, u? *u : 0); +#define traverse_f(p) { if (cnt == 0) y = *p; ++cnt; } + __kb_traverse(uint32_t, h, traverse_f); + __kb_get_first(uint32_t, h, x); + printf("# of elements from traversal: %d\n", cnt); + printf("first element: %d == %d\n", x, y); + } + __kb_destroy(h); +} +void ht_khash_str() +{ + int i; + char **data = str_data; + kbtree_t(str) *h; + + h = kb_init(str, KB_DEFAULT_SIZE); + for (i = 0; i < data_size; ++i) { + if (kb_get(str, h, data[i]) == 0) kb_put(str, h, data[i]); + else kb_del(str, h, data[i]); + } + printf("[ht_khash_int] size: %d\n", kb_size(h)); + __kb_destroy(h); +} +void ht_timing(void (*f)(void)) +{ + clock_t t = clock(); + (*f)(); + printf("[ht_timing] %.3lf sec\n", (double)(clock() - t) / CLOCKS_PER_SEC); +} +int main(int argc, char *argv[]) +{ + if (argc > 1) data_size = atoi(argv[1]); + ht_init_data(); + ht_timing(ht_khash_int); + ht_timing(ht_khash_str); + ht_destroy_data(); + return 0; +} diff --git a/web/server/h2o/libh2o/deps/klib/test/kgraph_test.c b/web/server/h2o/libh2o/deps/klib/test/kgraph_test.c new file mode 100644 index 000000000..3da1cd71b --- /dev/null +++ b/web/server/h2o/libh2o/deps/klib/test/kgraph_test.c @@ -0,0 +1,26 @@ +#include <stdio.h> +#include "kgraph.h" + +KHASH_INIT2(e32, extern, uint32_t, int, 1, kh_int_hash_func, kh_int_hash_equal) + +typedef struct { + int i; + khash_t(e32) *_arc; +} vertex_t; + +KGRAPH_INIT(g, extern, vertex_t, int, e32) +KGRAPH_PRINT(g, extern) + +int main() +{ + int *pb, *pe; + kgraph_t(g) *g; + g = kg_init_g(); + kg_put_a_g(g, 10, 20, 0, &pb, &pe); + kg_put_a_g(g, 20, 30, 0, &pb, &pe); + kg_put_a_g(g, 30, 10, 1, &pb, &pe); + kg_del_v_g(g, 20); + kg_print_g(g); + kg_destroy_g(g); + return 0; +} diff --git a/web/server/h2o/libh2o/deps/klib/test/khash_keith.c b/web/server/h2o/libh2o/deps/klib/test/khash_keith.c new file mode 100644 index 000000000..ddd755ac7 --- /dev/null +++ b/web/server/h2o/libh2o/deps/klib/test/khash_keith.c @@ -0,0 +1,95 @@ +/* + * This is an optimized version of the following C++ program: + * + * http://keithlea.com/javabench/src/cpp/hash.cpp + * + * Keith in his benchmark (http://keithlea.com/javabench/data) showed that the + * Java implementation is twice as fast as the C++ version. In fact, this is + * only because the C++ implementation is substandard. Most importantly, Keith + * is using "sprintf()" to convert an integer to a string, which is known to be + * extremely inefficient. + */ +#include <stdio.h> +#include "khash.h" +KHASH_MAP_INIT_STR(str, int) + +inline void int2str(int c, int base, char *ret) +{ + const char *tab = "0123456789abcdef"; + if (c == 0) ret[0] = '0', ret[1] = 0; + else { + int l, x, y; + char buf[16]; + for (l = 0, x = c < 0? -c : c; x > 0; x /= base) buf[l++] = tab[x%base]; + if (c < 0) buf[l++] = '-'; + for (x = l - 1, y = 0; x >= 0; --x) ret[y++] = buf[x]; + ret[y] = 0; + } +} + +#ifndef _USE_STRDUP +#define BLOCK_SIZE 0x100000 +int main(int argc, char *argv[]) +{ + char **mem = 0; + int i, l, n = 1000000, ret, block_end = 0, curr = 0, c = 0; + khash_t(str) *h; + h = kh_init(str); + if (argc > 1) n = atoi(argv[1]); + mem = malloc(sizeof(void*)); + mem[0] = malloc(BLOCK_SIZE); // memory buffer to avoid memory fragmentation + curr = block_end = 0; + for (i = 1; i <= n; ++i) { + char buf[16]; + int2str(i, 16, buf); + khint_t k = kh_put(str, h, buf, &ret); + l = strlen(buf) + 1; + if (block_end + l > BLOCK_SIZE) { + ++curr; block_end = 0; + mem = realloc(mem, (curr + 1) * sizeof(void*)); + mem[curr] = malloc(BLOCK_SIZE); + } + memcpy(mem[curr] + block_end, buf, l); + kh_key(h, k) = mem[curr] + block_end; + block_end += l; + kh_val(h, k) = i; + } + for (i = 1; i <= n; ++i) { + char buf[16]; + int2str(i, 10, buf); + khint_t k = kh_get(str, h, buf); + if (k != kh_end(h)) ++c; + } + printf("%d\n", c); + for (ret = 0; ret <= curr; ++ret) free(mem[ret]); + free(mem); + kh_destroy(str, h); + return 0; +} +#else // _USE_STRDUP +int main(int argc, char *argv[]) +{ + int i, l, n = 1000000, ret, c = 0; + khash_t(str) *h; + khint_t k; + h = kh_init(str); + if (argc > 1) n = atoi(argv[1]); + for (i = 1; i <= n; ++i) { + char buf[16]; + int2str(i, 16, buf); + k = kh_put(str, h, strdup(buf), &ret); + kh_val(h, k) = i; + } + for (i = 1; i <= n; ++i) { + char buf[16]; + int2str(i, 10, buf); + k = kh_get(str, h, buf); + if (k != kh_end(h)) ++c; + } + for (k = kh_begin(h); k != kh_end(h); ++k) // explicitly freeing memory takes 10-20% CPU time. + if (kh_exist(h, k)) free((char*)kh_key(h, k)); + printf("%d\n", c); + kh_destroy(str, h); + return 0; +} +#endif diff --git a/web/server/h2o/libh2o/deps/klib/test/khash_keith2.c b/web/server/h2o/libh2o/deps/klib/test/khash_keith2.c new file mode 100644 index 000000000..b9df9b7c1 --- /dev/null +++ b/web/server/h2o/libh2o/deps/klib/test/khash_keith2.c @@ -0,0 +1,67 @@ +/* + * This is an optimized version of the following C++ program: + * + * http://keithlea.com/javabench/src/cpp/hash.cpp + * + * Keith in his benchmark (http://keithlea.com/javabench/data) showed that the + * Java implementation is twice as fast as the C++ version. In fact, this is + * only because the C++ implementation is substandard. Most importantly, Keith + * is using "sprintf()" to convert an integer to a string, which is known to be + * extremely inefficient. + */ +#include <stdio.h> +#include "khash.h" +KHASH_MAP_INIT_STR(str, int) + +inline void int2str(int c, int base, char *ret) +{ + const char *tab = "0123456789abcdef"; + if (c == 0) ret[0] = '0', ret[1] = 0; + else { + int l, x, y; + char buf[16]; + for (l = 0, x = c < 0? -c : c; x > 0; x /= base) buf[l++] = tab[x%base]; + if (c < 0) buf[l++] = '-'; + for (x = l - 1, y = 0; x >= 0; --x) ret[y++] = buf[x]; + ret[y] = 0; + } +} + +int main(int argc, char *argv[]) +{ + int i, l, n = 1000, ret; + khash_t(str) *h, *h2; + khint_t k; + h = kh_init(str); + h2 = kh_init(str); + if (argc > 1) n = atoi(argv[1]); + for (i = 0; i < 10000; ++i) { + char buf[32]; + strcpy(buf, "foo_"); + int2str(i, 10, buf+4); + k = kh_put(str, h, strdup(buf), &ret); + kh_val(h, k) = i; + } + for (i = 0; i < n; ++i) { + for (k = kh_begin(h); k != kh_end(h); ++k) { + if (kh_exist(h, k)) { + khint_t k2 = kh_put(str, h2, kh_key(h, k), &ret); + if (ret) { // absent + kh_key(h2, k2) = strdup(kh_key(h, k)); + kh_val(h2, k2) = kh_val(h, k); + } else kh_val(h2, k2) += kh_val(h, k); + } + } + } + k = kh_get(str, h, "foo_1"); printf("%d", kh_val(h, k)); + k = kh_get(str, h, "foo_9999"); printf(" %d", kh_val(h, k)); + k = kh_get(str, h2, "foo_1"); printf(" %d", kh_val(h2, k)); + k = kh_get(str, h2, "foo_9999"); printf(" %d\n", kh_val(h2, k)); + for (k = kh_begin(h); k != kh_end(h); ++k) + if (kh_exist(h, k)) free((char*)kh_key(h, k)); + for (k = kh_begin(h2); k != kh_end(h2); ++k) + if (kh_exist(h2, k)) free((char*)kh_key(h2, k)); + kh_destroy(str, h); + kh_destroy(str, h2); + return 0; +} diff --git a/web/server/h2o/libh2o/deps/klib/test/khash_test.c b/web/server/h2o/libh2o/deps/klib/test/khash_test.c new file mode 100644 index 000000000..8d6687ff4 --- /dev/null +++ b/web/server/h2o/libh2o/deps/klib/test/khash_test.c @@ -0,0 +1,141 @@ +#include <stdio.h> +#include <assert.h> +#include <time.h> +#include <stdlib.h> +#include <string.h> + +#include "khash.h" +KHASH_SET_INIT_STR(str) +KHASH_MAP_INIT_INT(int, unsigned char) + +typedef struct { + unsigned key; + unsigned char val; +} int_unpack_t; + +typedef struct { + unsigned key; + unsigned char val; +} __attribute__ ((__packed__)) int_packed_t; + +#define hash_eq(a, b) ((a).key == (b).key) +#define hash_func(a) ((a).key) + +KHASH_INIT(iun, int_unpack_t, char, 0, hash_func, hash_eq) +KHASH_INIT(ipk, int_packed_t, char, 0, hash_func, hash_eq) + +static int data_size = 5000000; +static unsigned *int_data; +static char **str_data; + +void ht_init_data() +{ + int i; + char buf[256]; + khint32_t x = 11; + printf("--- generating data... "); + int_data = (unsigned*)calloc(data_size, sizeof(unsigned)); + str_data = (char**)calloc(data_size, sizeof(char*)); + for (i = 0; i < data_size; ++i) { + int_data[i] = (unsigned)(data_size * ((double)x / UINT_MAX) / 4) * 271828183u; + sprintf(buf, "%x", int_data[i]); + str_data[i] = strdup(buf); + x = 1664525L * x + 1013904223L; + } + printf("done!\n"); +} + +void ht_destroy_data() +{ + int i; + for (i = 0; i < data_size; ++i) free(str_data[i]); + free(str_data); free(int_data); +} + +void ht_khash_int() +{ + int i, ret; + unsigned *data = int_data; + khash_t(int) *h; + unsigned k; + + h = kh_init(int); + for (i = 0; i < data_size; ++i) { + k = kh_put(int, h, data[i], &ret); + kh_val(h, k) = i&0xff; + if (!ret) kh_del(int, h, k); + } + printf("[ht_khash_int] size: %u\n", kh_size(h)); + kh_destroy(int, h); +} + +void ht_khash_str() +{ + int i, ret; + char **data = str_data; + khash_t(str) *h; + unsigned k; + + h = kh_init(str); + for (i = 0; i < data_size; ++i) { + k = kh_put(str, h, data[i], &ret); + if (!ret) kh_del(str, h, k); + } + printf("[ht_khash_int] size: %u\n", kh_size(h)); + kh_destroy(str, h); +} + +void ht_khash_unpack() +{ + int i, ret; + unsigned *data = int_data; + khash_t(iun) *h; + unsigned k; + + h = kh_init(iun); + for (i = 0; i < data_size; ++i) { + int_unpack_t x; + x.key = data[i]; x.val = i&0xff; + k = kh_put(iun, h, x, &ret); + if (!ret) kh_del(iun, h, k); + } + printf("[ht_khash_unpack] size: %u (sizeof=%ld)\n", kh_size(h), sizeof(int_unpack_t)); + kh_destroy(iun, h); +} + +void ht_khash_packed() +{ + int i, ret; + unsigned *data = int_data; + khash_t(ipk) *h; + unsigned k; + + h = kh_init(ipk); + for (i = 0; i < data_size; ++i) { + int_packed_t x; + x.key = data[i]; x.val = i&0xff; + k = kh_put(ipk, h, x, &ret); + if (!ret) kh_del(ipk, h, k); + } + printf("[ht_khash_packed] size: %u (sizeof=%ld)\n", kh_size(h), sizeof(int_packed_t)); + kh_destroy(ipk, h); +} + +void ht_timing(void (*f)(void)) +{ + clock_t t = clock(); + (*f)(); + printf("[ht_timing] %.3lf sec\n", (double)(clock() - t) / CLOCKS_PER_SEC); +} + +int main(int argc, char *argv[]) +{ + if (argc > 1) data_size = atoi(argv[1]); + ht_init_data(); + ht_timing(ht_khash_int); + ht_timing(ht_khash_str); + ht_timing(ht_khash_unpack); + ht_timing(ht_khash_packed); + ht_destroy_data(); + return 0; +} diff --git a/web/server/h2o/libh2o/deps/klib/test/klist_test.c b/web/server/h2o/libh2o/deps/klib/test/klist_test.c new file mode 100644 index 000000000..cd13813df --- /dev/null +++ b/web/server/h2o/libh2o/deps/klib/test/klist_test.c @@ -0,0 +1,19 @@ +#include <stdio.h> +#include "klist.h" + +#define __int_free(x) +KLIST_INIT(32, int, __int_free) + +int main() +{ + klist_t(32) *kl; + kliter_t(32) *p; + kl = kl_init(32); + *kl_pushp(32, kl) = 1; + *kl_pushp(32, kl) = 10; + kl_shift(32, kl, 0); + for (p = kl_begin(kl); p != kl_end(kl); p = kl_next(p)) + printf("%d\n", kl_val(p)); + kl_destroy(32, kl); + return 0; +} diff --git a/web/server/h2o/libh2o/deps/klib/test/kmin_test.c b/web/server/h2o/libh2o/deps/klib/test/kmin_test.c new file mode 100644 index 000000000..33ccd1cbc --- /dev/null +++ b/web/server/h2o/libh2o/deps/klib/test/kmin_test.c @@ -0,0 +1,48 @@ +#include <stdio.h> +#include <math.h> +#include "kmath.h" + +static int n_evals; + +double f_Chebyquad(int n, double *x, void *data) +{ + int i, j; + double y[20][20], f; + int np, iw; + double sum; + for (j = 0; j != n; ++j) { + y[0][j] = 1.; + y[1][j] = 2. * x[j] - 1.; + } + for (i = 1; i != n; ++i) + for (j = 0; j != n; ++j) + y[i+1][j] = 2. * y[1][j] * y[i][j] - y[i-1][j]; + f = 0.; + np = n + 1; + iw = 1; + for (i = 0; i != np; ++i) { + sum = 0.; + for (j = 0; j != n; ++j) sum += y[i][j]; + sum /= n; + if (iw > 0) sum += 1. / ((i - 1) * (i + 1)); + iw = -iw; + f += sum * sum; + } + ++n_evals; + return f; +} + +int main() +{ + double x[20], y; + int n, i; + printf("\nMinimizer: Hooke-Jeeves\n"); + for (n = 2; n <= 8; n += 2) { + for (i = 0; i != n; ++i) x[i] = (double)(i + 1) / n; + n_evals = 0; + y = kmin_hj(f_Chebyquad, n, x, 0, KMIN_RADIUS, KMIN_EPS, KMIN_MAXCALL); + printf("n=%d,min=%.8lg,n_evals=%d\n", n, y, n_evals); + } + printf("\n"); + return 0; +} diff --git a/web/server/h2o/libh2o/deps/klib/test/kseq_bench.c b/web/server/h2o/libh2o/deps/klib/test/kseq_bench.c new file mode 100644 index 000000000..eeda13f71 --- /dev/null +++ b/web/server/h2o/libh2o/deps/klib/test/kseq_bench.c @@ -0,0 +1,69 @@ +#include <zlib.h> +#include <stdio.h> +#include <time.h> +#include <stdint.h> +#include <stdlib.h> +#include "kseq.h" + +#define BUF_SIZE 4096 +KSTREAM_INIT(gzFile, gzread, BUF_SIZE) + +int main(int argc, char *argv[]) +{ + gzFile fp; + clock_t t; + if (argc == 1) { + fprintf(stderr, "Usage: kseq_bench <in.gz>\n"); + return 1; + } + { + uint8_t *buf = malloc(BUF_SIZE); + fp = gzopen(argv[1], "r"); + t = clock(); + while (gzread(fp, buf, BUF_SIZE) > 0); + fprintf(stderr, "[gzread] %.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC); + gzclose(fp); + free(buf); + } + { + kstream_t *ks; + fp = gzopen(argv[1], "r"); + ks = ks_init(fp); + t = clock(); + while (ks_getc(ks) >= 0); + fprintf(stderr, "[ks_getc] %.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC); + ks_destroy(ks); + gzclose(fp); + } + { + kstream_t *ks; + kstring_t *s; + int dret; + s = calloc(1, sizeof(kstring_t)); + fp = gzopen(argv[1], "r"); + ks = ks_init(fp); + t = clock(); + while (ks_getuntil(ks, '\n', s, &dret) >= 0); + fprintf(stderr, "[ks_getuntil] %.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC); + ks_destroy(ks); + gzclose(fp); + free(s->s); free(s); + } + if (argc == 2) { + fp = gzopen(argv[1], "r"); + t = clock(); + while (gzgetc(fp) >= 0); + fprintf(stderr, "[gzgetc] %.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC); + gzclose(fp); + } + if (argc == 2) { + char *buf = malloc(BUF_SIZE); + fp = gzopen(argv[1], "r"); + t = clock(); + while (gzgets(fp, buf, BUF_SIZE) > 0); + fprintf(stderr, "[gzgets] %.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC); + gzclose(fp); + free(buf); + } + return 0; +} diff --git a/web/server/h2o/libh2o/deps/klib/test/kseq_bench2.c b/web/server/h2o/libh2o/deps/klib/test/kseq_bench2.c new file mode 100644 index 000000000..b4154583b --- /dev/null +++ b/web/server/h2o/libh2o/deps/klib/test/kseq_bench2.c @@ -0,0 +1,43 @@ +#include <stdio.h> +#include <time.h> +#include <stdint.h> +#include <stdlib.h> +#include <fcntl.h> +#include "kseq.h" +KSTREAM_INIT(int, read, 4096) + +#define BUF_SIZE 65536 + +int main(int argc, char *argv[]) +{ + clock_t t; + if (argc == 1) { + fprintf(stderr, "Usage: %s <in.txt>\n", argv[0]); + return 1; + } + { + FILE *fp; + char *s; + t = clock(); + s = malloc(BUF_SIZE); + fp = fopen(argv[1], "r"); + while (fgets(s, BUF_SIZE, fp)); + fclose(fp); + fprintf(stderr, "[fgets] %.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC); + } + { + int fd, dret; + kstream_t *ks; + kstring_t s; + t = clock(); + s.l = s.m = 0; s.s = 0; + fd = open(argv[1], O_RDONLY); + ks = ks_init(fd); + while (ks_getuntil(ks, '\n', &s, &dret) >= 0); + free(s.s); + ks_destroy(ks); + close(fd); + fprintf(stderr, "[kstream] %.2f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC); + } + return 0; +} diff --git a/web/server/h2o/libh2o/deps/klib/test/kseq_test.c b/web/server/h2o/libh2o/deps/klib/test/kseq_test.c new file mode 100644 index 000000000..0304dea35 --- /dev/null +++ b/web/server/h2o/libh2o/deps/klib/test/kseq_test.c @@ -0,0 +1,27 @@ +#include <zlib.h> +#include <stdio.h> +#include "kseq.h" +KSEQ_INIT(gzFile, gzread) + +int main(int argc, char *argv[]) +{ + gzFile fp; + kseq_t *seq; + int l; + if (argc == 1) { + fprintf(stderr, "Usage: %s <in.fasta>\n", argv[0]); + return 1; + } + fp = gzopen(argv[1], "r"); + seq = kseq_init(fp); + while ((l = kseq_read(seq)) >= 0) { + printf("name: %s\n", seq->name.s); + if (seq->comment.l) printf("comment: %s\n", seq->comment.s); + printf("seq: %s\n", seq->seq.s); + if (seq->qual.l) printf("qual: %s\n", seq->qual.s); + } + printf("return value: %d\n", l); + kseq_destroy(seq); + gzclose(fp); + return 0; +} diff --git a/web/server/h2o/libh2o/deps/klib/test/kseq_test.dat b/web/server/h2o/libh2o/deps/klib/test/kseq_test.dat new file mode 100644 index 000000000..b774ae289 --- /dev/null +++ b/web/server/h2o/libh2o/deps/klib/test/kseq_test.dat @@ -0,0 +1,12 @@ +>1 +acgtacgtacgtagc +>2 test +acgatcgatc +@3 test2 +cgctagcatagc +cgatatgactta ++ +78wo82usd980 +d88fau + +238ud8 diff --git a/web/server/h2o/libh2o/deps/klib/test/ksort_test.c b/web/server/h2o/libh2o/deps/klib/test/ksort_test.c new file mode 100644 index 000000000..92c7d3d16 --- /dev/null +++ b/web/server/h2o/libh2o/deps/klib/test/ksort_test.c @@ -0,0 +1,104 @@ +#include <stdlib.h> +#include <string.h> +#include <stdio.h> +#include <time.h> +#include "ksort.h" + +KSORT_INIT_GENERIC(int) + +int main(int argc, char *argv[]) +{ + int i, N = 10000000; + int *array, x; + clock_t t1, t2; + if (argc > 1) N = atoi(argv[1]); + array = (int*)malloc(sizeof(int) * N); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + x = ks_ksmall(int, N, array, 10500); + t2 = clock(); + fprintf(stderr, "ksmall [%d]: %.3lf\n", x, (double)(t2-t1)/CLOCKS_PER_SEC); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + ks_introsort(int, N, array); + t2 = clock(); + fprintf(stderr, "introsort [%d]: %.3lf\n", array[10500], (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in introsort!\n"); + exit(1); + } + } + +#ifndef _ALIGNED_ONLY + { // test unaligned ksmall + srand48(11); + unsigned char *a; + int *b; + a = malloc(N * sizeof(int) + 1); + b = (int*)(a + 1); + for (i = 0; i < N; ++i) b[i] = (int)lrand48(); + t1 = clock(); + ks_introsort(int, N, b); + t2 = clock(); + fprintf(stderr, "introsort [%d]: %.3lf (unaligned: 0x%lx) \n", b[10500], (double)(t2-t1)/CLOCKS_PER_SEC, (size_t)b); + } +#endif + + t1 = clock(); + ks_introsort(int, N, array); + t2 = clock(); + fprintf(stderr, "introsort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + ks_combsort(int, N, array); + t2 = clock(); + fprintf(stderr, "combsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in combsort!\n"); + exit(1); + } + } + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + ks_mergesort(int, N, array, 0); + t2 = clock(); + fprintf(stderr, "mergesort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in mergesort!\n"); + exit(1); + } + } + + t1 = clock(); + ks_mergesort(int, N, array, 0); + t2 = clock(); + fprintf(stderr, "mergesort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + ks_heapmake(int, N, array); + ks_heapsort(int, N, array); + t2 = clock(); + fprintf(stderr, "heapsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in heapsort!\n"); + exit(1); + } + } + + free(array); + return 0; +} diff --git a/web/server/h2o/libh2o/deps/klib/test/ksort_test.cc b/web/server/h2o/libh2o/deps/klib/test/ksort_test.cc new file mode 100644 index 000000000..8950d8064 --- /dev/null +++ b/web/server/h2o/libh2o/deps/klib/test/ksort_test.cc @@ -0,0 +1,997 @@ +#include <stdlib.h> +#include <string.h> +#include <stdio.h> +#include <time.h> +#include <algorithm> + +#include "ksort.h" +KSORT_INIT_GENERIC(int) + +using namespace std; + +/********************************** + * BEGIN OF PAUL'S IMPLEMENTATION * + **********************************/ + +/* Attractive Chaos: I have added inline where necessary. */ + +/* +Copyright (c) 2004 Paul Hsieh +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + Redistributions of source code must retain the above copyright notice, + this list of conditions and the following disclaimer. + + Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + Neither the name of sorttest nor the names of its contributors may be + used to endorse or promote products derived from this software without + specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* + +Recommended flags: +------------------ + +Intel C/C++: +icl /O2 /G6 /Qaxi /Qxi /Qip sorttest.c + +WATCOM C/C++: +wcl386 /otexan /6r sorttest.c + +GCC: +gcc -O3 -mcpu=athlon-xp -march=athlon-xp sorttest.c + +MSVC: +cl /O2 /Ot /Og /G6 sorttest.c + +*/ + +static inline void sort2 (int * numbers) { +int tmp; + + if (numbers[0] <= numbers[1]) return; + tmp = numbers[0]; + numbers[0] = numbers[1]; + numbers[1] = tmp; +} + +static inline void sort3 (int * numbers) { +int tmp; + + if (numbers[0] <= numbers[1]) { + if (numbers[1] <= numbers[2]) return; + if (numbers[2] <= numbers[0]) { + tmp = numbers[0]; + numbers[0] = numbers[2]; + numbers[2] = numbers[1]; + numbers[1] = tmp; + return; + } + tmp = numbers[1]; + } else { + tmp = numbers[0]; + if (numbers[0] <= numbers[2]) { + numbers[0] = numbers[1]; + numbers[1] = tmp; + return; + } + if (numbers[2] <= numbers[1]) { + numbers[0] = numbers[2]; + numbers[2] = tmp; + return; + } + numbers[0] = numbers[1]; + } + numbers[1] = numbers[2]; + numbers[2] = tmp; +} + +static inline void sort4 (int * num) { +int tmp; + if (num[0] < num[1]) { + if (num[1] < num[2]) { + if (num[1] < num[3]) { + if (num[2] >= num[3]) { + tmp = num[2]; + num[2] = num[3]; + num[3] = tmp; + } + } else { + tmp = num[1]; + if (num[0] < num[3]) { + num[1] = num[3]; + } else { + num[1] = num[0]; + num[0] = num[3]; + } + num[3] = num[2]; + num[2] = tmp; + } + } else { + if (num[0] < num[2]) { + if (num[2] < num[3]) { + if (num[1] < num[3]) { + tmp = num[1]; + } else { + tmp = num[3]; + num[3] = num[1]; + } + num[1] = num[2]; + num[2] = tmp; + } else { + if (num[0] < num[3]) { + tmp = num[3]; + } else { + tmp = num[0]; + num[0] = num[3]; + } + num[3] = num[1]; + num[1] = tmp; + } + } else { + if (num[0] < num[3]) { + tmp = num[0]; + num[0] = num[2]; + if (num[1] < num[3]) { + num[2] = num[1]; + } else { + num[2] = num[3]; + num[3] = num[1]; + } + num[1] = tmp; + } else { + if (num[2] < num[3]) { + tmp = num[0]; + num[0] = num[2]; + num[2] = tmp; + tmp = num[1]; + num[1] = num[3]; + } else { + tmp = num[1]; + num[1] = num[2]; + num[2] = num[0]; + num[0] = num[3]; + } + num[3] = tmp; + } + } + } + } else { + tmp = num[0]; + if (tmp < num[2]) { + if (tmp < num[3]) { + num[0] = num[1]; + num[1] = tmp; + if (num[2] >= num[3]) { + tmp = num[2]; + num[2] = num[3]; + num[3] = tmp; + } + } else { + if (num[1] < num[3]) { + num[0] = num[1]; + num[1] = num[3]; + } else { + num[0] = num[3]; + } + num[3] = num[2]; + num[2] = tmp; + } + } else { + if (num[1] < num[2]) { + if (num[2] < num[3]) { + num[0] = num[1]; + num[1] = num[2]; + if (tmp < num[3]) { + num[2] = tmp; + } else { + num[2] = num[3]; + num[3] = tmp; + } + } else { + if (num[1] < num[3]) { + num[0] = num[1]; + num[1] = num[3]; + } else { + num[0] = num[3]; + } + num[3] = tmp; + } + } else { + if (num[1] < num[3]) { + num[0] = num[2]; + if (tmp < num[3]) { + num[2] = tmp; + } else { + num[2] = num[3]; + num[3] = tmp; + } + } else { + if (num[2] < num[3]) { + num[0] = num[2]; + num[2] = num[1]; + num[1] = num[3]; + num[3] = tmp; + } else { + num[0] = num[3]; + num[3] = tmp; + tmp = num[1]; + num[1] = num[2]; + num[2] = tmp; + } + } + } + } + } +} + +static inline void sortAlt2 (int * numbers, int * altNumbers) { + if (numbers[0] <= numbers[1]) { + altNumbers[0] = numbers[0]; + altNumbers[1] = numbers[1]; + } else { + altNumbers[0] = numbers[1]; + altNumbers[1] = numbers[0]; + } +} + +static inline void sortAlt3 (int * numbers, int * altNumbers) { + if (numbers[0] <= numbers[1]) { + if (numbers[1] <= numbers[2]) { + altNumbers[0] = numbers[0]; + altNumbers[1] = numbers[1]; + altNumbers[2] = numbers[2]; + } else if (numbers[2] <= numbers[0]) { + altNumbers[0] = numbers[2]; + altNumbers[1] = numbers[0]; + altNumbers[2] = numbers[1]; + } else { + altNumbers[0] = numbers[0]; + altNumbers[1] = numbers[2]; + altNumbers[2] = numbers[1]; + } + } else { + if (numbers[0] <= numbers[2]) { + altNumbers[0] = numbers[1]; + altNumbers[1] = numbers[0]; + altNumbers[2] = numbers[2]; + } else if (numbers[2] <= numbers[1]) { + altNumbers[0] = numbers[2]; + altNumbers[1] = numbers[1]; + altNumbers[2] = numbers[0]; + } else { + altNumbers[0] = numbers[1]; + altNumbers[1] = numbers[2]; + altNumbers[2] = numbers[0]; + } + } +} + +/* + * Insert Sort + */ + +inline void insertSort (int numbers[], int qty) { +int i, j, idx, q4; +int tmp; + + if (qty <= 4) { + if (qty == 4) sort4 (numbers); + else if (qty == 3) sort3 (numbers); + else if (qty == 2) sort2 (numbers); + return; + } + + q4 = qty - 4; + + for (i=0; i < q4; i++) { + idx = i; + for (j=i+1; j < qty; j++) { + if (numbers[j] < numbers[idx]) idx = j; + } + if (idx != i) { + tmp = numbers[idx]; + numbers[idx] = numbers[i]; + numbers[i] = tmp; + } + } + + sort4 (numbers + q4); +} + +/* + * Heap Sort + */ + +/* Assure the heap property for entries from top to last */ +static void siftDown (int numbers[], int top, int last) { +int tmp = numbers[top]; +int maxIdx = top; + + while (last >= (maxIdx += maxIdx)) { + + /* This is where the comparison occurrs and where a sufficiently + good compiler can use a computed conditional result rather + than using control logic. */ + if (maxIdx != last && numbers[maxIdx] < numbers[maxIdx + 1]) maxIdx++; + + if (tmp >= numbers[maxIdx]) break; + numbers[top] = numbers[maxIdx]; + top = maxIdx; + } + numbers[top] = tmp; +} + +/* Peel off the top siftDown operation since its parameters are trivial to + fill in directly (and this saves us some moves.) */ +static void siftDown0 (int numbers[], int last) { +int tmp; + + if (numbers[0] < numbers[1]) { + tmp = numbers[1]; + numbers[1] = numbers[0]; + siftDown (numbers, 1, last); + } else { + tmp = numbers[0]; + } + numbers[0] = numbers[last]; + numbers[last] = tmp; +} + +void heapSort (int numbers[], int qty) { +int i; + + if (qty <= 4) { + if (qty == 4) sort4 (numbers); + else if (qty == 3) sort3 (numbers); + else if (qty == 2) sort2 (numbers); + return; + } + + i = qty / 2; + /* Enforce the heap property for each position in the tree */ + for ( qty--; i > 0; i--) siftDown (numbers, i, qty); + for (i = qty; i > 0; i--) siftDown0 (numbers, i); +} + +/* + * Quick Sort + */ + +static int medianOf3 (int * numbers, int i, int j) { +int tmp; + + if (numbers[0] <= numbers[i]) { + if (numbers[j] <= numbers[0]) return numbers[0]; /* j 0 i */ + if (numbers[i] <= numbers[j]) j = i; /* 0 i j */ + /* 0 j i */ + } else { + if (numbers[0] <= numbers[j]) return numbers[0]; /* i 0 j */ + if (numbers[j] <= numbers[i]) j = i; /* j i 0 */ + /* i j 0 */ + } + tmp = numbers[j]; + numbers[j] = numbers[0]; + numbers[0] = tmp; + return tmp; +} + +static void quickSortRecurse (int * numbers, int left, int right) { +int pivot, lTmp, rTmp; + + qsrStart:; + +#if defined(__GNUC__) + if (right <= left + 8) { + insertSort (numbers + left, right - left + 1); + return; + } +#else + if (right <= left + 3) { + if (right == left + 1) { + sort2 (numbers + left); + } else if (right == left + 2) { + sort3 (numbers + left); + } else if (right == left + 3) { + sort4 (numbers + left); + } + return; + } +#endif + + lTmp = left; + rTmp = right; + + pivot = medianOf3 (numbers + left, (right-left) >> 1, right-1-left); + + goto QStart; + while (1) { + do { + right--; + if (left >= right) goto QEnd; + QStart:; + } while (numbers[right] > pivot); + numbers[left] = numbers[right]; + do { + left++; + if (left >= right) { + left = right; + goto QEnd; + } + } while (numbers[ left] < pivot); + numbers[right] = numbers[left]; + } + QEnd:; + numbers[left] = pivot; + + /* Only recurse the smaller partition */ + + if (left-1 - lTmp <= rTmp - left - 1) { + if (lTmp < left) quickSortRecurse (numbers, lTmp, left-1); + + /* Set up for larger partition */ + left++; + right = rTmp; + } else { + if (rTmp > left) quickSortRecurse (numbers, left+1, rTmp); + + /* Set up for larger partition */ + right = left - 1; + left = lTmp; + } + + /* Rerun with larger partition (recursion not required.) */ + goto qsrStart; +} + +void quickSort (int numbers[], int qty) { + if (qty < 2) return; + quickSortRecurse (numbers, 0, qty - 1); +} + +/* + * Merge Sort + */ + +static void mergesortInPlace (int * numbers, int * altNumbers, int qty); + +/* Perform mergesort, but store results in altNumbers */ + +static void mergesortExchange (int * numbers, int * altNumbers, int qty) { +int half, i0, i1, i; + + if (qty == 2) { + sortAlt2 (numbers, altNumbers); + return; + } + if (qty == 3) { + sortAlt3 (numbers, altNumbers); + return; + } + + half = (qty + 1)/2; + + mergesortInPlace (numbers, altNumbers, half); + mergesortInPlace (numbers + half, altNumbers, qty - half); + + i0 = 0; i1 = half; + + for (i=0; i < qty; i++) { + if (i1 >= qty || (i0 < half && numbers[i0] < numbers[i1])) { + altNumbers[i] = numbers[i0]; + i0++; + } else { + altNumbers[i] = numbers[i1]; + i1++; + } + } +} + +/* Perform mergesort and store results in numbers */ + +static void mergesortInPlace (int * numbers, int * altNumbers, int qty) { +int half, i0, i1, i; + +#if 0 + if (qty == 2) { + sort2 (numbers); + return; + } + if (qty == 3) { + sort3 (numbers); + return; + } + if (qty == 4) { + sort4 (numbers); + return; + } +#else + if (qty <= 12) { + insertSort (numbers, qty); + return; + } +#endif + + half = (qty + 1)/2; + + mergesortExchange (numbers, altNumbers, half); + mergesortExchange (numbers + half, altNumbers + half, qty - half); + + i0 = 0; i1 = half; + + for (i=0; i < qty; i++) { + if (i1 >= qty || (i0 < half && altNumbers[i0] < altNumbers[i1])) { + numbers[i] = altNumbers[i0]; + i0++; + } else { + numbers[i] = altNumbers[i1]; + i1++; + } + } +} + +#include <stdlib.h> + +void mergeSort (int numbers[], int qty) { +int * tmpArray; + + if (qty <= 12) { + insertSort (numbers, qty); + return; + } + + tmpArray = (int *) malloc (qty * sizeof (int)); + mergesortInPlace (numbers, tmpArray, qty); + free (tmpArray); +} + +/******************************** + * END OF PAUL'S IMPLEMENTATION * + ********************************/ + +/************************************************* + *** Implementation 1: faster on sorted arrays *** + *************************************************/ + +#define rstype_t unsigned +#define rskey(x) (x) + +#define RS_MIN_SIZE 64 + +typedef struct { + rstype_t *b, *e; +} rsbucket_t; + +void rs_sort(rstype_t *beg, rstype_t *end, int n_bits, int s) +{ + rstype_t *i; + int size = 1<<n_bits, m = size - 1; + rsbucket_t *k, b[size], *be = b + size; + + for (k = b; k != be; ++k) k->b = k->e = beg; + for (i = beg; i != end; ++i) ++b[rskey(*i)>>s&m].e; + for (k = b + 1; k != be; ++k) + k->e += (k-1)->e - beg, k->b = (k-1)->e; + for (k = b; k != be;) { + if (k->b != k->e) { + rsbucket_t *l; + if ((l = b + (rskey(*k->b)>>s&m)) != k) { + rstype_t tmp = *k->b, swap; + do { + swap = tmp; tmp = *l->b; *l->b++ = swap; + l = b + (rskey(tmp)>>s&m); + } while (l != k); + *k->b++ = tmp; + } else ++k->b; + } else ++k; + } + for (b->b = beg, k = b + 1; k != be; ++k) k->b = (k-1)->e; + if (s) { + s = s > n_bits? s - n_bits : 0; + for (k = b; k != be; ++k) + if (k->e - k->b > RS_MIN_SIZE) rs_sort(k->b, k->e, n_bits, s); + else if (k->e - k->b > 1) + for (i = k->b + 1; i < k->e; ++i) + if (rskey(*i) < rskey(*(i - 1))) { + rstype_t *j, tmp = *i; + for (j = i; j > k->b && rskey(tmp) < rskey(*(j-1)); --j) + *j = *(j - 1); + *j = tmp; + } + } +} + +/************************************************* + *** Implementation 2: faster on random arrays *** + *************************************************/ + +static inline void rs_insertsort(rstype_t *s, rstype_t *t) +{ + rstype_t *i; + for (i = s + 1; i < t; ++i) { + if (rskey(*i) < rskey(*(i - 1))) { + rstype_t *j, tmp = *i; + for (j = i; j > s && rskey(tmp) < rskey(*(j-1)); --j) + *j = *(j - 1); + *j = tmp; + } + } +} +/* +void rs_sort2(rstype_t *beg, rstype_t *end, int n_bits, int s) +{ + int j, size = 1<<n_bits, m = size - 1; + unsigned long c[size]; + rstype_t *i, *b[size], *e[size]; + + for (j = 0; j < size; ++j) c[j] = 0; + for (i = beg; i != end; ++i) ++c[rskey(*i)>>s&m]; + b[0] = e[0] = beg; + for (j = 1; j != size; ++j) b[j] = e[j] = b[j - 1] + c[j - 1]; + for (i = beg, j = 0; i != end;) { + rstype_t tmp = *i, swap; + int x; + for (;;) { + x = rskey(tmp)>>s&m; + if (e[x] == i) break; + swap = tmp; tmp = *e[x]; *e[x]++ = swap; + } + *i++ = tmp; + ++e[x]; + while (j != size && i >= b[j]) ++j; + while (j != size && e[j-1] == b[j]) ++j; + if (i < e[j-1]) i = e[j-1]; + } + if (s) { + s = s > n_bits? s - n_bits : 0; + for (j = 0; j < size; ++j) { + if (c[j] >= RS_MIN_SIZE) rs_sort2(b[j], e[j], n_bits, s); + else if (c[j] >= 2) rs_insertsort(b[j], e[j]); + } + } +} +*/ +void radix_sort(unsigned *array, int offset, int end, int shift) { + int x, y, value, temp; + int last[256] = { 0 }, pointer[256]; + + for (x=offset; x<end; ++x) { + ++last[(array[x] >> shift) & 0xFF]; + } + + last[0] += offset; + pointer[0] = offset; + for (x=1; x<256; ++x) { + pointer[x] = last[x-1]; + last[x] += last[x-1]; + } + + for (x=0; x<256; ++x) { + while (pointer[x] != last[x]) { + value = array[pointer[x]]; + y = (value >> shift) & 0xFF; + while (x != y) { + temp = array[pointer[y]]; + array[pointer[y]++] = value; + value = temp; + y = (value >> shift) & 0xFF; + } + array[pointer[x]++] = value; + } + } + + if (shift > 0) { + shift -= 8; + for (x=0; x<256; ++x) { + temp = x > 0 ? pointer[x] - pointer[x-1] : pointer[0] - offset; + if (temp > 64) { + radix_sort(array, pointer[x] - temp, pointer[x], shift); + } else if (temp > 1) rs_insertsort(array + pointer[x] - temp, array + pointer[x]); + } + } +} +/************************* + *** END OF RADIX SORT *** + *************************/ + +template< class _Type, unsigned long PowerOfTwoRadix, unsigned long Log2ofPowerOfTwoRadix, long Threshold > +inline void _RadixSort_Unsigned_PowerOf2Radix_1( _Type* a, long last, _Type bitMask, unsigned long shiftRightAmount ) +{ + const unsigned long numberOfBins = PowerOfTwoRadix; + unsigned long count[ numberOfBins ]; + for( unsigned long i = 0; i < numberOfBins; i++ ) + count[ i ] = 0; + for ( long _current = 0; _current <= last; _current++ ) // Scan the array and count the number of times each value appears + { + unsigned long digit = (unsigned long)(( a[ _current ] & bitMask ) >> shiftRightAmount ); // extract the digit we are sorting based on + count[ digit ]++; + } + long startOfBin[ numberOfBins ], endOfBin[ numberOfBins ], nextBin; + startOfBin[ 0 ] = endOfBin[ 0 ] = nextBin = 0; + for( unsigned long i = 1; i < numberOfBins; i++ ) + startOfBin[ i ] = endOfBin[ i ] = startOfBin[ i - 1 ] + count[ i - 1 ]; + for ( long _current = 0; _current <= last; ) + { + unsigned long digit; + _Type tmp = a[ _current ]; // get the compiler to recognize that a register can be used for the loop instead of a[_current] memory location + while ( true ) { + digit = (unsigned long)(( tmp & bitMask ) >> shiftRightAmount ); // extract the digit we are sorting based on + if ( endOfBin[ digit ] == _current ) + break; + _Type tmp2; + //_swap( tmp, a[ endOfBin[ digit ] ] ); + tmp2 = a[endOfBin[digit]]; a[endOfBin[digit]] = tmp; tmp = tmp2; + endOfBin[ digit ]++; + } + a[ _current ] = tmp; + endOfBin[ digit ]++; // leave the element at its location and grow the bin + _current++; // advance the current pointer to the next element + while( _current >= startOfBin[ nextBin ] && nextBin < numberOfBins ) + nextBin++; + while( endOfBin[ nextBin - 1 ] == startOfBin[ nextBin ] && nextBin < numberOfBins ) + nextBin++; + if ( _current < endOfBin[ nextBin - 1 ] ) + _current = endOfBin[ nextBin - 1 ]; + } + bitMask >>= Log2ofPowerOfTwoRadix; + if ( bitMask != 0 ) // end recursion when all the bits have been processes + { + if ( shiftRightAmount >= Log2ofPowerOfTwoRadix ) shiftRightAmount -= Log2ofPowerOfTwoRadix; + else shiftRightAmount = 0; + for( unsigned long i = 0; i < numberOfBins; i++ ) + { + long numberOfElements = endOfBin[ i ] - startOfBin[ i ]; + if ( numberOfElements >= Threshold ) // endOfBin actually points to one beyond the bin + _RadixSort_Unsigned_PowerOf2Radix_1< _Type, PowerOfTwoRadix, Log2ofPowerOfTwoRadix, Threshold >( &a[ startOfBin[ i ]], numberOfElements - 1, bitMask, shiftRightAmount ); + else if ( numberOfElements >= 2 ) + rs_insertsort(&a[ startOfBin[ i ]], &a[ endOfBin[ i ]]); + } + } +} +inline void RadixSortInPlace_HybridUnsigned_Radix256( unsigned* a, unsigned long a_size ) +{ + if ( a_size < 2 ) return; + unsigned long bitMask = 0xFF000000; // bitMask controls how many bits we process at a time + unsigned long shiftRightAmount = 24; + if ( a_size >= 32 ) + _RadixSort_Unsigned_PowerOf2Radix_1<unsigned, 256, 8, 32>(a, a_size - 1, bitMask, shiftRightAmount ); + else + rs_insertsort(a, a + a_size); +} + +struct intcmp_t { + inline int operator() (int a, int b) const { + return a < b? -1 : a > b? 1 : 0; + } +}; + +int compare_int(int a, int b) +{ + return a < b? -1 : a > b? 1 : 0; +} +int compare(const void *a, const void *b) +{ + return *((int*)a) - *((int*)b); +} + +int main(int argc, char *argv[]) +{ + int i, N = 50000000; + int *array, *temp; + clock_t t1, t2; + if (argc == 1) fprintf(stderr, "Usage: %s [%d]\n", argv[0], N); + if (argc > 1) N = atoi(argv[1]); + temp = (int*)malloc(sizeof(int) * N); + array = (int*)malloc(sizeof(int) * N); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + rs_sort((unsigned*)array, (unsigned*)array + N, 8, 24); + t2 = clock(); + fprintf(stderr, "radix sort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in radix sort!\n"); + exit(1); + } + } + t1 = clock(); + rs_sort((unsigned*)array, (unsigned*)array + N, 8, 24); + t2 = clock(); + fprintf(stderr, "radix sort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + RadixSortInPlace_HybridUnsigned_Radix256((unsigned*)array, N); +// radix_sort((unsigned*)array, 0, N, 24); + t2 = clock(); + fprintf(stderr, "vd's radix sort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in radix sort!\n"); + exit(1); + } + } + t1 = clock(); + RadixSortInPlace_HybridUnsigned_Radix256((unsigned*)array, N); +// radix_sort((unsigned*)array, 0, N, 24); + t2 = clock(); + fprintf(stderr, "vd's radix sort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + sort(array, array+N); + t2 = clock(); + fprintf(stderr, "STL introsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + t1 = clock(); + sort(array, array+N); + t2 = clock(); + fprintf(stderr, "STL introsort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + stable_sort(array, array+N); + t2 = clock(); + fprintf(stderr, "STL stablesort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + t1 = clock(); + stable_sort(array, array+N); + t2 = clock(); + fprintf(stderr, "STL stablesort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + make_heap(array, array+N); + sort_heap(array, array+N); + t2 = clock(); + fprintf(stderr, "STL heapsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in heap_sort!\n"); + exit(1); + } + } + t1 = clock(); + make_heap(array, array+N); + sort_heap(array, array+N); + t2 = clock(); + fprintf(stderr, "STL heapsort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + ks_combsort(int, N, array); + t2 = clock(); + fprintf(stderr, "combsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in combsort!\n"); + exit(1); + } + } + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + qsort(array, N, sizeof(int), compare); + t2 = clock(); + fprintf(stderr, "libc qsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + ks_introsort(int, N, array); + t2 = clock(); + fprintf(stderr, "my introsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in intro_sort!\n"); + exit(1); + } + } + t1 = clock(); + ks_introsort(int, N, array); + t2 = clock(); + fprintf(stderr, "introsort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + ks_mergesort(int, N, array, 0); + t2 = clock(); + fprintf(stderr, "iterative mergesort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in merge_sort!\n"); + exit(1); + } + } + t1 = clock(); + ks_mergesort(int, N, array, 0); + t2 = clock(); + fprintf(stderr, "iterative mergesort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + ks_heapmake(int, N, array); + ks_heapsort(int, N, array); + t2 = clock(); + fprintf(stderr, "my heapsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in heap_sort!\n"); + exit(1); + } + } + t1 = clock(); + ks_heapmake(int, N, array); + ks_heapsort(int, N, array); + t2 = clock(); + fprintf(stderr, "heapsort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + heapSort(array, N); + t2 = clock(); + fprintf(stderr, "Paul's heapsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in intro_sort!\n"); + exit(1); + } + } + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + quickSort(array, N); + t2 = clock(); + fprintf(stderr, "Paul's quicksort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in intro_sort!\n"); + exit(1); + } + } + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + mergeSort(array, N); + t2 = clock(); + fprintf(stderr, "Paul's mergesort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in intro_sort!\n"); + exit(1); + } + } + + free(array); free(temp); + return 0; +} diff --git a/web/server/h2o/libh2o/deps/klib/test/kstring_bench.c b/web/server/h2o/libh2o/deps/klib/test/kstring_bench.c new file mode 100644 index 000000000..82598e88c --- /dev/null +++ b/web/server/h2o/libh2o/deps/klib/test/kstring_bench.c @@ -0,0 +1,51 @@ +#include <stdio.h> +#include <stdlib.h> +#include <time.h> +#include "kstring.h" + +#define N 10000000 + +int main() +{ + int i; + clock_t t; + kstring_t s, s2; + srand48(11); + s.l = s.m = 0; s.s = 0; + t = clock(); + for (i = 0; i < N; ++i) { + int x = lrand48(); + s.l = 0; + kputw(x, &s); + } + fprintf(stderr, "kputw: %lf\n", (double)(clock() - t) / CLOCKS_PER_SEC); + srand48(11); + t = clock(); + for (i = 0; i < N; ++i) { + int x = lrand48(); + s.l = 0; + ksprintf(&s, "%d", x); + } + fprintf(stderr, "ksprintf: %lf\n", (double)(clock() - t) / CLOCKS_PER_SEC); + + srand48(11); + s2.l = s2.m = 0; s2.s = 0; + t = clock(); + for (i = 0; i < N; ++i) { + int x = lrand48(); + s2.l = s.l = 0; + kputw(x, &s2); + kputs(s2.s, &s); + } + fprintf(stderr, "kputw+kputs: %lf\n", (double)(clock() - t) / CLOCKS_PER_SEC); + srand48(11); + t = clock(); + for (i = 0; i < N; ++i) { + int x = lrand48(); + s2.l = s.l = 0; + kputw(x, &s2); + ksprintf(&s, "%s", s2.s); + } + fprintf(stderr, "kputw+ksprintf: %lf\n", (double)(clock() - t) / CLOCKS_PER_SEC); + return 0; +} diff --git a/web/server/h2o/libh2o/deps/klib/test/kstring_bench2.c b/web/server/h2o/libh2o/deps/klib/test/kstring_bench2.c new file mode 100644 index 000000000..b7707a8ec --- /dev/null +++ b/web/server/h2o/libh2o/deps/klib/test/kstring_bench2.c @@ -0,0 +1,131 @@ +#include <string.h> +#include <stdio.h> +#include <stdlib.h> +#include <time.h> +#include "kstring.h" + +#ifdef __APPLE__ +#define HAVE_STRNSTR +#endif + +#ifdef __linux__ +#define HAVE_MEMMEM +#endif + +static int str_len = 1024*1024*128; +static int pat_len = 30; +static int alphabet = 2; +static int repeat = 50; + +char *gen_data(int len, int a) +{ + char *data; + int i; + long x; + srand48(11); + data = malloc(len); + for (i = 0; i < len; ++i) + data[i] = (int)(a * drand48()) + '!'; + data[str_len - 1] = 0; + return data; +} +// http://srcvault.scali.eu.org/cgi-bin/Syntax/c/BoyerMoore.c +char *BoyerMoore( unsigned char *data, unsigned int dataLength, unsigned char *string, unsigned int strLength ) +{ + unsigned int skipTable[256], i; + unsigned char *search; + register unsigned char lastChar; + + if (strLength == 0) + return NULL; + + for (i = 0; i < 256; i++) + skipTable[i] = strLength; + search = string; + i = --strLength; + do { + skipTable[*search++] = i; + } while (i--); + lastChar = *--search; + search = data + strLength; + dataLength -= strLength+(strLength-1); + while ((int)dataLength > 0 ) { + unsigned int skip; + skip = skipTable[*search]; + search += skip; + dataLength -= skip; + skip = skipTable[*search]; + search += skip; + dataLength -= skip; + skip = skipTable[*search]; + if (*search != lastChar) { + search += skip; + dataLength -= skip; + continue; + } + i = strLength; + do { + if (i-- == 0) return search; + } while (*--search == string[i]); + search += (strLength - i + 1); + dataLength--; + } + return NULL; +} + +int main() +{ + char *data; + int i; + clock_t t; + t = clock(); + data = gen_data(str_len, alphabet); + fprintf(stderr, "Generate data in %.3f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC); + { + t = clock(); srand48(1331); + for (i = 0; i < repeat; ++i) { + int y = lrand48() % (str_len - pat_len); + char *ret; + ret = kmemmem(data, str_len, data + y, pat_len, 0); +// printf("%d, %d\n", (int)(ret - data), y); + } + fprintf(stderr, "Search patterns in %.3f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC); + } + if (1) { + t = clock(); srand48(1331); + for (i = 0; i < repeat; ++i) { + int y = lrand48() % (str_len - pat_len); + char *ret; + ret = BoyerMoore(data, str_len, data + y, pat_len); +// printf("%d, %d\n", (int)(ret - data), y); + } + fprintf(stderr, "Search patterns in %.3f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC); + } +#ifdef HAVE_STRNSTR + if (1) { + char *tmp; + t = clock(); srand48(1331); + tmp = calloc(pat_len+1, 1); + for (i = 0; i < repeat; ++i) { + int y = lrand48() % (str_len - pat_len); + char *ret; + memcpy(tmp, data + y, pat_len); + ret = strnstr(data, tmp, str_len); + } + fprintf(stderr, "Search patterns in %.3f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC); + } +#endif +#ifdef HAVE_MEMMEM + if (1) { + t = clock(); srand48(1331); + for (i = 0; i < repeat; ++i) { + int y = lrand48() % (str_len - pat_len); + char *ret; + ret = memmem(data, str_len, data + y, pat_len); +// printf("%d, %d\n", (int)(ret - data), y); + } + fprintf(stderr, "Search patterns in %.3f sec\n", (float)(clock() - t) / CLOCKS_PER_SEC); + } +#endif + return 0; +} diff --git a/web/server/h2o/libh2o/deps/klib/test/kstring_test.c b/web/server/h2o/libh2o/deps/klib/test/kstring_test.c new file mode 100644 index 000000000..76f9532e7 --- /dev/null +++ b/web/server/h2o/libh2o/deps/klib/test/kstring_test.c @@ -0,0 +1,76 @@ +#include <limits.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "kstring.h" + +int nfail = 0; + +void check(const char *what, const kstring_t *ks, const char *correct) +{ + if (ks->l != strlen(correct) || strcmp(ks->s, correct) != 0) { + fprintf(stderr, "%s produced \"%.*s\" (\"%s\" is correct)\tFAIL\n", what, (int)(ks->l), ks->s, correct); + nfail++; + } +} + +void test_kputw(kstring_t *ks, int n) +{ + char buf[16]; + + ks->l = 0; + kputw(n, ks); + + sprintf(buf, "%d", n); + check("kputw()", ks, buf); +} + +void test_kputl(kstring_t *ks, long n) +{ + char buf[24]; + + ks->l = 0; + kputl(n, ks); + + sprintf(buf, "%ld", n); + check("kputl()", ks, buf); +} + +int main() +{ + kstring_t ks; + + ks.l = ks.m = 0; + ks.s = NULL; + + test_kputw(&ks, 0); + test_kputw(&ks, 1); + test_kputw(&ks, 37); + test_kputw(&ks, 12345); + test_kputw(&ks, -12345); + test_kputw(&ks, INT_MAX); + test_kputw(&ks, -INT_MAX); + test_kputw(&ks, INT_MIN); + + test_kputl(&ks, 0); + test_kputl(&ks, 1); + test_kputl(&ks, 37); + test_kputl(&ks, 12345); + test_kputl(&ks, -12345); + test_kputl(&ks, INT_MAX); + test_kputl(&ks, -INT_MAX); + test_kputl(&ks, INT_MIN); + test_kputl(&ks, LONG_MAX); + test_kputl(&ks, -LONG_MAX); + test_kputl(&ks, LONG_MIN); + + free(ks.s); + + if (nfail > 0) { + fprintf(stderr, "Total failures: %d\n", nfail); + return EXIT_FAILURE; + } + + return EXIT_SUCCESS; +} diff --git a/web/server/h2o/libh2o/deps/klib/test/kthread_test.c b/web/server/h2o/libh2o/deps/klib/test/kthread_test.c new file mode 100644 index 000000000..1b67ed4ea --- /dev/null +++ b/web/server/h2o/libh2o/deps/klib/test/kthread_test.c @@ -0,0 +1,69 @@ +#include <stdio.h> +#include <assert.h> +#include <stdlib.h> +#include <pthread.h> +#if HAVE_CILK +#include <cilk/cilk.h> +#include <cilk/cilk_api.h> +#endif + +typedef struct { + int max_iter, w, h; + double xmin, xmax, ymin, ymax; + int *k; +} global_t; + +static void compute(void *_g, int i, int tid) +{ + global_t *g = (global_t*)_g; + double x, x0 = g->xmin + (g->xmax - g->xmin) * (i%g->w) / g->w; + double y, y0 = g->ymin + (g->ymax - g->ymin) * (i/g->w) / g->h; + int k; + + assert(g->k[i] < 0); + x = x0, y = y0; + for (k = 0; k < g->max_iter; ++k) { + double z = x * y; + x *= x; y *= y; + if (x + y >= 4) break; + x = x - y + x0; + y = z + z + y0; + } + g->k[i] = k; +} + +void kt_for(int n_threads, int n_items, void (*func)(void*,int,int), void *data); + +int main(int argc, char *argv[]) +{ + int i, tmp, tot, type = 0, n_threads = 2; + global_t global = { 10240*100, 800, 600, -2., -1.2, -1.2, 1.2, 0 }; +// global_t global = { 10240*1, 8, 6, -2., -1.2, -1.2, 1.2, 0 }; + + if (argc > 1) { + type = argv[1][0] == 'o'? 2 : argv[1][0] == 'c'? 3 : argv[1][0] == 'n'? 1 : 0; + if (argv[1][0] >= '0' && argv[1][0] <= '9') + n_threads = atoi(argv[1]); + } else { + fprintf(stderr, "Usage: ./a.out [openmp | cilk | #threads]\n"); + } + tot = global.w * global.h; + global.k = calloc(tot, sizeof(int)); + for (i = 0; i < tot; ++i) global.k[i] = -1; + if (type == 0) { + kt_for(n_threads, tot, compute, &global); + } else if (type == 2) { + #pragma omp parallel for + for (i = 0; i < tot; ++i) + compute(&global, i, 0); + } else if (type == 3) { + #if HAVE_CILK + cilk_for (i = 0; i < tot; ++i) + compute(&global, i, 0); + #endif + } + for (i = tmp = 0; i < tot; ++i) tmp += (global.k[i] < 0); + free(global.k); + assert(tmp == 0); + return 0; +} diff --git a/web/server/h2o/libh2o/deps/klib/test/kvec_test.cc b/web/server/h2o/libh2o/deps/klib/test/kvec_test.cc new file mode 100644 index 000000000..1015574e4 --- /dev/null +++ b/web/server/h2o/libh2o/deps/klib/test/kvec_test.cc @@ -0,0 +1,69 @@ +#include <vector> +#include <time.h> +#include <stdio.h> +#include <stdlib.h> +#include "kvec.h" + +int main() +{ + int M = 10, N = 20000000, i, j; + clock_t t; + t = clock(); + for (i = 0; i < M; ++i) { + int *array = (int*)malloc(N * sizeof(int)); + for (j = 0; j < N; ++j) array[j] = j; + free(array); + } + printf("C array, preallocated: %.3f sec\n", + (float)(clock() - t) / CLOCKS_PER_SEC); + t = clock(); + for (i = 0; i < M; ++i) { + int *array = 0, max = 0; + for (j = 0; j < N; ++j) { + if (j == max) { + max = !max? 1 : max << 1; + array = (int*)realloc(array, sizeof(int)*max); + } + array[j] = j; + } + free(array); + } + printf("C array, dynamic: %.3f sec\n", + (float)(clock() - t) / CLOCKS_PER_SEC); + t = clock(); + for (i = 0; i < M; ++i) { + kvec_t(int) array; + kv_init(array); + kv_resize(int, array, N); + for (j = 0; j < N; ++j) kv_a(int, array, j) = j; + kv_destroy(array); + } + printf("C vector, dynamic(kv_a): %.3f sec\n", + (float)(clock() - t) / CLOCKS_PER_SEC); + t = clock(); + for (i = 0; i < M; ++i) { + kvec_t(int) array; + kv_init(array); + for (j = 0; j < N; ++j) + kv_push(int, array, j); + kv_destroy(array); + } + printf("C vector, dynamic(kv_push): %.3f sec\n", + (float)(clock() - t) / CLOCKS_PER_SEC); + t = clock(); + for (i = 0; i < M; ++i) { + std::vector<int> array; + array.reserve(N); + for (j = 0; j < N; ++j) array[j] = j; + } + printf("C++ vector, preallocated: %.3f sec\n", + (float)(clock() - t) / CLOCKS_PER_SEC); + t = clock(); + for (i = 0; i < M; ++i) { + std::vector<int> array; + for (j = 0; j < N; ++j) array.push_back(j); + } + printf("C++ vector, dynamic: %.3f sec\n", + (float)(clock() - t) / CLOCKS_PER_SEC); + return 0; +} |