6 ms·

Show HN: A Fast, Malloc-Free C++14 Json Parser and Encoder

98 points by matt42 12y ago

rurban 12y ago
Sorry, didn't read the code yet. But malloc free means stack allocation, thus dangerous to stack attacks. Please clarify.
- deleted 12y ago
  [deleted]
- BinaryIdiot 12y ago
  I also haven't read the code yet but malloc free may simply mean the code doesn't call malloc but it can still allocate things on the heap using New.
  - k4st 12y ago
    This program appears to use heap allocation, at least indirectly through its use of std::string. On a more general note, libraries that perform zero dynamic allocation (and instead require the library user to pass in memory) can be very convenient for systems programming where portability is a concern. For example, I use Intel XED instruction encoder/decoder, which is a library that performs no dynamic memory allocation. This allows me to use it in user space and kernel space without hijacking the malloc symbol.
rdtsc 12y ago
> In classic C or C++, you would define a function taking optional arguments as : Is that true? Can classic C have default (optional) arguments?
- Iftheshoefits 12y ago
  No, classic C doesn't have default arguments.
  - rdtsc 12y ago
    That's what I thought.
- cremno 12y ago
  void fun(int mandatory_arg, int optional_arg1 = 1, int optional_arg2 = 12, int optional_arg3 = 12); No, this isn't legal ISO C. There are ways to simulate them though: https://gustedt.wordpress.com/2010/06/03/default-arguments-for-c99/ https://gustedt.wordpress.com/2010/06/03/default-arguments-f...
  - matt42 12y ago
    My mistake, I just fixed the readme.
haberman 12y ago
> As of today, all json parsers rely dynamic data structures to parse and store the json objects. I'm not sure that's entirely fair. Callback-based parsers like YAJL leave the application free to store the data in whatever data structure they want, or even to stream-process the input without storing in a data structure at all. But regardless, the meta-programming approach described here is interesting and novel. Generating structure-specific parsing code is a well-explored area (for example, Protocol Buffers is designed entirely around this idea), but doing it as C++ metaprogramming is a novel approach (Protocol Buffers relies on compile-time code generation). I don't actually understand how the object inspection and compile-time codegen works with this meta-programming approach; will be interesting to dig in a little deeper and learn more.
- nly 12y ago
  I've used Boost Fusion associative maps, in conjunction with a bit of glue code and an appropriate JSON or XML library, to provide pretty seemless serialisation and de-serialisation for both XML and JSON for a while. For XML it's a little tricky because you have to have a means of mapping the simple flat relationship between a struct and its fields, to the various relationships between XML elements, subelements, attributes, and CDATA etc. Here's an example of what my declarations for XML look like in some code I wrote last year. BOOST_FUSION_ADAPT_ADT ( xml_encoded<Description>, XML_ATTR (string, "summary") XML_TEXT (string) ) BOOST_FUSION_ADAPT_ADT ( xml_encoded<Event>, XML_ATTR (string, "name") XML_SUBTREE (shared_ptr<Description const>, "description") XML_ATTR (optional<unsigned>, "since") ) The #defines for each macro are short, and beyond Fusion there's only a small support header Here's a talk from CppConn describing a similar use case, but for binary data formats https://www.youtube.com/watch?v=wbZdZKpUVeg https://www.youtube.com/watch?v=wbZdZKpUVeg
- aboodman 12y ago
  Not that it's well-known or anything, but the Gin library that's part of Chromium uses C++ meta-programming to generate structure-specific code to 'parse' JavaScript types into C++ types: https://code.google.com/p/chromium/codesearch#chromium/src/gin/function_template.h https://code.google.com/p/chromium/codesearch#chromium/src/g...
twic 12y ago
> This makes its performances impossible to match in other languages such as C or Java that do not provide static introspection. A CHALLENGE! So, er, who's up for it? You could implement an analogue of this approach in Java. It's true that Java doesn't have language constructs that would let you do this as part of compilation, but Java has its ways. You could write an annotation processor to do this at compile time, or use a bytecode parser at runtime (this is yucky, but a fairly standard technique these days). Either way, the output would be a pair of synthetic classes which implemented the parser and encoder. A tool like this would be moderately laborious to write, but a straightforward matter of programming.
- madbiz 12y ago
  Interesting approach. Could be a use case for the ByteBuddy library at http://bytebuddy.net http://bytebuddy.net
- astral303 12y ago
  It reminds me of jackson-afterburner[0] in Java, which generates byte code for parsing and generating JSON. [0] https://github.com/FasterXML/jackson-module-afterburner https://github.com/FasterXML/jackson-module-afterburner
nly 12y ago
RapidJSON claims to support "in-situ parsing", which is presumably mostly zero copy, and presumably doesn't allocate much either. I'd like to see benchmarks over comparable code.
- masklinn 12y ago
  in-situ parsing would only work when decoding from an existing buffer (returning slices from the original buffer instead of copying the data), not when decoding JSON from e.g. a socket, right?
densh 12y ago
See also: Scala Pickling [1]. Serialization and deserialisation logic optimised for specific datatype is generated purely at compile time using Scala Macros [2]. [1] http://lampwww.epfl.ch/~hmiller/pickling/ http://lampwww.epfl.ch/~hmiller/pickling/ [2] http://scalamacros.org http://scalamacros.org
jlarocco 12y ago
This uses std::string all over the place, which allocates memory under the hood. I'm not sure how any JSON parser could avoid memory allocation without a difficult to use interface. Numbers, arrays, strings, and objects are unbounded by the JSON spec, so a truly malloc free library would need to provide a kind of streaming interfaces where things are returned in fixed sized chunks. JSON wouldn't be my first choice for data storage in situations where I needed to avoid dynamic memory.
- pjungwir 12y ago
  jsmn is a nice JSON tokenizer. You malloc a chunk of memory up front, but that's it. It gives you pointers to the tokens and you can do what you like with them. I am using it in an app that has a fixed-size data structure that is populated from a JSON file. So my code is malloc-free also.
  - aktau 12y ago
    Link for those interested: https://bitbucket.org/zserge/jsmn/wiki/Home https://bitbucket.org/zserge/jsmn/wiki/Home jsmn is pretty awesome, and contrary to this (std::string, std::vector) actually puts you in charge of allocations. It's also in C. In a similar vein, and also possibly already mentioned: - yayl (C): https://lloyd.github.io/yajl/ https://lloyd.github.io/yajl/ - microjson (C): http://esr.ibiblio.org/?p=6262 http://esr.ibiblio.org/?p=6262
- Iftheshoefits 12y ago
  It also uses vector, which is almost certainly using malloc and/or placement new even if the SIO somehow really does reserve space for a single object. Its also using the heap unless there is some hidden Allocator object in the code that explicitly is using stack allocated space.
- codehero 12y ago
  I wrote a JSON parser that avoids using dynamic memory but works a bit differently. It's a callback interface like SAX, but instead of pushing already "typed" data to the user, the user calls a function to interpret the data. In this fashion, if the user wants a float instead of an integer, they call the function for float. Likewise, if the user has some space allocated for string values, the library can convert the already inmemory JSON format string to UTF-8 in the user's buffer. The C interface is purposely ugly but the C++ is much easier to work with. https://codehero.github.io/benejson/ https://codehero.github.io/benejson/
huhtenberg 12y ago
On one hand this is undoubtedly a very clever use of ++ features. On the other hand that heck of a lot of scaffolding (just look in /iod directory) and the more scaffolding there is, the more caution is needed in adopting the code. The same goal - not parsing what's not needed - can be done with a conventional callback-based C code. You basically go through the json data, parse, say, a field and call the app asking "is this ok? shall I proceed?". If it's a yes, then you indeed proceed and parse out the value chunk and pass it to the app the same way. If it's a no, you either abort or skip over the value. The end effect is the same - parsing of an invalid json input is aborted as soon as the app flags the first bad entry; and unwanted fields are never parsed in full. So I seriously doubt that this is a little more than a marketing spin of a proud developer - This makes its performances impossible to match in other languages such as C or Java that do not provide static introspection. I am fairly certain that vurtun's code [1] can match and most likely beat this lib's performance, with ease. [1] https://news.ycombinator.com/item?id=8609236 https://news.ycombinator.com/item?id=8609236
- matt42 12y ago
  Vurtun's code is probabely faster than the iod json parser since it leaves the type check and conversion to the user. Since iod knows the structure of the object you are parsing, it directly checks types and throw exceptions if the json string does not contains all the required fields of the destination object, things that you cannot do without compile-time introspection, and that vurtun's library leaves to the user.
  - huhtenberg 12y ago
    No, I meant of course that vurtun + all the callbacks are going to be at least as fast as iod. You'd basically pass a bit of context to every callback, so that the app would know where exactly it is in its parsing. It's clearly a bit more of leg work in terms of coding, but I would personally take that over introducing a dependency on a larger abstract framework. I come from the embedded programming background, so I would opt for a pre-processor step that takes in a struct definition and generates a proper set of parsing callbacks. This way you'd at least see the interim code before it gets compiled. But I digress, to each his own and that's not a point here. I spent a lot of time optimizing C code and I find your blanket performance claims to be too absolute and cocky for comfort.
dvt 12y ago
If you're using C++, it's by definition malloc-free ;)
- dvt 12y ago
  Random downvote? Using malloc in C++ is considered terrible practice. Should I even source it?

98 points by matt42 12y ago

Sorry, didn't read the code yet. But malloc free means stack allocation, thus dangerous to stack attacks. Please clarify.

deleted 12y ago
[deleted]
BinaryIdiot 12y ago
I also haven't read the code yet but malloc free may simply mean the code doesn't call malloc but it can still allocate things on the heap using New.
- k4st 12y ago
  This program appears to use heap allocation, at least indirectly through its use of std::string. On a more general note, libraries that perform zero dynamic allocation (and instead require the library user to pass in memory) can be very convenient for systems programming where portability is a concern. For example, I use Intel XED instruction encoder/decoder, which is a library that performs no dynamic memory allocation. This allows me to use it in user space and kernel space without hijacking the malloc symbol.

rdtsc 12y ago

> In classic C or C++, you would define a function taking optional arguments as : Is that true? Can classic C have default (optional) arguments?

Iftheshoefits 12y ago
No, classic C doesn't have default arguments.
- rdtsc 12y ago
  That's what I thought.
cremno 12y ago
void fun(int mandatory_arg, int optional_arg1 = 1, int optional_arg2 = 12, int optional_arg3 = 12); No, this isn't legal ISO C. There are ways to simulate them though: https://gustedt.wordpress.com/2010/06/03/default-arguments-for-c99/ https://gustedt.wordpress.com/2010/06/03/default-arguments-f...
- matt42 12y ago
  My mistake, I just fixed the readme.

haberman 12y ago

> As of today, all json parsers rely dynamic data structures to parse and store the json objects. I'm not sure that's entirely fair. Callback-based parsers like YAJL leave the application free to store the data in whatever data structure they want, or even to stream-process the input without storing in a data structure at all. But regardless, the meta-programming approach described here is interesting and novel. Generating structure-specific parsing code is a well-explored area (for example, Protocol Buffers is designed entirely around this idea), but doing it as C++ metaprogramming is a novel approach (Protocol Buffers relies on compile-time code generation). I don't actually understand how the object inspection and compile-time codegen works with this meta-programming approach; will be interesting to dig in a little deeper and learn more.

nly 12y ago
I've used Boost Fusion associative maps, in conjunction with a bit of glue code and an appropriate JSON or XML library, to provide pretty seemless serialisation and de-serialisation for both XML and JSON for a while. For XML it's a little tricky because you have to have a means of mapping the simple flat relationship between a struct and its fields, to the various relationships between XML elements, subelements, attributes, and CDATA etc. Here's an example of what my declarations for XML look like in some code I wrote last year. BOOST_FUSION_ADAPT_ADT ( xml_encoded<Description>, XML_ATTR (string, "summary") XML_TEXT (string) ) BOOST_FUSION_ADAPT_ADT ( xml_encoded<Event>, XML_ATTR (string, "name") XML_SUBTREE (shared_ptr<Description const>, "description") XML_ATTR (optional<unsigned>, "since") ) The #defines for each macro are short, and beyond Fusion there's only a small support header Here's a talk from CppConn describing a similar use case, but for binary data formats https://www.youtube.com/watch?v=wbZdZKpUVeg https://www.youtube.com/watch?v=wbZdZKpUVeg
aboodman 12y ago
Not that it's well-known or anything, but the Gin library that's part of Chromium uses C++ meta-programming to generate structure-specific code to 'parse' JavaScript types into C++ types: https://code.google.com/p/chromium/codesearch#chromium/src/gin/function_template.h https://code.google.com/p/chromium/codesearch#chromium/src/g...

twic 12y ago

> This makes its performances impossible to match in other languages such as C or Java that do not provide static introspection. A CHALLENGE! So, er, who's up for it? You could implement an analogue of this approach in Java. It's true that Java doesn't have language constructs that would let you do this as part of compilation, but Java has its ways. You could write an annotation processor to do this at compile time, or use a bytecode parser at runtime (this is yucky, but a fairly standard technique these days). Either way, the output would be a pair of synthetic classes which implemented the parser and encoder. A tool like this would be moderately laborious to write, but a straightforward matter of programming.

madbiz 12y ago
Interesting approach. Could be a use case for the ByteBuddy library at http://bytebuddy.net http://bytebuddy.net
astral303 12y ago
It reminds me of jackson-afterburner[0] in Java, which generates byte code for parsing and generating JSON. [0] https://github.com/FasterXML/jackson-module-afterburner https://github.com/FasterXML/jackson-module-afterburner

nly 12y ago

RapidJSON claims to support "in-situ parsing", which is presumably mostly zero copy, and presumably doesn't allocate much either. I'd like to see benchmarks over comparable code.

masklinn 12y ago
in-situ parsing would only work when decoding from an existing buffer (returning slices from the original buffer instead of copying the data), not when decoding JSON from e.g. a socket, right?

densh 12y ago

See also: Scala Pickling [1]. Serialization and deserialisation logic optimised for specific datatype is generated purely at compile time using Scala Macros [2]. [1] http://lampwww.epfl.ch/~hmiller/pickling/ http://lampwww.epfl.ch/~hmiller/pickling/ [2] http://scalamacros.org http://scalamacros.org

jlarocco 12y ago

This uses std::string all over the place, which allocates memory under the hood. I'm not sure how any JSON parser could avoid memory allocation without a difficult to use interface. Numbers, arrays, strings, and objects are unbounded by the JSON spec, so a truly malloc free library would need to provide a kind of streaming interfaces where things are returned in fixed sized chunks. JSON wouldn't be my first choice for data storage in situations where I needed to avoid dynamic memory.

pjungwir 12y ago
jsmn is a nice JSON tokenizer. You malloc a chunk of memory up front, but that's it. It gives you pointers to the tokens and you can do what you like with them. I am using it in an app that has a fixed-size data structure that is populated from a JSON file. So my code is malloc-free also.
- aktau 12y ago
  Link for those interested: https://bitbucket.org/zserge/jsmn/wiki/Home https://bitbucket.org/zserge/jsmn/wiki/Home jsmn is pretty awesome, and contrary to this (std::string, std::vector) actually puts you in charge of allocations. It's also in C. In a similar vein, and also possibly already mentioned: - yayl (C): https://lloyd.github.io/yajl/ https://lloyd.github.io/yajl/ - microjson (C): http://esr.ibiblio.org/?p=6262 http://esr.ibiblio.org/?p=6262
Iftheshoefits 12y ago
It also uses vector, which is almost certainly using malloc and/or placement new even if the SIO somehow really does reserve space for a single object. Its also using the heap unless there is some hidden Allocator object in the code that explicitly is using stack allocated space.
codehero 12y ago
I wrote a JSON parser that avoids using dynamic memory but works a bit differently. It's a callback interface like SAX, but instead of pushing already "typed" data to the user, the user calls a function to interpret the data. In this fashion, if the user wants a float instead of an integer, they call the function for float. Likewise, if the user has some space allocated for string values, the library can convert the already inmemory JSON format string to UTF-8 in the user's buffer. The C interface is purposely ugly but the C++ is much easier to work with. https://codehero.github.io/benejson/ https://codehero.github.io/benejson/

huhtenberg 12y ago

On one hand this is undoubtedly a very clever use of ++ features. On the other hand that heck of a lot of scaffolding (just look in /iod directory) and the more scaffolding there is, the more caution is needed in adopting the code. The same goal - not parsing what's not needed - can be done with a conventional callback-based C code. You basically go through the json data, parse, say, a field and call the app asking "is this ok? shall I proceed?". If it's a yes, then you indeed proceed and parse out the value chunk and pass it to the app the same way. If it's a no, you either abort or skip over the value. The end effect is the same - parsing of an invalid json input is aborted as soon as the app flags the first bad entry; and unwanted fields are never parsed in full. So I seriously doubt that this is a little more than a marketing spin of a proud developer - This makes its performances impossible to match in other languages such as C or Java that do not provide static introspection. I am fairly certain that vurtun's code [1] can match and most likely beat this lib's performance, with ease. [1] https://news.ycombinator.com/item?id=8609236 https://news.ycombinator.com/item?id=8609236

matt42 12y ago
Vurtun's code is probabely faster than the iod json parser since it leaves the type check and conversion to the user. Since iod knows the structure of the object you are parsing, it directly checks types and throw exceptions if the json string does not contains all the required fields of the destination object, things that you cannot do without compile-time introspection, and that vurtun's library leaves to the user.
- huhtenberg 12y ago
  No, I meant of course that vurtun + all the callbacks are going to be at least as fast as iod. You'd basically pass a bit of context to every callback, so that the app would know where exactly it is in its parsing. It's clearly a bit more of leg work in terms of coding, but I would personally take that over introducing a dependency on a larger abstract framework. I come from the embedded programming background, so I would opt for a pre-processor step that takes in a struct definition and generates a proper set of parsing callbacks. This way you'd at least see the interim code before it gets compiled. But I digress, to each his own and that's not a point here. I spent a lot of time optimizing C code and I find your blanket performance claims to be too absolute and cocky for comfort.

dvt 12y ago

If you're using C++, it's by definition malloc-free ;)

dvt 12y ago
Random downvote? Using malloc in C++ is considered terrible practice. Should I even source it?