Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
2807953002:
Use base::flat_map for base::Value dictionary storage. (Closed)
DescriptionUse base::flat_map for base::Value dictionary storage.
This should give better memory locality and fewer allocations for our
workloads.
Most dictionaries are small and previously sorted (JSON Chrome writes
like preferences is written in keyed-order). This makes the flat_map
a better storage option because it avoids separate allocation for each
node and has better memory locality.
Performance from base_perftests JSONPerfTest.StressTest:
Old: 84,807ms
Just replacing the storage: 70,363ms
Optimizing JSON parser: 69,286ms
Primarily the improvement is in read performance (in creating the
dictionary nodes) but write performance is also improved slightly,
presumably due to better memory locality.
I did some manual checking for the creation of large dictionary values
(where this change may perform poorly) and did not find any in normal
Chrome runs other than the JSON parser and the value copy constructor.
Bringing flat_map.h into values_unittests.cc seems to confuse MSVC's
ADL resolution of swap and it gives errors about calling
flat_map::swap with base::Values. I wasn't able to figure out the
source of this problem. The test is really checking for operator= that
is generated by the default std::swap implementation (base::Value
doesn't specialize a swap so the "using std/swap" pattern for ADL is a
no-op), so I qualified the call to swap with a std::.
Review-Url: https://codereview.chromium.org/2807953002
Cr-Commit-Position: refs/heads/master@{#463371}
Committed: https://chromium.googlesource.com/chromium/src/+/8dd10d4011015ae6ce376a94666d56696e1ea7cd
Patch Set 1 #Patch Set 2 : Swap #
Total comments: 4
Patch Set 3 : Fix swap #
Messages
Total messages: 30 (19 generated)
Description was changed from ========== Use base::flat_map for base::Value dictionary storage. This should give better memory locality and fewer allocations for our workloads. Most dictionaries are small and previously sorted (JSON Chrome writes like preferences is written in keyed-order). This makes the flat_map a better storage option because it avoids separate allocation for each node and has better memory locality. Performance from base_perftests JSONPerfTest.StressTest: Old: 84,807ms Just replacing the storage: 70,363ms Optimizing JSON parser: 69,286ms Primarily the improvement is in read performance (in creating the dicitonary nodes) but write performance is also improved slightly, presumably due to better memory locality. ========== to ========== Use base::flat_map for base::Value dictionary storage. This should give better memory locality and fewer allocations for our workloads. Most dictionaries are small and previously sorted (JSON Chrome writes like preferences is written in keyed-order). This makes the flat_map a better storage option because it avoids separate allocation for each node and has better memory locality. Performance from base_perftests JSONPerfTest.StressTest: Old: 84,807ms Just replacing the storage: 70,363ms Optimizing JSON parser: 69,286ms Primarily the improvement is in read performance (in creating the dicitonary nodes) but write performance is also improved slightly, presumably due to better memory locality. I did some manual checking for the creation of large dictionary values (where this change may perform poorly) and did not find any in normal Chrome runs other than the JSON parser and the value copy constructor. ==========
brettw@chromium.org changed reviewers: + jdoerrie@chromium.org
The CQ bit was checked by brettw@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: android_clang_dbg_recipe on master.tryserver.chromium.android (JOB_FAILED, https://build.chromium.org/p/tryserver.chromium.android/builders/android_clan...)
Description was changed from ========== Use base::flat_map for base::Value dictionary storage. This should give better memory locality and fewer allocations for our workloads. Most dictionaries are small and previously sorted (JSON Chrome writes like preferences is written in keyed-order). This makes the flat_map a better storage option because it avoids separate allocation for each node and has better memory locality. Performance from base_perftests JSONPerfTest.StressTest: Old: 84,807ms Just replacing the storage: 70,363ms Optimizing JSON parser: 69,286ms Primarily the improvement is in read performance (in creating the dicitonary nodes) but write performance is also improved slightly, presumably due to better memory locality. I did some manual checking for the creation of large dictionary values (where this change may perform poorly) and did not find any in normal Chrome runs other than the JSON parser and the value copy constructor. ========== to ========== Use base::flat_map for base::Value dictionary storage. This should give better memory locality and fewer allocations for our workloads. Most dictionaries are small and previously sorted (JSON Chrome writes like preferences is written in keyed-order). This makes the flat_map a better storage option because it avoids separate allocation for each node and has better memory locality. Performance from base_perftests JSONPerfTest.StressTest: Old: 84,807ms Just replacing the storage: 70,363ms Optimizing JSON parser: 69,286ms Primarily the improvement is in read performance (in creating the dictionary nodes) but write performance is also improved slightly, presumably due to better memory locality. I did some manual checking for the creation of large dictionary values (where this change may perform poorly) and did not find any in normal Chrome runs other than the JSON parser and the value copy constructor. ==========
The CQ bit was checked by brettw@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
Those are great results, thanks a lot for doing this! https://codereview.chromium.org/2807953002/diff/20001/base/values.cc File base/values.cc (right): https://codereview.chromium.org/2807953002/diff/20001/base/values.cc#newcode162 base/values.cc:162: Value::Value(DictStorage&& in_dict) noexcept : type_(Type::DICTIONARY) { Same here. https://codereview.chromium.org/2807953002/diff/20001/base/values.h File base/values.h (right): https://codereview.chromium.org/2807953002/diff/20001/base/values.h#newcode96 base/values.h:96: explicit Value(DictStorage&& in_dict) noexcept; nit: Consider moving this constructor down after the blob constructors. So far I was following the order of Types defined in line 55 when declaring these constructors. https://codereview.chromium.org/2807953002/diff/20001/base/values.h#newcode201 base/values.h:201: ManualConstructor<std::unique_ptr<DictStorage>> dict_ptr_; Now that DictStorage is effectively a vector there is no need to wrap it in a unique_ptr anymore. Dropping the wrapper should increase performance as well with no increase in memory usage. I am fine with both doing this in this CL or in a follow up CL authored by you or me. What do you prefer? https://codereview.chromium.org/2807953002/diff/20001/base/values_unittest.cc File base/values_unittest.cc (right): https://codereview.chromium.org/2807953002/diff/20001/base/values_unittest.cc... base/values_unittest.cc:1529: */ Uncomment this block. Just out of curiosity: It looks like you experimented with custom swaps, what were your findings?
Fix swap
Description was changed from ========== Use base::flat_map for base::Value dictionary storage. This should give better memory locality and fewer allocations for our workloads. Most dictionaries are small and previously sorted (JSON Chrome writes like preferences is written in keyed-order). This makes the flat_map a better storage option because it avoids separate allocation for each node and has better memory locality. Performance from base_perftests JSONPerfTest.StressTest: Old: 84,807ms Just replacing the storage: 70,363ms Optimizing JSON parser: 69,286ms Primarily the improvement is in read performance (in creating the dictionary nodes) but write performance is also improved slightly, presumably due to better memory locality. I did some manual checking for the creation of large dictionary values (where this change may perform poorly) and did not find any in normal Chrome runs other than the JSON parser and the value copy constructor. ========== to ========== Use base::flat_map for base::Value dictionary storage. This should give better memory locality and fewer allocations for our workloads. Most dictionaries are small and previously sorted (JSON Chrome writes like preferences is written in keyed-order). This makes the flat_map a better storage option because it avoids separate allocation for each node and has better memory locality. Performance from base_perftests JSONPerfTest.StressTest: Old: 84,807ms Just replacing the storage: 70,363ms Optimizing JSON parser: 69,286ms Primarily the improvement is in read performance (in creating the dictionary nodes) but write performance is also improved slightly, presumably due to better memory locality. I did some manual checking for the creation of large dictionary values (where this change may perform poorly) and did not find any in normal Chrome runs other than the JSON parser and the value copy constructor. Bringing flat_map.h into values_unittests.cc seems to confuse MSVC's ADL resolution of swap and it gives errors about calling flat_map::swap with base::Values. I wasn't able to figure out the source of this problem. The test is really checking for operator= that is generated by the default std::swap implementation (base::Value doesn't specialize a swap so the "using std/swap" pattern for ADL is a Nno-op), so I qualified the call to swap with a std::. ==========
Description was changed from ========== Use base::flat_map for base::Value dictionary storage. This should give better memory locality and fewer allocations for our workloads. Most dictionaries are small and previously sorted (JSON Chrome writes like preferences is written in keyed-order). This makes the flat_map a better storage option because it avoids separate allocation for each node and has better memory locality. Performance from base_perftests JSONPerfTest.StressTest: Old: 84,807ms Just replacing the storage: 70,363ms Optimizing JSON parser: 69,286ms Primarily the improvement is in read performance (in creating the dictionary nodes) but write performance is also improved slightly, presumably due to better memory locality. I did some manual checking for the creation of large dictionary values (where this change may perform poorly) and did not find any in normal Chrome runs other than the JSON parser and the value copy constructor. Bringing flat_map.h into values_unittests.cc seems to confuse MSVC's ADL resolution of swap and it gives errors about calling flat_map::swap with base::Values. I wasn't able to figure out the source of this problem. The test is really checking for operator= that is generated by the default std::swap implementation (base::Value doesn't specialize a swap so the "using std/swap" pattern for ADL is a Nno-op), so I qualified the call to swap with a std::. ========== to ========== Use base::flat_map for base::Value dictionary storage. This should give better memory locality and fewer allocations for our workloads. Most dictionaries are small and previously sorted (JSON Chrome writes like preferences is written in keyed-order). This makes the flat_map a better storage option because it avoids separate allocation for each node and has better memory locality. Performance from base_perftests JSONPerfTest.StressTest: Old: 84,807ms Just replacing the storage: 70,363ms Optimizing JSON parser: 69,286ms Primarily the improvement is in read performance (in creating the dictionary nodes) but write performance is also improved slightly, presumably due to better memory locality. I did some manual checking for the creation of large dictionary values (where this change may perform poorly) and did not find any in normal Chrome runs other than the JSON parser and the value copy constructor. Bringing flat_map.h into values_unittests.cc seems to confuse MSVC's ADL resolution of swap and it gives errors about calling flat_map::swap with base::Values. I wasn't able to figure out the source of this problem. The test is really checking for operator= that is generated by the default std::swap implementation (base::Value doesn't specialize a swap so the "using std/swap" pattern for ADL is a no-op), so I qualified the call to swap with a std::. ==========
New snap up. I added a paragraph at the end of the CL description about the problems I was having with swap.
Trying to make the map hold values instead of scoped_ptrs can be done independently of this change (we could have done it just as well before, too). That change will be even larger and more difficult to land than you ListValue one. I'm thinking to make the map unique_ptr->value change we should add a parallel API that takes values (moving into unique_ptr storage), change callers incrementally, delete the scoped_ptr functions, and then change the internal storage. I think one big patch will be prohibitively difficult to land.
The CQ bit was checked by brettw@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
On 2017/04/10 17:50:32, brettw (plz ping after 24h) wrote: > Trying to make the map hold values instead of scoped_ptrs can be done > independently of this change (we could have done it just as well before, too). > > That change will be even larger and more difficult to land than you ListValue > one. I'm thinking to make the map unique_ptr->value change we should add a > parallel API that takes values (moving into unique_ptr storage), change callers > incrementally, delete the scoped_ptr functions, and then change the internal > storage. I think one big patch will be prohibitively difficult to land. Thank you for the swap explanation and the new changes, this LGTM as is now. Regarding the unique_ptr -> value change: I completely agree with everything you said, having a parallel API makes a lot of sense. The presence of a parallel API for the various Set* methods makes Vaclav's raw pointer -> unique_ptr changes easier as well. There probably was a misunderstanding, though. I was not arguing in favor of changing DictStorage to base::flat_map<std::string, base::Value>, but simply for changing ManualConstructor<std::unique_ptr<DictStorage>> dict_ptr_; to ManualConstructor<DictStorage> dict_value_; We added the pointer to map to keep sizeof(Value) small (see the comment starting at base/values.h:198). However, this won't be necessary anymore given that sizeof(DictStorage) == sizeof(ListStorage) after this CL.
On 2017/04/10 18:08:44, jdoerrie wrote: > On 2017/04/10 17:50:32, brettw (plz ping after 24h) wrote: > > Trying to make the map hold values instead of scoped_ptrs can be done > > independently of this change (we could have done it just as well before, too). > > > > That change will be even larger and more difficult to land than you ListValue > > one. I'm thinking to make the map unique_ptr->value change we should add a > > parallel API that takes values (moving into unique_ptr storage), change > callers > > incrementally, delete the scoped_ptr functions, and then change the internal > > storage. I think one big patch will be prohibitively difficult to land. > > Thank you for the swap explanation and the new changes, this LGTM as is now. > > Regarding the unique_ptr -> value change: I completely agree with everything you > said, > having a parallel API makes a lot of sense. The presence of a parallel API for > the > various Set* methods makes Vaclav's raw pointer -> unique_ptr changes easier as > well. > > There probably was a misunderstanding, though. I was not arguing in favor of > changing > DictStorage to base::flat_map<std::string, base::Value>, but simply for changing > ManualConstructor<std::unique_ptr<DictStorage>> dict_ptr_; to > ManualConstructor<DictStorage> dict_value_; > > We added the pointer to map to keep sizeof(Value) small (see the comment > starting at > base/values.h:198). However, this won't be necessary anymore given that > sizeof(DictStorage) == sizeof(ListStorage) after this CL. Ohhhh, I see. Good idea, I'll do that in a followup since the bots are already happy with this patch.
The CQ bit was unchecked by brettw@chromium.org
The CQ bit was checked by brettw@chromium.org
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
CQ is committing da patch.
Bot data: {"patchset_id": 40001, "attempt_start_ts": 1491852492422390,
"parent_rev": "4541bd67f41fcadf05cfeb4a9f10abcd04110174", "commit_rev":
"8dd10d4011015ae6ce376a94666d56696e1ea7cd"}
Message was sent while issue was closed.
Description was changed from ========== Use base::flat_map for base::Value dictionary storage. This should give better memory locality and fewer allocations for our workloads. Most dictionaries are small and previously sorted (JSON Chrome writes like preferences is written in keyed-order). This makes the flat_map a better storage option because it avoids separate allocation for each node and has better memory locality. Performance from base_perftests JSONPerfTest.StressTest: Old: 84,807ms Just replacing the storage: 70,363ms Optimizing JSON parser: 69,286ms Primarily the improvement is in read performance (in creating the dictionary nodes) but write performance is also improved slightly, presumably due to better memory locality. I did some manual checking for the creation of large dictionary values (where this change may perform poorly) and did not find any in normal Chrome runs other than the JSON parser and the value copy constructor. Bringing flat_map.h into values_unittests.cc seems to confuse MSVC's ADL resolution of swap and it gives errors about calling flat_map::swap with base::Values. I wasn't able to figure out the source of this problem. The test is really checking for operator= that is generated by the default std::swap implementation (base::Value doesn't specialize a swap so the "using std/swap" pattern for ADL is a no-op), so I qualified the call to swap with a std::. ========== to ========== Use base::flat_map for base::Value dictionary storage. This should give better memory locality and fewer allocations for our workloads. Most dictionaries are small and previously sorted (JSON Chrome writes like preferences is written in keyed-order). This makes the flat_map a better storage option because it avoids separate allocation for each node and has better memory locality. Performance from base_perftests JSONPerfTest.StressTest: Old: 84,807ms Just replacing the storage: 70,363ms Optimizing JSON parser: 69,286ms Primarily the improvement is in read performance (in creating the dictionary nodes) but write performance is also improved slightly, presumably due to better memory locality. I did some manual checking for the creation of large dictionary values (where this change may perform poorly) and did not find any in normal Chrome runs other than the JSON parser and the value copy constructor. Bringing flat_map.h into values_unittests.cc seems to confuse MSVC's ADL resolution of swap and it gives errors about calling flat_map::swap with base::Values. I wasn't able to figure out the source of this problem. The test is really checking for operator= that is generated by the default std::swap implementation (base::Value doesn't specialize a swap so the "using std/swap" pattern for ADL is a no-op), so I qualified the call to swap with a std::. Review-Url: https://codereview.chromium.org/2807953002 Cr-Commit-Position: refs/heads/master@{#463371} Committed: https://chromium.googlesource.com/chromium/src/+/8dd10d4011015ae6ce376a94666d... ==========
Message was sent while issue was closed.
Committed patchset #3 (id:40001) as https://chromium.googlesource.com/chromium/src/+/8dd10d4011015ae6ce376a94666d...
Message was sent while issue was closed.
A revert of this CL (patchset #3 id:40001) has been created in https://codereview.chromium.org/2811043002/ by mkwst@chromium.org. The reason for reverting is: chromeos_unittests started failing in https://uberchromegw.corp.google.com/i/chromium.chromiumos/builders/Linux%20C...; FindIt points to this patch (with relatively low confidence), and the stack trace at least looks plausible (https://luci-logdog.appspot.com/v/?s=chromium%2Fbb%2Fchromium.chromiumos%2FLi....
Message was sent while issue was closed.
On 2017/04/11 at 06:47:23, Mike West wrote: > A revert of this CL (patchset #3 id:40001) has been created in https://codereview.chromium.org/2811043002/ by mkwst@chromium.org. > > The reason for reverting is: chromeos_unittests started failing in https://uberchromegw.corp.google.com/i/chromium.chromiumos/builders/Linux%20C...; FindIt points to this patch (with relatively low confidence), and the stack trace at least looks plausible (https://luci-logdog.appspot.com/v/?s=chromium%2Fbb%2Fchromium.chromiumos%2FLi.... Nevermind. https://bugs.chromium.org/p/chromium/issues/detail?id=710241 concludes that the tests were the problem, not this patch. I'll revert the revert, and disable the tests.. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
