Use a better buffer growth strategy during XDR encoding

RESOLVED FIXED in mozilla36

Status

()

defect
RESOLVED FIXED
5 years ago
5 years ago

People

(Reporter: njn, Assigned: njn)

Tracking

unspecified
mozilla36
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment)

(Assignee)

Description

5 years ago
For XDR encoding we have a buffer that must grow when it gets too small. We
uses a really silly strategy for this -- we grow it in 8 KiB increments. (Or
occasionally more, when the current write is larger than 8 KiB, which is rare.)

Just during startup the buffers get over 500 KiB on my Linux64 machine. So
we're doing *lots* of reallocs: 8 KiB, 16, 24, 32, ... 496, 504, ...,
etc. A doubling strategy would be better.
(Assignee)

Comment 1

5 years ago
(Luke, Igor wrote this code originally and you reviewed it, which is why you
get this review :)

This patch uses a doubling strategy with a minimum of 8 KiB. During start-up it
reduces the number of allocations from 1677 to 1428, and reduces their
cumulative size from 51 MB to 21 MB. (The avoided allocations are mostly large,
which explains why the cumulative size improvement is much higher than the
number of allocations improvement.)

Here are histograms of the most common size increases, where each entry is
weighted by the new size.

Before patch:

51560448 counts:
(  1)  9461760 (18.4%, 18.4%): grown:0 -> 8192
(  2)   589824 ( 1.1%, 19.5%): grown:581629 -> 589824
(  3)   581632 ( 1.1%, 20.6%): grown:573208 -> 581632
(  4)   573440 ( 1.1%, 21.7%): grown:565104 -> 573440
(  5)   565248 ( 1.1%, 22.8%): grown:556762 -> 565248
(  6)   557056 ( 1.1%, 23.9%): grown:548840 -> 557056
(  7)   548864 ( 1.1%, 25.0%): grown:540669 -> 548864
(  8)   540672 ( 1.0%, 26.0%): grown:532472 -> 540672
(  9)   532480 ( 1.0%, 27.1%): grown:524268 -> 532480
( 10)   524288 ( 1.0%, 28.1%): grown:516095 -> 524288

(So e.g. we grew from 0 to 8192 bytes 1155 times, for a cumulative size of
9461760 bytes; we grew from 581629 to 581632 once; etc.)

After patch:

21667840 counts:
(  1)  9461760 (43.7%, 43.7%): grown:0 -> 8192
(  2)  1048576 ( 4.8%, 48.5%): grown:524268 -> 1048576
(  3)   524288 ( 2.4%, 50.9%): grown:262143 -> 524288
(  4)   393216 ( 1.8%, 52.7%): grown:65533 -> 131072
(  5)   327680 ( 1.5%, 54.3%): grown:32767 -> 65536
(  6)   327680 ( 1.5%, 55.8%): grown:16383 -> 32768
(  7)   294912 ( 1.4%, 57.1%): grown:16384 -> 32768
(  8)   294912 ( 1.4%, 58.5%): grown:8192 -> 16384
(  9)   262144 ( 1.2%, 59.7%): grown:130287 -> 262144
( 10)   262144 ( 1.2%, 60.9%): grown:32766 -> 65536

The peak buffer size has gone up from 589824 to 1048576 bytes, but that's ok.
Peak memory usage should still be lower, because reallocating from 581629 to
589824 bytes requires 1171453 bytes.
Attachment #8506493 - Flags: review?(luke)
Comment on attachment 8506493 [details] [diff] [review]
Use a better buffer growth strategy during XDR encoding

Whoa, good catch.  I think in ye olde days, there was this unspoken assumption that realloc internally used a doubling strategy so that, if you realloc'd with constant increases, you'd actually get the amortized O(n) behavior that doubling gives you... or something... I rewrote pretty much all that code to use js::Vector :)

ooc, was this found as part of some program to track down overly-frequent malloc/realloc offenders?
Attachment #8506493 - Flags: review?(luke) → review+
(Assignee)

Comment 3

5 years ago
> Whoa, good catch.  I think in ye olde days, there was this unspoken
> assumption that realloc internally used a doubling strategy so that, if you
> realloc'd with constant increases, you'd actually get the amortized O(n)
> behavior that doubling gives you... or something...

That is an interesting assumption.

> ooc, was this found as part of some program to track down overly-frequent
> malloc/realloc offenders?

Kinda, yeah. I tried making DMD simply ignore all free() calls so it profiles the cumulative heap allocations rather than the live ones. One thing this does is identify places where we have lots of heap churn.

I've found a few other interesting things. E.g. we call deflateInit() a *lot* for compressing JS code, and every time we do that we allocate over 100 KiB of buffers... keeping a single deflate instance around would avoid that. Bugs to follow.
rock on dude
https://hg.mozilla.org/mozilla-central/rev/83544b7dad71
Status: ASSIGNED → RESOLVED
Last Resolved: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla36
(Assignee)

Updated

5 years ago
You need to log in before you can comment on or make changes to this bug.