February 2013 - Haskell-Cafe

Announce: Leksah 0.13.2.0 (still a bit experimental)
by Hamish Mackenzie 02 Feb '13

02 Feb '13

Version Control --------------- Harald and Stephan's Version Control integration has been merged in! If you want to help out on this there are still some cool things that could be added. I for one would love something to show my changes vs. the repo as I edit. Harald and Stephan also added a number of other nice UI changes. Unfortunately I do not have a list (but my favourite is that selecting some text highlights other occurrences). Better Haddock and GHCi support ------------------------------- While writing documentation for jsc, I made a few changes to help make writing Haddock docs easier.... * Documentation pane - New pane that uses WebKit to display your packages Haddock docs (Package -> Open Documentation). * Auto build Haddock docs - If you click the tick button on the toolbar it will automatically build your docs and reload the Documentation pane while you edit your code. If you have background build switched off then Ctrl+B will run tests and build docs if the tick is on. * Auto run - While you are in GHCi mode background build will also reevaluate the last expression sent to GHCi with Ctrl+Enter (also works with Ctrl+B if you have background build off). * Haddock & Ctrl+Enter - Haddock code block comments ( -- > and -- >>> ) are removed before the current line or selected text is sent to GHCi. * Support for choosing which executable or test suite GHCi should run (expand the package in the workspace pane to see the list and activate the one you want to load in GHCi). Hop on #leksah if you have any questions. OS X ---- Sorry, I am still having trouble building WebKitGTK+ on OSX. If you want a challenge... https://github.com/jralls/gtk-osx-build https://github.com/leksah/leksah/blob/master/osx/gtk.sh Alternatively we might have to build Leksah with -f-webkit to leave out the webkit stuff. Windows ------- Choose the version that matches your installed GHC http://leksah.org/packages/leksah-0.13.2.0-ghc-7.0.3.exe http://leksah.org/packages/leksah-0.13.2.0-ghc-7.0.4.exe http://leksah.org/packages/leksah-0.13.2.0-ghc-7.4.1.exe http://leksah.org/packages/leksah-0.13.2.0-ghc-7.4.2.exe http://leksah.org/packages/leksah-0.13.2.0-ghc-7.6.1.exe Linux ----- Follow the steps in the .travis.yml file... https://github.com/leksah/leksah/blob/master/.travis.yml Should go something like this... https://travis-ci.org/leksah/leksah

1 0

Why does not zipWith' exist
by Kazu Yamamoto 02 Feb '13

02 Feb '13

Hello, Many texts explain the following Fibonacci code: fibs :: [Integer] fibs = 0 : 1 : zipWith (+) fibs (tail fibs) But this code is very slow because evaluation of (+) is done lazily. If we have the following strict zipWith', the code above becomes much faster. zipWith' f (a:as) (b:bs) = x `seq` x : zipWith' f as bs where x = f a b zipWith' _ _ _ = [] Data.List defines foldl' against foldl. But it does not define zipWith'. I'm curious why zipWith' does not exist in the standard libraries. --Kazu

4 8

Optimizing performance problems with Aeson rendering large Text arrays
by Oliver Charles 01 Feb '13

01 Feb '13

Hello, In summary, i'm working on an application that responds to a users query, a sequence index, with the union of a list of UUIDs that have "changed" since that same sequence index, split into 6 sections. I wish to respond to these queries via JSON to provide an easy to use web service, and for the most part, what I have works. The problem I am having is that profiling seems to show that the majority of the time spent in my application is encoding this to JSON, and also that the application is only 60% productive with 40% allocations happening in Data.Aeson.encode (and friends). Here's an overview of what I'm doing, the full code can be found at the end of this email. I am storing my data in memory as an IntMap, from sequence index to a changeset: IntMap ChangeSet Where a ChangeSet is essentially a tuple of HashSet's of UUIDs: data ChangeSet = ChangeSet { artistChanges :: !(HashSet MBID) , labelChanges :: !(HashSet MBID) , recordingChanges :: !(HashSet MBID) , releaseChanges :: !(HashSet MBID) , releaseGroupChanges :: !(HashSet MBID) , workChanges :: !(HashSet MBID) } deriving (Generic) The MBID newtype is just a newtype around Text, but you can only create MBIDs by parsing a UUID fromString - just to enforce a bit more correctness, but without the cost of having to serialize the UUID to JSON. When I query, I splitLookup on the IntMap to get the requested change set by sequence index, and all future changesets. I union all of these, and then render the response back to the client: let (_, !cs, !futureCs) = IntMap.splitLookup csId changeSets writeLBS $ encode $ mconcat $ catMaybes $ map Just (IntMap.elems futureCs) ++ [ cs ] None of this shows up in profiling however, and here's what I see: Thu Jan 31 17:03 2013 Time and Allocation Profiling Report (Final) Main +RTS -p -RTS total time = 4.75 secs (4748 ticks @ 1000 us, 1 processor) total alloc = 4,329,582,160 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc encode Data.Aeson.Encode 23.5 17.4 string Data.Aeson.Encode 18.5 35.1 break Data.Aeson.Encode 17.5 2.3 mconcat Main 15.1 9.7 fromValue/Array Data.Aeson.Encode 9.2 14.8 toJSON Main 5.7 9.0 send.loop Snap.Internal.Http.Server.HttpPort 3.0 0.0 mapIter Snap.Iteratee 2.1 2.3 parseJSON Main 1.7 3.0 writeLBS Snap.Internal.Types 1.1 4.9 COST CENTRE MODULE no. entries %time %alloc %time %alloc MAIN MAIN 216 0 0.0 0.0 100.0 100.0 main Main 433 0 0.0 0.0 100.0 100.0 main.since Main 1063 1 0.0 0.0 75.3 78.7 encode Data.Aeson.Encode 1391 0 23.5 17.4 75.3 78.7 fromValue/Object Data.Aeson.Encode 1395 254 0.0 0.0 46.0 52.2 fromValue/Array Data.Aeson.Encode 1420 757 7.9 12.0 36.4 25.7 fromValue/String Data.Aeson.Encode 1422 3089095 0.7 0.0 28.5 13.7 string Data.Aeson.Encode 1423 3089095 10.2 11.4 27.8 13.7 break Data.Aeson.Encode 1425 3089095 17.5 2.3 17.5 2.3 string Data.Aeson.Encode 1396 884 8.3 23.7 9.6 26.6 fromValue/Array Data.Aeson.Encode 1421 0 1.3 2.9 1.3 2.9 fromValue/String Data.Aeson.Encode 1424 0 0.0 0.0 0.0 0.0 break Data.Aeson.Encode 1397 884 0.0 0.0 0.0 0.0 toJSON Main 1393 127 5.7 9.0 5.7 9.0 Unless I'm reading this incorrectly, this shows that 75% of the time is spent in encode, along with almost 80% of my allocations. While the performance of my application is actually satisfactory (I respond in around 0.04s), I'd still like to do better - if only for the practical experience of learning how to optimize. Any ideas what I can do about this? I feel like I might get better performance if fromValue/Array new that I had a vector of Text values, and they could just be intercalated with ", " - but I have no idea how the internals of Text works so this might really perform the same as the fold that is currently used. I am compiling for benchmarking purposes with: ghc -Wall -fno-warn-orphans -Werror -O2 -rtsopts \ -hide-package hashable-1.2.0.5 Main.hs And I run with: ./Main Though I have tried with +RTS -A2M, -A4M and -A8M - none of which seem to make a huge difference. -N2 seems to performance worse with a single connection, though that might perform better for many concurrent connections - I haven't yet looked. I'd love to hear your thoughts on what I can do to get this even faster!If you need any more information, don't hesitate to ask. Thanks, - ocharles -------------------- Here is the code I am using. If you want to run this, you will need a directory 'change-sets', which contain JSON files named according to the pattern (\d+).json. I've tared up my test directory and uploaded it to http://ocharles.org.uk/change-sets.tar.gz, if you want to try running this. You will need to install: cabal install aeson unordered-containers containers text uuid snap-core snap-server I run a benchmark with this Perl script, which just does 30 requests and then prints out the average request time. #!/usr/bin/perl use 5.10.0; use List::Util qw( sum ); use LWP::UserAgent; use Time::HiRes qw( gettimeofday tv_interval ); my $lwp = LWP::UserAgent->new; my @intervals; for my $i (0..30) { my $t0 = [ gettimeofday ]; $lwp->get('http://0.0.0.0:8000/since/65527'); push @intervals, tv_interval($t0); } say sum(@intervals) / $#intervals; I think that's it! {-# LANGUAGE BangPatterns, FlexibleContexts, GeneralizedNewtypeDeriving, OverloadedStrings, TypeOperators #-} import Prelude hiding (readFile) import Control.Applicative import Control.Monad (forM, mzero) import Data.Aeson import Data.ByteString.Lazy (readFile) import Data.IntMap.Strict (IntMap) import Data.Hashable import Data.List import Data.Maybe (catMaybes, fromMaybe) import Data.Monoid import Data.HashSet (HashSet) import Data.Text (Text) import Data.UUID import Snap.Core import Snap.Http.Server import System.Directory import System.FilePath import qualified Data.IntMap as IntMap import qualified Data.HashSet as HashSet import qualified Data.Text as Text import qualified Data.Text.Encoding as Encoding data ChangeSet = ChangeSet { artistChanges :: !(HashSet MBID) , labelChanges :: !(HashSet MBID) , recordingChanges :: !(HashSet MBID) , releaseChanges :: !(HashSet MBID) , releaseGroupChanges :: !(HashSet MBID) , workChanges :: !(HashSet MBID) } newtype MBID = MBID Text deriving (Eq, Show, Ord, Hashable, ToJSON) instance Monoid ChangeSet where mempty = ChangeSet mempty mempty mempty mempty mempty mempty a `mappend` b = ChangeSet { artistChanges = artistChanges a `mappend` artistChanges b , labelChanges = labelChanges a `mappend` labelChanges b , recordingChanges = recordingChanges a `mappend` recordingChanges b , releaseGroupChanges = releaseGroupChanges a `mappend` releaseGroupChanges b , releaseChanges = releaseChanges a `mappend` releaseChanges b , workChanges = workChanges a `mappend` workChanges b } mconcat as = ChangeSet { artistChanges = HashSet.unions (map artistChanges as) , labelChanges = HashSet.unions (map labelChanges as) , recordingChanges = HashSet.unions (map recordingChanges as) , releaseChanges = HashSet.unions (map releaseChanges as) , releaseGroupChanges = HashSet.unions (map releaseGroupChanges as) , workChanges = HashSet.unions (map workChanges as) } instance FromJSON ChangeSet where parseJSON (Object j) = j .: "data" >>= go where go o = ChangeSet <$> (HashSet.fromList <$> o .: "artist") <*> (HashSet.fromList <$> o .: "label") <*> (HashSet.fromList <$> o .: "recording") <*> (HashSet.fromList <$> o .: "release") <*> (HashSet.fromList <$> o .: "release_group") <*> (HashSet.fromList <$> o .: "work") parseJSON _ = mzero instance ToJSON ChangeSet where toJSON c = object [ "data" .= object [ "artist" .= artistChanges c , "label" .= labelChanges c , "recording" .= recordingChanges c , "release" .= releaseChanges c , "release_group" .= releaseGroupChanges c , "work" .= workChanges c ] ] instance FromJSON MBID where parseJSON (String s) = maybe mzero (const $ return (MBID s)) $ fromString (Text.unpack s) parseJSON _ = mzero loadChangeSets :: FilePath -> IO (IntMap ChangeSet) loadChangeSets d = do changeSetFiles <- filter (isSuffixOf ".json") <$> getDirectoryContents d fmap IntMap.fromList $ forM changeSetFiles $ \f -> do let csId = read $ reverse $ drop 5 $ reverse f changeSet <- fromMaybe (error "Failed to decode") . decode' <$> readFile (d </> f) return (csId, changeSet) main :: IO () main = do changeSets <- loadChangeSets "change-sets" quickHttpServe $ route [("/since/:x", since changeSets)] where since changeSets = do Just csId <- fmap (read . Text.unpack . Encoding.decodeUtf8) <$> getParam "x" let (_, !cs, !futureCs) = IntMap.splitLookup csId changeSets writeLBS $ encode $ mconcat $ catMaybes $ map Just (IntMap.elems futureCs) ++ [ cs ]

2 3

Re: [Haskell-cafe] Ticking time bomb
by Alexander Kjeldaas 01 Feb '13

01 Feb '13

Forgot the list. On Fri, Feb 1, 2013 at 10:21 AM, Alexander Kjeldaas < alexander.kjeldaas(a)gmail.com> wrote: > > Trying to avoid the wrath of Ketil I'll refrain from suggesting to do > anything, I'll just explain why git is good at this, and not arbitrary. :-) > > Most systems that I know of to verify *anything*, use merkle trees, or > something very similar. > http://en.wikipedia.org/wiki/Hash_tree > > For example the TPM chip on your motherboard, used for example to ensure > the integrity of the Google Chromebook and Windows BitLocker > http://en.wikipedia.org/wiki/Trusted_Platform_Module > (simplified example: in secure memory it stores H1=hash(microcode), then > H2=hash(H1 || BIOS), then H3=hash(H2 || MBR), then H4=hash(H3 || kernel), > ...). > > Or the integrity of the bitcoin currency. > https://en.bitcoin.it/wiki/Protocol_specification#Merkle_Trees > > So these are pretty different systems, but it all boils down to doing > cryptographic secure hashes over a previous hash + new data to ensure > integrity of the new combined data. Given only one verified hash in such a > system, no part of the data, nor its history of mutation can be forged. > "History" can mean which software runs on your computer (TPM), which > transactions are valid (Bitcoin), or which commits have been done in a SCM > (git, mercurial). > > So git is not magical, it is just a practical implementation of something > that works. Any other *general* solution will be based on similar basic > principles. Mercurial does this and there is a GPG extension for it. > > Bazaar does not use a SHA1-based content addressable storage, so while a > signed commit signs the tree, it does not represent the history (no "hash > of hash", only "hash" if you look at it as a merkle tree), but it does > chain commits. To verify a tree + history, *all* commits must be signed, > which is fragile IMO. > > Regarding Darcs, my understanding is that it deliberately rejects hashing > the tree, so it is not clear to me how to verify tree+history. Patches can > be signed, but as long as patches are independent, there is no "hash of > hash" component which makes it difficult to see how one can verify the > tree. My understanding of darcs is very limited though. > > But to be *practical* the rest of the workflow should be secure as well, > so you need: > > 1. A way to distribute the merkle tree (git pull/clone/push). > Distribution is of the data that is to be signed is required for > security, because otherwise the representation of the data itself (web view > or 'git diff') can be compromised. Signatures have no meaning if you > cannot trust that you know what you sign. > 2. A way to sign a change to the merkle tre (git commit -S, git tag -s etc) > 3. A way to have multiple signatures on a given hash (i.e. commit, or tag, > or whatever it is called in a particular merkle tree implementation). > This is required to avoid catastrophic "owning" of core developers. > If required, I do think that multiple signatures can be emulated by a > structured set of commits that have single signatures though. > 3. A way to reliably do code reviews on the changes to the data (git diff) > This is really the same as 1). We cannot reliably do 'git diff' > unless the developers do it on their own equipment, thus the system must be > distributed. > 4. Given the requirement for a distributed merkle tree, some merge > strategy is needed. It is thus practical, though not required, to have > good support for this. > (Btw, even the bitcoin hash chain has a merge strategy - the tree with > the most compute power will win, and others are forced to "rebase" their > transactions on that tree) > > > So my choice of git is not arbitrary. The way git works is pretty > fundamental to verifying the integrity of stuff. > > Though when I have looked through the other options, mercurial might be a > better fit since it is supported on Windows. > > Trying to solve this problem from scratch might not be such a good idea, > because it might be very close to a reimplementation of git or mercurial. > Or maybe it is a good idea for someone who has some time on their hands. > Just be aware that the requirements for verifying anything is very close > to what existing distributed SCM systems do. > > Alexander > > > On Fri, Feb 1, 2013 at 3:32 AM, Kevin Quick <quick(a)sparq.org> wrote: > >> Git has the ability to solve all of this. >>> >> ... >> >> 2. Uploads to hackage either happen through commits to the git >>> repository, >>> or an old-style upload to hackage automatically creates a new anonymous >>> branch in the git repository. >>> 3. The git repository is authorative. Signing releases, code reviews >>> etc. >>> all happens through the git repositories. This gives us all the >>> flexibility of a git-style trust model. >>> >> ... >> >> 5. Who owns which package names can be held in a separate meta-tree git >>> repository, and can have consensus requirements on commits. >>> 6. This special meta-tree can also contain suggested verification keys >>> for >>> commits to the other hackage git trees. It can even contain keys that >>> protect Haskell namespaces in general, so that no hackage package can >>> overwrite a protected Haskell namespace. >>> 7. As backward compatibility, the meta-tree can sign simple hashes of >>> already existing packages on hackage. >>> >> ... >> >> 1. There could be some git magic script that downloads the signed git tag >>> objects only (small data set). Then another script would generate a >>> git-compatible SHA1 of the extracted tarball, given that the tarball was >>> fetched from hackage. >>> 2. Or cabal-install could fetch directly from git repositories and use >>> standard git verification. >>> 3. Or a trusted machine creates tarballs from the git repositories, signs >>> them and uploads them to hackage. >>> >> >> Without details of git's trust/verification model, it's difficult to see >> how this particular SCM tool provides the trust capabilities being >> discussed any better than a more focused solution. Additionally, the use >> of git is also difficult for many Windows users (80MB installed footprint, >> last I tried). git has a much broader solution space than simply ensuring >> the integrity of package downloads, especially when "there could be some >> git magic script" that is still not identified and appears to have the same >> insecurities as the package download/upload itself. >> >> Instead of using the "git" solution and looking for problems to solve >> with it, IMHO we should work from clearly defined problem to solution in >> general terms as our class, and then determine what specific tools >> represent an instance of that solution class. >> >> -- >> -KQ >> >> >> ______________________________**_________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/**mailman/listinfo/haskell-cafe<http://www.haskell.org/mailman/listinfo/haskell-cafe> >> > >

1 0