• Simon Zünd's avatar
    Reland "[array] Use random middle element to determine pivot during sorting" · 3896cdc2
    Simon Zünd authored
    This is a reland of 91bab558
    
    This CL contains two major changes w.r.t to the original CL:
    
    The random state is removed from the Smi root list and we pre-seed the RNG
    on each sort with the length of the array.
    
    To cut down on the length of the arguments list and to keep track of the
    random state across recursive calls, we move most of the sort arguments into
    a FixedArray and reload from the array for each recursion.
    
    Original change's description:
    > [array] Use random middle element to determine pivot during sorting
    >
    > This CL adds a "random state" to the Smi Root list and implements a
    > basic Linear congruential pseudo random number generator in Torque.
    >
    > The RNG is used to determine the pivot element for sorting. This will
    > prevent the worst cases for certain data layouts.
    >
    > Drive-by-fix: Make sorting of ranges and execution pauses for profviz
    > deterministic by adding a secondary sorting criteria.
    >
    > Bug: v8:7382
    > Cq-Include-Trybots: luci.v8.try:v8_linux_noi18n_rel_ng
    > Change-Id: Ieb871e98e74bdb803f821b0cd35d2f67ee0f2868
    > Reviewed-on: https://chromium-review.googlesource.com/1082193
    > Reviewed-by: Hannes Payer <hpayer@chromium.org>
    > Reviewed-by: Jakob Gruber <jgruber@chromium.org>
    > Reviewed-by: Camillo Bruni <cbruni@chromium.org>
    > Commit-Queue: Simon Zünd <szuend@google.com>
    > Cr-Commit-Position: refs/heads/master@{#53524}
    
    Bug: v8:7382
    Change-Id: Ia7bef7ed1c0e904ffe43bc428e702f64f9c6a60b
    Cq-Include-Trybots: luci.v8.try:v8_linux_noi18n_rel_ng
    Reviewed-on: https://chromium-review.googlesource.com/1087888Reviewed-by: 's avatarCamillo Bruni <cbruni@chromium.org>
    Reviewed-by: 's avatarJakob Gruber <jgruber@chromium.org>
    Commit-Queue: Simon Zünd <szuend@google.com>
    Cr-Commit-Position: refs/heads/master@{#53583}
    3896cdc2
Name
Last commit
Last update
..
blink_tests Loading commit data...
cfi Loading commit data...
clusterfuzz Loading commit data...
dev Loading commit data...
gcmole Loading commit data...
generate_shim_headers Loading commit data...
heap-stats Loading commit data...
ignition Loading commit data...
jsfunfuzz Loading commit data...
link_clicker.extension Loading commit data...
mb Loading commit data...
memory Loading commit data...
msan Loading commit data...
ninja Loading commit data...
node Loading commit data...
perf Loading commit data...
profview Loading commit data...
profviz Loading commit data...
release Loading commit data...
sanitizers Loading commit data...
sodium Loading commit data...
testrunner Loading commit data...
toolchain Loading commit data...
torque Loading commit data...
turbolizer Loading commit data...
ubsan Loading commit data...
unittests Loading commit data...
v8.xcodeproj Loading commit data...
valgrind/asan Loading commit data...
vim Loading commit data...
visual_studio Loading commit data...
wasm Loading commit data...
BUILD.gn Loading commit data...
DEPS Loading commit data...
Makefile.tags Loading commit data...
OWNERS Loading commit data...
SourceMap.js Loading commit data...
adb-d8.py Loading commit data...
android-build.sh Loading commit data...
android-ll-prof.sh Loading commit data...
android-run.py Loading commit data...
android-sync.sh Loading commit data...
arguments.js Loading commit data...
bash-completion.sh Loading commit data...
bigint-tester.py Loading commit data...
callstats.html Loading commit data...
callstats.py Loading commit data...
check-inline-includes.sh Loading commit data...
check-static-initializers.sh Loading commit data...
check-unused-bailouts.sh Loading commit data...
codemap.js Loading commit data...
collect_deprecation_stats.sh Loading commit data...
compare-table-gen.js Loading commit data...
concatenate-files.py Loading commit data...
consarray.js Loading commit data...
cpu.sh Loading commit data...
cross_build_gcc.sh Loading commit data...
csvparser.js Loading commit data...
detect-builtins.js Loading commit data...
disasm.py Loading commit data...
draw_instruction_graph.sh Loading commit data...
dump-cpp.py Loading commit data...
dumpcpp-driver.js Loading commit data...
dumpcpp.js Loading commit data...
eval_gc_nvp.py Loading commit data...
eval_gc_time.sh Loading commit data...
find-commit-for-patch.py Loading commit data...
find_depot_tools.py Loading commit data...
freebsd-tick-processor Loading commit data...
fuzz-harness.sh Loading commit data...
gc-nvp-to-csv.py Loading commit data...
gc-nvp-trace-processor.py Loading commit data...
gc_nvp_common.py Loading commit data...
gdb-v8-support.py Loading commit data...
gdbinit Loading commit data...
gen-inlining-tests.py Loading commit data...
gen-postmortem-metadata.py Loading commit data...
generate-builtins-tests.py Loading commit data...
generate-ten-powers.scm Loading commit data...
get_landmines.py Loading commit data...
grokdump.py Loading commit data...
ic-explorer.html Loading commit data...
ic-processor Loading commit data...
ic-processor-driver.js Loading commit data...
ic-processor.js Loading commit data...
js2c.py Loading commit data...
jsmin.py Loading commit data...
linux-tick-processor Loading commit data...
ll_prof.py Loading commit data...
lldb_commands.py Loading commit data...
lldbinit Loading commit data...
logreader.js Loading commit data...
mac-nm Loading commit data...
mac-tick-processor Loading commit data...
map-processor Loading commit data...
map-processor-driver.js Loading commit data...
map-processor.html Loading commit data...
map-processor.js Loading commit data...
mips_toolchain.tar.gz.sha1 Loading commit data...
objdump-v8 Loading commit data...
parse-processor Loading commit data...
parse-processor-driver.js Loading commit data...
parse-processor.html Loading commit data...
parse-processor.js Loading commit data...
perf-compare.py Loading commit data...
perf-to-html.py Loading commit data...
plot-timer-events Loading commit data...
predictable_wrapper.py Loading commit data...
presubmit.py Loading commit data...
profile.js Loading commit data...
profile_view.js Loading commit data...
run-llprof.sh Loading commit data...
run-num-fuzzer.py Loading commit data...
run-perf.sh Loading commit data...
run-tests.py Loading commit data...
run.py Loading commit data...
run_perf.py Loading commit data...
shell-utils.h Loading commit data...
splaytree.js Loading commit data...
stats-viewer.py Loading commit data...
tick-processor.html Loading commit data...
tickprocessor-driver.js Loading commit data...
tickprocessor.js Loading commit data...
trace-maps-processor.py Loading commit data...
try_perf.py Loading commit data...
turbolizer-perf.py Loading commit data...
v8heapconst.py Loading commit data...
whitespace.txt Loading commit data...
windows-tick-processor.bat Loading commit data...