libstdc++-v3/testsuite/20_util/hash/quality.cc

   1 // { dg-options "-DNTESTS=1 -DNSTRINGS=100 -DSTRSIZE=21" { target simulator } }
   2 // { dg-do run { target c++11 } }
   3
   4 // Copyright (C) 2010-2021 Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 3, or (at your option)
  10 // any later version.
  11 //
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16 //
  17 // You should have received a copy of the GNU General Public License
  18 // along with this library; see the file COPYING3.  If not see
  19 // <http://www.gnu.org/licenses/>.
  20
  21 #include <cstdlib>
  22 #include <unordered_set>
  23 #include <string>
  24 #include <functional>
  25 #include <vector>
  26 #include <testsuite_hooks.h>
  27
  28 using namespace std;
  29
  30 #ifndef NTESTS
  31 #define NTESTS 5
  32 #endif
  33 #ifndef NSTRINGS
  34 #define NSTRINGS 200
  35 #endif
  36 #ifndef STRSIZE
  37 #define STRSIZE 42
  38 #endif
  39
  40 const unsigned int num_quality_tests = NTESTS;
  41 const unsigned int num_strings_for_quality_tests = NSTRINGS;
  42 const unsigned int string_size = STRSIZE;
  43
  44 vector<string>
  45 random_strings(unsigned int n, unsigned int len)
  46 {
  47   string s(len, '\0');
  48   unordered_set<string> result_set;
  49   while (result_set.size() < n)
  50     {
  51       result_set.insert(s);
  52       unsigned int tmp = rand();
  53       tmp %= len * 256;
  54       s[tmp / 256] = tmp % 256;
  55     }
  56   return vector<string>(result_set.begin(), result_set.end());
  57 }
  58
  59 double
  60 score_from_varying_position(string s, unsigned int index)
  61 {
  62   unsigned int bits_in_hash_code = sizeof(size_t) * 8;
  63
  64   // We'll iterate through all 256 vals for s[index], leaving the rest
  65   // of s fixed.  Then, for example, out of the 128 times that
  66   // s[index] has its 3rd bit equal to 0 we would like roughly half 1s
  67   // and half 0s in bit 9 of the hash codes.
  68   //
  69   // Bookkeeping: Conceptually we want a 3D array of ints.  We want to
  70   // count the number of times each output position (of which there are
  71   // bits_in_hash_code) is 1 for each bit position within s[index] (of
  72   // which there are 8) and value of that bit (of which there are 2).
  73   const unsigned int jj = 2;
  74   const unsigned int kk = jj * bits_in_hash_code;
  75   const unsigned int array_size = 8 * kk;
  76   vector<int> ones(array_size, 0);
  77
  78   for (int i = 0; i < 256; i++)
  79     {
  80       s[index] = i;
  81       size_t h = hash<string>()(s);
  82       for (int j = 0; h != 0; j++, h >>= 1)
  83         {
  84           if (h & 1)
  85             {
  86               for (int k = 0; k < 8; k++)
  87                 ++ones[k * kk + j * jj + ((i >> k) & 1)];
  88             }
  89         }
  90     }
  91
  92   // At most, the innermost statement in the above loop nest can
  93   // execute 256 * bits_in_hash_code * 8 times.  If the hash is good,
  94   // it'll execute about half that many times, with a pretty even
  95   // spread across the elements of ones[].
  96   VERIFY( 256 * bits_in_hash_code * 8 / array_size == 128 );
  97   int max_ones_possible = 128;
  98   int good = 0, bad = 0;
  99   for (int bit = 0; bit <= 1; bit++)
 100     {
 101       for (unsigned int j = 0; j < bits_in_hash_code; j++)
 102         {
 103           for (int bitpos = 0; bitpos < 8; bitpos++)
 104             {
 105               int z = ones[bitpos * kk + j * jj + bit];
 106               if (z <= max_ones_possible / 6
 107                   || z >= max_ones_possible * 5 / 6)
 108                 {
 109                   // The hash function screwed up, or was just unlucky,
 110                   // as 128 flips of a perfect coin occasionally yield
 111                   // far from 64 heads.
 112                   bad++;
 113                 }
 114               else
 115                 good++;
 116             }
 117         }
 118     }
 119   return good / (double)(good + bad);
 120 }
 121
 122 double
 123 score_from_varying_position(const vector<string>& v, unsigned int index)
 124 {
 125   double score = 0;
 126   for (unsigned int i = 0; i < v.size(); i++)
 127     score += score_from_varying_position(v[i], index);
 128   return score / v.size();
 129 }
 130
 131 double
 132 quality_test(unsigned int num_strings, unsigned int string_size)
 133 {
 134   // Construct random strings.
 135   vector<string> v = random_strings(num_strings, string_size);
 136   double sum_of_scores = 0;
 137   for (unsigned int i = 0; i < string_size; i++)
 138     sum_of_scores += score_from_varying_position(v, i);
 139
 140   // A good hash function should have a score very close to 1, and a bad
 141   // hash function will have a score close to 0.
 142   return sum_of_scores / string_size;
 143 }
 144
 145 void
 146 quality_test()
 147 {
 148   srand(137);
 149   double sum_of_scores = 0;
 150   for (unsigned int i = 0; i < num_quality_tests; i++)
 151     {
 152       double score = quality_test(num_strings_for_quality_tests,
 153                                   string_size);
 154       sum_of_scores += score;
 155       VERIFY( score > 0.99 );
 156     }
 157
 158   if (num_quality_tests > 1)
 159     {
 160       double mean_quality = sum_of_scores / num_quality_tests;
 161       VERIFY( mean_quality > 0.9999 );
 162     }
 163 }
 164
 165 int
 166 main()
 167 {
 168   quality_test();
 169   return 0;
 170 }