using Map rather than FiniteMap

S. Alexander Jacobson

25 Jan 2005 25 Jan '05

2:54 p.m.

Just did a search after my last post and learned that FiniteMap is bad. Discoverd that Data.Map is the intended replacement. Downloaded it and modified it to work with 6.2. Blazingly fast! Yay. Please ignore the prior message. -Alex- ______________________________________________________________ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com

Show replies by date

Ketil Malde

25 Jan 25 Jan

3:48 p.m.

"S. Alexander Jacobson" writes:

...

Just did a search after my last post and learned that FiniteMap is bad. Discoverd that Data.Map is the intended replacement. Downloaded it and modified it to work with 6.2. Blazingly fast!

Oh? I was aware that Data.Map was supposed to be better, but not that FiniteMap was particularly bad. Is there any information about when, why and by how much Data.Map is better? -kzm -- If I haven't seen further, it is by standing in the footprints of giants

S. Alexander Jacobson

3:53 p.m.

I didn't find any such information. I just decided to look at the FiniteMap source code in CVS and discovered in the comments that it was deprecated in favor of Data.Map. So I downloaded the new Data.Map and Data.Set and ran the code I posted before. I executed basically instantly and used minimal memory. I think Map picked up a lot of speed because it doesn't spaceleak, but am not sure. -Alex- On Tue, 25 Jan 2005, Ketil Malde wrote:

...

"S. Alexander Jacobson" writes:

...
Just did a search after my last post and learned that FiniteMap is bad. Discoverd that Data.Map is the intended replacement. Downloaded it and modified it to work with 6.2. Blazingly fast!

Oh? I was aware that Data.Map was supposed to be better, but not that FiniteMap was particularly bad. Is there any information about when, why and by how much Data.Map is better?

-kzm -- If I haven't seen further, it is by standing in the footprints of giants

______________________________________________________________ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com

Jorge Adriano Aires

4:54 p.m.

...

Just did a search after my last post and learned that FiniteMap is bad. Discoverd that Data.Map is the intended replacement. Downloaded it and modified it to work with 6.2. Blazingly fast!

Yay.

Hi, just curious, How much trouble was getting it to work with ghc 6.2 and adapting your program to use the API of Data.Map instead of Data.FiniteMap? J.A.

S. Alexander Jacobson

6:26 p.m.

Oops. It pays to check your checking code before making posts like this. After actually running the correct test, I am still getting semi-ridiculous space behavior (6k/pair)! import qualified Map zipped =zip [1..] [1..100000]::[(Int,Int)] untup f (x,y) = f x y produce = foldr (untup Map.insert) Map.empty zipped fm = length $ Map.keys produce main = print $ fm Has this profile: example +RTS -p -K5M -RTS total time = 5.10 secs (255 ticks @ 20 ms) total alloc = 612,534,236 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc balance Map 71.8 72.8 insert Map 12.2 10.8 size Map 9.0 9.7 bin Map 2.4 2.2 rotateR Map 1.6 0.3 zipped Main 0.8 1.9 Notice the 612Mb for storing a mapping from Int to Int!! Also 5M of stack is required to make this work. Can anyone help? -Alex- ______________________________________________________________ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com On Tue, 25 Jan 2005, Jorge Adriano Aires wrote:

...

...
Just did a search after my last post and learned that FiniteMap is bad. Discoverd that Data.Map is the intended replacement. Downloaded it and modified it to work with 6.2. Blazingly fast!

Yay.

Hi, just curious, How much trouble was getting it to work with ghc 6.2 and adapting your program to use the API of Data.Map instead of Data.FiniteMap?

J.A.

David Menendez

10:59 p.m.

S. Alexander Jacobson writes:

...

After actually running the correct test, I am still getting semi-ridiculous space behavior (6k/pair)!

import qualified Map zipped =zip [1..] [1..100000]::[(Int,Int)] untup f (x,y) = f x y produce = foldr (untup Map.insert) Map.empty zipped fm = length $ Map.keys produce main = print $ fm

Two questions I'm currently too lazy to investigate myself: Does having 'zipped' at the top level mean that the program is keeping the entire 100,000-element list in memory? Also, would performance improve if you used Map.fromList? How about Map.fromAscList? -- David Menendez | "In this house, we obey the laws http://www.eyrie.org/~zednenem | of thermodynamics!"

S. Alexander Jacobson

26 Jan 26 Jan

12:21 p.m.

On Tue, 25 Jan 2005, David Menendez wrote:

...

Does having 'zipped' at the top level mean that the program is keeping the entire 100,000-element list in memory?

I don't know, but I tested with zipped at the top, in the where, and it appears to make no performance or memory difference.

...

Also, would performance improve if you used Map.fromList? How about Map.fromAscList?

HUGE IMPROVEMENT. The old code had maximum residency of 11Mb and running time of 41s. The code using Map.fromList has max. residency of 6.4Mb and running time of 5.2s! I guess foldlStrict is HUGELY more efficient than than foldr. (Why isn't it in the prelude?) But even using foldrStrict (fromList), we are still using 60 bytes per item and have ~30 bytes unaccounted for. Any hints? import qualified Map main = print $ length $ Map.keys theMap where zipped =zip [1..] [1..100000]::[(Int,Int)] theMap = Map.fromList zipped -Alex- ______________________________________________________________ S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com

...

S. Alexander Jacobson writes:

...
After actually running the correct test, I am still getting semi-ridiculous space behavior (6k/pair)!

import qualified Map zipped =zip [1..] [1..100000]::[(Int,Int)] untup f (x,y) = f x y produce = foldr (untup Map.insert) Map.empty zipped fm = length $ Map.keys produce main = print $ fm

Two questions I'm currently too lazy to investigate myself:

-- David Menendez | "In this house, we obey the laws http://www.eyrie.org/~zednenem | of thermodynamics!"

Christian Maeder

11:09 a.m.

S. Alexander Jacobson wrote:

...

zipped =zip [1..] [1..100000]::[(Int,Int)] untup f (x,y) = f x y produce = foldr (untup Map.insert) Map.empty zipped fm = length $ Map.keys produce main = print $ fm

Has this profile:

example +RTS -p -K5M -RTS

total time = 5.10 secs (255 ticks @ 20 ms) total alloc = 612,534,236 bytes (excludes profiling overheads)

COST CENTRE MODULE %time %alloc balance Map 71.8 72.8 insert Map 12.2 10.8 size Map 9.0 9.7 bin Map 2.4 2.2 rotateR Map 1.6 0.3 zipped Main 0.8 1.9

I get similar results without optimizations and much better ones using only about 160MB with -O. Cheers Christian -- unoptimized testMap +RTS -p -K5m -RTS total time = 6.34 secs (317 ticks @ 20 ms) total alloc = 612,549,684 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc balance Common.Lib.Map 74.1 72.8 insert Common.Lib.Map 9.8 10.8 size Common.Lib.Map 9.5 9.7 bin Common.Lib.Map 1.6 2.2 zipped Main 1.3 1.9 -- optimized results ghc --make TestMap.hs -O -prof -auto-all -o testMap testMap +RTS -p -K5m -RTS total time = 1.22 secs (61 ticks @ 20 ms) total alloc = 159,737,668 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc insert Common.Lib.Map 39.3 0.5 balance Common.Lib.Map 24.6 47.4 size Common.Lib.Map 21.3 34.1 foldR Common.Lib.Map 3.3 2.5 zipped Main 3.3 6.5 untup Main 3.3 0.8 produce Main 3.3 0.8 singleR Common.Lib.Map 1.6 0.0 toAscList Common.Lib.Map 0.0 1.5 single Common.Lib.Map 0.0 1.5 keys Common.Lib.Map 0.0 1.5 bin Common.Lib.Map 0.0 3.0

7419

Age (days ago)

7420

Last active (days ago)

List overview

Download

7 comments

5 participants

participants (5)

Christian Maeder
David Menendez
Jorge Adriano Aires
Ketil Malde
S. Alexander Jacobson