A Friendly Challenge for D

[Jabari Zakiya]

On Tuesday, 16 October 2018 at 07:09:05 UTC, Vijay Nayar wrote:
> On Monday, 15 October 2018 at 22:17:57 UTC, Jabari Zakiya wrote:
>>> $ dub build --compiler=ldc2 -b=release && echo "3000000000" | 
>>> ./twinprimes
>>> Enter integer number:
>>> threads = 8
>>> each thread segment is [1 x 65536] bytes array
>>> twinprime candidates = 175324676; resgroups = 1298702
>>> each 135 threads has nextp[2 x 5566] array
>>> setup time = 1 ms, 864 μs, and 7 hnsecs
>>> perform twinprimes ssoz sieve
>>> sieve time = 196 ms, 566 μs, and 5 hnsecs
>>> last segment = 53518 resgroups; segment slices = 20
>>> total twins = 9210144; last twin = 2999999712+/- 1
>>> total time = 198 ms, 431 μs, and 2 hnsecs
>>>
>>> My understanding is that the difference in performance is 
>>> largely due to slightly better optimization from the LLVM 
>>> based ldc2 compiler, where I believe Nim is using gcc.
>>
>> Here's what I get on my system.
>>
>> $ echo 3_000_000_000 | ./twinprimes_test7yc.0180.gcc821
>> Enter integer number: threads = 8
>> each thread segment is [1 x 65536] bytes array
>> twinprime candidates = 175324676; resgroups = 1298702
>> each 135 threads has nextp[2 x 5566] array
>> setup time = 0.000 secs
>> perform twinprimes ssoz sieve
>> sieve time = 0.144 secs
>> last segment = 53518 resgroups; segment slices = 20
>> total twins = 9210144; last twin = 2999999712+/-1
>> total time = 0.144 secs

Hey Vijay I found subtle static typing errors.

When N < 2^32 - 1 (4,294,967,295) the twimprime count and 
lastprime values are correct.
When N > 2^32 - 1 both values start to be incorrect.

Examples: For N = 4,000,000,000 you get correct answers

$ echo 4000000000 | ./twinprimes_ssoz
Enter integer number:
threads = 8
each thread segment is [1 x 65536] bytes array
twinprime candidates = 233766231; resgroups = 1731602
each 135 threads has nextp[2 x 6332] array
setup time = 667 μs and 5 hnsecs
perform twinprimes ssoz sieve
sieve time = 181 ms, 277 μs, and 6 hnsecs
last segment = 27666 resgroups; segment slices = 27
total twins = 11944438; last twin = 3999999798+/- 1
total time = 181 ms, 945 μs, and 1 hnsec

Examples: For N = 5,000,000,000 you get wrong answers

$ echo 5000000000 | ./twinprimes_ssoz
Enter integer number:
threads = 8
each thread segment is [1 x 65536] bytes array
twinprime candidates = 292207792; resgroups = 2164503
each 135 threads has nextp[2 x 6999] array
setup time = 744 μs and 7 hnsecs
perform twinprimes ssoz sieve
sieve time = 225 ms, 323 μs, and 4 hnsecs
last segment = 1815 resgroups; segment slices = 34
total twins = 14618173; last twin = 705034592+/- 1
total time = 226 ms, 68 μs, and 1 hnse

These are correct answers for N = 5,000,000,000

$ echo 5000000000 | ./twinprimes_test7yc.0180.gcc821
Enter integer number: threads = 8
each thread segment is [1 x 65536] bytes array
twinprime candidates = 292207792; resgroups = 2164503
each 135 threads has nextp[2 x 6999] array
setup time = 0.001 secs
perform twinprimes ssoz sieve
sieve time = 0.237 secs
last segment = 1815 resgroups; segment slices = 34
total twins = 14618166; last twin = 4999999860+/-1
total time = 0.237 secs

The first easy check should show the lastprime value just a 
little smaller than N.
See the timing|results table I posted earlier to see correct 
outputs as N gets bigger.

It took me a looong time, and was a big PITA, to get the correct 
static typing too in Nim, especially coming from a dynamic 
language like Ruby.