Galois is pleased to host the following tech talk. These talks are open to the interested public. Please join us!
title: Faster Persistent Data Structures Through Hashing
presenter: Johan Tibell
time: Tuesday, 15 February 2011, 10:30am
location:
Galois Inc.421 SW 6th Ave. Suite 300, Portland, OR, USA(3rd floor of the Commonwealth building)
abstract:
The most commonly used map (dictionary) data type in Haskell is implemented using a size balanced tree. While size balanced 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 we will look at two different map implementations that use hashing to achieve better real world performance. The implementations have different performance characteristics: one provides very fast look-ups while the other trades better insert performance for somewhat slower look-ups. I will describe the design of these data structures and show some early benchmark results.
bio:
Johan Tibell is a Software Engineer at Google Inc. He received a M.S. in Software Engineering from Chalmers University of Technology, Sweden, in 2007.