• heimbuef's avatar
    New zone-backed list datastructure to replace ZoneList · 610c0d75
    heimbuef authored
    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
    
    Review-Url: https://codereview.chromium.org/2449383002
    Cr-Commit-Position: refs/heads/master@{#40602}
    610c0d75
Name
Last commit
Last update
..
base Loading commit data...
compiler Loading commit data...
compiler-dispatcher Loading commit data...
heap Loading commit data...
interpreter Loading commit data...
libplatform Loading commit data...
wasm Loading commit data...
zone Loading commit data...
BUILD.gn Loading commit data...
DEPS Loading commit data...
cancelable-tasks-unittest.cc Loading commit data...
char-predicates-unittest.cc Loading commit data...
counters-unittest.cc Loading commit data...
eh-frame-iterator-unittest.cc Loading commit data...
eh-frame-writer-unittest.cc Loading commit data...
locked-queue-unittest.cc Loading commit data...
register-configuration-unittest.cc Loading commit data...
run-all-unittests.cc Loading commit data...
source-position-table-unittest.cc Loading commit data...
test-utils.cc Loading commit data...
test-utils.h Loading commit data...
unittests.gyp Loading commit data...
unittests.isolate Loading commit data...
unittests.status Loading commit data...
value-serializer-unittest.cc Loading commit data...