Align base::Pickle allocations to 4k boundaries

Align base::Pickle allocations to 4k boundaries

Currently the growth logic of base::Pickle (the one that kicks
in exceeding the current capacity when writing) is as follows:
new_payload_capacity = current_payload_capacity * 2
with an initial payload capacity of 64 bytes.

However, the size of the heap held by Pickle (the one which gets
realloc-ated on each growth) is:
payload_capacity + header_size (typically 4-20 bytes).

In practice, this means that when the Pickle is expanded, the
size of its underlying heap becomes a power of two plus some extra.
This causes funky behaviors of realloc, which makes extremely
difficult to estimate the size of a pickle (for the sake of
memory profiling, Pickle is used to store TracedValue(s)).

This CL adds a small adjustment to the Pickle growth strategy,
making the underlying realloc sizes close to a full page size.
This in turn makes the realloc behavior much more predictable.

As a bonus this CL refactors the use of "Align", moving it to
base/bits.h

BUG=512383
Committed: https://crrev.com/32a7f50559fbaf7319a32048383d4c790f2a3c20
Cr-Commit-Position: refs/heads/master@{#340318}

[Primiano Tucci (use gerrit), 2015-07-23 20:56:13]

Patchset #1 (id:1) has been deleted

[Primiano Tucci (use gerrit), 2015-07-23 20:57:32]

primiano@chromium.org changed reviewers:
+ piman@chromium.org

[Primiano Tucci (use gerrit), 2015-07-23 21:00:45]

piman@ you seem to have done some micro-optimizations to Pickle. Could you
please take a look to base/pickle.cc?
The rest of the CL is just refactoring / cleanup, I'll pick a base OWNER for
that. I just want to doublecheck that this is not breaking any intended
behavior.

My feeling looking at the code is that the header_size was overlooked when doing
the "* 2" growth rule and this was not intended.
Is that right?

[piman, 2015-07-23 22:37:06]

On 2015/07/23 21:00:45, Primiano Tucci wrote:
> piman@ you seem to have done some micro-optimizations to Pickle. Could you
> please take a look to base/pickle.cc?
> The rest of the CL is just refactoring / cleanup, I'll pick a base OWNER for
> that. I just want to doublecheck that this is not breaking any intended
> behavior.
> 
> My feeling looking at the code is that the header_size was overlooked when
doing
> the "* 2" growth rule and this was not intended.
> Is that right?

Well, the header itself doesn't grow, only the payload, right? The *2 growth is
to avoid O(n^2) behavior... it wasn't particularly meant to align to malloc
bucket sizes.

Do we really need to grow to 4k as soon as we're >64 bytes? tcmalloc for example
has a *lot* of intermediate bucket sizes (see about:tcmalloc for example).

[piman, 2015-07-23 22:37:11]

https://codereview.chromium.org/1249643007/diff/40001/base/pickle.cc
File base/pickle.cc (right):

https://codereview.chromium.org/1249643007/diff/40001/base/pickle.cc#newcode217
base/pickle.cc:217: pickle_kpayloadunit_must_be_a_power_of_two);
nit: static_assert

https://codereview.chromium.org/1249643007/diff/40001/base/pickle.cc#newcode379
base/pickle.cc:379: Resize(std::max(new_capacity, new_size));
You may want to do the Align after the max to get the full benefits. What do you
think?

[Primiano Tucci (use gerrit), 2015-07-23 23:00:50]

> Well, the header itself doesn't grow, only the payload, right? 
Correct

> Do we really need to grow to 4k as soon as we're >64 bytes? tcmalloc for
example
> has a *lot* of intermediate bucket sizes (see about:tcmalloc for example).

No, that was me doing something stupid. I fixed it in patchset 2 (I think I sent
it while you were reviewing PS1)
I meant to align only after passing the 4k barrier, not unconditionally, look at
PS2 (sorry for the double round).
My problem here is just large pickles (when they become 16k + 4, 32k + 4 etc).
<4k are fine.
After passing 4k, instead, aligning makes a marginal difference on the actual
size of the pickle (and allocator buckets are usually exponential), but makes a
huge difference for the predictability.

>You may want to do the Align after the max to get the full benefits. What do
you think?
See PS2. When I'm < 4k, I don't align at all anymore.
When it's > 4k, the max is almost never hit, as the *2 growth dominates the
overflow (which is typicaly smaller, it's unlikely that you write a 4k string
into a pickle).
So I'd probably keep it and a void adding a third if in that logic, WDYT?

[piman, 2015-07-23 23:10:36]

OK, LGTM after nit.

[Primiano Tucci (use gerrit), 2015-07-23 23:24:01]

primiano@chromium.org changed reviewers:
+ thestig@chromium.org

[Primiano Tucci (use gerrit), 2015-07-23 23:24:02]

+thestig as base/ OWNER

[Lei Zhang, 2015-07-24 01:36:48]

In the commit msg, there's a typo: "onw"

https://codereview.chromium.org/1249643007/diff/60001/base/trace_event/trace_...
File base/trace_event/trace_event_argument.cc (right):

https://codereview.chromium.org/1249643007/diff/60001/base/trace_event/trace_...
base/trace_event/trace_event_argument.cc:457: const size_t kPickleAlignment =
4096;
Is this assuming |kPickleHeapAlign| in pickle.cc is 4096?

https://codereview.chromium.org/1249643007/diff/60001/base/trace_event/trace_...
File base/trace_event/trace_event_memory_overhead.cc (right):

https://codereview.chromium.org/1249643007/diff/60001/base/trace_event/trace_...
base/trace_event/trace_event_memory_overhead.cc:59: //  - longer stings seem to
malloc() multiples of 16 bytes.
BTW, typo: "stings"

[Primiano Tucci (use gerrit), 2015-07-24 09:37:38]

See answers inline. I also added a test to bits_unittest.cc to cover the Align

>In the commit msg, there's a typo: "onw"
Done

https://codereview.chromium.org/1249643007/diff/60001/base/trace_event/trace_...
File base/trace_event/trace_event_argument.cc (right):

https://codereview.chromium.org/1249643007/diff/60001/base/trace_event/trace_...
base/trace_event/trace_event_argument.cc:457: const size_t kPickleAlignment =
4096;
On 2015/07/24 01:36:48, Lei Zhang wrote:
> Is this assuming |kPickleHeapAlign| in pickle.cc is 4096?

Yes. It felt a bit of a stretch exposing it as a public const of base::Pickle as
it is an implementation detail and I find hard to think about other cases where
you need to know the heap size of Pickle. WDYT?
Should I move it to be Pickle::kPickleHeapAlign ?

I changed the name here (to match kPickleHeapAlign) and added a comment

https://codereview.chromium.org/1249643007/diff/60001/base/trace_event/trace_...
File base/trace_event/trace_event_memory_overhead.cc (right):

https://codereview.chromium.org/1249643007/diff/60001/base/trace_event/trace_...
base/trace_event/trace_event_memory_overhead.cc:59: //  - longer stings seem to
malloc() multiples of 16 bytes.
On 2015/07/24 01:36:48, Lei Zhang wrote:
> BTW, typo: "stings"

Ah, thanks

[Lei Zhang, 2015-07-24 18:59:54]

The CQ bit was checked by thestig@chromium.org

[Lei Zhang, 2015-07-24 18:59:55]

lgtm

https://codereview.chromium.org/1249643007/diff/60001/base/trace_event/trace_...
File base/trace_event/trace_event_argument.cc (right):

https://codereview.chromium.org/1249643007/diff/60001/base/trace_event/trace_...
base/trace_event/trace_event_argument.cc:457: const size_t kPickleAlignment =
4096;
On 2015/07/24 09:37:38, Primiano Tucci (OOO til Aug 9) wrote:
> On 2015/07/24 01:36:48, Lei Zhang wrote:
> > Is this assuming |kPickleHeapAlign| in pickle.cc is 4096?
> 
> Yes. It felt a bit of a stretch exposing it as a public const of base::Pickle
as
> it is an implementation detail and I find hard to think about other cases
where
> you need to know the heap size of Pickle. WDYT?
> Should I move it to be Pickle::kPickleHeapAlign ?
> 
> I changed the name here (to match kPickleHeapAlign) and added a comment

Ok. Maybe expose it if we ever find another need to expose it.

https://codereview.chromium.org/1249643007/diff/80001/base/bits_unittest.cc
File base/bits_unittest.cc (right):

https://codereview.chromium.org/1249643007/diff/80001/base/bits_unittest.cc#n...
base/bits_unittest.cc:50: TEST(BitsTest, Align) {
Thanks!

[Lei Zhang, 2015-07-24 18:59:55]

The patchset sent to the CQ was uploaded after l-g-t-m from piman@chromium.org
Link to the patchset: https://codereview.chromium.org/1249643007/#ps80001
(title: "Nits   test")

[commit-bot: I haz the power, 2015-07-24 19:00:19]

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

[commit-bot: I haz the power, 2015-07-24 20:13:41]

Committed patchset #4 (id:80001)

[commit-bot: I haz the power, 2015-07-24 20:14:23]

Patchset 4 (id:??) landed as
https://crrev.com/32a7f50559fbaf7319a32048383d4c790f2a3c20
Cr-Commit-Position: refs/heads/master@{#340318}