• 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...
build_overrides Loading commit data...
docs Loading commit data...
gni Loading commit data...
gypfiles Loading commit data...
include Loading commit data...
infra Loading commit data...
samples Loading commit data...
src Loading commit data...
test Loading commit data...
testing Loading commit data...
third_party/binutils Loading commit data...
tools Loading commit data...
.clang-format Loading commit data...
.gitignore Loading commit data...
.gn Loading commit data...
.ycm_extra_conf.py Loading commit data...
AUTHORS Loading commit data...
BUILD.gn Loading commit data...
CODE_OF_CONDUCT.md Loading commit data...
ChangeLog Loading commit data...
DEPS Loading commit data...
LICENSE Loading commit data...
LICENSE.fdlibm Loading commit data...
LICENSE.strongtalk Loading commit data...
LICENSE.v8 Loading commit data...
LICENSE.valgrind Loading commit data...
Makefile Loading commit data...
Makefile.android Loading commit data...
OWNERS Loading commit data...
PRESUBMIT.py Loading commit data...
README.md Loading commit data...
WATCHLISTS Loading commit data...
codereview.settings Loading commit data...
snapshot_toolchain.gni Loading commit data...