What is the most efficient way to hardcode a map in Haskell?

Question

I want to hard code a map in Haskell. I can see at least three ways to do it:

Using multiple equations:

message 200 = "OK"
message 404 = "Not found"
...

Using a case expression:

message s = case s of
    200 -> "OK"
    404 -> "Not found"

Actually using a Map.

Which is the most efficient way do it? Is one solution faster than the others, and why? Are the first two solutions equivalent? (Will the compiler generates the same code?) What is the recommended way (easier to read)?

(Note that I use Int in my example, but that is not essential. The keys might be Strings as well so I'm interested in both cases.)

`String` is not a good type to use in most cases if you're interested in efficiency. It's unlikely that the GHC developers even tried to write special optimizations for pattern matching `String`s—I imagine they're matched the same way other lists are. — dfeuer, May 20 '14 at 18:17
For strings, you might want to consider using the `bytestring` and `bytestring-trie` packages. — dfeuer, May 20 '14 at 18:29

score 6 · Answer 1 · answered May 20 '14 at 01:33

Pattern matching on Ints happens in O(log(n)) time, like a map lookup.

Consider the following code, compiled to x86 assembly by ghc -S

module F (
    f
) where

f :: Int -> String
f 0 = "Zero"
f 1 = "One"
f 2 = "Two"
f 3 = "Three"
f 4 = "Four"
f 5 = "Five"
f 6 = "Six"
f 7 = "Seven"
f _ = "Undefined"

The compiled assembly code is

.text
    .align 4,0x90
    .long   _F_f_srt-(_sl8_info)+0
    .long   0
    .long   65568
_sl8_info:
.Lcma:
    movl 3(%esi),%eax
    cmpl $4,%eax
    jl .Lcmq
    cmpl $6,%eax
    jl .Lcmi
    cmpl $7,%eax
    jl .Lcme
    cmpl $7,%eax
    jne .Lcmc
    movl $_ghczmprim_GHCziCString_unpackCStringzh_closure,%esi
    movl $_cm7_str,0(%ebp)
    jmp _stg_ap_n_fast
.Lcmc:
    movl $_ghczmprim_GHCziCString_unpackCStringzh_closure,%esi
    movl $_clB_str,0(%ebp)
    jmp _stg_ap_n_fast
.Lcme:
    cmpl $6,%eax
    jne .Lcmc
    movl $_ghczmprim_GHCziCString_unpackCStringzh_closure,%esi
    movl $_cm3_str,0(%ebp)
    jmp _stg_ap_n_fast
.Lcmg:
    cmpl $4,%eax
    jne .Lcmc
    movl $_ghczmprim_GHCziCString_unpackCStringzh_closure,%esi
    movl $_clV_str,0(%ebp)
    jmp _stg_ap_n_fast
.Lcmi:
    cmpl $5,%eax
    jl .Lcmg
    cmpl $5,%eax
    jne .Lcmc
    movl $_ghczmprim_GHCziCString_unpackCStringzh_closure,%esi
    movl $_clZ_str,0(%ebp)
    jmp _stg_ap_n_fast
.Lcmk:
    cmpl $2,%eax
    jne .Lcmc
    movl $_ghczmprim_GHCziCString_unpackCStringzh_closure,%esi
    movl $_clN_str,0(%ebp)
    jmp _stg_ap_n_fast
.Lcmm:
    testl %eax,%eax
    jne .Lcmc
    movl $_ghczmprim_GHCziCString_unpackCStringzh_closure,%esi
    movl $_clF_str,0(%ebp)
    jmp _stg_ap_n_fast
.Lcmo:
    cmpl $1,%eax
    jl .Lcmm
    cmpl $1,%eax
    jne .Lcmc
    movl $_ghczmprim_GHCziCString_unpackCStringzh_closure,%esi
    movl $_clJ_str,0(%ebp)
    jmp _stg_ap_n_fast
.Lcmq:
    cmpl $2,%eax
    jl .Lcmo
    cmpl $3,%eax
    jl .Lcmk
    cmpl $3,%eax
    jne .Lcmc
    movl $_ghczmprim_GHCziCString_unpackCStringzh_closure,%esi
    movl $_clR_str,0(%ebp)
    jmp _stg_ap_n_fast
.text
    .align 4,0x90
    .long   _F_f_srt-(_F_f_info)+0
    .long   65541
    .long   0
    .long   65551
.globl _F_f_info
_F_f_info:
.Lcmu:
    movl 0(%ebp),%esi
    movl $_sl8_info,0(%ebp)
    testl $3,%esi
    jne .Lcmx
    jmp *(%esi)
.Lcmx:
    jmp _sl8_info

This is doing a binary search on the integer arguments. .Lcma is branching on <4 then <6 then <7. The first comparsion goes to .Lcmq which is branching on <2 then <3. The first comparison from that goes to .Lcmo, which branches on <1.

With ghc -O2 -S, instead we get this, where we can see the same pattern:

.text
    .align 4,0x90
    .long   _F_zdwf_srt-(_F_zdwf_info)+0
    .long   65540
    .long   0
    .long   33488911
.globl _F_zdwf_info
_F_zdwf_info:
.LcqO:
    movl 0(%ebp),%eax
    cmpl $4,%eax
    jl .Lcr6
    cmpl $6,%eax
    jl .LcqY
    cmpl $7,%eax
    jl .LcqU
    cmpl $7,%eax
    jne .LcqS
    movl $_F_f1_closure,%esi
    addl $4,%ebp
    andl $-4,%esi
    jmp *(%esi)
.LcqS:
    movl $_F_f9_closure,%esi
    addl $4,%ebp
    andl $-4,%esi
    jmp *(%esi)
.LcqU:
    cmpl $6,%eax
    jne .LcqS
    movl $_F_f2_closure,%esi
    addl $4,%ebp
    andl $-4,%esi
    jmp *(%esi)
.LcqW:
    cmpl $4,%eax
    jne .LcqS
    movl $_F_f4_closure,%esi
    addl $4,%ebp
    andl $-4,%esi
    jmp *(%esi)
.LcqY:
    cmpl $5,%eax
    jl .LcqW
    cmpl $5,%eax
    jne .LcqS
    movl $_F_f3_closure,%esi
    addl $4,%ebp
    andl $-4,%esi
    jmp *(%esi)
.Lcr0:
    cmpl $2,%eax
    jne .LcqS
    movl $_F_f6_closure,%esi
    addl $4,%ebp
    andl $-4,%esi
    jmp *(%esi)
.Lcr2:
    testl %eax,%eax
    jne .LcqS
    movl $_F_f8_closure,%esi
    addl $4,%ebp
    andl $-4,%esi
    jmp *(%esi)
.Lcr4:
    cmpl $1,%eax
    jl .Lcr2
    cmpl $1,%eax
    jne .LcqS
    movl $_F_f7_closure,%esi
    addl $4,%ebp
    andl $-4,%esi
    jmp *(%esi)
.Lcr6:
    cmpl $2,%eax
    jl .Lcr4
    cmpl $3,%eax
    jl .Lcr0
    cmpl $3,%eax
    jne .LcqS
    movl $_F_f5_closure,%esi
    addl $4,%ebp
    andl $-4,%esi
    jmp *(%esi)
.section .data
    .align 4
.align 1
_F_f_srt:
    .long   _F_zdwf_closure
.data
    .align 4
.align 1
.globl _F_f_closure
_F_f_closure:
    .long   _F_f_info
    .long   0
.text
    .align 4,0x90
    .long   _F_f_srt-(_srh_info)+0
    .long   0
    .long   65568
_srh_info:
.Lcrv:
    movl 3(%esi),%eax
    movl %eax,0(%ebp)
    jmp _F_zdwf_info
.text
    .align 4,0x90
    .long   _F_f_srt-(_F_f_info)+0
    .long   65541
    .long   0
    .long   65551
.globl _F_f_info
_F_f_info:
.Lcrz:
    movl 0(%ebp),%esi
    movl $_srh_info,0(%ebp)
    testl $3,%esi
    jne _srh_info
    jmp *(%esi)

If we change the original code to

f :: Int -> String
f 1 = "Zero"
f 2 = "One"
f 3 = "Two"
f 4 = "Three"
f 5 = "Four"
f 6 = "Five"
f 7 = "Six"
f 8 = "Seven"
f _ = "Undefined"

The branches are on <5, <7, <8, with <5 going to <3, <4, etc., so it's probably doing this based on sorting the arguments. We can test that by scrambling the numbers, and even adding spacing between them:

f :: Int -> String
f 20 = "Zero"
f 80 = "One"
f 70 = "Two"
f 30 = "Three"
f 40 = "Four"
f 50 = "Five"
f 10 = "Six"
f 60 = "Seven"
f _ = "Undefined"

Sure enough, the branches are still on <50, <70, <80, with <50 going to <30, <40, etc.

If you use an ADT with `-O2` I believe you will get a jump table. Also see this haskell-cafe thread: https://groups.google.com/d/msg/haskell-cafe/-YTVNbNHHLo/rTWtxwZm8hkJ — ErikR, May 20 '14 at 04:57
this doesn't work well with strings - I had two generated functions with approx 16000 lines of patterns and it added several minutes to the package build time + was noticeably slow (although I didn't profile properly) — JonnyRaa, Apr 04 '18 at 16:33

score 3 · Answer 2 · edited May 23 '17 at 12:27

3

Apparently function pattern matching happens in O(1) (constant time), while Map's lookup (of course referring to Data.Map) is guaranteed to be O(logn).

Considering the above assumptions, I'd go with pattern matching:

message 200 = "OK"
message 404 = "Not found"

edited May 23 '17 at 12:27

Community

1
1

answered May 19 '14 at 22:50

Shoe

74,840
36
166
272

2

Do you have evidence of linear complexity? I'd be very surprised if that held for small algebraic types, but I suppose it could be true for `Int`s. – dfeuer May 19 '14 at 23:34
@dfeuer, Actually [it's constant time](http://stackoverflow.com/a/9027441/493122). Interesting. Updated answer accordingly. Thanks for making me check. – Shoe May 19 '14 at 23:43
2

Are you sure matching a constructor for an `Int` is implemented the same way as matching the tag for a constructor, which is what's happening in the linked answer? – Cirdec May 20 '14 at 00:06
2

See my answer for what actually happens when matching on a constructor for an Int. – Cirdec May 20 '14 at 01:36

Tobias Brandt · Answer 3 · 2014-05-19T22:58:28.413

1

The case ... of and the multiple equations are exactly equivalent. They compile to the same core. For a large number of cases you should probably do this:

import qualified Data.Map as Map

message =
    let
        theMap = Map.fromList [ (200, "OK"), (404, "Not found"), ... ]
    in
        \x -> Map.lookup x theMap

This constructs the map only once. If you don't like the Maybe String return type you can apply fromMaybe to the result.

For a small number of cases (especially if they are integers) the case statement is probably faster if the compiler can translate it to a jump table.

In an ideal world, ghc would pick the right version automatically.

edited May 19 '14 at 22:58

answered May 19 '14 at 22:50

Tobias Brandt

3,393
18
28

A jump table makes a lot of sense for a small type like `Bool` (well, maybe not *that* small), and probably also makes sense in some cases for a medium-sized one like `Word8`, and may make sense as part of a hybrid scheme for larger types (i.e., first check range, then jump if in the range) but for arbitrary values of a big type like `Int`, either a linear scan (for small numbers of cases) or a `Map`-like implementation (for large numbers of cases) should be more efficient, I believe. – dfeuer May 19 '14 at 23:33
1

This haskell-cafe thread touches on this topic: https://groups.google.com/d/msg/haskell-cafe/-YTVNbNHHLo/rTWtxwZm8hkJ – ErikR May 20 '14 at 04:59

What is the most efficient way to hardcode a map in Haskell?

3 Answers3