Closed
Bug 1376678
Opened 8 years ago
Closed 8 years ago
MFBT's Vector doesn't use exponential growth
Categories
(Core :: MFBT, enhancement)
Core
MFBT
Tracking
()
RESOLVED
INVALID
People
(Reporter: ehsan.akhgari, Unassigned)
References
Details
See this call: <https://searchfox.org/mozilla-central/rev/fdb811340ac4e6b93703d72ee99217f3b1d250ac/js/src/json.cpp#78>
StringBuffer uses MFBT Vector internally, so this appendSubstring() call grows the buffer only by the amount appended, so the loop is O(n2) due to the memcpy involved, I think.
We fixed this for nsTArray in bug 1048044. Nick, what is your recommendation about Vector, if any?
Flags: needinfo?(n.nethercote)
|
||
Comment 1•8 years ago
|
||
Why do you think Vector doesn't use exponential growth? I'm certain it does, see growStorageBy() and also CapacityHasExcessSpace(). The latter function was added in bug 685783 to reduce wasted space in some cases, but Vector used exponential growth even before that.
Flags: needinfo?(n.nethercote)
|
Reporter | |
Comment 2•8 years ago
|
||
Hmm yes you're right. I'm surprised about what made me think this. It seems like the realloc/memmove cost in this profile is just too high and I got confused somehow along the way following the code. Sorry about the noise.
Status: NEW → RESOLVED
Closed: 8 years ago
Resolution: --- → INVALID
You need to log in
before you can comment on or make changes to this bug.
Description
•