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       15443 : TEST(PersistentMap, RefTest) {
      21             :   base::RandomNumberGenerator rand(92834738);
      22           2 :   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      200001 :   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       49850 :       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        1007 :       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             :       ref_maps[target] = std::move(ref_maps[0]);
      56        2014 :       pers_maps[0] = pers_maps[source];
      57             :       ref_maps[0] = ref_maps[source];
      58             :     }
      59             :   }
      60         151 :   for (size_t i = 0; i < pers_maps.size(); ++i) {
      61             :     std::set<int> keys;
      62      117585 :     for (auto pair : pers_maps[i]) {
      63      117510 :       ASSERT_EQ(keys.count(pair.first), 0u);
      64             :       keys.insert(pair.first);
      65       78340 :       ASSERT_EQ(ref_maps[i][pair.first], pair.second);
      66             :     }
      67       39348 :     for (auto pair : ref_maps[i]) {
      68       39273 :       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             :   }
      77             : }
      78             : 
      79       15443 : TEST(PersistentMap, Zip) {
      80             :   base::RandomNumberGenerator rand(92834738);
      81           2 :   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       60001 :   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       18203 :   for (auto pair : a) {
     111        9101 :     sum_a -= pair.second;
     112             :   }
     113           2 :   ASSERT_EQ(0u, sum_a);
     114             : 
     115       17853 :   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           2 :   ASSERT_EQ(0u, sum);
     130             : }
     131             : 
     132             : }  // namespace compiler
     133             : }  // namespace internal
     134        9264 : }  // namespace v8