# Map.fromList slow for 6-tuple with 15000 items

**URL:** <https://discourse.haskell.org/t/map-fromlist-slow-for-6-tuple-with-15000-items/8827>\
**Category:** Uncategorized\
**Created:** [February 18, 2024, 7:41pm UTC](https://discourse.haskell.org/t/map-fromlist-slow-for-6-tuple-with-15000-items/8827 "2024-02-18T19:41:45Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![emiruz](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/emiruz/32/4042_2.png) [@emiruz](https://discourse.haskell.org/u/emiruz)\
**Post date:** [February 18, 2024, 7:41pm UTC](https://discourse.haskell.org/t/map-fromlist-slow-for-6-tuple-with-15000-items/8827/1 "2024-02-18T19:41:45Z")

</div>

I’m using `import Data.Map.Strict as M` and then doing `M.fromList xs` where `xs` is a list of 15000 items of the type `[((b, b, b), (b, b, c))]` where `b` is an `Int` and `c` is a `Char`. The list is fully materialised when `M.fromList` is called, yet it takes about **30 seconds** to create the map! I verified this by creating the list without the map and checking its length (it takes about 1 second).

Is this expected?

---

<div class="post-metadata">

**Author:** ![jaror](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/jaror/32/3271_2.png) [@jaror](https://discourse.haskell.org/u/jaror)\
**Post date:** [February 18, 2024, 8:15pm UTC](https://discourse.haskell.org/t/map-fromlist-slow-for-6-tuple-with-15000-items/8827/2 "2024-02-18T20:15:09Z")

</div>

Are you sure the list is fully evaluated before converting to a map? Testing the length of the list is not always enough. It’s better to use `force` or `rnf` from the deepseq package.

---

<div class="post-metadata">

**Author:** ![emiruz](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/emiruz/32/4042_2.png) [@emiruz](https://discourse.haskell.org/u/emiruz)\
**Post date:** [February 18, 2024, 8:45pm UTC](https://discourse.haskell.org/t/map-fromlist-slow-for-6-tuple-with-15000-items/8827/3 "2024-02-18T20:45:48Z")

</div>

Is `last` enough ? If so, yes its the same result as when using `length`.

---

<div class="post-metadata">

**Author:** ![tomjaguarpaw](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/tomjaguarpaw/32/1230_2.png) [@tomjaguarpaw](https://discourse.haskell.org/u/tomjaguarpaw)\
**Post date:** [February 18, 2024, 8:53pm UTC](https://discourse.haskell.org/t/map-fromlist-slow-for-6-tuple-with-15000-items/8827/4 "2024-02-18T20:53:17Z")

</div>

No, `last` is not enough. You have to force the contents of each tuples element in the list.

---

<div class="post-metadata">

**Author:** ![emiruz](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/emiruz/32/4042_2.png) [@emiruz](https://discourse.haskell.org/u/emiruz)\
**Post date:** [February 18, 2024, 8:53pm UTC](https://discourse.haskell.org/t/map-fromlist-slow-for-6-tuple-with-15000-items/8827/5 "2024-02-18T20:53:24Z")

</div>

Ok, I think I know what it may be. I think these shallow queries (last or length) do not require evaluation of nested structure, and so pass quickly. Meanwhile there is a O(log(N)) operation which ends up executed per item only when M.fromList hits.

---

<div class="post-metadata">

**Author:** ![jaror](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/jaror/32/3271_2.png) [@jaror](https://discourse.haskell.org/u/jaror)\
**Post date:** [February 18, 2024, 9:56pm UTC](https://discourse.haskell.org/t/map-fromlist-slow-for-6-tuple-with-15000-items/8827/6 "2024-02-18T21:56:44Z")

</div>

If you don’t want to use the deepseq package you can also use this function in your case:

```haskell
myseq :: [((Int,Int,Int),(Int,Int,Char))] -> a -> a
myseq [] a = a
myseq (((!x1,!x2,!x3),(!y1,!y2,!y3)):xs) a = myseq xs a

```

---

<div class="post-metadata">

**Author:** ![BurningWitness](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/burningwitness/32/3665_2.png) [@BurningWitness](https://discourse.haskell.org/u/BurningWitness)\
**Post date:** [February 19, 2024, 6:00am UTC](https://discourse.haskell.org/t/map-fromlist-slow-for-6-tuple-with-15000-items/8827/7 "2024-02-19T06:00:17Z")

</div>

Could also build the dictionary while at it:

```haskell
f :: Ord b => [((b, b, b), (b, b, c))] -> Map (b, b, b) (b, b, c)
f = foldl' (\z (k@(!_, !_, !_), a@(!_, !_, !_)) -> Map.insert k a z) Map.empty

```

If the list is fed into `f` and never mentioned again, the garbage collector won’t be obligated to keep the entire list in memory.

---

<div class="post-metadata">

**Author:** ![tomjaguarpaw](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/tomjaguarpaw/32/1230_2.png) [@tomjaguarpaw](https://discourse.haskell.org/u/tomjaguarpaw)\
**Post date:** [February 19, 2024, 7:31am UTC](https://discourse.haskell.org/t/map-fromlist-slow-for-6-tuple-with-15000-items/8827/8 "2024-02-19T07:31:39Z")

</div>

But aren’t we trying to distinguish the time take to build the list from the time taken to build the map?

---

<div class="post-metadata">

**Author:** ![BurningWitness](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/burningwitness/32/3665_2.png) [@BurningWitness](https://discourse.haskell.org/u/BurningWitness)\
**Post date:** [February 19, 2024, 8:32am UTC](https://discourse.haskell.org/t/map-fromlist-slow-for-6-tuple-with-15000-items/8827/9 "2024-02-19T08:32:04Z")

</div>

Perhaps, but then the question won’t be about dictionaries, it will be about constructing the intermediate data structure (currently list) in such a way that it doesn’t take 30 seconds to evaluate.

---

<div class="post-metadata">

**Author:** ![jaror](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/jaror/32/3271_2.png) [@jaror](https://discourse.haskell.org/u/jaror)\
**Post date:** [February 19, 2024, 9:08am UTC](https://discourse.haskell.org/t/map-fromlist-slow-for-6-tuple-with-15000-items/8827/10 "2024-02-19T09:08:58Z")

</div>

My understanding is that the question is:

> Why does it take 30 seconds to create the map, while creating the list only takes 1 second?

I’m guessing that these measurements may have been due to wrong assumptions. I’m wondering if the list is really fully evaluated in that 1 second or if that is only the time it takes to construct the spine of the list.

One way to test that is to compare the running time of these two main functions:

```haskell
main1 = M.toList (M.fromList xs) `myseq` putStrLn "Done!"

main2 = xs `myseq` putStrLn "Done!"

```

That’s how I suggest you should use `myseq`.

---

<div class="post-metadata">

**Author:** ![olf](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/olf/32/3813_2.png) [@olf](https://discourse.haskell.org/u/olf)\
**Post date:** [February 19, 2024, 9:57am UTC](https://discourse.haskell.org/t/map-fromlist-slow-for-6-tuple-with-15000-items/8827/11 "2024-02-19T09:57:54Z")

</div>

Also keep in mind that creation of a `Data.Map` from an unordered list is at least as expensive as ordering the list, while comparisons on 3-tuples itself is not terribly efficient. Building such a map also requires re-arranging the internal tree, which entails garbage collections. There are other container types that are more efficient. `Data.Map` should only be used if having the keys sorted is a must, e.g. for min/max queries, splitting the map or traversal in order.

---

<div class="post-metadata">

**Author:** ![emiruz](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/emiruz/32/4042_2.png) [@emiruz](https://discourse.haskell.org/u/emiruz)\
**Post date:** [February 22, 2024, 11:39am UTC](https://discourse.haskell.org/t/map-fromlist-slow-for-6-tuple-with-15000-items/8827/12 "2024-02-22T11:39:02Z")

</div>

You were quite right. The issue is that the list items had a nested structure and they were only partly evaluated.