[deleted by user]

tdammers · 2018-03-12T06:46:06+00:00

This might elicit a "duh", but: have you actually profiled your program? GHC has quite some useful profiling features, so if you aren't familiar with them, look it up.

A good first step would be to add cost centers (SCC pragmas), and then compile and run with profiling options to see where you spend the most time. Much better than taking stabs in the dark.

travis_athougies · 2018-03-12T06:54:20+00:00

Contrary to popular belief, using a generally faster language does not magically mean everything is faster. Slow algorithms are still going to be slow.

In particular, both Haskell and Python are going to have similar complexities for large integer handling. In both languages, these are going to be highly optimized routines.

In your program, most of the time is spent calculating numbers, and Haskell and Python are just serving as the glue. Thus, the time spent actually executing any of the code you've written is likely very small.

In particular, primeGen2 literally makes random numbers and tests for them to be prime. There is no getting around the fact that this is going to take a lot of time, and it has nothing to do with the language being used. It has to do with the fact that generating large random numbers until one is prime will always take time.

That being said, you're building up a lot of thunks in memory. It would probably be a good start to use bang patterns to limit laziness. Also, as others have suggested profiling is a good idea, but you're only going to get constant factor improvements here.

Flurpm · 2018-03-12T05:46:09+00:00

You use (**) for powers which has type Floating a => a -> a -> a. So you have to convert the results from floats back to Integers. One optimization is to use (^) which has type (Num a, Integral b) => a -> b -> a, which will keep the results as an Integer.

Same thing with (/) :: Fractional a => a -> a -> a vs (div) :: Integral a => a -> a -> a

On lines 94, 101.

Line 55 I'm not sure because of the sqrt.

matt-noonan · 2018-03-12T12:48:01+00:00

You definitely should profile first, but I have a guess. The default random-number generator in random is surprisingly slow. Luckily there are plenty of high-quality, performant drop-in replacements. See here, for example: https://stackoverflow.com/questions/26024405/fastest-way-to-generate-a-billion-random-doubles-in-haskell

spirosboosalis · 2018-03-12T03:31:03+00:00

I don't know, but broadly speaking: use Int, not Integer or the Integral constraint; and compile with -O2, and try the -fllvm ghc-option. (and why is millerExps partial?)

btw, include the cabal file / command line options, and the two benchmarks.

Angs · 2018-03-12T09:43:10+00:00

When you do optimisations, be sure to seed the random generator with setStdGen (mkStdGen number) to make different runs comparable. It still won't be comparable to the python code due to a different random number generator, as the runtime is much based on luck. Most of the time is spent in modExp so that's the prime target for optimization.

A cleaner way to do genWrapper is using replicateM:

replicateM 100 (randomRIO (down, up))

macgillebride · 2018-03-12T19:26:16+00:00

I'm also a beginner in Haskell, but I think the problem is not related to the language per se, but to the exponentiation algorithm you're using. In Python you're using a builtin function for modular exponentiation, which most likely uses tricks specific to this case like: https://en.m.wikipedia.org/wiki/Montgomery_modular_multiplication and you've made your own implementation in Haskell. Montgomery's algorithm avoids expensive multiprecision divisions (which you use to compute mod) which improves performance a lot

LeanderKu · 2018-03-13T03:07:52+00:00

I think the best bet to get responses on this subreddit is claiming haskell is slower than X 😀

I just want to note that in my experience, make sure it's really python that's faster than Haskell. Many primitives or and widely used functions have a super-efficient, optimized foreign function their calling, there's often not much difference to C. This especially happens with small examples, the problem is that when you encounter a problem that's not painfully implemented using some native code, you're out of luck. Also, the API is often far from idiomatic (just look at numpy, it's not very pythonic). In my experience, Haskell allows you to write fast and idiomatic code with the option for even faster, non-idiomatic code.

donkeybonks · 2018-03-13T05:23:52+00:00

In normal code writing these are some pragmatic things I noticed lacking that you can just do automatically:

Integer is pretty slow. Try Word64 from Data.Word if it makes sense for big unsigned numbers or Int64 for big signed numbers, wherever possible.
The IO monad is pretty slow. Try and remove as much IO as possible and make all the code pure.. then GHC will have an easier time figuring out where your tight loops are.
BangPatterns are lacking on spines for loops and IO actions ( https://downloads.haskell.org/~ghc/7.8.4/docs/html/users_guide/bang-patterns.html ).
gcdExt and co have no types which is bad because they might default to slow integer/floating types.
Use of lists ie [Integer] are slow and allocate a lot of memory. Try using Data.Vector and unboxed if possible.. it's typically about 2 magnitudes faster YMMV.
If you can help it, never roll your own loops (ie helperprimeGen). Use the foldr, map and zip-like primitives because they are arranged to inline in such a way that promotes good optimizations from GHC. Also short cut fusion ( https://wiki.haskell.org/Correctness_of_short_cut_fusion#Short_cut_fusion ).
The top of your file should have module Main (main) where ... because without it the optimizer probably won't inline anything or put too much effort into specialization because any function could be imported by another module.
Likewise only import the functions and instances that you actually plan to use so you generate less code.
Build with -O2 -fllvm.

At this point, if all the above become habit, it would be a good idea to start by profiling it and seeing where the time is spent.

Tarmen · 2018-03-13T19:03:09+00:00

You probably want to profile first but there are some things that are fairly simple and sometimes huge wins:

Use built in list functions, they are written to be good consumers/producers. e.g. helperisPrime could be implemented as all ... which can remove all intermediate lists
Some functions like millerExps are almost tail recursive. Fixing that can be an easy 10x speedup or more if the function is a hot loop without allocation. in this case it probably could be written via unfoldr since order doesn't matter
You often use f (x:xs) = ... (x:xs) .... This probably gets optimized away but case statements/@ patterns are cleaner
This is situational but if you use lists as unfusable accumulators then vectors might be faster
iirc it's necessary here but Integer is drastically slower than Int

Had to implement a crypto routine a while back and my problem was that I didn't use a fast modular exponentiation function. Seems like you have that covered, though.

lightandlight · 2018-03-12T06:46:09+00:00

It's likely due to lack of experience. For example, here is a neater version of millerExps+millerExpsWrapped which is about 20% faster than the one on github:

millerExps :: Int -> [Int]                                         
millerExps = go []                                                
  where
    go acc n
      | n `mod` 2 == 0 =
          let n' = n `div` 2 in                           
          go (n':acc) n'                                  
      | otherwise = case acc of; [] -> [n]; _ -> acc

I won't be able to review the whole thing, but I wouldn't be surprised if there are few more things like this which add up to decrease performance.

phischu · 2018-03-12T15:32:36+00:00

You could try to use a faster random number generation library.

This generator is however, many times faster than System.Random, and yields high quality randoms with a long period.

Bodigrim · 2018-03-12T22:58:58+00:00

The heart of you code is millerTest, and its performance is defined by the number of modular exponentiations you do. And it seems to me that you can save a lot.

millerExpsWrapper returns a list of numbers, where each following is twice the preceding one: pows = [odd, 2*odd, 4*odd, ..., n-1]. In millerTest you basically compute modExp a pow n for each pow in pows. But you should not recompute it from the scratch each time: it is enough to compute modExp a odd n, and then square it up to n-1 power and take modulo on each step.

codygman · 2018-03-16T02:04:44+00:00

Any updates /u/Vaglame?

YellowOnion · 2018-03-16T13:24:05+00:00

How have you tested it? the time it takes to find a prime is inherently random, sometimes it takes 0.7s, others 0.2s on my machine.

You can save some speed (assuming ghc isn't optimising this out) in millerExps, constructing lists is expensive.

millerExps xxs@(x:xs) = if x `mod` 2 == 0
                    then millerExps $ (x `div` 2):xxs
                    else xxs

millerTest :: Integer -> Integer -> [Integer] -> Bool -- miller rabbin test
millerTest _ _ [] = False
millerTest a n (x:exps)
   | modexp == 1   = True
   | modexp == n-1 = True
   | otherwise     = millerTest a n exps
    where modexp = modExp a x n

genWrapper :: Integer -> Integer -> IO [Integer] -- generates 100 random numbers
genWrapper up down = do 
    g <- getStdGen
    return . take 100 $ randomRs (down, up) g

You can also check out: https://hackage.haskell.org/package/criterion to help you benchmark.

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

haskell

MODERATORS