Issue 1840843004: Improve efficiency of persistent sparse histograms.

Issue 1840843004: Improve efficiency of persistent sparse histograms. (Closed)

Created:
4 years, 8 months ago by bcwhite

Modified:
4 years, 8 months ago

Reviewers:
Alexei Svitkine (slow)

CC:
chromium-reviews, asvitkine+watch_chromium.org

Base URL:
https://chromium.googlesource.com/chromium/src.git@improved-pma-iterator

Target Ref:
refs/pending/heads/master

Project:
chromium

Visibility:
Public.

More Reviews

Description

Improve efficiency of persistent sparse histograms. It's expensive to find all the records pertaining to a persistent-sample-map if each instance locates them individually. Instead, have a "helper" object which locates them all and makes them available in constant- time. BUG=546019 Committed: https://crrev.com/b0bb9194eb7b530cdd16ca926e94d424b6766746 Cr-Commit-Position: refs/heads/master@{#387841}

Patch Set 1 #

Patch Set 2 : bug fix and some clean-up #

Patch Set 3 : rebased #

Patch Set 4 : simplify seen/unseen and preserve order of samples #

Patch Set 5 : rebased #

Total comments: 43

Patch Set 6 : addressed review comments by Alexei #

Patch Set 7 : re-order classes to make DataManager a member instead of pointer; change IDmap (which is not multi-… #

Patch Set 8 : remove Reset semantics in favor of Acquire/Release #

Patch Set 9 : move all found_ logic inside DataManager #

Patch Set 10 : added comment clarifying loop behavior #

Created: 4 years, 8 months ago

Download [raw] [tar.bz2]

	Unified diffs	Side-by-side diffs	Delta from patch set	Stats (+459 lines, -112 lines)			Patch
M	base/metrics/persistent_histogram_allocator.h	View	1 2 3 4 5 6 7 8	5 chunks	+158 lines, -1 line	0 comments	Download
M	base/metrics/persistent_histogram_allocator.cc	View	1 2 3 4 5 6 7 8 9	5 chunks	+139 lines, -3 lines	0 comments	Download
M	base/metrics/persistent_memory_allocator.h	View	1 2 3 4 5	2 chunks	+4 lines, -1 line	0 comments	Download
M	base/metrics/persistent_memory_allocator.cc	View	1 2 3 4 5	1 chunk	+0 lines, -2 lines	0 comments	Download
M	base/metrics/persistent_sample_map.h	View	1 2 3 4 5	3 chunks	+36 lines, -5 lines	0 comments	Download
M	base/metrics/persistent_sample_map.cc	View	1 2 3 4 5 6 7	5 chunks	+67 lines, -49 lines	0 comments	Download
M	base/metrics/persistent_sample_map_unittest.cc	View	1 2 3 4 5	9 chunks	+50 lines, -46 lines	0 comments	Download
M	base/metrics/sparse_histogram.h	View	1 2	3 chunks	+3 lines, -3 lines	0 comments	Download
M	base/metrics/sparse_histogram.cc	View	1 2	2 chunks	+2 lines, -2 lines	0 comments	Download

Messages

Total messages: 25 (13 generated)

Expand Messages | Collapse Messages | Show Generated Messages | Hide Generated Messages

Alexei Svitkine (slow)

Sorry for the delay in getting to this. Have been busy with an UMA P0. ...

4 years, 8 months ago (2016-04-13 15:53:51 UTC) #10

bcwhite

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persistent_histogram_allocator.cc File base/metrics/persistent_histogram_allocator.cc (right): https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persistent_histogram_allocator.cc#newcode628 base/metrics/persistent_histogram_allocator.cc:628: uint64_t load_id) { On 2016/04/13 15:53:50, Alexei Svitkine wrote: ...

4 years, 8 months ago (2016-04-13 22:45:04 UTC) #12

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
File base/metrics/persistent_histogram_allocator.cc (right):

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.cc:628: uint64_t load_id) {
On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> Nit: Add lock_.AssertAcquired()

Done.

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.cc:635: for (int count = 0; !found
|| count < kMinimumNumberToLoad; ++count) {
On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> Nit: I would just remove the found var and return true & false directly in the
> two cases. It makes the logic a little bit easier to follow.

For performance reasons, I want to load a minimum number of records while the
lock is held.  Otherwise there is a good chance it'll just have to be repeatedly
acquired.

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.cc:639:
PersistentSampleMap::GetNextPersistentRecord(record_iterator_,
On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> In the previous code, you had a comment about the general algorithm of keeping
> around the iterator and always going forward in it and why it makes sense. Can
> you preserve the comment in the code somewhere?

Done.

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.cc:678: if
(!helper_->LoadRecordsForSampleMapWhileLocked(sample_map_id_))
On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> So the function you call will give up after not finding things for 10 records.
> Why is this correct to return 0 in this case?

It loads 10 records.  If it hasn't found one for this ID, it continues until it
does find one or everything has been loaded.  But that's an internal detail.  To
the outside it just returns true/false if it found anything for this ID.

False return means didn't find anything for this specific ID.  It may have found
records for other ones and held them for future requests for those IDs.

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.cc:679: return 0;
On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> Hmm, can we expose kReferenceNull to be public and return it here? Otherwise,
> this relying on the assumption that 0 is null.

Done.

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.cc:683:
records_.reserve(records_.size() + found_.size());
On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> Seems wasteful to copy this stuff twice. How about making
> LoadRecordsForSampleMapWhileLocked() take an output vector param. Then, if it
> gets an entry for the sample_map_id that's passed to it, it can put it
directly
> into that vector, otherwise it can put it into found_ for the corresponding
one.
> 

Done but I think this makes the code more confusing.  I think the old way, while
perhaps slightly less efficient, is much easier to read and maintain.

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.cc:694: return records_[seen_++];
On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> Shouldn't this code also be locked?

No need.  records_ is only ever accessed by a single object and one thread at a
time.  See comment in .h file, line 390.

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
File base/metrics/persistent_histogram_allocator.h (right):

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.h:194:
std::unique_ptr<PersistentSparseHistogramHelper> sparse_histogram_helper_;
On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> Why is this a unique_ptr? Can it just be a member?

I had originally planned to not create it until needed.  Let me see what I can
do.

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.h:288: class BASE_EXPORT
PersistentSparseHistogramHelper {
On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> Helper is not a very descriptive name. Can this be named more descriptively?
> Maybe PersistentSparseHistogramManager?

Done.

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.h:292:
PersistentSparseHistogramHelper(PersistentMemoryAllocator* allocator);
On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> Nit: explicit

Done.

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.h:304: template <typename T>
On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> Does this need to be a template if we know it's managing data for a sparse
> histogram? Can it be concrete and named appropriately for what it's querying?

It's a template because the type on which it's used is private to other files. 
This class doesn't know the format of the record, just that it exists.

The type could be made public but it works better to keep it completely
encapsulated in the PersistentSampleMap and have this class call that one to do
the low-level work.

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.h:320: bool
LoadRecordsForSampleMapWhileLocked(uint64_t load_id);
On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> Nit: Why load_id if Load is already part of the method name? Just id?

Because parameter names here need to match parameter names in the implementation
and just "id" made for unclear code.

> Also, not sure you need "ForSampleMap" in the name - I think
> LoadRecordsWhileLocked() is easier to digest. If you really want to have the
> extra info you can name the param sample_map_id.

Done.

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.h:339: // that underlie persistent
SparseHistogram objects. It is broken out into a
On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> This sentence is confusing since it's using plurals (containers, objects), but
> the reality is this corresponds to a single
SparseHistogram/PersistentSampleMap.
> Can you please re-word?

Done.

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.h:359: void Reset();
On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> I don't quite understand the reasoning here. It feels wrong to need this, but
> I'm not quite following the scenario.
> 
> Can you explain the scenario a bit more?

Done.

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.h:384: uint64_t sample_map_id_;
On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> Nit: const?

Done.

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
File base/metrics/persistent_sample_map.h (right):

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_sample_map.h:45: Metadata* meta);
> Do we really need all 3? I think it would be useful to discuss why all the
> different types are needed. I would possibly vote for simplifying this to
avoid
> needing all the different permutations.

The one taking a PersistentSampleMapRecords is the real constructor that does
the work.

The one taking a PersitentSparseHistogramHelper is used by tests which need to
validate sample sharing between multiple instances of the same histogram (like
having multiple processes).  This could be removed and the test altered to use
duplicate allocators instead of independent helpers.

The one taking a PersistentHistogramAllocator simplifies the interface and means
that the SparseHistogram class doesn't have to include the full
persistent_histogram_allocator.h file just to call GetSampleMapRecords() off of
the passed-in allocator object.

> Specifically, it seems the last one does a Reset() which should definitely be
> documented if we're keeping that version.

They all do exactly the same thing.  The first two just dereference the middle
parameter before "delegating" to the third one.

bcwhite

Use embedded object instead of pointer to object: Done. Remove Reset in favor of Acquire/Release ...

4 years, 8 months ago (2016-04-14 15:55:46 UTC) #13

Alexei Svitkine (slow)

Haven't looked at your new patchset yet, will do later today - but replying to ...

4 years, 8 months ago (2016-04-14 19:30:03 UTC) #14

Haven't looked at your new patchset yet, will do later today - but replying to
our previous comment discussion first.

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
File base/metrics/persistent_histogram_allocator.cc (right):

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.cc:635: for (int count = 0; !found
|| count < kMinimumNumberToLoad; ++count) {
On 2016/04/13 22:45:03, bcwhite wrote:
> On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> > Nit: I would just remove the found var and return true & false directly in
the
> > two cases. It makes the logic a little bit easier to follow.
> 
> For performance reasons, I want to load a minimum number of records while the
> lock is held.  Otherwise there is a good chance it'll just have to be
repeatedly
> acquired.

I understand that, I was not suggesting here to remove the iteration, just the
"!found" condition in the for loop. So the loop becomes:

for (int count = 0; count < kMinimumNumberToLoad; ++count) {
  ...
  if (sample_map_id == load_id)
    return true;
}
return false;

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.cc:678: if
(!helper_->LoadRecordsForSampleMapWhileLocked(sample_map_id_))
On 2016/04/13 22:45:03, bcwhite wrote:
> On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> > So the function you call will give up after not finding things for 10
records.
> > Why is this correct to return 0 in this case?
> 
> It loads 10 records.  If it hasn't found one for this ID, it continues until
it
> does find one or everything has been loaded.  But that's an internal detail. 
To
> the outside it just returns true/false if it found anything for this ID.
> 
> False return means didn't find anything for this specific ID.  It may have
found
> records for other ones and held them for future requests for those IDs.

Where does it continue? I don't see a loop inside GetNext()? Reading this code,
it seems it just loads 10 records and if not found within the 10, it returns 0.
That seems to not match what you're saying. What am I missing?

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.cc:694: return records_[seen_++];
On 2016/04/13 22:45:03, bcwhite wrote:
> On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> > Shouldn't this code also be locked?
> 
> No need.  records_ is only ever accessed by a single object and one thread at
a
> time.  See comment in .h file, line 390.

I see. So it's only the helper that needs the lock. That makes sense.

Perhaps the logic you have in the if above that grabs helper_->lock_ could just
become a function of the helper? Then, this code wouldn't need to reach into the
private member lock_ on it.

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
File base/metrics/persistent_histogram_allocator.h (right):

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.h:304: template <typename T>
On 2016/04/13 22:45:03, bcwhite wrote:
> On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> > Does this need to be a template if we know it's managing data for a sparse
> > histogram? Can it be concrete and named appropriately for what it's
querying?
> 
> It's a template because the type on which it's used is private to other files.

> This class doesn't know the format of the record, just that it exists.
> 
> The type could be made public but it works better to keep it completely
> encapsulated in the PersistentSampleMap and have this class call that one to
do
> the low-level work.

Okay, maybe mention that in the method comment. Otherwise, it's confusing why
it's a template.

bcwhite

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persistent_histogram_allocator.cc File base/metrics/persistent_histogram_allocator.cc (right): https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persistent_histogram_allocator.cc#newcode635 base/metrics/persistent_histogram_allocator.cc:635: for (int count = 0; !found || count < ...

4 years, 8 months ago (2016-04-15 02:36:18 UTC) #15

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
File base/metrics/persistent_histogram_allocator.cc (right):

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.cc:635: for (int count = 0; !found
|| count < kMinimumNumberToLoad; ++count) {
On 2016/04/14 19:30:03, Alexei Svitkine wrote:
> On 2016/04/13 22:45:03, bcwhite wrote:
> > On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> > > Nit: I would just remove the found var and return true & false directly in
> the
> > > two cases. It makes the logic a little bit easier to follow.
> > 
> > For performance reasons, I want to load a minimum number of records while
the
> > lock is held.  Otherwise there is a good chance it'll just have to be
> repeatedly
> > acquired.
> 
> I understand that, I was not suggesting here to remove the iteration, just the
> "!found" condition in the for loop. So the loop becomes:
> 
> for (int count = 0; count < kMinimumNumberToLoad; ++count) {
>   ...
>   if (sample_map_id == load_id)
>     return true;
> }
> return false;

That would stop loading when the first match was found.  I want it to keep
loading.

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.cc:678: if
(!helper_->LoadRecordsForSampleMapWhileLocked(sample_map_id_))
On 2016/04/14 19:30:03, Alexei Svitkine wrote:
> On 2016/04/13 22:45:03, bcwhite wrote:
> > On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> > > So the function you call will give up after not finding things for 10
> records.
> > > Why is this correct to return 0 in this case?
> > 
> > It loads 10 records.  If it hasn't found one for this ID, it continues until
> it
> > does find one or everything has been loaded.  But that's an internal detail.

> To
> > the outside it just returns true/false if it found anything for this ID.
> > 
> > False return means didn't find anything for this specific ID.  It may have
> found
> > records for other ones and held them for future requests for those IDs.
> 
> Where does it continue? I don't see a loop inside GetNext()? Reading this
code,
> it seems it just loads 10 records and if not found within the 10, it returns
0.
> That seems to not match what you're saying. What am I missing?

"!found" in the "for" condition.

LoadRecordsForSampleMapWhileLocked will load at least 1 record for the specified
ID if any remain.  That's its contract.  As it's written, however, it loads
_at_least_ 10 records and _at_least_ 1 record for the specified ID.  (Assuming
that many remain to be read, of course.)  It does this extra work for efficiency
so it has to acquire the lock fewer times.

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.cc:694: return records_[seen_++];
On 2016/04/14 19:30:03, Alexei Svitkine wrote:
> On 2016/04/13 22:45:03, bcwhite wrote:
> > On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> > > Shouldn't this code also be locked?
> > 
> > No need.  records_ is only ever accessed by a single object and one thread
at
> a
> > time.  See comment in .h file, line 390.
> 
> I see. So it's only the helper that needs the lock. That makes sense.
> 
> Perhaps the logic you have in the if above that grabs helper_->lock_ could
just
> become a function of the helper? Then, this code wouldn't need to reach into
the
> private member lock_ on it.

Hmmm...  Let me think about it.  I worry that the "only one user, no reentry"
contract of PersistentSampleMapRecords won't clearly carry over to the
DataManager (what was Helper) class making it possible to create a bad
implementation.

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
File base/metrics/persistent_histogram_allocator.h (right):

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persisten...
base/metrics/persistent_histogram_allocator.h:304: template <typename T>
On 2016/04/14 19:30:03, Alexei Svitkine wrote:
> On 2016/04/13 22:45:03, bcwhite wrote:
> > On 2016/04/13 15:53:50, Alexei Svitkine wrote:
> > > Does this need to be a template if we know it's managing data for a sparse
> > > histogram? Can it be concrete and named appropriately for what it's
> querying?
> > 
> > It's a template because the type on which it's used is private to other
files.
> 
> > This class doesn't know the format of the record, just that it exists.
> > 
> > The type could be made public but it works better to keep it completely
> > encapsulated in the PersistentSampleMap and have this class call that one to
> do
> > the low-level work.
> 
> Okay, maybe mention that in the method comment. Otherwise, it's confusing why
> it's a template.

Will do.

bcwhite

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persistent_histogram_allocator.cc File base/metrics/persistent_histogram_allocator.cc (right): https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persistent_histogram_allocator.cc#newcode694 base/metrics/persistent_histogram_allocator.cc:694: return records_[seen_++]; On 2016/04/15 02:36:18, bcwhite wrote: > On ...

4 years, 8 months ago (2016-04-15 14:12:57 UTC) #17

Alexei Svitkine (slow)

lgtm https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persistent_histogram_allocator.cc File base/metrics/persistent_histogram_allocator.cc (right): https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persistent_histogram_allocator.cc#newcode635 base/metrics/persistent_histogram_allocator.cc:635: for (int count = 0; !found || count ...

4 years, 8 months ago (2016-04-15 15:05:07 UTC) #18

bcwhite

https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persistent_histogram_allocator.cc File base/metrics/persistent_histogram_allocator.cc (right): https://codereview.chromium.org/1840843004/diff/220001/base/metrics/persistent_histogram_allocator.cc#newcode635 base/metrics/persistent_histogram_allocator.cc:635: for (int count = 0; !found || count < ...

4 years, 8 months ago (2016-04-15 18:23:02 UTC) #19

commit-bot: I haz the power

CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1840843004/360001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1840843004/360001

4 years, 8 months ago (2016-04-18 00:11:50 UTC) #22

commit-bot: I haz the power

4 years, 8 months ago (2016-04-18 01:34:30 UTC) #25

Message was sent while issue was closed.

Patchset 10 (id:??) landed as
https://crrev.com/b0bb9194eb7b530cdd16ca926e94d424b6766746
Cr-Commit-Position: refs/heads/master@{#387841}

Expand Messages | Collapse Messages | Show Generated Messages | Hide Generated Messages