3 ms·

TL;DR: They created a functional programming language which uses an in-memory representation of data structures that avoids pointers, instead organizing object

TL;DR: They created a functional programming language which uses an in-memory representation of data structures that avoids pointers, instead organizing object trees in preorder, much like most serialization formats would use. To support access patterns that aren't strictly preorder, the compiler (optionally?) injects offsets into the structure, to allow "skipping over" branches to get to the one you want. Apparently, any value can optionally be a pointer, in order to allow for aliasing. But this is the exception rather than the norm. Aliasing is of course critical to allow data structures to be updated -- in the FP copy-on-write sense, where you clone and update all objects on the path from the root to the modified one. This seems to be a nice fit for functional programming and is pretty cool in that context. I suspect it would be a lot more difficult to take this approach in an imperative model. Amusingly, in a way this is the opposite of what Cap'n Proto does (disclosure: I'm the author of Cap'n proto). LoCal is a programming language whose in-memory representation looks like a serialization format (preorder; no pointers). Cap'n Proto is a serialization format which looks like an in-memory representation (arbitrary order; using pointers). They have a table of benchmarks showing LoCal being faster than Cap'n Proto. It would be nice to see code for these benchmarks. It sounds like the test case is a binary tree. This is an almost pathologically pointer-heavy use case, and as a result would tend to show LoCal in the best possible light and Cap'n Proto in the worst. Cap'n Proto will spend 8 bytes on every pointer; LoCal will spend zero. I take issue with the "treeInsert" benchmark, in which the paper claims Cap'n Proto is O(n) whereas LoCal is O(log(N)). It sounds like for some reason the authors decided they needed to copy the entire Cap'n Proto message before they could mutate it. Cap'n Proto supports in-place mutation, so should be O(log(N)) reads and O(1) writes (compared to O(log(n)) reads and writes for LoCal). (Admittedly in-place modification of files loaded from disk is tricky to set up at present, but this is an implementation limitation, not a theoretical one -- and it's not clear to me that this test was loading files from disk anyhow.) Maybe they decided that a complete copy was needed in order to get FP copy-on-write semantics, but that's not really true either. In principle, it would be possible to create a Cap'n Proto implementation that can start from a file on disk and modify it in an object-by-object copy-on-write way, appending new/modified objects to the end of the file in order to avoid destroying any information. At present this hasn't been implemented, but that's largely because no one has had a pressing need for it, to my knowledge.

rrnewton 7y ago
Hi Kenton, TL;DR: we'd love to get some pointers on our Cap'n Proto usage -- let's set up a call between all us authors and you. > difficult to take this approach in an imperative model. Indeed, we are eventually adding mutation of fixed sized fields, but mutating the structure of the tree is really problematic with these kinds of encodings. But one silver lining of this functional approach is that for some tree traversals the out-of-place copying Gibbon version touches less total memory than the idiomatic C version that updates the tree in place in-place. > LoCal is a programming language whose in-memory representation looks like a serialization format (preorder; no pointers). Cap'n Proto is a serialization format which looks like an in-memory representation (arbitrary order; using pointers). Yes, well put! We're big fans of Cap'n Proto. The comparison in our evaluation is not apples-to-apples, because Gibbon and Cap'n Proto serve very different purposes. We used Cap'n Proto here mainly because of a paucity of anything close to Gibbon in this space. While there's a bit of discussion of differences in 7.2, I think my student, Michael Vollmer, emphasized this a bit better in the talk (which should be posted online at some point). > They have a table of benchmarks showing LoCal being faster than Cap'n Proto. It would be nice to see code for these benchmarks. It sounds like the test case is a binary tree. Yes: several operations on binary trees, plus the benchmarks reading tweets and large ASTs from disk. The compiler is here: https://github.com/iu-parfunc/gibbon https://github.com/iu-parfunc/gibbon And the benchmarks from the paper are here: https://github.com/iu-parfunc/tree-velocity-benchdata https://github.com/iu-parfunc/tree-velocity-benchdata (The ACM digital library entry for the paper is supposed to link the artifact, but it seems its not posted yet.) > "treeInsert" .. Cap'n Proto supports in-place mutation, so should be O(log(N)) reads and O(1) writes (compared to O(log(n)) reads and writes for LoCal). The "insertDestr" variant is the in-place tree-insert with Cap'n Proto (1.72μs). The code is here [1] and capnp data definition here [2]. Maybe it could be further improved. > In principle, it would be possible to create a Cap'n Proto implementation that can start from a file on disk and modify it in an object-by-object copy-on-write way, appending new/modified objects to the end Yes, that would work the same as the Gibbon version, tacking on a new chunk of `log(N)` bytes on each insert. I submit that no one has needed this in Cap'n Proto because they have not used it as the in-memory representation for all values in a functional-language compiler ;-). [1] https://github.com/iu-parfunc/tree-velocity-benchdata/blob/master/pldi19/litmus_tests/capnproto/test_litmus_insert_destructive/main.cpp https://github.com/iu-parfunc/tree-velocity-benchdata/blob/m... [2] https://github.com/iu-parfunc/tree-velocity-benchdata/blob/master/pldi19/litmus_tests/capnproto/test_litmus_insert_destructive/tree.capnp https://github.com/iu-parfunc/tree-velocity-benchdata/blob/m...

rrnewton 7y ago

Hi Kenton, TL;DR: we'd love to get some pointers on our Cap'n Proto usage -- let's set up a call between all us authors and you. > difficult to take this approach in an imperative model. Indeed, we are eventually adding mutation of fixed sized fields, but mutating the structure of the tree is really problematic with these kinds of encodings. But one silver lining of this functional approach is that for some tree traversals the out-of-place copying Gibbon version touches less total memory than the idiomatic C version that updates the tree in place in-place. > LoCal is a programming language whose in-memory representation looks like a serialization format (preorder; no pointers). Cap'n Proto is a serialization format which looks like an in-memory representation (arbitrary order; using pointers). Yes, well put! We're big fans of Cap'n Proto. The comparison in our evaluation is not apples-to-apples, because Gibbon and Cap'n Proto serve very different purposes. We used Cap'n Proto here mainly because of a paucity of anything close to Gibbon in this space. While there's a bit of discussion of differences in 7.2, I think my student, Michael Vollmer, emphasized this a bit better in the talk (which should be posted online at some point). > They have a table of benchmarks showing LoCal being faster than Cap'n Proto. It would be nice to see code for these benchmarks. It sounds like the test case is a binary tree. Yes: several operations on binary trees, plus the benchmarks reading tweets and large ASTs from disk. The compiler is here: https://github.com/iu-parfunc/gibbon https://github.com/iu-parfunc/gibbon And the benchmarks from the paper are here: https://github.com/iu-parfunc/tree-velocity-benchdata https://github.com/iu-parfunc/tree-velocity-benchdata (The ACM digital library entry for the paper is supposed to link the artifact, but it seems its not posted yet.) > "treeInsert" .. Cap'n Proto supports in-place mutation, so should be O(log(N)) reads and O(1) writes (compared to O(log(n)) reads and writes for LoCal). The "insertDestr" variant is the in-place tree-insert with Cap'n Proto (1.72μs). The code is here [1] and capnp data definition here [2]. Maybe it could be further improved. > In principle, it would be possible to create a Cap'n Proto implementation that can start from a file on disk and modify it in an object-by-object copy-on-write way, appending new/modified objects to the end Yes, that would work the same as the Gibbon version, tacking on a new chunk of `log(N)` bytes on each insert. I submit that no one has needed this in Cap'n Proto because they have not used it as the in-memory representation for all values in a functional-language compiler ;-). [1] https://github.com/iu-parfunc/tree-velocity-benchdata/blob/master/pldi19/litmus_tests/capnproto/test_litmus_insert_destructive/main.cpp https://github.com/iu-parfunc/tree-velocity-benchdata/blob/m... [2] https://github.com/iu-parfunc/tree-velocity-benchdata/blob/master/pldi19/litmus_tests/capnproto/test_litmus_insert_destructive/tree.capnp https://github.com/iu-parfunc/tree-velocity-benchdata/blob/m...