3

I'm implementing a symbol table for a translator in haskell. My question is how big should the table be on an average use-case before converting from an association list to a trie/map/hashmap, assuming my keys are small strings or bytestrings? I don't want to use hashtable because unwrapping from the io Monad seems like a step backwards in terms of efficiency (insert haskell efficiency joke here :))

Edit: Strike my comment about hashtables. They are as good an option as the others, according to the most recent implementations.

5
  • What are you optimising for? Feb 1, 2014 at 22:14
  • 1
    I might be misunderstanding you, but I don't see a minimum size for using a map, seeing as it's so easy to use.
    – not my job
    Feb 1, 2014 at 22:16
  • I don't understand the comment about hashmaps being inefficient; can you explain what you're worried about? I also don't understand what "unwrapping from the IO monad" means. If you make your problem description more precise, you can expect to get better advice about what tradeoffs to be aware of. Feb 1, 2014 at 22:20
  • @leftaroundabout: I am optimizing for speed of lookup and insertion. The symbol table will be used to insert segments of code (text). I realize that if the list is small enough, it won't matter if I use an association list or a tree. My question is basically: how big does the list have to be on average (in Haskell's implementations), for a tree implementation of said list to make an appreciable performance difference? Feb 1, 2014 at 22:52
  • 2
    @MikeMenzel You can use a list until profiling shows that a lot of time is spent in searching the list. Alternatively, you can use a proper container (such as Map) from the start, since that will most likely give better code.
    – kqr
    Feb 2, 2014 at 0:50

1 Answer 1

3

I think you should always* use a (Hash)Map for any thing more than just a quick script.

First argument, use the best datatype from a design point. Maps scale to larger sizes. Even for smaller sized associate list it wouldn't surprise me (and almost expect it) if it would be practically as fast. The reason behind this feeling comes from following 1, on using Set for nub, where they found that it was not slower even for small lists. Furthermore Maps have quite some useful functions related to them which can be used to manipulate them. For lists they don't exist, or you would have to write them yourself (and they probably would not be that fast).

Second argument, don't optimize if it isn't needed. As kqr noted in his comment on your answer, don't optimize until there is proof you need it (and that you really need to optimize this list/map) . A thing to keep in mind for this is the question how often would such a small sized dictionary happen? Would it then even contribute much time to the overall time of your program. Or is the execution then already so small that there would be no noticeable difference?

*: The one exception I can think of now is if you want to create an infinite associate list.

P.S. For a nice article on what could go wrong with lists (and company policy) see http://thedailywtf.com/Articles/Coding-Practices-MUST-Be-Followed.aspx

Not the answer you're looking for? Browse other questions tagged or ask your own question.