sc/workben/dpcache/perf-test.cpp

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * Version: MPL 1.1 / GPLv3+ / LGPLv3+
   4  *
   5  * The contents of this file are subject to the Mozilla Public License Version
   6  * 1.1 (the "License"); you may not use this file except in compliance with
   7  * the License or as specified alternatively below. You may obtain a copy of
   8  * the License at http://www.mozilla.org/MPL/
   9  *
  10  * Software distributed under the License is distributed on an "AS IS" basis,
  11  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12  * for the specific language governing rights and limitations under the
  13  * License.
  14  *
  15  * Major Contributor(s):
  16  *   Copyright (C) 2012 Kohei Yoshida <kohei.yoshida@suse.com>
  17  *
  18  * All Rights Reserved.
  19  *
  20  * For minor contributions see the git repository.
  21  *
  22  * Alternatively, the contents of this file may be used under the terms of
  23  * either the GNU General Public License Version 3 or later (the "GPLv3+"), or
  24  * the GNU Lesser General Public License Version 3 or later (the "LGPLv3+"),
  25  * in which case the provisions of the GPLv3+ or the LGPLv3+ are applicable
  26  * instead of those above.
  27  */
  28
  29 #include <cstdlib>
  30 #include <iostream>
  31 #include <stdio.h>
  32 #include <string>
  33 #include <sys/time.h>
  34 #include <vector>
  35 #include <iterator>
  36 #include <algorithm>
  37 #include <functional>
  38
  39 #include <boost/noncopyable.hpp>
  40
  41 using namespace std;
  42
  43 namespace {
  44
  45 class stack_printer
  46 {
  47 public:
  48     explicit stack_printer(const char* msg) :
  49         msMsg(msg)
  50     {
  51         fprintf(stdout, "%s: --begin\n", msMsg.c_str());
  52         mfStartTime = getTime();
  53     }
  54
  55     ~stack_printer()
  56     {
  57         double fEndTime = getTime();
  58         fprintf(stdout, "%s: --end (duration: %g sec)\n", msMsg.c_str(), (fEndTime-mfStartTime));
  59     }
  60
  61     void printTime(int line) const
  62     {
  63         double fEndTime = getTime();
  64         fprintf(stdout, "%s: --(%d) (duration: %g sec)\n", msMsg.c_str(), line, (fEndTime-mfStartTime));
  65     }
  66
  67 private:
  68     double getTime() const
  69     {
  70         timeval tv;
  71         gettimeofday(&tv, NULL);
  72         return tv.tv_sec + tv.tv_usec / 1000000.0;
  73     }
  74
  75     ::std::string msMsg;
  76     double mfStartTime;
  77 };
  78
  79 typedef std::vector<int> values_type;
  80 typedef std::vector<size_t> indices_type;
  81
  82 #if 1
  83 size_t val_count = 6000000;
  84 double multiplier = 300000.0;
  85 bool dump_values = false;
  86 #else
  87 size_t val_count = 20;
  88 double multiplier = 10.0;
  89 bool dump_values = true;
  90 #endif
  91
  92 struct field : boost::noncopyable
  93 {
  94     values_type items;   /// unique values
  95     indices_type data;   /// original value series as indices into unique values.
  96     indices_type order;  /// ascending order of the values as indices.
  97 };
  98
  99 long compare(int left, int right)
 100 {
 101     if (left == right)
 102         return 0;
 103     if (left < right)
 104         return -1;
 105     return 1;
 106 }
 107
 108 bool has_item(const values_type& items, const indices_type& order, int val, long& index)
 109 {
 110     index = items.size();
 111     bool found = false;
 112     long low = 0;
 113     long high = items.size() - 1;
 114     long comp_res;
 115     while (low <= high)
 116     {
 117         long this_index = (low + high) / 2;
 118         comp_res = compare(items[order[this_index]], val);
 119         if (comp_res < 0)
 120             low = this_index + 1;
 121         else
 122         {
 123             high = this_index - 1;
 124             if (comp_res == 0)
 125             {
 126                 found = true;
 127                 low = this_index;
 128             }
 129         }
 130     }
 131     index = low;
 132     return found;
 133 }
 134
 135 bool check_items(const values_type& items)
 136 {
 137     if (items.empty())
 138         return false;
 139
 140     // Items are supposed to be all unique values.
 141     values_type copied(items);
 142     sort(copied.begin(), copied.end());
 143     copied.erase(unique(copied.begin(), copied.end()), copied.end());
 144     return copied.size() == items.size();
 145 }
 146
 147 bool check_order(const values_type& items, const indices_type& order)
 148 {
 149     // Ensure that the order is truly in ascending order.
 150     if (items.size() != order.size())
 151         return false;
 152
 153     if (items.empty())
 154         return false;
 155
 156     indices_type::const_iterator it = order.begin();
 157     values_type::value_type prev = items[*it];
 158     for (++it; it != order.end(); ++it)
 159     {
 160         values_type::value_type val = items[*it];
 161         if (prev >= val)
 162             return false;
 163
 164         prev = val;
 165     }
 166
 167     return true;
 168 }
 169
 170 bool check_data(const values_type& items, const indices_type& data, const values_type& original)
 171 {
 172     if (items.empty() || data.empty() || original.empty())
 173         return false;
 174
 175     if (data.size() != original.size())
 176         return false;
 177
 178     size_t n = data.size();
 179     for (size_t i = 0; i < n; ++i)
 180     {
 181         if (items[data[i]] != original[i])
 182             return false;
 183     }
 184     return true;
 185 }
 186
 187 bool dump_and_check(const field& fld, const values_type& original, bool dump_values)
 188 {
 189     cout << "unique item count:   " << fld.items.size() << endl;
 190     cout << "original data count: " << fld.data.size() << endl;
 191
 192     if (dump_values)
 193     {
 194         cout << "--- items" << endl;
 195         copy(fld.items.begin(), fld.items.end(), ostream_iterator<int>(cout, "\n"));
 196         cout << "--- sorted items" << endl;
 197         {
 198             indices_type::const_iterator it = fld.order.begin(), it_end = fld.order.end();
 199             for (; it != it_end; ++it)
 200             {
 201                 cout << fld.items[*it] << endl;
 202             }
 203         }
 204     }
 205
 206     if (!check_items(fld.items))
 207     {
 208         cout << "item check failed" << endl;
 209         return false;
 210     }
 211
 212     if (!check_order(fld.items, fld.order))
 213     {
 214         cout << "order check failed" << endl;
 215         return false;
 216     }
 217
 218     if (!check_data(fld.items, fld.data, original))
 219     {
 220         cout << "data check failed" << endl;
 221         return false;
 222     }
 223
 224     return true;
 225 }
 226
 227 void run1(const values_type& vals, bool dump_values)
 228 {
 229     field fld;
 230     {
 231         stack_printer __stack_printer__("::run1 (existing algorithm)");
 232         values_type::const_iterator it = vals.begin(), it_end = vals.end();
 233         for (; it != it_end; ++it)
 234         {
 235             long index = 0;
 236             if (!has_item(fld.items, fld.order, *it, index))
 237             {
 238                 // This item doesn't exist in the dimension array yet.
 239                 fld.items.push_back(*it);
 240                 fld.order.insert(
 241                     fld.order.begin()+index, fld.items.size()-1);
 242                 fld.data.push_back(fld.items.size()-1);
 243             }
 244             else
 245                 fld.data.push_back(fld.order[index]);
 246         }
 247     }
 248
 249     bool res = dump_and_check(fld, vals, dump_values);
 250     cout << "check: " << (res ? "success" : "failure") << endl;
 251 }
 252
 253 struct bucket
 254 {
 255     int value;
 256     size_t order_index;
 257     size_t data_index;
 258
 259     bucket(int _value, size_t _order_index, size_t _data_index) :
 260         value(_value), order_index(_order_index), data_index(_data_index) {}
 261
 262     bucket(const bucket& r) :
 263         value(r.value), order_index(r.order_index), data_index(r.data_index) {}
 264 };
 265
 266 void print_buckets(const vector<bucket>& buckets, const char* msg)
 267 {
 268     cout << "--- buckets content (" << msg << ")" << endl;
 269     vector<bucket>::const_iterator it = buckets.begin(), it_end = buckets.end();
 270     for (; it != it_end; ++it)
 271     {
 272         cout << "value: " << it->value << "  order index: " << it->order_index
 273              << "  data index: " << it->data_index << endl;
 274     }
 275     cout << "---" << endl;
 276 }
 277
 278 struct less_by_value : std::binary_function<bucket, bucket, bool>
 279 {
 280     bool operator() (const bucket& left, const bucket& right) const
 281     {
 282         return left.value < right.value;
 283     }
 284 };
 285
 286 struct less_by_data_index : std::binary_function<bucket, bucket, bool>
 287 {
 288     bool operator() (const bucket& left, const bucket& right) const
 289     {
 290         return left.data_index < right.data_index;
 291     }
 292 };
 293
 294 struct equal_by_value : std::binary_function<bucket, bucket, bool>
 295 {
 296     bool operator() (const bucket& left, const bucket& right) const
 297     {
 298         return left.value == right.value;
 299     }
 300 };
 301
 302 class push_back_value : std::unary_function<bucket, void>
 303 {
 304     values_type& items;
 305 public:
 306     push_back_value(values_type& _items) : items(_items) {}
 307     void operator() (const bucket& v)
 308     {
 309         items.push_back(v.value);
 310     }
 311 };
 312
 313 class push_back_order_index : std::unary_function<bucket, void>
 314 {
 315     indices_type& data_indices;
 316 public:
 317     push_back_order_index(indices_type& _items) : data_indices(_items) {}
 318     void operator() (const bucket& v)
 319     {
 320         data_indices.push_back(v.order_index);
 321     }
 322 };
 323
 324 void run2(const values_type& vals, bool dump_values)
 325 {
 326     field fld;
 327     {
 328         stack_printer __stack_printer__("::run2 (alternative algorithm)");
 329         vector<bucket> buckets;
 330         buckets.reserve(vals.size());
 331         {
 332             // Push back all original values.
 333             values_type::const_iterator it = vals.begin(), it_end = vals.end();
 334             for (size_t i = 0; it != it_end; ++it, ++i)
 335                 buckets.push_back(bucket(*it, 0, i));
 336         }
 337
 338         if (buckets.empty())
 339         {
 340             cout << "error: empty buckets" << endl;
 341             return;
 342         }
 343
 344 //      print_buckets(buckets, "original");
 345
 346         // Sort by the value.
 347         sort(buckets.begin(), buckets.end(), less_by_value());
 348
 349 //      print_buckets(buckets, "sorted");
 350
 351         {
 352             // Set order index such that unique values have identical index value.
 353             size_t cur_index = 0;
 354             vector<bucket>::iterator it = buckets.begin(), it_end = buckets.end();
 355             int prev = it->value;
 356             it->order_index = cur_index;
 357             for (++it; it != it_end; ++it)
 358             {
 359                 if (prev != it->value)
 360                     ++cur_index;
 361
 362                 it->order_index = cur_index;
 363                 prev = it->value;
 364             }
 365         }
 366
 367 //      print_buckets(buckets, "sorted and indexed");
 368
 369         // Re-sort the bucket this time by the data index.
 370         sort(buckets.begin(), buckets.end(), less_by_data_index());
 371 //      print_buckets(buckets, "re-sort by data index");
 372
 373         // Copy the order index series into the field object.
 374         fld.data.reserve(buckets.size());
 375         for_each(buckets.begin(), buckets.end(), push_back_order_index(fld.data));
 376
 377         // Sort by the value again.
 378         sort(buckets.begin(), buckets.end(), less_by_value());
 379
 380         // Unique by value.
 381         vector<bucket>::iterator it_unique_end =
 382             unique(buckets.begin(), buckets.end(), equal_by_value());
 383
 384 //      print_buckets(buckets, "uniqued");
 385
 386         // Copy the unique values into items.
 387         vector<bucket>::iterator it_beg = buckets.begin();
 388         size_t len = distance(it_beg, it_unique_end);
 389         fld.items.reserve(len);
 390         for_each(it_beg, it_unique_end, push_back_value(fld.items));
 391
 392         // The items are actually already sorted.  So, just insert a sequence
 393         // of integers from 0 and up.
 394         fld.order.reserve(len);
 395         for (size_t i = 0; i < len; ++i)
 396             fld.order.push_back(i);
 397     }
 398
 399     bool res = dump_and_check(fld, vals, dump_values);
 400     cout << "check: " << (res ? "success" : "failure") << endl;
 401 }
 402
 403 }
 404
 405 int main()
 406 {
 407     values_type vals;
 408     vals.reserve(val_count);
 409
 410     if (dump_values)
 411         cout << "--- original" << endl;
 412
 413     for (size_t i = 0; i < val_count; ++i)
 414     {
 415         double v = rand();
 416         v /= RAND_MAX;
 417         v *= multiplier;
 418         values_type::value_type v2 = v;
 419         vals.push_back(v2);
 420
 421         if (dump_values)
 422             cout << i << ": " << v2 << endl;
 423     }
 424
 425     if (dump_values)
 426         cout << "---" << endl;
 427
 428     run1(vals, dump_values);
 429     run2(vals, dump_values);
 430
 431     return EXIT_SUCCESS;
 432 }
 433
 434 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */