Fastest way to simulate the birthday paradox

General Usage Performance
3

The GPU version can reach a scary 2ms on my RTX2080 (no Ti)

BenchmarkTools.Trial:
  memory estimate:  1.28 KiB
  allocs estimate:  42
  --------------
  minimum time:     1.813 ms (0.00% GC)
  median time:      1.930 ms (0.00% GC)
  mean time:        76.165 ms (0.04% GC)
  maximum time:     304.536 ms (0.00% GC)
  --------------
  samples:          66
  evals/sample:     1

Code

# Birtyday paradox

using Pkg

Pkg.activate("c:/scratch/cuda-test")

using CUDA

CUDA.allowscalar(false)

N = 1_000_000

# The winner of bencharmks/bencharmks-countmap

function atleast2_gpu_v1!(b, e)

    i = (blockIdx().x - 1) * blockDim().x + threadIdx().x

    stride = gridDim().x * blockDim().x

    t = threadIdx().x

    j = Float32(0.0)

    for idx in i:stride:size(e, 2)

        local_j = Float32(0.0)

        for k in 1:23-1

            if e[k, idx] < k/365

                local_j = max(local_j, Float32(1.0))

            end

        end

        j += local_j

    end

    @atomic b[t] = b[t] + j

    return

end

function simulate_bday_gpu_v1(; threads = 256, blocks = N ÷ 256)

    b = CUDA.zeros(Float32, threads)

    r = CUDA.rand(Float32, 23-1, N)

    CUDA.@sync @cuda threads = threads blocks = blocks atleast2_gpu_v1!(b, r)

    sum(b)/1_000_000

end

using BenchmarkTools

@benchmark CUDA.@sync blocking = false simulate_bday_gpu_v1()