Upload

Loading...

Faster persistent data structures through hashing - Johan Tibell

1,522

Loading...

Loading...

Transcript

The interactive transcript could not be loaded.

Loading...

Loading...

Rating is available when the video has been rented.
This feature is not available right now. Please try again later.
Uploaded on Nov 1, 2011

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.

From the Haskell Implementors Workshop 2011: http://www.haskell.org/haskellwiki/Ha...

Loading...

Autoplay When autoplay is enabled, a suggested video will automatically play next.

Up Next


to add this to Watch Later

Add to