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       13158 : 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       13158 : 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       60000 :     size_t operator()(int key) { return static_cast<size_t>(key) % 1000; }
      87             :   };
      88             :   PersistentMap<int, int, bad_hash> a(&zone);
      89             :   PersistentMap<int, int, bad_hash> b(&zone);
      90             : 
      91           1 :   int sum_a = 0;
      92           1 :   int sum_b = 0;
      93             : 
      94       30001 :   for (int i = 0; i < 30000; ++i) {
      95       30000 :     int key = small_big_distr(&rand);
      96       30000 :     int value = small_big_distr(&rand);
      97       30000 :     if (rand.NextBool()) {
      98       15130 :       sum_a += value;
      99       15130 :       a.Set(key, a.Get(key) + value);
     100             :     } else {
     101       14870 :       sum_b += value;
     102       14870 :       b.Set(key, b.Get(key) + value);
     103             :     }
     104             :   }
     105             : 
     106           1 :   int sum = sum_a + sum_b;
     107             : 
     108       18204 :   for (auto pair : a) {
     109        9101 :     sum_a -= pair.second;
     110             :   }
     111           2 :   ASSERT_EQ(0, sum_a);
     112             : 
     113       17854 :   for (auto pair : b) {
     114        8926 :     sum_b -= pair.second;
     115             :   }
     116           2 :   ASSERT_EQ(0, sum_b);
     117             : 
     118       17161 :   for (auto triple : a.Zip(b)) {
     119       17160 :     sum -= std::get<1>(triple) + std::get<2>(triple);
     120             :   }
     121           3 :   ASSERT_EQ(0, sum);
     122             : }
     123             : 
     124             : }  // namespace compiler
     125             : }  // namespace internal
     126        7893 : }  // namespace v8