GTTF: Enable glibcxx debug mode for Debug builds by default.

chrome/browser/safe_browsing/prefix_set_unittest.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "chrome/browser/safe_browsing/prefix_set.h"
 
 #include <algorithm>
 #include <iterator>
 
 #include "base/file_util.h"
@@ skipping 12 matching lines @@
   // Constants for the v1 format.
   static const size_t kMagicOffset = 0 * sizeof(uint32);
   static const size_t kVersionOffset = 1 * sizeof(uint32);
   static const size_t kIndexSizeOffset = 2 * sizeof(uint32);
   static const size_t kDeltasSizeOffset = 3 * sizeof(uint32);
   static const size_t kPayloadOffset = 4 * sizeof(uint32);
 
   // Generate a set of random prefixes to share between tests.  For
   // most tests this generation was a large fraction of the test time.
   static void SetUpTestCase() {
-    for (size_t i = 0; i < 50000; ++i) {
+    for (size_t i = 0; i < 5000; ++i) {

[Scott Hess - ex-Googler, 2013/11/05 03:04:58]

In theory, this many values should be able to spread out in the 32-bit space
with only singleton runs.  What's the rationale for doing this?  Is it just the
cost of push_back?  If things were inserted in bulk would that help?

[Paweł Hajdan Jr., 2013/11/05 03:10:06]

I'm not sure now - it's definitely about the speed.

I actually suspect quadratic complexity somewhere when GLIBCXX_DEBUG is used.

How would you insert these random values in bulk? If there is some specific
alternative you have in mind I'm happy to try it. Note that it's likely to need
another container, which would run into same problem.

[Scott Hess - ex-Googler, 2013/11/05 03:17:24]

for (size_t i = 0; i < 500; ++i) {
  SBPrefix a[100];
  for (size_t j = 0; j < 100; ++j) {
    a[j] = static_cast<SBPrefix>(base::RandUint64());
  }
  shared_prefixes_.insert(shared_prefixes_.end(), &a[0], &a[100]);
}

though if the quadratic part is in the users of this rather than the creation,
doomed.

The data structure delta-encodes items closer together than 2^16.  So with 50000
items, there's a fair number of runs of such items.  With 5000, less so, though
I'd expect it to be non-zero.  Unfortunately, I don't have the math to calculate
this off-the-cuff, but I'll think on where the knee might be.

[Paweł Hajdan Jr., 2013/11/05 22:42:26]

I've tried it and it doesn't help in a meaningful way (I've tried with 50000 of
course - for 5000 the difference is similarly small).

Numbers are 495 s for original non-batch version and 490 s for batch version.

Total test run time is 973 s and 983 s respectively (not sure why batch would be
slower there - maybe more runs would flesh out any differences, but then I don't
think we get any real speed-up from this).

[Scott Hess - ex-Googler, 2013/11/06 00:47:14]

495 _seconds_?  Normally the entire PrefixSetTest.* group runs in 843
_milliseconds_.  This doesn't make much sense, and I'm not sure I'm happy to
make this kind of change without a stronger rationale.  As I noted the
difference between 50k and 5k is pretty material to this data structure.

Note that shared_prefixes_ is static, and should only be initialized once.  So
it somewhat makes sense not to see much gain from initialization, I guess.  Do
you have a better breakdown of where the slowdown comes from?  Perhaps there's a
specific case which is hitting it.  This doesn't seem like a very extreme
structure to me, WRT Chromium in general.

       const SBPrefix prefix = static_cast<SBPrefix>(base::RandUint64());
       shared_prefixes_.push_back(prefix);
     }
 
     // Sort for use with PrefixSet constructor.
     std::sort(shared_prefixes_.begin(), shared_prefixes_.end());
   }
 
   // Check that all elements of |prefixes| are in |prefix_set|, and
   // that nearby elements are not (for lack of a more sensible set of
@@ skipping 415 matching lines @@
   file_util::ScopedFILE file(file_util::OpenFile(filename, "ab"));
   const char buf[] = "im in ur base, killing ur d00dz.";
   ASSERT_EQ(strlen(buf), fwrite(buf, 1, strlen(buf), file.get()));
   file.reset();
   scoped_ptr<safe_browsing::PrefixSet>
       prefix_set(safe_browsing::PrefixSet::LoadFile(filename));
   ASSERT_FALSE(prefix_set.get());
 }
 
 }  // namespace