| 1 |
# Internals |
| 2 |
|
| 3 |
This section records some design and implementation details. |
| 4 |
|
| 5 |
[TOC] |
| 6 |
|
| 7 |
# Architecture {#Architecture} |
| 8 |
|
| 9 |
## SAX and DOM |
| 10 |
|
| 11 |
The basic relationships of SAX and DOM is shown in the following UML diagram. |
| 12 |
|
| 13 |
 |
| 14 |
|
| 15 |
The core of the relationship is the `Handler` concept. From the SAX side, `Reader` parses a JSON from a stream and publish events to a `Handler`. `Writer` implements the `Handler` concept to handle the same set of events. From the DOM side, `Document` implements the `Handler` concept to build a DOM according to the events. `Value` supports a `Value::Accept(Handler&)` function, which traverses the DOM to publish events. |
| 16 |
|
| 17 |
With this design, SAX is not dependent on DOM. Even `Reader` and `Writer` have no dependencies between them. This provides flexibility to chain event publisher and handlers. Besides, `Value` does not depends on SAX as well. So, in addition to stringify a DOM to JSON, user may also stringify it to a XML writer, or do anything else. |
| 18 |
|
| 19 |
## Utility Classes |
| 20 |
|
| 21 |
Both SAX and DOM APIs depends on 3 additional concepts: `Allocator`, `Encoding` and `Stream`. Their inheritance hierarchy is shown as below. |
| 22 |
|
| 23 |
 |
| 24 |
|
| 25 |
# Value {#Value} |
| 26 |
|
| 27 |
`Value` (actually a typedef of `GenericValue<UTF8<>>`) is the core of DOM API. This section describes the design of it. |
| 28 |
|
| 29 |
## Data Layout {#DataLayout} |
| 30 |
|
| 31 |
`Value` is a [variant type](http://en.wikipedia.org/wiki/Variant_type). In RapidJSON's context, an instance of `Value` can contain 1 of 6 JSON value types. This is possible by using `union`. Each `Value` contains two members: `union Data data_` and a`unsigned flags_`. The `flags_` indicates the JSON type, and also additional information. |
| 32 |
|
| 33 |
The following tables show the data layout of each type. The 32-bit/64-bit columns indicates the size of the field in bytes. |
| 34 |
|
| 35 |
| Null | |32-bit|64-bit| |
| 36 |
|-------------------|----------------------------------|:----:|:----:| |
| 37 |
| (unused) | |4 |8 | |
| 38 |
| (unused) | |4 |4 | |
| 39 |
| (unused) | |4 |4 | |
| 40 |
| `unsigned flags_` | `kNullType kNullFlag` |4 |4 | |
| 41 |
|
| 42 |
| Bool | |32-bit|64-bit| |
| 43 |
|-------------------|----------------------------------------------------|:----:|:----:| |
| 44 |
| (unused) | |4 |8 | |
| 45 |
| (unused) | |4 |4 | |
| 46 |
| (unused) | |4 |4 | |
| 47 |
| `unsigned flags_` | `kBoolType` (either `kTrueFlag` or `kFalseFlag`) |4 |4 | |
| 48 |
|
| 49 |
| String | |32-bit|64-bit| |
| 50 |
|---------------------|-------------------------------------|:----:|:----:| |
| 51 |
| `Ch* str` | Pointer to the string (may own) |4 |8 | |
| 52 |
| `SizeType length` | Length of string |4 |4 | |
| 53 |
| (unused) | |4 |4 | |
| 54 |
| `unsigned flags_` | `kStringType kStringFlag ...` |4 |4 | |
| 55 |
|
| 56 |
| Object | |32-bit|64-bit| |
| 57 |
|---------------------|-------------------------------------|:----:|:----:| |
| 58 |
| `Member* members` | Pointer to array of members (owned) |4 |8 | |
| 59 |
| `SizeType size` | Number of members |4 |4 | |
| 60 |
| `SizeType capacity` | Capacity of members |4 |4 | |
| 61 |
| `unsigned flags_` | `kObjectType kObjectFlag` |4 |4 | |
| 62 |
|
| 63 |
| Array | |32-bit|64-bit| |
| 64 |
|---------------------|-------------------------------------|:----:|:----:| |
| 65 |
| `Value* values` | Pointer to array of values (owned) |4 |8 | |
| 66 |
| `SizeType size` | Number of values |4 |4 | |
| 67 |
| `SizeType capacity` | Capacity of values |4 |4 | |
| 68 |
| `unsigned flags_` | `kArrayType kArrayFlag` |4 |4 | |
| 69 |
|
| 70 |
| Number (Int) | |32-bit|64-bit| |
| 71 |
|---------------------|-------------------------------------|:----:|:----:| |
| 72 |
| `int i` | 32-bit signed integer |4 |4 | |
| 73 |
| (zero padding) | 0 |4 |4 | |
| 74 |
| (unused) | |4 |8 | |
| 75 |
| `unsigned flags_` | `kNumberType kNumberFlag kIntFlag kInt64Flag ...` |4 |4 | |
| 76 |
|
| 77 |
| Number (UInt) | |32-bit|64-bit| |
| 78 |
|---------------------|-------------------------------------|:----:|:----:| |
| 79 |
| `unsigned u` | 32-bit unsigned integer |4 |4 | |
| 80 |
| (zero padding) | 0 |4 |4 | |
| 81 |
| (unused) | |4 |8 | |
| 82 |
| `unsigned flags_` | `kNumberType kNumberFlag kUintFlag kUint64Flag ...` |4 |4 | |
| 83 |
|
| 84 |
| Number (Int64) | |32-bit|64-bit| |
| 85 |
|---------------------|-------------------------------------|:----:|:----:| |
| 86 |
| `int64_t i64` | 64-bit signed integer |8 |8 | |
| 87 |
| (unused) | |4 |8 | |
| 88 |
| `unsigned flags_` | `kNumberType kNumberFlag kInt64Flag ...` |4 |4 | |
| 89 |
|
| 90 |
| Number (Uint64) | |32-bit|64-bit| |
| 91 |
|---------------------|-------------------------------------|:----:|:----:| |
| 92 |
| `uint64_t i64` | 64-bit unsigned integer |8 |8 | |
| 93 |
| (unused) | |4 |8 | |
| 94 |
| `unsigned flags_` | `kNumberType kNumberFlag kInt64Flag ...` |4 |4 | |
| 95 |
|
| 96 |
| Number (Double) | |32-bit|64-bit| |
| 97 |
|---------------------|-------------------------------------|:----:|:----:| |
| 98 |
| `uint64_t i64` | Double precision floating-point |8 |8 | |
| 99 |
| (unused) | |4 |8 | |
| 100 |
| `unsigned flags_` | `kNumberType kNumberFlag kDoubleFlag` |4 |4 | |
| 101 |
|
| 102 |
Here are some notes: |
| 103 |
* To reduce memory consumption for 64-bit architecture, `SizeType` is typedef as `unsigned` instead of `size_t`. |
| 104 |
* Zero padding for 32-bit number may be placed after or before the actual type, according to the endianness. This makes possible for interpreting a 32-bit integer as a 64-bit integer, without any conversion. |
| 105 |
* An `Int` is always an `Int64`, but the converse is not always true. |
| 106 |
|
| 107 |
## Flags {#Flags} |
| 108 |
|
| 109 |
The 32-bit `flags_` contains both JSON type and other additional information. As shown in the above tables, each JSON type contains redundant `kXXXType` and `kXXXFlag`. This design is for optimizing the operation of testing bit-flags (`IsNumber()`) and obtaining a sequential number for each type (`GetType()`). |
| 110 |
|
| 111 |
String has two optional flags. `kCopyFlag` means that the string owns a copy of the string. `kInlineStrFlag` means using [Short-String Optimization](#ShortString). |
| 112 |
|
| 113 |
Number is a bit more complicated. For normal integer values, it can contains `kIntFlag`, `kUintFlag`, `kInt64Flag` and/or `kUint64Flag`, according to the range of the integer. For numbers with fraction, and integers larger than 64-bit range, they will be stored as `double` with `kDoubleFlag`. |
| 114 |
|
| 115 |
## Short-String Optimization {#ShortString} |
| 116 |
|
| 117 |
[Kosta](https://github.com/Kosta-Github) provided a very neat short-string optimization. The optimization idea is given as follow. Excluding the `flags_`, a `Value` has 12 or 16 bytes (32-bit or 64-bit) for storing actual data. Instead of storing a pointer to a string, it is possible to store short strings in these space internally. For encoding with 1-byte character type (e.g. `char`), it can store maximum 11 or 15 characters string inside the `Value` type. |
| 118 |
|
| 119 |
| ShortString (Ch=char) | |32-bit|64-bit| |
| 120 |
|---------------------|-------------------------------------|:----:|:----:| |
| 121 |
| `Ch str[MaxChars]` | String buffer |11 |15 | |
| 122 |
| `Ch invLength` | MaxChars - Length |1 |1 | |
| 123 |
| `unsigned flags_` | `kStringType kStringFlag ...` |4 |4 | |
| 124 |
|
| 125 |
A special technique is applied. Instead of storing the length of string directly, it stores (MaxChars - length). This make it possible to store 11 characters with trailing `\0`. |
| 126 |
|
| 127 |
This optimization can reduce memory usage for copy-string. It can also improve cache-coherence thus improve runtime performance. |
| 128 |
|
| 129 |
# Allocator {#InternalAllocator} |
| 130 |
|
| 131 |
`Allocator` is a concept in RapidJSON: |
| 132 |
~~~cpp |
| 133 |
concept Allocator { |
| 134 |
static const bool kNeedFree; //!< Whether this allocator needs to call Free(). |
| 135 |
|
| 136 |
// Allocate a memory block. |
| 137 |
// \param size of the memory block in bytes. |
| 138 |
// \returns pointer to the memory block. |
| 139 |
void* Malloc(size_t size); |
| 140 |
|
| 141 |
// Resize a memory block. |
| 142 |
// \param originalPtr The pointer to current memory block. Null pointer is permitted. |
| 143 |
// \param originalSize The current size in bytes. (Design issue: since some allocator may not book-keep this, explicitly pass to it can save memory.) |
| 144 |
// \param newSize the new size in bytes. |
| 145 |
void* Realloc(void* originalPtr, size_t originalSize, size_t newSize); |
| 146 |
|
| 147 |
// Free a memory block. |
| 148 |
// \param pointer to the memory block. Null pointer is permitted. |
| 149 |
static void Free(void *ptr); |
| 150 |
}; |
| 151 |
~~~ |
| 152 |
|
| 153 |
Note that `Malloc()` and `Realloc()` are member functions but `Free()` is static member function. |
| 154 |
|
| 155 |
## MemoryPoolAllocator {#MemoryPoolAllocator} |
| 156 |
|
| 157 |
`MemoryPoolAllocator` is the default allocator for DOM. It allocate but do not free memory. This is suitable for building a DOM tree. |
| 158 |
|
| 159 |
Internally, it allocates chunks of memory from the base allocator (by default `CrtAllocator`) and stores the chunks as a singly linked list. When user requests an allocation, it allocates memory from the following order: |
| 160 |
|
| 161 |
1. User supplied buffer if it is available. (See [User Buffer section in DOM](doc/dom.md)) |
| 162 |
2. If user supplied buffer is full, use the current memory chunk. |
| 163 |
3. If the current block is full, allocate a new block of memory. |
| 164 |
|
| 165 |
# Parsing Optimization {#ParsingOptimization} |
| 166 |
|
| 167 |
## Skip Whitespaces with SIMD {#SkipwhitespaceWithSIMD} |
| 168 |
|
| 169 |
When parsing JSON from a stream, the parser need to skip 4 whitespace characters: |
| 170 |
|
| 171 |
1. Space (`U+0020`) |
| 172 |
2. Character Tabulation (`U+000B`) |
| 173 |
3. Line Feed (`U+000A`) |
| 174 |
4. Carriage Return (`U+000D`) |
| 175 |
|
| 176 |
A simple implementation will be simply: |
| 177 |
~~~cpp |
| 178 |
void SkipWhitespace(InputStream& s) { |
| 179 |
while (s.Peek() == ' ' || s.Peek() == '\n' || s.Peek() == '\r' || s.Peek() == '\t') |
| 180 |
s.Take(); |
| 181 |
} |
| 182 |
~~~ |
| 183 |
|
| 184 |
However, this requires 4 comparisons and a few branching for each character. This was found to be a hot spot. |
| 185 |
|
| 186 |
To accelerate this process, SIMD was applied to compare 16 characters with 4 white spaces for each iteration. Currently RapidJSON supports SSE2, SSE4.2 and ARM Neon instructions for this. And it is only activated for UTF-8 memory streams, including string stream or *in situ* parsing. |
| 187 |
|
| 188 |
To enable this optimization, need to define `RAPIDJSON_SSE2`, `RAPIDJSON_SSE42` or `RAPIDJSON_NEON` before including `rapidjson.h`. Some compilers can detect the setting, as in `perftest.h`: |
| 189 |
|
| 190 |
~~~cpp |
| 191 |
// __SSE2__ and __SSE4_2__ are recognized by gcc, clang, and the Intel compiler. |
| 192 |
// We use -march=native with gmake to enable -msse2 and -msse4.2, if supported. |
| 193 |
// Likewise, __ARM_NEON is used to detect Neon. |
| 194 |
#if defined(__SSE4_2__) |
| 195 |
# define RAPIDJSON_SSE42 |
| 196 |
#elif defined(__SSE2__) |
| 197 |
# define RAPIDJSON_SSE2 |
| 198 |
#elif defined(__ARM_NEON) |
| 199 |
# define RAPIDJSON_NEON |
| 200 |
#endif |
| 201 |
~~~ |
| 202 |
|
| 203 |
Note that, these are compile-time settings. Running the executable on a machine without such instruction set support will make it crash. |
| 204 |
|
| 205 |
### Page boundary issue |
| 206 |
|
| 207 |
In an early version of RapidJSON, [an issue](https://code.google.com/archive/p/rapidjson/issues/104) reported that the `SkipWhitespace_SIMD()` causes crash very rarely (around 1 in 500,000). After investigation, it is suspected that `_mm_loadu_si128()` accessed bytes after `'\0'`, and across a protected page boundary. |
| 208 |
|
| 209 |
In [Intel® 64 and IA-32 Architectures Optimization Reference Manual |
| 210 |
](http://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-optimization-manual.html), section 10.2.1: |
| 211 |
|
| 212 |
> To support algorithms requiring unaligned 128-bit SIMD memory accesses, memory buffer allocation by a caller function should consider adding some pad space so that a callee function can safely use the address pointer safely with unaligned 128-bit SIMD memory operations. |
| 213 |
> The minimal padding size should be the width of the SIMD register that might be used in conjunction with unaligned SIMD memory access. |
| 214 |
|
| 215 |
This is not feasible as RapidJSON should not enforce such requirement. |
| 216 |
|
| 217 |
To fix this issue, currently the routine process bytes up to the next aligned address. After tha, use aligned read to perform SIMD processing. Also see [#85](https://github.com/Tencent/rapidjson/issues/85). |
| 218 |
|
| 219 |
## Local Stream Copy {#LocalStreamCopy} |
| 220 |
|
| 221 |
During optimization, it is found that some compilers cannot localize some member data access of streams into local variables or registers. Experimental results show that for some stream types, making a copy of the stream and used it in inner-loop can improve performance. For example, the actual (non-SIMD) implementation of `SkipWhitespace()` is implemented as: |
| 222 |
|
| 223 |
~~~cpp |
| 224 |
template<typename InputStream> |
| 225 |
void SkipWhitespace(InputStream& is) { |
| 226 |
internal::StreamLocalCopy<InputStream> copy(is); |
| 227 |
InputStream& s(copy.s); |
| 228 |
|
| 229 |
while (s.Peek() == ' ' || s.Peek() == '\n' || s.Peek() == '\r' || s.Peek() == '\t') |
| 230 |
s.Take(); |
| 231 |
} |
| 232 |
~~~ |
| 233 |
|
| 234 |
Depending on the traits of stream, `StreamLocalCopy` will make (or not make) a copy of the stream object, use it locally and copy the states of stream back to the original stream. |
| 235 |
|
| 236 |
## Parsing to Double {#ParsingDouble} |
| 237 |
|
| 238 |
Parsing string into `double` is difficult. The standard library function `strtod()` can do the job but it is slow. By default, the parsers use normal precision setting. This has has maximum 3 [ULP](http://en.wikipedia.org/wiki/Unit_in_the_last_place) error and implemented in `internal::StrtodNormalPrecision()`. |
| 239 |
|
| 240 |
When using `kParseFullPrecisionFlag`, the parsers calls `internal::StrtodFullPrecision()` instead, and this function actually implemented 3 versions of conversion methods. |
| 241 |
1. [Fast-Path](http://www.exploringbinary.com/fast-path-decimal-to-floating-point-conversion/). |
| 242 |
2. Custom DIY-FP implementation as in [double-conversion](https://github.com/floitsch/double-conversion). |
| 243 |
3. Big Integer Method as in (Clinger, William D. How to read floating point numbers accurately. Vol. 25. No. 6. ACM, 1990). |
| 244 |
|
| 245 |
If the first conversion methods fail, it will try the second, and so on. |
| 246 |
|
| 247 |
# Generation Optimization {#GenerationOptimization} |
| 248 |
|
| 249 |
## Integer-to-String conversion {#itoa} |
| 250 |
|
| 251 |
The naive algorithm for integer-to-string conversion involves division per each decimal digit. We have implemented various implementations and evaluated them in [itoa-benchmark](https://github.com/miloyip/itoa-benchmark). |
| 252 |
|
| 253 |
Although SSE2 version is the fastest but the difference is minor by comparing to the first running-up `branchlut`. And `branchlut` is pure C++ implementation so we adopt `branchlut` in RapidJSON. |
| 254 |
|
| 255 |
## Double-to-String conversion {#dtoa} |
| 256 |
|
| 257 |
Originally RapidJSON uses `snprintf(..., ..., "%g")` to achieve double-to-string conversion. This is not accurate as the default precision is 6. Later we also find that this is slow and there is an alternative. |
| 258 |
|
| 259 |
Google's V8 [double-conversion](https://github.com/floitsch/double-conversion |
| 260 |
) implemented a newer, fast algorithm called Grisu3 (Loitsch, Florian. "Printing floating-point numbers quickly and accurately with integers." ACM Sigplan Notices 45.6 (2010): 233-243.). |
| 261 |
|
| 262 |
However, since it is not header-only so that we implemented a header-only version of Grisu2. This algorithm guarantees that the result is always accurate. And in most of cases it produces the shortest (optimal) string representation. |
| 263 |
|
| 264 |
The header-only conversion function has been evaluated in [dtoa-benchmark](https://github.com/miloyip/dtoa-benchmark). |
| 265 |
|
| 266 |
# Parser {#Parser} |
| 267 |
|
| 268 |
## Iterative Parser {#IterativeParser} |
| 269 |
|
| 270 |
The iterative parser is a recursive descent LL(1) parser |
| 271 |
implemented in a non-recursive manner. |
| 272 |
|
| 273 |
### Grammar {#IterativeParserGrammar} |
| 274 |
|
| 275 |
The grammar used for this parser is based on strict JSON syntax: |
| 276 |
~~~~~~~~~~ |
| 277 |
S -> array | object |
| 278 |
array -> [ values ] |
| 279 |
object -> { members } |
| 280 |
values -> non-empty-values | ε |
| 281 |
non-empty-values -> value addition-values |
| 282 |
addition-values -> ε | , non-empty-values |
| 283 |
members -> non-empty-members | ε |
| 284 |
non-empty-members -> member addition-members |
| 285 |
addition-members -> ε | , non-empty-members |
| 286 |
member -> STRING : value |
| 287 |
value -> STRING | NUMBER | NULL | BOOLEAN | object | array |
| 288 |
~~~~~~~~~~ |
| 289 |
|
| 290 |
Note that left factoring is applied to non-terminals `values` and `members` |
| 291 |
to make the grammar be LL(1). |
| 292 |
|
| 293 |
### Parsing Table {#IterativeParserParsingTable} |
| 294 |
|
| 295 |
Based on the grammar, we can construct the FIRST and FOLLOW set. |
| 296 |
|
| 297 |
The FIRST set of non-terminals is listed below: |
| 298 |
|
| 299 |
| NON-TERMINAL | FIRST | |
| 300 |
|:-----------------:|:--------------------------------:| |
| 301 |
| array | [ | |
| 302 |
| object | { | |
| 303 |
| values | ε STRING NUMBER NULL BOOLEAN { [ | |
| 304 |
| addition-values | ε COMMA | |
| 305 |
| members | ε STRING | |
| 306 |
| addition-members | ε COMMA | |
| 307 |
| member | STRING | |
| 308 |
| value | STRING NUMBER NULL BOOLEAN { [ | |
| 309 |
| S | [ { | |
| 310 |
| non-empty-members | STRING | |
| 311 |
| non-empty-values | STRING NUMBER NULL BOOLEAN { [ | |
| 312 |
|
| 313 |
The FOLLOW set is listed below: |
| 314 |
|
| 315 |
| NON-TERMINAL | FOLLOW | |
| 316 |
|:-----------------:|:-------:| |
| 317 |
| S | $ | |
| 318 |
| array | , $ } ] | |
| 319 |
| object | , $ } ] | |
| 320 |
| values | ] | |
| 321 |
| non-empty-values | ] | |
| 322 |
| addition-values | ] | |
| 323 |
| members | } | |
| 324 |
| non-empty-members | } | |
| 325 |
| addition-members | } | |
| 326 |
| member | , } | |
| 327 |
| value | , } ] | |
| 328 |
|
| 329 |
Finally the parsing table can be constructed from FIRST and FOLLOW set: |
| 330 |
|
| 331 |
| NON-TERMINAL | [ | { | , | : | ] | } | STRING | NUMBER | NULL | BOOLEAN | |
| 332 |
|:-----------------:|:---------------------:|:---------------------:|:-------------------:|:-:|:-:|:-:|:-----------------------:|:---------------------:|:---------------------:|:---------------------:| |
| 333 |
| S | array | object | | | | | | | | | |
| 334 |
| array | [ values ] | | | | | | | | | | |
| 335 |
| object | | { members } | | | | | | | | | |
| 336 |
| values | non-empty-values | non-empty-values | | | ε | | non-empty-values | non-empty-values | non-empty-values | non-empty-values | |
| 337 |
| non-empty-values | value addition-values | value addition-values | | | | | value addition-values | value addition-values | value addition-values | value addition-values | |
| 338 |
| addition-values | | | , non-empty-values | | ε | | | | | | |
| 339 |
| members | | | | | | ε | non-empty-members | | | | |
| 340 |
| non-empty-members | | | | | | | member addition-members | | | | |
| 341 |
| addition-members | | | , non-empty-members | | | ε | | | | | |
| 342 |
| member | | | | | | | STRING : value | | | | |
| 343 |
| value | array | object | | | | | STRING | NUMBER | NULL | BOOLEAN | |
| 344 |
|
| 345 |
There is a great [tool](http://hackingoff.com/compilers/predict-first-follow-set) for above grammar analysis. |
| 346 |
|
| 347 |
### Implementation {#IterativeParserImplementation} |
| 348 |
|
| 349 |
Based on the parsing table, a direct(or conventional) implementation |
| 350 |
that pushes the production body in reverse order |
| 351 |
while generating a production could work. |
| 352 |
|
| 353 |
In RapidJSON, several modifications(or adaptations to current design) are made to a direct implementation. |
| 354 |
|
| 355 |
First, the parsing table is encoded in a state machine in RapidJSON. |
| 356 |
States are constructed by the head and body of production. |
| 357 |
State transitions are constructed by production rules. |
| 358 |
Besides, extra states are added for productions involved with `array` and `object`. |
| 359 |
In this way the generation of array values or object members would be a single state transition, |
| 360 |
rather than several pop/push operations in the direct implementation. |
| 361 |
This also makes the estimation of stack size more easier. |
| 362 |
|
| 363 |
The state diagram is shown as follows: |
| 364 |
|
| 365 |
 |
| 366 |
|
| 367 |
Second, the iterative parser also keeps track of array's value count and object's member count |
| 368 |
in its internal stack, which may be different from a conventional implementation. |