Juan Pedro Bolivar Puente explains immutable and persistent data structures in C++ using the Immer library and relaxed radix balanced trees.
Presentation Slides, PDFs, Source Code and other presenter materials are available at: github.com/CppCon/CppCon2017
—
The C++ elites have been talking for years about value semantics, immutability, and sharing by communicating. A better world without mutexes, races, observers, command patterns and so more lies ahead! When it comes to doing it in practice, it is not so easy. One of the main problem lies in our data structures...
Immutable data structures don't change their values. They are manipulated by producing new values. The old values remain there, and can be read safely from multiple threads without locks. They provide structural sharing, because new and old values can share common data — they are fast to compare and can keep a compact undo-history. As such, they are great for concurrent and interactive systems: they simplify the architecture of desktop software and allow servers to scale better. They are the secret sauce behind the success of Clojure and Scala, and even the JavaScript crowd is loving it via Facebook's Immutable.js.
We are presenting Immer, a C++ library implementing modern and efficient data immutable data structures.
In this session, we will talk about the architectural benefits of immutability and show how a very efficient yet powerful persistent vector type can be built using state of the art structures (Relaxed Radix Balanced Trees). We will also show an example application (a text-editor) built using the architectural style here proposed. Not only is its code extremely simple, it outperforms most similar programs. Don't believe it? Come and see!
Immer: immutable data structures | sinusoid.es/immer
Ewig: a text editor with an immutable data model | github.com/arximboldi/ewig
—
Juan Pedro Bolivar Puente: Sinusoidal engineering, Independent consultant
Juanpe is a Berlin based freelance software engineer, with a focus on interactive software, modern C++, functional programming and open source strategy. Before he worked for Ableton and he has been involved in various music technology projects. He has also developed for the GNU project and cofounded a Hacklab in Granada.
—
Videos Filmed & Edited by Bash Films: BashFilms.com
Work at Hudson River Trading (HRT): tinyurl.com/safxfctf
---
Videos Filmed & Edited by Bash Films: BashFilms.com
Why it's here
6 people recommend this
What people say. Recommended for its clear explanation of relaxed radix balanced trees and how value-oriented design simplifies concurrent programming and undo-redo systems.
o
u/oilshellin r/ProgrammingLanguages • Recommends
Immer: Clojure-like persistent data structures in C++
I stumbled across this CppCon talk and found it interesting. The Ewig text editor example with concurrent loading and editing is impressive. The code seems clean.
There is a lucid exposition of Relaxed Radix Balanced Trees (RRB trees) in the video.
Although I lost the plot with C++ around C++ 11, it is impressive how the language has fully delegated its data structures to library code.
https://github.com/arximboldi/immer
https://public.sinusoid.es/misc/immer/immer-icfp17.pdf
link to this video
On “Ask HN: What are the best advanced computer science courses online?”
Hey. Check out Juan Pedro Bolivar Puente's talks om value oriented design. He worked on Ableton which is a large application. He specifically speaks to Undo. He describes a much better pattern than the Command Pattern. He also released his source for Value Oriented Data structures Juan Pedro is a next level programmer who I think has pushed the craft forward through his work on bringing Value Oriented Design into the C++ world. Talk I link to this video Talk II link Data Structures: link Application Structure: link Text Editor: link Good luck.
In case anyone hasn't seen it this CppCon talk link to this video talks about rrb-trees and how they're a great data structure for writing a text editor that can handle unlimited sized documents without locking up, and allows for editing while saving and opening, and an easy way to support an undo command. Most text editors today do not support such functionality. With lockless data structures like an rrb-tree it becomes easy. It really is an ideal way to do write a text editor.
On “You're doing it wrong: B-heap 10x faster than binary heap (2010)”
Not a benchmark but rrb-trees are pretty neat. They give an effective O(1) for all operations. Modern languages like Scala's Vector type is an rrb-tree under the hood: link For more fun: link to this video
On “Alex: ML-enhanced range index, similar in functionality to a B+ Tree”
Mmm tasty. If anyone wants a backstory building up to this data structure checkout this talk: link to this video He builds an rrb-tree which uses the same underlying concepts ALEX uses, just without the ML-enhancement.
You might be interested in ewig and immer by Juan Pedro Bolivar Puente: linklink See the author instantly opening a ~1GB text file with async loading, paging through, copying/pasting, and undoing/redoing in their prototype “ewig” text editor about 27 minutes into their talk here: link to this video It’s backed by a “vector of vectors” data structure called a relaxed radix balanced tree: link That original paper has seen lots of attention and attempts at performance improvements, such as: linklink
On “Type Theory and Functional Programming (1999) [pdf]”
…by introducing more language concepts like ownership, borrowing, and lifetimes, to formalize, who has access when and how. It also creates things as immutable by default, unless you make use of `mut`. Unfortunately, Rust's philosophy is shared memory and making shared memory access safe, rather than message passing, which is at odds with FP. 1: link to this video…
On “Ask HN: How much time do you spend on “marketing” your open source projects?”
My most popular open-source project 1 I talk about at conferences, mostly C++ ones (last example 2). I was lucky to also land a paper about it at ICFP'17 3. On Friday I will talk at the MeetingCpp conference in Berlin about a new library I am building (kind of experimental Redux for C++ with time-travelling debugger!). I work as a freelancer and at the moment I do client work 3 days a week and dedicate the rest of the time to the open-source work. The open-source work includes doing research and implementing these tools, but also preparing the talks, which is a very time consuming task for me. Doing conference talks is very emotionally exhausting, I dread the previous weeks to the talk…
Interesting to hear about C++ in this context, since of my goals is to make C++ more like Clojure: link to this videolink There is a lot of I could say about the relationship between C++ and Clojure, but I'll leave it at that for now :-)
On “Why Are So Many Developers Hating on Object-Oriented Programming?”
…was introduced to optimize processing large sets of data, by streaming it. MapReduce does not. For a more heavy example, a few data structures that are quite powerful come from the FP world. For example, this cppcon talk is introduces one, which gives near O(1) time for all uses (insert, delete, lookup, ...), and can be used in a thread safe way: link to this video…
On “Show HN: Array with Constant Time Access and Fast Insertion and Deletion”
Interesting. I wonder how similar a Judy array is to an rrb-tree (relaxed radix binary tree), or if they're the same thing. An rrb-tree is an effective O(1) time for every category. Scala's Vector type implements one. If interested about the data structure: link to this video Scala bigO doc: link Scala's doc on it: link
For another approach: I built a didactic text editor to teach "value oriented design" and immutable data-structures in C++: link It's design is covered in these talks: - Postmodern immutable data structures: link to this video - The most valuable values: link
Not to disagree, but to be fair modern fp runtimes use data structures that wouldn't have to copy so many bytes as the whole state. A nice showcase of this idea is in Juan Pedro Bolivar Puente's CppCon '17 talk Postmodern Immutable Data Structures: link to this video
