Eliminate use of vector<pair> in flat_map to save on binary size |
|||||||||||
Issue descriptionSee the link to graphs below.
,
Jun 5 2017
Rev range is a single change: commit 6f5b3053ff11488b985c18e8d03472356e049fd5 author alexclarke <alexclarke@chromium.org> Fri Jun 02 14:32:30 2017 committer Commit Bot <commit-bot@chromium.org> Fri Jun 02 14:32:30 2017 DevTools protocol interception, blocking & modification of requests
,
Jun 8 2017
Size breakdown: https://chromeperf.appspot.com/report?sid=a097e74b1aa288511afb4cb616efe0f95ba4d347ad61d5e835072f23450938ba&rev=476635 Almost entirely from growth in native code. Running: tools/binary_size/diagnose_bloat.py --cloud 6f5b3053ff11488b985c18e8d03472356e049fd5 Gives: Section Sizes (Total=22.8kb (23320 bytes)): .bss: 0 bytes (0 bytes) (not included in totals) .data: 32 bytes (32 bytes) (0.1%) .data.rel.ro: 656 bytes (656 bytes) (2.8%) .data.rel.ro.local: 128 bytes (128 bytes) (0.5%) .rodata: 1024 bytes (1024 bytes) (4.4%) .text: 21.0kb (21480 bytes) (92.1%) 201 symbols added (+), 277 changed (~), 0 removed (-), 379580 unchanged (not shown) 1 paths added, 0 removed, 264 changed Details: Common Metadata: apk_file_name=apks/MonochromePublic.apk elf_arch=arm elf_file_name=lib.unstripped/libmonochrome.so gn_args=ffmpeg_branding="Chrome" goma_dir="/b/build/slave/cache/goma_client" is_chrome_branded=true is_debug=false is_official_build=true proprietary_codecs=true strip_absolute_paths_from_debug_symbols=true symbol_level=1 target_os="android" use_goma=true map_file_name=lib.unstripped/libmonochrome.so.map.gz tool_prefix=third_party/android_tools/ndk/toolchains/arm-linux-androideabi-4.9/prebuilt/linux-x86_64/bin/arm-linux-androideabi- Old Metadata: elf_build_id=88432c0f6851cd96fb1e3ab62a69c691c66c9561 elf_mtime=2017-06-04 01:42:57 git_revision=4cb7c3991639f0275c790e357cf80d3a0565a028 New Metadata: elf_build_id=382ad92200819d476d6cbd6424732bbc9550f19a elf_mtime=2017-06-04 01:49:05 git_revision=6f5b3053ff11488b985c18e8d03472356e049fd5 Section Sizes (Total=22.8kb (23320 bytes)): .bss: 0 bytes (0 bytes) (not included in totals) .data: 32 bytes (32 bytes) (0.1%) .data.rel.ro: 656 bytes (656 bytes) (2.8%) .data.rel.ro.local: 128 bytes (128 bytes) (0.5%) .rodata: 1024 bytes (1024 bytes) (4.4%) .text: 21.0kb (21480 bytes) (92.1%) 201 symbols added (+), 277 changed (~), 0 removed (-), 379580 unchanged (not shown) 1 paths added, 0 removed, 264 changed Showing 478 symbols (464 unique) with total pss: 22340 bytes .text=20.0kb .rodata=1024 bytes .data*=816 bytes .bss=0 bytes total=21.8kb Number of unique paths: 264 Index, Running Total, Section@Address, PSS ------------------------------------------------------------ ~ 0) 2048 (9.2%) r@0x2a9a848 2048 v8/src/json-stringifier.cc ~ 1) 12 (0.1%) r@0x2a97468 -2036 v8/src/compiler/c-linkage.cc + 2) 1262 (5.6%) t@Group 1250 content/browser/devtools/devtools_url_interceptor_request_job.cc content::DevToolsURLInterceptorRequestJob::ContinueInterceptedRequest (count=2) + 3) 2450 (11.0%) t@0xbdc9fc 1188 content/browser/devtools/protocol/network.cc content::protocol::Network::DispatcherImpl::continueInterceptedRequest + 4) 3482 (15.6%) t@0xc56e4c 1032 content/browser/devtools/protocol/network_handler.cc content::protocol::NetworkHandler::ContinueInterceptedRequest + 5) 4250 (19.0%) r@0x2c9cde0 768 third_party/android_tools/ndk/sources/cxx-stl/llvm-libc++/libs/armeabi-v7a/libc++_static.a/locale_android.o ~ 6) 4978 (22.3%) r@0x2bbb990 728 third_party/webrtc/pc/peerconnectionfactory.cc ~ 7) 5609 (25.1%) r@Group 631 {{no path}} ** merge strings (count=6) + 8) 6169 (27.6%) t@0xc4e6ac 560 content/browser/devtools/devtools_url_interceptor_request_job.cc content::DevToolsURLInterceptorRequestJob::DevToolsURLInterceptorRequestJob + 9) 6721 (30.1%) t@0xc4fac0 552 content/browser/devtools/devtools_url_request_interceptor.cc content::DevToolsURLRequestInterceptor::State::ContinueInterceptedRequestOnIoThread + 10) 7259 (32.5%) t@0xc5161c 538 content/browser/devtools/devtools_url_request_interceptor.cc std::__ndk1::vector::insert + 11) 7763 (34.7%) t@0xc51b34 504 content/browser/devtools/devtools_url_request_interceptor.cc std::__ndk1::vector::emplace + 12) 8263 (37.0%) t@0xc567b0 500 content/browser/devtools/protocol/network_handler.cc content::protocol::NetworkHandler::CreateRequestFromURLRequest + 13) 8761 (39.2%) t@0xc51084 498 content/browser/devtools/devtools_url_request_interceptor.cc std::__ndk1::vector::emplace + 14) 9253 (41.4%) t@0xc4e2dc 492 content/browser/devtools/devtools_url_interceptor_request_job.cc content::DevToolsURLInterceptorRequestJob::OnReceivedRedirect + 15) 9721 (43.5%) t@0xc50144 468 content/browser/devtools/devtools_url_request_interceptor.cc std::__ndk1::vector::insert + 16) 10175 (45.5%) t@0xc4ff80 454 content/browser/devtools/devtools_url_request_interceptor.cc std::__ndk1::vector::insert + 17) 10615 (47.5%) t@0xc51834 440 content/browser/devtools/devtools_url_request_interceptor.cc content::DevToolsURLRequestInterceptor::State::StartInterceptingRequests + 18) 11035 (49.4%) t@0xc4e8ec 420 content/browser/devtools/devtools_url_interceptor_request_job.cc content::DevToolsURLInterceptorRequestJob::MockResponseDetails::MockResponseDetails + 19) 11447 (51.2%) t@0xc5096c 412 content/browser/devtools/devtools_url_request_interceptor.cc content::DevToolsURLRequestInterceptor::State::StopInterceptingRequestsOnIoThread + 20) 11851 (53.0%) t@0xc51304 404 content/browser/devtools/devtools_url_request_interceptor.cc content::DevToolsURLRequestInterceptor::State::MaybeCreateDevToolsURLInterceptorRequestJob + 21) 12239 (54.8%) t@0xbdc260 388 content/browser/devtools/protocol/network.cc content::protocol::Network::RequestInterceptedNotification::toValue const + 22) 12627 (56.5%) t@0xc507e8 388 content/browser/devtools/devtools_url_request_interceptor.cc std::__ndk1::vector::insert ~ 23) 12243 (54.8%) r@0x2c9bad4 -384 third_party/android_tools/ndk/sources/cxx-stl/llvm-libc++/libs/armeabi-v7a/libc++_static.a/hash.o ~ 24) 11867 (53.1%) r@0x2c34728 -376 components/subresource_filter/content/renderer/subresource_filter_agent.cc ~ 25) 11495 (51.5%) r@0x2bbb3a8 -372 third_party/webrtc/pc/peerconnection.cc + 26) 11867 (53.1%) t@0xc50544 372 content/browser/devtools/devtools_url_request_interceptor.cc std::__ndk1::vector::insert ~ 27) 11511 (51.5%) r@0x2bb71a0 -356 third_party/webrtc/p2p/stunprober/stunprober.cc + 28) 11863 (53.1%) t@0xbdd2d4 352 content/browser/devtools/protocol/network.cc content::protocol::Network::Frontend::RequestIntercepted + 29) 12199 (54.6%) d@0x2d93b28 336 content/browser/devtools/devtools_url_request_interceptor.cc content::DevToolsURLRequestInterceptor::State::InterceptedWebContentsObserver [vtable] + 30) 12521 (56.0%) t@0xc4ef74 322 content/browser/devtools/devtools_url_interceptor_request_job.cc content::DevToolsURLInterceptorRequestJob::StopIntercepting + 31) 12825 (57.4%) t@0xc506b8 304 content/browser/devtools/devtools_url_request_interceptor.cc content::DevToolsURLRequestInterceptor::State::StartInterceptingRequestsInternal + 32) 13127 (58.8%) t@0xc50f54 302 content/browser/devtools/devtools_url_request_interceptor.cc std::__ndk1::__split_buffer::emplace_back + 33) 13425 (60.1%) t@0xc50c6c 298 content/browser/devtools/devtools_url_request_interceptor.cc content::DevToolsURLRequestInterceptor::State::GetIdForRequest + 34) 13715 (61.4%) t@0xc51a12 290 content/browser/devtools/devtools_url_request_interceptor.cc std::__ndk1::__split_buffer::emplace_back + 35) 13999 (62.7%) t@0xc4e4d0 284 content/browser/devtools/devtools_url_interceptor_request_job.cc content::DevToolsURLInterceptorRequestJob::Start + 36) 14275 (63.9%) t@0xbda800 276 content/browser/devtools/protocol/network.cc content::protocol::Network::DispatcherImpl::enableRequestInterception ~ 37) 14015 (62.7%) r@0x2aa7948 -260 v8/src/arm/code-stubs-arm.cc
,
Jun 8 2017
Using supersize console, the two vectors are for types: std::__ndk1::vector<pair<content::WebContents*, std::__ndk1::unique_ptr<content::DevToolsURLRequestInterceptor::State::InterceptedWebContentsObserver> > > std::__ndk1::vector<std::__ndk1::pair<net::URLRequest const*, std::__ndk1::basic_string One tweak that would probably reduce code size is to use 4 vectors rather than 2 vectors of pairs. Here's another more concise output from running: Print(Diff().symbols.GroupedByName().Sorted()) 118 symbols added (+), 44 changed (~), 0 removed (-), 289946 unchanged (not shown) 1 paths added, 0 removed, 264 changed Showing 162 symbols (162 unique) with total pss: 22340 bytes .text=20.0kb .rodata=1024 bytes .data*=816 bytes .bss=0 bytes total=21.8kb Number of unique paths: 2919 Index, Running Total, Section@Address, PSS ------------------------------------------------------------ ~ 0) 2220 (9.9%) *@Group 2220 std::__ndk1::vector::insert (count=182) + 1) 3470 (15.5%) *@Group 1250 content::DevToolsURLInterceptorRequestJob::ContinueInterceptedRequest (count=1) + 2) 4658 (20.9%) *@Group 1188 content::protocol::Network::DispatcherImpl::continueInterceptedRequest (count=1) + 3) 5690 (25.5%) *@Group 1032 content::protocol::NetworkHandler::ContinueInterceptedRequest (count=1) ~ 4) 6692 (30.0%) *@Group 1002 std::__ndk1::vector::emplace (count=30) ~ 5) 7542 (33.8%) *@Group 850 base::internal::flat_tree::erase (count=25) ~ 6) 8173 (36.6%) *@Group 631 ** merge strings (count=1) ~ 7) 8765 (39.2%) *@Group 592 std::__ndk1::__split_buffer::emplace_back (count=23) + 8) 9325 (41.7%) *@Group 560 content::DevToolsURLInterceptorRequestJob::DevToolsURLInterceptorRequestJob (count=1) + 9) 9877 (44.2%) *@Group 552 content::DevToolsURLRequestInterceptor::State::ContinueInterceptedRequestOnIoThread (count=1) + 10) 10377 (46.5%) *@Group 500 content::protocol::NetworkHandler::CreateRequestFromURLRequest (count=1) + 11) 10869 (48.7%) *@Group 492 content::DevToolsURLInterceptorRequestJob::OnReceivedRedirect (count=1) + 12) 11329 (50.7%) *@Group 460 content::DevToolsURLInterceptorRequestJob::MockResponseDetails::MockResponseDetails (count=2) + 13) 11769 (52.7%) *@Group 440 content::DevToolsURLRequestInterceptor::State::StartInterceptingRequests (count=1) + 14) 12181 (54.5%) *@Group 412 content::DevToolsURLRequestInterceptor::State::StopInterceptingRequestsOnIoThread (count=1) + 15) 12585 (56.3%) *@Group 404 content::DevToolsURLRequestInterceptor::State::MaybeCreateDevToolsURLInterceptorRequestJob (count=1) + 16) 12973 (58.1%) *@Group 388 content::protocol::Network::RequestInterceptedNotification::toValue const (count=1) ~ 17) 13347 (59.7%) *@Group 374 base::internal::Invoker::RunImpl (count=47) ~ 18) 13713 (61.4%) *@Group 366 base::internal::flat_tree::lower_bound const (count=43) + 19) 14065 (63.0%) *@Group 352 content::protocol::Network::Frontend::RequestIntercepted (count=1) + 20) 14401 (64.5%) *@Group 336 content::DevToolsURLRequestInterceptor::State::InterceptedWebContentsObserver [vtable] (count=1) + 21) 14723 (65.9%) *@Group 322 content::DevToolsURLInterceptorRequestJob::StopIntercepting (count=1) ~ 22) 15027 (67.3%) *@Group 304 base::internal::flat_tree::equal_range const (count=23) + 23) 15331 (68.6%) *@Group 304 content::DevToolsURLRequestInterceptor::State::StartInterceptingRequestsInternal (count=1) + 24) 15629 (70.0%) *@Group 298 content::DevToolsURLRequestInterceptor::State::GetIdForRequest (count=1) + 25) 15913 (71.2%) *@Group 284 content::DevToolsURLInterceptorRequestJob::Start (count=1) + 26) 16189 (72.5%) *@Group 276 content::protocol::Network::DispatcherImpl::enableRequestInterception (count=1) ~ 27) 16463 (73.7%) *@Group 274 std::__ndk1::vector::__swap_out_circular_buffer (count=274) ~ 28) 16717 (74.8%) *@Group 254 base::internal::BindState::Destroy (count=6736) + 29) 16949 (75.9%) *@Group 232 content::DevToolsURLInterceptorRequestJob [vtable] (count=1) + 30) 17181 (76.9%) *@Group 232 content::DevToolsURLRequestInterceptor::State::ContinueInterceptedRequest (count=1) + 31) 17411 (77.9%) *@Group 230 content::DevToolsURLRequestInterceptor::State::InterceptedWebContentsObserver::RenderFrameCreated (count=1) + 32) 17621 (78.9%) *@Group 210 content::DevToolsURLInterceptorRequestJob::~DevToolsURLInterceptorRequestJob (count=1) + 33) 17821 (79.8%) *@Group 200 content::DevToolsURLRequestInterceptor::State::InterceptedWebContentsObserver::RenderFrameDeleted (count=1) ~ 34) 18015 (80.6%) *@Group 194 std::__ndk1::vector::__move_range (count=22) + 35) 18207 (81.5%) *@Group 192 content::SendRedirectInterceptedEventOnUiThread (count=1) ~ 36) 18379 (82.3%) *@Group 172 base::internal::Invoker::Run (count=6015) + 37) 18545 (83.0%) *@Group 166 content::DevToolsURLRequestInterceptor::State::StopInterceptingRequests (count=1) ~ 38) 18704 (83.7%) *@Group 159 ** aggregate padding of diff'ed symbols (count=5) + 39) 18858 (84.4%) *@Group 154 content::DevToolsURLInterceptorRequestJob::SubRequest::SubRequest (count=1) + 40) 19006 (85.1%) *@Group 148 content::DevToolsURLRequestInterceptor::State::ExpectRequestAfterRedirect (count=1) + 41) 19154 (85.7%) *@Group 148 content::SendRequestInterceptedEventOnUiThread (count=1) ~ 42) 19298 (86.4%) *@Group 144 base::flat_map::operator[] (count=19) + 43) 19428 (87.0%) *@Group 130 content::DevToolsURLRequestInterceptor::State::~State (count=1) + 44) 19556 (87.5%) *@Group 128 content::protocol::NetworkHandler::EnableRequestInterception (count=1) + 45) 19668 (88.0%) *@Group 112 content::DevToolsURLRequestInterceptor::Modifications::Modifications (count=1) ~ 46) 19778 (88.5%) *@Group 110 std::__ndk1::__split_buffer::~__split_buffer (count=463) + 47) 19886 (89.0%) *@Group 108 content::DevToolsURLRequestInterceptor::DevToolsURLRequestInterceptor (count=1) ~ 48) 19992 (89.5%) *@Group 106 base::internal::Invoker::RunOnce (count=810) ~ 49) 20096 (90.0%) *@Group 104 content::protocol::Network::DispatcherImpl::DispatcherImpl (count=1) ~ 50) 20196 (90.4%) *@Group 100 base::BindOnce (count=46) + 51) 20276 (90.8%) *@Group 80 content::protocol::resourcePriority (count=1) + 52) 20352 (91.1%) *@Group 76 content::protocol::Network::RequestInterceptedNotification::~RequestInterceptedNotification (count=1) ~ 53) 20428 (91.4%) *@Group 76 std::__ndk1::__vector_base::~__vector_base (count=758) + 54) 20500 (91.8%) *@Group 72 content::DevToolsURLRequestInterceptor::State::InterceptedWebContentsObserver::~InterceptedWebContentsObserver (count=1) ~ 55) 20428 (91.4%) *@Group -72 content::protocol::NetworkHandler::NavigationPreloadRequestSent (count=1) + 56) 20492 (91.7%) *@Group 64 content::DevToolsURLRequestInterceptor::Modifications::~Modifications (count=1) + 57) 20550 (92.0%) *@Group 58 content::DevToolsURLInterceptorRequestJob::MockResponseDetails::ReadRawData (count=1) + 58) 20608 (92.2%) *@Group 58 content::DevToolsURLRequestInterceptor::State::RegisterSubRequest (count=1) + 59) 20662 (92.5%) *@Group 54 content::DevToolsURLInterceptorRequestJob::RequestDetails::RequestDetails (count=1) + 60) 20716 (92.7%) *@Group 54 content::DevToolsURLRequestInterceptor::State::InterceptedPage::operator= (count=1) + 61) 20768 (93.0%) *@Group 52 content::DevToolsURLRequestInterceptor::~DevToolsURLRequestInterceptor (count=1) ~ 62) 20820 (93.2%) *@Group 52 content::StoragePartitionImplMap::Get (count=1) + 63) 20872 (93.4%) *@Group 52 content::protocol::Network::ContinueInterceptedRequestCallbackImpl::~ContinueInterceptedRequestCallbackImpl (count=1) + 64) 20922 (93.7%) *@Group 50 content::DevToolsURLRequestInterceptor::State::GetJob const (count=1) + 65) 20970 (93.9%) *@Group 48 content::ProxyUploadElementReader [vtable] (count=1) + 66) 21018 (94.1%) *@Group 48 content::protocol::Network::ContinueInterceptedRequestCallbackImpl [vtable] (count=1) + 67) 21062 (94.3%) *@Group 44 content::DevToolsURLInterceptorRequestJob::OnResponseStarted (count=1) + 68) 21106 (94.5%) *@Group 44 content::DevToolsURLRequestInterceptor::State::State (count=1) + 69) 21148 (94.7%) *@Group 42 content::DevToolsURLInterceptorRequestJob::RequestDetails::~RequestDetails (count=1) + 70) 21188 (94.8%) *@Group 40 content::DevToolsURLInterceptorRequestJob::SubRequest::~SubRequest (count=1) + 71) 21228 (95.0%) *@Group 40 content::DevToolsURLRequestInterceptor::State::ContinueInterceptedRequestOnIoThread::__func__ (count=1) ...
,
Jun 9 2017
The data structures involved are a bunch of base::flat_map/flat_sets. I suppose I could merge the |sub_requests_| and the |expected_redirects_| but that feels like the sort of micro optimisation we shouldn't be encouraging. I think developers should be able to use these data structures without fear of too much template bloat, so maybe it makes sense to tweak the implementation of base::flat_map? +brettw WDYT? Here's the newly added flat maps: https://cs.chromium.org/chromium/src/content/browser/devtools/devtools_url_request_interceptor.h?type=cs&q=base::flat_map%3CWebContents*&l=166
,
Jun 9 2017
Ah, interesting. Didn't realize the pair<>s were coming from flat_map.
Just did a test by checking out this commit, and converting all flat_map & flat_set within devtools_url_request_interceptor.{cc,h} to std::map, std::set (8 in total. 6 in .h, 2 in .cc). The binary shrank by 5812 bytes.
Hopefully we can fix this in flat_*.h and get some bigger savings.
,
Jun 12 2017
Removing sheriff label as relevant owners have been assigned/cc'ed.
,
Jun 13 2017
I'm going to assign this to Brett for now. Brett WDYT, is there something in flat_map that could be tweaked?
,
Jun 15 2017
Updating title to reflect current task.
I had a look at flat_map.h, and it looks like the vector<pair> comes from the decision to have flat_tree store the keys inside the values, and then have a "GetKeyFromValue" function. This format allows flat_set to reuse flat_tree and just tell it not to store the key with the value.
This seems like it might be fairly easy to change, by having flat_map store a vector<value> separate from flat_tree. However, there are also some vector<pair<>> that appear in the public interface. Specifically:
flat_map(std::vector<value_type> items,
FlatContainerDupes dupe_handling,
const Compare& comp = Compare());
flat_map(std::initializer_list<value_type> ilist,
FlatContainerDupes dupe_handling,
const Compare& comp = Compare());
flat_map& operator=(std::initializer_list<value_type> ilist);
value_type is defined as std::pair<Key, Value>.
The initializer lists match std::map's api, but I don't see std::map with an overload that accepts a vector<pair>:
http://en.cppreference.com/w/cpp/container/map/map
I don't have time right now to look at this further, but my best guess here is:
1. Remove the vector constructor
2. Store values as a separate vector directly in flat_map, and change from using a "GetKeyFromValue", to a "GetValueFromKey", which uses the address of the key to calculate its index, and then use that index for the values vector.
Moving brettw back to CC in case he wants to pick this up / comment, but I think the analysis is basically done.
Also related: a bug for looking at why vector is so big: bug 733470
,
Jun 15 2017
The iterator of a base::flat_map is defined to be a pair<Key, Value>. This should be the same as std::map. Changing this would require changing all iterators from pointers to a complicated iterator wrapper that provides a redirection from (first, second) to the underlying storage. I *think* this is possible, but there may be some gotchas. It's definitely non-trivial. This wrapper will also add its own code bloat. I'm not sure what the net will be. I would also like to point out that the vector constructors are not there just for fun. Because a flat_map is much slower than std::map to mutate (linear time per mutation), the recommended pattern for constructing one is to fill a vector with the items and do one-shot construction with it which is optimized. This optimization netted measurable improvements in the JSON parser, for example. Removing the moved vector constructor will require an additional copy/move for each element in such scenarios.
,
Jun 15 2017
Based on bug 733470, I think the majority of the bloat caused by vectors is from them having to be able to resize (and thus call constructors & destructors, which are different for each type). We'll have to try and see, but it may be the case that we could leave the vector constructor, and then only pay that cost when it's used. Good point about the iterators needing to change. Since they won't result in calling constructors, I'd guess there would still be a good savings, but we'll just need to try and see.
,
Jun 23 2017
,
Sep 6 2017
,
Aug 1
|
|||||||||||
►
Sign in to add a comment |
|||||||||||
Comment 1 by m...@chromium.org
, Jun 5 2017