Retired Microsoft Engineer Dave Plummer is doing a software drag race on his youtube channel comparing execution time of various languages(github page here: https://github.com/PlummersSoftwareLLC/Primes). The test algorithm is a simple Prime Number sieve. I’ve written a Racket version that follows his initial C++ implementation here: https://github.com/jjsimpso/misc-racket/blob/master/sieve.rkt. I’m sure someone can improve on my version. It would be nice to get a Racket implementation in the drag race!
Nice job!
I am unsure whether or not (sqrt up-bound) can be made faster with (sqrt (exact->inexact up-bound)). If the input is an exact integer, then sqrt makes an effort to return the exact square root, in case the input is a square number.
Hmm. Since that computation is only done once, it won’t change much.
I see that the byte vector also contains the even numbers. Is that part of Dave’s version of the sieve? (Making the even entries implicit would cut space in half).
Thanks for taking a look! The versions that I’ve looked at include the even numbers. One advantage the C++ version has is that it uses a single bit per number, instead of a whole byte. If someone had an efficient implementation of bit vectors for racket that would help a lot.
The test results are divided so that the ‘faithful’ implementations can be separated from the non-faithful. So people have been submitting some crazy stuff that doesn’t actually qualify for the ‘official’ test.
The one in data/bitvector is restricted to using 30 (I think) bits per fixnum, since it needs to work unchanged on both 32 and 64 bits machines.
Maybe pmatos’s bitvectors are faster?
But I wouldn’t be surprised if it turns out you byte vectors turns out to be faster.
If tricks are allowed, there is a nice trick where a single u16 represents a block of 60 numbers. https://github.com/racket/math/blob/master/math-lib/math/private/number-theory/small-primes.rkt
But I think that sieve is optimized for space rather than speed.
I tried data/bit-vector and it was significantly slower than just vectors. bv isn’t an easy replacement for what I have but might be worth looking at.
Maybe if I was using Typed Racket data/bit-vector would be faster? Is data/bit-vector Typed Racket?
A separate Typed Racket implementation would be nice to have and a good advertisement for Racket itself.
I had to check, but no data/bit-vector uses plain racket. https://github.com/racket/racket/blob/master/racket/collects/data/bit-vector.rkt
Still, unsafe-bytes-ref and unsafe-bit-vector-set! are fast, so I think you version will beat a version using bit vectors.
An obligatory and enlightening read, which I was reminded of when I almost suggested comparing with a streaming implementation: https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf\|https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
If I have a .zo file (for Racket CS), is there a way to check for which platform/arch it was compiled?
I think the simple answer is “no”.
A more complicated is “no published way”, but I’m not sure how much would be easy to expose. Currently, raco make and similar do not try to read the “.zo”, but get version and platform information from the adjacent “.dep” file. A public interface to “.dep” information would certainly be possible.
Very interesting. I don’t really know Haskell, so the code is hard to parse, but I’ll give this a read.
I was curious if it’s possible because I was debugging a problem today and wondered if knowing the platform in the zo file would help with debugging. Apart from that, at the moment I wouldn’t need an API.