6 ms·

LoCal: A Language for Programs Operating on Serialized Data

89 points by matt_d 7y ago

_pmf_ 7y ago
Every serializer/deserializer for nested, dynamically sized blocks of binary data contains a buggy, ad hoc variant of this. I'd already be happy with something like Erlang's standard binary matching library[0] as part of each language's stdlib. Block deduplication, block reference counting (and the requirement to in-file-GC unused blocks), n:m references are things that arise in some formats that don't seem to be part of this language? [0] http://erlang.org/doc/efficiency_guide/binaryhandling.html http://erlang.org/doc/efficiency_guide/binaryhandling.html
perfunctory 7y ago
Definitely going to dive into this. Majority of enterprise software is processing serialized data - send data from the browser to the middleware, mung it, send it to the database, and then all the way back in reverse order. And we don't have good tool support for this.
- pavlov 7y ago
  Is LoCal going to help with this? The abstract suggests that they've figured out a unified representation for in-memory and disk/wire layout. That's an interesting performance feature for new applications, but doesn't seem to do anything to help existing serialization wranglers since you can't make the old formats go away.
  - rrnewton 7y ago
    Absolutely true. It's future work to train our Gibbon/LoCal compiler to generate code operating over more interesting, existing binary formats (CBOR, Avro, CapNP...), some of which are a better fit than others. Or for text formats we could focus on writing high-performance parsers and fusing them with recursive functions that consume the result. Lots more to do here.
    - sitkack 7y ago
      Could you differentiate LoCal programs and generate succinct data structures? Apply transforms to make the code incremental? Sounds like magic, so I make requests for more magic.
misterman0 7y ago
This is interesting. Without fully understanding the design of this system, I wonder how far it scales. Can you process big data with LoCal?
- jacobush 7y ago
  Is it web scale? :-) Sorry couldn’t resist... https://m.youtube.com/watch?v=b2F-DItXtZs https://m.youtube.com/watch?v=b2F-DItXtZs
  - misterman0 7y ago
    I actually thought that by now, in 2019, this forum would have realized that big data is real. It's a thing. Some of us are forced to deal with it. It's a hard problem that is well-suited for having discussions around on forums that are populated by intelligent people, but apparently it's not a suitable topic on this particular forum. I will certainly keep that in mind from hereon out.
    - tempguy9999 7y ago
      Big data is mainly a marketing term to me. I've been involved in a Big Data project that wasn't because someone wanted to massage their CV with fancy tech. With current multicore machines and SSDs or cheap spinny disks you can hold and process incredible amounts of data. So, serious question, how do you define big data? By some size threshold, or "it can't possibly be done on a single box", or something else? And If I may, what is the BD work that you do (feel free to decline that one). TIA
    - kjs3 7y ago
      I actually thought that by now, in 2019, that people doing big data work understood that big data covered a vast number of processing use cases and saying "can it process big data" has about as much semantic meaning as "can it process blue". I will certainly keep that in mind from hereon out.
- rrnewton 7y ago
  Well, if you have a big document collection or something, the faster you can process each individual document the more you can scale, right? I guess I'm not sure what scalability would mean here other than speeding up that individual, sequential processing job on one node (e.g. the map step in a MapReduce).
the_duke 7y ago
So after skimming the paper, this seems like a formalization of something like Protobuf/CaptnProto with native language support. Interesting, but not necessarily very practical.
- firethief 7y ago
  Capn proto is like a RAM format that can be directly serialized. This is a serialization format that can be directly worked with. They both allow skipping deserialization, but that's not the main draw of this approach. The ability to design data representation around expected access patterns can make traversal faster and data more compact even if you don't plan to ever "serialize" it.
- aidenn0 7y ago
  You may want to read this comment: https://news.ycombinator.com/item?id=20266970 https://news.ycombinator.com/item?id=20266970
- rrnewton 7y ago
  Our main focus of the Gibbon project is to make tree traversals very fast, and only secondarily to work with serialized data. CapnProto is a wonderful library interface for dealing with serialized data, but I think the usual library-vs-compiler distinction applies. A library operates at the level of individual data access methods, but it doesn't try to change the control flow of the code calling those methods. That's our goal with this project. We sometimes turn the code a bit inside out in order to make it better operate on serialized data. (For instance, switching a postorder traversal to a preorder one.)
enriquto 7y ago
In a few years, young people will rediscover unix and we will have gone full circle.
firethief 7y ago
I can't believe this. I had the same idea and I've been working on a demo. The abstract and introduction of this paper could be describing my project, verbatim. Well, there's nothing more powerful than an idea whose time has come. This is going to shake up anything that operates on hierarchical data in passes, because traditional structure layouts have everyone doing a lot of pointer chasing. That approach got old when CPUs got fast.
- firethief 7y ago
  Now that I've read the full paper: they've have taken all the research novelty out of my sails. I'm amazed how parallel our designs are. I guess once you've gone down the rabbit hole of committing to operating on a dense serialized format, things like decoupling application data types from concrete representations suggest themselves. I'd be sunk if I were doing this for Science. But I'm doing this for Engineering, and I like my implementation choices. I have achieved some properties that I think are important for practical integration with other code. The working name of my project is Re, because the core data structure is reified traversals and operating on them involves reifying some other things that aren't normally reified. Edit to add: my elevator pitch (needs condensing, I haven't pitched it to anyone but my mom): It used to be common practice to use tree structures to represent linear data. As CPUs have become faster than RAM the pointer-heaviness of this approach has made the constant factors awful, and it's now avoided when possible. It's now actually efficient to do the opposite and represent trees as linear data when you can. This can be done explicitly, e.g. in the WASM format, but such structures can't be operated on directly unless it's done "in the raw", outside the type system and other facilities of the language. What's missing is a generic abstraction layer that maps between operations on conceptual application objects and linearized trees. I've found that once you have that, you can also do things with linearized data that would be impractical with trees. (Actually, it happened the other way around. Some time ago I prototyped a regex-like engine for finding and replacing fragments of ASTs [https://blog.lambdaverse.org/comacro/ https://blog.lambdaverse.org/comacro/], and I discovered operating directly on serialized representation enabled that. I haven't had a chance to make a production implementation yet. Then recently I was working on tree-structured template inference to turn collections of webpages back into the databases that generated them with minimal interaction, and I realized... the comacro construction is a perfect fit here. So it became an excuse to develop that idea ostensibly as part of a project I could actually make money with.)
kentonv 7y ago
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.
- 7y ago
rrnewton 7y ago
One thing that might not be clear from the paper: while the Gibbon compiler currently handles a small subset of Haskell, we plan to deploy it by integrating with GHC. That is, we want to make it possible to compile a subset of your Haskell program through Gibbon, while seamlessly calling that accelerated code from regular Haskell code utilizing the full library ecosystem.

89 points by matt_d 7y ago

Every serializer/deserializer for nested, dynamically sized blocks of binary data contains a buggy, ad hoc variant of this. I'd already be happy with something like Erlang's standard binary matching library[0] as part of each language's stdlib. Block deduplication, block reference counting (and the requirement to in-file-GC unused blocks), n:m references are things that arise in some formats that don't seem to be part of this language? [0] http://erlang.org/doc/efficiency_guide/binaryhandling.html http://erlang.org/doc/efficiency_guide/binaryhandling.html

perfunctory 7y ago

Definitely going to dive into this. Majority of enterprise software is processing serialized data - send data from the browser to the middleware, mung it, send it to the database, and then all the way back in reverse order. And we don't have good tool support for this.

pavlov 7y ago
Is LoCal going to help with this? The abstract suggests that they've figured out a unified representation for in-memory and disk/wire layout. That's an interesting performance feature for new applications, but doesn't seem to do anything to help existing serialization wranglers since you can't make the old formats go away.
- rrnewton 7y ago
  Absolutely true. It's future work to train our Gibbon/LoCal compiler to generate code operating over more interesting, existing binary formats (CBOR, Avro, CapNP...), some of which are a better fit than others. Or for text formats we could focus on writing high-performance parsers and fusing them with recursive functions that consume the result. Lots more to do here.
  - sitkack 7y ago
    Could you differentiate LoCal programs and generate succinct data structures? Apply transforms to make the code incremental? Sounds like magic, so I make requests for more magic.

misterman0 7y ago

This is interesting. Without fully understanding the design of this system, I wonder how far it scales. Can you process big data with LoCal?

jacobush 7y ago
Is it web scale? :-) Sorry couldn’t resist... https://m.youtube.com/watch?v=b2F-DItXtZs https://m.youtube.com/watch?v=b2F-DItXtZs
- misterman0 7y ago
  I actually thought that by now, in 2019, this forum would have realized that big data is real. It's a thing. Some of us are forced to deal with it. It's a hard problem that is well-suited for having discussions around on forums that are populated by intelligent people, but apparently it's not a suitable topic on this particular forum. I will certainly keep that in mind from hereon out.
  - tempguy9999 7y ago
    Big data is mainly a marketing term to me. I've been involved in a Big Data project that wasn't because someone wanted to massage their CV with fancy tech. With current multicore machines and SSDs or cheap spinny disks you can hold and process incredible amounts of data. So, serious question, how do you define big data? By some size threshold, or "it can't possibly be done on a single box", or something else? And If I may, what is the BD work that you do (feel free to decline that one). TIA
  - kjs3 7y ago
    I actually thought that by now, in 2019, that people doing big data work understood that big data covered a vast number of processing use cases and saying "can it process big data" has about as much semantic meaning as "can it process blue". I will certainly keep that in mind from hereon out.
rrnewton 7y ago
Well, if you have a big document collection or something, the faster you can process each individual document the more you can scale, right? I guess I'm not sure what scalability would mean here other than speeding up that individual, sequential processing job on one node (e.g. the map step in a MapReduce).

the_duke 7y ago

So after skimming the paper, this seems like a formalization of something like Protobuf/CaptnProto with native language support. Interesting, but not necessarily very practical.

firethief 7y ago
Capn proto is like a RAM format that can be directly serialized. This is a serialization format that can be directly worked with. They both allow skipping deserialization, but that's not the main draw of this approach. The ability to design data representation around expected access patterns can make traversal faster and data more compact even if you don't plan to ever "serialize" it.
aidenn0 7y ago
You may want to read this comment: https://news.ycombinator.com/item?id=20266970 https://news.ycombinator.com/item?id=20266970
rrnewton 7y ago
Our main focus of the Gibbon project is to make tree traversals very fast, and only secondarily to work with serialized data. CapnProto is a wonderful library interface for dealing with serialized data, but I think the usual library-vs-compiler distinction applies. A library operates at the level of individual data access methods, but it doesn't try to change the control flow of the code calling those methods. That's our goal with this project. We sometimes turn the code a bit inside out in order to make it better operate on serialized data. (For instance, switching a postorder traversal to a preorder one.)

enriquto 7y ago

In a few years, young people will rediscover unix and we will have gone full circle.

firethief 7y ago

I can't believe this. I had the same idea and I've been working on a demo. The abstract and introduction of this paper could be describing my project, verbatim. Well, there's nothing more powerful than an idea whose time has come. This is going to shake up anything that operates on hierarchical data in passes, because traditional structure layouts have everyone doing a lot of pointer chasing. That approach got old when CPUs got fast.

firethief 7y ago
Now that I've read the full paper: they've have taken all the research novelty out of my sails. I'm amazed how parallel our designs are. I guess once you've gone down the rabbit hole of committing to operating on a dense serialized format, things like decoupling application data types from concrete representations suggest themselves. I'd be sunk if I were doing this for Science. But I'm doing this for Engineering, and I like my implementation choices. I have achieved some properties that I think are important for practical integration with other code. The working name of my project is Re, because the core data structure is reified traversals and operating on them involves reifying some other things that aren't normally reified. Edit to add: my elevator pitch (needs condensing, I haven't pitched it to anyone but my mom): It used to be common practice to use tree structures to represent linear data. As CPUs have become faster than RAM the pointer-heaviness of this approach has made the constant factors awful, and it's now avoided when possible. It's now actually efficient to do the opposite and represent trees as linear data when you can. This can be done explicitly, e.g. in the WASM format, but such structures can't be operated on directly unless it's done "in the raw", outside the type system and other facilities of the language. What's missing is a generic abstraction layer that maps between operations on conceptual application objects and linearized trees. I've found that once you have that, you can also do things with linearized data that would be impractical with trees. (Actually, it happened the other way around. Some time ago I prototyped a regex-like engine for finding and replacing fragments of ASTs [https://blog.lambdaverse.org/comacro/ https://blog.lambdaverse.org/comacro/], and I discovered operating directly on serialized representation enabled that. I haven't had a chance to make a production implementation yet. Then recently I was working on tree-structured template inference to turn collections of webpages back into the databases that generated them with minimal interaction, and I realized... the comacro construction is a perfect fit here. So it became an excuse to develop that idea ostensibly as part of a project I could actually make money with.)

kentonv 7y ago

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.

7y ago

rrnewton 7y ago

One thing that might not be clear from the paper: while the Gibbon compiler currently handles a small subset of Haskell, we plan to deploy it by integrating with GHC. That is, we want to make it possible to compile a subset of your Haskell program through Gibbon, while seamlessly calling that accelerated code from regular Haskell code utilizing the full library ecosystem.