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
>>
>> Could you list your hardware, D ver, compiler specs.
>>
>> I will run your code on my system with your D version and 
>> compiler, if I can.
>>
>> Excellent work!
>
> D has multiple compilers, but for the speed of the finished 
> binary, LDC2 is generally recommended.  I used version 1.11.0.  
> https://github.com/ldc-developers/ldc/releases/tag/v1.11.0
>
> I was using DUB to manage the project, but to build the 
> stand-alone file from the gist link, use this command:  $ ldc2 
> -release -O3 twinprimes_ssoz.d
> And to run it:  $ echo "3000000000" | ./twinprimes_ssoz
>
> Running the program a bunch of times, I get variable results, 
> mostly between 195ms and 250ms.  Running the Nim version, I 
> also get variable results, mostly between 230ms and 280ms.
>
> My system is an Alienware 14x R2 from 2012.  Specs can be found 
> here: 
> https://www.cnet.com/products/alienware-m14xr2-14-core-i7-3630qm-8-gb-ram-750-gb-hdd/specs/

Hey Vijay I got a complete D version running correctly.

https://gist.github.com/jzakiya/ae93bfa03dbc8b25ccc7f97ff8ad0f61

Here's the Nim code for comparison.

https://gist.github.com/jzakiya/6c7e1868bd749a6b1add62e3e3b2341e

I'm about 80-85% finished writing my paper. It's interesting the 
things you learn about a topic if you try to write about it. :-)  
When I finish I'll post it here, and everything will become a 
whole lot clearer about what|why|how the algorithm|code works.

I found a few edge case bugs in the original code I posted, but 
also found some coding and performance improvements too. The D 
(and revised Nim) code reflects all these changes, and are the 
current state-of-the-art regarding this implementation.

One thing that could|should make it faster is the use of fast 
bitarrays to create the seg arrays in the threads (vs byte 
arrays). I didn't find anywhere that D has a native bitarray 
structure (Nim doesn't either).

Please don't be too offset by my coding style. I tried to mimick 
the Nim style (which is non-standard too).  I code to minimize 
the syntax noise, and like complete concepts on one line.

Performance is "similar" to Nim's, though Nim is slightly faster 
as N increases. Both are still faster than primesieve however. 
Still hoping someone does a GPU version.

Please compile on the different Nim compilers and see what 
differences they produce.

And last, the D version doesn't us P17, as in the Nim version, 
because of the issue you found with the D compiler when trying to 
compile with P17. If you have time maybe you (someone) can try to 
resolve that issue, to match its functionality to the Nim version.