feat(findall): Add findall kernel

[shreyas-omkar]

NVIDIA GeForce RTX 5080

n	selectivity	AK (ms)	CUDA.jl (ms)
1,000,000	0.5	0.212	0.281
1,000,000	0.1	0.214	0.297
1,000,000	0.9	0.190	0.262
4,000,000	0.5	0.436	0.353
4,000,000	0.1	0.226	0.292
4,000,000	0.9	0.237	0.299
16,000,000	0.5	1.756	1.334
16,000,000	0.1	1.075	1.006
16,000,000	0.9	1.276	1.500

AMD Radeon RX 9060 XT

n	selectivity	AK (ms)	AMDGPU.jl (ms)
1,000,000	0.5	0.278	0.267
1,000,000	0.1	0.269	0.261
1,000,000	0.9	0.281	0.269
4,000,000	0.5	0.948	0.861
4,000,000	0.1	0.946	0.811
4,000,000	0.9	1.315	0.926
16,000,000	0.5	4.459	4.271
16,000,000	0.1	3.978	4.203
16,000,000	0.9	4.851	4.605

Apple M5

n	selectivity	AK (ms)	Metal.jl (ms)
1,000,000	0.5	1.592	1.073
1,000,000	0.1	0.994	0.950
1,000,000	0.9	1.147	1.105
4,000,000	0.5	3.076	3.354
4,000,000	0.1	2.690	2.726
4,000,000	0.9	3.503	4.843
16,000,000	0.5	11.554	12.833
16,000,000	0.1	10.093	15.357
16,000,000	0.9	17.754	19.665

[shreyas-omkar]

@christiangnrd @maleadt give it a check please. :)

[christiangnrd]

This looks good to me

[maleadt]

LGTM. I did some more benchmarking against all platforms I have access to, and CUB's DeviceSelect and PyTorch's nonzero still performed quite a bit better. AFAIU that's because the current design, copied from CUDA.jl, copies the Bool mask into an Int array, scans that in two passes, then re-reads it in the scatter. Meanwhile, the other libraries have an algorithm doing a reduce-then-scan stream compaction that reads significantly fewer bytes:

1. Count: one block kernel counts the selected elements of each block (block-local scan of per-thread counts, striped byte loads through local memory).
2. Scan: a tiny accumulate! over the per-block counts gives every block its output offset; the last entry is the total, which is the one host readback we need anyway to allocate the output.
3. Scatter: the same kernel runs again, seeded with the block offset, so each thread's exclusive prefix is directly an output slot; selected indices are written straight to out.

The mask is read twice (a byte per element) and the output written once. There are no atomics and no device-scope fences, so it runs unchanged on every backend, Metal included. The predicate form still evaluates the predicate exactly once per element into a Bool mask, which is cheaper than re-evaluating it in both passes for anything wider than a byte.

This seems to perform significantly better. AK.findall(x -> x < s, v) on Float32 input, milliseconds, selectivity 0.1 / 0.5 / 0.9. "Vendor" is the backend package's own findall; CUB is DeviceSelect::Flagged with a transform iterator over the same floats (i.e. what torch.nonzero calls).

Device	n	Before (this PR)	After	Vendor findall	CUB
RTX 5080	16M	1.05 / 1.17 / 1.24	0.26 / 0.30 / 0.40	0.97 / 1.07 / 1.15	0.09 / 0.16 / 0.23
RTX 5080	64M	4.19 / 4.65 / 4.96	0.91 / 1.08 / 1.45	3.78 / 4.19 / 4.50	0.36 / 0.63 / 0.92
Apple M1	16M	19.4 / 21.9 / 24.5	6.6 / 9.3 / 11.2	19.5 / 22.4 / 24.5
Apple M1	64M	74.0 / 85.9 / 94.7	19.4 / 25.8 / 33.7	76.9 / 89.0 / 98.5
Intel Xe iGPU (oneAPI)	16M	61.0 / 73.0 / 81.7	13.1 / 23.0 / 36.0	61.8 / 82.3 / 86.8
Intel Xe iGPU (oneAPI)	64M	240 / 288 / 321	46.6 / 88.2 / 134	245 / 293 / 329

Mask-only compaction (AK.findall(bools), 64M elements, RTX 5080): 0.49 / 0.65 / 1.03 ms versus CUB's 0.24 / 0.43 / 0.70 ms, so within about 1.5x of CUB. The remaining gap is CUB's single-pass decoupled lookback, which we can't use as the default because Metal lacks the required memory ordering.

I did introduce an Algorithm struct as we have with other abstractions, so if you think it's valuable we could restore the old approach as well under a different entry.

[maleadt]

Took another look, and I don't think the old implementation is worth keeping.

[shreyas-omkar]

I validated the new ScanScatter implementation on AMD (RX 9060 XT / gfx1200), which wasn't in the table:

Correctness: full findall test suite 205/205 on the GPU path.

Perf — findall(x -> x < s, v), Float32, ms (selectivity 0.1 / 0.5 / 0.9):

n	Old (this PR)	New (ScanScatter)
16M	3.98 / 4.46 / 4.85	1.07 / 1.30 / 1.60
64M		4.35 / 4.23 / 4.80

So the ~3-4x speedup holds on AMD too, matching your RTX 5080 / M1 / Intel numbers. (Aside: the vendor AMDGPU.jl findall hard-crashes at >=16M on this card while ours runs clean.)

On restoring the old approach as a second algorithm: I'd rather not - it's slower on every backend and reads more bytes, so there's no case where it wins. I'd keep the FindallAlgorithm abstraction but save the second slot for the single-pass decoupled-lookback variant (the CUB DeviceSelect path that's the remaining ~1.5x gap), now buildable since the DL device fence merged.