Line data Source code
1 : // Copyright 2017 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #include <tuple>
6 :
7 : #include "src/base/utils/random-number-generator.h"
8 : #include "src/compiler/persistent-map.h"
9 : #include "test/unittests/test-utils.h"
10 :
11 : namespace v8 {
12 : namespace internal {
13 : namespace compiler {
14 :
15 : // A random distribution that produces both small values and arbitrary numbers.
16 209618 : static int small_big_distr(base::RandomNumberGenerator* rand) {
17 419236 : return rand->NextInt() / std::max(1, rand->NextInt() / 100);
18 : }
19 :
20 15188 : TEST(PersistentMap, RefTest) {
21 : base::RandomNumberGenerator rand(92834738);
22 1 : AccountingAllocator allocator;
23 2 : Zone zone(&allocator, ZONE_NAME);
24 : std::vector<PersistentMap<int, int>> pers_maps;
25 1 : pers_maps.emplace_back(&zone);
26 2 : std::vector<std::map<int, int>> ref_maps(1);
27 100001 : for (int i = 0; i < 100000; ++i) {
28 100000 : if (rand.NextInt(2) == 0) {
29 : // Read value;
30 49850 : int key = small_big_distr(&rand);
31 99700 : if (ref_maps[0].count(key) > 0) {
32 14692 : ASSERT_EQ(pers_maps[0].Get(key), ref_maps[0][key]);
33 : } else {
34 85008 : ASSERT_EQ(pers_maps[0].Get(key), 0);
35 : }
36 : }
37 100000 : if (rand.NextInt(2) == 0) {
38 : // Add value;
39 49884 : int key = small_big_distr(&rand);
40 49884 : int value = small_big_distr(&rand);
41 49884 : pers_maps[0].Set(key, value);
42 49884 : ref_maps[0][key] = value;
43 : }
44 100000 : if (rand.NextInt(1000) == 0) {
45 : // Create empty map.
46 74 : pers_maps.emplace_back(&zone);
47 74 : ref_maps.emplace_back();
48 : }
49 100000 : if (rand.NextInt(100) == 0) {
50 : // Copy and move around maps.
51 2014 : int num_maps = static_cast<int>(pers_maps.size());
52 1007 : int source = rand.NextInt(num_maps - 1) + 1;
53 1007 : int target = rand.NextInt(num_maps - 1) + 1;
54 2014 : pers_maps[target] = std::move(pers_maps[0]);
55 2014 : ref_maps[target] = std::move(ref_maps[0]);
56 2014 : pers_maps[0] = pers_maps[source];
57 1007 : ref_maps[0] = ref_maps[source];
58 : }
59 : }
60 227 : for (size_t i = 0; i < pers_maps.size(); ++i) {
61 : std::set<int> keys;
62 117660 : for (auto pair : pers_maps[i]) {
63 117510 : ASSERT_EQ(keys.count(pair.first), 0u);
64 : keys.insert(pair.first);
65 117510 : ASSERT_EQ(ref_maps[i][pair.first], pair.second);
66 : }
67 39498 : for (auto pair : ref_maps[i]) {
68 78546 : int value = pers_maps[i].Get(pair.first);
69 39273 : ASSERT_EQ(pair.second, value);
70 39273 : if (value != 0) {
71 117510 : ASSERT_EQ(keys.count(pair.first), 1u);
72 : keys.erase(pair.first);
73 : }
74 : }
75 75 : ASSERT_TRUE(keys.empty());
76 1 : }
77 : }
78 :
79 15188 : TEST(PersistentMap, Zip) {
80 : base::RandomNumberGenerator rand(92834738);
81 1 : AccountingAllocator allocator;
82 2 : Zone zone(&allocator, ZONE_NAME);
83 :
84 : // Provoke hash collisions to stress the iterator.
85 : struct bad_hash {
86 : size_t operator()(uint32_t key) {
87 94320 : return base::hash_value(static_cast<size_t>(key) % 1000);
88 : }
89 : };
90 : PersistentMap<int, uint32_t, bad_hash> a(&zone);
91 : PersistentMap<int, uint32_t, bad_hash> b(&zone);
92 :
93 1 : uint32_t sum_a = 0;
94 1 : uint32_t sum_b = 0;
95 :
96 30001 : for (int i = 0; i < 30000; ++i) {
97 30000 : int key = small_big_distr(&rand);
98 30000 : uint32_t value = small_big_distr(&rand);
99 30000 : if (rand.NextBool()) {
100 15130 : sum_a += value;
101 15130 : a.Set(key, a.Get(key) + value);
102 : } else {
103 14870 : sum_b += value;
104 14870 : b.Set(key, b.Get(key) + value);
105 : }
106 : }
107 :
108 1 : uint32_t sum = sum_a + sum_b;
109 :
110 18204 : for (auto pair : a) {
111 9101 : sum_a -= pair.second;
112 : }
113 2 : ASSERT_EQ(0u, sum_a);
114 :
115 17854 : for (auto pair : b) {
116 8926 : sum_b -= pair.second;
117 : }
118 2 : ASSERT_EQ(0u, sum_b);
119 :
120 17161 : for (auto triple : a.Zip(b)) {
121 17160 : int key = std::get<0>(triple);
122 17160 : uint32_t value_a = std::get<1>(triple);
123 17160 : uint32_t value_b = std::get<2>(triple);
124 34320 : ASSERT_EQ(value_a, a.Get(key));
125 34320 : ASSERT_EQ(value_b, b.Get(key));
126 17160 : sum -= value_a;
127 17160 : sum -= value_b;
128 : }
129 3 : ASSERT_EQ(0u, sum);
130 : }
131 :
132 : } // namespace compiler
133 : } // namespace internal
134 9111 : } // namespace v8
|