Closed
Bug 1084114
Opened 10 years ago
Closed 10 years ago
Use a better buffer growth strategy during XDR encoding
Categories
(Core :: JavaScript Engine, defect)
Core
JavaScript Engine
Tracking
()
RESOLVED
FIXED
mozilla36
People
(Reporter: n.nethercote, Assigned: n.nethercote)
References
Details
Attachments
(1 file)
1.10 KB,
patch
|
luke
:
review+
|
Details | Diff | Splinter Review |
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•10 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 2•10 years ago
|
||
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•10 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.
Comment 4•10 years ago
|
||
rock on dude
Assignee | ||
Comment 5•10 years ago
|
||
https://hg.mozilla.org/integration/mozilla-inbound/rev/83544b7dad71
Comment 6•10 years ago
|
||
https://hg.mozilla.org/mozilla-central/rev/83544b7dad71
Status: ASSIGNED → RESOLVED
Closed: 10 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla36
Assignee | ||
Updated•10 years ago
|
Depends on: cumulative-heap-profiling
You need to log in
before you can comment on or make changes to this bug.
Description
•