Wednesday 21 November 2018

Rethinking Shareable Data Structures

I have been recently developing a set of data structures following on from Okasaki's Purely Functional Data Structures. There is a lot to be gained by using immutable data structures, that is, where all the fields are public readonly in C# or public final in Java. Strings in C# and Java already have this property and it turns out to be remarkably easy to develop all the usual data structure types with this property. Something of the kind had already started to happen in Pyrrho: many of Pyrrho's data structures are immutable, and Pyrrho uses Bookmarks instead of Iterators. Specifically, the benefits (as with strings) are
  •  a snapshot is obtained by a simple assignment, so rollback is a breeze
  •  structures can be modified while a traversal continues with the previous state#
  •  they are thread-safe and safe to pass as a parameter in C# or Java, so that
  •  these data structures never need to be locked
The price to be paid is extra work for the garbage collector: this is a reasonable trade-off.
So the time seemed ripe for a serious approach to #ShareableDataStructures and the fruits of these labours are emerging at . Eventually the classes will be rich enough to implement a DBMS, and the plan is to implement everything in C# and Java, and then Python later. Efforts in the DBMS direction are currently called #StrongDBMS . A lot will depend on the performance of the TPCC benchmark.
It is natural to ask what this might mean for Pyrrho. It does seem like a natural evolution (Pyrrho 7.0 maybe), but some of the Pyrrho code would be a real nuisance to transform. Time will tell.

No comments:

Post a Comment