• 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
build_overrides Loading commit data...
custom_deps Loading commit data...
docs Loading commit data...
gni 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 Loading commit data...
tools Loading commit data...
.clang-format Loading commit data...
.clang-tidy Loading commit data...
.editorconfig Loading commit data...
.flake8 Loading commit data...
.git-blame-ignore-revs Loading commit data...
.gitattributes Loading commit data...
.gitignore Loading commit data...
.gn Loading commit data...
.vpython 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...
COMMON_OWNERS Loading commit data...
DEPS Loading commit data...
ENG_REVIEW_OWNERS Loading commit data...
INFRA_OWNERS Loading commit data...
INTL_OWNERS 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...
MIPS_OWNERS Loading commit data...
OWNERS Loading commit data...
PPC_OWNERS Loading commit data...
PRESUBMIT.py Loading commit data...
README.md Loading commit data...
S390_OWNERS Loading commit data...
WATCHLISTS Loading commit data...
codereview.settings Loading commit data...