| 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
And the benchmarks from the paper are here:
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/m...
[2] https://github.com/iu-parfunc/tree-velocity-benchdata/blob/m... |