diff options
author | 2017-03-08 14:17:49 -0500 | |
---|---|---|
committer | 2017-03-08 19:58:36 +0000 | |
commit | 7dd57b6a936af923a031f21c4ca9dc1031742473 (patch) | |
tree | 98bdb5820902b13dbc1f3f8597ff215ddeb5f883 /src | |
parent | 91b961d33d1d3e78c212be8738c1c7c468c358ca (diff) |
Use Fibonacci instead of 2^n for block growth.
Chrome on android showed an increase of 5% memory use when 2^n block
growth was introduced. Use Fibonacci instead.
BUG=chromium:699130
Change-Id: I228d66385c63d487e72db46356f44e9efb5fa0f3
Reviewed-on: https://skia-review.googlesource.com/9447
Reviewed-by: Ben Wagner <bungeman@google.com>
Commit-Queue: Herb Derby <herb@google.com>
Diffstat (limited to 'src')
-rw-r--r-- | src/core/SkArenaAlloc.cpp | 5 | ||||
-rw-r--r-- | src/core/SkArenaAlloc.h | 11 |
2 files changed, 9 insertions, 7 deletions
diff --git a/src/core/SkArenaAlloc.cpp b/src/core/SkArenaAlloc.cpp index 779eaff0f1..eca3aa97d7 100644 --- a/src/core/SkArenaAlloc.cpp +++ b/src/core/SkArenaAlloc.cpp @@ -100,8 +100,9 @@ void SkArenaAlloc::ensureSpace(uint32_t size, uint32_t alignment) { objSizeAndOverhead += alignment - 1; } - uint32_t allocationSize = std::max(objSizeAndOverhead, fExtraSize << fLogGrowth); - fLogGrowth++; + uint32_t allocationSize = std::max(objSizeAndOverhead, fExtraSize * fFib0); + fFib0 += fFib1; + std::swap(fFib0, fFib1); // Round up to a nice size. If > 32K align to 4K boundary else up to max_align_t. The > 32K // heuristic is from the JEMalloc behavior. diff --git a/src/core/SkArenaAlloc.h b/src/core/SkArenaAlloc.h index 04f929181c..494696ce76 100644 --- a/src/core/SkArenaAlloc.h +++ b/src/core/SkArenaAlloc.h @@ -54,8 +54,9 @@ // addition overhead when switching from POD data to non-POD data of typically 8 bytes. // // If additional blocks are needed they are increased exponentially. This strategy bounds the -// recursion of the RunDtorsOnBlock to be limited to O(ln size-of-memory). In practical terms, this -// is a maximum recursion depth of 33 for an 8GB machine but usually much less. +// recursion of the RunDtorsOnBlock to be limited to O(log size-of-memory). Block size grow using +// the Fibonacci sequence which means that for 2^32 memory there are 48 allocations, and for 2^48 +// there are 71 allocations. class SkArenaAlloc { public: SkArenaAlloc(char* block, size_t size, size_t extraSize = 0); @@ -196,9 +197,9 @@ private: char* const fFirstBlock; const uint32_t fFirstSize; const uint32_t fExtraSize; - // The extra size allocations grow exponentially: - // size-allocated = extraSize * 2 ^ fLogGrowth. - uint8_t fLogGrowth {0}; + // Use the Fibonacci sequence as the growth factor for block size. The size of the block + // allocated is fFib0 * fExtraSize. Using 2 ^ n * fExtraSize had too much slop for Android. + uint32_t fFib0 {1}, fFib1 {1}; }; #endif//SkFixedAlloc_DEFINED |