Investigate warpspeed scan regressions for small problem sizes

[bernhardmgruber]

When integrating the warpspeed scan implemenation #6811, we ate a few regressions compared to the old implementation, especially for small problem sizes.

We should investigate whether we can improve the new scan implementation on those small problem sizes to recover the lost performance.

[bernhardmgruber]

Current performance comparison of old vs. new scan implementation on B200:

T{ct}	OffsetT{ct}	Elements{io}	Ref Time	Ref Noise	Cmp Time	Cmp Noise	Diff	%Diff	Status
I8	I64	2^16	9.134 us	1.60%	11.180 us	0.94%	2.046 us	22.40%	🔴 SLOW
I8	I64	2^20	11.729 us	6.69%	13.393 us	4.28%	1.663 us	14.18%	🔴 SLOW
I8	I64	2^24	50.335 us	2.13%	26.068 us	2.99%	-24.266 us	-48.21%	🟢 FAST
I8	I64	2^28	664.678 us	0.55%	214.950 us	0.60%	-449.729 us	-67.66%	🟢 FAST
I8	I64	2^32	10.530 ms	0.14%	3.237 ms	0.24%	-7293.352 us	-69.26%	🟢 FAST
I16	I64	2^16	10.258 us	10.01%	11.384 us	0.49%	1.126 us	10.98%	🔴 SLOW
I16	I64	2^20	15.420 us	3.35%	12.484 us	8.17%	-2.935 us	-19.04%	🟢 FAST
I16	I64	2^24	51.088 us	4.45%	28.786 us	3.92%	-22.302 us	-43.65%	🟢 FAST
I16	I64	2^28	613.018 us	1.48%	212.022 us	0.50%	-400.996 us	-65.41%	🟢 FAST
I16	I64	2^32	9.587 ms	0.37%	3.222 ms	1.19%	-6364.300 us	-66.39%	🟢 FAST
I32	I64	2^16	11.259 us	1.87%	10.413 us	9.79%	-0.845 us	-7.51%	🟢 FAST
I32	I64	2^20	12.549 us	7.95%	13.055 us	5.16%	0.506 us	4.03%	🔵 SAME
I32	I64	2^24	48.383 us	3.05%	34.798 us	3.45%	-13.585 us	-28.08%	🟢 FAST
I32	I64	2^28	623.571 us	0.90%	320.067 us	0.50%	-303.504 us	-48.67%	🟢 FAST
I32	I64	2^32	9.842 ms	0.24%	4.952 ms	0.88%	-4890.313 us	-49.69%	🟢 FAST
I64	I64	2^16	11.233 us	2.06%	12.164 us	8.77%	0.931 us	8.28%	🔴 SLOW
I64	I64	2^20	15.310 us	3.09%	15.827 us	5.01%	0.517 us	3.38%	🔴 SLOW
I64	I64	2^24	87.347 us	1.89%	55.298 us	2.04%	-32.049 us	-36.69%	🟢 FAST
I64	I64	2^28	1.235 ms	0.42%	622.147 us	0.19%	-612.443 us	-49.61%	🟢 FAST
I64	I64	2^32	19.606 ms	0.11%	10.251 ms	0.74%	-9354.826 us	-47.71%	🟢 FAST
I128	I64	2^16	13.468 us	3.89%	12.408 us	8.36%	-1.060 us	-7.87%	🟢 FAST
I128	I64	2^20	31.084 us	3.62%	21.506 us	2.19%	-9.578 us	-30.81%	🟢 FAST
I128	I64	2^24	346.849 us	0.42%	146.160 us	0.79%	-200.690 us	-57.86%	🟢 FAST
I128	I64	2^28	5.347 ms	0.10%	2.011 ms	0.24%	-3335.592 us	-62.38%	🟢 FAST
I128	I64	2^32	85.378 ms	0.03%	31.699 ms	0.04%	-53678.382 us	-62.87%	🟢 FAST
F32	I64	2^16	11.115 us	4.97%	11.255 us	4.64%	0.139 us	1.25%	🔵 SAME
F32	I64	2^20	12.667 us	7.44%	13.434 us	3.00%	0.767 us	6.06%	🔴 SLOW
F32	I64	2^24	48.437 us	3.35%	36.162 us	3.65%	-12.275 us	-25.34%	🟢 FAST
F32	I64	2^28	622.133 us	1.00%	318.619 us	0.39%	-303.513 us	-48.79%	🟢 FAST
F32	I64	2^32	9.809 ms	0.24%	4.857 ms	0.56%	-4951.773 us	-50.48%	🟢 FAST
F64	I64	2^16	11.294 us	2.34%	11.540 us	4.62%	0.246 us	2.17%	🔵 SAME
F64	I64	2^20	15.361 us	1.38%	16.090 us	6.24%	0.729 us	4.75%	🔴 SLOW
F64	I64	2^24	78.598 us	1.44%	57.088 us	2.19%	-21.510 us	-27.37%	🟢 FAST
F64	I64	2^28	1.083 ms	0.34%	640.154 us	0.21%	-443.189 us	-40.91%	🟢 FAST
F64	I64	2^32	17.160 ms	0.08%	10.008 ms	0.14%	-7151.614 us	-41.68%	🟢 FAST
C32	I64	2^16	11.024 us	5.93%	11.245 us	2.94%	0.221 us	2.00%	🔵 SAME
C32	I64	2^20	15.697 us	4.90%	15.639 us	3.62%	-0.057 us	-0.37%	🔵 SAME
C32	I64	2^24	95.608 us	1.61%	55.429 us	1.93%	-40.179 us	-42.02%	🟢 FAST
C32	I64	2^28	1.364 ms	0.40%	624.489 us	0.19%	-739.365 us	-54.21%	🟢 FAST
C32	I64	2^32	21.684 ms	0.10%	9.762 ms	0.06%	-11921.183 us	-54.98%	🟢 FAST

[bernhardmgruber]

I think I am happy with the current performance compared to the old implementation. We are really shipping some super solid speedups! The few regressions we have:

|  T{ct}  |  OffsetT{ct}  |  Elements{io}  |   Ref Time |   Ref Noise |   Cmp Time |   Cmp Noise |          Diff |   %Diff |  Status  |
|---------|---------------|----------------|------------|-------------|------------|-------------|---------------|---------|----------|
|   I8    |      I64      |      2^16      |   9.134 us |       1.60% |  11.180 us |       0.94% |      2.046 us |  22.40% |  🔴 SLOW  |
|   I8    |      I64      |      2^20      |  11.729 us |       6.69% |  13.393 us |       4.28% |      1.663 us |  14.18% |  🔴 SLOW  |
|   I16   |      I64      |      2^16      |  10.258 us |      10.01% |  11.384 us |       0.49% |      1.126 us |  10.98% |  🔴 SLOW  |
|   I64   |      I64      |      2^16      |  11.233 us |       2.06% |  12.164 us |       8.77% |      0.931 us |   8.28% |  🔴 SLOW  |
|   I64   |      I64      |      2^20      |  15.310 us |       3.09% |  15.827 us |       5.01% |      0.517 us |   3.38% |  🔴 SLOW  |
|   F32   |      I64      |      2^20      |  12.667 us |       7.44% |  13.434 us |       3.00% |      0.767 us |   6.06% |  🔴 SLOW  |
|   F64   |      I64      |      2^20      |  15.361 us |       1.38% |  16.090 us |       6.24% |      0.729 us |   4.75% |  🔴 SLOW  |

look relatively large, but their absolute time increases are below 2us. I think we can tolerate this for now, since we have other issues to look into as well.

[bernhardmgruber]

I discussed this with @gevtushenko and we decided that we are happy with the current state and leave further investigation for later.