September 2008 - Libraries

Cabal 1.4.0.2 won't configure on Vista
by Justin Bailey 27 Sep '08

27 Sep '08

As I posted in ticket #360 (http://hackage.haskell.org/trac/hackage/ticket/360) the latest Cabal on hackage won't configure on Vista. Using GHC 6.8.3, when I run the "configure" command, I get this error: "During interactive linking, GHCi couldn't find the following symbol: SHGetFolderPathA@20 This may be due to you not asking GHCi to load extra object files, archives or DLLs needed by your current session. Restart GHCi, specifying the missing library using the -L/path/to/object/dir and -lmissinglibname flags, or simply by naming the relevant files on the GHCi command line" Any ideas? Justin

2 1

Map / IntMap laziness (was: export toDescList from Data.Map)
by Scott Dillard 26 Sep '08

26 Sep '08

On Fri, Sep 26, 2008 at 8:20 AM, Evan Laforge <qdunkan(a)gmail.com> wrote: > Of course, anything that boosts performance is a win. Does anyone > know of any Map benchmarks? I suppose I could write some, but I'd be > sort of surprised if someone else hasn't already done that. Then we > could throw in all the various avl / redblack / whatever map variants > in there and see how they stack up. I'm sure everyone has a benchmark floating around. I've attached the one I've been using. As we all know from following the shootout rankings, a single benchmark is pointless and misleading. Better to have targeted benchmarks for specific use patterns. The problem is that search trees are used in so many ways. I've divided it up into two domains: inputs and queries. Then you get a single micro-benchmark by picking one thing in each domain. Here's what I've got Inputs : - Random - Random with duplicates - Sequential - The union of many small (100 or so) random sets Queries : - Sum all keys (or values) - Sum a random subset of keys (may or may not be present in the map) That last query takes an additional parameter, how large of a subset to search for. This is important to capture the case when you build a map but only query it a few times. I can't think of when I've done this, but laziness is a big win here, just as in "take n . sort" for big lists and small n. I've made an optionally-lazy IntMap (attached). I removed the bangs from the tree node constructors and replaced them with seqs in the functions. I've only added strictness to the "one-at-a-time" functions: insert, delete, update, etc. I've let all the functions of type Map -> Map -> Map become lazy. Here is the speedup I get for performing a single lookup on the result of the union 10000 lists, each of size 100. STRICT: 976,823,060 bytes allocated in the heap 572,439,796 bytes copied during GC (scavenged) 3,426,580 bytes copied during GC (not scavenged) 31,641,600 bytes maximum residency (21 sample(s)) 1864 collections in generation 0 ( 2.76s) 21 collections in generation 1 ( 1.76s) 84 Mb total memory in use MUT time 3.70s ( 3.79s elapsed) GC time 4.52s ( 4.58s elapsed) Total time 8.22s ( 8.38s elapsed) %GC time 55.0% (54.7% elapsed) Productivity 45.0% of total user, 44.1% of total elapsed real 0m8.391s user 0m8.217s sys 0m0.172s LAZY: 740,632,056 bytes allocated in the heap 147,902,632 bytes copied during GC (scavenged) 3,316,016 bytes copied during GC (not scavenged) 32,079,872 bytes maximum residency (7 sample(s)) 1412 collections in generation 0 ( 0.60s) 7 collections in generation 1 ( 0.42s) 66 Mb total memory in use MUT time 1.96s ( 2.02s elapsed) GC time 1.02s ( 1.09s elapsed) Total time 2.98s ( 3.10s elapsed) %GC time 34.2% (35.0% elapsed) Productivity 65.8% of total user, 63.3% of total elapsed real 0m3.114s user 0m2.984s sys 0m0.132s This difference quickly disappears as the size of the query set increases, but I've not been able to get the lazy version to go slower. In all use-cases that I've tried, lazy IntMaps and Maps performed no worse than the current strict implementations. The difference between lazy and strict tree constructors is less pronounced with Data.Map. I can't get it to make much of a difference. Using seq instead of bangs seems to speed things up a little, but I think this is spurious compiler behavior. Keeping the tree balanced limits how much work you can put off, so really the only benefit for Data.Map is in functions like mapKeysMonotonic and mapWithKey, but I still think it would be useful to have lazy versions of those functions. The trie on which IntMap is based allows for a lot more laziness because its structure only changes along the path between the root and the point of operation. This is why lazy unioning works so well. This will become even more useful as we all start writing parallel code (which of course we all plan to start doing Real Soon Now) because "foldr insert" doesn't parallelize but "unions . map singleton" does. The issue then is how to expose this laziness. I think the semantics (lazy or strict) of the currently exported functions should not be changed. Instead there should be lazy functions, either named like unionL, or put in a Lazy submodule. The submodule approach seems better to me but it would necessitate splitting up the library into more than 2 files. Data.Map.Base, Data.Map.Strict, Data.Map.Lazy, etc. The current interface would be rexported from Data.Map, unchanged. To be honest, I had no particular rational reason for wanting IntMap > (and in fact I'm not using it). I just heard some mumbling on the > list about "Data.Map so slow, IntMap so much faster especially for > unions". Though to be honest, probably what most matters to me is how > much garbage an insert generates (and similarly how much the resulting > structures will share). I didn't run any tests or anything, so I > wasn't that upset to not be able to use IntMap :) > They are currently the best option for pure, persistent arrays. Better even than Data.Sequence. (I'm told.) I use them a lot. You heard right about unioning. The above mentioned benchmark takes 18 seconds with a Map. They generate much less garbage because less of the tree is mutated after an insert/delete. > Points in time. I was using Int64 at the time, but I'm actually using > Doubles now. Plain Data.Map is working fine in practice. Yeah for that use-case I don't think you'll beat a good balanced binary tree, not in any language. A bit-trie won't really work because you could have duplicate entries (+/- 0) and they wouldn't be stored in sorted order. Scott

3 4

Re: export toDescList from Data.Map
by Scott Dillard 26 Sep '08

26 Sep '08

> Date: Tue, 23 Sep 2008 09:09:44 -0700 > From: "Evan Laforge" <qdunkan(a)gmail.com> > Subject: Re: export toDescList from Data.Map > > > > Actually, Data.Map, Data.IntMap, Data.Set and Data.IntSet do not have an > > active maintainer and maybe everybody waits for "GSoC thing for tries". > > > > Indeed, as you noted yourself "it would be nice to fix up Map, Set, > > IntMap, and IntSet". I think it is almost mandatory. So would you do > > this, too? "toDescList" makes sense for sets, too. On the other hand, I > > was against toAscList as it is identical to toList. That means I always > > assumed a bias towards "ascending operations". > > I wouldn't mind doing some cleanup... I use Map, Set, IntMap and IntSet very much, and I'm very interested in seeing to it that these important libraries are maintained and improved. However, short of a major API change, like what's going on with generalized tries and what's already been done with Edison, I don't think there is much work left to be done with these libraries at the API level. Just minor changes like the one you've proposed. There are some things that could be done though... - I'm not sure what Benedikt Huber meant by 'view', but I think he means exposing the tree structure, in a read-only way, to users. I think its a shame that the Map/Set libraries do not expose this. The simplest solution would be to have toTree functions that convert it to a Data.Tree, but I don't think anybody actually likes that data type. A specialized binary tree data type would be more elegant, but there is an issue of how data is stored in the tree. Map/Set store keys and values in internal nodes and use null leaves. IntMap/IntSet store all keys/values in non-null leaves. So maybe this TreeView type would have to be specific to either Map or IntMap. The idea here is that the algorithms and data structures used for these trees are well-known. The papers are linked from the documentation. So the library should expose this to users, in a safe way. - Since someone raised the issue of test suites for performance and correctness, I think it would also be interesting to investigate what effect the strictness annotations in the tree constructors have on performance. Everyone takes for granted that bangs=faster, but I've noticed, as have others, that removing these strictness annotations actually make things run faster. Instead, the tree construction _functions_ should be made strict using seq. The Map construction functions are already strict enough on account of the balancing. Try it for yourself, remove the bangs from the sub-tree fields in the Bin constructor, and run a little benchmark. This would open up the possibility for lazy versions of functions like mapWithKey and mapKeysMonotonic. I had mentioned this previously, but few seemed to care, so I just made the change locally. http://www.haskell.org/pipermail/libraries/2008-August/010371.html . If we we're going to start a little Map/Set/IntMap/IntSet working group, then I'd like to throw that idea back into the mix. > It's also galling that IntMap is hardcoded to 32bit ints and writing a > 64 bit version would seem to require yet another copy and paste > session. And it seems like theoretically patricia should work on > doubles too. But I'm not sure how to address all this code sharing. > IntMap is hard coded to Int, which is 32 bits on a 32 bit architecture, and 64 bits on a 64 bit architecture. I think the main reason for this is so that the key can be unpacked/specialized for extra performance, since that is the primary purpose of the library. If you just need sublinear insert/lookup/delete then use a Map. Are you galled that the key type is not hardcoded to Int64, or that the key is not allowed to be any instance of the Bits class? In the former case, you'd inflate the size of the tree and take a small speed hit on 32bit archs, and in the latter I think you'd have even worse performance. I think the choice of Int is wise because it is the fastest, and that is the point of the library, and if you think about it you're not going to be dealing with more that 2^32 Ints on a 32 bit computer. (What would they be referencing? Not array positions or file offsets.) If you're trying to optimize, say, "Map (Int32,Int32) a" into "IntMap64 a", there are other ways to accomplish that: import qualified Data.IntMap as IM import Data.IntMap (IntMap) newtype IntTrie = IntTrie (IntMap IntTrie) empty :: IntTrie empty = IntTrie IM.empty insert :: [Int] -> IntTrie -> IntTrie insert [] t = t insert (x:xs) (IntTrie t) = IntTrie t' where (y,t') = IM.insertLookupWithKey (const union) x y' t y' = case y of Just y -> insert xs y; Nothing -> insert xs empty delete :: [Int] -> IntTrie -> IntTrie delete [] t = empty delete (x:xs) (IntTrie t) = IntTrie (IM.update f x t) where f y = case IM.delete x (case delete xs y of IntTrie t -> t) of t' | IM.null t' -> Nothing | otherwise -> Just (IntTrie t') And so forth. This is an IntSet for arbitrarily long integers represented as [Int]. An IntMap is probably not much more work. > > Maybe this explains the little feedback to this ticket, but I would like > > to encourge you, to improve things, anyway. > > Well thanks. It's nice to hear *something* :) > > For my $0.02 your proposal is good. toDescList is very important to have in many situations. I've had it un-hidden locally for a while now. It's silly that it wasn't exported in the first place. Scott

4 4

Re: Libraries Digest, Vol 61, Issue 23
by Scott Dillard 26 Sep '08

26 Sep '08

> Date: Fri, 26 Sep 2008 15:36:46 +0100 > From: Ross Paterson <ross(a)soi.city.ac.uk> > > On Fri, Sep 26, 2008 at 04:12:17PM +0200, Benedikt Huber wrote: > > I think that having a function > > > > > treeView :: Map k v -> T (k,v) > > > > s.t. T is an instance of Foldable, supports efficient left and right > > folds, and additional operations like subrange queries (all pairs (k,v) > > s.t. l <= k <= u) would be useful. > > I'd like to have all functions from Data.Foldable available for folds > > with key, e.g fold[lr]MWithKey. > > Map has split and splitLookup for subrange queries, and you could get > the folds with > > mapWithKey (,) :: Map k v -> Map k (k,v) > > I don't follow FP research, but has anyone formalized the "divide and conquer" strategy into a type class? I guess it would be something like MapReduce, but I don't know what the details of that framework are. Something like... class DivideAndConquer t where mapReduce :: (a -> b) -> (b -> b -> b) -> t a -> b splitLookup can get you close, but the user does not know a good split position, so he has to guess something like halfway between min and max. I think in a many-core setting this would be a heavily used method. Data.Map and Data.Sequence would be very good at implementing it because they are balanced, but Data.Tree and Data.IntMap can also do it, just not with good load-balancing guarantees. The other option, related to this thread, is to just have a BinTree data type, like Data.Tree but strictly binary, and have the various balanced-tree libraries provide views of that type. Then one needs to write mapReduce for only one data type. Scott

1 0

darcs patch: Fix build with ghc-6.10
by Bertram Felgenhauer 26 Sep '08

26 Sep '08

Hi, with the patch below, the head version[1] of bytestring compiles in the ghc tree (replacing libraries/bytestring) and passes validate. No code had to be changed, just the base dependency and a few OPTIONS_GHC pragmas because of orphan instances. enjoy, Bertram [1] http://darcs.haskell.org/bytestring/ not http://darcs.haskell.org/ghc-6.10/packages/bytestring/ or http://darcs.haskell.org/packages/bytestring/ P.S. why does it list libraries(a)h.o as the maintainer? But never mind, Don reads this list. Tue Sep 23 05:49:33 CEST 2008 Bertram Felgenhauer <int-e(a)gmx.de> * Fix build with ghc-6.10 Also fix build with -Werror.

1 0

Proposal: fix iso8601 date in old-time
by Magnus Therning 24 Sep '08

24 Sep '08

I just raised http://hackage.haskell.org/trac/ghc/ticket/2626 /M -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus＠therning．org Jabber: magnus＠therning．org http://therning.org/magnus Haskell is an even 'redder' pill than Lisp or Scheme. -- PaulPotts

1 0

Re: export toDescList from Data.Map
by Christian Maeder 24 Sep '08

24 Sep '08

Hallo Evan, If it is really such a performance difference the functions should be exported by all means. (Another work-around might by to inverse the order of the keys, but that'll be unnatural at least for Int keys.) Obviously, I rarely have 1 million elements in my maps. Evan Laforge wrote: >>> That's one of the things I was asking... how do you obtain toDescList >>> without foldlWithKey? And for me, since since the order of the keys >>> is important (say points in time), the order of the fold matters a >>> great deal. >> I thought of "reverse . toList". Maybe the folding functions are not >> needed at all (or only short cuts): > > Ah, well if I really didn't care about performance, then I wouldn't > use Map at all, just an unsorted [(k, v)]. But it's sort of awkward > for the GUI to freeze for a second (yes, it really does take that > long) while haskell reverses a 1 million element list just to get the > first 3 elements (and does so many times)... findMax (deleteFinMax) for the highest 3 elements would be faster then. >> foldlWithKey f z = foldl (\ b (k, v) -> f b k v) z . toList > > This is equivalent to reverse, isn't it? It also takes a second or so > (well, once I add a prime of course, without the prime it sends the > whole system into OOM molasses). Yes, but folding is linear anyway (if the whole result is needed). Cheers Christian

1 0

(lib network) Should inet_aton be called instead of inet_addr ?
by Marc Weber 24 Sep '08

24 Sep '08

Hi @ll Reading http://linux.die.net/man/3/inet_addr I noticed that inet_addr is obsolete and inet_aton should be used because inet_addr indicates error by returning -1 which is a valid address (255.255.255.0) as well. Don't know wether it's worth changing or wether inet_aton is peresent on all systems Marc Weber

4 5

ANNOUNCE: protocol-buffers-0.2.9 for Haskell is ready
by ChrisK 23 Sep '08

23 Sep '08

Hello one and all, Amid much rejoicing, my Haskell version of protocol-buffer is now released (version 0.2.9). What is this for? What does it do? Why? Shorter answer: It generates Haskell data types that can be converted back and forth to lazy ByteStrings that interoperate with Google's generated code in C++/Java/python. It is a pure Haskell re-implementation of the Google code at http://code.Google.com/apis/protocolbuffers/docs/overview.html which is "...a language-neutral, platform-neutral, extensible way of serializing structured data for use in communications protocols, data storage, and more." Google's project produces C++, Java, and Python code. This one produces Haskell code. The release tarball (with 3 Haskell packages inside, see README in source) is at http://hackage.haskell.org/cgi-bin/hackage-scripts/package/protocol-buffers The darcs repository has moved to http://darcs.haskell.org/packages/protocol-buffers2/ You will also need a recent ghc compiler, the "binary" package and the "utf8-string" package from hackage.haskell.org (same site as mentioned above). The source compiles to 3 things: 1) the package "protocol-buffers" with the library API 2) the package "protocol-buffers-descriptor" with the descriptor.proto code 3) The 'hprotoc' executable which is a command line program similar to 'protoc'. The "examples" sub-directory in the code has the Haskell version of the "addressbook.proto" example and is compatible with Google's similar example code. The code generated from unittest.proto (and unittest_import.proto) includes messages TestAllTypes and TestAllExtensions which have been extensively tested by QuickCheck to ensure they can be wire encoded and decoded (see the "tests" sub-directory in the code). The user API, as exported by Text.ProtocolBuffers, allows for converting messages back and forth to the lazy ByteString type. And such messages can be merged, and the defaults accessed via the MessageAPI type class. The messages in Haskell as just regular data types and are thus immutable. Required types are simple record fields, optional types are Maybe, and repeated types are Seq (from Data.Sequence). Extensions are supported via Key data that allows access to the extension fields. Extensible messages contain an opaque ext'field entry of type ExtField that contains the map data structure to contain the extension field values. The User API allows for serializing messages as the usual series of fields. It also provides for a length prefix to be written to create delimited messages. It also provides to write a wire tag with any field number before the length and message data. This last form looks like a field on the wire, and there is a special api call to read back just the one message and its field number. This last API is similar to the one that is part of the C# API. No benchmarks have been run yet. Any suggestions? Unsupported for the moment is loading and storing "unknown" fields. It can be added sooner if someone has a use for this. Unsupported indefinitely is code generation for Services and Methods. I have yet to look into how this is presented in the other languages. The API to read a single message field, as mentioned above, might be extended to read any type instead of just messages. optional clever_quote { <autrijus> Perl: "Easy things are easy, hard things are possible" <autrijus> Haskell: "Hard things are easy, the impossible just happened" } Cheers! Chris Kuklewicz

7 8

Following up on a patch for the network package (trac #2005)
by Judah Jacobson 22 Sep '08

22 Sep '08

Hi all, A few weeks ago I proposed a (1-line) patch to the network package to fix trac bug #2005 (getnameinfo error on OS X): http://www.haskell.org/pipermail/libraries/2008-July/010239.html And then I forgot about it until today; looks like it's been sitting in limbo since I sent it. Any chance of this making it into 6.10.1? Thanks, -Judah

2 1