#!../_build/trust --run -Wsigil=ignore -Wembed=ignore --stack-check=explicit # # Recursive primality test with stack overflow protection and # a performance comparison between standard and protected implementations. # # Works with arbitrary-precision integers (BigInteger); the initial number # can far exceed the limits of an Int64. # # If free space runs low (i.e., *before* an actual stack overflow and crash occurs), # a standard software exception is thrown and caught via a try { ... } catch(_){ ... } block. # Native function for measuring execution speed @forward %clock():Int64; # Helper functions @func parse_i64(s:StrChar):Int64 { try { {% return (int64_t)std::stoll(c_s); %}; } catch(:StdException) { return -1; }; return -1; }; @func parse_bigint(s:StrChar):BigInteger { try { {% return trust::BigInteger(c_s); %}; } catch(:StdException) { return :BigInteger(-1); }; return :BigInteger(-1); }; # Recursion depth and call count counters currentDepth:Int64 := 0; maxDepth:Int64 := 0; callCount:Int64 := 0; # Macro to define a function for the recursive primality test @@ primeFn $fname @@ @func @$fname(n:BigInteger, divisor:BigInteger):Bool { callCount = callCount + 1; currentDepth = currentDepth + 1; if (currentDepth > maxDepth) { maxDepth = currentDepth; }; if (n < 2) { currentDepth = currentDepth - 1; @return false; }; if (divisor > n / divisor) { currentDepth = currentDepth - 1; @return true; }; if ((n / divisor) * divisor == n) { currentDepth = currentDepth - 1; @return false; }; $r := @$fname(n, divisor + 1); currentDepth = currentDepth - 1; return $r; }; @@@@; # Function without stack overflow checking @primeFn isPrime; # Function with stack overflow protection @[ stack_check @] @primeFn isPrimeSafe; @main(argv^:Dict, args^:Dict) := { if (:Int32({% $argv.size() %}) < 2) { @print('Usage: prime \n'); @print(' - start number (>= 2), BigInteger\n'); @print(' - how many primes to find (> 0)\n'); @return 1; }; $start := parse_bigint(:StrChar(argv[0])); $count := parse_i64(:StrChar(argv[1])); if ($start < 2) { @print('Error: invalid : "{}" (expected integer >= 2)\n', argv[0]); return 1; }; if ($count < 1) { @print('Error: invalid : "{}" (expected integer > 0)\n', argv[1]); return 1; }; @print('Searching for {} primes starting from {}:\n', $count, $start); # The first call to the protected function checks whether the stack size is sufficient for the entire call depth. callCount = 0; maxDepth = 0; currentDepth = 0; $t0 := %clock(); try_error { $n := $start; $found := 0; while ($found < $count) { if (isPrimeSafe($n, 2)) { @print(' prime: {}\n', $n); $found += 1; }; $n += 1; }; # Copy the statistics of the protected version into local variables. $t1 := %clock(); $safeMax := maxDepth; $safeCalls := callCount; } catch(_) { # Handling any exception (in this case, a stack overflow) @print('safe: STACK OVERFLOW caught at max depth={}, calls={}\n', maxDepth, callCount); @print('safe: time until overflow = {} ticks\n', %clock() - $t0); @return 0; } else { @print('safe: completed, max depth={}, calls={}, time={} ticks\n', $safeMax, $safeCalls, $t1 - $t0); # The UNPROTECTED version executes only if the function with stack overflow protection has completed successfully. callCount = 0; maxDepth = 0; currentDepth = 0; $t2 := %clock(); $n2 := $start; $found2 := 0; while ($found2 < $count) { if (isPrime($n2, 2)) { @print(' prime: {}\n', $n2); $found2 += 1; }; $n2 += 1; }; $t3 := %clock(); $unprotMax := maxDepth; $unprotCalls := callCount; @print('unprotected: completed, max depth={}, calls={}, time={} ticks\n', $unprotMax, $unprotCalls, $t3 - $t2); $du := $t3 - $t2; if ($du > 0) { @print('difference: protected is {:.2f}% slower\n',1000.0*($t1 - $t0 - $du) / (10 * $du)); }; return 0; }; }