Personal tools

HaskellImplementorsWorkshop/2011/Tibell

From HaskellWiki

< HaskellImplementorsWorkshop | 2011(Difference between revisions)
Jump to: navigation, search
(Faster persistent data structures through hashing)
(Added Category:Community)
 
Line 6: Line 6:
   
 
In this talk I will describe a new map data type that uses a recently developed data structure, a hash array mapped trie, to achieve better real world performance. I will describe the design and implementation of this new data structure, improvements made to GHC to improve its performance, benchmark results, and finally conclude with a discussion on compiler improvements that could further improve the performance of this data type.
 
In this talk I will describe a new map data type that uses a recently developed data structure, a hash array mapped trie, to achieve better real world performance. I will describe the design and implementation of this new data structure, improvements made to GHC to improve its performance, benchmark results, and finally conclude with a discussion on compiler improvements that could further improve the performance of this data type.
  +
  +
  +
[[Category:Community]]

Latest revision as of 13:45, 17 December 2012

[edit] Faster persistent data structures through hashing

Johan Tibell

The most commonly used map (dictionary) data types in Haskell are implemented using some kind of binary tree, typically a size balanced tree or a Patricia tree. While binary trees provide good asymptotic performance, their real world performance is not stellar, especially when used with keys which are expensive to compare, such as strings.

In this talk I will describe a new map data type that uses a recently developed data structure, a hash array mapped trie, to achieve better real world performance. I will describe the design and implementation of this new data structure, improvements made to GHC to improve its performance, benchmark results, and finally conclude with a discussion on compiler improvements that could further improve the performance of this data type.