Re: [Haskell-cafe] Unboxed arrays
Hello Andrew,
Wednesday, March 26, 2008, 3:37:53 PM, you wrote:
> type of your own, you just need to write your own instance". The thing
> that makes me suspicious of this logic is the absense of an instance for
> tuples.
> Any insights here?
and even insiders :) i've rewrote arrays library to be more uniform
using ideas of Simon Marlow and Oleg Kiselyov
unboxed arrays implementation uses GHC primitives that fetches/stores
array element by its index. these primitives implemented for simple
types - from Word8 to Double but nothing more. they use *indexes*, not
*byte offsets* which means that you can use them for addressing array
of {Word8,Double}, for example
i believe that it should be possible to rewrite array machinery using
storable class (now it should not have any overheads compared to these
primitives). meanwhile i recommend you to use storable array together
with Storable instances for tuples
--
Best regards,
Bulatmailto:[EMAIL PROTECTED]
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Unboxed arrays
* Andrew Coppin <[EMAIL PROTECTED]> [2008-03-26 12:37:53+] > Somebody asked me, so now I'm asking you... > > In Haskell, you can make "unboxed" arrays of certain value types. These > are typically more efficient in space, and probably time too, and also > make the array strict in its values. However, you can only do this magic > trick for certain types - not for *all* types. > > Why is that? Is it because nobody has done anything about it yet? Is it > because it's thought to be "not necessary" in some way? Is there some > theoretical problem? Has somebody got a better idea? > > I did think it was along the lines of "oh, well, if you want to unbox a > type of your own, you just need to write your own instance". The thing > that makes me suspicious of this logic is the absense of an instance for > tuples. Surely this would be trivial to write, and yet it's not present. > If we had instances for a couple of sizes of tuples, it would surely be > quite easy to write your own custom instances that just sit on top of > this and tuple/untuple your custom values... > > Any insights here? Could Data Parallel Haskell[1] be useful for you? It was designed for parallel computation, but it includes unboxed arrays, nice list-like syntax and array comprehensions. 1. http://www.haskell.org/haskellwiki/GHC/Data_Parallel_Haskell -- Roman I. Cheplyaka :: http://ro-che.info/ ...being in love is totally punk rock... signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Unboxed arrays
On Wed, 26 Mar 2008, Roman Cheplyaka wrote: * Andrew Coppin <[EMAIL PROTECTED]> [2008-03-26 12:37:53+] Somebody asked me, so now I'm asking you... In Haskell, you can make "unboxed" arrays of certain value types. These are typically more efficient in space, and probably time too, and also make the array strict in its values. However, you can only do this magic trick for certain types - not for *all* types. Why is that? Is it because nobody has done anything about it yet? Is it because it's thought to be "not necessary" in some way? Is there some theoretical problem? Has somebody got a better idea? I did think it was along the lines of "oh, well, if you want to unbox a type of your own, you just need to write your own instance". The thing that makes me suspicious of this logic is the absense of an instance for tuples. Surely this would be trivial to write, and yet it's not present. If we had instances for a couple of sizes of tuples, it would surely be quite easy to write your own custom instances that just sit on top of this and tuple/untuple your custom values... Any insights here? Could Data Parallel Haskell[1] be useful for you? It was designed for parallel computation, but it includes unboxed arrays, nice list-like syntax and array comprehensions. 1. http://www.haskell.org/haskellwiki/GHC/Data_Parallel_Haskell A light-weight unboxed array variant is: http://code.haskell.org/~sjanssen/storablevector/ I thought it might be more efficient sometimes to split, say Word8 and Double data into two arrays, instead of padding data in order to align a (Word8,Double) record, but this wouldn't fit into the array data structure. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Unboxed arrays
Roman Cheplyaka wrote: * Andrew Coppin <[EMAIL PROTECTED]> [2008-03-26 12:37:53+] Any insights here? Could Data Parallel Haskell[1] be useful for you? It was designed for parallel computation, but it includes unboxed arrays, nice list-like syntax and array comprehensions. 1. http://www.haskell.org/haskellwiki/GHC/Data_Parallel_Haskell Mmm, maybe. Does it implement unboxed arrays for arbitrary types? For that matter, it seems like this NDP stuff has been "in development" for a seemingly long time now. Does anybody know what the current status is? (I'm guessing the people working on this are more interested in working on it than documenting every step of their progress... which leaves outsiders with the impression that nothing is happening.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Unboxed arrays
Andrew Coppin wrote: Roman Cheplyaka wrote: * Andrew Coppin <[EMAIL PROTECTED]> [2008-03-26 12:37:53+] Any insights here? Could Data Parallel Haskell[1] be useful for you? It was designed for parallel computation, but it includes unboxed arrays, nice list-like syntax and array comprehensions. 1. http://www.haskell.org/haskellwiki/GHC/Data_Parallel_Haskell Mmm, maybe. Does it implement unboxed arrays for arbitrary types? For that matter, it seems like this NDP stuff has been "in development" for a seemingly long time now. Does anybody know what the current status is? Google -> http://research.microsoft.com/~simonpj/papers/ndp/ (I'm guessing the people working on this are more interested in working on it than documenting every step of their progress... which leaves outsiders with the impression that nothing is happening.) I don't think the above suggests that "nothing is happening" ... -- Dr. Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Unboxed arrays
Janis Voigtlaender wrote: Google -> http://research.microsoft.com/~simonpj/papers/ndp/ I don't think the above suggests that "nothing is happening" ... The latet thing on that page is dated over a year ago. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Unboxed arrays
Andrew Coppin wrote: Janis Voigtlaender wrote: Google -> http://research.microsoft.com/~simonpj/papers/ndp/ I don't think the above suggests that "nothing is happening" ... The latet thing on that page is dated over a year ago. Well, if you expect monthly updates... -- Dr. Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Unboxed arrays
* Henning Thielemann <[EMAIL PROTECTED]> [2008-03-26 14:22:20+0100] > > On Wed, 26 Mar 2008, Roman Cheplyaka wrote: > >> * Andrew Coppin <[EMAIL PROTECTED]> [2008-03-26 12:37:53+] >>> Somebody asked me, so now I'm asking you... >>> >>> In Haskell, you can make "unboxed" arrays of certain value types. These >>> are typically more efficient in space, and probably time too, and also >>> make the array strict in its values. However, you can only do this magic >>> trick for certain types - not for *all* types. >>> >>> Why is that? Is it because nobody has done anything about it yet? Is it >>> because it's thought to be "not necessary" in some way? Is there some >>> theoretical problem? Has somebody got a better idea? >>> >>> I did think it was along the lines of "oh, well, if you want to unbox a >>> type of your own, you just need to write your own instance". The thing >>> that makes me suspicious of this logic is the absense of an instance for >>> tuples. Surely this would be trivial to write, and yet it's not present. >>> If we had instances for a couple of sizes of tuples, it would surely be >>> quite easy to write your own custom instances that just sit on top of >>> this and tuple/untuple your custom values... >>> >>> Any insights here? >> >> Could Data Parallel Haskell[1] be useful for you? >> It was designed for parallel computation, but it includes unboxed >> arrays, nice list-like syntax and array comprehensions. >> >> 1. http://www.haskell.org/haskellwiki/GHC/Data_Parallel_Haskell > > A light-weight unboxed array variant is: > http://code.haskell.org/~sjanssen/storablevector/ > > > I thought it might be more efficient sometimes to split, say Word8 and > Double data into two arrays, instead of padding data in order to align a > (Word8,Double) record, but this wouldn't fit into the array data > structure. As far as I know, ndp (which I linked above) takes exactly this approach. -- Roman I. Cheplyaka :: http://ro-che.info/ ...being in love is totally punk rock... signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Unboxed arrays
On Wed 2008-03-26 14:22, Henning Thielemann wrote: > A light-weight unboxed array variant is: > http://code.haskell.org/~sjanssen/storablevector/ There is also CArray which offers an immutable interface for any Storable. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/carray You can also do unsafe (no-copy) freeze/thaw to IOCArray which is equivalent to StorableArray. Unfortunately there is a performance hit to using Storable versus the built in unboxed types. On the other hand, CArray is binary compatible with C which is handy if you are making foreign calls. > I thought it might be more efficient sometimes to split, say Word8 and > Double data into two arrays, instead of padding data in order to align a > (Word8,Double) record, but this wouldn't fit into the array data structure. This depends on the access pattern, but if it makes you miss the cache frequently, then it is certainly not the way to go. For split storage to win, you must frequently traverse while only referencing one entry. It is not clear (to me) how to make an interface where the split storage is hidden, but the compiler can still remove all references to the unused part (without boxing which defeats the purpose). Jed pgpsQTUt7ru5r.pgp Description: PGP signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Unboxed arrays
On Wed 2008-03-26 19:50, Bulat Ziganshin wrote: > Hello Jed, > > Wednesday, March 26, 2008, 7:02:28 PM, you wrote: > > > StorableArray. Unfortunately there is a performance hit to using Storable > > versus the built in unboxed types. > > are you sure? it was in ghc 6.4, now afair they should be the same. > look in http://haskell.org/haskellwiki/Modern_array_libraries The comparison I'm referring to is a micro-benchmark taken from the shootout. I modified the nsieve-bits code here: http://shootout.alioth.debian.org/gp4/benchmark.php?test=nsievebits&lang=ghc&id=0 The shootout code uses STUArray, one modification uses IOCArray, another uses StorableArray (which should be equivalent to IOCArray). Here are some timing results with ghc-6.8.2 on x86_64. $ for e in nsU nsC nsS; do time ./$e 12 > /dev/null; done 1.087 real 1.087 user 0.000 sys 99.96 cpu 3.454 real 3.326 user 0.127 sys 99.98 cpu 3.448 real 3.343 user 0.103 sys 99.94 cpu With ghc-6.8.2 on x86, I get $ for e in nsU nsC nsS; do time ./$e 12 > /dev/null; done ./nsU 124.57 real 4.45 user 0.01 sys ./nsC 1210.46 real 9.88 user 0.27 sys ./nsS 1210.59 real 9.86 user 0.24 sys That is, the STUArray version (nsU) is much faster than IOCArray (nsC) and StorableArray (nsS) for this test. To see for yourself, checkout CArray darcs get http://code.haskell.org/carray build it, then see the script in tests/runtests.sh. It will build an run these benchmarks, confirming that the output is the same and providing timing information. I would love to see this discrepancy go away, but sadly, it is not there yet. Jed pgprbNe5PRMWN.pgp Description: PGP signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Unboxed arrays
andrewcoppin: > Janis Voigtlaender wrote: > >Google -> http://research.microsoft.com/~simonpj/papers/ndp/ > > > >I don't think the above suggests that "nothing is happening" ... > > The latet thing on that page is dated over a year ago. It's very active. See: http://haskell.org/haskellwiki/GHC/Data_Parallel_Haskell and watch the commits coming in from Roman. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Unboxed arrays
Don Stewart wrote: It's very active. See: http://haskell.org/haskellwiki/GHC/Data_Parallel_Haskell and watch the commits coming in from Roman. *digs around* Hmm. So in summary, stuff is happening behind the scenes, there's just not a lot of visible activity at the surface. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] unboxed arrays restricted to simple types (Int, Float, ..)
On Wed, Nov 11, 2009 at 12:58 PM, Tillmann Vogt wrote: > Hi, > > I tried to use unboxed arrays for generating an antialiased texture. To make > it easier to understand, here is the stripped down code that produces an > error: > *snip* > > What do you think? > It is generally acknowledged that the array types bundled with GHC have serious shortcomings, such as for example the one you just pointed out. There is not, however, a consensus on how to change them. To solve your particular problem, I would suggest looking up the storablevector package on Hackage, which I know can handle arbitrary unboxed elements. That said, I'm sure someone will be along shortly to give you the full story. :-) -- Svein Ove Aas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] unboxed arrays restricted to simple types (Int, Float, ..)
On Wed, Nov 11, 2009 at 5:28 PM, Tillmann Vogt wrote:
> Hi,
>
> I tried to use unboxed arrays for generating an antialiased texture. To
> make it easier to understand, here is the stripped down code that produces
> an error:
>
> >import Control.Monad.ST
> >import Data.Array.ST
> >import Data.Array.Unboxed
> >import Data.Word
> >type BitMask = UArray Int Word16 -- for determining the grey value of a
> pixel
> >type Pixels = (Int, Int, T)
> >data T = N | B BitMask -- this does not work
> >-- type T = Int -- this works if int the next line N is replaced by ..lets
> say 0
> >f = newArray (0,10) N :: (ST s (STUArray s Int T))
>
>
> http://hackage.haskell.org/packages/archive/array/0.2.0.0/doc/html/Data-Array-MArray.html#t%3AMArray
> shows that mutable/unboxed arrays only allow simple types:
> i.e. MArray (STUArray s) Int32 (ST s)
>
> Isn't this ugly? Imagine this would be the case in C:
>
>
> struct stupidArrayElement{
> int a;
> int b; // not allowed!
> }
>
> stupidArrayElement s[10];
>
>
> Wouldn't it be nice to have something like: MArray (STUArray s) e (ST s)
> with e being a non-recursive data type (like data T = N | B Bitmask).
> My understanding of Haskell isn't deep enough to know if I have overlooked
> something or if the problem is solvable without a language extension. With a
> language extension I guess that it is not hard to find out if an abstract
> data type is non-recursive. Then this type should be serializable
> automatically.
>
> What do you think?
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
Actually, there's a cool package called storable record. Could it be of
some use to you? (Perhaps you *might* be able to use it if the BitMasks are
of uniform length). Am not 100% sure though.
Isn't this ugly?
I am not sure if it is really *ugly*...and if am allowed to nit-pick,
the analogy with C is not appropriate either.
Arrays are just different. (At least thats how I console myself, when am
looking for a high performance strict array). Also, on an approximately
related issue,
I was suggested to look into data parallel arrays.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] unboxed arrays restricted to simple types (Int, Float, ..)
You might also look at how Data Parallel Haskell implements its arrays.
IIRC, it implements an array of n-field records as n arrays. You can
easily do that with typeclasses and type families.
2009/11/11 Tillmann Vogt :
> Hi,
>
> I tried to use unboxed arrays for generating an antialiased texture. To make
> it easier to understand, here is the stripped down code that produces an
> error:
>
>>import Control.Monad.ST
>>import Data.Array.ST
>>import Data.Array.Unboxed
>>import Data.Word
>>type BitMask = UArray Int Word16 -- for determining the grey value of a
>> pixel
>>type Pixels = (Int, Int, T)
>>data T = N | B BitMask -- this does not work
>>-- type T = Int -- this works if int the next line N is replaced by ..lets
>> say 0
>>f = newArray (0,10) N :: (ST s (STUArray s Int T))
>
> http://hackage.haskell.org/packages/archive/array/0.2.0.0/doc/html/Data-Array-MArray.html#t%3AMArray
> shows that mutable/unboxed arrays only allow simple types:
> i.e. MArray (STUArray s) Int32 (ST s)
>
> Isn't this ugly? Imagine this would be the case in C:
>
>
> struct stupidArrayElement{
> int a;
> int b; // not allowed!
> }
>
> stupidArrayElement s[10];
>
>
> Wouldn't it be nice to have something like: MArray (STUArray s) e (ST s)
> with e being a non-recursive data type (like data T = N | B Bitmask).
> My understanding of Haskell isn't deep enough to know if I have overlooked
> something or if the problem is solvable without a language extension. With a
> language extension I guess that it is not hard to find out if an abstract
> data type is non-recursive. Then this type should be serializable
> automatically.
>
> What do you think?
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
--
Eugene Kirpichov
Web IR developer, market.yandex.ru
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] unboxed arrays restricted to simple types (Int, Float, ..)
There's a couple of things going on here:
-If you use storablevector and storable-tuple, or uvector, you can
store tuples of things. So your stupidArrayElement could be mimicked
by (Int, Int).
-But what you want to do is store a variable-sized data type. How
would you do that in C? If you can spare another bit of memory, it
might be better to define type T = (Bool, Bitmask) and use
storablevector. Or maybe you want a sparse array of Bitmasks?
-Yes it is a shame that Haskell does not have good support for
unbounded polymorphic arrays. What if I want an array of functions?
Here's a little trick that can make it a bit easier to store any data
type in an unboxed array. I don't know, for instance, of any other way
to define unrestricted functor/applicative for unboxed arrays. This
trick should work with any other array library.
{-# LANGUAGE GADTs#-}
module FArray where
import Data.StorableVector
import Foreign.Storable
import Control.Applicative
data EqOrF a b where
Eq :: EqOrF a a
F :: (a->b) -> EqOrF a b
data FArray a where
FArray :: Storable a => Vector a -> EqOrF a b -> FArray b
ConstArr :: a -> FArray a
instance Functor FArray where
fmap f (ConstArr x) = ConstArr $ f x
fmap f (FArray sv Eq) = FArray sv $ F f
fmap f (FArray sv (F g)) = FArray sv $ F $ f . g
instance Applicative FArray where
pure x = ConstArr x
(ConstArr f) <*> farr = fmap f farr
-- other cases left as an exercise. Which is to say, my bladder is
bursting and I also need lunch.
arrayOfInts = FArray (pack [1..10]) Eq
arrayOfAdders = (+) `fmap` arrayOfInts
Tom
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] unboxed arrays restricted to simple types (Int, Float, ..)
On Wed, 11 Nov 2009, Tom Nielsen wrote: There's a couple of things going on here: -If you use storablevector and storable-tuple, or uvector, you can store tuples of things. So your stupidArrayElement could be mimicked by (Int, Int). Btw. there is Data.Array.Storable. Maybe I should just add a conversion from StorableArray to StorableVector and back. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
