Avoid sorting in hash map stable hashing

[Kobzol]

Suggested by @the8472 here. I hope that I understood it right, I replaced the sort with modular multiplication, which should be commutative.

Can I ask for a perf. run? However, locally it didn't help at all. Creating the StableHasher all over again is probably slowing it down quite a lot. And using FxHasher is not straightforward, because the keys and values only implement HashStable (and probably they shouldn't be just hashed via Hash anyway for it to actually be stable).

Maybe the StableHash interface could be changed somehow to better suppor these scenarios where the hasher is short-lived. Or the StableHasher implementation could have variants with e.g. a shorter buffer for these scenarios.

[rust-highfive]

r? @davidtwco

(rust-highfive has picked a reviewer for you, use r? to override)

[the8472]

@bors try @rust-timer queue

However, locally it didn't help at all. Creating the StableHasher all over again is probably slowing it down quite a lot.

Yeah, that's what I meant that it would probably need a FastStableHasher.

[rust-timer]

Awaiting bors try build completion.

@rustbot label: +S-waiting-on-perf

[bors]

⌛ Trying commit a5f5f6b with merge 4324513d2ed2011b78a1cf96c1ffddf672c4fe5c...

[the8472]

I replaced the sort with modular multiplication, which should be commutative.

You might want to use a modular addition instead. At least a theoretical issue with multiplies is that they have an absorbing element (zero). Although for u128 it's exceedingly unlikely to hit that element at random, assuming the hash function is good.
And of course multipliers are slower.

[camelid]

@bors try

[bors]

⌛ Trying commit 6e33d3e with merge 3c7d8f13f3bb90efbad4e21f0b2baf0bf274c42d...

[bors]

☀️ Try build successful - checks-actions
Build commit: 3c7d8f13f3bb90efbad4e21f0b2baf0bf274c42d (3c7d8f13f3bb90efbad4e21f0b2baf0bf274c42d)

[rust-timer]

Queued 3c7d8f13f3bb90efbad4e21f0b2baf0bf274c42d with parent 6bda5b3, future comparison URL.

[rust-timer]

Finished benchmarking commit (3c7d8f13f3bb90efbad4e21f0b2baf0bf274c42d): comparison url.

Summary: This change led to large relevant mixed results 🤷 in compiler performance.

• Large improvement in instruction counts (up to -4.8% on incr-full builds of clap-rs)
• Small regression in instruction counts (up to 0.7% on incr-patched: println builds of style-servo)

If you disagree with this performance assessment, please file an issue in rust-lang/rustc-perf.

Benchmarking this pull request likely means that it is perf-sensitive, so we're automatically marking it as not fit for rolling up. While you can manually mark this PR as fit for rollup, we strongly recommend not doing so since this PR led to changes in compiler perf.

Next Steps: If you can justify the regressions found in this try perf run, please indicate this with @rustbot label: +perf-regression-triaged along with sufficient written justification. If you cannot justify the regressions please fix the regressions and do another perf run. If the next run shows neutral or positive results, the label will be automatically removed.

@bors rollup=never
@rustbot label: +S-waiting-on-review -S-waiting-on-perf +perf-regression

[Kobzol]

Not too bad. I tried to use the same approach for more data structures, could I ask for another perf. run please?

[davidtwco]

@bors try @rust-timer queue

[rust-timer]

Awaiting bors try build completion.

@rustbot label: +S-waiting-on-perf

[bors]

⌛ Testing commit 1f284b0 with merge aa63e5d0547b2df209cbcb4ce313c56abdf375a7...

[rust-log-analyzer]

The job x86_64-msvc-2 failed! Check out the build log: (web) (plain)

Click to see the possible cause of the failure (guessed by this bot)

9 note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
10 


The actual run.stderr differed from the expected run.stderr.
Actual run.stderr saved to D:\a\rust\rust\build\x86_64-pc-windows-msvc\test\ui\panics\panic-short-backtrace-windows-x86_64\panic-short-backtrace-windows-x86_64.run.stderr
error: 1 errors occurred comparing run output.
status: exit code: 101
status: exit code: 101
command: PATH="D:\a\rust\rust\build\x86_64-pc-windows-msvc\stage2\lib\rustlib\x86_64-pc-windows-msvc\lib;C:\Program Files (x86)\Windows Kits\10\bin\x64;C:\Program Files (x86)\Windows Kits\10\bin\10.0.22000.0\x64;C:\Program Files (x86)\Microsoft Visual Studio\2019\Enterprise\VC\Tools\MSVC\14.29.30133\bin\HostX64\x64;C:\Program Files (x86)\Microsoft Visual Studio\2019\Enterprise\VC\Tools\MSVC\14.29.30133\bin\HostX64\x64;D:\a\rust\rust\build\x86_64-pc-windows-msvc\stage0-bootstrap-tools\x86_64-pc-windows-msvc\release\deps;D:\a\rust\rust\build\x86_64-pc-windows-msvc\stage0\bin;D:\a\rust\rust\ninja;D:\a\rust\rust\msys2\mingw64\bin;C:\hostedtoolcache\windows\Python\3.10.0\x64\Scripts;C:\hostedtoolcache\windows\Python\3.10.0\x64;C:\msys64\usr\bin;D:\a\rust\rust\sccache;C:\Program Files\MongoDB\Server\5.0\bin;C:\aliyun-cli;C:\vcpkg;C:\cf-cli;C:\Program Files (x86)\NSIS;C:\tools\zstd;C:\Program Files\Mercurial;C:\hostedtoolcache\windows\stack\2.7.3\x64;C:\cabal\bin;C:\ghcup\bin;C:\tools\ghc-9.2.1\bin;C:\Program Files\dotnet;C:\mysql\bin;C:\Program Files\R\R-4.1.2\bin\x64;C:\SeleniumWebDrivers\GeckoDriver;C:\Program Files (x86)\sbt\bin;C:\Rust\.cargo\bin;C:\Program Files (x86)\GitHub CLI;C:\Program Files\Git\bin;C:\Program Files (x86)\pipx_bin;C:\hostedtoolcache\windows\go\1.15.15\x64\bin;C:\hostedtoolcache\windows\Python\3.7.9\x64\Scripts;C:\hostedtoolcache\windows\Python\3.7.9\x64;C:\hostedtoolcache\windows\Ruby\2.5.9\x64\bin;C:\tools\kotlinc\bin;C:\hostedtoolcache\windows\Java_Temurin-Hotspot_jdk\8.0.312-7\x64\bin;C:\npm\prefix;C:\Program Files (x86)\Microsoft SDKs\Azure\CLI2\wbin;C:\ProgramData\kind;C:\Program Files\Eclipse Foundation\jdk-8.0.302.8-hotspot\bin;C:\Windows\system32;C:\Windows;C:\Windows\System32\Wbem;C:\Windows\System32\WindowsPowerShell\v1.0;C:\Windows\System32\OpenSSH;C:\ProgramData\Chocolatey\bin;C:\Program Files\Docker;C:\Program Files\PowerShell\7;C:\Program Files\Microsoft\Web Platform Installer;C:\Program Files\dotnet;C:\Program Files\Microsoft SQL Server\130\Tools\Binn;C:\Program Files\Microsoft SQL Server\Client SDK\ODBC\170\Tools\Binn;C:\Program Files (x86)\Windows Kits\10\Windows Performance Toolkit;C:\Program Files (x86)\Microsoft SQL Server\110\DTS\Binn;C:\Program Files (x86)\Microsoft SQL Server\120\DTS\Binn;C:\Program Files (x86)\Microsoft SQL Server\130\DTS\Binn;C:\Program Files (x86)\Microsoft SQL Server\140\DTS\Binn;C:\Program Files (x86)\Microsoft SQL Server\150\DTS\Binn;C:\Program Files\nodejs;C:\Program Files\OpenSSL\bin;C:\Strawberry\c\bin;C:\Strawberry\perl\site\bin;C:\Strawberry\perl\bin;C:\ProgramData\chocolatey\lib\pulumi\tools\Pulumi\bin;C:\Program Files\TortoiseSVN\bin;C:\Program Files\CMake\bin;C:\ProgramData\chocolatey\lib\maven\apache-maven-3.8.4\bin;C:\Program Files\Microsoft Service Fabric\bin\Fabric\Fabric.Code;C:\Program Files\Microsoft SDKs\Service Fabric\Tools\ServiceFabricLocalClusterManager;C:\Program Files\Git\cmd;C:\Program Files\Git\mingw64\bin;C:\Program Files\Git\usr\bin;C:\tools\php;C:\Program Files (x86)\sbt\bin;C:\SeleniumWebDrivers\ChromeDriver;C:\SeleniumWebDrivers\EdgeDriver;C:\Program Files\Amazon\AWSCLIV2;C:\Program Files\Amazon\SessionManagerPlugin\bin;C:\Program Files\Amazon\AWSSAMCLI\bin;C:\Program Files (x86)\Google\Cloud SDK\google-cloud-sdk\bin;C:\Program Files (x86)\Microsoft BizTalk Server;C:\Program Files\LLVM\bin;C:\Users\runneradmin\.dotnet\tools;C:\Users\runneradmin\AppData\Local\Microsoft\WindowsApps" "D:\\a\\rust\\rust\\build\\x86_64-pc-windows-msvc\\test\\ui\\panics\\panic-short-backtrace-windows-x86_64\\a.exe"
------------------------------------------

------------------------------------------
stderr:
stderr:
------------------------------------------
thread 'main' panicked at 'd was called', D:\a\rust\rust\src/test\ui\panics\panic-short-backtrace-windows-x86_64.rs:48:5
   0: std::panicking::begin_panic
   1: d
   2: c
   3: b
---

Some tests failed in compiletest suite=ui mode=ui host=x86_64-pc-windows-msvc target=x86_64-pc-windows-msvc


command did not execute successfully: "D:\\a\\rust\\rust\\build\\x86_64-pc-windows-msvc\\stage0-tools-bin\\compiletest.exe" "--compile-lib-path" "D:\\a\\rust\\rust\\build\\x86_64-pc-windows-msvc\\stage2\\bin" "--run-lib-path" "D:\\a\\rust\\rust\\build\\x86_64-pc-windows-msvc\\stage2\\lib\\rustlib\\x86_64-pc-windows-msvc\\lib" "--rustc-path" "D:\\a\\rust\\rust\\build\\x86_64-pc-windows-msvc\\stage2\\bin\\rustc.exe" "--src-base" "D:\\a\\rust\\rust\\src/test\\ui" "--build-base" "D:\\a\\rust\\rust\\build\\x86_64-pc-windows-msvc\\test\\ui" "--stage-id" "stage2-x86_64-pc-windows-msvc" "--suite" "ui" "--mode" "ui" "--target" "x86_64-pc-windows-msvc" "--host" "x86_64-pc-windows-msvc" "--llvm-filecheck" "D:\\a\\rust\\rust\\build\\x86_64-pc-windows-msvc\\llvm\\build\\bin\\FileCheck.exe" "--nodejs" "C:\\Program Files\\nodejs\\node" "--npm" "C:\\Program Files\\nodejs\\npm" "--host-rustcflags" "-Crpath -O -Cdebuginfo=0  -Lnative=D:\\a\\rust\\rust\\build\\x86_64-pc-windows-msvc\\native\\rust-test-helpers" "--target-rustcflags" "-Crpath -O -Cdebuginfo=0  -Lnative=D:\\a\\rust\\rust\\build\\x86_64-pc-windows-msvc\\native\\rust-test-helpers" "--docck-python" "C:\\hostedtoolcache\\windows\\Python\\3.10.0\\x64\\python3.exe" "--lldb-python" "C:\\hostedtoolcache\\windows\\Python\\3.10.0\\x64\\python3.exe" "--gdb" "C:\\msys64\\usr\\bin\\gdb" "--llvm-version" "13.0.0-rust-1.59.0-nightly" "--llvm-components" "aarch64 aarch64asmparser aarch64codegen aarch64desc aarch64disassembler aarch64info aarch64utils aggressiveinstcombine all all-targets analysis arm armasmparser armcodegen armdesc armdisassembler arminfo armutils asmparser asmprinter avr avrasmparser avrcodegen avrdesc avrdisassembler avrinfo binaryformat bitreader bitstreamreader bitwriter bpf bpfasmparser bpfcodegen bpfdesc bpfdisassembler bpfinfo cfguard codegen core coroutines coverage debuginfocodeview debuginfodwarf debuginfogsym debuginfomsf debuginfopdb demangle dlltooldriver dwarflinker dwp engine executionengine extensions filecheck frontendopenacc frontendopenmp fuzzmutate globalisel hexagon hexagonasmparser hexagoncodegen hexagondesc hexagondisassembler hexagoninfo instcombine instrumentation interfacestub interpreter ipo irreader jitlink libdriver lineeditor linker lto m68k m68kasmparser m68kcodegen m68kdesc m68kdisassembler m68kinfo mc mca mcdisassembler mcjit mcparser mips mipsasmparser mipscodegen mipsdesc mipsdisassembler mipsinfo mirparser msp430 msp430asmparser msp430codegen msp430desc msp430disassembler msp430info native nativecodegen nvptx nvptxcodegen nvptxdesc nvptxinfo objcarcopts object objectyaml option orcjit orcshared orctargetprocess passes powerpc powerpcasmparser powerpccodegen powerpcdesc powerpcdisassembler powerpcinfo profiledata remarks riscv riscvasmparser riscvcodegen riscvdesc riscvdisassembler riscvinfo runtimedyld scalaropts selectiondag sparc sparcasmparser sparccodegen sparcdesc sparcdisassembler sparcinfo support symbolize systemz systemzasmparser systemzcodegen systemzdesc systemzdisassembler systemzinfo tablegen target textapi transformutils vectorize webassembly webassemblyasmparser webassemblycodegen webassemblydesc webassemblydisassembler webassemblyinfo webassemblyutils windowsmanifest x86 x86asmparser x86codegen x86desc x86disassembler x86info xray" "--cc" "" "--cxx" "" "--cflags" "" "--adb-path" "adb" "--adb-test-dir" "/data/tmp/work" "--android-cross-path" "" "--channel" "nightly" "--color" "always"


Build completed unsuccessfully in 0:38:00
Build completed unsuccessfully in 0:38:00
make: *** [Makefile:74: ci-subset-2] Error 1

[bors]

💔 Test failed - checks-actions

[the8472]

Seems to affect other PRs too, e.g #91110

@bors retry

[bors]

⌛ Testing commit 1f284b0 with merge 9fcd6dee4904d6ab8364f00d2bfca1a64f2e73f0...

[bors]

💥 Test timed out

[rust-log-analyzer]

A job failed! Check out the build log: (web) (plain)

Click to see the possible cause of the failure (guessed by this bot)

[the8472]

@bors retry

[bors]

⌛ Testing commit 1f284b0 with merge daf2204...

[bors]

☀️ Test successful - checks-actions
Approved by: the8472
Pushing daf2204 to master...

[rust-timer]

Finished benchmarking commit (daf2204): comparison url.

Summary: This change led to large relevant mixed results 🤷 in compiler performance.

• Large improvement in instruction counts (up to -4.9% on incr-full builds of clap-rs)
• Moderate regression in instruction counts (up to 2.8% on incr-patched: println builds of regression-31157)

If you disagree with this performance assessment, please file an issue in rust-lang/rustc-perf.

Next Steps: If you can justify the regressions found in this perf run, please indicate this with @rustbot label: +perf-regression-triaged along with sufficient written justification. If you cannot justify the regressions please open an issue or create a new PR that fixes the regressions, add a comment linking to the newly created issue or PR, and then add the perf-regression-triaged label to this PR.

@rustbot label: +perf-regression