1 /* Copyright 2016 The TensorFlow Authors. All Rights Reserved. 2 3 Licensed under the Apache License, Version 2.0 (the "License"); 4 you may not use this file except in compliance with the License. 5 You may obtain a copy of the License at 6 7 http://www.apache.org/licenses/LICENSE-2.0 8 9 Unless required by applicable law or agreed to in writing, software 10 distributed under the License is distributed on an "AS IS" BASIS, 11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 See the License for the specific language governing permissions and 13 limitations under the License. 14 ==============================================================================*/ 15 16 #include "tensorflow/core/util/presized_cuckoo_map.h" 17 #include <array> 18 #include "tensorflow/core/platform/env.h" 19 #include "tensorflow/core/platform/fingerprint.h" 20 #include "tensorflow/core/platform/test.h" 21 #include "tensorflow/core/platform/test_benchmark.h" 22 23 namespace tensorflow { 24 namespace { 25 26 TEST(PresizedCuckooMapTest, MultiplyHigh) { 27 struct Testcase { 28 uint64 x; 29 uint64 y; 30 uint64 result; 31 }; 32 std::array<Testcase, 7> testcases{ 33 {{0, 0, 0}, 34 {0xffffffff, 0xffffffff, 0}, 35 {0x2, 0xf000000000000000, 1}, 36 {0x3, 0xf000000000000000, 2}, 37 {0x3, 0xf000000000000001, 2}, 38 {0x3, 0xffffffffffffffff, 2}, 39 {0xffffffffffffffff, 0xffffffffffffffff, 0xfffffffffffffffe}}}; 40 for (auto &tc : testcases) { 41 EXPECT_EQ(tc.result, presized_cuckoo_map::multiply_high_u64(tc.x, tc.y)); 42 } 43 } 44 45 TEST(PresizedCuckooMapTest, Basic) { 46 PresizedCuckooMap<int> pscm(1000); 47 EXPECT_TRUE(pscm.InsertUnique(1, 2)); 48 int out; 49 EXPECT_TRUE(pscm.Find(1, &out)); 50 EXPECT_EQ(out, 2); 51 } 52 53 TEST(PresizedCuckooMapTest, TooManyItems) { 54 static constexpr int kTableSize = 1000; 55 PresizedCuckooMap<int> pscm(kTableSize); 56 for (uint64 i = 0; i < kTableSize; i++) { 57 uint64 key = 58 Fingerprint64(string(reinterpret_cast<char *>(&i), sizeof(int64))); 59 ASSERT_TRUE(pscm.InsertUnique(key, i)); 60 } 61 // Try to over-fill the table. A few of these 62 // inserts will succeed, but should start failing. 63 uint64 failed_at = 0; 64 for (uint64 i = kTableSize; i < (2 * kTableSize); i++) { 65 uint64 key = 66 Fingerprint64(string(reinterpret_cast<char *>(&i), sizeof(int64))); 67 if (!pscm.InsertUnique(key, i)) { 68 failed_at = i; 69 break; 70 } 71 } 72 // Requirement 1: Table must return failure when it's full. 73 EXPECT_NE(failed_at, 0); 74 75 // Requirement 2: Table must preserve all items inserted prior 76 // to the failure. 77 for (uint64 i = 0; i < failed_at; i++) { 78 int out; 79 uint64 key = 80 Fingerprint64(string(reinterpret_cast<char *>(&i), sizeof(int64))); 81 EXPECT_TRUE(pscm.Find(key, &out)); 82 EXPECT_EQ(out, i); 83 } 84 } 85 86 TEST(PresizedCuckooMapTest, ZeroSizeMap) { 87 PresizedCuckooMap<int> pscm(0); 88 int out; 89 for (uint64 i = 0; i < 100; i++) { 90 EXPECT_FALSE(pscm.Find(i, &out)); 91 } 92 } 93 94 TEST(PresizedCuckooMapTest, RepeatedClear) { 95 PresizedCuckooMap<int> pscm(2); 96 int out; 97 for (int i = 0; i < 100; ++i) { 98 pscm.InsertUnique(0, 0); 99 pscm.InsertUnique(1, 1); 100 EXPECT_TRUE(pscm.Find(0, &out)); 101 EXPECT_EQ(0, out); 102 EXPECT_TRUE(pscm.Find(1, &out)); 103 EXPECT_EQ(1, out); 104 pscm.Clear(2); 105 EXPECT_FALSE(pscm.Find(0, &out)); 106 EXPECT_FALSE(pscm.Find(1, &out)); 107 } 108 } 109 110 void RunFill(int64 table_size) { 111 PresizedCuckooMap<int> pscm(table_size); 112 for (int64 i = 0; i < table_size; i++) { 113 uint64 key = 114 Fingerprint64(string(reinterpret_cast<char *>(&i), sizeof(int64))); 115 EXPECT_TRUE(pscm.InsertUnique(key, i)); 116 } 117 for (int64 i = 0; i < table_size; i++) { 118 uint64 key = 119 Fingerprint64(string(reinterpret_cast<char *>(&i), sizeof(int64))); 120 int out; 121 EXPECT_TRUE(pscm.Find(key, &out)); 122 EXPECT_EQ(out, i); 123 } 124 } 125 126 TEST(PresizedCuckooMapTest, Fill) { 127 for (int64 table_size = 10; table_size <= 5000000; table_size *= 71) { 128 RunFill(table_size); 129 } 130 } 131 132 TEST(PresizedCuckooMapTest, Duplicates) { 133 static constexpr int kSmallTableSize = 1000; 134 PresizedCuckooMap<int> pscm(kSmallTableSize); 135 136 for (uint64 i = 0; i < kSmallTableSize; i++) { 137 uint64 key = 138 Fingerprint64(string(reinterpret_cast<char *>(&i), sizeof(uint64))); 139 EXPECT_TRUE(pscm.InsertUnique(key, i)); 140 } 141 142 for (uint64 i = 0; i < kSmallTableSize; i++) { 143 uint64 key = 144 Fingerprint64(string(reinterpret_cast<char *>(&i), sizeof(uint64))); 145 EXPECT_FALSE(pscm.InsertUnique(key, i)); 146 } 147 } 148 149 static void CalculateKeys(uint64 num, std::vector<uint64> *dst) { 150 dst->resize(num); 151 for (uint64 i = 0; i < num; i++) { 152 uint64 key = 153 Fingerprint64(string(reinterpret_cast<char *>(&i), sizeof(uint64))); 154 dst->at(i) = key; 155 } 156 } 157 158 static void BM_CuckooFill(int iters, int arg) { 159 uint64 table_size = arg; 160 testing::StopTiming(); 161 std::vector<uint64> calculated_keys; 162 CalculateKeys(table_size, &calculated_keys); 163 testing::StartTiming(); 164 for (int iter = 0; iter < iters; iter++) { 165 PresizedCuckooMap<int> pscm(table_size); 166 for (uint64 i = 0; i < table_size; i++) { 167 pscm.InsertUnique(calculated_keys[i], i); 168 } 169 } 170 } 171 172 BENCHMARK(BM_CuckooFill)->Arg(1000)->Arg(10000000); 173 174 static void BM_CuckooRead(int iters, int arg) { 175 uint64 table_size = arg; 176 testing::StopTiming(); 177 std::vector<uint64> calculated_keys; 178 CalculateKeys(table_size, &calculated_keys); 179 PresizedCuckooMap<int> pscm(table_size); 180 for (uint64 i = 0; i < table_size; i++) { 181 pscm.InsertUnique(calculated_keys[i], i); 182 } 183 testing::StartTiming(); 184 uint64_t defeat_optimization = 0; 185 for (int i = 0; i < iters; i++) { 186 uint64 key_index = i % table_size; // May slow down bench! 187 int out = 0; 188 pscm.Find(calculated_keys[key_index], &out); 189 defeat_optimization += out; 190 } 191 if (defeat_optimization == 0) { 192 printf("Preventing the compiler from eliding the inner loop\n"); 193 } 194 } 195 196 BENCHMARK(BM_CuckooRead)->Arg(1000)->Arg(10000000); 197 198 } // namespace 199 } // namespace tensorflow 200
