|
|
DescriptionAdd heuristic to order non bit fields in ComputedStyleBase.
Currently, when we generate non bit fields, we order them in
alphabetical order. This may result in unnecessary padding, e.g.
struct {
char a;
/* char padding[3] */
int b;
char c;
/* char padding[3] */
};
See [1] for an explanation.
This patch defines an ordering on field types so that we can sort
non bit fields from largest alignment size to smallest. This heuristic
minimises the padding most of the time:
struct {
int b;
char a;
char c;
/* char padding[2] */
};
This is purely a memory optimisation, not speed. It does not take into
account data access patterns and cache locality. We use the data from
[2] to define the order of types.
With this heuristic, some of the generated code has changed, but it is
unlikely to have changed the size of any structs.
Diff of generated files:
https://gist.github.com/darrnshn/81d146c2696ef100d56309e5b4b529ff/revisions
[1] http://www.drdobbs.com/cpp/padding-and-rearranging-structure-member/240007649?pgno=2
[2] https://codereview.chromium.org/2841413002
BUG=628043
Review-Url: https://codereview.chromium.org/2844223002
Cr-Commit-Position: refs/heads/master@{#468293}
Committed: https://chromium.googlesource.com/chromium/src/+/e8abebbc560bc64554c06e0480c2c9e75b0d3d32
Patch Set 1 #Patch Set 2 : Rebase #
Total comments: 4
Patch Set 3 : Address comments #Patch Set 4 : Assert #Messages
Total messages: 36 (25 generated)
Description was changed from ========== Add heuristic to order non bit fields in ComputedStyleBase. Currently, when we generate non bit fields, we order them in alphabetical order. This may result in unnecessary padding, e.g. struct { char a; /* char padding[3] */ int b; char c; /* char padding[3] */ }; See [1] for an explanation. This patch defines an ordering on primitive types so that we can sort non bit fields from largest alignment size to smallest. This heuristic minimises the padding most of the time: struct { char a; char c; /* char padding[2] */ int b; }; This is purely a memory optimisation, not speed. It does not take into account data access patterns and cache locality. [1] http://www.drdobbs.com/cpp/padding-and-rearranging-structure-member/240007649... BUG=628043 ========== to ========== Add heuristic to order non bit fields in ComputedStyleBase. Currently, when we generate non bit fields, we order them in alphabetical order. This may result in unnecessary padding, e.g. struct { char a; /* char padding[3] */ int b; char c; /* char padding[3] */ }; See [1] for an explanation. This patch defines an ordering on primitive types so that we can sort non bit fields from largest alignment size to smallest. This heuristic minimises the padding most of the time: struct { char a; char c; /* char padding[2] */ int b; }; This is purely a memory optimisation, not speed. It does not take into account data access patterns and cache locality. We use the data from [2] to define the order of types. [1] http://www.drdobbs.com/cpp/padding-and-rearranging-structure-member/240007649... [2] https://codereview.chromium.org/2841413002 BUG=628043 ==========
Description was changed from ========== Add heuristic to order non bit fields in ComputedStyleBase. Currently, when we generate non bit fields, we order them in alphabetical order. This may result in unnecessary padding, e.g. struct { char a; /* char padding[3] */ int b; char c; /* char padding[3] */ }; See [1] for an explanation. This patch defines an ordering on primitive types so that we can sort non bit fields from largest alignment size to smallest. This heuristic minimises the padding most of the time: struct { char a; char c; /* char padding[2] */ int b; }; This is purely a memory optimisation, not speed. It does not take into account data access patterns and cache locality. We use the data from [2] to define the order of types. [1] http://www.drdobbs.com/cpp/padding-and-rearranging-structure-member/240007649... [2] https://codereview.chromium.org/2841413002 BUG=628043 ========== to ========== Add heuristic to order non bit fields in ComputedStyleBase. Currently, when we generate non bit fields, we order them in alphabetical order. This may result in unnecessary padding, e.g. struct { char a; /* char padding[3] */ int b; char c; /* char padding[3] */ }; See [1] for an explanation. This patch defines an ordering on field types so that we can sort non bit fields from largest alignment size to smallest. This heuristic minimises the padding most of the time: struct { char a; char c; /* char padding[2] */ int b; }; This is purely a memory optimisation, not speed. It does not take into account data access patterns and cache locality. We use the data from [2] to define the order of types. [1] http://www.drdobbs.com/cpp/padding-and-rearranging-structure-member/240007649... [2] https://codereview.chromium.org/2841413002 BUG=628043 ==========
The CQ bit was checked by shend@chromium.org to run a CQ dry run
The CQ bit was unchecked by shend@chromium.org
Description was changed from ========== Add heuristic to order non bit fields in ComputedStyleBase. Currently, when we generate non bit fields, we order them in alphabetical order. This may result in unnecessary padding, e.g. struct { char a; /* char padding[3] */ int b; char c; /* char padding[3] */ }; See [1] for an explanation. This patch defines an ordering on field types so that we can sort non bit fields from largest alignment size to smallest. This heuristic minimises the padding most of the time: struct { char a; char c; /* char padding[2] */ int b; }; This is purely a memory optimisation, not speed. It does not take into account data access patterns and cache locality. We use the data from [2] to define the order of types. [1] http://www.drdobbs.com/cpp/padding-and-rearranging-structure-member/240007649... [2] https://codereview.chromium.org/2841413002 BUG=628043 ========== to ========== Add heuristic to order non bit fields in ComputedStyleBase. Currently, when we generate non bit fields, we order them in alphabetical order. This may result in unnecessary padding, e.g. struct { char a; /* char padding[3] */ int b; char c; /* char padding[3] */ }; See [1] for an explanation. This patch defines an ordering on field types so that we can sort non bit fields from largest alignment size to smallest. This heuristic minimises the padding most of the time: struct { char a; char c; /* char padding[2] */ int b; }; This is purely a memory optimisation, not speed. It does not take into account data access patterns and cache locality. We use the data from [2] to define the order of types. Diff of generated files: https://gist.github.com/darrnshn/81d146c2696ef100d56309e5b4b529ff/revisions [1] http://www.drdobbs.com/cpp/padding-and-rearranging-structure-member/240007649... [2] https://codereview.chromium.org/2841413002 BUG=628043 ==========
shend@chromium.org changed reviewers: + bugsnash@chromium.org
Hi Bugs, PTAL :)
The CQ bit was checked by shend@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...
Description was changed from ========== Add heuristic to order non bit fields in ComputedStyleBase. Currently, when we generate non bit fields, we order them in alphabetical order. This may result in unnecessary padding, e.g. struct { char a; /* char padding[3] */ int b; char c; /* char padding[3] */ }; See [1] for an explanation. This patch defines an ordering on field types so that we can sort non bit fields from largest alignment size to smallest. This heuristic minimises the padding most of the time: struct { char a; char c; /* char padding[2] */ int b; }; This is purely a memory optimisation, not speed. It does not take into account data access patterns and cache locality. We use the data from [2] to define the order of types. Diff of generated files: https://gist.github.com/darrnshn/81d146c2696ef100d56309e5b4b529ff/revisions [1] http://www.drdobbs.com/cpp/padding-and-rearranging-structure-member/240007649... [2] https://codereview.chromium.org/2841413002 BUG=628043 ========== to ========== Add heuristic to order non bit fields in ComputedStyleBase. Currently, when we generate non bit fields, we order them in alphabetical order. This may result in unnecessary padding, e.g. struct { char a; /* char padding[3] */ int b; char c; /* char padding[3] */ }; See [1] for an explanation. This patch defines an ordering on field types so that we can sort non bit fields from largest alignment size to smallest. This heuristic minimises the padding most of the time: struct { char a; char c; /* char padding[2] */ int b; }; This is purely a memory optimisation, not speed. It does not take into account data access patterns and cache locality. We use the data from [2] to define the order of types. With this heuristic, some of the generated code has changed, but it is unlikely to have changed the size of any structs. Diff of generated files: https://gist.github.com/darrnshn/81d146c2696ef100d56309e5b4b529ff/revisions [1] http://www.drdobbs.com/cpp/padding-and-rearranging-structure-member/240007649... [2] https://codereview.chromium.org/2841413002 BUG=628043 ==========
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
lgtm https://codereview.chromium.org/2844223002/diff/20001/third_party/WebKit/Sour... File third_party/WebKit/Source/build/scripts/make_computed_style_base.py (right): https://codereview.chromium.org/2844223002/diff/20001/third_party/WebKit/Sour... third_party/WebKit/Source/build/scripts/make_computed_style_base.py:20: # We want to sort fields by their alignment sizes. Specifying the exact alignment requirements Add to the comment where the types hard coded here have come from. Also perhaps reword to "Heuristic ordering of types from largest to smallest, used to sort fields by their alignment sizes. Specifying the exact blah blah". https://codereview.chromium.org/2844223002/diff/20001/third_party/WebKit/Sour... third_party/WebKit/Source/build/scripts/make_computed_style_base.py:321: known_alignment = [field for field in non_bit_fields if field.type_name in ALIGNMENT_ORDER] nit: swap these lines so that unknown_alignment comes first (as it does in the return statement)
Description was changed from ========== Add heuristic to order non bit fields in ComputedStyleBase. Currently, when we generate non bit fields, we order them in alphabetical order. This may result in unnecessary padding, e.g. struct { char a; /* char padding[3] */ int b; char c; /* char padding[3] */ }; See [1] for an explanation. This patch defines an ordering on field types so that we can sort non bit fields from largest alignment size to smallest. This heuristic minimises the padding most of the time: struct { char a; char c; /* char padding[2] */ int b; }; This is purely a memory optimisation, not speed. It does not take into account data access patterns and cache locality. We use the data from [2] to define the order of types. With this heuristic, some of the generated code has changed, but it is unlikely to have changed the size of any structs. Diff of generated files: https://gist.github.com/darrnshn/81d146c2696ef100d56309e5b4b529ff/revisions [1] http://www.drdobbs.com/cpp/padding-and-rearranging-structure-member/240007649... [2] https://codereview.chromium.org/2841413002 BUG=628043 ========== to ========== Add heuristic to order non bit fields in ComputedStyleBase. Currently, when we generate non bit fields, we order them in alphabetical order. This may result in unnecessary padding, e.g. struct { char a; /* char padding[3] */ int b; char c; /* char padding[3] */ }; See [1] for an explanation. This patch defines an ordering on field types so that we can sort non bit fields from largest alignment size to smallest. This heuristic minimises the padding most of the time: struct { int b; char a; char c; /* char padding[2] */ }; This is purely a memory optimisation, not speed. It does not take into account data access patterns and cache locality. We use the data from [2] to define the order of types. With this heuristic, some of the generated code has changed, but it is unlikely to have changed the size of any structs. Diff of generated files: https://gist.github.com/darrnshn/81d146c2696ef100d56309e5b4b529ff/revisions [1] http://www.drdobbs.com/cpp/padding-and-rearranging-structure-member/240007649... [2] https://codereview.chromium.org/2841413002 BUG=628043 ==========
shend@chromium.org changed reviewers: + meade@chromium.org
Thanks Bugs. Hi Eddy, can you PTAL? https://codereview.chromium.org/2844223002/diff/20001/third_party/WebKit/Sour... File third_party/WebKit/Source/build/scripts/make_computed_style_base.py (right): https://codereview.chromium.org/2844223002/diff/20001/third_party/WebKit/Sour... third_party/WebKit/Source/build/scripts/make_computed_style_base.py:20: # We want to sort fields by their alignment sizes. Specifying the exact alignment requirements On 2017/04/28 at 00:16:51, Bugs Nash wrote: > Add to the comment where the types hard coded here have come from. > > Also perhaps reword to "Heuristic ordering of types from largest to smallest, used to sort fields by their alignment sizes. Specifying the exact blah blah". done https://codereview.chromium.org/2844223002/diff/20001/third_party/WebKit/Sour... third_party/WebKit/Source/build/scripts/make_computed_style_base.py:321: known_alignment = [field for field in non_bit_fields if field.type_name in ALIGNMENT_ORDER] On 2017/04/28 at 00:16:51, Bugs Nash wrote: > nit: swap these lines so that unknown_alignment comes first (as it does in the return statement) done
The CQ bit was checked by shend@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.
lgtm Hey, cool! I have a question though, how will we make sure this list is properly updated when we add fields that use other types?
On 2017/04/28 at 07:51:20, meade wrote: > lgtm > > Hey, cool! I have a question though, how will we make sure this list is properly updated when we add fields that use other types? Good question :) There are two situations where we would want to update this list: 1) A new type is added. We can assert that there are no unknown types (as opposed to right now, where we just put them in front). 2) An existing type changes and its alignment changes. This is harder to detect. Perhaps we could put a bunch of static_asserts like https://codereview.chromium.org/2841413002, so any changes to alignment is at least explicit. WDYT?
On 2017/04/30 at 22:22:20, shend wrote: > On 2017/04/28 at 07:51:20, meade wrote: > > lgtm > > > > Hey, cool! I have a question though, how will we make sure this list is properly updated when we add fields that use other types? > > Good question :) There are two situations where we would want to update this list: > 1) A new type is added. We can assert that there are no unknown types (as opposed to right now, where we just put them in front). > 2) An existing type changes and its alignment changes. This is harder to detect. Perhaps we could put a bunch of static_asserts like > https://codereview.chromium.org/2841413002, so any changes to alignment is at least explicit. > > WDYT? assert seems like the best option to me, with an error message that tells the dev to add the type to the list, and a comment on the struct saying that new types need to be added to it. Also have you looked into dynamically finding the size of the objects? This library might be of interest http://starship.python.net/crew/theller/ctypes/tutorial.html If you can get the size of the types at runtime you might be able to import the types at runtime too, making adding new types simpler
On 2017/04/30 at 22:56:29, bugsnash wrote: > On 2017/04/30 at 22:22:20, shend wrote: > > On 2017/04/28 at 07:51:20, meade wrote: > > > lgtm > > > > > > Hey, cool! I have a question though, how will we make sure this list is properly updated when we add fields that use other types? > > > > Good question :) There are two situations where we would want to update this list: > > 1) A new type is added. We can assert that there are no unknown types (as opposed to right now, where we just put them in front). > > 2) An existing type changes and its alignment changes. This is harder to detect. Perhaps we could put a bunch of static_asserts like > > https://codereview.chromium.org/2841413002, so any changes to alignment is at least explicit. > > > > WDYT? > > assert seems like the best option to me, with an error message that tells the dev to add the type to the list, and a comment on the struct saying that new types need to be added to it. > > Also have you looked into dynamically finding the size of the objects? This library might be of interest http://starship.python.net/crew/theller/ctypes/tutorial.html > > If you can get the size of the types at runtime you might be able to import the types at runtime too, making adding new types simpler Interesting idea. By runtime, you mean at runtime of the Python script right (i.e. compile-time of C++)? If I understand correctly, we'd have to compile blink first before getting sizes, but to compile blink we need to generate code first, so I don't know how to make this work.
On 2017/04/30 at 23:08:34, shend wrote: > On 2017/04/30 at 22:56:29, bugsnash wrote: > > On 2017/04/30 at 22:22:20, shend wrote: > > > On 2017/04/28 at 07:51:20, meade wrote: > > > > lgtm > > > > > > > > Hey, cool! I have a question though, how will we make sure this list is properly updated when we add fields that use other types? > > > > > > Good question :) There are two situations where we would want to update this list: > > > 1) A new type is added. We can assert that there are no unknown types (as opposed to right now, where we just put them in front). > > > 2) An existing type changes and its alignment changes. This is harder to detect. Perhaps we could put a bunch of static_asserts like > > > https://codereview.chromium.org/2841413002, so any changes to alignment is at least explicit. > > > > > > WDYT? > > > > assert seems like the best option to me, with an error message that tells the dev to add the type to the list, and a comment on the struct saying that new types need to be added to it. > > > > Also have you looked into dynamically finding the size of the objects? This library might be of interest http://starship.python.net/crew/theller/ctypes/tutorial.html > > > > If you can get the size of the types at runtime you might be able to import the types at runtime too, making adding new types simpler > > Interesting idea. By runtime, you mean at runtime of the Python script right (i.e. compile-time of C++)? If I understand correctly, we'd have to compile blink first before getting sizes, but to compile blink we need to generate code first, so I don't know how to make this work. does that library require c++ code to be compiled before it can get the sizes?
On 2017/04/30 at 23:27:39, Bugs Nash wrote: > On 2017/04/30 at 23:08:34, shend wrote: > > On 2017/04/30 at 22:56:29, bugsnash wrote: > > > On 2017/04/30 at 22:22:20, shend wrote: > > > > On 2017/04/28 at 07:51:20, meade wrote: > > > > > lgtm > > > > > > > > > > Hey, cool! I have a question though, how will we make sure this list is properly updated when we add fields that use other types? > > > > > > > > Good question :) There are two situations where we would want to update this list: > > > > 1) A new type is added. We can assert that there are no unknown types (as opposed to right now, where we just put them in front). > > > > 2) An existing type changes and its alignment changes. This is harder to detect. Perhaps we could put a bunch of static_asserts like > > > > https://codereview.chromium.org/2841413002, so any changes to alignment is at least explicit. > > > > > > > > WDYT? > > > > > > assert seems like the best option to me, with an error message that tells the dev to add the type to the list, and a comment on the struct saying that new types need to be added to it. > > > > > > Also have you looked into dynamically finding the size of the objects? This library might be of interest http://starship.python.net/crew/theller/ctypes/tutorial.html > > > > > > If you can get the size of the types at runtime you might be able to import the types at runtime too, making adding new types simpler > > > > Interesting idea. By runtime, you mean at runtime of the Python script right (i.e. compile-time of C++)? If I understand correctly, we'd have to compile blink first before getting sizes, but to compile blink we need to generate code first, so I don't know how to make this work. > > does that library require c++ code to be compiled before it can get the sizes? oh, yes I did mean python runtime :)
The CQ bit was checked by shend@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.
The CQ bit was checked by shend@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from bugsnash@chromium.org, meade@chromium.org Link to the patchset: https://codereview.chromium.org/2844223002/#ps60001 (title: "Assert")
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": 60001, "attempt_start_ts": 1493617621063530, "parent_rev": "73fe6ba4ceb2db91a43ee2305f69ffde08001f62", "commit_rev": "e8abebbc560bc64554c06e0480c2c9e75b0d3d32"}
Message was sent while issue was closed.
Description was changed from ========== Add heuristic to order non bit fields in ComputedStyleBase. Currently, when we generate non bit fields, we order them in alphabetical order. This may result in unnecessary padding, e.g. struct { char a; /* char padding[3] */ int b; char c; /* char padding[3] */ }; See [1] for an explanation. This patch defines an ordering on field types so that we can sort non bit fields from largest alignment size to smallest. This heuristic minimises the padding most of the time: struct { int b; char a; char c; /* char padding[2] */ }; This is purely a memory optimisation, not speed. It does not take into account data access patterns and cache locality. We use the data from [2] to define the order of types. With this heuristic, some of the generated code has changed, but it is unlikely to have changed the size of any structs. Diff of generated files: https://gist.github.com/darrnshn/81d146c2696ef100d56309e5b4b529ff/revisions [1] http://www.drdobbs.com/cpp/padding-and-rearranging-structure-member/240007649... [2] https://codereview.chromium.org/2841413002 BUG=628043 ========== to ========== Add heuristic to order non bit fields in ComputedStyleBase. Currently, when we generate non bit fields, we order them in alphabetical order. This may result in unnecessary padding, e.g. struct { char a; /* char padding[3] */ int b; char c; /* char padding[3] */ }; See [1] for an explanation. This patch defines an ordering on field types so that we can sort non bit fields from largest alignment size to smallest. This heuristic minimises the padding most of the time: struct { int b; char a; char c; /* char padding[2] */ }; This is purely a memory optimisation, not speed. It does not take into account data access patterns and cache locality. We use the data from [2] to define the order of types. With this heuristic, some of the generated code has changed, but it is unlikely to have changed the size of any structs. Diff of generated files: https://gist.github.com/darrnshn/81d146c2696ef100d56309e5b4b529ff/revisions [1] http://www.drdobbs.com/cpp/padding-and-rearranging-structure-member/240007649... [2] https://codereview.chromium.org/2841413002 BUG=628043 Review-Url: https://codereview.chromium.org/2844223002 Cr-Commit-Position: refs/heads/master@{#468293} Committed: https://chromium.googlesource.com/chromium/src/+/e8abebbc560bc64554c06e0480c2... ==========
Message was sent while issue was closed.
Committed patchset #4 (id:60001) as https://chromium.googlesource.com/chromium/src/+/e8abebbc560bc64554c06e0480c2... |