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

   1 // { dg-options "-std=gnu++11" }
   2 // { dg-options "-DNTESTS=1 -DNSTRINGS=100 -DSTRSIZE=21 -std=gnu++11" { target simulator } }
   3
   4 // Copyright (C) 2010-2015 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   bool test __attribute__((unused)) = true;
  63   unsigned int bits_in_hash_code = sizeof(size_t) * 8;
  64
  65   // We'll iterate through all 256 vals for s[index], leaving the rest
  66   // of s fixed.  Then, for example, out of the 128 times that
  67   // s[index] has its 3rd bit equal to 0 we would like roughly half 1s
  68   // and half 0s in bit 9 of the hash codes.
  69   //
  70   // Bookkeeping: Conceptually we want a 3D array of ints.  We want to
  71   // count the number of times each output position (of which there are
  72   // bits_in_hash_code) is 1 for each bit position within s[index] (of
  73   // which there are 8) and value of that bit (of which there are 2).
  74   const unsigned int jj = 2;
  75   const unsigned int kk = jj * bits_in_hash_code;
  76   const unsigned int array_size = 8 * kk;
  77   vector<int> ones(array_size, 0);
  78
  79   for (int i = 0; i < 256; i++)
  80     {
  81       s[index] = i;
  82       size_t h = hash<string>()(s);
  83       for (int j = 0; h != 0; j++, h >>= 1)
  84         {
  85           if (h & 1)
  86             {
  87               for (int k = 0; k < 8; k++)
  88                 ++ones[k * kk + j * jj + ((i >> k) & 1)];
  89             }
  90         }
  91     }
  92
  93   // At most, the innermost statement in the above loop nest can
  94   // execute 256 * bits_in_hash_code * 8 times.  If the hash is good,
  95   // it'll execute about half that many times, with a pretty even
  96   // spread across the elements of ones[].
  97   VERIFY( 256 * bits_in_hash_code * 8 / array_size == 128 );
  98   int max_ones_possible = 128;
  99   int good = 0, bad = 0;
 100   for (int bit = 0; bit <= 1; bit++)
 101     {
 102       for (unsigned int j = 0; j < bits_in_hash_code; j++)
 103         {
 104           for (int bitpos = 0; bitpos < 8; bitpos++)
 105             {
 106               int z = ones[bitpos * kk + j * jj + bit];
 107               if (z <= max_ones_possible / 6
 108                   || z >= max_ones_possible * 5 / 6)
 109                 {
 110                   // The hash function screwed up, or was just unlucky,
 111                   // as 128 flips of a perfect coin occasionally yield
 112                   // far from 64 heads.
 113                   bad++;
 114                 }
 115               else
 116                 good++;
 117             }
 118         }
 119     }
 120   return good / (double)(good + bad);
 121 }
 122
 123 double
 124 score_from_varying_position(const vector<string>& v, unsigned int index)
 125 {
 126   double score = 0;
 127   for (unsigned int i = 0; i < v.size(); i++)
 128     score += score_from_varying_position(v[i], index);
 129   return score / v.size();
 130 }
 131
 132 double
 133 quality_test(unsigned int num_strings, unsigned int string_size)
 134 {
 135   // Construct random strings.
 136   vector<string> v = random_strings(num_strings, string_size);
 137   double sum_of_scores = 0;
 138   for (unsigned int i = 0; i < string_size; i++)
 139     sum_of_scores += score_from_varying_position(v, i);
 140
 141   // A good hash function should have a score very close to 1, and a bad
 142   // hash function will have a score close to 0.
 143   return sum_of_scores / string_size;
 144 }
 145
 146 void
 147 quality_test()
 148 {
 149   bool test __attribute__((unused)) = true;
 150   srand(137);
 151   double sum_of_scores = 0;
 152   for (unsigned int i = 0; i < num_quality_tests; i++)
 153     {
 154       double score = quality_test(num_strings_for_quality_tests,
 155                                   string_size);
 156       sum_of_scores += score;
 157       VERIFY( score > 0.99 );
 158     }
 159
 160   if (num_quality_tests > 1)
 161     {
 162       double mean_quality = sum_of_scores / num_quality_tests;
 163       VERIFY( mean_quality > 0.9999 );
 164     }
 165 }
 166
 167 int
 168 main()
 169 {
 170   quality_test();
 171   return 0;
 172 }