Galois Tech Talks

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.

# vimeo.com/20655874 Uploaded 1,266 Plays / / 0 Comments Watch in Couch Mode

Follow

Galois Tech Talks

Galois Video Plus

This channel contains video from the tech talks presented by galois.com

Galois has been holding weekly technical seminars since 2006 on topics from functional programming, formal methods, compiler and language design, to cryptography, and operating system construction, with talks by many figures from the programming language and formal methods communities. The talks are open and free.

Each week new tech talks


+ More

This channel contains video from the tech talks presented by galois.com

Galois has been holding weekly technical seminars since 2006 on topics from functional programming, formal methods, compiler and language design, to cryptography, and operating system construction, with talks by many figures from the programming language and formal methods communities. The talks are open and free.

Each week new tech talks are published at galois.com/blog/category/techtalks/ and you can find out about upcoming talks on twitter.com/galoisinc

Browse This Channel

Shout Box

Channels are a simple, beautiful way to showcase and watch videos. Browse more Channels. Channels