- Libraries - Haskell.org

DiffArray deadlock
by Lauri Alanko 03 Jun '04

03 Jun '04

The following program gets stuck in ghci, and when compiled with ghc and run, fails with "Fail: thread blocked indefinitely". import Data.Array.Diff main = print (a // [((a ! 0, 1))] ! 0) where a = array (0,0) [(0,0)] :: DiffArray Int Int When DiffArray is replaced with Array, it just prints out "1" as it should. Apparently there is some kind of a deadlock internally, with the update operation holding the lock already before the lookup operation is evaluated. I think the solution is to evaluate all the indices in the argument to replaceDiffArray _before_ obtaining the lock. Changing a single line in Diff.hs gives a partial quick fix: @@ -287 +287 @@ -a `replaceDiffArray` ies = do +a `replaceDiffArray` ies = sum (map fst ies) `seq` do However, in DiffUArray, when the underlying imperative array is unboxed, the operation is strict also in the elements, and then (and _only_ then) the elements, too, need to be evaluated before the MVar is taken, or otherwise their evaluation may lead to a deadlock. I'm not really sure what would be the neatest solution. Lauri Alanko la(a)iki.fi

1 0

sequences
by Ross Paterson 03 Jun '04

03 Jun '04

I've done some crude benchmarking of different implementations of sequences: (ghc -O, times in microseconds) test cases Stack Queue Deque Append Index Update ------------------------------------------------------------- [] 5399 - - - - - JoinList 8498 17897 18197 35194 - - SimpleQueue 9198 12298 - - - - RealtimeQueue 64290 72389 - - - - BootQueue 17997 22896 - - - - BankersQueue 12098 21196 - - - - BankersDeque 16997 70589 22496 - - - Catenable 41593 123881 - 77788 - - CatDeque 57791 145477 62790 132879 - - RandList 11598 - - - 13498 29895 FingerTree 24996 33894 32994 45293 - - FingerTreeS 28995 44693 37894 68689 37094 37994 Test cases: Stack: 100000 random stack operations on a sequence of 2000 elements Queue: 100000 random queue operations on a sequence of 2000 elements Deque: 100000 random deque operations on a sequence of 2000 elements Append: building a sequence of fib 25 elements using appends Index: 100000 accesses at random indices on a sequence of 2000 elements Update: 10000 updates at random indices on a sequence of 2000 elements Implementations: [] you know; the rest are from Edison or Chris's book (RandList is skew binary random access lists), except for the last two: - an implementation using 2-3 finger trees, giving constant time access to the ends and O(log n) append. - a variant annotated with size information to support index, update and split in time O(log(min(i,n-i)). Conclusions: - Cute though the real-time queue is, the Banker's version is much better. - No implementation is clearly superior. A library would need [], JoinList, BankersQueue, BankersDeque, RandList and at least one with efficient append. (I've discounted SimpleQueue because it performs badly in a shared context.) I've argued before that the best way to express their commonality is using a Haskell 98 constructor class (albeit a fairly big one). - Catenable lists and catenable deques are still behind finger trees at these sizes, though eventually their constant time append will win out. - Finger trees with sizes look like a reasonable general purpose sequence implementation. They're not too far behind on every operation, and they also support split efficiently. Their main weakness is the O(log n) bound on append. There's a structure by Kaplan and Tarjan that improves that to O(log(log n)) while keeping the others, but it looks very complicated (and thus may have large constant factors). The code is at http://www.soi.city.ac.uk/~ross/seq.tar.gz docs are at http://www.soi.city.ac.uk/~ross/seq/

1 0

FTP library
by Keith Wansbrough 03 Jun '04

03 Jun '04

Hi all... is there an FTP client library for Haskell? I just looked through the GHC libs, haskell.org, and a quick Google, without finding anything. --KW 8-)

3 3

RE: new Library Infrastructure spec.
by Simon Marlow 02 Jun '04

02 Jun '04

On 02 June 2004 11:20, Keith Wansbrough wrote: >> We would welcome your feedback, either as a potential library or tool >> author, or as a potential consumer, or both. The specification isn't >> complete in every detail, but it seems better to post it before >> investing in details that may be rendered void by subsequent >> discussion. > > This looks great! A few comments: > > 1. In the document, Angela uses `#! runhugs' or `#! runghc' at the top > of her Setup.lhs. But Joe is running an nhc install. Angela can't > know which compiler Joe is using, and so she shouldn't have to > specify at the top of Setup.lhs. I propose that she write `#! > runhs' instead, and the compiler writers all provide a `runhs' > script (or symlink) as appropriate. Probably better than a symlink is to have a 'runhaskell' program that dynamically looks for a compiler to run, based on an order of preference. Then runhaskell can be distributed separately, and there's no retargetting of symlinks required when compilers are installed or uninstalled. This is like the runghc I wrote recently: it searches for a ghc binary in the path, so that I don't have to wire in the path to ghc when runghc is built. > 2. In section 4.1, the syntax for pkg.desc is discussed. I think the > simplest and least surprising syntax to use would be the RFC-2822 > email message header syntax (specifically sections 2.2 and 2.2.3). > That is, each field is first written as > > <fieldname> ":" <fieldbody> > > ; then long lines may be "folded" by breaking them anywhere > <whitespace> is allowed, by inserting <newline><whitespace>. > > To read this format back, first "unfold" by replacing all > <newline><whitespace> pairs with <whitespace>; then expect > <fieldname> ":" at the start of each line, with the remainder being > <fieldbody>. I like this. Cheers, Simon

1 0

RE: Tree Wars, IntMap strikes back.
by Simon Marlow 01 Jun '04

01 Jun '04

On 28 May 2004 13:59, JP Bernardy wrote: > --- Simon Marlow <simonmar(a)microsoft.com> wrote: > >> Interesting, I get pretty much the same results as >> you, except that >> DData.Map is now quicker on the lookup test than >> both FiniteMap and AVL >> (0.120 vs. 0.134 and 0.138 respectively). > > Ok, so that means that I should merge in the last > change by Daan (and in IntSet too)? I wasn't using that patch for my measurements. Cheers, Simon

2 1

RE: Tree Wars (latest round :-)
by Simon Marlow 28 May '04

28 May '04

On 27 May 2004 17:18, Adrian Hey wrote: > On Wednesday 26 May 2004 10:53 am, Adrian Hey wrote: >> I can post the test code to anyone who wants it. > > I've put the test code here.. > http://homepages.nildram.co.uk/~ahey/HLibs/TreeWars.tar.gz Interesting, I get pretty much the same results as you, except that DData.Map is now quicker on the lookup test than both FiniteMap and AVL (0.120 vs. 0.134 and 0.138 respectively). I'm not going to investigate this any further, because it'll take forever to get to the bottom of. I think we've arrived at a reasonable conclusion, that the old FiniteMap is definitely superceded but there isn't a clear choice between the others, so we should provide them all. How about the following modules: Data.Map -- a default implementation of maps, eg. DData.Map Data.Map.AVL -- same interface, based on AVL trees Data.Map.Int -- current DData.IntMap Cheers, Simon

3 2

Re: Tree Wars (latest round :-)
by Daan Leijen 27 May '04

27 May '04

On Wed, 26 May 2004 10:53:54 +0100, Adrian Hey <ahey(a)iee.org> wrote: > I got these results: > > For 500,000 random elements > Insert Lookup Delete > Data.Tree.AVL 0.923 0.203 0.798 > Data.FiniteMap 1.150 0.203 1.259 > DData.Map 1.177 0.205 1.084 > DData.IntMap 0.648 0.163 0.627 > > > For 500,000 ordered elements: > Insert Lookup Delete > Data.Tree.AVL 0.210 0.060 0.117 > Data.FiniteMap 0.473 0.076 0.137 > DData.Map 0.488 0.079 0.145 > DData.IntMap 0.108 0.039 0.054 Very cool results for AVL :-) > We still have no idea how well AVL trees perform for > set operations (haven't written the necessary code yet). Let me take this opportunity to remind us all of being careful when interpreting these numbers: most programs don't just insert and lookup in that order, but mix the operations in a lazy fashion which can lead to wildly different results. Furthermore, I tend to use "union" a lot -- I know/suspect from simple tests that DData.IntMap tends to outperform Data.Map by a wide margin on those kind of operations, etc. Btw. Given the good performance of AVL, maybe we should try to make the interface look like DData.Map (or maybe provide a seperate AVL.Map module to does that). This would allow one to use IntMap, AVL.Map or Map without changing (much) code. All the best, Daan. > > I can post the test code to anyone who wants it. > The mods to test287.hs are: > > Removed size calculation, as this O(n) for AVL trees but O(1) for > FiniteMap and DData.map and is irrelevant to insertion/deletion times. > > Increased testData size from 100,000 to 500,000. > > Used foldl' instead of foldr to prevent stack overflow. > > PerformGC at start of each test in test10 > > Had to swap args of Map.lookup in lookupsMap > > Changed the way results are displayed to be more comprehensible (to me:-) > > Regards > -- > Adrian Hey > > > > _______________________________________________ > Libraries mailing list > Libraries(a)haskell.org > http://www.haskell.org/mailman/listinfo/libraries >

2 1

Re: Tree Wars (latest round :-)
by Adrian Hey 27 May '04

27 May '04

On Wednesday 26 May 2004 10:53 am, Adrian Hey wrote: > I can post the test code to anyone who wants it. I've put the test code here.. http://homepages.nildram.co.uk/~ahey/HLibs/TreeWars.tar.gz Regards -- Adrian Hey

1 0

RE: DData
by Simon Marlow 25 May '04

25 May '04

On 25 May 2004 15:52, Daan Leijen wrote: > Ok, here is a new "IntMap" module that might improve the > performance of "lookup". Please, let's first test it before > adding the changes to the real distribution. > > I have: > 1) removed calls to "natFromInt" and "intFromNat". Supposedly, > they should expand to nothing but who knows... These calls were being optimised away by GHC. However, something else wasn't: namely the value of maxBound::Word which is used by complement. There's no substitue for actually looking at the code that GHC generates! > 2) I have commented out the guard that tests if the integer > is in the tree at all. When a key is present, lookup will be > faster -- if the key is not present, lookup might be slower. > > Simon, I would be interested to see how it performs with and > without the comment (2) (line 269). If performance is better > without the comment, it means that ghc is spending time doing > intFromNat/natFromInt which means that we might improve matters > by storing Nat's instead of Int's in the IntMap. (I don't know > if such tweaking is worth the trouble though.) I'll run your new code tomorrow and let you know the results. Cheers, Simon

1 0

RE: DData
by Simon Marlow 25 May '04

25 May '04

On 24 May 2004 12:03, Adrian Hey wrote: > On Thursday 20 May 2004 5:04 pm, Simon Marlow wrote: >> And after eliminating some bogosity in the benchmark, I now get: >> >> Insert Lookup Delete >> AVL 0.87 0.22 0.87 >> FiniteMap 1.07 0.17 1.11 >> DData.Map 1.08 0.16 1.02 >> DData.IntMap 0.65 0.16 0.61 >> >> So I declare that on random data, DData.Map has essentially the same >> performance as FiniteMap. IntMap is faster for insertion/deletion as >> expected. AVL is better than FiniteMap for insertion/deletion but >> slower for lookups. > > Could you explain the bogosity you eliminated? I did a full GC before running each part of the test to keep random GC effects to a minimum, and eliminated a couple of cases of badly optimised code in the test program. > The reason I ask is that those second results for lookup for AVL > trees seem pretty reasonable to me, considering the AVL library is > general purpose > and not specialised for any kind of map. Currently the AVL > implementation will have to read 3 heap records per tree node > visited, vs. 2 for FiniteMap and DData.Map. > > For the balanced tree implementations, I wouldn't expect to see any > significant difference in lookup times (given the same degree of > specialisation) and what differences there may be would most likely > be due to differences in how well they managed to balance trees. (But > I guess if random data is to be our benchmark, even simple unbalanced > trees would probably look quite reasonable :-) Of course, this isn't testing how well the balancing works. It is comparing raw performance of several balanced tree implementations, so measuring the overhead of balancing, if you like. > DData.IntMap is rather different from the other three, so I'm not > sure exactly how well I would expect it to perform, but if you assume > lookup time is proportional to the No. of heap records examined > (seems to be reasonable comparing AVL and FiniteMap/DData.Map), then > you'd expect a lookup time of about 0.08 for each if they were > specialised for Int maps. Yes, IntMap should get faster lookup. I looked at the code and managed to make a couple of improvements: adding a 'seq k $' at the beginning of lookup helps, and I fixed a small performance problem with the Word library, but interestingly these don't help the results. I still get 0.16s for the lookup test, so perhaps it is dominated by something else. Cheers, Simon

3 4