Avoiding Pain With Persistent Data Structures

Bob Ippolito, Nom Labs

Stevenson Hall 1300
12:00 PM - 12:50 PM

The work we do with data structures has gotten a lot more sophisticated in recent years due to the rise of multicore devices, distributed applications, and the expectation that updates should be transactional and/or reversible. Many of the mutable data structures in common use do not adapt well to these constraints without excessive locking, copying, or other forms of bookkeeping. Persistent (effectively immutable) variants of data structures can often be used to simplify these classes of problems. While many of these data structures are already commonplace in functional programming languages such as Haskell, Scala or Erlang, they can be adapted for use in any garbage-collected language such as Java, Python or JavaScript. I will discuss the implementation and usage of several persistent data structures and compare them with their mutable counterparts.