Send Beginners mailing list submissions to
beginners@haskell.org
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Errors while compiling webkit (Lorenzo Bolla)
2. Red-black tree performance (Adrien Haxaire)
3. Re: Red-black tree performance (Lorenzo Bolla)
4. Re: Red-black tree performance (Adrien Haxaire)
5. Re: Red-black tree performance (Heinrich Apfelmus)
6. Re: Errors while compiling webkit (Dino Morelli)
7. Re: Red-black tree performance (Lorenzo Bolla)
----------------------------------------------------------------------
Message: 1
Date: Tue, 20 Mar 2012 11:09:00 +0000
From: Lorenzo Bolla <lbo...@gmail.com>
Subject: [Haskell-beginners] Errors while compiling webkit
To: beginners@haskell.org
Message-ID:
<CADjgTRxSKxhwSxkWKSB+=c76-3xCt=fvqxazax1r0xrger1...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Hi all,
I'm trying to compile Haskell's webkit package, but I'm getting this error:
$ cabal install webkit
Resolving dependencies...
[1 of 2] Compiling SetupWrapper (
/tmp/webkit-0.12.3-9205/webkit-0.12.3/SetupWrapper.hs,
/tmp/webkit-0.12.3-9205/webkit-0.12.3/dist/setup/SetupWrapper.o )
[2 of 2] Compiling Main (
/tmp/webkit-0.12.3-9205/webkit-0.12.3/Setup.hs,
/tmp/webkit-0.12.3-9205/webkit-0.12.3/dist/setup/Main.o )
Linking /tmp/webkit-0.12.3-9205/webkit-0.12.3/dist/setup/setup ...
[1 of 2] Compiling Gtk2HsSetup ( Gtk2HsSetup.hs,
dist/setup-wrapper/Gtk2HsSetup.o )
[2 of 2] Compiling Main ( SetupMain.hs,
dist/setup-wrapper/Main.o )
Linking dist/setup-wrapper/setup ...
Configuring webkit-0.12.3...
Building webkit-0.12.3...
Preprocessing library webkit-0.12.3...
dist/build/Graphics/UI/Gtk/WebKit/Types.h:1:22: fatal error: hswebkit.h: No
such file or directory
compilation terminated.
gtk2hsC2hs: Error during preprocessing custom header file
cabal: Error: some packages failed to install:
webkit-0.12.3 failed during the building phase. The exception was:
ExitFailure 1
I'm compiling it inside a hsenv, with this ghc:
$ ghc -v
Glasgow Haskell Compiler, Version 7.4.1, stage 2 booted by GHC version 7.4.1
Using binary package database: /tmp/webkit/.hsenv/ghc_pkg_db/package.cache
wired-in package ghc-prim mapped to
ghc-prim-0.2.0.0-c2ff696e5b8ec4d4b2bc2e42085fe471
wired-in package integer-gmp mapped to
integer-gmp-0.4.0.0-3cccac07aef8e27023f605c1f45bdf74
wired-in package base mapped to
base-4.5.0.0-40b99d05fae6a4eea95ea69e6e0c9702
wired-in package rts mapped to builtin_rts
wired-in package template-haskell mapped to
template-haskell-2.7.0.0-8c8cd20e21666657195efabced685fe1
wired-in package dph-seq not found.
wired-in package dph-par not found.
Hsc static flags: -static
Any ideas?
Thanks,
L.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120320/4fb0d868/attachment-0001.htm>
------------------------------
Message: 2
Date: Tue, 20 Mar 2012 15:37:18 +0100
From: Adrien Haxaire <adr...@haxaire.org>
Subject: [Haskell-beginners] Red-black tree performance
To: <beginners@haskell.org>
Message-ID: <fc5670926825f7921bf214edda5e9...@haxaire.org>
Content-Type: text/plain; charset=UTF-8; format=flowed
Dear list,
I had to implement a red-black tree in C++. So I took Okasaki's
functional pearl and ported the algorithm to C++, where the rebalancing
is done by following parent pointers. I shew the Haskell algorithm to
colleagues, and after admitting it is impressive, they told me whatever
the beauty as long as we have performance. So I benchmarked it and the
C++ implementation, insertion of one million elements, and the C++
version is 15 times faster. Mainly because in C++ it is just moving
pointers around I guess. I have to mention that the space usage is
outrageous with Haskell.
The Tree is strict in its subtrees, but I think the problem comes from
the laziness of the balance function, which needs to hold the whole
tree.
This reduces to my main question: how can I decompose balance in a
stricter version? Or maybe I'm completely wrong and there is something
obvious I am missing?
If you want to take a look, the code is here: http://hpaste.org/65611
Adrien
PS: compiler options and profiling stderr output
> ghc -Wall -O2 -prof -auto-all -rtsopts rbt.hs
> rbt.exe +RTS -K20M -p -sstderr -RTS
1000000
964,079,612 bytes allocated in the heap
230,842,072 bytes copied during GC
58,442,812 bytes maximum residency (7 sample(s))
327,812 bytes maximum slop
105 MB total memory in use (0 MB lost due to
fragmentation)
Tot time (elapsed) Avg pause Max
pause
Gen 0 1810 colls, 0 par 0.30s 0.27s 0.0001s
0.0034s
Gen 1 7 colls, 0 par 0.19s 0.19s 0.0278s
0.0938s
INIT time 0.00s ( 0.00s elapsed)
MUT time 1.78s ( 1.82s elapsed)
GC time 0.48s ( 0.46s elapsed)
RP time 0.00s ( 0.00s elapsed)
PROF time 0.00s ( 0.00s elapsed)
EXIT time 0.00s ( 0.00s elapsed)
Total time 2.28s ( 2.28s elapsed)
%GC time 21.2% (20.3% elapsed)
Alloc rate 537,387,643 bytes per MUT second
Productivity 78.8% of total user, 78.5% of total elapsed
--
Adrien Haxaire
www.adrienhaxaire.org | @adrienhaxaire
------------------------------
Message: 3
Date: Tue, 20 Mar 2012 16:27:08 +0000
From: Lorenzo Bolla <lbo...@gmail.com>
Subject: Re: [Haskell-beginners] Red-black tree performance
To: Adrien Haxaire <adr...@haxaire.org>
Cc: beginners@haskell.org
Message-ID:
<CADjgTRwXb+nSH3rq9iq+XXW=jk8Bg5mnQKsKsfyDpzh593=8...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Your scripts stack-overflows on my box.
I've made 2 little changes, to ensure strictness. I believe your
"insertList" is building up a huge list of thunks.
import Data.Foldable (foldr')
<snip>
main :: IO ()
main = putStrLn $ show $ maxTree $ foldr' insert Empty toInsert
Better?
L.
On Tue, Mar 20, 2012 at 2:37 PM, Adrien Haxaire <adr...@haxaire.org> wrote:
> Dear list,
>
> I had to implement a red-black tree in C++. So I took Okasaki's functional
> pearl and ported the algorithm to C++, where the rebalancing is done by
> following parent pointers. I shew the Haskell algorithm to colleagues, and
> after admitting it is impressive, they told me whatever the beauty as long
> as we have performance. So I benchmarked it and the C++ implementation,
> insertion of one million elements, and the C++ version is 15 times faster.
> Mainly because in C++ it is just moving pointers around I guess. I have to
> mention that the space usage is outrageous with Haskell.
>
> The Tree is strict in its subtrees, but I think the problem comes from the
> laziness of the balance function, which needs to hold the whole tree.
>
> This reduces to my main question: how can I decompose balance in a
> stricter version? Or maybe I'm completely wrong and there is something
> obvious I am missing?
>
> If you want to take a look, the code is here: http://hpaste.org/65611
>
>
> Adrien
>
>
> PS: compiler options and profiling stderr output
>
> ghc -Wall -O2 -prof -auto-all -rtsopts rbt.hs
>>
>
> rbt.exe +RTS -K20M -p -sstderr -RTS
>>
> 1000000
> 964,079,612 bytes allocated in the heap
> 230,842,072 bytes copied during GC
> 58,442,812 bytes maximum residency (7 sample(s))
> 327,812 bytes maximum slop
> 105 MB total memory in use (0 MB lost due to fragmentation)
>
> Tot time (elapsed) Avg pause Max pause
> Gen 0 1810 colls, 0 par 0.30s 0.27s 0.0001s 0.0034s
> Gen 1 7 colls, 0 par 0.19s 0.19s 0.0278s 0.0938s
>
> INIT time 0.00s ( 0.00s elapsed)
> MUT time 1.78s ( 1.82s elapsed)
> GC time 0.48s ( 0.46s elapsed)
> RP time 0.00s ( 0.00s elapsed)
> PROF time 0.00s ( 0.00s elapsed)
> EXIT time 0.00s ( 0.00s elapsed)
> Total time 2.28s ( 2.28s elapsed)
>
> %GC time 21.2% (20.3% elapsed)
>
> Alloc rate 537,387,643 bytes per MUT second
>
> Productivity 78.8% of total user, 78.5% of total elapsed
>
>
>
>
> --
> Adrien Haxaire
> www.adrienhaxaire.org | @adrienhaxaire
>
> ______________________________**_________________
> Beginners mailing list
> Beginners@haskell.org
> http://www.haskell.org/**mailman/listinfo/beginners<http://www.haskell.org/mailman/listinfo/beginners>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120320/aac10451/attachment-0001.htm>
------------------------------
Message: 4
Date: Tue, 20 Mar 2012 18:05:15 +0100
From: Adrien Haxaire <adr...@haxaire.org>
Subject: Re: [Haskell-beginners] Red-black tree performance
To: beginners@haskell.org
Message-ID: <20120320170515.GA1426@arch>
Content-Type: text/plain; charset=us-ascii
On Tue, Mar 20, 2012 at 04:27:08PM +0000, Lorenzo Bolla wrote:
> Your scripts stack-overflows on my box.
>
> I've made 2 little changes, to ensure strictness. I believe your
> "insertList" is building up a huge list of thunks.
>
> import Data.Foldable (foldr')
> <snip>
> main :: IO ()
> main = putStrLn $ show $ maxTree $ foldr' insert Empty toInsert
>
> Better?
> L.
Yes definitely, thank you. That was someting obvious that I didn't see.
Now I have 0.64 seconds for C++ and 3.95 for Haskell. That's better!
The ratio 3.95/0.64 is 6.171875, which is more in the range I expected. That's
twice better from what I had before.
I am still looking at the balance function, maybe there is some things I can
optimize there as well.
--
Adrien Haxaire
www.adrienhaxaire.org | @adrienhaxaire
------------------------------
Message: 5
Date: Tue, 20 Mar 2012 18:30:04 +0100
From: Heinrich Apfelmus <apfel...@quantentunnel.de>
Subject: Re: [Haskell-beginners] Red-black tree performance
To: beginners@haskell.org
Message-ID: <jkaeqs$8l6$1...@dough.gmane.org>
Content-Type: text/plain; charset=UTF-8; format=flowed
Lorenzo Bolla wrote:
> Your scripts stack-overflows on my box.
>
> I've made 2 little changes, to ensure strictness. I believe your
> "insertList" is building up a huge list of thunks.
>
> import Data.Foldable (foldr')
> <snip>
> main :: IO ()
> main = putStrLn $ show $ maxTree $ foldr' insert Empty toInsert
>
> Better?
Huh, why foldr' and not Data.List.foldl' ? As far as I understand, the
former has to evaluate the whole spine of the list first before it can
begin to assemble the tree. The latter can start building trees right away.
I'm not sure whether the integers in toInsert are evaluated to WHNF.
You can make the insert function strict in the first argument to make
sure that they are.
Best regards,
Heinrich Apfelmus
--
http://apfelmus.nfshost.com
------------------------------
Message: 6
Date: Tue, 20 Mar 2012 19:12:53 +0000 (UTC)
From: Dino Morelli <d...@ui3.info>
Subject: Re: [Haskell-beginners] Errors while compiling webkit
To: beginners@haskell.org
Message-ID: <loom.20120320t200141-...@post.gmane.org>
Content-Type: text/plain; charset=utf-8
Lorenzo Bolla <lbolla <at> gmail.com> writes:
> Hi all,
>
> I'm trying to compile Haskell's webkit package, but I'm getting this error:
>
>
> $ cabal install webkit
> Resolving dependencies...
> [1 of 2] Compiling SetupWrapper ? ? ( /tmp/webkit-0.12.3-9205/webkit-
0.12.3/SetupWrapper.hs, /tmp/webkit-0.12.3-9205/webkit-
0.12.3/dist/setup/SetupWrapper.o )
> [2 of 2] Compiling Main ? ? ? ? ? ? ( /tmp/webkit-0.12.3-9205/webkit-
0.12.3/Setup.hs, /tmp/webkit-0.12.3-9205/webkit-0.12.3/dist/setup/Main.o )
> Linking /tmp/webkit-0.12.3-9205/webkit-0.12.3/dist/setup/setup ...
> [1 of 2] Compiling Gtk2HsSetup ? ? ?( Gtk2HsSetup.hs, dist/setup-
wrapper/Gtk2HsSetup.o )
> [2 of 2] Compiling Main ? ? ? ? ? ? ( SetupMain.hs, dist/setup-wrapper/Main.o
)
> Linking dist/setup-wrapper/setup ...
> Configuring webkit-0.12.3...
> Building webkit-0.12.3...
> Preprocessing library webkit-0.12.3...
> dist/build/Graphics/UI/Gtk/WebKit/Types.h:1:22: fatal error: hswebkit.h: No
such file or directory
> compilation terminated.
> gtk2hsC2hs: Error during preprocessing custom header file
> cabal: Error: some packages failed to install:
> webkit-0.12.3 failed during the building phase. The exception was:
> ExitFailure 1
>
>
> I'm compiling it inside a hsenv, with this ghc:
>
> $ ghc -v
> Glasgow Haskell Compiler, Version 7.4.1, stage 2 booted by GHC version 7.4.1
>
> Using binary package database: /tmp/webkit/.hsenv/ghc_pkg_db/package.cache
> wired-in package ghc-prim mapped to ghc-prim-0.2.0.0-
c2ff696e5b8ec4d4b2bc2e42085fe471
> wired-in package integer-gmp mapped to integer-gmp-0.4.0.0-
3cccac07aef8e27023f605c1f45bdf74
> wired-in package base mapped to base-4.5.0.0-40b99d05fae6a4eea95ea69e6e0c9702
> wired-in package rts mapped to builtin_rts
> wired-in package template-haskell mapped to template-haskell-2.7.0.0-
8c8cd20e21666657195efabced685fe1
> wired-in package dph-seq not found.
> wired-in package dph-par not found.
> Hsc static flags: -static
>
>
> Any ideas?
>
> Thanks,
> L.
>
By complete chance, I happened to be trying to use webkit today as well,
ran into the same problem.
Looks like hswebkit.h isn't getting installed anywhere in an include
dir on my system. I was able to install and build against the webkit library
after copying that file manually myself from the root of the webkit dev dir
to /usr/local/include
You can get the webkit source to get this .h file:
$ darcs get http://code.haskell.org/webkit/
This is of course not a good long-term solution. I'm trying to figure out
whom to email or where to send a bug report now.
--
Dino Morelli email: d...@ui3.info web: http://ui3.info/d/
pubkey: http://ui3.info/d/dino-4AA4F02D-pub.gpg
------------------------------
Message: 7
Date: Tue, 20 Mar 2012 21:03:30 +0000
From: Lorenzo Bolla <lbo...@gmail.com>
Subject: Re: [Haskell-beginners] Red-black tree performance
To: Heinrich Apfelmus <apfel...@quantentunnel.de>
Cc: beginners@haskell.org
Message-ID:
<CADjgTRwJgvSkjGUXX4=moutv3y3w_tzkqkv5r6yenuqraqt...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Tue, Mar 20, 2012 at 5:30 PM, Heinrich Apfelmus <
apfel...@quantentunnel.de> wrote:
> Lorenzo Bolla wrote:
>
>> Your scripts stack-overflows on my box.
>>
>> I've made 2 little changes, to ensure strictness. I believe your
>> "insertList" is building up a huge list of thunks.
>>
>> import Data.Foldable (foldr')
>> <snip>
>> main :: IO ()
>> main = putStrLn $ show $ maxTree $ foldr' insert Empty toInsert
>>
>> Better?
>>
>
> Huh, why foldr' and not Data.List.foldl' ? As far as I understand, the
> former has to evaluate the whole spine of the list first before it can
> begin to assemble the tree. The latter can start building trees right away.
>
>
Yes, definitely foldl' is worth a try, too:
main = putStrLn $ show $ maxTree $ foldl' (flip insert) Empty toInsert
L.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20120320/53b8c3df/attachment.htm>
------------------------------
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 45, Issue 25
*****************************************
