miloyip/rapidjson — pull request #76 by thebusytypist (2014-07-17 13:10:33+00:00)
Title: Iterative Parsing (for issue #35)

* Implementation Overview
This pull request provides an iterative(non-recursive) implementation of JSON parsing.
It tries to resolve the issue #35 by:
+ saving parser state in an internal stack rather than using function local stack. In this way the complexity of function stack size is constant.
+ providing a stack size limit to the parsing function.

* Implementation Details
This pull request adds a new flag `kParseIterativeFlag` to `ParseFlag`.
Parsing work with this flag will be directed to `GenericReader::IterativeParse`, which is the entry point of this iterative parser.
Then the parser will traverse the given token stream and make transitions on a state machine.
The state transition table is manually encoded in a static array, which is in function `GenericReader::Predict`.
And the action code for every transition is in function `GenericReader::Transit`.

* Performance Report
Performance tests have been taken among:
+ `kParseDefaultFlags` (recursive parser, without in-situ)
+ `kParseIterativeFlag` (iterative parser, without in-situ)
+ `kParseInsituFlag` (recursive parser, with in-situ)
+ `kParseIterativeFlag | kParseInsituFlag` (iterative parser, with in-situ)

I expected the parsers with `kParseIterativeFlag` are both slower or quicker than their counterparts.
But the iterative parser without in-situ flag runs exceptionally slower than other parsers, while the iterative parser with in-situ being the most quick one.
@pah pointed out this may be compiler-specific in https://github.com/miloyip/rapidjson/issues/35#issuecomment-48700648.