A Friendly Challenge for D

[Jabari Zakiya]

On Thursday, 8 November 2018 at 18:49:35 UTC, Bastiaan Veelo 
wrote:
> Hi Jabari,
>
> On Wednesday, 7 November 2018 at 20:30:33 UTC, Jabari Zakiya 
> wrote:
>> Hey Vijay I got a complete D version running correctly.
>>
>> https://gist.github.com/jzakiya/ae93bfa03dbc8b25ccc7f97ff8ad0f61
>
> I cloned this and enabled P17 for you, get it at 
> https://github.com/veelo/twinprimes_ssoz
>
> I basically optimized the compile time table generation by 
> removing templates and avoiding reallocations. This is a big 
> deal because currently the compiler will not collect its own 
> garbage. You'll see that I reserve exactly the minimum array 
> lengths; of course I didn't know these when I started, I got it 
> to work just by preallocating for up to P13 and using appender 
> for P17. But since I now know the exact required length, I can 
> just as well use it. My system has 16GB of RAM, which is enough.
>
> [...]
>> 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).
>
> There is https://dlang.org/phobos/std_bitmanip.html#BitArray
>
> I haven't looked at the run-time code, it is very well possible 
> that similar optimizations are possible there too.

Hi Bastiaan,

Good work on the code.

I've been playing with it, and made versions using boolean and 
bitarrays for seg array. Byte arrays are definitely faster, with 
bools slightly slower, but bitarrays way slower, by at least 2x.

I also had made a slight modification to twin_sieve, at its end, 
to speed it up a smidgen. I didn't know if you want PRs to your 
code.

However, there is a problem in the code when using P17. It 
generates incorrect results > 15 trillion (when P17 is selected). 
For 20 trillion (20_000_000_000_000) it gives 37,593,079,058 
instead of 30,198,862,775 for the twins count, and the last twin 
value is off too.This likely means the P17 parameters are off, 
and/or nextp values, as not enough of the k values in twins_sieve 
are marking off prime multiples in the seg array.

However for P5-P13 the results are correct, and the performance 
is comparable to the Nim version, up to N = 5 billion, where you 
start to see D be slower (by a few percent). You can run both on 
your system to see what the difference is on it.

Anyway, if you figure out what's up with P17 that we can get it 
totally working, and I'll look at playing around with it to.

I'm over 90% finished with my paper now (want to finish b4 
Thanksgiving).