Support incremental-max and sample in Profiler data

base/tracked_objects.cc

 // Copyright (c) 2011 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 "base/tracked_objects.h"
 
 #include <math.h>
 
 #include "base/format_macros.h"
 #include "base/message_loop.h"
@@ skipping 15 matching lines @@
 // that we only record after parsing the command line flag --enable-tracking.
 // Note that the flag may force either state, so this really controls only the
 // period of time up until that flag is parsed. If there is no flag seen, then
 // this state may prevail for much or all of the process lifetime.
 static const ThreadData::Status kInitialStartupState = ThreadData::ACTIVE;
 }  // anonymous namespace.
 
 //------------------------------------------------------------------------------
 // DeathData tallies durations when a death takes place.
 
-void DeathData::RecordDeath(DurationInt queue_duration,
-                            DurationInt run_duration) {
-  ++count_;
-  queue_time_.AddDuration(queue_duration);
-  run_time_.AddDuration(run_duration);
+DeathData::DeathData() {
+  Clear();
 }
 
-DurationInt DeathData::AverageMsRunDuration() const {
-  return run_time_.AverageMsDuration(count_);
+DeathData::DeathData(int count) {
+  Clear();
+  count_ = count;
 }
 
-DurationInt DeathData::AverageMsQueueDuration() const {
-  return queue_time_.AverageMsDuration(count_);
+// TODO(jar): I need to see if this macro to optimize branching is worth it.
+//
+// This macro has no branching, so it is surely fast, and is equivalent to:
+//             if (assign_it)
+//               target = source;
+// We use a macro rather than a template to force this to inline.
+// Related code for calculating max is discussed on the web.
+#define CONDITIONAL_ASSIGN(assign_it, target, source) \
+    ((target) ^= ((target) ^ (source)) & -static_cast<DurationInt>(assign_it))
+
+void DeathData::RecordDeath(const DurationInt queue_duration,
+                            const DurationInt run_duration,
+                            int32 random_number) {
+  queue_duration_sum_ += queue_duration;
+  run_duration_sum_ += run_duration;
+  ++count_;
+
+  // Take a uniformly distributed sample over all durations ever supplied.
+  // The probability that we (instead) use this new sample is 1/count_.  This
+  // results in a completely uniform selection of the sample.
+  // We ignore the fact that we correlated our selection of a sample of run
+  // and queue times.
+  bool take_sample = 0 == (random_number % count_);
+  CONDITIONAL_ASSIGN(take_sample, queue_duration_sample_, queue_duration);
+  CONDITIONAL_ASSIGN(take_sample, run_duration_sample_, run_duration);
+
+  CONDITIONAL_ASSIGN(queue_duration_max_ < queue_duration, queue_duration_max_,
+                     queue_duration);
+  CONDITIONAL_ASSIGN(run_duration_max_ < run_duration, run_duration_max_,
+                     run_duration);
+  // Ensure we got the macros right.
+  DCHECK_GE(queue_duration_max_, queue_duration);
+  DCHECK_GE(run_duration_max_, run_duration);
+  DCHECK(!take_sample || run_duration_sample_ == run_duration);
+  DCHECK(!take_sample || queue_duration_sample_ == queue_duration);
 }
 
-void DeathData::AddDeathData(const DeathData& other) {
-  count_ += other.count_;
-  queue_time_.AddData(other.queue_time_);
-  run_time_.AddData(other.run_time_);
+int DeathData::count() const { return count_; }
+
+DurationInt DeathData::run_duration_sum() const { return run_duration_sum_; }
+
+DurationInt DeathData::run_duration_max() const { return run_duration_max_; }
+
+DurationInt DeathData::run_duration_sample() const {
+  return run_duration_sample_;
 }
 
+DurationInt DeathData::queue_duration_sum() const {
+  return queue_duration_sum_;
+}
+
+DurationInt DeathData::queue_duration_max() const {
+  return queue_duration_max_;
+}
+
+DurationInt DeathData::queue_duration_sample() const {
+  return queue_duration_sample_;
+}
+
+
 base::DictionaryValue* DeathData::ToValue() const {
   base::DictionaryValue* dictionary = new base::DictionaryValue;
   dictionary->Set("count", base::Value::CreateIntegerValue(count_));
   dictionary->Set("run_ms",
-      base::Value::CreateIntegerValue(run_time_.duration()));
+      base::Value::CreateIntegerValue(run_duration_sum()));
+  dictionary->Set("run_ms_max",
+      base::Value::CreateIntegerValue(run_duration_max()));
+  dictionary->Set("run_ms_sample",
+      base::Value::CreateIntegerValue(run_duration_sample()));
   dictionary->Set("queue_ms",
-      base::Value::CreateIntegerValue(queue_time_.duration()));
-  dictionary->Set("run_ms_max",
-      base::Value::CreateIntegerValue(run_time_.max()));
+      base::Value::CreateIntegerValue(queue_duration_sum()));
   dictionary->Set("queue_ms_max",
-      base::Value::CreateIntegerValue(queue_time_.max()));
+      base::Value::CreateIntegerValue(queue_duration_max()));
+  dictionary->Set("queue_ms_sample",
+      base::Value::CreateIntegerValue(queue_duration_sample()));
   return dictionary;
 }
 
+void DeathData::ResetMax() {
+  run_duration_max_ = 0;
+  queue_duration_max_ = 0;
+}
+
 void DeathData::Clear() {
   count_ = 0;
-  run_time_.Clear();
-  queue_time_.Clear();
+  run_duration_sum_ = 0;
+  run_duration_max_ = 0;
+  run_duration_sample_ = 0;
+  queue_duration_sum_ = 0;
+  queue_duration_max_ = 0;
+  queue_duration_sample_ = 0;
 }
 
 //------------------------------------------------------------------------------
-
-void DeathData::Data::AddData(const Data& other) {
-  duration_ += other.duration_;
-  if (max_ > other.max_)
-    return;
-  max_ = other.max_;
-}
-
-void DeathData::Data::AddDuration(DurationInt duration) {
-  duration_ += duration;
-  if (max_ > duration)
-    return;
-  max_ = duration;
-}
-
-DurationInt DeathData::Data::AverageMsDuration(int count) const {
-  if (duration_ == 0 || !count)
-    return 0;
-  return (duration_ + count / 2) / count;
-}
-
-void DeathData::Data::Clear() {
-  duration_ = 0;
-  max_ = 0;
-}
-//------------------------------------------------------------------------------
 BirthOnThread::BirthOnThread(const Location& location,
                              const ThreadData& current)
     : location_(location),
-      birth_thread_(&current) {}
+      birth_thread_(&current) {
+}
+
+const Location BirthOnThread::location() const { return location_; }
+const ThreadData* BirthOnThread::birth_thread() const { return birth_thread_; }
 
 //------------------------------------------------------------------------------
 Births::Births(const Location& location, const ThreadData& current)
     : BirthOnThread(location, current),
       birth_count_(1) { }
 
+int Births::birth_count() const { return birth_count_; }
+
+void Births::RecordBirth() { ++birth_count_; }
+
+void Births::ForgetBirth() { --birth_count_; }
+
+void Births::Clear() { birth_count_ = 0; }
+
 //------------------------------------------------------------------------------
-// ThreadData maintains the central data for all births and deaths.
+// ThreadData maintains the central data for all births and deaths on a single
+// thread.
 
 // TODO(jar): We should pull all these static vars together, into a struct, and
 // optimize layout so that we benefit from locality of reference during accesses
 // to them.
 
 // A TLS slot which points to the ThreadData instance for the current thread. We
 // do a fake initialization here (zeroing out data), and then the real in-place
 // construction happens when we call tls_index_.Initialize().
 // static
 base::ThreadLocalStorage::Slot ThreadData::tls_index_(base::LINKER_INITIALIZED);
@@ skipping 37 matching lines @@
       next_retired_worker_(NULL),
       worker_thread_number_(thread_number) {
   CHECK_GT(thread_number, 0);
   base::StringAppendF(&thread_name_, "WorkerThread-%d", thread_number);
   PushToHeadOfList();  // Which sets real incarnation_count_for_pool_.
 }
 
 ThreadData::~ThreadData() {}
 
 void ThreadData::PushToHeadOfList() {
+  // Toss in a hint of randomness (atop the uniniitalized value).
+  random_number_ += static_cast<int32>(this - static_cast<ThreadData*>(0));
+  random_number_ ^= (Now() - TrackedTime()).InMilliseconds();
+
   DCHECK(!next_);
   base::AutoLock lock(*list_lock_.Pointer());
   incarnation_count_for_pool_ = incarnation_counter_;
   next_ = all_thread_data_list_head_;
   all_thread_data_list_head_ = this;
 }
 
 // static
+ThreadData* ThreadData::first() {
+  base::AutoLock lock(*list_lock_.Pointer());
+  return all_thread_data_list_head_;
+}
+
+ThreadData* ThreadData::next() const { return next_; }
+
+// static
 void ThreadData::InitializeThreadContext(const std::string& suggested_name) {
   if (!Initialize())  // Always initialize if needed.
     return;
   ThreadData* current_thread_data =
       reinterpret_cast<ThreadData*>(tls_index_.Get());
   if (current_thread_data)
     return;  // Browser tests instigate this.
   current_thread_data = new ThreadData(suggested_name);
   tls_index_.Set(current_thread_data);
 }
@@ skipping 54 matching lines @@
     return;
   }
   // We must NOT do any allocations during this callback.
   // Using the simple linked lists avoids all allocations.
   DCHECK_EQ(this->next_retired_worker_, reinterpret_cast<ThreadData*>(NULL));
   this->next_retired_worker_ = first_retired_worker_;
   first_retired_worker_ = this;
 }
 
 // static
-base::DictionaryValue* ThreadData::ToValue() {
+base::DictionaryValue* ThreadData::ToValue(bool reset_max) {
   DataCollector collected_data;  // Gather data.
+  // Request multiple calls to collected_data.Append() for all threads.
+  SendAllMaps(reset_max, &collected_data);
   collected_data.AddListOfLivingObjects();  // Add births that are still alive.
   base::ListValue* list = collected_data.ToValue();
   base::DictionaryValue* dictionary = new base::DictionaryValue();
   dictionary->Set("list", list);
   return dictionary;
 }
 
 Births* ThreadData::TallyABirth(const Location& location) {
   BirthMap::iterator it = birth_map_.find(location);
   if (it != birth_map_.end()) {
     it->second->RecordBirth();
     return it->second;
   }
 
   Births* tracker = new Births(location, *this);
   // Lock since the map may get relocated now, and other threads sometimes
   // snapshot it (but they lock before copying it).
   base::AutoLock lock(map_lock_);
   birth_map_[location] = tracker;
   return tracker;
 }
 
 void ThreadData::TallyADeath(const Births& birth,
                              DurationInt queue_duration,
                              DurationInt run_duration) {
+  // Stir in some randomness, plus add constant in case durations are zero.
+  const DurationInt kSomePrimeNumber = 4294967279;
+  random_number_ += queue_duration + run_duration + kSomePrimeNumber;
+  // An address is going to have some randomness to it as well ;-).
+  random_number_ ^= static_cast<int32>(&birth - reinterpret_cast<Births*>(0));
+
   DeathMap::iterator it = death_map_.find(&birth);
   DeathData* death_data;
   if (it != death_map_.end()) {
     death_data = &it->second;
   } else {
     base::AutoLock lock(map_lock_);  // Lock as the map may get relocated now.
     death_data = &death_map_[&birth];
   }  // Release lock ASAP.
-  death_data->RecordDeath(queue_duration, run_duration);
+  death_data->RecordDeath(queue_duration, run_duration, random_number_);
 }
 
 // static
 Births* ThreadData::TallyABirthIfActive(const Location& location) {
   if (!kTrackAllTaskObjects)
     return NULL;  // Not compiled in.
 
   if (!tracking_status())
     return NULL;
   ThreadData* current_thread_data = Get();
@@ skipping 101 matching lines @@
   if (!current_thread_data)
     return;
 
   DurationInt queue_duration = 0;
   DurationInt run_duration = 0;
   if (!start_of_run.is_null() && !end_of_run.is_null())
     run_duration = (end_of_run - start_of_run).InMilliseconds();
   current_thread_data->TallyADeath(*birth, queue_duration, run_duration);
 }
 
-// static
-ThreadData* ThreadData::first() {
-  base::AutoLock lock(*list_lock_.Pointer());
-  return all_thread_data_list_head_;
-}
+const std::string ThreadData::thread_name() const { return thread_name_; }
 
 // This may be called from another thread.
-void ThreadData::SnapshotBirthMap(BirthMap *output) const {
+void ThreadData::SnapshotMaps(bool reset_max,
+                              BirthMap* birth_map,
+                              DeathMap* death_map) {
   base::AutoLock lock(map_lock_);
   for (BirthMap::const_iterator it = birth_map_.begin();
        it != birth_map_.end(); ++it)
-    (*output)[it->first] = it->second;
-}
-
-// This may be called from another thread.
-void ThreadData::SnapshotDeathMap(DeathMap *output) const {
-  base::AutoLock lock(map_lock_);
-  for (DeathMap::const_iterator it = death_map_.begin();
-       it != death_map_.end(); ++it)
-    (*output)[it->first] = it->second;
+    (*birth_map)[it->first] = it->second;
+  for (DeathMap::iterator it = death_map_.begin();
+       it != death_map_.end(); ++it) {
+    (*death_map)[it->first] = it->second;
+    if (reset_max)
+      it->second.ResetMax();
+  }
 }
 
 // static
+void ThreadData::SendAllMaps(bool reset_max, class DataCollector* target) {
+  if (!kTrackAllTaskObjects)
+    return;  // Not compiled in.
+  // Get an unchanging copy of a ThreadData list.
+  ThreadData* my_list = ThreadData::first();
+
+  // Gather data serially.
+  // This hackish approach *can* get some slighly corrupt tallies, as we are
+  // grabbing values without the protection of a lock, but it has the advantage
+  // of working even with threads that don't have message loops.  If a user
+  // sees any strangeness, they can always just run their stats gathering a
+  // second time.
+  for (ThreadData* thread_data = my_list;
+       thread_data;
+       thread_data = thread_data->next()) {
+    // Get copy of data.
+    ThreadData::BirthMap birth_map;
+    ThreadData::DeathMap death_map;
+    thread_data->SnapshotMaps(reset_max, &birth_map, &death_map);
+    target->Append(*thread_data, birth_map, death_map);
+  }
+}
+
+// static
 void ThreadData::ResetAllThreadData() {
   ThreadData* my_list = first();
 
   for (ThreadData* thread_data = my_list;
        thread_data;
        thread_data = thread_data->next())
     thread_data->Reset();
 }
 
 void ThreadData::Reset() {
@@ skipping 91 matching lines @@
   // We must be single threaded... but be careful anyway.
   if (!InitializeAndSetTrackingStatus(false))
     return;
   ThreadData* thread_data_list;
   {
     base::AutoLock lock(*list_lock_.Pointer());
     thread_data_list = all_thread_data_list_head_;
     all_thread_data_list_head_ = NULL;
     ++incarnation_counter_;
     // To be clean, break apart the retired worker list (though we leak them).
-    while(first_retired_worker_) {
+    while (first_retired_worker_) {
       ThreadData* worker = first_retired_worker_;
       CHECK_GT(worker->worker_thread_number_, 0);
       first_retired_worker_ = worker->next_retired_worker_;
       worker->next_retired_worker_ = NULL;
     }
   }
 
   // Put most global static back in pristine shape.
   worker_thread_data_creation_count_ = 0;
   cleanup_count_ = 0;
@@ skipping 53 matching lines @@
       base::Value::CreateStringValue(birth_->birth_thread()->thread_name()));
   dictionary->Set("death_thread",
       base::Value::CreateStringValue(DeathThreadName()));
   dictionary->Set("location", birth_->location().ToValue());
   return dictionary;
 }
 
 //------------------------------------------------------------------------------
 // DataCollector
 
-DataCollector::DataCollector() {
-  if (!kTrackAllTaskObjects)
-    return;  // Not compiled in.
-
-  // Get an unchanging copy of a ThreadData list.
-  ThreadData* my_list = ThreadData::first();
-
-  // Gather data serially.
-  // This hackish approach *can* get some slighly corrupt tallies, as we are
-  // grabbing values without the protection of a lock, but it has the advantage
-  // of working even with threads that don't have message loops.  If a user
-  // sees any strangeness, they can always just run their stats gathering a
-  // second time.
-  for (ThreadData* thread_data = my_list;
-       thread_data;
-       thread_data = thread_data->next()) {
-    Append(*thread_data);
-  }
-}
+DataCollector::DataCollector() {}
 
 DataCollector::~DataCollector() {
 }
 
-void DataCollector::Append(const ThreadData& thread_data) {
-  // Get copy of data.
-  ThreadData::BirthMap birth_map;
-  thread_data.SnapshotBirthMap(&birth_map);
-  ThreadData::DeathMap death_map;
-  thread_data.SnapshotDeathMap(&death_map);
-
+void DataCollector::Append(const ThreadData &thread_data,
+                           const ThreadData::BirthMap &birth_map,
+                           const ThreadData::DeathMap &death_map) {
   for (ThreadData::DeathMap::const_iterator it = death_map.begin();
        it != death_map.end(); ++it) {
     collection_.push_back(Snapshot(*it->first, thread_data, it->second));
     global_birth_count_[it->first] -= it->first->birth_count();
   }
 
   for (ThreadData::BirthMap::const_iterator it = birth_map.begin();
        it != birth_map.end(); ++it) {
     global_birth_count_[it->second] += it->second->birth_count();
   }
@@ skipping 13 matching lines @@
 
 base::ListValue* DataCollector::ToValue() const {
   base::ListValue* list = new base::ListValue;
   for (size_t i = 0; i < collection_.size(); ++i) {
     list->Append(collection_[i].ToValue());
   }
   return list;
 }
 
 }  // namespace tracked_objects