News for hackers. Stuff that matters.
Re:Bad JSON Parsers by marcosdumay on Friday November 08, 2019 @12:02PM (#21484171)
You'll need a stack anyway, because the structure is logically a tree. Better to use the call stack, that is already there and heavily optimized.
Re:Bad JSON Parsers by Spivak on Friday November 08, 2019 @12:14PM (#21484304)
Naive person here. Isn’t the call stack a lot heavier than pushing data structures on a std::stack?
Re:Bad JSON Parsers by MaulingMonkey on Friday November 08, 2019 @01:44PM (#21485370)
A recursive parsing call stack has the overhead of pushing/popping return addresses and maybe a couple other registers. Maybe a bit more if there are security protections like stack cookies that didn't get optimized away, or if shadow stacks are enabled. It's not free, but is pretty cheap. A non-recursive use of std::stack dodges some of that, but instead has the overhead of dynamic allocation, which I'm generally going to consider more expensive - but does have the advantage of being more of a once-off cost - so perhaps it'd be cheaper for long but shallow JSON objects? The cost of the call stack vs std::stack is probably dwarfed by the cost of allocating arrays/objects/strings and decoding in either case.

If you want to over-optimize for that specific case anyways, you can take a hybrid approach with smaller stacks kept on the stack in a single linear root blob, with larger stacks falling back onto the heap, using a non-recursive style.

However, if you're capping JSON depths as an anti-DoS measure anyways (your parser isn't the only thing possibly vulnerable to blowing the stack via recursion - anything dealing with the parsed result is also in danger if it can be recursive), the heap fallback may be entirely dead code anyways... so why bother coding it?

Re:Bad JSON Parsers by __david__ on Friday November 08, 2019 @01:52PM (#21485425)
It depends on how big the stack frame of the recursive function is vs how big the amount of data needs to be saved fore each recursion level.

But… most likely yes.

Re:Bad JSON Parsers by zeroimpl on Friday November 08, 2019 @02:11PM (#21485632)
You'll need a data structure to store the results to return to the caller. This data structure by definition cannot be the call stack. So using a call stack is technically redundant.