sozpg

bench.cr

def mark_nonprimes(residues, val, md)
  bitn = [0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 4, 0, 0, 0, 8, 0, 16, 0, 0, 0, 32, 0, 0, 0, 0, 0, 64, 0, 128]
  kmax = (val - 2) // md + 1
  nonprimes = Array(UInt8).new(kmax, 0)

  breakpoint = Math.isqrt(val)
  nonprimes.each_with_index do |resgroup, k|
    residues.each_with_index do |prime_residue, i|
      next if resgroup & (1 << i) != 0
      prime = md * k + prime_residue
      return nonprimes if prime > breakpoint
      residues.each do |ri|
        kn, rn = (prime_residue * ri - 2).divmod(md)
        prime_multiple = k * (prime + ri) + kn
        while prime_multiple < kmax
          nonprimes[prime_multiple] |= bitn[rn]
          prime_multiple += prime
        end
      end
    end
  end
  raise "Unreachable"
end

def sozpg_meth(val)
  md, rscnt = 30u64, 8
  res = [7, 11, 13, 17, 19, 23, 29, 31]

  nonprimes = mark_nonprimes(res, val, md)

  primes = [2, 3, 5] of UInt64

  nonprimes.each_with_index do |resgroup, k|
    res.each_with_index do |r_i, i|
      primes << md * k + r_i if resgroup & (1 << i) == 0
    end
  end

  primes
end

def sozpg(val)
  md, rscnt = 30u64, 8

  res = [7, 11, 13, 17, 19, 23, 29, 31]

  bitn = [0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 4, 0, 0, 0, 8, 0, 16, 0, 0, 0, 32, 0, 0, 0, 0, 0, 64, 0, 128]

  kmax = (val - 2) // md + 1

  prms = Array(UInt8).new(kmax, 0)

  func = ->{
    prms.each_with_index do |resgroup, k|
      res.each_with_index do |prm_r, i|
        next if resgroup & (1 << i) != 0

        prime = md * k + prm_r

        return if prime > Math.isqrt(val)

        res.each do |ri|
          kn, rn = (prm_r * ri - 2).divmod md

          kpm = k * (prime + ri) + kn

          while kpm < kmax
            prms[kpm] |= bitn[rn]; kpm += prime
          end
        end
      end
    end
  }

  func.call

  primes = [2, 3, 5] of UInt64

  prms.each_with_index do |resgroup, k|
    res.each_with_index do |r_i, i|
      primes << md * k + r_i if resgroup & (1 << i) == 0
    end
  end

  primes
end

class Break < Exception
  getter symbol : Symbol

  def initialize(@symbol : Symbol)
  end
end

def catch(symbol : Symbol)
  begin
    yield
  rescue e : Break
    unless e.symbol == symbol
      raise e
    end
  end
end

def throw(symbol : Symbol)
  exception = Break.new(symbol)

  unwind_ex = Pointer(LibUnwind::Exception).malloc

  unwind_ex.value.exception_class = LibC::SizeT.zero

  unwind_ex.value.exception_cleanup = LibC::SizeT.zero

  unwind_ex.value.exception_object = exception.as(Void*)

  unwind_ex.value.exception_type_id = exception.crystal_type_id

  __crystal_raise(unwind_ex)
end

def sozpg_throw(val)
  md, rscnt = 30u64, 8

  res = [7, 11, 13, 17, 19, 23, 29, 31]

  bitn = [0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 4, 0, 0, 0, 8, 0, 16, 0, 0, 0, 32, 0, 0, 0, 0, 0, 64, 0, 128]

  kmax = (val - 2) // md + 1

  prms = Array(UInt8).new(kmax, 0)

  catch(:here) do
    prms.each_with_index do |resgroup, k|
      res.each_with_index do |prm_r, i|
        next if resgroup & (1 << i) != 0

        prime = md * k + prm_r

        throw :here if prime > Math.isqrt(val)

        res.each do |ri|
          kn, rn = (prm_r * ri - 2).divmod md

          kpm = k * (prime + ri) + kn

          while kpm < kmax
            prms[kpm] |= bitn[rn]; kpm += prime
          end
        end
      end
    end
  end

  primes = [2, 3, 5] of UInt64

  prms.each_with_index do |resgroup, k|
    res.each_with_index do |r_i, i|
      primes << md * k + r_i if resgroup & (1 << i) == 0
    end
  end

  primes
end

Benchmark.ips do |x|
  x.report("throw/catch") do
    sozpg_throw(541)
  end

  x.report("return") do
    sozpg(541)
  end

  x.report("meth") do
    sozpg_meth(541)
  end
end