diff options
author | Nico Weber <nicolasweber@gmx.de> | 2012-06-15 16:50:06 (GMT) |
---|---|---|
committer | Nico Weber <nicolasweber@gmx.de> | 2012-06-15 19:57:27 (GMT) |
commit | d59e82c4a098f4e3987871fae0fbd6347b64b1f2 (patch) | |
tree | c831b1d94681da67af479d2a46ad8a7e0f0a2539 /src | |
parent | 5be83d0b2e4909f39998c98dde9a1393d8e5f1c2 (diff) | |
download | Ninja-d59e82c4a098f4e3987871fae0fbd6347b64b1f2.zip Ninja-d59e82c4a098f4e3987871fae0fbd6347b64b1f2.tar.gz Ninja-d59e82c4a098f4e3987871fae0fbd6347b64b1f2.tar.bz2 |
Add a hash collision benchmark.
Diffstat (limited to 'src')
-rw-r--r-- | src/hash_collision_bench.cc | 43 |
1 files changed, 43 insertions, 0 deletions
diff --git a/src/hash_collision_bench.cc b/src/hash_collision_bench.cc new file mode 100644 index 0000000..d9b09d9 --- /dev/null +++ b/src/hash_collision_bench.cc @@ -0,0 +1,43 @@ +#include "build_log.h" + +int random(int low, int high) { + return int(low + (rand() / double(RAND_MAX)) * (high - low) + 0.5); +} + +void RandomCommand(char** s) { + int len = random(5, 100); + *s = new char[len]; + for (int i = 0; i < len; ++i) + (*s)[i] = random(32, 127); +} + +int main() { + const int N = 20 * 1000 * 1000; + + // Leak these, else 10% of the runtime is spent destroying strings. + char** commands = new char*[N]; + pair<uint64_t, int>* hashes = new pair<uint64_t, int>[N]; + + srand(time(NULL)); + + for (int i = 0; i < N; ++i) { + RandomCommand(&commands[i]); + hashes[i] = make_pair(BuildLog::LogEntry::HashCommand(commands[i]), i); + } + + sort(hashes, hashes + N); + + int num_collisions = 0; + for (int i = 1; i < N; ++i) { + if (hashes[i - 1].first == hashes[i].first) { + if (strcmp(commands[hashes[i - 1].second], + commands[hashes[i].second]) != 0) { + printf("collision!\n string 1: '%s'\n string 2: '%s'\n", + commands[hashes[i - 1].second], + commands[hashes[i].second]); + num_collisions++; + } + } + } + printf("\n\n%d collisions after %d runs\n", num_collisions, N); +} |