Re: [Haskell-cafe] lookup tables style guidelines
Don Stewart [EMAIL PROTECTED] writes: 1) what is the most performant lookup table/hashtable/dictionary solution for Haskell? Data.IntMap is awfully good. Is it benchmarked anywhere? Compared to the Judy bindings, or Adrian Hey's AVL trees, or Data.Hashtable? I rewrote (roughly) a Python program in Haskell, and it was my impression back then that Python's associative arrays was faster than Haskell maps - but this could well have been back in the FiniteMap days, and I don't think I benchmarked very precisely. Anyway, there's a Google Summer-of-code project that will hopefully produce some benchmarks of the different alternatives. Data.Map tends to consume a lot of memory as well. But - Data.(Int)Map is likely to be the easiest available - I'd try that first, and if things are still too slow, profile, and then look for alternatives. -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] lookup tables style guidelines
On Apr 24, 2008, at 2:31 , Ketil Malde wrote: Don Stewart [EMAIL PROTECTED] writes: 1) what is the most performant lookup table/hashtable/ dictionary solution for Haskell? Data.IntMap is awfully good. Is it benchmarked anywhere? Compared to the Judy bindings, or Adrian Hey's AVL trees, or Data.Hashtable? I don't know if anyone has benched them recently, but some time back there was a comparison of Data.HashTable, Data.Map, and Data.IntMap posted to one of the Haskell lists; HashTable was usually the slowest, and IntMap the fastest because it could take advantage of optimizations due to the key being a specific type (among other things, IIRC it's unboxed). This also reduces the memory usage compared to the more general Data.Map. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] [EMAIL PROTECTED] system administrator [openafs,heimdal,too many hats] [EMAIL PROTECTED] electrical and computer engineering, carnegie mellon universityKF8NH ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] How to define tail function for Even/Odd GADT lists?
On Wed, 23 Apr 2008, Iavor Diatchki wrote: Hello, I am not sure of the use case here but you could also do the following: data EvenList a = Nil | ConsE a (OddList a) data OddList a = ConsO a (EvenList a) Or just use: http://darcs.haskell.org/event-list/src/Data/AlternatingList/List/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] mapM vs mapM_ performance
On Tue, Apr 22, 2008 at 11:32 AM, Ben [EMAIL PROTECTED] wrote: Hello Haskellers, I'm running ghc 6.8.2 on vista 64. Consider the following program, which is compiled with -02 -prof -auto-all: module Main where import System.IO (openFile, IOMode(..), hPutStr) testlst = let ls = [(i, [(j, (fromIntegral j)::Float) | j - [1..5]::[Int]]) | i - [1..50]::[Int]] in ls main2 = do h - openFile bardump WriteMode mapM_ ((hPutStr h) . show) testlst main = do h - openFile bardump2 WriteMode mapM ((hPutStr h) . show) testlst return () main and main2 are different in only that mapM_ versus mapM_ are used. But the mapM version runs about 20x slower! I'm running with +RTS -p -hc -RTS and I see that the amount of memory allocated is about the same, and I think the resident memory is about the same too. But the mapM_ version runs in about 8.7 seconds, and the mapM version takes 167 seconds. My first guess is that the garbage collector is not running at all in the mapM_ version, but is working it's ass off in the mapM version cleaning up the list that will never be used. You may ask, why use mapM if you're discarding the values? Unfortunately in my real app I need the values, which are more interesting than IO (). If you need the values, then you've got to pay that price I suppose. If you need the values, I'm going to take a stab that in your real app you use a lot of memory because of this (because presumably you're keeping the values around), whereas you're just seeing a speed hit on this small test program. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] lookup tables style guidelines
What are good options for concurrent dictionaries? A while ago i wrote a concurrent hash table prototype, but there are probably better solutions for Haskell. Regards, Felix ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Fw: I have a problem
I have a problem which i can'tsolve. Is there any one who has an idea? Two lists is sent as parameter to a function. If second list contains first list, return true, else return false. This comparision must be in order of first list. You can look at examples. function type as follows: sublist:: [a] - [a] - Bool examples: For instance [2,4,5]list is sub list of [3,7,2,4,5,9] list but not of[3,7,4,2,5,9] list. sublist [2,8][1,5,6,2,4,7,8,2] False sublist [1,2,3][0,1,2,3,4,5,6] True sublist [5,4] [1,4,5,7,8,3,5,4] True sublist [1,2,4,3,4,5,7,8,9,5] [8,2,3,1,2,4,3,4,5,7,8,9,5,1,6,2] True Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] functional update
On Tue, Apr 22, 2008 at 6:26 AM, Henning Thielemann
[EMAIL PROTECTED] wrote:
On Mon, 21 Apr 2008, Ryan Ingram wrote:
I recommend this blog entry:
http://twan.home.fmf.nl/blog/haskell/overloading-functional-references.details
along with a few additional combinators for imperative update:
data FRef s a = FRef
{ frGet :: s - a
, frSet :: a - s - s
}
http://darcs.haskell.org/record-access/src/Data/Accessor.hs
http://darcs.haskell.org/record-access/src/Data/Accessor/Example.hs
I should upload this to Hackage, I know ...
Not to toot my own horn, but there's already something like this on
hackage:
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/data-accessor-0.0.1
Which has template haskell routines for generating accessors for
record types also.
Luke
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Fw: I have a problem
First, I'd refer you to this list's rules on homework, and what people will or won't answer. Secondly to that though, rather than provide a solution, I'll give you an idea that may lead to you coming up with a solution. First, try and write a function that can test if your first list is at the start of the second list: startlist [2,3] [2,3,4,5] True startlist [2,3] [1,2,3,4] False Then use this function to write your sublist function. Hope that helps Tom Davie On 24 Apr 2008, at 10:29, cetin tozkoparan wrote: I have a problem which i can't solve. Is there any one who has an idea? Two lists is sent as parameter to a function. If second list contains first list, return true, else return false. This comparision must be in order of first list. You can look at examples. function type as follows: sublist:: [a] - [a] - Bool examples: For instance [2,4,5] list is sub list of [3,7,2,4,5,9] list but not of [3,7,4,2,5,9] list. sublist [2,8] [1,5,6,2,4,7,8,2] False sublist [1,2,3] [0,1,2,3,4,5,6] True sublist [5,4] [1,4,5,7,8,3,5,4] True sublist [1,2,4,3,4,5,7,8,9,5] [8,2,3,1,2,4,3,4,5,7,8,9,5,1,6,2] True Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now.___ 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
[Haskell-cafe] Re: Stronger STM primitives needed? Or am I just doing it wrong?
David Roundy wrote: A simple primitive to do this (in combination with a totally rewritten STM runtime) would be subatomically :: ReadOnlySTM a - STM () which would run a STM computation that is guaranteed to have no side-effects (i.e. can't write to TVars) and ignore its results (and let the runtime know that the results have been ignored). Matthew Brecknell wrote: Nevertheless, the distinction between read-only and read-write transactions does not necessarily have to occur at the level of types. STM is fundamentally a dynamic approach to concurrency control, so I think it would make sense for transactions to *dynamically* determine whether they are read-only or read-write, as they compose with each other. In that case, we can treat subatomic as a hint to the STM runtime. subatomic :: STM a - STM () Concerning this question of whether the argument to subatomic should statically or dynamically be known to be read-only, there is also the option of collapsing ReadOnlySTM a and STM a by changing the semantics of writeTVar . I mean, writeTVar can be used for two different things: 1) communicate with other threads, i.e. crossing atomically boundaries 2) communicating inside a single thread/STM action à la mutable state (IORef). We only want 1), but 2) is expendable, we can always use parameters to pass state around or wrap the whole thing into a state monad. For 1), it's enough to have a primitive scheduleWriteTVar :: TVar a - a - STM () that ensures to write the TVar at the very end of the atomically block. (This is similar to scheduleIO :: IO a - STM ()). In other words, the current STM semantics can be implemented in terms of ReadOnlySTM assuming that the latter has such a primitive for scheduling. type ReadOnlySTM a = StateT TVarEnvironment STM a Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Stronger STM primitives needed? Or am I just doing it wrong?
Ryan Ingram wrote: No spooky-action-at-a-distance is possible. David's more general subatomically primitive would achieve the same results; the proof is that (1) no side effects can be caused by the subatomic action, that is, no writes happen which could change future reads. (2) the result of the computation is ignored -except- for whether it retries or returns, that is, it can't affect the control flow of the rest of the transaction. So, if have a transaction T that is waiting inside retry for a variable that it read to change, and a variable that is only accessed in a subatomic part of T is changed, we can try running the subatomic computation first. Here are the four cases: 1) The subatomic computation succeeded before and still succeeded. Then we know the end result of the computation is unaffected, and will still retry. No need to do anything. 2) The subatomic computation succeeded before and now fails (calls 'retry' or retryRO'). Then we know that the computation will now fail at this earlier point. Mark the change to fail in the transaction log and leave the computation in the waiting for retry state. 3) The subatomic computation failed before and still fails. See (1) 4) The subatomic computation failed before and now succeeds. The result of the entire computation can change, we should now re-run the entire computation. Sounds good. But I wonder what obscure optimization comes next; can we have a toy-model of STM? I mean, it should be possible to express both the continuation-logging and read-only-fail optimization in terms of type STM a = Maybe a or similar? Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Infix search (Was: I have a problem)
On Thu, 24 Apr 2008, cetin tozkoparan wrote: I have a problem which i can'tsolve. Is there any one who has an idea? Two lists is sent as parameter to a function. If second list contains first list, return true, else return false. This comparision must be in order of first list. You can look at examples. function type as follows: sublist:: [a] - [a] - Bool try 'List.tails' and 'List.isPrefixOf' ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Stronger STM primitives needed? Or am I just doing it wrong?
On Thu, 24 Apr 2008 12:57:56 +0200, apfelmus wrote: there is also the option of collapsing ReadOnlySTM a and STM a by changing the semantics of writeTVar . I mean, writeTVar can be used for two different things: 1) communicate with other threads, i.e. crossing atomically boundaries 2) communicating inside a single thread/STM action à la mutable state (IORef). We only want 1), but 2) is expendable, we can always use parameters to pass state around or wrap the whole thing into a state monad. For 1), it's enough to have a primitive scheduleWriteTVar :: TVar a - a - STM () that ensures to write the TVar at the very end of the atomically block. Unfortunately, though, this breaks the very thing that makes STM attractive: namely, composability. Now in order to work with a TVar, I need to know whether anything that came before me might have modified it, and if so take the current value as a parameter instead of reading it like normal. Or am I misunderstanding something? -- Chris Smith ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Call for Contributions - Haskell Communities and Activities Report, May 2008 edition
Dear Haskellers, so much has happened in the Haskell world in the past months. Therefore, we would very much like to collect contributions for the 14th edition of the Haskell Communities Activities Report http://www.haskell.org/communities/ Submission deadline: 10 May 2008 (please send your contributions to hcar at haskell.org, in plain text or LaTeX format) This is the short story: * If you are working on any project that is in some way related to Haskell, please write a short entry and submit it to the us. Even if the project is very small or unfinished or you think it is not important enough -- please reconsider and submit an entry anyway! * If you are interested in any project related to Haskell that has not previously been mentioned in the HCA Report, please tell us, so that we can contact the project leaders and ask them to submit an entry. * Feel free to pass on this call for contributions to others that might be interested. More detailed information: The Haskell Communities Activities Report is a bi-annual overview of the state of Haskell as well as Haskell-related projects over the last, and possibly the upcoming 6 months. If you have only recently been exposed to Haskell, it might be a good idea to browse the December 2007 edition -- you will find interesting topics described as well as several starting points and links that may provide answers to many questions. Contributions will be collected until the submission deadline. They will then be compiled into a coherent report that is published online as soon as it is ready. As always, this is a great opportunity to update your webpages, make new releases, announce or even start new projects, or to talk about developments you want every Haskeller to know about! As the purpose of the report is to collect recent or current activities, we encourage you to update all existing summaries and reports. We will probably drop any topics that have not had any activity for the past year, i.e., since May 2007, but we would very much prefer you to present an updated description of the topic. Of course, new entries are more than welcome. Reports should generally be kept brief and informative, ranging from a few sentences to a few hundred words, to keep the whole report reasonably sized. Looking forward to your contributions, Andres and Janis (current editors) FAQ: Q: Which topics are relevant? A: *All* topics which are related to Haskell in some way are relevant. We usually had reports from users of Haskell (private, academic, or commercial), from authors or contributors to projects related to Haskell, from people working on the Haskell language, libraries, on language extensions or variants. We also like reports over distributions of Haskell software, Haskell infrastructure, books and tutorials on Haskell. Reports on past and upcoming events related to Haskell are also relevant. Finally, there might be new topics we don't even think about. As a rule of thumb: if in doubt, then it probably is relevant and has a place in the HCAR. You can also ask the editors. Q: Is unfinished work relevant? Are ideas for projects relevant? A: Yes! You can use the HCAR to talk about projects you are currently working on. You can use it to look for other developers that might help you. You can use it to write ``wishlist'' items for libraries and language features you would like to see implemented. Q: How much should I write? A: There's no formal limit. But generally, entries should be short and to the point. A general introduction is helpful. Apart from that, you should focus on recent or upcoming developments. There also is no minimum length of an entry! The report aims at being as complete as possible, so please consider writing an entry, even if it's only a few lines long. Q: If I don't update my entry, but want to keep it in the report, what should I do? A: Tell us that there are no changes. We will reuse the old entry in this case, but we might drop it if it's older than a year, to give more room and more attention to projects that change a lot. Don't resent complete entries if you haven't changed them. Q: What format should I write in? A: The best format is a LaTeX source file, adhering to the template that's available at: http://haskell.org/communities/05-2008/template.tex There's also a LaTeX style file at http://haskell.org/communities/05-2008/hcar.sty that you can use to preview your entry. If you don't know LaTeX, then use plain text. If you modify an old entry, we will send you your old entry as a template within the next hours (provided we have your valid email address). Please modify that template, rather than using your own version of the old entry as a template. Don't worry about writing correct LaTeX, we will be
Re: [Haskell-cafe] lookup tables style guidelines
Ketil Malde wrote: Don Stewart [EMAIL PROTECTED] writes: 1) what is the most performant lookup table/hashtable/dictionary solution for Haskell? Data.IntMap is awfully good. Is it benchmarked anywhere? Compared to the Judy bindings, or Adrian Hey's AVL trees, or Data.Hashtable? I must get around to putting the AVL clones of Data.Map/Set in Hackage sometime. Meanwhile anyone wanting to roll their own maps with an API of their chosing could do a lot worse than the raw AVL lib.. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/AvlTree-3.1 Also, if you're likely to be using union/intersection a lot you should know that Data.Map/Set are very slow for this because they use the not efficient hedge algorithm :-) There's a really cool demo I found from wikipedia that shows why it is that AVL trees perform so well in the pathological situation of sorted insertions.. http://www.csi.uottawa.ca/~stan/csi2514/applets/avl/BT.html If you try it you can see that after 2^n-1 sorted insertions you always get a perfectly balanced tree. This explains these benchmark results.. http://groups.google.co.uk/group/comp.lang.functional/msg/74a422ea04ff1217 DData is what became Data.Map/Set and it would appear to be the worst performing of the four tree types tested there :-( Don is right about Data.IntMap/IntSet. For Ints it will be much faster than Data.Map/Set or even (polymorphic) AVL tree. But an AVL tree of unboxed Ints gives faster lookup than IntMap/Set and about the same insert/delete times.. http://www.haskell.org/pipermail/libraries/2005-October/004518.html Union and Intersection times for AVL aren't so great, but I think I know what to do about that (especially intersection). But the real way ahead has to be Tries for non-trivial keys and (I suspect) AVL trees of unboxed Ints for simple keys (serialisable as 1 machine word). This is what that GSoC project is all about. At the moment we have the exact opposite, Tries for Ints and balanced trees for non-trivial keys. Oh well.. Regards -- Adrian Hey ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] curl binding examples?
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 i was once given this snippet with reference to an earlier incarnation of the curl bindings: http://hpaste.org/3529 my guess is that this is no longer accurate documentation (?) anything that could be provided in the way of examples would be nice, i have placed a stub here: http://haskell.org/haskellwiki/Network.Curl it would be nice of people inlined small examples directly into the haddock docs for libraries. putting a minimal hello world example illustrating the basics of a library would preclude 90% of the followup questions on lists and irc. -BEGIN PGP SIGNATURE- Version: GnuPG v2.0.8 (FreeBSD) iEYEARECAAYFAkgQrvMACgkQxRg3RkRK91NuEQCfUdInLYcjioLRsHfYGkwMW2Dp jI8An3uEuuF/aaXimZwhweJJ4zGz3CsY =qs80 -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Stronger STM primitives needed? Or am I just doing it wrong?
Chris Smith wrote: apfelmus wrote: For 1), it's enough to have a primitive scheduleWriteTVar :: TVar a - a - STM () that ensures to write the TVar at the very end of the atomically block.. Unfortunately, though, this breaks the very thing that makes STM attractive: namely, composability. Now in order to work with a TVar, I need to know whether anything that came before me might have modified it, and if so take the current value as a parameter instead of reading it like normal. Or am I misunderstanding something? You're correct, that's what I meant. But it's nothing more and nothing less than the purely functional way of dealing with mutable state, isn't it? And you need a parameter anyway, namely the TVar a itself. I mean, when it's in scope like in do a - readTVar v writeTVar v (a+1) readTVar v you don't need a parameter. But if the do-block is broken up into functions, you need a parameter foo v = do a - readTVar v writeTVar v (a+1) bar v bar v = readTVar v and you may as well supply its value instead of the reference v . Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] announce: Glome.hs-0.3 (Haskell raytracer)
Jim Snow wrote: Those are good links. It's good to see that the groups of people who know about Haskell and people who know about ray tracing do, in fact, overlap. Background information for everyone else: Wald's work is related to OpenRT, which is an OpenGL-like api for interactive ray tracing (despite the name, it is not, in fact, open source). OpenRT makes for stiff competition. Arauna (http://igad.nhtv.nl/~bikker/) is very impressive, as well. On the other end of the spectrum, there's POV-Ray, which isn't known for its speed, but it is very flexible in the kinds of things it can render and can generate some fairly realistic images. Unlike most real-time ray tracers, which only render triangles, POV-Ray can render native representations of spheres, cones, toruses, heightfields, julia fractals, and a few dozen other kinds of primitives. Pbrt (http://www.pbrt.org/) is another renderer, more modern than POV-Ray, that focuses more on output quality than speed. Wow. The POV-Ray guys are talking about Haskell [or rather, my personal addiction to it] and the Haskell guys are talking about POV-Ray... on the same day... How unlikely is that? ;-) I've been using POV-Ray for a long time. I like it for several reasons: 1. It's the only program I've ever seen [on a PC] that does ray tracing. [I'm sure there must be others...] 2. It's the only program I've seen that can render *real* curves, not fake trickery with triangle meshes. 3. It can render *arbitrary* mathematical surfaces. Want to render a 3D slice of the 4D cubic Mandelbrot set? No problem! 4. It has a novel scene description language, which does far more than describe scenes. It's Turing-complete, and you can build physics engines with it. [It's painfully slow though!] Basically, as a maths addict, POV-Ray appeals to me. However, there are problems... The scene description language is basically a macro expansion language, and is chronically poor in data types and control structures. (The worst thing about Haskell is that IT MAKES YOU HATE NORMAL LANGUAGES!) Preserving complex scene state from frame to frame in an animation is notoriously tedious to code. Certain features are accessed in unintuitive ways to avoid breaking backwards compatibility. Overall, you tend to spend a lot of time saying which effects to simulate. [Not all of them matter for a given scene, so some can be left out - thus saving on speed!] I dislike such clutter. For no objective reason. The POV-Ray team is currently working on the first multi-threaded version. [After years of saying it would never happen.] It's taking a while. (That's partly because the developers take product quality very seriously.) It should be interesting when it's done, but it's still taking a while. Personally, I'd quite like to write my own ray tracer to address some of these limitations. But every time I try, I end up hitting design issues [Haskell works very differently to Java] or performance issues [which I don't even know how to begin debugging]. Not to mention that POV-Ray uses sophisticated techniques like volume bounding that I know nothing about. (There's nothing like using an inherantly superior algorithm to make your code orders of magnitude faster...) Simon Marlow wrote: There's definitely a bug here, regardless of whether this example demonstrates it. Use of par shouldn't introduce a space leak, and currently it can. (fortunately I'm fixing it as we speak...) Cheers, Simon Oh, good. Indeed - yay for Simon! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] announce: Glome.hs-0.3 (Haskell raytracer)
I've ended up writing something more like POV-Ray than OpenRT, and that's fine with me. I'd rather have something that's slower but more expressive than fast but inflexible. (The former is also perhaps more easily attainable, particularly in Haskell.) Not knowing anything about raytracing, one of the things I found interesting about the paper was that he claimed that the speedups were from using coherent ray packets, and that the shader model was orthogonal, and enough much is spent raycasting that the shader code to make much difference. The implication was that you could graft a packet style raycasting engine onto even povray and give it a nice speed boost... though you might have to lose the nifty real shapes to tessellated approximations. Is this accurate? True but reality is more complicated? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] announce: Glome.hs-0.3 (Haskell raytracer)
On Thursday 24 April 2008 20:29:50 Andrew Coppin wrote: 2. It's the only program I've seen that can render *real* curves, not fake trickery with triangle meshes. What you called fake trickery with triangle meshes is the core of all modern computer graphics. Focussing on ray tracing instead of that is rather missing the point, IMHO. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/products/?e ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
a faster, accumulating mapM (was Re: [Haskell-cafe] mapM vs mapM_ performance)
Hello Luke and other Haskellers,
Thanks for the reply, but as I noted before, the amount of memory
allocated (and resident) is roughly the same. Anyhow it's definitely
not a GC issue because I wrote an accumulating version of mapM and got
close to mapM_ 's performance.
In the code below, main1 is mapM_, main2 is the current mapM
(basicallly sequence . map), map3 is a hand-coded accumulating
parameter version, mapM2 is the accumulating parameter mapM and main4
uses mapM2. The timings I get are about 15, 175, 20 and 20 seconds
for main1, main2, main3 and main4 respectively. main2 uses about 2%
less memory than main3 or main4 on this particular run, though I don't
know if that is true generally.
Unless someone can see a reason why mapM2 is not as good as mapM, can
I suggest replacing the implementation of mapM by the implementation
of mapM2. A 10x speedup seems to be a bigger deal than GCing 2% more
memory.
best regards, Ben
module Main where
import System.IO (openFile, IOMode(..), hPutStr)
testlst = let ls = [(i, [(j, (fromIntegral j)::Float) | j -
[1..5]::[Int]]) | i - [1..50]::[Int]]
in ls
main = do
h - openFile bardump WriteMode
mapM_ ((hPutStr h) . show) testlst
main2 = do
h - openFile bardump2 WriteMode
result - mapM ((hPutStr h) . show) testlst
print $ length result
main3 = do
h - openFile bardump3 WriteMode
result - dump h testlst []
print $ length result
where dump h (x:xs) accum = do
hPutStr h $ show x
dump h xs $ ():accum
dump _ [] accum = return accum
mapM2 :: Monad m = (a - m b) - [a] - m [b]
{-# INLINE mapM2 #-}
mapM2 fn lst = mapM2accum fn lst []
where mapM2accum _ [] accum = return accum
mapM2accum fn (x:xs) accum = do
r - fn x
mapM2accum fn xs (r:accum)
main4 = do
h - openFile bardump2 WriteMode
result - mapM2 ((hPutStr h) . show) testlst
print $ length result
On Thu, Apr 24, 2008 at 1:37 AM, Luke Palmer [EMAIL PROTECTED] wrote:
On Tue, Apr 22, 2008 at 11:32 AM, Ben [EMAIL PROTECTED] wrote:
Hello Haskellers,
I'm running ghc 6.8.2 on vista 64. Consider the following program,
which is compiled with -02 -prof -auto-all:
module Main where
import System.IO (openFile, IOMode(..), hPutStr)
testlst = let ls = [(i, [(j, (fromIntegral j)::Float) | j -
[1..5]::[Int]]) | i - [1..50]::[Int]]
in ls
main2 = do
h - openFile bardump WriteMode
mapM_ ((hPutStr h) . show) testlst
main = do
h - openFile bardump2 WriteMode
mapM ((hPutStr h) . show) testlst
return ()
main and main2 are different in only that mapM_ versus mapM_ are used.
But the mapM version runs about 20x slower! I'm running with +RTS -p
-hc -RTS and I see that the amount of memory allocated is about the
same, and I think the resident memory is about the same too. But the
mapM_ version runs in about 8.7 seconds, and the mapM version takes
167 seconds.
My first guess is that the garbage collector is not running at all in
the mapM_ version, but is working it's ass off in the mapM version
cleaning up the list that will never be used.
You may ask, why use mapM if you're discarding the values?
Unfortunately in my real app I need the values, which are more
interesting than IO ().
If you need the values, then you've got to pay that price I suppose.
If you need the values, I'm going to take a stab that in your real app
you use a lot of memory because of this (because presumably you're
keeping the values around), whereas you're just seeing a speed hit on
this small test program.
Luke
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: a faster, accumulating mapM (was Re: [Haskell-cafe] mapM vs mapM_ performance)
Hello Ben,
Friday, April 25, 2008, 1:14:17 AM, you wrote:
mapM2 :: Monad m = (a - m b) - [a] - m [b]
{-# INLINE mapM2 #-}
mapM2 fn lst = mapM2accum fn lst []
where mapM2accum _ [] accum = return accum
mapM2accum fn (x:xs) accum = do
r - fn x
mapM2accum fn xs (r:accum)
it seems you forget to reverse accum before returning it?
--
Best regards,
Bulatmailto:[EMAIL PROTECTED]
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: a faster, accumulating mapM (was Re: [Haskell-cafe] mapM vs mapM_ performance)
Hi Ben,
mapM2 :: Monad m = (a - m b) - [a] - m [b]
{-# INLINE mapM2 #-}
mapM2 fn lst = mapM2accum fn lst []
where mapM2accum _ [] accum = return accum
mapM2accum fn (x:xs) accum = do
r - fn x
mapM2accum fn xs (r:accum)
Not that it should matter for performance any, but you really ought to
reverse the result list too, or compute the accumulator in the right
order. :-)
mapM2 :: Monad m = (a - m b) - [a] - m [b]
{-# INLINE mapM2 #-}
mapM2 fn lst = mapM2accum fn lst id
where mapM2accum _ [] accum = return $ accum []
mapM2accum fn (x:xs) accum = do
r - fn x
mapM2accum fn xs (accum . (r:))
Cheers,
/Niklas
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: a faster, accumulating mapM (was Re: [Haskell-cafe] mapM vs mapM_ performance)
Hello Niklas, Friday, April 25, 2008, 1:25:39 AM, you wrote: Not that it should matter for performance any, but you really ought to reverse the result list too, or compute the accumulator in the right order. :-) unfortunately, this affects performance too. reverse costs one more scan through the list and building lot of thunks has its own space and time cost -- Best regards, Bulatmailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Terminal manipulation in windows?
I have a program that requires the user to be in raw mode. This doesn't seem to be an issue on linux, but in Windows, it's a bit tricky (System.Posix.Terminal isn't an option). Is there a possible way to set this in Haskell? Or even outside of Haskell? It doesn't appear cygwin has a raw mode. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Help me refactor this type!
More FRP stuff: a new type for Future that came to me in an inspiration this morning. But it's ugly and I need someone with better theoretical underpinnings than me to tell me what I've really built :) data Future t a = Known t a | Unknown (t - IO (STM (Maybe (Future t a Given Eq t, Ord t, Bounded t, this type is at least member of Monad, Applicative, Functor, and MonadPlus/Monoid. But the derivation gives me that needs refactoring feeling; here's an example: force :: (Ord t, Bounded t) = Future t a - IO (t, a) force (Known t a) = return (t, a) force (Unknown f) = do stmF - f maxBound mF - atomically stmF case mF of Nothing - return (maxBound, error never) Just fut' - force fut' delayF :: Ord t = t - Future t a - Future t a delayF t0 (Known t a) = Known (max t0 t) a delayF t0 (Unknown f) = Unknown $ \t - fmap (fmap (fmap (delayF t0))) (f t) instance (Ord t, Bounded t) = Monad (Future t) where return = Known minBound Known t a = g = delayF t (g a) Unknown f = g = Unknown $ \t - do -- IO stmF - f t return $ do -- STM mF - stmF return $ do -- Maybe fut' - mF return (fut' = g) This code makes me sad; so many nested blocks. There's got to be a refactoring of this that I am missing! It's clearly got something to do with Fix, Either, ReaderT, and MaybeT, and type composition, but none of those seem to answer the whole question. Any thoughts? -- ryan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: a faster, accumulating mapM (was Re: [Haskell-cafe] mapM vs mapM_ performance)
On the test case i'm running the performance impacts of reversing the
return list are negligible:
mapM3 :: Monad m = (a - m b) - [a] - m [b]
{-# INLINE mapM3 #-}
mapM3 fn lst = mapM3accum fn lst []
where mapM3accum _ [] accum = return $ reverse accum
mapM3accum fn (x:xs) accum = do
r - fn x
mapM3accum fn xs (r:accum)
main5 = do
print $ length $ mapM_ (flip replicate ()) [1..11]
time ~ 18 seconds (about the same, faster on my machine probably due
to timing artifacts) and the memory was about the same (strangely less
than the non-reversing one though again that's probably an artifact.)
In any case, I have some questions:
1) Why is the Prelude mapM so slow? It seems like running 10x slower
than mapM_ when generating only 50,000 return values is a problem.
2) Is there a reason to not use mapM3 above?
Thanks and take care, Ben
On Thu, Apr 24, 2008 at 2:33 PM, Bulat Ziganshin
[EMAIL PROTECTED] wrote:
Hello Niklas,
Friday, April 25, 2008, 1:25:39 AM, you wrote:
Not that it should matter for performance any, but you really ought to
reverse the result list too, or compute the accumulator in the right
order. :-)
unfortunately, this affects performance too. reverse costs one more scan
through the list and building lot of thunks has its own space and time
cost
--
Best regards,
Bulatmailto:[EMAIL PROTECTED]
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: a faster, accumulating mapM (was Re: [Haskell-cafe] mapM vs mapM_ performance)
On Thu, Apr 24, 2008 at 11:28 PM, Ben [EMAIL PROTECTED] wrote: 2) Is there a reason to not use mapM3 above? Yes, there certainly is. mapM3 is not equivalent to mapM; it is too strict: *Main take 3 $ head $ mapM return [1,2,3,4,undefined] [1,2,3] *Main take 3 $ head $ mapM3 return [1,2,3,4,undefined] [*** Exception: Prelude.undefined So, like foldl', mapM3 seems a viable alternative for mapM, but not a replacement. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: a faster, accumulating mapM (was Re: [Haskell-cafe] mapM vs mapM_ performance)
Luke, Thanks for the nice answer. So maybe I'll give mapM3 the name mapM' and put it in my personal library. But I'm still a bit curious about the performance profile of mapM. The profiler is telling me they're allocating around the same amount of memory, so I am not clear what is making it slow. I am guessing it has something to do with extra thunks due to laziness, but a 10x slowdown? Thanks again, B On Thu, Apr 24, 2008 at 4:45 PM, Luke Palmer [EMAIL PROTECTED] wrote: On Thu, Apr 24, 2008 at 11:28 PM, Ben [EMAIL PROTECTED] wrote: 2) Is there a reason to not use mapM3 above? Yes, there certainly is. mapM3 is not equivalent to mapM; it is too strict: *Main take 3 $ head $ mapM return [1,2,3,4,undefined] [1,2,3] *Main take 3 $ head $ mapM3 return [1,2,3,4,undefined] [*** Exception: Prelude.undefined So, like foldl', mapM3 seems a viable alternative for mapM, but not a replacement. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Help me refactor this type!
On Thu, Apr 24, 2008 at 11:10 PM, Ryan Ingram [EMAIL PROTECTED] wrote: More FRP stuff: a new type for Future that came to me in an inspiration this morning. But it's ugly and I need someone with better theoretical underpinnings than me to tell me what I've really built :) data Future t a = Known t a | Unknown (t - IO (STM (Maybe (Future t a This looks similar to my friend the free monad over exponentiation, or Suspend, which I also discovered while experimenting with FRP. After experimenting a bit, I found that the following variant lead to more elegant implementations of the same things: newtype SuspendT v m a = SuspendT (m (Either a (v - SuspendT v m a))) Implemented pretty fully here: http://luqui.org/git/?p=luqui-misc.git;a=blob;f=work/code/haskell/frp/Fregl/Suspend.hs;h=d5d2daa02c9c392ac3788c3346fb8b6ab6acabf7;hb=63f7752229e63bd8d1aa9a7a9a8d6a785669cd45 I'm not quite sure whether you can make it have all the capabilities yours does (there is no STMT...). Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Call for Contributions - Haskell Communities and Activities Report, May 2008 edition
se bem me lembro o 2lt já está neste report, que tal acrescentar uma referência a isto das type families ou n vale a pena? On Thu, Apr 24, 2008 at 3:01 PM, Janis Voigtlaender [EMAIL PROTECTED] wrote: Dear Haskellers, so much has happened in the Haskell world in the past months. Therefore, we would very much like to collect contributions for the 14th edition of the Haskell Communities Activities Report http://www.haskell.org/communities/ Submission deadline: 10 May 2008 (please send your contributions to hcar at haskell.org, in plain text or LaTeX format) This is the short story: * If you are working on any project that is in some way related to Haskell, please write a short entry and submit it to the us. Even if the project is very small or unfinished or you think it is not important enough -- please reconsider and submit an entry anyway! * If you are interested in any project related to Haskell that has not previously been mentioned in the HCA Report, please tell us, so that we can contact the project leaders and ask them to submit an entry. * Feel free to pass on this call for contributions to others that might be interested. More detailed information: The Haskell Communities Activities Report is a bi-annual overview of the state of Haskell as well as Haskell-related projects over the last, and possibly the upcoming 6 months. If you have only recently been exposed to Haskell, it might be a good idea to browse the December 2007 edition -- you will find interesting topics described as well as several starting points and links that may provide answers to many questions. Contributions will be collected until the submission deadline. They will then be compiled into a coherent report that is published online as soon as it is ready. As always, this is a great opportunity to update your webpages, make new releases, announce or even start new projects, or to talk about developments you want every Haskeller to know about! As the purpose of the report is to collect recent or current activities, we encourage you to update all existing summaries and reports. We will probably drop any topics that have not had any activity for the past year, i.e., since May 2007, but we would very much prefer you to present an updated description of the topic. Of course, new entries are more than welcome. Reports should generally be kept brief and informative, ranging from a few sentences to a few hundred words, to keep the whole report reasonably sized. Looking forward to your contributions, Andres and Janis (current editors) FAQ: Q: Which topics are relevant? A: *All* topics which are related to Haskell in some way are relevant. We usually had reports from users of Haskell (private, academic, or commercial), from authors or contributors to projects related to Haskell, from people working on the Haskell language, libraries, on language extensions or variants. We also like reports over distributions of Haskell software, Haskell infrastructure, books and tutorials on Haskell. Reports on past and upcoming events related to Haskell are also relevant. Finally, there might be new topics we don't even think about. As a rule of thumb: if in doubt, then it probably is relevant and has a place in the HCAR. You can also ask the editors. Q: Is unfinished work relevant? Are ideas for projects relevant? A: Yes! You can use the HCAR to talk about projects you are currently working on. You can use it to look for other developers that might help you. You can use it to write ``wishlist'' items for libraries and language features you would like to see implemented. Q: How much should I write? A: There's no formal limit. But generally, entries should be short and to the point. A general introduction is helpful. Apart from that, you should focus on recent or upcoming developments. There also is no minimum length of an entry! The report aims at being as complete as possible, so please consider writing an entry, even if it's only a few lines long. Q: If I don't update my entry, but want to keep it in the report, what should I do? A: Tell us that there are no changes. We will reuse the old entry in this case, but we might drop it if it's older than a year, to give more room and more attention to projects that change a lot. Don't resent complete entries if you haven't changed them. Q: What format should I write in? A: The best format is a LaTeX source file, adhering to the template that's available at: http://haskell.org/communities/05-2008/template.tex There's also a LaTeX style file at http://haskell.org/communities/05-2008/hcar.sty that you can use to preview your entry. If you don't know LaTeX, then use plain text. If you modify an old
Re: Re[2]: a faster, accumulating mapM (was Re: [Haskell-cafe] mapM vs mapM_ performance)
On Fri, Apr 25, 2008 at 12:02 AM, Ben [EMAIL PROTECTED] wrote: Luke, Thanks for the nice answer. So maybe I'll give mapM3 the name mapM' and put it in my personal library. Except the answer was wrong. I forgot the reverse in my implementation, so that undefined we were seeing was just the last element of the list. But the conclusion is still true :-) *Main take 3 $ runIdentity $ mapM return (1:2:3:4:undefined) [1,2,3] *Main take 3 $ runIdentity $ mapM3 return (1:2:3:4:undefined) *** Exception: Prelude.undefined But I'm still a bit curious about the performance profile of mapM. The profiler is telling me they're allocating around the same amount of memory, so I am not clear what is making it slow. I am guessing it has something to do with extra thunks due to laziness, but a 10x slowdown? Tail recursion can make a huge difference in strict settings: the difference between a loop and recursion in C. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: a faster, accumulating mapM (was Re: [Haskell-cafe] mapM vs mapM_ performance)
2) Is there a reason to not use mapM3 above? Yes, there certainly is. mapM3 is not equivalent to mapM; it is too strict: *Main take 3 $ head $ mapM return [1,2,3,4,undefined] [1,2,3] *Main take 3 $ head $ mapM3 return [1,2,3,4,undefined] [*** Exception: Prelude.undefined So, like foldl', mapM3 seems a viable alternative for mapM, but not a replacement. Wow. A 10x slowdown for a very commonly used function that in 99.8% of all use cases has no need for the extra laziness at all. No wonder some people say Haskell is a toy language... /Niklas ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: a faster, accumulating mapM (was Re: [Haskell-cafe] mapM vs mapM_ performance)
niklas.broberg: 2) Is there a reason to not use mapM3 above? Yes, there certainly is. mapM3 is not equivalent to mapM; it is too strict: *Main take 3 $ head $ mapM return [1,2,3,4,undefined] [1,2,3] *Main take 3 $ head $ mapM3 return [1,2,3,4,undefined] [*** Exception: Prelude.undefined So, like foldl', mapM3 seems a viable alternative for mapM, but not a replacement. Wow. A 10x slowdown for a very commonly used function that in 99.8% of all use cases has no need for the extra laziness at all. No wonder some people say Haskell is a toy language... mapM_ is far more common, and optimised specially. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] how can this code be less?
I wrote this code and Can it be less? [2,4,5]list is sub list of [3,7,2,4,5,9] list and return True but not of[3,7,4,2,5,9] list ; return False sublist :: Eq a = [a] - [a] - Bool sublist [] _ = True sublist (_:_) [] = False sublist (x:xs) (y:ys) | x == y = if isEqual (x:xs) (y:ys) == False then sublist (x:xs) ys else True | otherwise = sublist (x:xs) ys isEqual :: Eq a = [a] - [a] - Bool isEqual [] _ = True isEqual (_:_) [] = False isEqual (x:xs) (y:ys) | x==y= isEqual xs ys | otherwise= False Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Kieran Beltran/Watson/IBM is out of the office.
I will be out of the office starting 04/23/2008 and will not return until 04/28/2008. I will be on vacation for a few days. If this is urgent please reach my Admin Kristine Smester ((917) 472-3387), otherwise I will respond to your message when I return. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how can this code be less?
cetin tozkoparan wrote: I wrote this code and Can it be less? [2,4,5] list is sub list of [3,7,*2,4,5*,9] list and return True but not of [3,7,*4,2,5*,9] list ; return False sublist :: Eq a = [a] - [a] - Bool sublist [] _ = True sublist (_:_) [] = False sublist (x:xs) (y:ys) | x == y = if isEqual (x:xs) (y:ys) == False then sublist (x:xs) ys else True | otherwise = sublist (x:xs) ys isEqual :: Eq a = [a] - [a] - Bool isEqual [] _ = True isEqual (_:_) [] = False isEqual (x:xs) (y:ys) | x==y= isEqual xs ys | otherwise= False One way is to use existing library functions as Henning suggested (but maybe you missed it because he mischievously changed the subject!) Henning Thielemann wrote: try 'List.tails' and 'List.isPrefixOf' You should be able to define sublist using only some combination of the following (and one pair of parentheses) in one line of code! import List(isPrefixOf,tails) (.):: (b - c) - (a - b) - a - c any:: (a - Bool) - [a] - Bool tails :: [a] - [[a]] isPrefixOf :: (Eq a) = [a] - [a] - Bool ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how can this code be less?
I think you're looking for Data.List.isInfixOf. Alex On Thu, Apr 24, 2008 at 7:40 PM, Dan Weston [EMAIL PROTECTED] wrote: cetin tozkoparan wrote: I wrote this code and Can it be less? [2,4,5] list is sub list of [3,7,*2,4,5*,9] list and return True but not of [3,7,*4,2,5*,9] list ; return False sublist :: Eq a = [a] - [a] - Bool sublist [] _ = True sublist (_:_) [] = False sublist (x:xs) (y:ys) | x == y = if isEqual (x:xs) (y:ys) == False then sublist (x:xs) ys else True | otherwise = sublist (x:xs) ys isEqual :: Eq a = [a] - [a] - Bool isEqual [] _ = True isEqual (_:_) [] = False isEqual (x:xs) (y:ys) | x==y= isEqual xs ys | otherwise= False One way is to use existing library functions as Henning suggested (but maybe you missed it because he mischievously changed the subject!) Henning Thielemann wrote: try 'List.tails' and 'List.isPrefixOf' You should be able to define sublist using only some combination of the following (and one pair of parentheses) in one line of code! import List(isPrefixOf,tails) (.):: (b - c) - (a - b) - a - c any:: (a - Bool) - [a] - Bool tails :: [a] - [[a]] isPrefixOf :: (Eq a) = [a] - [a] - Bool ___ 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] announce: Glome.hs-0.3 (Haskell raytracer)
Andrew Coppin wrote: Wow. The POV-Ray guys are talking about Haskell [or rather, my personal addiction to it] and the Haskell guys are talking about POV-Ray... on the same day... How unlikely is that? ;-) That's odd; I had a personal addiction to POV-Ray for a few years, and just now have started using Haskell. I've been using POV-Ray for a long time. I like it for several reasons: 1. It's the only program I've ever seen [on a PC] that does ray tracing. [I'm sure there must be others...] 2. It's the only program I've seen that can render *real* curves, not fake trickery with triangle meshes. 3. It can render *arbitrary* mathematical surfaces. Want to render a 3D slice of the 4D cubic Mandelbrot set? No problem! 4. It has a novel scene description language, which does far more than describe scenes. It's Turing-complete, and you can build physics engines with it. [It's painfully slow though!] The Scene Description Language (SDL) is the best and worst thing about POV-Ray. It's very intuitive and user-friendly, so a person can reasonably write a complex scene in pure code without using an external GUI editor. Unfortunately, the SDL is so complex it's well-nigh impossible to support in other third-party applications. It's also slow. I don't know if this is still the case, but the standard way of doing an animation was to reference a clock variable in your scene source code that went from 0 to 1; for instance, a command to make a swing swing back and forth might looks like this: rotate 15*sin((clock/2)*seconds*(2*pi)-((2/3)*pi))*x seconds here is a variable set to the number of seconds in the animation, and x is the X axis unit vector 1,0,0. The (2/3)*pi thing is to make it swing out of phase with the other swings. (this rather obfuscatory example taken from an actual ancient povray source file, you can see a rendering here: http://syn.cs.pdx.edu/~jsnow/playground.png) The scene then has to be re-parsed for every frame. For complex scenes, the scene parsing could take longer than the actual render. There are many other PC programs that do ray tracing, but POV-Ray is the only one I've had any experience with. The POV-Ray team is currently working on the first multi-threaded version. [After years of saying it would never happen.] It's taking a while. (That's partly because the developers take product quality very seriously.) It should be interesting when it's done, but it's still taking a while. Personally, I'd quite like to write my own ray tracer to address some of these limitations. But every time I try, I end up hitting design issues [Haskell works very differently to Java] or performance issues [which I don't even know how to begin debugging]. Not to mention that POV-Ray uses sophisticated techniques like volume bounding that I know nothing about. (There's nothing like using an inherantly superior algorithm to make your code orders of magnitude faster...) I haven't really run into any issues where Haskell didn't let me do what I want, except for the performance counters thing mentioned way back at the beginning of this thread (and which I've more or less given up on for now, since the acceleration structure seems to be working okay and I have other things to work on). I would certainly welcome any patches to Glome if you want to contribute in some way rather than write something from scratch. A good acceleration structure definitely makes everything go a lot faster. It's the difference between rendering a scene in a few seconds or ten minutes. BIH is what I'm using. It's relatively new. Here's a paper about it: http://ainc.de/Research/BIH.pdf The actual constructor is based loosely on this pseudocode: http://ompf.org/forum/viewtopic.php?p=1411#p1411 Evan Laforge wrote: Not knowing anything about raytracing, one of the things I found interesting about the paper was that he claimed that the speedups were from using coherent ray packets, and that the shader model was orthogonal, and enough much is spent raycasting that the shader code to make much difference. The implication was that you could graft a packet style raycasting engine onto even povray and give it a nice speed boost... though you might have to lose the nifty real shapes to tessellated approximations. Is this accurate? True but reality is more complicated? You don't need to drop support for the whole multitude of primitives, though the ones that are packet-friendly will render faster. Many modern ray tracers spend most of their time traversing the acceleration structure rather than doing intersection tests with actual geometry, so all you really need to do to get most of the benefit of packet tracing is to make the acceleration structure support packets. (For the actual geometry, you can fall back on mono-rays.) I tried 2x2 packets out last night and got about a 10-15% speed improvement on the level-3 SPD sphereflake. (Shadow and reflection rays
