Repository: pytorch
Issue: The CPU version of `torch.cummax` is slow
Labels: module: performance,module: cpu,triaged

### 🐛 Describe the bug

The CPU version of `cummax` is very slow, even more than a naive custom implementation.
This does not happen on the GPU `cummax`. 

This problem was originally posted [in the forum](https://discuss.pytorch.org/t/cpu-version-of-torch-cummax-is-slow/187612/2).
This benchmark code below is not from me but from the user `KFrank`. 
It can reproduce the problem while being more simple.

```python
import torch
print (torch.__version__)
print (torch.version.cuda)
print (torch.cuda.get_device_name())

from time import time

_ = torch.manual_seed (2023)

def corner_pool(x: torch.Tensor, dim: int, flip: bool):
    sz = x.size(dim)
    outputs = list(x.unbind(dim))
    
    for i in range(1, sz):
        if flip:
            i_in = sz - i
            i_out = sz - i - 1
        else:
            i_in = i - 1
            i_out = i
        outputs[i_out] = torch.maximum(outputs[i_out], outputs[i_in])
    
    return torch.stack(outputs, dim=dim)

img = torch.rand (1, 128, 256, 256)

cmA = torch.cummax (img, dim = -2)[0]
cmB = corner_pool (img, -2, False)
print ('cpu equal:', torch.equal (cmA, cmB))

t0 = time()
for  i in range (10):
    cmA = torch.cummax (img, dim = -2)[0]

print ('cpu cummax time:      ', time() - t0)

t0 = time()
for  i in range (10):
    cmB = corner_pool (img, -2, False)

print ('cpu corner_pool time: ', time() - t0)

img = img.cuda()

cmA = torch.cummax (img, dim = -2)[0]
cmB = corner_pool (img, -2, False)
print ('gpu equal:', torch.equal (cmA, cmB))

torch.cuda.synchronize()
t0 = time()
for  i in range (10):
    cmA = torch.cummax (img, dim = -2)[0]

torch.cuda.synchronize()
print ('gpu cummax time:      ', time() - t0)
```

The script's output is:

```shell
2.0.1+cu117
11.7
NVIDIA GeForce GTX 1660 Ti
cpu equal: True
cpu cummax time:       1.9056651592254639
cpu corner_pool time:  0.25840282440185547
gpu equal: True
gpu cummax time:       0.007984399795532227
```

### Versions

```
Collecting environment information...
PyTorch version: 2.0.1+cu117
Is debug build: False
CUDA used to build PyTorch: 11.7
ROCM used to build PyTorch: N/A

OS: Debian GNU/Linux 12 (bookworm) (x86_64)
GCC version: (Debian 12.2.0-14) 12.2.0
Clang version: Could not collect
CMake version: version 3.26.4
Libc version: glibc-2.36

Python version: 3.11.2 (main, Mar 13 2023, 12:18:29) [GCC 12.2.0] (64-bit runtime)
Python platform: Linux-6.1.0-10-amd64-x86_64-with-glibc2.36
Is CUDA available: True
CUDA runtime version: 12.2.91
CUDA_MODULE_LOADING set to: LAZY
GPU models and configuration: GPU 0: NVIDIA GeForce GTX 1660 Ti
Nvidia driver version: 535.54.03
cuDNN version: Could not collect
HIP runtime version: N/A
MIOpen runtime version: N/A
Is XNNPACK available: True

CPU:
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Address sizes:                   48 bits physical, 48 bits virtual
Byte Order:                      Little Endian
CPU(s):                          16
On-line CPU(s) list:             0-15
Vendor ID:                       AuthenticAMD
Model name:                      AMD Ryzen 7 4800H with Radeon Graphics
CPU family:                      23
Model:                           96
Thread(s) per core:              2
Core(s) per socket:              8
Socket(s):                       1
Stepping:                        1
Frequency boost:                 enabled
CPU(s) scaling MHz:              50%
CPU max MHz:                     2900.0000
CPU min MHz:                     1400.0000
BogoMIPS:                        5788.80
Flags:                           fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt pdpe1gb rdtscp lm constant_tsc rep_good nopl nonstop_tsc cpuid extd_apicid aperfmperf rapl pni pclmulqdq monitor ssse3 fma cx16 sse4_1 sse4_2 movbe popcnt aes xsave avx f16c rdrand lahf_lm cmp_legacy svm extapic cr8_legacy abm sse4a misalignsse 3dnowprefetch osvw ibs skinit wdt tce topoext perfctr_core perfctr_nb bpext perfctr_llc mwaitx cpb cat_l3 cdp_l3 hw_pstate ssbd mba ibrs ibpb stibp vmmcall fsgsbase bmi1 avx2 smep bmi2 cqm rdt_a rdseed adx smap clflushopt clwb sha_ni xsaveopt xsavec xgetbv1 cqm_llc cqm_occup_llc cqm_mbm_total cqm_mbm_local clzero irperf xsaveerptr rdpru wbnoinvd cppc arat npt lbrv svm_lock nrip_save tsc_scale vmcb_clean flushbyasid decodeassists pausefilter pfthreshold avic v_vmsave_vmload vgif v_spec_ctrl umip rdpid overflow_recov succor smca
Virtualization:                  AMD-V
L1d cache:                       256 KiB (8 instances)
L1i cache:                       256 KiB (8 instances)
L2 cache:                        4 MiB (8 instances)
L3 cache:                        8 MiB (2 instances)
NUMA node(s):                    1
NUMA node0 CPU(s):               0-15
Vulnerability Itlb multihit:     Not affected
Vulnerability L1tf:              Not affected
Vulnerability Mds:               Not affected
Vulnerability Meltdown:          Not affected
Vulnerability Mmio stale data:   Not affected
Vulnerability Retbleed:          Mitigation; untrained return thunk; SMT enabled with STIBP protection
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1:        Mitigation; usercopy/swapgs barriers and __user pointer sanitization
Vulnerability Spectre v2:        Mitigation; Retpolines, IBPB conditional, STIBP always-on, RSB filling, PBRSB-eIBRS Not affected
Vulnerability Srbds:             Not affected
Vulnerability Tsx async abort:   Not affected

Versions of relevant libraries:
[pip3] dirtytorch==1.2.1
[pip3] flake8==6.0.0
[pip3] mypy-extensions==0.4.3
[pip3] numpy==1.24.2
[pip3] pytorch-lightning==2.0.5
[pip3] torch==2.0.1
[pip3] torchmetrics==1.0.1
[pip3] triton==2.0.0
[conda] Could not collect
```

cc @jgong5 @mingfeima @XiaobingSuper @sanchitintel @ashokei @jingxu10 @albanD