• 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
BUILD.gn 84.2 KB