Re: [Haskell-cafe] memorize function with number parameterized types in GHC
Hi, Oleg Thanks for your time and your brilliant code. I think this problem is solved. Best wishes to you Regards Bin On Wed, Nov 9, 2011 at 2:05 PM, o...@okmij.org wrote: p2num :: Dep a b ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] memorize function with number parameterized types in GHC
Hi,
Thanks for your reply!
I made some changes according to your suggest. Now I get rid of
argument p. Unfortunately, GHC is not smart enough to memorize
this true polymorphic constant.
Can you give some hints on what kind of specialize pragmas I should
use?
Regards,
Bin Jin
On Tue, Nov 8, 2011 at 2:35 PM, o...@okmij.org wrote:
Bin Jin wrote:
Here is a function that will be called everytime by `(*)` in `Num`
typeclass
montgKeys :: (PostiveN p, Integral a, Bits a) = p - a
as you can imagine, I always pass (undefined :: p) as parameter to
`montgKeys`, so if it's handled well, it should be memorized for
future usage. But tracing shows that both `p2num` and `montgKeys` are
evaluated every time being called.
First of all, let us get rid of the argument p. Let's define
newtype W p a = W{unW:: a}
then we can easily re-write montgKeys to give it the following signature:
montgKeys :: (PostiveN p, Integral a, Bits a) = W p a
You can use ScopedTypevariables to set the needed 'p' from the context.
So, montgKeys becomes a polymorphic constant, quite like minBound.
Now, the hope is that when the types p and a are determined, GHC could
specialize montgKeys and turn it into a real constant. Perhaps some
RULE or specialize pragmas may help...
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] memorize function with number parameterized types in GHC
It seems GHC can be pursuaded to do proper specialization and
memoization. We can see that, first, using trace:
class (Ord b, Integral b, Num b, Bits b) = PositiveN a b where
p2num :: Dep a b
instance (Ord b, Integral b, Num b, Bits b) = PositiveN One b where
p2num = trace p2num 1 $ Dep 1
If we define
:: PositiveN p Int = ModP2 p Int - ModP2 p Int
x = x * x * x * x
:: PositiveN p Int = ModP2 p Int - ModP2 p Int
x = x + x + x + x
test2 = x + x
where x = 1 :: ModP2 (D1 One) Int
and run test2 in GHCi, we see
*Math.Montg test2
p2num 1
1+p2num 1
4Z
That is, p2num was invoked only twice; I guess one invocation is for
converting 1 to a modular number, and the other invocation was used
for all 4 additions and 3 multiplications, distributed across
multiple functions.
Looking at the core is a better test:
ghc -O2 -c -ddump-prep Montg.hs
Math.Montg.test2
:: Math.Montg.ModP2 (Math.Montg.D1 Math.Montg.One) GHC.Types.Int
[GblId, Str=DmdType]
Math.Montg.test2 =
case Math.Montg.test14 of _ { GHC.Types.I# ww_s1Ww -
case Math.Montg.$w$s ww_s1Ww of ww1_s1WB { __DEFAULT -
case Math.Montg.$w$s ww_s1Ww of ww2_s1WC { __DEFAULT -
case Math.Montg.$fNumModP2_$spmask
`cast` (Math.Montg.NTCo:Dep
(Math.Montg.D1 Math.Montg.One) GHC.Types.Int
:: Math.Montg.Dep (Math.Montg.D1 Math.Montg.One) GHC.Types.Int
~
GHC.Types.Int)
of _ { GHC.Types.I# y#_s1WF -
case GHC.Prim.int2Word# y#_s1WF of sat_s2m8 { __DEFAULT -
case GHC.Prim.+# ww1_s1WB ww2_s1WC of sat_s2m9 { __DEFAULT -
case GHC.Prim.int2Word# sat_s2m9 of sat_s2ma { __DEFAULT -
case GHC.Prim.and# sat_s2ma sat_s2m8 of sat_s2mb { __DEFAULT -
case GHC.Prim.word2Int# sat_s2mb of sat_s2mc { __DEFAULT -
(GHC.Types.I# sat_s2mc)
As you can see, the program used Math.Montg.$fNumModP2_$spmask.
Here is thus definition in core:
Math.Montg.$fNumModP2_$spmask
:: Math.Montg.Dep (Math.Montg.D1 Math.Montg.One) GHC.Types.Int
[GblId, Str=DmdType]
Math.Montg.$fNumModP2_$spmask =
case Math.Montg.$wbitLen
@ GHC.Types.Int
GHC.Base.$fEqInt
GHC.Num.$fNumInt_$cfromInteger
You only need to look at the type to see that GHC has specialized
pmask to the particular instance Dep (D1 One) Int -- just as we
wanted.
Here is the prefix of your code with my modifications
module Math.Montg where
import Data.Bits
import Debug.Trace
newtype Dep a b = Dep { unDep :: b }
data One = One
data D0 a = D0 a
data D1 a = D1 a
class (Ord b, Integral b, Num b, Bits b) = PositiveN a b where
p2num :: Dep a b
instance (Ord b, Integral b, Num b, Bits b) = PositiveN One b where
p2num = trace p2num 1 $ Dep 1
instance PositiveN p b = PositiveN (D0 p) b where
p2num = Dep (unDep (p2num :: Dep p b) * 2)
instance PositiveN p b = PositiveN (D1 p) b where
p2num = Dep (unDep (p2num :: Dep p b) * 2 + 1)
ctz :: (Num a, Bits a) = a - Int
ctz x | testBit x 0 = 0
| otherwise = ctz (x `shiftR` 1)
bitLen :: (Num a, Bits a) = a - Int
bitLen 0 = 0
bitLen x = bitLen (x `shiftR` 1) + 1
pmask :: forall p b. (PositiveN p b) = Dep p b
pmask | bitLen n == ctz n + 1 = Dep (bit (ctz n) - 1)
| otherwise = Dep (bit (bitLen n) - 1)
where
n = unDep (p2num :: Dep p b)
addmod2 :: forall p b. (PositiveN p b) = Dep p b - Dep p b - Dep p b
addmod2 (Dep a) (Dep b) = Dep ((a + b) .. unDep (pmask :: Dep p b))
{-# INLINE addmod2 #-}
submod2 :: forall p b. (PositiveN p b) = p - b - b - b
submod2 _ a b = (a - b) .. unDep (pmask :: Dep p b)
{-# INLINE submod2 #-}
mulmod2 :: forall p b. (PositiveN p b) = Dep p b - Dep p b - Dep p b
mulmod2 (Dep a) (Dep b) = Dep $ (a * b) .. unDep (pmask :: Dep p b)
{-# INLINE mulmod2 #-}
addmod :: forall p b. (PositiveN p b) = p - b - b - b
addmod _ a b | a + b = p = a + b - p
| otherwise = a + b
where
p = unDep (p2num :: Dep p b)
{-# INLINE addmod #-}
submod :: forall p b. (PositiveN p b) = p - b - b - b
submod _ a b | a b = a + unDep (p2num :: Dep p b) - b
| otherwise = a - b
{-# INLINE submod #-}
-- | extended euclidean algorithm
-- `extgcd a b` returns `(g, x, y)` s.t. `g = gcd a b` and `ax + by = g`
--
extgcd :: Integral a = a - a - (a, a, a)
extgcd a b | a 0 = let (g, x, y) = extgcd (-a) b in (g, -x, y)
extgcd a b | b 0 = let (g, x, y) = extgcd a (-b) in (g, x, -y)
extgcd a 0 = (a, 1, 0)
extgcd a b = let
(adivb, amodb) = a `divMod` b
(g, y, x) = extgcd b amodb
-- (a - a / b * b) * x + b * y
-- = a * x - a / b * b * x + b * y
-- = a * x + (y - a / b * x) * b
in
(g, x, y - adivb * x)
newtype PositiveN p a = ModP2 p a = ModP2 { unModP2 :: a } deriving Eq
instance PositiveN p a = Show (ModP2 p a) where
show (ModP2 r) = show r ++ + ++ show (unDep (pmask :: Dep p a) + 1) ++ Z
-- In principle, Dep and
Re: [Haskell-cafe] memorize function with number parameterized types in GHC
Bin Jin wrote:
Here is a function that will be called everytime by `(*)` in `Num` typeclass
montgKeys :: (PostiveN p, Integral a, Bits a) = p - a
as you can imagine, I always pass (undefined :: p) as parameter to
`montgKeys`, so if it's handled well, it should be memorized for
future usage. But tracing shows that both `p2num` and `montgKeys` are
evaluated every time being called.
First of all, let us get rid of the argument p. Let's define
newtype W p a = W{unW:: a}
then we can easily re-write montgKeys to give it the following signature:
montgKeys :: (PostiveN p, Integral a, Bits a) = W p a
You can use ScopedTypevariables to set the needed 'p' from the context.
So, montgKeys becomes a polymorphic constant, quite like minBound.
Now, the hope is that when the types p and a are determined, GHC could
specialize montgKeys and turn it into a real constant. Perhaps some
RULE or specialize pragmas may help...
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] memorize function with number parameterized types in GHC
Hi, everyone I'm recently trying to implement the Montgomery reduction algorithm[1] in Haskell, the code can be found on my Github page[2]. After doing some benchmark testing I found that the library works rather slow. With the help of `trace` function from Debug.Trace, I found that GHC is not magical enough to memorize values with the same type(well, it's actually dynamically generated number parameterized type). I used binary representation to handle all positive numbers in type system. data One = One data D0 a = D0 a data D1 a = D1 a class PostiveN a where p2num :: (Num b, Bits b) = a - b instance PostiveN One ... instance PostiveN a = PostiveN (D0 a) ... instance PostiveN a = PostiveN (D1 a) ... Here is a function that will be called everytime by `(*)` in `Num` typeclass montgKeys :: (PostiveN p, Integral a, Bits a) = p - a as you can imagine, I always pass (undefined :: p) as parameter to `montgKeys`, so if it's handled well, it should be memorized for future usage. But tracing shows that both `p2num` and `montgKeys` are evaluated every time being called. So my question is, how to force GHC memorizing this kind of functions? [1]: http://en.wikipedia.org/wiki/Montgomery_reduction [2]: https://github.com/bjin/montg-reduce Regards, Bin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] memorize function with number parameterized types in GHC
On Sun, Nov 6, 2011 at 9:10 PM, Bin Jin bjin1...@gmail.com wrote: Hi, everyone I'm recently trying to implement the Montgomery reduction algorithm[1] in Haskell, the code can be found on my Github page[2]. After doing some benchmark testing I found that the library works rather slow. With the help of `trace` function from Debug.Trace, I found that GHC is not magical enough to memorize values with the same type(well, it's actually dynamically generated number parameterized type). I used binary representation to handle all positive numbers in type system. data One = One data D0 a = D0 a data D1 a = D1 a class PostiveN a where p2num :: (Num b, Bits b) = a - b instance PostiveN One ... instance PostiveN a = PostiveN (D0 a) ... instance PostiveN a = PostiveN (D1 a) ... Here is a function that will be called everytime by `(*)` in `Num` typeclass montgKeys :: (PostiveN p, Integral a, Bits a) = p - a as you can imagine, I always pass (undefined :: p) as parameter to `montgKeys`, so if it's handled well, it should be memorized for future usage. But tracing shows that both `p2num` and `montgKeys` are evaluated every time being called. So my question is, how to force GHC memorizing this kind of functions? [1]: http://en.wikipedia.org/wiki/Montgomery_reduction [2]: https://github.com/bjin/montg-reduce Regards, Bin GHC only memorizes data structures, but not functions. See [1]. [1] http://www.haskell.org/haskellwiki/Memoization -- Yucheng Zhang ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] memorize function with number parameterized types in GHC
Hi, Since I actually didn't use the parameter in calculation, the return value only depends on the type of input, not the actually value. If it's impossible to cache the result, is there another way to memorize this function ? On Sun, Nov 6, 2011 at 9:20 PM, Yucheng Zhang yczhan...@gmail.com wrote: On Sun, Nov 6, 2011 at 9:10 PM, Bin Jin bjin1...@gmail.com wrote: Hi, everyone I'm recently trying to implement the Montgomery reduction algorithm[1] in Haskell, the code can be found on my Github page[2]. After doing some benchmark testing I found that the library works rather slow. With the help of `trace` function from Debug.Trace, I found that GHC is not magical enough to memorize values with the same type(well, it's actually dynamically generated number parameterized type). I used binary representation to handle all positive numbers in type system. data One = One data D0 a = D0 a data D1 a = D1 a class PostiveN a where p2num :: (Num b, Bits b) = a - b instance PostiveN One ... instance PostiveN a = PostiveN (D0 a) ... instance PostiveN a = PostiveN (D1 a) ... Here is a function that will be called everytime by `(*)` in `Num` typeclass montgKeys :: (PostiveN p, Integral a, Bits a) = p - a as you can imagine, I always pass (undefined :: p) as parameter to `montgKeys`, so if it's handled well, it should be memorized for future usage. But tracing shows that both `p2num` and `montgKeys` are evaluated every time being called. So my question is, how to force GHC memorizing this kind of functions? [1]: http://en.wikipedia.org/wiki/Montgomery_reduction [2]: https://github.com/bjin/montg-reduce Regards, Bin GHC only memorizes data structures, but not functions. See [1]. [1] http://www.haskell.org/haskellwiki/Memoization -- Yucheng Zhang ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] memorize function with number parameterized types in GHC
On Sun, Nov 6, 2011 at 9:35 PM, Bin Jin bjin1...@gmail.com wrote: Hi, Since I actually didn't use the parameter in calculation, the return value only depends on the type of input, not the actually value. If it's impossible to cache the result, is there another way to memorize this function ? Sorry, I haven't considered about 'number parameterized type' when I answered the question. However, you can still use a data structure like MemoTrie [1] to memorize the function. The memorization is trivial, since you can convert between the number-typed 'undefined' and 'Integer' with the functions 'p2num' and 'num2p' in your code. I've not tested, but this is an example using MemoTrie: import Data.MemoTrie memoMontgKeys :: (PostiveN p, Integral a, Bits a) = p - a memoMontgKeys = memoMontgKeys' . p2num memoMontgKeys' :: (Integral a) = Integer - a memoMontgKeys' = memo (montgKeys . num2p) On the other hand, I think GHC is not expected to do the memorization automatically. An arbitrary number can turn up as the argument type of 'montgKeys'. This is similar to a function with an Integer argument, which GHC does not memorize now. [1] http://hackage.haskell.org/package/MemoTrie Yucheng Zhang ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] memorize function with number parameterized types in GHC
Hi, Then how about p2num, how to memorize this function. Also I think it's okay to memorize this kind of function. The type system ensure all calling of montgKeys have the same type, e.g., it's a pure function without parameter, it's safe to memorize it since it didn't occupy more memory than representing dynamic generated types. On Nov 6, 2011 11:06 PM, Yucheng Zhang yczhan...@gmail.com wrote: On Sun, Nov 6, 2011 at 9:35 PM, Bin Jin bjin1...@gmail.com wrote: Hi, Since I actually didn't use the parameter in calculation, the return value only depends on the type of input, not the actually value. If it's impossible to cache the result, is there another way to memorize this function ? Sorry, I haven't considered about 'number parameterized type' when I answered the question. However, you can still use a data structure like MemoTrie [1] to memorize the function. The memorization is trivial, since you can convert between the number-typed 'undefined' and 'Integer' with the functions 'p2num' and 'num2p' in your code. I've not tested, but this is an example using MemoTrie: import Data.MemoTrie memoMontgKeys :: (PostiveN p, Integral a, Bits a) = p - a memoMontgKeys = memoMontgKeys' . p2num memoMontgKeys' :: (Integral a) = Integer - a memoMontgKeys' = memo (montgKeys . num2p) On the other hand, I think GHC is not expected to do the memorization automatically. An arbitrary number can turn up as the argument type of 'montgKeys'. This is similar to a function with an Integer argument, which GHC does not memorize now. [1] http://hackage.haskell.org/package/MemoTrie Yucheng Zhang ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] memorize function with number parameterized types in GHC
On Sun, Nov 6, 2011 at 10:31, Bin Jin bjin1...@gmail.com wrote: Then how about p2num, how to memorize this function. Also I think it's okay to memorize this kind of function. The type system ensure all calling of montgKeys have the same type, e.g., it's a pure function without parameter, it's safe to memorize it since it didn't occupy more memory than representing dynamic generated types. Did you read the wiki page you were pointed to? ghc never memoizes functions by itself; the page provides pointers to a number of ways that you can add memoization, along with pointers to discussion of why there is no automated memoization. http://haskell.org/haskellwiki/Memoization -- brandon s allbery allber...@gmail.com wandering unix systems administrator (available) (412) 475-9364 vm/sms ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] memorize function with number parameterized types in GHC
Yes, but I think it's not a funtion since the function didn't use the parameter. So maybe there is a way to make memorizing possible. Also p2num is a general function used in number parameterized types, so I asked this question here. On Nov 6, 2011 11:41 PM, Brandon Allbery allber...@gmail.com wrote: On Sun, Nov 6, 2011 at 10:31, Bin Jin bjin1...@gmail.com wrote: Then how about p2num, how to memorize this function. Also I think it's okay to memorize this kind of function. The type system ensure all calling of montgKeys have the same type, e.g., it's a pure function without parameter, it's safe to memorize it since it didn't occupy more memory than representing dynamic generated types. Did you read the wiki page you were pointed to? ghc never memoizes functions by itself; the page provides pointers to a number of ways that you can add memoization, along with pointers to discussion of why there is no automated memoization. http://haskell.org/haskellwiki/Memoization -- brandon s allbery allber...@gmail.com wandering unix systems administrator (available) (412) 475-9364 vm/sms ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] memorize function with number parameterized types in GHC
What's the purpose of all the type trickery? Why not just implement the algorithm using Integer? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] memorize function with number parameterized types in GHC
In order to represent Z/nZ, regular way need to store two integers, and a data constructer. With number parameterized types, newtype+Integer can be used, it's much more efficient. For this project, montg reduce require to calculate a key for each modulus, but the modulus won't be changed within Num typeclass. It's better to fix it in type system. On Nov 7, 2011 1:38 AM, DavidA polyom...@f2s.com wrote: What's the purpose of all the type trickery? Why not just implement the algorithm using Integer? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] memorize function with number parameterized types in GHC
Bin Jin bjin1990 at gmail.com writes: In order to represent Z/nZ, regular way need to store two integers, and a data constructer. With number parameterized types, newtype+Integer can be used, it's much more efficient. For this project, montg reduce require to calculate a key for each modulus, but the modulus won't be changed within Num typeclass. It's better to fix it in type system. On Nov 7, 2011 1:38 AM, DavidA polyomino at f2s.com wrote: What's the purpose of all the type trickery? Why not just implement the algorithm using Integer? ___ Haskell-Cafe mailing listHaskell-Cafe at haskell.orghttp://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe at haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe Ok, but even if you want to represent the inputs and outputs to be in Z/nZ, that doesn't mean that you have to work in Z/nZ while performing the algorithm. I think it would probably be faster to convert from Z/nZ to Integer, do the algorithm, and then convert the result back to Z/nZ. Anyway, good luck, and if you succeed in getting it fast enough, I hope you'll make the results available somewhere. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] memorize function with number parameterized types in GHC
On 11/6/11 10:51 AM, Bin Jin wrote: Yes, but I think it's not a funtion since the function didn't use the parameter. So maybe there is a way to make memorizing possible. In general, if the argument is not used then \x - E is equal to let e = E in \x - e Which we can make strict by adding a bang-pattern or a seq let !e = E in \x - e == let e = E in e `seq` \x - e The strictness isn't always necessary, but it helps to ensure that GHC doesn't get rid of the let-binding which would take us back to the original (\x - E). Now, if we use this as the definition of the function, it'll ensure that the computation of E is done as a CAF and hence is memoized (since laziness is call-by-name + memoization). This trick can be generalized to any function of which parts of it are constant in some subset of parameters. That is, if we have \x y z - E (F (G H x) y) z then this can be converted into let !h = H in \x - let !g = G h x in \y - let !f = F g y in \z - E f z Now, whenever we want to use this function we pass in as many arguments as we are holding fixed, and force the resulting function in order to memoize the initial computations. For example, if the above function is called foo, then we could use it like: forM xs $ \x - do let !foo_x = foo x forM ys $ \y - do let !foo_x_y = foo_x y forM zs $ \z - do let !foo_x_y_z = foo_x_y z ... In this example we're performing loop invariant code motion, but doing so dynamically in order to maintain a separation between the definition of foo and its use. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] memorize function with number parameterized types in GHC
Hi This method is what I'm looking for. it's a nice general solution, but it doesn't solve my problem here. I'm using ghc 7.0.3, I tried to cache p2num and montgKeys in the way you showed. It seems that ghc doesn't memorize p2num and reject to compile new montgKeys. I think caching values with dynamic types is complicated in ghc's runtime environment. Anyone knows the details? On Nov 7, 2011 7:07 AM, wren ng thornton w...@freegeek.org wrote: On 11/6/11 10:51 AM, Bin Jin wrote: Yes, but I think it's not a funtion since the function didn't use the parameter. So maybe there is a way to make memorizing possible. In general, if the argument is not used then \x - E is equal to let e = E in \x - e Which we can make strict by adding a bang-pattern or a seq let !e = E in \x - e == let e = E in e `seq` \x - e The strictness isn't always necessary, but it helps to ensure that GHC doesn't get rid of the let-binding which would take us back to the original (\x - E). Now, if we use this as the definition of the function, it'll ensure that the computation of E is done as a CAF and hence is memoized (since laziness is call-by-name + memoization). This trick can be generalized to any function of which parts of it are constant in some subset of parameters. That is, if we have \x y z - E (F (G H x) y) z then this can be converted into let !h = H in \x - let !g = G h x in \y - let !f = F g y in \z - E f z Now, whenever we want to use this function we pass in as many arguments as we are holding fixed, and force the resulting function in order to memoize the initial computations. For example, if the above function is called foo, then we could use it like: forM xs $ \x - do let !foo_x = foo x forM ys $ \y - do let !foo_x_y = foo_x y forM zs $ \z - do let !foo_x_y_z = foo_x_y z ... In this example we're performing loop invariant code motion, but doing so dynamically in order to maintain a separation between the definition of foo and its use. -- Live well, ~wren __**_ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/**mailman/listinfo/haskell-cafehttp://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] memorize function with number parameterized types in GHC
On Mon, Nov 7, 2011 at 9:29 AM, Bin Jin bjin1...@gmail.com wrote: Hi This method is what I'm looking for. it's a nice general solution, but it doesn't solve my problem here. I'm using ghc 7.0.3, I tried to cache p2num and montgKeys in the way you showed. It seems that ghc doesn't memorize p2num and reject to compile new montgKeys. I think caching values with dynamic types is complicated in ghc's runtime environment. Anyone knows the details? Adding memorization directly to 'montgKeys' or 'p2num' should be possible, if you write your own version of MemoTrie dealing with dynamic types. However, this memorization requires an O(log P) lookup in the trie. This lookup process will require the whole type structure of P to be examined, which is of size O(log P). Yucheng Zhang ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] memorize function with number parameterized types in GHC
The actual time to calculate p2num and montgKeys are both O(log P). What I'm looking is a constant time lookup. On Nov 7, 2011 1:51 PM, Yucheng Zhang yczhan...@gmail.com wrote: On Mon, Nov 7, 2011 at 9:29 AM, Bin Jin bjin1...@gmail.com wrote: Hi This method is what I'm looking for. it's a nice general solution, but it doesn't solve my problem here. I'm using ghc 7.0.3, I tried to cache p2num and montgKeys in the way you showed. It seems that ghc doesn't memorize p2num and reject to compile new montgKeys. I think caching values with dynamic types is complicated in ghc's runtime environment. Anyone knows the details? Adding memorization directly to 'montgKeys' or 'p2num' should be possible, if you write your own version of MemoTrie dealing with dynamic types. However, this memorization requires an O(log P) lookup in the trie. This lookup process will require the whole type structure of P to be examined, which is of size O(log P). Yucheng Zhang ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] memorize function with number parameterized types in GHC
On 7 November 2011 16:54, Bin Jin bjin1...@gmail.com wrote: The actual time to calculate p2num and montgKeys are both O(log P). What I'm looking is a constant time lookup. Are these two functions CPU bottlenecks as revealed by profiling? If not, then you're probably over-optimising. Note that if O(1) lookup is really required, then that implies you use a static array, which requires you to pre-populate such an array with all possible values. -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] memorize function with number parameterized types in GHC
It's all on these two functions. Three most frequently used operations of Num (ModP x) are (+) (-) (*)，each of them will at least call p2num once(to get the modulus), in addition multiplication will call montgKeys. usual implementation do both in constant time: p2num is written as number literal with type Integral a=a, so a reasonable implementation should handle these two function in constant time(in amortized time, of course). On Nov 7, 2011 2:27 PM, Ivan Lazar Miljenovic ivan.miljeno...@gmail.com wrote: On 7 November 2011 16:54, Bin Jin bjin1...@gmail.com wrote: The actual time to calculate p2num and montgKeys are both O(log P). What I'm looking is a constant time lookup. Are these two functions CPU bottlenecks as revealed by profiling? If not, then you're probably over-optimising. Note that if O(1) lookup is really required, then that implies you use a static array, which requires you to pre-populate such an array with all possible values. -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
