From 462b26c1cc041a8fa26deb62cf12f1f351a5b2f6 Mon Sep 17 00:00:00 2001 From: Joshua Haberman Date: Wed, 8 Jul 2009 12:06:47 -0700 Subject: Directory restructuring. --- tests/test_table.cc | 276 ++++++++++++++++++++++++++++++++++++++++++++++++++++ tests/test_util.h | 53 ++++++++++ tests/tests.c | 72 ++++++++++++++ 3 files changed, 401 insertions(+) create mode 100644 tests/test_table.cc create mode 100644 tests/test_util.h create mode 100644 tests/tests.c (limited to 'tests') diff --git a/tests/test_table.cc b/tests/test_table.cc new file mode 100644 index 0000000..0337eaa --- /dev/null +++ b/tests/test_table.cc @@ -0,0 +1,276 @@ + +#include "upb_table.h" +#include "test_util.h" +#include +#include +#include +#include +#include +#include +#include +#include + +using std::string; +using std::vector; + +struct inttable_entry { + struct upb_inttable_entry e; + uint32_t value; /* key*2 */ +}; + +struct strtable_entry { + struct upb_strtable_entry e; + int32_t value; /* ASCII Value of first letter */ +}; + +double get_usertime() +{ + struct rusage usage; + getrusage(RUSAGE_SELF, &usage); + return usage.ru_utime.tv_sec + (usage.ru_utime.tv_usec/1000000.0); +} + +struct upb_string *get_upbstring(const string& key) { + static struct upb_string str; + str.ptr = (char*)key.c_str(); + str.byte_len = key.size(); + return &str; +} + +/* num_entries must be a power of 2. */ +void test_strtable(const vector& keys, uint32_t num_to_insert) +{ + /* Initialize structures. */ + struct upb_strtable table; + std::map m; + upb_strtable_init(&table, 0, sizeof(struct strtable_entry)); + std::set all; + for(size_t i = 0; i < num_to_insert; i++) { + const string& key = keys[i]; + all.insert(key); + struct strtable_entry e; + e.value = key[0]; + e.e.key = *get_upbstring(key); + upb_strtable_insert(&table, &e.e); + m[key] = key[0]; + } + + /* Test correctness. */ + for(uint32_t i = 0; i < keys.size(); i++) { + const string& key = keys[i]; + struct upb_string *str = get_upbstring(key); + struct strtable_entry *e = + (struct strtable_entry*)upb_strtable_lookup( &table, str); + if(m.find(key) != m.end()) { /* Assume map implementation is correct. */ + assert(e); + assert(upb_streql(&e->e.key, get_upbstring(key))); + assert(e->value == key[0]); + assert(m[key] == key[0]); + } else { + assert(e == NULL); + } + } + + struct strtable_entry *e; + for(e = (struct strtable_entry*)upb_strtable_begin(&table); e; + e = (struct strtable_entry*)upb_strtable_next(&table, &e->e)) { + string tmp(e->e.key.ptr, e->e.key.byte_len); + std::set::iterator i = all.find(tmp); + assert(i != all.end()); + all.erase(i); + } + assert(all.empty()); + + upb_strtable_free(&table); +} + +/* num_entries must be a power of 2. */ +void test_inttable(int32_t *keys, size_t num_entries) +{ + /* Initialize structures. */ + struct upb_inttable table; + uint32_t largest_key = 0; + std::map m; + __gnu_cxx::hash_map hm; + upb_inttable_init(&table, num_entries, sizeof(struct inttable_entry)); + for(size_t i = 0; i < num_entries; i++) { + int32_t key = keys[i]; + largest_key = max(largest_key, key); + struct inttable_entry e; + e.e.key = key; + e.value = key*2; + upb_inttable_insert(&table, &e.e); + m[key] = key*2; + hm[key] = key*2; + } + + /* Test correctness. */ + for(uint32_t i = 1; i <= largest_key; i++) { + struct inttable_entry *e = (struct inttable_entry*)upb_inttable_lookup( + &table, i, sizeof(struct inttable_entry)); + if(m.find(i) != m.end()) { /* Assume map implementation is correct. */ + assert(e); + assert(e->e.key == i); + assert(e->value == i*2); + assert(m[i] == i*2); + assert(hm[i] == i*2); + } else { + assert(e == NULL); + } + } + + /* Test performance. We only test lookups for keys that are known to exist. */ + uintptr_t x = 0; + const unsigned int iterations = 0xFFFFFF; + const int32_t mask = num_entries - 1; + printf("Measuring sequential loop overhead..."); + fflush(stdout); + double before = get_usertime(); + for(unsigned int i = 0; i < iterations; i++) { + int32_t key = keys[i & mask]; + x += key; + } + double seq_overhead = get_usertime() - before; + printf("%0.3f seconds for %d iterations\n", seq_overhead, iterations); + + printf("Measuring random loop overhead..."); + rand(); + fflush(stdout); + before = get_usertime(); + for(unsigned int i = 0; i < iterations; i++) { + int32_t key = keys[rand() & mask]; + x += key; + } + double rand_overhead = get_usertime() - before; + printf("%0.3f seconds for %d iterations\n", rand_overhead, iterations); + + printf("upb_table(seq): "); + fflush(stdout); + before = get_usertime(); + for(unsigned int i = 0; i < iterations; i++) { + int32_t key = keys[i & mask]; + struct inttable_entry *e = (struct inttable_entry*)upb_inttable_lookup( + &table, key, sizeof(struct inttable_entry)); + x += (uintptr_t)e; + } + double total = get_usertime() - before; + double without_overhead = total - seq_overhead; + printf("%0.3f seconds (%0.3f - %0.3f overhead) for %d iterations. %s/s\n", without_overhead, total, seq_overhead, iterations, eng(iterations/without_overhead, 3, false)); + + printf("upb_table(rand): "); + fflush(stdout); + before = get_usertime(); + for(unsigned int i = 0; i < iterations; i++) { + int32_t key = keys[rand() & mask]; + struct inttable_entry *e = (struct inttable_entry*)upb_inttable_lookup( + &table, key, sizeof(struct inttable_entry)); + x += (uintptr_t)e; + } + total = get_usertime() - before; + without_overhead = total - rand_overhead; + printf("%0.3f seconds (%0.3f - %0.3f overhead) for %d iterations. %s/s\n", without_overhead, total, rand_overhead, iterations, eng(iterations/without_overhead, 3, false)); + + printf("map(seq): "); + fflush(stdout); + before = get_usertime(); + for(unsigned int i = 0; i < iterations; i++) { + int32_t key = keys[i & mask]; + x += m[key]; + } + total = get_usertime() - before; + without_overhead = total - seq_overhead; + printf("%0.3f seconds (%0.3f - %0.3f overhead) for %d iterations. %s/s\n", without_overhead, total, seq_overhead, iterations, eng(iterations/without_overhead, 3, false)); + + printf("map(rand): "); + fflush(stdout); + before = get_usertime(); + for(unsigned int i = 0; i < iterations; i++) { + int32_t key = keys[rand() & mask]; + x += m[key]; + } + total = get_usertime() - before; + without_overhead = total - rand_overhead; + printf("%0.3f seconds (%0.3f - %0.3f overhead) for %d iterations. %s/s\n", without_overhead, total, rand_overhead, iterations, eng(iterations/without_overhead, 3, false)); + + printf("hash_map(seq): "); + fflush(stdout); + before = get_usertime(); + for(unsigned int i = 0; i < iterations; i++) { + int32_t key = keys[i & mask]; + x += hm[key]; + } + total = get_usertime() - before; + without_overhead = total - seq_overhead; + printf("%0.3f seconds (%0.3f - %0.3f overhead) for %d iterations. %s/s\n", without_overhead, total, seq_overhead, iterations, eng(iterations/without_overhead, 3, false)); + + printf("hash_map(rand): "); + fflush(stdout); + before = get_usertime(); + for(unsigned int i = 0; i < iterations; i++) { + int32_t key = keys[rand() & mask]; + x += hm[key]; + } + total = get_usertime() - before; + without_overhead = total - rand_overhead; + printf("%0.3f seconds (%0.3f - %0.3f overhead) for %d iterations. %s/s\n\n", without_overhead, total, rand_overhead, iterations, eng(iterations/without_overhead, 3, false)); + upb_inttable_free(&table); +} + +int32_t *get_contiguous_keys(int32_t num) +{ + int32_t *buf = new int32_t[num]; + for(int32_t i = 0; i < num; i++) + buf[i] = i+1; + return buf; +} + +int main() +{ + vector keys; + keys.push_back("google.protobuf.FileDescriptorSet"); + keys.push_back("google.protobuf.FileDescriptorProto"); + keys.push_back("google.protobuf.DescriptorProto"); + keys.push_back("google.protobuf.DescriptorProto.ExtensionRange"); + keys.push_back("google.protobuf.FieldDescriptorProto"); + keys.push_back("google.protobuf.EnumDescriptorProto"); + keys.push_back("google.protobuf.EnumValueDescriptorProto"); + keys.push_back("google.protobuf.ServiceDescriptorProto"); + keys.push_back("google.protobuf.MethodDescriptorProto"); + keys.push_back("google.protobuf.FileOptions"); + keys.push_back("google.protobuf.MessageOptions"); + keys.push_back("google.protobuf.FieldOptions"); + keys.push_back("google.protobuf.EnumOptions"); + keys.push_back("google.protobuf.EnumValueOptions"); + keys.push_back("google.protobuf.ServiceOptions"); + keys.push_back("google.protobuf.MethodOptions"); + keys.push_back("google.protobuf.UninterpretedOption"); + keys.push_back("google.protobuf.UninterpretedOption.NamePart"); + + test_strtable(keys, 18); + + int32_t *keys1 = get_contiguous_keys(8); + printf("Contiguous 1-8 ====\n"); + test_inttable(keys1, 8); + delete[] keys1; + + int32_t *keys2 = get_contiguous_keys(64); + printf("Contiguous 1-64 ====\n"); + test_inttable(keys2, 64); + delete[] keys2; + + int32_t *keys3 = get_contiguous_keys(512); + printf("Contiguous 1-512 ====\n"); + test_inttable(keys3, 512); + delete[] keys3; + + int32_t *keys4 = new int32_t[64]; + for(int32_t i = 0; i < 64; i++) { + if(i < 32) + keys4[i] = i+1; + else + keys4[i] = 10101+i; + } + printf("1-32 and 10133-10164 ====\n"); + test_inttable(keys4, 64); + delete[] keys4; +} diff --git a/tests/test_util.h b/tests/test_util.h new file mode 100644 index 0000000..a998a19 --- /dev/null +++ b/tests/test_util.h @@ -0,0 +1,53 @@ +/* Function for printing numbers using si prefixes (k, M, G, etc.). + * From http://www.cs.tut.fi/~jkorpela/c/eng.html */ + +#define PREFIX_START (-24) +/* Smallest power of then for which there is a prefix defined. + If the set of prefixes will be extended, change this constant + and update the table "prefix". */ + +#include +#include + +static char *eng(double value, int digits, int numeric) +{ + static const char *prefix[] = { + "y", "z", "a", "f", "p", "n", "u", "m", "", + "k", "M", "G", "T", "P", "E", "Z", "Y" + }; +#define PREFIX_END (PREFIX_START+\ +(int)((sizeof(prefix)/sizeof(char *)-1)*3)) + + int expof10; + static char result[100]; + char *res = result; + + if (value < 0.) + { + *res++ = '-'; + value = -value; + } + + expof10 = (int) log10(value); + if(expof10 > 0) + expof10 = (expof10/3)*3; + else + expof10 = (-expof10+3)/3*(-3); + + value *= pow(10,-expof10); + + if (value >= 1000.) + { value /= 1000.0; expof10 += 3; } + else if(value >= 100.0) + digits -= 2; + else if(value >= 10.0) + digits -= 1; + + if(numeric || (expof10 < PREFIX_START) || + (expof10 > PREFIX_END)) + sprintf(res, "%.*fe%d", digits-1, value, expof10); + else + sprintf(res, "%.*f %s", digits-1, value, + prefix[(expof10-PREFIX_START)/3]); + return result; +} diff --git a/tests/tests.c b/tests/tests.c new file mode 100644 index 0000000..7bc5dde --- /dev/null +++ b/tests/tests.c @@ -0,0 +1,72 @@ + +#include +#include +#include +#include "descriptor.c" +#include "upb_enum.c" +#include "upb_parse.c" +#include "upb_context.c" +#include "upb_msg.c" +#include "upb_table.c" + +void test_get_v_uint64_t() +{ + upb_status_t status; + + uint8_t zero[] = {0x00}; + void *zero_buf = zero; + uint64_t zero_val = 0; + status = get_v_uint64_t(&zero_buf, zero + sizeof(zero), &zero_val); + assert(status == UPB_STATUS_OK); + assert(zero_val == 0); + assert(zero_buf == zero + sizeof(zero)); + + uint8_t one[] = {0x01}; + void *one_buf = one; + uint64_t one_val = 0; + status = get_v_uint64_t(&one_buf, one + sizeof(one), &one_val); + assert(status == UPB_STATUS_OK); + assert(one_val == 1); + assert(one_buf == one + sizeof(one)); + + uint8_t twobyte[] = {0xAC, 0x02}; + void *twobyte_buf = twobyte; + uint64_t twobyte_val = 0; + status = get_v_uint64_t(&twobyte_buf, twobyte + sizeof(twobyte), &twobyte_val); + assert(status == UPB_STATUS_OK); + assert(twobyte_val == 300); + assert(twobyte_buf == twobyte + sizeof(twobyte)); + + uint8_t tenbyte[] = {0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 0x88, 0x89, 0x7F}; + void *tenbyte_buf = tenbyte; + uint64_t tenbyte_val = 0; + status = get_v_uint64_t(&tenbyte_buf, tenbyte + sizeof(tenbyte), &tenbyte_val); + assert(status == UPB_STATUS_OK); + assert(tenbyte_val == 0x89101c305080c101); + assert(tenbyte_buf == tenbyte + sizeof(tenbyte)); + + uint8_t elevenbyte[] = {0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x01}; + void *elevenbyte_buf = elevenbyte; + uint64_t elevenbyte_val = 0; + status = get_v_uint64_t(&elevenbyte_buf, elevenbyte + sizeof(elevenbyte), &elevenbyte_val); + assert(status == UPB_ERROR_UNTERMINATED_VARINT); + status = get_v_uint64_t(&elevenbyte_buf, elevenbyte + sizeof(elevenbyte)-1, &elevenbyte_val); + /* Byte 10 is 0x80, so we know it's unterminated. */ + assert(status == UPB_ERROR_UNTERMINATED_VARINT); + status = get_v_uint64_t(&elevenbyte_buf, elevenbyte + sizeof(elevenbyte)-2, &elevenbyte_val); + assert(status == UPB_STATUS_NEED_MORE_DATA); +} + +void test_upb_context() { + struct upb_context c; + assert(upb_context_init(&c)); + upb_context_free(&c); +} + +int main() +{ + test_get_v_uint64_t(); + test_upb_context(); + printf("All tests passed.\n"); + return 0; +} -- cgit v1.2.3