libs/unordered/test/unordered/unnecessary_copy_tests.cpp

   1
   2 // Copyright 2006-2009 Daniel James.
   3 // Distributed under the Boost Software License, Version 1.0. (See accompanying
   4 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   5
   6 // clang-format off
   7 #include "../helpers/prefix.hpp"
   8 #include <boost/unordered_set.hpp>
   9 #include <boost/unordered_map.hpp>
  10 #include "../helpers/postfix.hpp"
  11 // clang-format on
  12
  13 #include <iostream>
  14 #include "../helpers/test.hpp"
  15
  16 namespace unnecessary_copy_tests {
  17 struct count_copies
  18 {
  19   private:
  20     BOOST_COPYABLE_AND_MOVABLE(count_copies)
  21   public:
  22     static int copies;
  23     static int moves;
  24     static int id_count;
  25
  26     count_copies() : tag_(0), id_(++id_count)
  27     {
  28         ++copies;
  29         trace_op("Default construct");
  30     }
  31
  32     explicit count_copies(int tag) : tag_(tag), id_(++id_count)
  33     {
  34         ++copies;
  35         trace_op("Tag construct");
  36     }
  37
  38     // This bizarre constructor is an attempt to confuse emplace.
  39     //
  40     // unordered_map<count_copies, count_copies> x:
  41     // x.emplace(count_copies(1), count_copies(2));
  42     // x.emplace(count_copies(1), count_copies(2), count_copies(3));
  43     //
  44     // The first emplace should use the single argument constructor twice.
  45     // The second emplace should use the single argument contructor for
  46     // the key, and this constructor for the value.
  47     count_copies(count_copies const&, count_copies const& x)
  48         : tag_(x.tag_), id_(++id_count)
  49     {
  50         ++copies;
  51         trace_op("Pair construct");
  52     }
  53
  54     count_copies(count_copies const& x) : tag_(x.tag_), id_(++id_count)
  55     {
  56         ++copies;
  57         trace_op("Copy construct");
  58     }
  59
  60     count_copies(BOOST_RV_REF(count_copies) x) : tag_(x.tag_), id_(++id_count)
  61     {
  62         x.tag_ = -1;
  63         ++moves;
  64         trace_op("Move construct");
  65     }
  66
  67     count_copies& operator=(
  68         BOOST_COPY_ASSIGN_REF(count_copies) p) // Copy assignment
  69     {
  70         tag_ = p.tag_;
  71         ++copies;
  72         trace_op("Copy assign");
  73         return *this;
  74     }
  75
  76     count_copies& operator=(BOOST_RV_REF(count_copies) p) // Move assignment
  77     {
  78         tag_ = p.tag_;
  79         ++moves;
  80         trace_op("Move assign");
  81         return *this;
  82     }
  83
  84     ~count_copies() { trace_op("Destruct"); }
  85
  86     void trace_op(char const* str)
  87     {
  88         BOOST_LIGHTWEIGHT_TEST_OSTREAM << str << ": " << tag_ << " (#" << id_
  89                                        << ")" << std::endl;
  90     }
  91
  92     int tag_;
  93     int id_;
  94 };
  95
  96 bool operator==(count_copies const& x, count_copies const& y)
  97 {
  98     return x.tag_ == y.tag_;
  99 }
 100
 101 template <class T> T source() { return T(); }
 102
 103 void reset()
 104 {
 105     count_copies::copies = 0;
 106     count_copies::moves = 0;
 107
 108     BOOST_LIGHTWEIGHT_TEST_OSTREAM << "\nReset\n" << std::endl;
 109 }
 110 }
 111
 112 #if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
 113 namespace boost
 114 #else
 115 namespace unnecessary_copy_tests
 116 #endif
 117 {
 118 std::size_t hash_value(unnecessary_copy_tests::count_copies const& x)
 119 {
 120     return static_cast<std::size_t>(x.tag_);
 121 }
 122 }
 123
 124 // Boost.Move doesn't seem to work very well on this compiler.
 125 // For example for:
 126 //
 127 //     T x;
 128 //
 129 // It will default construct T, and then move it in.
 130 // For 'T const' it seems to copy.
 131
 132 #if defined(__IBMCPP__) && __IBMCPP__ <= 1210
 133 #define EXTRA_CONSTRUCT_COST 1
 134 #else
 135 #define EXTRA_CONSTRUCT_COST 0
 136 #endif
 137
 138 #define COPY_COUNT(n)                                                          \
 139     if (::unnecessary_copy_tests::count_copies::copies != n) {                 \
 140         BOOST_ERROR("Wrong number of copies.");                                \
 141         std::cerr << "Number of copies: "                                      \
 142                   << ::unnecessary_copy_tests::count_copies::copies            \
 143                   << " expecting: " << n << std::endl;                         \
 144     }
 145 #define MOVE_COUNT(n)                                                          \
 146     if (::unnecessary_copy_tests::count_copies::moves != n) {                  \
 147         BOOST_ERROR("Wrong number of moves.");                                 \
 148         std::cerr << "Number of moves: "                                       \
 149                   << ::unnecessary_copy_tests::count_copies::moves             \
 150                   << " expecting: " << n << std::endl;                         \
 151     }
 152 #define COPY_COUNT_RANGE(a, b)                                                 \
 153     if (::unnecessary_copy_tests::count_copies::copies < a ||                  \
 154         ::unnecessary_copy_tests::count_copies::copies > b) {                  \
 155         BOOST_ERROR("Wrong number of copies.");                                \
 156         std::cerr << "Number of copies: "                                      \
 157                   << ::unnecessary_copy_tests::count_copies::copies            \
 158                   << " expecting: [" << a << ", " << b << "]" << std::endl;    \
 159     }
 160 #define MOVE_COUNT_RANGE(a, b)                                                 \
 161     if (::unnecessary_copy_tests::count_copies::moves < a ||                   \
 162         ::unnecessary_copy_tests::count_copies::moves > b) {                   \
 163         BOOST_ERROR("Wrong number of moves.");                                 \
 164         std::cerr << "Number of moves: "                                       \
 165                   << ::unnecessary_copy_tests::count_copies::moves             \
 166                   << " expecting: [" << a << ", " << b << "]" << std::endl;    \
 167     }
 168 #define COPY_COUNT_EXTRA(a, b) COPY_COUNT_RANGE(a, a + b * EXTRA_CONSTRUCT_COST)
 169 #define MOVE_COUNT_EXTRA(a, b) MOVE_COUNT_RANGE(a, a + b * EXTRA_CONSTRUCT_COST)
 170
 171 namespace unnecessary_copy_tests {
 172 int count_copies::copies;
 173 int count_copies::moves;
 174 int count_copies::id_count;
 175
 176 template <class T> void unnecessary_copy_insert_test(T*)
 177 {
 178     T x;
 179     BOOST_DEDUCED_TYPENAME T::value_type a;
 180     reset();
 181     x.insert(a);
 182     COPY_COUNT(1);
 183 }
 184
 185 boost::unordered_set<count_copies>* set;
 186 boost::unordered_multiset<count_copies>* multiset;
 187 boost::unordered_map<int, count_copies>* map;
 188 boost::unordered_multimap<int, count_copies>* multimap;
 189
 190 UNORDERED_TEST(unnecessary_copy_insert_test, ((set)(multiset)(map)(multimap)))
 191
 192 template <class T> void unnecessary_copy_emplace_test(T*)
 193 {
 194     reset();
 195     T x;
 196     BOOST_DEDUCED_TYPENAME T::value_type a;
 197     COPY_COUNT(1);
 198     x.emplace(a);
 199     COPY_COUNT(2);
 200 }
 201
 202 template <class T> void unnecessary_copy_emplace_rvalue_test(T*)
 203 {
 204     reset();
 205     T x;
 206     x.emplace(source<BOOST_DEDUCED_TYPENAME T::value_type>());
 207 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
 208     COPY_COUNT(1);
 209 #else
 210     COPY_COUNT(2);
 211 #endif
 212 }
 213
 214 UNORDERED_TEST(unnecessary_copy_emplace_test, ((set)(multiset)(map)(multimap)))
 215 UNORDERED_TEST(
 216     unnecessary_copy_emplace_rvalue_test, ((set)(multiset)(map)(multimap)))
 217
 218 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
 219 template <class T> void unnecessary_copy_emplace_std_move_test(T*)
 220 {
 221     reset();
 222     T x;
 223     BOOST_DEDUCED_TYPENAME T::value_type a;
 224     COPY_COUNT(1);
 225     MOVE_COUNT(0);
 226     x.emplace(std::move(a));
 227     COPY_COUNT(1);
 228     MOVE_COUNT(1);
 229 }
 230
 231 UNORDERED_TEST(
 232     unnecessary_copy_emplace_std_move_test, ((set)(multiset)(map)(multimap)))
 233 #endif
 234
 235 template <class T> void unnecessary_copy_emplace_boost_move_test(T*)
 236 {
 237     reset();
 238     T x;
 239     BOOST_DEDUCED_TYPENAME T::value_type a;
 240     COPY_COUNT(1);
 241     MOVE_COUNT_EXTRA(0, 1);
 242     x.emplace(boost::move(a));
 243 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
 244     COPY_COUNT(1);
 245     MOVE_COUNT(1);
 246 #else
 247     // Since std::pair isn't movable, move only works for sets.
 248     COPY_COUNT_RANGE(1, 2);
 249     MOVE_COUNT_RANGE(0, 1);
 250 #endif
 251 }
 252
 253 UNORDERED_TEST(
 254     unnecessary_copy_emplace_boost_move_test, ((set)(multiset)(map)(multimap)))
 255
 256 template <class T> void unnecessary_copy_emplace_boost_move_set_test(T*)
 257 {
 258     reset();
 259     T x;
 260     BOOST_DEDUCED_TYPENAME T::value_type a;
 261     COPY_COUNT(1);
 262     MOVE_COUNT(0);
 263     x.emplace(boost::move(a));
 264     COPY_COUNT(1);
 265     MOVE_COUNT(1);
 266 }
 267
 268 UNORDERED_TEST(unnecessary_copy_emplace_boost_move_set_test, ((set)(multiset)))
 269
 270 template <class T> void unnecessary_copy_emplace_boost_move_map_test(T*)
 271 {
 272     reset();
 273     T x;
 274     COPY_COUNT(0);
 275     MOVE_COUNT(0);
 276     BOOST_DEDUCED_TYPENAME T::value_type a;
 277     COPY_COUNT(1);
 278     MOVE_COUNT_EXTRA(0, 1);
 279     x.emplace(boost::move(a));
 280 #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
 281     COPY_COUNT(2);
 282     MOVE_COUNT_EXTRA(0, 1);
 283 #else
 284     COPY_COUNT(1);
 285     MOVE_COUNT(1);
 286 #endif
 287 }
 288
 289 UNORDERED_TEST(unnecessary_copy_emplace_boost_move_map_test, ((map)(multimap)))
 290
 291 UNORDERED_AUTO_TEST(unnecessary_copy_emplace_set_test)
 292 {
 293     // When calling 'source' the object is moved on some compilers, but not
 294     // others. So count that here to adjust later.
 295
 296     reset();
 297     source<count_copies>();
 298     int source_cost = ::unnecessary_copy_tests::count_copies::moves;
 299
 300     //
 301
 302     reset();
 303     boost::unordered_set<count_copies> x;
 304     count_copies a;
 305     x.insert(a);
 306     COPY_COUNT(2);
 307     MOVE_COUNT(0);
 308
 309 //
 310 // 0 arguments
 311 //
 312
 313 #if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100))
 314     // The container will have to create a copy in order to compare with
 315     // the existing element.
 316     reset();
 317     x.emplace();
 318 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) ||                             \
 319     !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
 320     // source_cost doesn't make much sense here, but it seems to fit.
 321     COPY_COUNT(1);
 322     MOVE_COUNT(source_cost);
 323 #else
 324     COPY_COUNT(1);
 325     MOVE_COUNT(1 + source_cost);
 326 #endif
 327 #endif
 328
 329     //
 330     // 1 argument
 331     //
 332
 333     // Emplace should be able to tell that there already is an element
 334     // without creating a new one.
 335     reset();
 336     x.emplace(a);
 337     COPY_COUNT(0);
 338     MOVE_COUNT(0);
 339
 340     // A new object is created by source, but it shouldn't be moved or
 341     // copied.
 342     reset();
 343     x.emplace(source<count_copies>());
 344     COPY_COUNT(1);
 345     MOVE_COUNT(source_cost);
 346
 347     // No move should take place.
 348     reset();
 349     x.emplace(boost::move(a));
 350 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
 351     COPY_COUNT(0);
 352     MOVE_COUNT(0);
 353 #else
 354     COPY_COUNT(0);
 355     MOVE_COUNT(1);
 356 #endif
 357
 358     // Use a new value for cases where a did get moved...
 359     count_copies b;
 360
 361     // The container will have to create a copy in order to compare with
 362     // the existing element.
 363     reset();
 364     x.emplace(b.tag_);
 365     COPY_COUNT(1);
 366     MOVE_COUNT(0);
 367
 368     //
 369     // 2 arguments
 370     //
 371
 372     // The container will have to create b copy in order to compare with
 373     // the existing element.
 374     //
 375     // Note to self: If copy_count == 0 it's an error not an optimization.
 376     // TODO: Devise a better test.
 377
 378     reset();
 379
 380     x.emplace(b, b);
 381     COPY_COUNT(1);
 382     MOVE_COUNT(0);
 383 }
 384
 385 UNORDERED_AUTO_TEST(unnecessary_copy_emplace_map_test)
 386 {
 387     // When calling 'source' the object is moved on some compilers, but not
 388     // others. So count that here to adjust later.
 389
 390     reset();
 391     source<count_copies>();
 392     int source_cost = ::unnecessary_copy_tests::count_copies::moves;
 393
 394     reset();
 395     source<std::pair<count_copies, count_copies> >();
 396     int source_pair_cost = ::unnecessary_copy_tests::count_copies::moves;
 397
 398     //
 399
 400     reset();
 401     boost::unordered_map<count_copies, count_copies> x;
 402     // TODO: Run tests for pairs without const etc.
 403     std::pair<count_copies const, count_copies> a;
 404     x.emplace(a);
 405     COPY_COUNT_EXTRA(4, 1);
 406     MOVE_COUNT_EXTRA(0, 1);
 407
 408 //
 409 // 0 arguments
 410 //
 411
 412 #if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100))
 413     // COPY_COUNT(1) would be okay here.
 414     reset();
 415     x.emplace();
 416 #if BOOST_WORKAROUND(BOOST_MSVC, == 1700)
 417     // This is a little odd, Visual C++ 11 seems to move the pair, which
 418     // results in one copy (for the const key) and one move (for the
 419     // non-const mapped value). Since 'emplace(boost::move(a))' (see below)
 420     // has the normal result, it must be some odd consequence of how
 421     // Visual C++ 11 handles calling move for default arguments.
 422     COPY_COUNT(3);
 423     MOVE_COUNT(1);
 424 #else
 425     COPY_COUNT_EXTRA(2, 1);
 426     MOVE_COUNT_EXTRA(0, 1);
 427 #endif
 428 #endif
 429
 430     reset();
 431     x.emplace(boost::unordered::piecewise_construct, boost::make_tuple(),
 432         boost::make_tuple());
 433     COPY_COUNT(2);
 434     MOVE_COUNT(0);
 435
 436     //
 437     // 1 argument
 438     //
 439
 440     reset();
 441     x.emplace(a);
 442     COPY_COUNT(0);
 443     MOVE_COUNT(0);
 444
 445     // A new object is created by source, but it shouldn't be moved or
 446     // copied.
 447     reset();
 448     x.emplace(source<std::pair<count_copies, count_copies> >());
 449     COPY_COUNT(2);
 450     MOVE_COUNT(source_pair_cost);
 451
 452 #if !(defined(__GNUC__) && __cplusplus < 199900L) &&                           \
 453     !(defined(_MSC_VER) && _MSC_VER < 1600)
 454     count_copies part;
 455     reset();
 456     std::pair<count_copies const&, count_copies const&> a_ref(part, part);
 457     x.emplace(a_ref);
 458     COPY_COUNT(2);
 459     MOVE_COUNT(0);
 460
 461 #endif
 462
 463     // No move should take place.
 464     // (since a is already in the container)
 465     reset();
 466     x.emplace(boost::move(a));
 467     COPY_COUNT(0);
 468     MOVE_COUNT(0);
 469
 470     //
 471     // 2 arguments
 472     //
 473
 474     std::pair<count_copies const, count_copies> b;
 475
 476     reset();
 477     x.emplace(b.first, b.second);
 478     COPY_COUNT(0);
 479     MOVE_COUNT(0);
 480
 481     reset();
 482     x.emplace(source<count_copies>(), source<count_copies>());
 483     COPY_COUNT(2);
 484     MOVE_COUNT(source_cost * 2);
 485
 486     // source<count_copies> creates a single copy.
 487     reset();
 488     x.emplace(b.first, source<count_copies>());
 489     COPY_COUNT(1);
 490     MOVE_COUNT(source_cost);
 491
 492     reset();
 493     x.emplace(count_copies(b.first.tag_), count_copies(b.second.tag_));
 494     COPY_COUNT(2);
 495     MOVE_COUNT(0);
 496
 497     reset();
 498     x.emplace(boost::unordered::piecewise_construct,
 499         boost::make_tuple(boost::ref(b.first)),
 500         boost::make_tuple(boost::ref(b.second)));
 501     COPY_COUNT(0);
 502     MOVE_COUNT(0);
 503
 504 #if !defined(BOOST_NO_CXX11_HDR_TUPLE) || defined(BOOST_HAS_TR1_TUPLE)
 505
 506     reset();
 507     x.emplace(boost::unordered::piecewise_construct,
 508         std::make_tuple(std::ref(b.first)),
 509         std::make_tuple(std::ref(b.second)));
 510     COPY_COUNT(0);
 511     MOVE_COUNT(0);
 512
 513     std::pair<count_copies const, count_copies> move_source_trial;
 514     reset();
 515     std::make_tuple(std::move(move_source_trial.first));
 516     std::make_tuple(std::move(move_source_trial.second));
 517     int tuple_move_cost = ::unnecessary_copy_tests::count_copies::moves;
 518     int tuple_copy_cost = ::unnecessary_copy_tests::count_copies::copies;
 519
 520     std::pair<count_copies const, count_copies> move_source;
 521     reset();
 522     x.emplace(boost::unordered::piecewise_construct,
 523         std::make_tuple(std::move(move_source.first)),
 524         std::make_tuple(std::move(move_source.second)));
 525     COPY_COUNT(tuple_copy_cost);
 526     MOVE_COUNT(tuple_move_cost);
 527
 528 #if !defined(BOOST_NO_CXX11_HDR_TUPLE) &&                                      \
 529     !(defined(__GNUC__) && __GNUC__ == 4 && __GNUC_MINOR__ < 6) &&             \
 530     !(defined(BOOST_MSVC) && BOOST_MSVC < 1700)
 531     reset();
 532     x.emplace(boost::unordered::piecewise_construct,
 533         std::forward_as_tuple(b.first), std::forward_as_tuple(b.second));
 534     COPY_COUNT(0);
 535     MOVE_COUNT(0);
 536 #endif
 537
 538 #endif
 539 }
 540 }
 541
 542 RUN_TESTS()