Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
2449383002:
New zone-backed list datastructure to replace ZoneList (Closed)
DescriptionNew zone-backed list datastructure to replace ZoneList
Since ZoneLists are essentially non-standard ZoneVectors and have a bad
growing behaviour (ZoneList-allocations make up ~50% of website parse
zone memory) we should stop using them. The zone-containers are merely
a clean-up, with none of them actually better suited to be used with
zones. This new datastructure allows most operations of a LinkedList (
except pop_first and insertAt/removeAt) but uses about the same memory
as a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably
large lists). It also never attempts to free memory again (which would
not work in zones anyway).
The ZoneChunkList is essentially a doubly-linked-list of arrays of
variable size.
Some test-results where I tried storing 16k pointers in different list
types (lists themselves also zone-allocated):
List type Zone memory used Time taken
-----------------------------------------------------------------------
Zone array (for comparison) 131072 B
Ideally initialized ZoneList 131088 B 0.062ms
ChunkZoneList 134744 B 0.052ms <--new thing
ZoneDeque 141744 B
ZoneLinkedList 393264 B
Initially empty ZoneList 524168 B 0.171ms <--right now
ChunkZoneList only push_front 524320 B
Committed: https://crrev.com/610c0d75c872c85af5d8fa88fd947e957956a505
Cr-Commit-Position: refs/heads/master@{#40602}
Patch Set 1 : Changed test to account for the list sizes as well #
Total comments: 23
Patch Set 2 : Reaction to comments #Patch Set 3 : Added time measurements #Patch Set 4 : appease trybots #Patch Set 5 : appease windows compiler #Patch Set 6 : Reaction to comments #
Total comments: 2
Patch Set 7 : Added some debug checks #
Messages
Total messages: 49 (41 generated)
Description was changed from ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory of a well-initialized ZoneVector/ZoneList (<2% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. ========== to ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory of a well-initialized ZoneVector/ZoneList (<2% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried saving 16k pointers in different list types: List type Bytes of Zone memory used -------------------------------------------------------------- Zone array 131072 B Ideally Initialized Zone list 131072 B Chunk zone list 134712 B ZoneDeque 141632 B Initially Empty Zone list 269992 B ZoneLinkedList 393216 B Chunk zone list push_front 524288 B ==========
Description was changed from ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory of a well-initialized ZoneVector/ZoneList (<2% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried saving 16k pointers in different list types: List type Bytes of Zone memory used -------------------------------------------------------------- Zone array 131072 B Ideally Initialized Zone list 131072 B Chunk zone list 134712 B ZoneDeque 141632 B Initially Empty Zone list 269992 B ZoneLinkedList 393216 B Chunk zone list push_front 524288 B ========== to ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory of a well-initialized ZoneVector/ZoneList (<2% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types: List type Bytes of Zone memory used -------------------------------------------------------------- Zone array 131072 B Ideally Initialized Zone list 131072 B Chunk zone list 134712 B ZoneDeque 141632 B Initially Empty Zone list 269992 B ZoneLinkedList 393216 B Chunk zone list push_front 524288 B ==========
Description was changed from ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory of a well-initialized ZoneVector/ZoneList (<2% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types: List type Bytes of Zone memory used -------------------------------------------------------------- Zone array 131072 B Ideally Initialized Zone list 131072 B Chunk zone list 134712 B ZoneDeque 141632 B Initially Empty Zone list 269992 B ZoneLinkedList 393216 B Chunk zone list push_front 524288 B ========== to ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory of a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types: List type Bytes of Zone memory used -------------------------------------------------------------- Zone array 131072 B Ideally Initialized Zone list 131072 B Chunk zone list 134712 B ZoneDeque 141632 B Initially Empty Zone list 269992 B ZoneLinkedList 393216 B Chunk zone list push_front 524288 B ==========
heimbuef@google.com changed reviewers: + jochen@chromium.org, verwaest@chromium.org
PTAL
Description was changed from ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory of a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types: List type Bytes of Zone memory used -------------------------------------------------------------- Zone array 131072 B Ideally Initialized Zone list 131072 B Chunk zone list 134712 B ZoneDeque 141632 B Initially Empty Zone list 269992 B ZoneLinkedList 393216 B Chunk zone list push_front 524288 B ========== to ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory of a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types: List type Bytes of Zone memory used ---------------------------------------------------------- Zone array 131072 B Ideally Initialized Zone list 131088 B Chunk zone list 134744 B ZoneDeque 141744 B ZoneLinkedList 393264 B Initially Empty Zone list 524168 B Chunk zone list push_front 524320 B ==========
Description was changed from ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory of a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types: List type Bytes of Zone memory used ---------------------------------------------------------- Zone array 131072 B Ideally Initialized Zone list 131088 B Chunk zone list 134744 B ZoneDeque 141744 B ZoneLinkedList 393264 B Initially Empty Zone list 524168 B Chunk zone list push_front 524320 B ========== to ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory of a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types (lists themselves also zone-allocated): List type Bytes of Zone memory used ---------------------------------------------------------- Zone array 131072 B Ideally Initialized Zone list 131088 B Chunk zone list 134744 B ZoneDeque 141744 B ZoneLinkedList 393264 B Initially Empty Zone list 524168 B Chunk zone list push_front 524320 B ==========
Patchset #1 (id:1) has been deleted
Description was changed from ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory of a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types (lists themselves also zone-allocated): List type Bytes of Zone memory used ---------------------------------------------------------- Zone array 131072 B Ideally Initialized Zone list 131088 B Chunk zone list 134744 B ZoneDeque 141744 B ZoneLinkedList 393264 B Initially Empty Zone list 524168 B Chunk zone list push_front 524320 B ========== to ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory of a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types (lists themselves also zone-allocated): List type Bytes of Zone memory used ---------------------------------------------------------- Zone array (for comparison) 131072 B Ideally Initialized Zone list 131088 B Chunk zone list 134744 B ZoneDeque 141744 B ZoneLinkedList 393264 B Initially Empty Zone list 524168 B Chunk zone list push_front 524320 B ==========
Description was changed from ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory of a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types (lists themselves also zone-allocated): List type Bytes of Zone memory used ---------------------------------------------------------- Zone array (for comparison) 131072 B Ideally Initialized Zone list 131088 B Chunk zone list 134744 B ZoneDeque 141744 B ZoneLinkedList 393264 B Initially Empty Zone list 524168 B Chunk zone list push_front 524320 B ========== to ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory of a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types (lists themselves also zone-allocated): List type Bytes of Zone memory used ---------------------------------------------------------- Zone array (for comparison) 131072 B Ideally Initialized ZoneList 131088 B ChunkZoneList 134744 B ZoneDeque 141744 B ZoneLinkedList 393264 B Initially empty ZoneList 524168 B ChunkZoneList with push_front 524320 B ==========
Description was changed from ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory of a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types (lists themselves also zone-allocated): List type Bytes of Zone memory used ---------------------------------------------------------- Zone array (for comparison) 131072 B Ideally Initialized ZoneList 131088 B ChunkZoneList 134744 B ZoneDeque 141744 B ZoneLinkedList 393264 B Initially empty ZoneList 524168 B ChunkZoneList with push_front 524320 B ========== to ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory of a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types (lists themselves also zone-allocated): List type Bytes of Zone memory used ---------------------------------------------------------- Zone array (for comparison) 131072 B Ideally Initialized ZoneList 131088 B ChunkZoneList 134744 B ZoneDeque 141744 B ZoneLinkedList 393264 B Initially empty ZoneList 524168 B ChunkZoneList only push_front 524320 B ==========
Description was changed from ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory of a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types (lists themselves also zone-allocated): List type Bytes of Zone memory used ---------------------------------------------------------- Zone array (for comparison) 131072 B Ideally Initialized ZoneList 131088 B ChunkZoneList 134744 B ZoneDeque 141744 B ZoneLinkedList 393264 B Initially empty ZoneList 524168 B ChunkZoneList only push_front 524320 B ========== to ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory of a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types (lists themselves also zone-allocated): List type Bytes of Zone memory used ---------------------------------------------------------- Zone array (for comparison) 131072 B Ideally Initialized ZoneList 131088 B ChunkZoneList 134744 B <-- new thing ZoneDeque 141744 B ZoneLinkedList 393264 B Initially empty ZoneList 524168 B <-- right now ChunkZoneList only push_front 524320 B ==========
what's the runtime performance of using this? Can you please run tryjobs? I'd expect that this doesn't compile on the debug bots... https://codereview.chromium.org/2449383002/diff/20001/src/zone/zone-chunk-list.h File src/zone/zone-chunk-list.h (right): https://codereview.chromium.org/2449383002/diff/20001/src/zone/zone-chunk-lis... src/zone/zone-chunk-list.h:40: enum StartMode { please use an enum class https://codereview.chromium.org/2449383002/diff/20001/src/zone/zone-chunk-lis... src/zone/zone-chunk-list.h:131: }; DISALLOW_COPY_AND_ASSIGN
On 2016/10/26 at 13:24:12, jochen wrote: > what's the runtime performance of using this? > > Can you please run tryjobs? I'd expect that this doesn't compile on the debug bots... > > https://codereview.chromium.org/2449383002/diff/20001/src/zone/zone-chunk-list.h > File src/zone/zone-chunk-list.h (right): > > https://codereview.chromium.org/2449383002/diff/20001/src/zone/zone-chunk-lis... > src/zone/zone-chunk-list.h:40: enum StartMode { > please use an enum class > > https://codereview.chromium.org/2449383002/diff/20001/src/zone/zone-chunk-lis... > src/zone/zone-chunk-list.h:131: }; > DISALLOW_COPY_AND_ASSIGN Done. I'll post performance measurements as soon as I have them. I would expect the Windows trybots to complain about all kinds of number-converting issues.
Description was changed from ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory of a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types (lists themselves also zone-allocated): List type Bytes of Zone memory used ---------------------------------------------------------- Zone array (for comparison) 131072 B Ideally Initialized ZoneList 131088 B ChunkZoneList 134744 B <-- new thing ZoneDeque 141744 B ZoneLinkedList 393264 B Initially empty ZoneList 524168 B <-- right now ChunkZoneList only push_front 524320 B ========== to ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory as a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types (lists themselves also zone-allocated): List type Bytes of Zone memory used ---------------------------------------------------------- Zone array (for comparison) 131072 B Ideally Initialized ZoneList 131088 B ChunkZoneList 134744 B <-- new thing ZoneDeque 141744 B ZoneLinkedList 393264 B Initially empty ZoneList 524168 B <-- right now ChunkZoneList only push_front 524320 B ==========
Description was changed from ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory as a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types (lists themselves also zone-allocated): List type Bytes of Zone memory used ---------------------------------------------------------- Zone array (for comparison) 131072 B Ideally Initialized ZoneList 131088 B ChunkZoneList 134744 B <-- new thing ZoneDeque 141744 B ZoneLinkedList 393264 B Initially empty ZoneList 524168 B <-- right now ChunkZoneList only push_front 524320 B ========== to ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory as a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types (lists themselves also zone-allocated): List type Bytes of Zone memory used Time taken ----------------------------------------------------------------------- Zone array (for comparison) 131072 B Ideally Initialized ZoneList 131088 B 0.062000 ms ChunkZoneList 134744 B <-- new thing 0.052000 ms ZoneDeque 141744 B ZoneLinkedList 393264 B Initially empty ZoneList 524168 B <-- right now 0.171000 ms ChunkZoneList only push_front 524320 B ==========
Description was changed from ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory as a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types (lists themselves also zone-allocated): List type Bytes of Zone memory used Time taken ----------------------------------------------------------------------- Zone array (for comparison) 131072 B Ideally Initialized ZoneList 131088 B 0.062000 ms ChunkZoneList 134744 B <-- new thing 0.052000 ms ZoneDeque 141744 B ZoneLinkedList 393264 B Initially empty ZoneList 524168 B <-- right now 0.171000 ms ChunkZoneList only push_front 524320 B ========== to ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory as a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types (lists themselves also zone-allocated): List type Zone memory used Time taken ----------------------------------------------------------------------- Zone array (for comparison) 131072 B Ideally Initialized ZoneList 131088 B 0.062000 ms ChunkZoneList 134744 B 0.052000 ms <--new thing ZoneDeque 141744 B ZoneLinkedList 393264 B Initially empty ZoneList 524168 B 0.171000 ms <--right now ChunkZoneList only push_front 524320 B ==========
heimbuef@google.com changed reviewers: + jakoberow@chromium.org
Description was changed from ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory as a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types (lists themselves also zone-allocated): List type Zone memory used Time taken ----------------------------------------------------------------------- Zone array (for comparison) 131072 B Ideally Initialized ZoneList 131088 B 0.062000 ms ChunkZoneList 134744 B 0.052000 ms <--new thing ZoneDeque 141744 B ZoneLinkedList 393264 B Initially empty ZoneList 524168 B 0.171000 ms <--right now ChunkZoneList only push_front 524320 B ========== to ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory as a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types (lists themselves also zone-allocated): List type Zone memory used Time taken ----------------------------------------------------------------------- Zone array (for comparison) 131072 B Ideally Initialized ZoneList 131088 B 0.062ms ChunkZoneList 134744 B 0.052ms <--new thing ZoneDeque 141744 B ZoneLinkedList 393264 B Initially empty ZoneList 524168 B 0.171ms <--right now ChunkZoneList only push_front 524320 B ==========
The CQ bit was checked by heimbuef@google.com 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: v8_win64_rel_ng on master.tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_win64_rel_ng/builds/16786) v8_win_compile_dbg on master.tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_win_compile_dbg/builds/2...)
The CQ bit was checked by heimbuef@google.com 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...
jkummerow@chromium.org changed reviewers: + jkummerow@chromium.org - jakoberow@chromium.org
I like this! But I have a bunch of comments. https://codereview.chromium.org/2449383002/diff/20001/src/zone/zone-chunk-list.h File src/zone/zone-chunk-list.h (right): https://codereview.chromium.org/2449383002/diff/20001/src/zone/zone-chunk-lis... src/zone/zone-chunk-list.h:25: // * needs to grow indefinitly, nit: "indefinitely" https://codereview.chromium.org/2449383002/diff/20001/src/zone/zone-chunk-lis... src/zone/zone-chunk-list.h:72: // Todo(heimbuef): Add 'push_front_many'. nit: s/Todo/TODO/ https://codereview.chromium.org/2449383002/diff/20001/src/zone/zone-chunk-lis... src/zone/zone-chunk-list.h:78: // Quickly seeks the list to retrieve the element at the given index. Will nit: s/seeks/searches/ (or "scans" or "walks"). https://codereview.chromium.org/2449383002/diff/20001/src/zone/zone-chunk-lis... src/zone/zone-chunk-list.h:82: // Todo(heimbuef): Add 'rFind', seeking from the end and returning a nit: s/Todo/TODO/ https://codereview.chromium.org/2449383002/diff/20001/src/zone/zone-chunk-lis... src/zone/zone-chunk-list.h:212: if (list->back_->position_ >= list->back_->capacity_) { I don't understand why this condition is necessary. AFAICS, the ">" case can never happen (->DCHECK?), and "==" should be handled by the case below (line 216). Am I missing something? https://codereview.chromium.org/2449383002/diff/20001/src/zone/zone-chunk-lis... src/zone/zone-chunk-list.h:281: DCHECK_LE(0, size()); This check is useless, every size_t is >= 0. Did you mean "DCHECK_LT"? https://codereview.chromium.org/2449383002/diff/20001/src/zone/zone-chunk-lis... src/zone/zone-chunk-list.h:287: DCHECK_LE(0, size()); This check is useless, every size_t is >= 0. Did you mean "DCHECK_LT"? https://codereview.chromium.org/2449383002/diff/20001/src/zone/zone-chunk-lis... src/zone/zone-chunk-list.h:288: return back_->items()[back_->position_ - 1]; This is missing a check for back_->position_ == 0. https://codereview.chromium.org/2449383002/diff/20001/src/zone/zone-chunk-lis... src/zone/zone-chunk-list.h:298: if (back_->position_ >= back_->capacity_) { nit: ">" can't happen (or can it?); just check if "==". https://codereview.chromium.org/2449383002/diff/20001/src/zone/zone-chunk-lis... src/zone/zone-chunk-list.h:313: DCHECK_LE(0, size()); This check is useless, every size_t is >= 0. Did you mean "DCHECK_LT"? https://codereview.chromium.org/2449383002/diff/20001/src/zone/zone-chunk-lis... src/zone/zone-chunk-list.h:325: front_->previous_ = chunk; nit: {} please, and for the else-branch too https://codereview.chromium.org/2449383002/diff/20001/src/zone/zone-chunk-lis... src/zone/zone-chunk-list.h:338: DCHECK_LE(0, size()); This check is useless, every size_t is >= 0. Did you mean DCHECK_LE(index, size())? https://codereview.chromium.org/2449383002/diff/20001/src/zone/zone-chunk-lis... src/zone/zone-chunk-list.h:344: SeekResult result; simpler: SeekResult result = { current, static_cast<uint32_t>(index) }; https://codereview.chromium.org/2449383002/diff/20001/src/zone/zone-chunk-lis... src/zone/zone-chunk-list.h:356: if (seek_result.chunk_ == nullptr) return; Can this happen? https://codereview.chromium.org/2449383002/diff/20001/src/zone/zone-chunk-lis... src/zone/zone-chunk-list.h:361: // Set back_ so iterators will work correctly nit: trailing full stop. https://codereview.chromium.org/2449383002/diff/20001/test/unittests/unittest... File test/unittests/unittests.gyp (right): https://codereview.chromium.org/2449383002/diff/20001/test/unittests/unittest... test/unittests/unittests.gyp:120: 'zone/zone-chunk-list-unittest.cc', nit: maintain alpha-sorting https://codereview.chromium.org/2449383002/diff/20001/test/unittests/zone/zon... File test/unittests/zone/zone-chunk-list-unittest.cc (right): https://codereview.chromium.org/2449383002/diff/20001/test/unittests/zone/zon... test/unittests/zone/zone-chunk-list-unittest.cc:5: #include "src/zone/zone-chunk-list.h" nit: one empty line after this https://codereview.chromium.org/2449383002/diff/20001/test/unittests/zone/zon... test/unittests/zone/zone-chunk-list-unittest.cc:7: #include "src/list.h" nit: if you #include foo-inl.h, you don't need foo.h https://codereview.chromium.org/2449383002/diff/20001/test/unittests/zone/zon... test/unittests/zone/zone-chunk-list-unittest.cc:16: const size_t kItemCount = size_t(1) << 14; suggestion: 1 << 10 is enough; once you reach maximum chunk size, nothing interesting will happen that hasn't happened before. https://codereview.chromium.org/2449383002/diff/20001/test/unittests/zone/zon... test/unittests/zone/zone-chunk-list-unittest.cc:114: TEST(Zone, ListSizeComparisons) { While this test is useful to validate the design, I don't think it provides value in the long term, and should be deleted before committing this CL. https://codereview.chromium.org/2449383002/diff/20001/test/unittests/zone/zon... test/unittests/zone/zone-chunk-list-unittest.cc:144: count++; suggestion: add "EXPECT_EQ(count, static_cast<size_t>(item));" as the first thing in this loop, drop ChunkListDataTest below, and save some test time :-)
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: v8_win_compile_dbg on master.tryserver.v8 (JOB_FAILED, http://build.chromium.org/p/tryserver.v8/builders/v8_win_compile_dbg/builds/2...)
The CQ bit was checked by heimbuef@google.com 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 with two more comments. https://codereview.chromium.org/2449383002/diff/120001/src/zone/zone-chunk-li... File src/zone/zone-chunk-list.h (right): https://codereview.chromium.org/2449383002/diff/120001/src/zone/zone-chunk-li... src/zone/zone-chunk-list.h:348: DCHECK_LT(size_t(0), size()); Did you mean DCHECK_LT(index, size())? https://codereview.chromium.org/2449383002/diff/120001/test/unittests/zone/zo... File test/unittests/zone/zone-chunk-list-unittest.cc (right): https://codereview.chromium.org/2449383002/diff/120001/test/unittests/zone/zo... test/unittests/zone/zone-chunk-list-unittest.cc:5: #include <ctime> what's this needed for?
Patchset #7 (id:140001) has been deleted
The CQ bit was checked by heimbuef@google.com 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...
Patchset #7 (id:160001) has been deleted
The CQ bit was checked by heimbuef@google.com 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 ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory as a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types (lists themselves also zone-allocated): List type Zone memory used Time taken ----------------------------------------------------------------------- Zone array (for comparison) 131072 B Ideally Initialized ZoneList 131088 B 0.062ms ChunkZoneList 134744 B 0.052ms <--new thing ZoneDeque 141744 B ZoneLinkedList 393264 B Initially empty ZoneList 524168 B 0.171ms <--right now ChunkZoneList only push_front 524320 B ========== to ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory as a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types (lists themselves also zone-allocated): List type Zone memory used Time taken ----------------------------------------------------------------------- Zone array (for comparison) 131072 B Ideally initialized ZoneList 131088 B 0.062ms ChunkZoneList 134744 B 0.052ms <--new thing ZoneDeque 141744 B ZoneLinkedList 393264 B Initially empty ZoneList 524168 B 0.171ms <--right now ChunkZoneList only push_front 524320 B ==========
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 heimbuef@google.com
The patchset sent to the CQ was uploaded after l-g-t-m from jkummerow@chromium.org Link to the patchset: https://codereview.chromium.org/2449383002/#ps180001 (title: "Added some debug checks")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
Message was sent while issue was closed.
Committed patchset #7 (id:180001)
Message was sent while issue was closed.
Description was changed from ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory as a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types (lists themselves also zone-allocated): List type Zone memory used Time taken ----------------------------------------------------------------------- Zone array (for comparison) 131072 B Ideally initialized ZoneList 131088 B 0.062ms ChunkZoneList 134744 B 0.052ms <--new thing ZoneDeque 141744 B ZoneLinkedList 393264 B Initially empty ZoneList 524168 B 0.171ms <--right now ChunkZoneList only push_front 524320 B ========== to ========== New zone-backed list datastructure to replace ZoneList Since ZoneLists are essentially non-standard ZoneVectors and have a bad growing behaviour (ZoneList-allocations make up ~50% of website parse zone memory) we should stop using them. The zone-containers are merely a clean-up, with none of them actually better suited to be used with zones. This new datastructure allows most operations of a LinkedList ( except pop_first and insertAt/removeAt) but uses about the same memory as a well-initialized ZoneVector/ZoneList (<3% overhead with reasonably large lists). It also never attempts to free memory again (which would not work in zones anyway). The ZoneChunkList is essentially a doubly-linked-list of arrays of variable size. Some test-results where I tried storing 16k pointers in different list types (lists themselves also zone-allocated): List type Zone memory used Time taken ----------------------------------------------------------------------- Zone array (for comparison) 131072 B Ideally initialized ZoneList 131088 B 0.062ms ChunkZoneList 134744 B 0.052ms <--new thing ZoneDeque 141744 B ZoneLinkedList 393264 B Initially empty ZoneList 524168 B 0.171ms <--right now ChunkZoneList only push_front 524320 B Committed: https://crrev.com/610c0d75c872c85af5d8fa88fd947e957956a505 Cr-Commit-Position: refs/heads/master@{#40602} ==========
Message was sent while issue was closed.
Patchset 7 (id:??) landed as https://crrev.com/610c0d75c872c85af5d8fa88fd947e957956a505 Cr-Commit-Position: refs/heads/master@{#40602} |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
