Repository: rust
Issue: `[u128; N]` array equality test is unproportionally slow
Labels: I-slow,T-compiler,C-optimization

Hello, for my ML research [I wrote a generic newtype wrapper](https://gist.github.com/0x7CFE/ac4504c84834b39b50bad4b3bff9a187) around primitive types that act as a fixed-size bit vector.

When profiling my code I've noticed some really strange performance difference depending on what underlying types were used.

It appeared that on the same workload `BitVector<[u128; 2]>` is **twice as slow** when compared to `BitVector<[u64; 4]>` (see profiles below). Notice, that the bit width in both cases is equal: 128 * 2 = 64 * 4 = 256.

I then wrote a minimal repdoducible variant of the issue:
```rust
#[test]
fn eq_bench() {
    type BitVector = super::BitVector<[u128; 2]>;
    // type BitVector = super::BitVector<[u64; 4]>;

    let set = std::collections::BTreeSet::from_iter((1..100_000).map(|_| BitVector::random(12)));
    let mut yay = 0usize;
    let mut nay = 0usize;

    let mut timestamp = std::time::Instant::now();
    let mut last_index = 0;

    for i in 0.. {
        let code = BitVector::random(12);

        for item in set.iter() {
            if *item & code == code {
                yay += 1;
            } else {
                nay += 1;
            }
        }

        if timestamp.elapsed().as_millis() > 1000 {
            println!("{i}: {yay} to {nay}, rate {rate}", rate = i - last_index);

            timestamp = std::time::Instant::now();
            last_index = i;
        }
    }
}
```

Depending on what type is used, on my machine it consistently takes around 4481 iterations per second on `[u64; 4]` and 1750 on `[u128; 2]` (2.5 times slower!). Interestingly enough, if I remove `& code` part, then both versions start performing more or less the same.

The profiles looks even stranger ([profile.tar.gz](https://github.com/rust-lang/rust/files/14220380/profile.tar.gz)).

`u64` version seems normal:
<img src = "https://github.com/rust-lang/rust/assets/3784017/11706beb-9c25-4d88-a55a-a264e5bd92c0" width="25%" height="25%">

...whereas on `u128`  you can quickly notice that `SpecArrayEq::spec_eq`'s time skyrockets and even dwarfs `BTreeSet` iteration!
<img src = "https://github.com/rust-lang/rust/assets/3784017/48800527-5d68-4d03-ab5a-e89a3e80053a" width="25%" height="25%">

It appears that the unsafe call to `crate::intrinsics::raw_eq` is the culprit:
https://github.com/rust-lang/rust/blob/c29082fe7dc6e902169cacbae165562a7e4a1fd6/library/core/src/array/equality.rs#L146-L156

### Meta

I built everything with just `cargo test --release`. No LTO, no `target-cpu=native`.

`rustc --version --verbose`:
```
rustc 1.74.0 (79e9716c9 2023-11-13)
binary: rustc
commit-hash: 79e9716c980570bfd1f666e3b16ac583f0168962
commit-date: 2023-11-13
host: x86_64-unknown-linux-gnu
release: 1.74.0
LLVM version: 17.0.4
```

`lscpu`:

```
$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  16
  On-line CPU(s) list:   0-15
Vendor ID:               GenuineIntel
  Model name:            12th Gen Intel(R) Core(TM) i7-1260P
    CPU family:          6
    Model:               154
    Thread(s) per core:  2
    Core(s) per socket:  12
    Socket(s):           1
    Stepping:            3
    CPU max MHz:         4700,0000
    CPU min MHz:         400,0000
    BogoMIPS:            4992.00
    Flags:               fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe sy
                         scall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc
                         _known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm sse4_1 sse4_2 x2apic movbe p
                         opcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb ssbd ibrs ibpb stibp ibrs_enh
                         anced tpr_shadow vnmi flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid rdseed adx smap cl
                         flushopt clwb intel_pt sha_ni xsaveopt xsavec xgetbv1 xsaves split_lock_detect avx_vnni dtherm ida arat pln pts hwp hwp_no
                         tify hwp_act_window hwp_epp hwp_pkg_req umip pku ospke waitpkg gfni vaes vpclmulqdq rdpid movdiri movdir64b fsrm md_clear 
                         serialize arch_lbr flush_l1d arch_capabilities
Virtualization features: 
  Virtualization:        VT-x
Caches (sum of all):     
  L1d:                   448 KiB (12 instances)
  L1i:                   640 KiB (12 instances)
  L2:                    9 MiB (6 instances)
  L3:                    18 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-15
Vulnerabilities:         
  Gather data sampling:  Not affected
  Itlb multihit:         Not affected
  L1tf:                  Not affected
  Mds:                   Not affected
  Meltdown:              Not affected
  Mmio stale data:       Not affected
  Retbleed:              Not affected
  Spec rstack overflow:  Not affected
  Spec store bypass:     Mitigation; Speculative Store Bypass disabled via prctl and seccomp
  Spectre v1:            Mitigation; usercopy/swapgs barriers and __user pointer sanitization
  Spectre v2:            Mitigation; Enhanced IBRS, IBPB conditional, RSB filling, PBRSB-eIBRS SW sequence
  Srbds:                 Not affected
  Tsx async abort:       Not affected
```