• 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
..
benchmarks Loading commit data...
cctest Loading commit data...
common Loading commit data...
debugger Loading commit data...
fuzzer Loading commit data...
inspector Loading commit data...
intl Loading commit data...
js-perf-test Loading commit data...
memory Loading commit data...
message Loading commit data...
mjsunit Loading commit data...
mozilla Loading commit data...
preparser Loading commit data...
promises-aplus Loading commit data...
simdjs Loading commit data...
test262 Loading commit data...
unittests Loading commit data...
webkit Loading commit data...
BUILD.gn Loading commit data...
bot_default.gyp Loading commit data...
bot_default.isolate Loading commit data...
default.gyp Loading commit data...
default.isolate Loading commit data...
optimize_for_size.gyp Loading commit data...
optimize_for_size.isolate Loading commit data...
perf.gyp Loading commit data...
perf.isolate Loading commit data...