Compilation of big, computed tables
Dear all, can ghc compile huge tables into efficient code if they are constant at compile time? Two examples may clearify the question: big1 :: UArray Int Char big1 = array (0,1000) $! map (\i -> (i,toEnum i)) [0..1000] big2 = sum [0..10000]::Int -- == 50005000 == n*(n+1)/2 where n = 10000 Both values are constant at compile time. As they are given by pure functions, the compiler could evaluate them and write the *result* into the object file 'foo.o'. This would save code size and run time. I peeked into 'foo.hc' but I didn't found 0x2fb0408 nor an array {0, 1, 2, 3, ..., 1000} or similar things. The function in big2 should show that the computation of the value could be very time consuming. If the compiler does not compute it, the source file could be generated by a helper program (or template Haskell?). The function in big1 should show that the conversion of the data into an array could be run-time, code-size and heap-size consuming. (You need the list (maybe explicitly - think of 1000 fixed pseudo-random numbers) and convert it into an array.) If the compiler generates the unboxed array directly it could be rather efficient. PS: I compiled with: ghc6 -c -O2 -keep-tmp-files -keep-hc-files foo.hs Regards, -- Stefan Karrmann
Stefan Karrmann wrote:
Dear all,
can ghc compile huge tables into efficient code if they are constant at compile time?
Two examples may clearify the question:
big1 :: UArray Int Char big1 = array (0,1000) $! map (\i -> (i,toEnum i)) [0..1000]
big2 = sum [0..10000]::Int -- == 50005000 == n*(n+1)/2 where n = 10000
GHC does not compute such values are compile time because *) The computation may not finish in reasonable time (infinite/not halting) *) The computation may generate a run-time error and crash the compilation (divide by zero, pattern march failure, etc.) *) Haskell is supposed to be lazy, things are computed when needed, not before The big1 UArray is unboxed which prevents laziness, so big1 will be fully computed the first time any of the values are referenced. There is a way around this: I have not needed to use it, but template haskell can compute things at compile time. ( http://haskell.org/hawiki/TemplateHaskell and http://haskell.org/hawiki/TemplateHaskellTutorial are good links) [ Template haskell could even be abused to interactively allow you to interactively type in a URL from which to download code to insert into the file. ]
Chris Kuklewicz:
Stefan Karrmann wrote:
Dear all,
can ghc compile huge tables into efficient code if they are constant at compile time?
Two examples may clearify the question:
big1 :: UArray Int Char big1 = array (0,1000) $! map (\i -> (i,toEnum i)) [0..1000]
big2 = sum [0..10000]::Int -- == 50005000 == n*(n+1)/2 where n = 10000
GHC does not compute such values are compile time because *) The computation may not finish in reasonable time (infinite/not halting) *) The computation may generate a run-time error and crash the compilation (divide by zero, pattern march failure, etc.) *) Haskell is supposed to be lazy, things are computed when needed, not before
Does this mean that GHC does not evaluate constant subexpressions at compile-time? Or does it evaluate only some subclass of surely terminating and non-erroneous subexpressions at compile-time? Constant subexpression evaluation is a common compiler optimization technique, so I would be a bit surprised if GHC does not do it. Björn LIsper
Bjorn Lisper wrote:
Chris Kuklewicz:
Stefan Karrmann wrote:
Dear all,
can ghc compile huge tables into efficient code if they are constant at compile time?
Two examples may clearify the question:
big1 :: UArray Int Char big1 = array (0,1000) $! map (\i -> (i,toEnum i)) [0..1000]
big2 = sum [0..10000]::Int -- == 50005000 == n*(n+1)/2 where n = 10000
GHC does not compute such values are compile time because *) The computation may not finish in reasonable time (infinite/not halting) *) The computation may generate a run-time error and crash the compilation (divide by zero, pattern march failure, etc.) *) Haskell is supposed to be lazy, things are computed when needed, not before
Does this mean that GHC does not evaluate constant subexpressions at compile-time?
No, constant folding is definitely one of the optimisations that GHC performs.
Or does it evaluate only some subclass of surely terminating and non-erroneous subexpressions at compile-time?
Yes, the compiler will not evaluate expressions that raise exceptions or fail. For example, integer division is only performed at compile time for a non-zero dividend. Cheers, Simon
Bjorn Lisper wrote:
Chris Kuklewicz:
Stefan Karrmann wrote:
Dear all,
can ghc compile huge tables into efficient code if they are constant at compile time?
Two examples may clearify the question:
big1 :: UArray Int Char big1 = array (0,1000) $! map (\i -> (i,toEnum i)) [0..1000]
big2 = sum [0..10000]::Int -- == 50005000 == n*(n+1)/2 where n = 10000
GHC does not compute such values are compile time because *) The computation may not finish in reasonable time (infinite/not halting) *) The computation may generate a run-time error and crash the compilation (divide by zero, pattern march failure, etc.) *) Haskell is supposed to be lazy, things are computed when needed, not before
Does this mean that GHC does not evaluate constant subexpressions at compile-time?
No, constant folding is definitely one of the optimisations that GHC performs.
Or does it evaluate only some subclass of surely terminating and non-erroneous subexpressions at compile-time?
Yes, the compiler will not evaluate expressions that raise exceptions or fail. For example, integer division is only performed at compile time for a non-zero dividend. Cheers, Simon
Stefan Karrmann <S.Karrmann@web.de> wrote:
can ghc compile huge tables into efficient code if they are constant at compile time?
I have a related but different question. If I have large, statically defined tables of data e.g. table = listArray (0,max) [ [1,2,3,4] , [5,6,7,8,9,10] , [11,12,13] ... ] i.e. no computation is required, can these be compiled directly to a space-efficient lookup structure? Compilers might do something reasonable for large static strings of chars, but they cannot do the same for arrays. The trouble is that the Array types are abstract, so one cannot use the natural literal constructor. What I would really like is a syntax to statically construct an array, without having to compute it from a list. I'm not sure that even Template Haskell can help here, since there is no normal form for it to translate to. Regards, Malcolm
Malcolm Wallace wrote:
Stefan Karrmann <S.Karrmann@web.de> wrote:
can ghc compile huge tables into efficient code if they are constant at compile time?
I have a related but different question. If I have large, statically defined tables of data e.g.
table = listArray (0,max) [ [1,2,3,4] , [5,6,7,8,9,10] , [11,12,13] ... ]
i.e. no computation is required, can these be compiled directly to a space-efficient lookup structure? Compilers might do something reasonable for large static strings of chars, but they cannot do the same for arrays. The trouble is that the Array types are abstract, so one cannot use the natural literal constructor.
What I would really like is a syntax to statically construct an array, without having to compute it from a list. I'm not sure that even Template Haskell can help here, since there is no normal form for it to translate to.
This has always been a weakness in GHC, and perhaps in Haskell itself. In theory GHC could compile a completely static array declaration (like yours above) into a static array, but it doesn't. It's not trivial to do, because it involves unrolling the (recursive) definition of listArray, or perhaps some special-case code to spot array/listArray applied to static lists. Happy & Alex use the hack of encoding static arrays as strings and using peek to access the data at runtime, FWIW. Cheers, Simon
Hello Simon, Thursday, February 23, 2006, 3:35:51 PM, you wrote:
What I would really like is a syntax to statically construct an array, without having to compute it from a list. I'm not sure that even Template Haskell can help here, since there is no normal form for it to translate to.
SM> Happy & Alex use the hack of encoding static arrays as strings and using SM> peek to access the data at runtime, FWIW. this can be accomplished using TH and ForeignArray constructed from string constant ("..."#) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
What I would really like is a syntax to statically construct an array, without having to compute it from a list. I'm not sure that even Template Haskell can help here, since there is no normal form for it to translate to.
SM> Happy & Alex use the hack of encoding static arrays as strings and SM> using peek to access the data at runtime, FWIW.
this can be accomplished using TH and ForeignArray constructed from string constant ("..."#)
Hmm, that only works if the data being stored in the table is of regular size? I need variable-length values. Using a two- or three-level encoding into strings would start to get /really/ unpleasant. And this is pretty ghc-specific stuff. Perhaps I should propose a new syntactic construct for the language? (Although not necessarily in time for haskell-prime.) literalArray -> « literal_0, literal_1, ... , literal_n » The type of the literal array would be something like « » :: Ix i => Array i t Could the array be used at /any/ index type i? Or would it be a fixed index type, selected by type signature, inference from the usage context, or failing either of those, the monomorphism restriction? In any case, the actual bounds would be calculated by the compiler. What about the content type t? Should it be a fixed type, or would we permit overloading? Come to think of it, why should we permit only literals as content elements? Arrays are lazy, so the contents could be arbitrary expressions, provided they are all of the same type. literalArray -> « exp_0, exp_1, ... , exp_n » Would we allow the « » brackets to be used for pattern-matching as well as construction? Thoughts? Regards, Malcolm
Malcolm Wallace wrote:
Hmm, that only works if the data being stored in the table is of regular size? I need variable-length values. Using a two- or three-level encoding into strings would start to get /really/ unpleasant.
And this is pretty ghc-specific stuff.
Perhaps I should propose a new syntactic construct for the language?
And how about create a 'reduction rules' syntax? It maps a common construct that usually becomes slow code in predefined fast code. So the optimization done by compiler becomes more transparent, easy to ennhance and the user can include his own reduction rules. In this especific case, the rule could be something like 'if the function returns an array of numbers and the function dont depends on other functions, the function is a literal array'. This could be used in IO too, to teach the compiler how to transform a slow code in a fast code. Atila
(Although not necessarily in time for haskell-prime.)
literalArray -> « literal_0, literal_1, ... , literal_n »
The type of the literal array would be something like
« » :: Ix i => Array i t
Could the array be used at /any/ index type i? Or would it be a fixed index type, selected by type signature, inference from the usage context, or failing either of those, the monomorphism restriction?
In any case, the actual bounds would be calculated by the compiler.
What about the content type t? Should it be a fixed type, or would we permit overloading? Come to think of it, why should we permit only literals as content elements? Arrays are lazy, so the contents could be arbitrary expressions, provided they are all of the same type.
literalArray -> « exp_0, exp_1, ... , exp_n »
Would we allow the « » brackets to be used for pattern-matching as well as construction?
Thoughts?
Regards, Malcolm _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Atila Romero <atilaromero@yahoo.com.br> wrote:
Perhaps I should propose a new syntactic construct for the language?
And how about create a 'reduction rules' syntax? It maps a common construct that usually becomes slow code in predefined fast code. So the optimization done by compiler becomes more transparent, easy to ennhance and the user can include his own reduction rules.
I believe ghc already has something like this: the {-# RULES #-} pragma. The problem is that there is no portable notation for the target of the rule, if you want to specify a constant array. Regards, Malcolm
On Thu, Feb 23, 2006 at 10:40:31AM +0000, Malcolm Wallace wrote:
What I would really like is a syntax to statically construct an array, without having to compute it from a list. I'm not sure that even Template Haskell can help here, since there is no normal form for it to translate to.
This is exactly what my ForeignData proposal on the haskell-prime wiki is meant to address http://haskell.galois.com/cgi-bin/haskell-prime/trac.cgi/wiki/ForeignData It is trivial to implement and seems like a straightforward accidental omission in the FFI spec so I'd like to see it go in. though, I only have it specified for creating pointers to data, it wouldn't be much trickier to make it work for haskell unboxed arrays too (though, you can just make a StorableArray out of them easily as stands) Plus, if this were in haskell I can honestly say "Haskell can do everything C can do but better" without mubling something about with a few caveats under my breath :) John -- John Meacham - ⑆repetae.net⑆john⑈
John Meacham wrote:
On Thu, Feb 23, 2006 at 10:40:31AM +0000, Malcolm Wallace wrote:
What I would really like is a syntax to statically construct an array, without having to compute it from a list.
This is exactly what my ForeignData proposal on the haskell-prime wiki is meant to address [...] though, I only have it specified for creating pointers to data, it wouldn't be much trickier to make it work for haskell unboxed arrays too (though, you can just make a StorableArray out of them easily as stands)
What about boxed arrays? A static Array of thunks makes as much sense to me as a static UArray of CInts. This doesn't really feel like an FFI feature. (Not that foreign data wouldn't be useful too.) -- Ben
participants (9)
-
Atila Romero -
Ben Rudiak-Gould -
Bjorn Lisper -
Bulat Ziganshin -
Chris Kuklewicz -
John Meacham -
Malcolm Wallace -
Simon Marlow -
Stefan Karrmann