Ninja
hash_collision_bench.cc
Go to the documentation of this file.
00001 // Copyright 2012 Google Inc. All Rights Reserved.
00002 //
00003 // Licensed under the Apache License, Version 2.0 (the "License");
00004 // you may not use this file except in compliance with the License.
00005 // You may obtain a copy of the License at
00006 //
00007 //     http://www.apache.org/licenses/LICENSE-2.0
00008 //
00009 // Unless required by applicable law or agreed to in writing, software
00010 // distributed under the License is distributed on an "AS IS" BASIS,
00011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00012 // See the License for the specific language governing permissions and
00013 // limitations under the License.
00014 
00015 #include "build_log.h"
00016 
00017 #include <algorithm>
00018 using namespace std;
00019 
00020 #include <time.h>
00021 
00022 int random(int low, int high) {
00023   return int(low + (rand() / double(RAND_MAX)) * (high - low) + 0.5);
00024 }
00025 
00026 void RandomCommand(char** s) {
00027   int len = random(5, 100);
00028   *s = new char[len];
00029   for (int i = 0; i < len; ++i)
00030     (*s)[i] = (char)random(32, 127);
00031 }
00032 
00033 int main() {
00034   const int N = 20 * 1000 * 1000;
00035 
00036   // Leak these, else 10% of the runtime is spent destroying strings.
00037   char** commands = new char*[N];
00038   pair<uint64_t, int>* hashes = new pair<uint64_t, int>[N];
00039 
00040   srand((int)time(NULL));
00041 
00042   for (int i = 0; i < N; ++i) {
00043     RandomCommand(&commands[i]);
00044     hashes[i] = make_pair(BuildLog::LogEntry::HashCommand(commands[i]), i);
00045   }
00046 
00047   sort(hashes, hashes + N);
00048 
00049   int num_collisions = 0;
00050   for (int i = 1; i < N; ++i) {
00051     if (hashes[i - 1].first == hashes[i].first) {
00052       if (strcmp(commands[hashes[i - 1].second],
00053                  commands[hashes[i].second]) != 0) {
00054         printf("collision!\n  string 1: '%s'\n  string 2: '%s'\n",
00055                commands[hashes[i - 1].second],
00056                commands[hashes[i].second]);
00057         num_collisions++;
00058       }
00059     }
00060   }
00061   printf("\n\n%d collisions after %d runs\n", num_collisions, N);
00062 }