• Clemens Backes's avatar
    [wasm] Fix performance bottleneck in DisjointAllocationPool · 7e0279fa
    Clemens Backes authored
    When compiling modules with many functions, the list of regions in the
    {DisjointAllocationPool} can become quite large if the functions die in
    a random order (which they typically do, since the order of Liftoff
    compilation is different than the order to TurboFan compilation; which
    work stealing, both are nondeterministic).
    Iterating the list of regions in the {DisjointAllocationPool} was thus
    linear in the number of regions, which is linear in the number of
    functions of the module. Since we insert new regions one by one, overall
    runtime was quadratic.
    
    This CL fixes this by switching from a linked list to a std::set.
    Merging a new region is thus logarithmic instead of linear, and overall
    we are {n*log(n)} instead of {n^2}.
    
    Note: For {AllocateInRegion} we still need to linearly iterate all
    regions that overlap the requested region, but this has not shown to be
    a problem so far.
    
    R=ahaas@chromium.org
    
    Bug: v8:10432
    Change-Id: I193e56c2abab782e386194fbe64dadfa250916f7
    Reviewed-on: https://chromium-review.googlesource.com/c/v8/v8/+/2154797
    Commit-Queue: Clemens Backes <clemensb@chromium.org>
    Reviewed-by: 's avatarAndreas Haas <ahaas@chromium.org>
    Cr-Commit-Position: refs/heads/master@{#67303}
    7e0279fa
Name
Last commit
Last update
..
api Loading commit data...
asmjs Loading commit data...
assembler Loading commit data...
base Loading commit data...
codegen Loading commit data...
compiler Loading commit data...
compiler-dispatcher Loading commit data...
date Loading commit data...
diagnostics Loading commit data...
execution Loading commit data...
heap Loading commit data...
interpreter Loading commit data...
libplatform Loading commit data...
logging Loading commit data...
numbers Loading commit data...
objects Loading commit data...
parser Loading commit data...
profiler Loading commit data...
regress Loading commit data...
strings Loading commit data...
tasks Loading commit data...
torque Loading commit data...
utils Loading commit data...
wasm Loading commit data...
zone Loading commit data...
BUILD.gn Loading commit data...
DEPS Loading commit data...
run-all-unittests.cc Loading commit data...
test-helpers.cc Loading commit data...
test-helpers.h Loading commit data...
test-utils.cc Loading commit data...
test-utils.h Loading commit data...
testcfg.py Loading commit data...
unittests.status Loading commit data...