Why shifting is slower than powering on old haskell !? How to make it faster?
When first searched where my code is slow I'm really surprised, not expected this, that powering (or multiplication) can be faster, so something in the shift code is really slow.
code for (integer) powering
{-# OPTIONS_GHC -O2 #-}
import System.Environment(getArgs)
main = do
[a,b] <- getArgs
let c = ( read a::Integer ) ^ ( read b::Int )
print ( mod c 2 )
sample code for shifting
{-# OPTIONS_GHC -O2 #-}
import Data.Bits
import System.Environment(getArgs)
main = do
[a,b] <- getArgs
let c = shift ( read a::Integer ) ( read b::Int )
print( mod c 2 )
and my runs on old and on newest haskell:
c:ghcghc-6.10.4bin>cmd /v:on /c "echo !TIME! & pow.exe 33 40000000 & echo !TIME!"
1:24:29,02
1
1:24:41,48
-- 12.46 sec. for powering
c:ghcghc-6.10.4bin>cmd /v:on /c "echo !TIME! & shift.exe 3 200000000 & echo !TIME!"
1:27:08,76
0
1:27:22,06
-- 13.30 sec. for shift
c:ghcghc-7.6.3bin>cmd /v:on /c "echo !TIME! & pow.exe 33 40000000 & echo !TIME!"
2:19:29,39
1
2:19:37,06
-- 7.67 sec. for powering (so powering is improved a little)
c:ghcghc-7.6.3bin>cmd /v:on /c "echo !TIME! & shift.exe 3 200000000 & echo !TIME!"
2:20:49,61
0
2:20:49,69
-- 0.08 sec. for shifting (that means a speedup by a factor of roughly 150)
or even (here 2 billion bits shift):
c:ghcghc-7.6.3bin>cmd /v:on /c "echo !TIME! & shift.exe 3 2000000000 & echo !TIME!"
3:07:22,05
0
3:07:22,56
-- 0.51 sec.
In runs the numbers are quite big to see a long running time. In the first code we calculate 33^40000000 (mod 2), in the second code 3*2^200000000 (mod 2). The mod operation (or something else) must have to see a not 0 time (as haskell wouldn't compute it in that case). And as said the powering was faster, and note also that in that case 33^40000000 is bigger than 3*2^200000000. Furthermore on memory usage you can see that 3^200000000 is computed on the newest haskell also, so there is no deep optimization trick here.
Would it be possible to get a speedup in this old haskell version? I'm interested in shifting (big integers) in both direction, and we can assume that we shift with a multiple of 64 bits (or 63 or 32 or 31; the size of the word in the integer representation on haskell), so there is no wrap around.
Tried to compute 2^n then perform multiplication (or division) to do shift, but it didn't give speedup on the old haskell.
UPDATE
running the compiler with -v flag begins the print with: (i can post the rest ones also) Glasgow Haskell Compiler, Version 6.10.4, for Haskell 98, stage 2 booted by GHC version 6.10.1 Using package config file: C:ghcghc-6.10.4package.conf hiding package base-3.0.3.1 to avoid conflict with later version base-4.1.0.0 wired-in package ghc-prim mapped to ghc-prim-0.1.0.0 wired-in package integer mapped to integer-0.1.0.1 wired-in package base mapped to base-4.1.0.0 wired-in package rts mapped to rts-1.0 wired-in package haskell98 mapped to haskell98-1.0.1.0 wired-in package syb mapped to syb-0.1.0.1 wired-in package template-haskell mapped to template-haskell-2.3.0.1 wired-in package dph-seq mapped to dph-seq-0.3 wired-in package dph-par mapped to dph-par-0.3 Hsc static flags: -static
My guess is that the older version of GHC doesn't have specialized implementations for Integer shifts and thus falls back to the default Haskell implementation, see Data.Bits :
shift x i | i >= 0 = x * 2^i
| otherwise = x `div` 2^(-i)
Current version, however, has GMP-based primops for both left and right shifts, see shiftLInteger and shiftRInteger functions in GHC.Integer.Type module from integer-gmp package.
上一篇: 迁移EJB2.x BMP实体bean