std::deque default block size (4096) is too generous

[llvmbot]

Bugzilla Link	32435
Version	unspecified
OS	All
Reporter	LLVM Bugzilla Contributor
CC	@mclow,@nico

Extended Description

Hi,

I profiled STL containers in Chrome on Android and found that std::deque (std::queue, std::stack) wastes considerable amount of memory because of its 4096-byte block size. I'm proposing changing block size to 512 bytes and min block length to 1.

More info in the doc: https://docs.google.com/document/d/1PEuPnSW54LaoWpUIEAHobqGt9nbD2DgQ_W5DdlJOkJU/edit#

[nico]

Eric, dskiba found that std::deque storage with libc++ in chrome/android wastes 447KiB of memory (see linked doc in comment 0, should be world-readable). I suggested that we try to fix this in upstream libc++ instead of carrying local patches. Does that sound fine to you?

[llvmbot]

If the changes bring a performance improvement then I would greatly appreciate them as an upstream contribution (Although I haven't actually looked at them at this point).

The easiest starting point would be to contribute tests for deque under libcxx/benchmarks. That way we have a baseline of the existing performance that we can test against while reviewing the changes to deque.

[mclow]

I'm proposing changing block size to 512 bytes and min block length to 1.

Speaking without data, I suspect that a smaller block size would make the Chrome people happy (and possibly perform as well), but setting the "min block length" to 1 seems like a pessimization to me. When you have only one element in a block, you have a linked list.

The easiest starting point would be to contribute tests for deque under libcxx/benchmarks.

I agree. Then we can compare apples to apples.

[llvmbot]

Benchmark patch

[llvmbot]

Hi guys! Sorry for the delay.

I've added a simple benchmark that does push_back / clear with two payloads: cheap (that doesn't anything in the ctor) and costly (which does something). I also added a "model" benchmark, that models deque behavior allocation-wise, i.e. it does similar number of allocations / frees.

I also found that deque is not designed to work with block length of 1: deque::__capacity() always subtracts 1 and messes __back_spare() when we're inserting second element (we're ending up with "0 - 1"). So for 512-byte block I tested with min block length of 2.

Results from my MBP (15", Mid 2014):

4096/16:

Run on (8 X 2200 MHz CPU s)
2017-04-12 15:03:06
Benchmark Time CPU Iterations

BM_PushBackClear/deque_CheapPayload4/3k 5326 ns 5325 ns 120254
BM_PushBackClear/deque_CheapPayload8/3k 5861 ns 5861 ns 115352
BM_PushBackClear/deque_CheapPayload16/3k 6976 ns 6975 ns 99138
BM_PushBackClear/deque_CheapPayload32/3k 9013 ns 9013 ns 78499
BM_PushBackClear/deque_CheapPayload64/3k 12075 ns 12069 ns 57667
BM_PushBackClear/deque_CheapPayload128/3k 19433 ns 19432 ns 36129
BM_PushBackClear/deque_CheapPayload256/3k 30166 ns 30161 ns 23092
BM_PushBackClear/deque_CheapPayload512/3k 30980 ns 30908 ns 23340
BM_PushBackClear/deque_CheapPayload1024/3k 27758 ns 27758 ns 24075

BM_PushBackClear/deque_CostlyPayload4/3k 18166 ns 18164 ns 38322
BM_PushBackClear/deque_CostlyPayload8/3k 35013 ns 34897 ns 18692
BM_PushBackClear/deque_CostlyPayload16/3k 73121 ns 72940 ns 8878
BM_PushBackClear/deque_CostlyPayload32/3k 240866 ns 240616 ns 2996
BM_PushBackClear/deque_CostlyPayload64/3k 550852 ns 550437 ns 1296
BM_PushBackClear/deque_CostlyPayload128/3k 1197040 ns 1195661 ns 551
BM_PushBackClear/deque_CostlyPayload256/3k 2361846 ns 2360227 ns 273
BM_PushBackClear/deque_CostlyPayload512/3k 4544200 ns 4543268 ns 127
BM_PushBackClear/deque_CostlyPayload1024/3k 9093714 ns 9093566 ns 76

BM_ModelPushBackClear/deque_CheapPayload4/3k 183 ns 182 ns 3896183
BM_ModelPushBackClear/deque_CheapPayload8/3k 547 ns 547 ns 1226199
BM_ModelPushBackClear/deque_CheapPayload16/3k 1299 ns 1299 ns 551229
BM_ModelPushBackClear/deque_CheapPayload32/3k 2534 ns 2534 ns 277792
BM_ModelPushBackClear/deque_CheapPayload64/3k 5787 ns 5778 ns 130863
BM_ModelPushBackClear/deque_CheapPayload128/3k 12037 ns 12001 ns 56359
BM_ModelPushBackClear/deque_CheapPayload256/3k 23690 ns 23656 ns 28694
BM_ModelPushBackClear/deque_CheapPayload512/3k 24027 ns 23971 ns 30636
BM_ModelPushBackClear/deque_CheapPayload1024/3k 22072 ns 22065 ns 27568

512/2:

BM_PushBackClear/deque_CheapPayload4/3k 8942 ns 8936 ns 73439
BM_PushBackClear/deque_CheapPayload8/3k 11951 ns 11945 ns 51271
BM_PushBackClear/deque_CheapPayload16/3k 20437 ns 20353 ns 37981
BM_PushBackClear/deque_CheapPayload32/3k 31767 ns 31752 ns 19530
BM_PushBackClear/deque_CheapPayload64/3k 58989 ns 58958 ns 11684
BM_PushBackClear/deque_CheapPayload128/3k 114849 ns 114804 ns 6312
BM_PushBackClear/deque_CheapPayload256/3k 250603 ns 248808 ns 2829
BM_PushBackClear/deque_CheapPayload512/3k 222239 ns 222070 ns 3091
BM_PushBackClear/deque_CheapPayload1024/3k 218928 ns 218789 ns 3419

BM_PushBackClear/deque_CostlyPayload4/3k 23358 ns 23338 ns 30480
BM_PushBackClear/deque_CostlyPayload8/3k 40815 ns 40778 ns 18300
BM_PushBackClear/deque_CostlyPayload16/3k 87919 ns 87769 ns 8591
BM_PushBackClear/deque_CostlyPayload32/3k 273693 ns 272402 ns 2597
BM_PushBackClear/deque_CostlyPayload64/3k 574300 ns 574077 ns 1208
BM_PushBackClear/deque_CostlyPayload128/3k 1319633 ns 1313259 ns 552
BM_PushBackClear/deque_CostlyPayload256/3k 2752349 ns 2745968 ns 249
BM_PushBackClear/deque_CostlyPayload512/3k 5152932 ns 5142412 ns 131
BM_PushBackClear/deque_CostlyPayload1024/3k 9894782 ns 9885284 ns 74

BM_ModelPushBackClear/deque_CheapPayload4/3k 2748 ns 2747 ns 260659
BM_ModelPushBackClear/deque_CheapPayload8/3k 5456 ns 5453 ns 122895
BM_ModelPushBackClear/deque_CheapPayload16/3k 11273 ns 11264 ns 65404
BM_ModelPushBackClear/deque_CheapPayload32/3k 22793 ns 22774 ns 32786
BM_ModelPushBackClear/deque_CheapPayload64/3k 47022 ns 46969 ns 12976
BM_ModelPushBackClear/deque_CheapPayload128/3k 100500 ns 100340 ns 6632
BM_ModelPushBackClear/deque_CheapPayload256/3k 194526 ns 194419 ns 3639
BM_ModelPushBackClear/deque_CheapPayload512/3k 212491 ns 211890 ns 3408
BM_ModelPushBackClear/deque_CheapPayload1024/3k 195754 ns 195746 ns 3334

I added these numbers to a world-editable spreadsheet: https://docs.google.com/spreadsheets/d/1xuQn-6XbzmpETxrKyAK64e7Cq3QJLzm5qMHbTfRmoX4/edit?usp=sharing

As you can see we regress ~20% when payload does something costly in the ctor and offsets overhead of additional allocations.

When payload is dumb, the 512/2 version is up to 6x slower.

However, the difference between real and model test with cheap payload is where it gets interesting. For example for CheapPayload4 real test regressed 67%, but model test regressed 1400%! This suggests that either my CheapPayload is not that cheap, or deque does something not accounted by model test. Any insight is appreciated.

[mclow]

I've got questions about your usage of deque.

What are you using it for?
In general, what are the sizes of the collections that you're storing in the deque? (and the types?).
Are you using deque directly, or via a container adapter (For example, stack)?

[llvmbot]

Here are details of std::deque usage, from the trace in the document (see the first message).

Size Container sizeof(T)

276 std::stack v8::internal::TypedSlotSet::Chunk* 4
244 std::queue base::PendingTask 64
163 std::deque net::SpdyWriteQueue::PendingWrite 20
100 std::deque scoped_refptrgpu::gles2::QueryManager::Query 4
96 std::queue SyncTokenToFenceMap::iterator 4
60 std::deque net::HpackDecoderDynamicTable::HpackDecoderTableEntry 32
56 std::deque gcm::DecryptionFailureActivity 56
40 std::deque unique_ptrRenderFrameImpl::PendingFileChooser 4
24 std::deque unique_ptrmojo::internal::MultiplexRouter::Task 4
24 std::deque net::PriorityWriteScheduler<>::StreamInfo* 4

(Size is total allocated size, in KiB. Data from 32-bit Android release build.)

Totals by Chrome process type / container:

Browser:
std::deque: 446.9 KiB wasted (out of 486.7 KiB)
std::queue: 357.0 KiB wasted (out of 364.1 KiB)
std::stack: 15 KiB wasted (out of 16 KiB)

Renderer:
std::deque: 98.4 KiB wasted (out of 108.1 KiB)
std::queue: 94.7 KiB wasted (out of 96.1 KiB)
std::stack: 297.9 KiB wasted (out of 300 KiB)

GPU:
std::deque: 28 KiB wasted (out of 28 KiB)
std::queue: 56.1 KiB wasted (out of 53.3 KiB)
std::stack: 16 KiB wasted (out of 15.8 KiB)

TOTAL: 1410 KiB wasted (out of 1468.1 KiB)

Where 'wasted' is 'total allocated' - 'total constructed', as seen by counting_allocator (https://chromium-review.googlesource.com/c/419077/3/sources/cxx-stl/llvm-libc%252B%252B/libcxx/include/memory#1892).

[mclow]

Here are details of std::deque usage, from the trace in the document.

Well, shucks. I was kinda hoping that most of your usage would be std::stack, because then I could just say "use std::stack<T, std::vector> instead" and you'd be golden.
That's probably still good advice for your cases, but it's not a complete solution.

(Personally, I think that std::stack should use vector by default instead of deque)

Anyway, thanks for the data.

[llvmbot]

We found a new case where std::deque wastes memory on blocks: crrev.com/719774

What is our next steps here? Do we want to get more data before deciding?

[llvmbot]

Oops, the above bug reference is invalid (crrev.com instead of crbug.com). Clickable link: https://bugs.chromium.org/p/chromium/issues/detail?id=719774

[mclow]

A compromise proposal: Keep the minimum block length at 16 objects, but reduce the minimum block size to 1024 bytes (from 4096). This should save about 75% of the memory for your small deques (storing 20 or so ints), keep stuff aligned on cache lines, and require almost no code changes, while resisting the tendency to degenerate into a linked list.

[llvmbot]

BTW, I switched Chrome for Android to 512/2 (512 byte size block, min 2 blocks), and saw ~1 MiB decrease in all memory benchmarks.

1024 is certainly better than 4096, so I definitely support this direction, but I was thinking of whether we can make deque parameters configurable?

In Chrome we have plans to build libc++ ourselves for several platforms (Android included), and it would be nice to be able to tune deque parameters per platform (i.e. for example to take bitness into account).

[llvmbot]

Ping. Any thoughts on tunable block size idea from #​12?

[llvmbot]

@​dskiba is it OK if I commit a modified version of your benchmark?

[llvmbot]

Sure!

Are you going to change std::deque to have smaller (or tunable) block size?