I've been toying with the idea of using Haskell to write a medium sized simulation of a wireless network. However I have a number of concerns as I've begun to program a bit more in Haskell. The first concern is that the simulation needs to be fast, much faster than Matlab for example, to justify the use of Haskell. Given GHCs speed improvement in recent releases, I have high hopes that this is possible. To be honest, I'd probably pick Clean here, but I've been unable to consistently link to third party DLLs with the Clean IDE. The second concern is that the simulation requires heavy use of complex valued matrices. Since I'm on windows and the only reasonably well developed matrix library doesn't run on windows I would be forced to use the FFI to bring in various BLAS and LAPACK routines to support this. I've convinced myself that this is quite possible, if somewhat tedious by virtue of the unpleasant array access syntax for mutable arrays. The third and final concern is the point of this post. How does one handle state efficiently in Haskell? I've seen the various state monads and gained a superficial enough understanding to be concerned about how useful they are, for the following reason: I would like to aggregrate a large number of state variables (possibly in the hundreds of variables) into a few data structures. These structures would not only contain basic variable types, but probably some rather large mutable arrays. So lets say I have such a structure called world and I wish to update just 1 entry. If I do w=world{entry=newentry}, the entire enormous world structure is copied to w. If I bury world in a state monad, then inside a do loop it appears that the get function extracts the entire world state and the set function writes it back into the monad after I've altered it. It still seems to me that the entire structure is copied again to achieve this. I'm not sure if this is true or not. Perhaps the compiler can pull apart the aggregation to fix this issue, but I'm not sure if such an optimization is performed. The only other thing I could think of would be to somehow create get and set functions for every variable in the aggregation, which also would be impossibly tedious. It is possible for me to structure the program so that most of the simulation parameters are set once by the user and then never changed during the rest of the program operation, although incremental state updates are a bit more efficient than this approach. To make this reasonably clean I would probably do some kind of unsafe extraction out of the IO monad to get my input variables, which would then not be changed for the rest of the simulation, although many of the matrices, themselves embedded in the IO monad would have to change incrementally as the simulation progresses. Right now I would favor the latter approach, if I stay with Haskell, but so far it's not clear to me that Haskell is 'convenient' for this kind of development, though I would like to be proven wrong. I am also looking at D or possibly LUA+C for this task, but LUA is not much faster than Matlab.
On Sunday 28 May 2006 23:38, Matthew Bromberg wrote:
I've been toying with the idea of using Haskell to write a medium sized simulation of a wireless network. However I have a number of concerns as I've begun to program a bit more in Haskell.
The first concern is that the simulation needs to be fast, much faster than Matlab for example, to justify the use of Haskell.
(...)
The second concern is that the simulation requires heavy use of complex valued matrices. Since I'm on windows and the only reasonably well developed matrix library doesn't run on windows I would be forced to use the FFI to bring in various BLAS and LAPACK routines to support this. (...)
If matrix operations with very large matrices are the most expensive part of your application it is not easy to be much faster than Matlab or Octave, which already use the optimized ATLAS BLAS and LAPACK. But you can obtain similar performance with a much better language :) Which matrix computations do you need? Alberto
Yes that's true, if the problem could be formulated as monolothic operations on large matrices, then Matlab will be as fast as anything else. My current Matlab implementation, however, generates hundreds of 'small' matrices (say 32 x 32 complex roughly) and does nasty order cubic operations on them inside a bunch of nested for loops. The matrices are generated on the fly as a function of these somewhat large parameter tables. Unfortunately the number of these matrices grows quadratically with the number of nodes in the network I am simulating. In Matlab I believe all structures are dynamic hash tables and for loops are not particularly efficient. My experience has shown that Matlab simulations of this type can be made 4-5 times faster when implemented (rather painfully) into C. The thought is that I could get some of the higher order language capabilities of Matlab but in a more powerful setting such as Haskell, with all of it's meta-language constructs, without having to sacrifice too much performance over a raw C implementation. Alberto Ruiz wrote:
If matrix operations with very large matrices are the most expensive part of your application it is not easy to be much faster than Matlab or Octave, which already use the optimized ATLAS BLAS and LAPACK. But you can obtain similar performance with a much better language :)
Which matrix computations do you need?
Alberto _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
ah... simulation in haskell ... that's a thing i thought a bit of ..
(disclaimer : i'm not so good at haskell, so... :)
here how i've started :
you have your global state : it's a bunch of IORef or STRef. Each one
maps to one of the individual thing you want to update. You can choose
the hierarchy (of non-mutable/mutable fields of the global state) you
want. (For example, you can have only one IORef pointing to the whole
state, or having one IORef for each simple variable).
Since all your updatable things are accessed via IORef, you can just
"read" your state with the ReaderT transformer then "writeIORef" to
change the state.
I join two exemple files i've done ... some comments are in french,
others in english.
hope it helps !
mt
2006/5/28, Matthew Bromberg
I've been toying with the idea of using Haskell to write a medium sized simulation of a wireless network. However I have a number of concerns as I've begun to program a bit more in Haskell.
The first concern is that the simulation needs to be fast, much faster than Matlab for example, to justify the use of Haskell. Given GHCs speed improvement in recent releases, I have high hopes that this is possible. To be honest, I'd probably pick Clean here, but I've been unable to consistently link to third party DLLs with the Clean IDE.
The second concern is that the simulation requires heavy use of complex valued matrices. Since I'm on windows and the only reasonably well developed matrix library doesn't run on windows I would be forced to use the FFI to bring in various BLAS and LAPACK routines to support this. I've convinced myself that this is quite possible, if somewhat tedious by virtue of the unpleasant array access syntax for mutable arrays.
The third and final concern is the point of this post. How does one handle state efficiently in Haskell? I've seen the various state monads and gained a superficial enough understanding to be concerned about how useful they are, for the following reason:
I would like to aggregrate a large number of state variables (possibly in the hundreds of variables) into a few data structures. These structures would not only contain basic variable types, but probably some rather large mutable arrays. So lets say I have such a structure called world and I wish to update just 1 entry. If I do w=world{entry=newentry}, the entire enormous world structure is copied to w.
If I bury world in a state monad, then inside a do loop it appears that the get function extracts the entire world state and the set function writes it back into the monad after I've altered it. It still seems to me that the entire structure is copied again to achieve this. I'm not sure if this is true or not. Perhaps the compiler can pull apart the aggregation to fix this issue, but I'm not sure if such an optimization is performed. The only other thing I could think of would be to somehow create get and set functions for every variable in the aggregation, which also would be impossibly tedious.
It is possible for me to structure the program so that most of the simulation parameters are set once by the user and then never changed during the rest of the program operation, although incremental state updates are a bit more efficient than this approach. To make this reasonably clean I would probably do some kind of unsafe extraction out of the IO monad to get my input variables, which would then not be changed for the rest of the simulation, although many of the matrices, themselves embedded in the IO monad would have to change incrementally as the simulation progresses. Right now I would favor the latter approach, if I stay with Haskell, but so far it's not clear to me that Haskell is 'convenient' for this kind of development, though I would like to be proven wrong. I am also looking at D or possibly LUA+C for this task, but LUA is not much faster than Matlab.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Hello Matthew, Monday, May 29, 2006, 1:38:38 AM, you wrote:
The third and final concern is the point of this post. How does one handle state efficiently in Haskell? I've seen the various state monads and gained a superficial enough understanding to be concerned about how useful they are, for the following reason:
I would like to aggregrate a large number of state variables (possibly in the hundreds of variables) into a few data structures. These structures would not only contain basic variable types, but probably some rather large mutable arrays. So lets say I have such a structure called world and I wish to update just 1 entry. If I do w=world{entry=newentry}, the entire enormous world structure is copied to w.
use RealWorld :) IORef and StorableArray are you best friends. after all, it's not good idea to work with StorableArray otherwise than via the IO monad. i think you should create separate thread for each part of your simulation and send data between them through Channels -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
hi,
Bulat, i quote the doc for Data.Array.Storable :
"It is similar to IOUArray but slower. Its advantage is that it's
compatible with C."
So you speak about Storable because Matthew wants to use BLAS and LAPACK ?
Cheers,
mt
2006/5/29, Bulat Ziganshin
Hello Matthew,
Monday, May 29, 2006, 1:38:38 AM, you wrote:
The third and final concern is the point of this post. How does one handle state efficiently in Haskell? I've seen the various state monads and gained a superficial enough understanding to be concerned about how useful they are, for the following reason:
I would like to aggregrate a large number of state variables (possibly in the hundreds of variables) into a few data structures. These structures would not only contain basic variable types, but probably some rather large mutable arrays. So lets say I have such a structure called world and I wish to update just 1 entry. If I do w=world{entry=newentry}, the entire enormous world structure is copied to w.
use RealWorld :) IORef and StorableArray are you best friends. after all, it's not good idea to work with StorableArray otherwise than via the IO monad. i think you should create separate thread for each part of your simulation and send data between them through Channels
-- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Hello minh, Monday, May 29, 2006, 2:01:29 PM, you wrote:
hi,
Bulat, i quote the doc for Data.Array.Storable : "It is similar to IOUArray but slower. Its advantage is that it's compatible with C." So you speak about Storable because Matthew wants to use BLAS and LAPACK ?
of course. IOUArray can't be used together with external libs. and if someone need this fast speed together with FFI, he can switch to ghc 6.5 or use module i attached here -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
How hard would it be to build 6.5 on a windows box without visual studio 2003? Regards Bulat Ziganshin wrote:
Hello minh,
Monday, May 29, 2006, 2:01:29 PM, you wrote:
hi,
Bulat, i quote the doc for Data.Array.Storable : "It is similar to IOUArray but slower. Its advantage is that it's compatible with C." So you speak about Storable because Matthew wants to use BLAS and LAPACK ?
of course. IOUArray can't be used together with external libs. and if someone need this fast speed together with FFI, he can switch to ghc 6.5 or use module i attached here
Hello Matthew, Monday, May 29, 2006, 7:38:40 PM, you wrote:
How hard would it be to build 6.5 on a windows box without visual studio 2003?
there are prebuilt installations at GHC site, last of those is http://www.haskell.org/ghc/dist/current/dist/ghc-6.5.20060328-i386-unknown-m... (btw, ghc compiled by gcc, not msvc. they use VS only for their additional IDE project) but you don't need 6.5 if time-consuming operations will be implemented via C functions. using StorableArray slowdowns only access to these arrays inside of Haskell code -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
What is the difference between the ForeignArray defined in this source and the StorableArray? The source code of both modules are very similar. Bulat Ziganshin wrote:
Hello minh,
Monday, May 29, 2006, 2:01:29 PM, you wrote:
hi,
Bulat, i quote the doc for Data.Array.Storable : "It is similar to IOUArray but slower. Its advantage is that it's compatible with C." So you speak about Storable because Matthew wants to use BLAS and LAPACK ?
of course. IOUArray can't be used together with external libs. and if someone need this fast speed together with FFI, he can switch to ghc 6.5 or use module i attached here
Hello Matthew, Monday, May 29, 2006, 8:04:56 PM, you wrote:
What is the difference between the ForeignArray defined in this source and the StorableArray? The source code of both modules are very similar.
the devil in details :) - StorableArray in 6.4 is slow because it uses ForeignPtr. there are two possible solutions - either speed up ForeignPtr (done in 6.5) or use Ptr instead of ForeignPtr (used in my module). of course in this case you lose all the benefits of ForeignPtr's and in particular you will need to make explicit 'free' if you create such array via 'newArray' or it's derivatives. if you create such array via 'unsafePtrToForeignArray', then you don't need to make any additional steps to free it's memory besides of that required for StorableArray (i.e. in most cases it's the problem of FFI library you are used) simply speaking, if you don't create ForeignArray on the Haskell side, it's as simple in use as StorableArray and as fast as IOUArray -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
If possible I'd like to memory manage on the Haskell side. All of the calls to BLAS and LAPACK that I'm aware of assume that all arrays are allocated outside of the C or Fortran that implement the matrix algorithms. They never return buffers to newly allocated arrays. So what I'd like to do is something like allocate an array in Haskell, freeze it and extract a pointer, send it to the C code, and then unfreeze it. That way I benefit from Haskell's garbage collector. Explicitly managing memory is a huge bug generator in C and C++. In fact I'd say it's number one on the list. So can I modify Foreign Array to achieve this, or do I just end up with essentially a Storable Array? Maybe it would be just easier to use 6.5, though heaven knows what sorts of bugs may be lurking there. I downloaded it already per your link. Bulat Ziganshin wrote:
Hello Matthew,
Monday, May 29, 2006, 8:04:56 PM, you wrote:
What is the difference between the ForeignArray defined in this source and the StorableArray? The source code of both modules are very similar.
the devil in details :) - StorableArray in 6.4 is slow because it uses ForeignPtr. there are two possible solutions - either speed up ForeignPtr (done in 6.5) or use Ptr instead of ForeignPtr (used in my module). of course in this case you lose all the benefits of ForeignPtr's and in particular you will need to make explicit 'free' if you create such array via 'newArray' or it's derivatives. if you create such array via 'unsafePtrToForeignArray', then you don't need to make any additional steps to free it's memory besides of that required for StorableArray (i.e. in most cases it's the problem of FFI library you are used)
simply speaking, if you don't create ForeignArray on the Haskell side, it's as simple in use as StorableArray and as fast as IOUArray
Hello Matthew, Monday, May 29, 2006, 10:54:36 PM, you wrote:
If possible I'd like to memory manage on the Haskell side. All of the calls to BLAS and LAPACK that I'm aware of assume that all arrays are allocated outside of the C or Fortran that implement the matrix algorithms. They never return buffers to newly allocated arrays. So what I'd like to do is something like allocate an array in Haskell, freeze it and extract a pointer, send it to the C code, and then unfreeze it. That way I benefit from Haskell's garbage collector. Explicitly managing memory is a huge bug generator in C and C++. In fact I'd say it's number one on the list.
So can I modify Foreign Array to achieve this, or do I just end up with essentially a Storable Array?
you should use StorableArray. the speed drawbacks is larger overhead for each access to array in Haskell code, including uses of withStorableArray to call FFI operations. as far as most of your usage of these arrays is to pass their addresses to FFI calls that process many data (as opposite to FFI calls that process just several elements), you will see no much penalty
Maybe it would be just easier to use 6.5, though heaven knows what sorts of bugs may be lurking there. I downloaded it already per your link.
you can try to compile with it just to compare speed. then you will know how much you are lose (sorry for my awkward english) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
participants (4)
-
Alberto Ruiz -
Bulat Ziganshin -
Matthew Bromberg -
minh thu