Test collision problem with multiple mod steps (IMPALA-219)
| 29 | |
| 30 | // Test collision problem with multiple mod steps (IMPALA-219) |
| 31 | int main(int argc, char **argv) { |
| 32 | google::InitGoogleLogging(argv[0]); |
| 33 | CpuInfo::Init(); |
| 34 | |
| 35 | int num_buckets1 = 16; |
| 36 | int num_buckets2 = 1024; |
| 37 | int num_values = num_buckets1 * num_buckets2; |
| 38 | |
| 39 | int num_collisions1 = 0; |
| 40 | int num_collisions2 = 0; |
| 41 | int num_empty2 = num_buckets2; |
| 42 | vector<bool> buckets1; |
| 43 | vector<bool> buckets2; |
| 44 | buckets1.resize(num_buckets1); |
| 45 | buckets2.resize(num_buckets2); |
| 46 | |
| 47 | // First test using the same hash fn both times |
| 48 | for (int i = 0; i < num_values; ++i) { |
| 49 | uint32_t hash1 = HashUtil::Hash(&i, sizeof(int), 0) >> 8; |
| 50 | uint32_t hash2 = HashUtil::Hash(&i, sizeof(int), 1) >> 8; |
| 51 | uint32_t bucket1_idx = hash1 % num_buckets1; |
| 52 | if (buckets1[bucket1_idx]) ++num_collisions1; |
| 53 | buckets1[bucket1_idx] = true; |
| 54 | |
| 55 | LOG(ERROR) << i << ":" << hash1 << ":" << hash2; |
| 56 | // If they matched bucket 0, put it into buckets2 |
| 57 | if (bucket1_idx == 0) { |
| 58 | uint32_t bucket2_idx = hash2 % num_buckets2; |
| 59 | if (buckets2[bucket2_idx]) { |
| 60 | ++num_collisions2; |
| 61 | } else { |
| 62 | buckets2[bucket2_idx] = true; |
| 63 | --num_empty2; |
| 64 | } |
| 65 | } |
| 66 | } |
| 67 | |
| 68 | LOG(ERROR) << "Same hash:" << endl |
| 69 | << " Bucket 1 Collisions: " << num_collisions1 << endl |
| 70 | << " Expected 1 Collisions: " << num_values - num_buckets1 << endl |
| 71 | << " Bucket 2 Collisions: " << num_collisions2 << endl |
| 72 | << " Bucket 2 Empties: " << num_empty2 << endl |
| 73 | << " Bucket 2 Total Values: " << num_values / num_buckets1; |
| 74 | |
| 75 | return 0; |
| 76 | } |