• 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
..
debug Loading commit data...
platform Loading commit data...
utils Loading commit data...
DEPS Loading commit data...
OWNERS Loading commit data...
address-region.h Loading commit data...
atomic-utils.h Loading commit data...
atomicops.h Loading commit data...
atomicops_internals_atomicword_compat.h Loading commit data...
atomicops_internals_portable.h Loading commit data...
atomicops_internals_std.h Loading commit data...
base-export.h Loading commit data...
bit-field.h Loading commit data...
bits-iterator.h Loading commit data...
bits.cc Loading commit data...
bits.h Loading commit data...
bounded-page-allocator.cc Loading commit data...
bounded-page-allocator.h Loading commit data...
bounds.h Loading commit data...
build_config.h Loading commit data...
compiler-specific.h Loading commit data...
cpu.cc Loading commit data...
cpu.h Loading commit data...
division-by-constant.cc Loading commit data...
division-by-constant.h Loading commit data...
enum-set.h Loading commit data...
export-template.h Loading commit data...
file-utils.cc Loading commit data...
file-utils.h Loading commit data...
flags.h Loading commit data...
free_deleter.h Loading commit data...
functional.cc Loading commit data...
functional.h Loading commit data...
hashmap-entry.h Loading commit data...
hashmap.h Loading commit data...
ieee754.cc Loading commit data...
ieee754.h Loading commit data...
iterator.h Loading commit data...
lazy-instance.h Loading commit data...
list.h Loading commit data...
logging.cc Loading commit data...
logging.h Loading commit data...
lsan.h Loading commit data...
macros.h Loading commit data...
memory.h Loading commit data...
once.cc Loading commit data...
once.h Loading commit data...
optional.h Loading commit data...
overflowing-math.h Loading commit data...
page-allocator.cc Loading commit data...
page-allocator.h Loading commit data...
qnx-math.h Loading commit data...
region-allocator.cc Loading commit data...
region-allocator.h Loading commit data...
ring-buffer.h Loading commit data...
safe_conversions.h Loading commit data...
safe_conversions_impl.h Loading commit data...
small-vector.h Loading commit data...
sys-info.cc Loading commit data...
sys-info.h Loading commit data...
template-utils.h Loading commit data...
threaded-list.h Loading commit data...
timezone-cache.h Loading commit data...
type-traits.h Loading commit data...
ubsan.cc Loading commit data...
v8-fallthrough.h Loading commit data...
vlq-base64.cc Loading commit data...
vlq-base64.h Loading commit data...
win32-headers.h Loading commit data...