mirror of
https://github.com/simdjson/simdjson
synced 2026-06-08 17:27:07 +00:00
lemire
341 lines
20 KiB
HTML
341 lines
20 KiB
HTML
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "https://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
|
|
<html xmlns="http://www.w3.org/1999/xhtml" lang="en-US">
|
|
<head>
|
|
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
|
|
<meta http-equiv="X-UA-Compatible" content="IE=11"/>
|
|
<meta name="generator" content="Doxygen 1.9.8"/>
|
|
<meta name="viewport" content="width=device-width, initial-scale=1"/>
|
|
<title>simdjson: parse_many</title>
|
|
<link href="tabs.css" rel="stylesheet" type="text/css"/>
|
|
<script type="text/javascript" src="jquery.js"></script>
|
|
<script type="text/javascript" src="dynsections.js"></script>
|
|
<link href="navtree.css" rel="stylesheet" type="text/css"/>
|
|
<script type="text/javascript" src="resize.js"></script>
|
|
<script type="text/javascript" src="navtreedata.js"></script>
|
|
<script type="text/javascript" src="navtree.js"></script>
|
|
<link href="search/search.css" rel="stylesheet" type="text/css"/>
|
|
<script type="text/javascript" src="search/searchdata.js"></script>
|
|
<script type="text/javascript" src="search/search.js"></script>
|
|
<link href="doxygen.css" rel="stylesheet" type="text/css" />
|
|
<link href="doxygen-awesome.css" rel="stylesheet" type="text/css"/>
|
|
<link href="doxygen-awesome-sidebar-only.css" rel="stylesheet" type="text/css"/>
|
|
<link href="doxygen-awesome-sidebar-only-darkmode-toggle.css" rel="stylesheet" type="text/css"/>
|
|
</head>
|
|
<body>
|
|
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
|
|
<div id="titlearea">
|
|
<table cellspacing="0" cellpadding="0">
|
|
<tbody>
|
|
<tr id="projectrow">
|
|
<td id="projectlogo"><img alt="Logo" src="logotiny.png"/></td>
|
|
<td id="projectalign">
|
|
<div id="projectname">simdjson<span id="projectnumber"> 4.6.4</span>
|
|
</div>
|
|
<div id="projectbrief">Ridiculously Fast JSON</div>
|
|
</td>
|
|
</tr>
|
|
</tbody>
|
|
</table>
|
|
</div>
|
|
<!-- end header part -->
|
|
<!-- Generated by Doxygen 1.9.8 -->
|
|
<script type="text/javascript">
|
|
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
|
|
var searchBox = new SearchBox("searchBox", "search/",'.html');
|
|
/* @license-end */
|
|
</script>
|
|
<script type="text/javascript" src="menudata.js"></script>
|
|
<script type="text/javascript" src="menu.js"></script>
|
|
<script type="text/javascript">
|
|
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
|
|
$(function() {
|
|
initMenu('',true,false,'search.php','Search');
|
|
$(document).ready(function() { init_search(); });
|
|
});
|
|
/* @license-end */
|
|
</script>
|
|
<div id="main-nav"></div>
|
|
</div><!-- top -->
|
|
<div id="side-nav" class="ui-resizable side-nav-resizable">
|
|
<div id="nav-tree">
|
|
<div id="nav-tree-contents">
|
|
<div id="nav-sync" class="sync"></div>
|
|
</div>
|
|
</div>
|
|
<div id="splitbar" style="-moz-user-select:none;"
|
|
class="ui-resizable-handle">
|
|
</div>
|
|
</div>
|
|
<script type="text/javascript">
|
|
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
|
|
$(document).ready(function(){initNavTree('md_doc_2parse__many.html',''); initResizable(); });
|
|
/* @license-end */
|
|
</script>
|
|
<div id="doc-content">
|
|
<!-- window showing the filter options -->
|
|
<div id="MSearchSelectWindow"
|
|
onmouseover="return searchBox.OnSearchSelectShow()"
|
|
onmouseout="return searchBox.OnSearchSelectHide()"
|
|
onkeydown="return searchBox.OnSearchSelectKey(event)">
|
|
</div>
|
|
|
|
<!-- iframe showing the search results (closed by default) -->
|
|
<div id="MSearchResultsWindow">
|
|
<div id="MSearchResults">
|
|
<div class="SRPage">
|
|
<div id="SRIndex">
|
|
<div id="SRResults"></div>
|
|
<div class="SRStatus" id="Loading">Loading...</div>
|
|
<div class="SRStatus" id="Searching">Searching...</div>
|
|
<div class="SRStatus" id="NoMatches">No Matches</div>
|
|
</div>
|
|
</div>
|
|
</div>
|
|
</div>
|
|
|
|
<div><div class="header">
|
|
<div class="headertitle"><div class="title">parse_many</div></div>
|
|
</div><!--header-->
|
|
<div class="contents">
|
|
<div class="textblock"><p>An interface providing features to work with files or streams containing multiple small JSON documents. Given an input such as </p><div class="fragment"><div class="line">{"text":"a"}</div>
|
|
<div class="line">{"text":"b"}</div>
|
|
<div class="line">{"text":"c"}</div>
|
|
<div class="line">...</div>
|
|
</div><!-- fragment --><p> ... you want to read the entries (individual JSON documents) as quickly and as conveniently as possible. Importantly, the input might span several gigabytes, but you want to use a small (fixed) amount of memory. Ideally, you'd also like the parallelize the processing (using more than one core) to speed up the process.</p>
|
|
<h1><a class="anchor" id="autotoc_md137"></a>
|
|
Contents</h1>
|
|
<ul>
|
|
<li>Motivations</li>
|
|
<li>Performance</li>
|
|
<li>How it works</li>
|
|
<li>Support</li>
|
|
<li>API</li>
|
|
<li>Use cases</li>
|
|
<li>Tracking your position</li>
|
|
<li>Incomplete streams</li>
|
|
</ul>
|
|
<h1><a class="anchor" id="autotoc_md138"></a>
|
|
Motivation</h1>
|
|
<p>The main motivation for this piece of software is to achieve maximum speed and offer a better quality of life in parsing files containing multiple small JSON documents.</p>
|
|
<p>The JavaScript Object Notation (JSON) <a href="https://tools.ietf.org/html/rfc7159">RFC7159</a> is a handy serialization format. However, when serializing a large sequence of values as an array, or a possibly indeterminate-length or never- ending sequence of values, JSON may be inconvenient.</p>
|
|
<p>Consider a sequence of one million values, each possibly one kilobyte when encoded – roughly one gigabyte. It is often desirable to process such a dataset incrementally without having to first read all of it before beginning to produce results.</p>
|
|
<h1><a class="anchor" id="autotoc_md139"></a>
|
|
Performance</h1>
|
|
<p>The following is a chart comparing the speed of the different alternatives to parse a multiline JSON. The simdjson library provides a threaded and non-threaded <code>parse_many()</code> implementation. As the figure below shows, if you can, use threads, but if you cannot, the unthreaded mode is still fast! <a href="/doc/Multiline_JSON_Parse_Competition.png"><img src="/doc/Multiline_JSON_Parse_Competition.png" alt="Chart.png" class="inline"/></a></p>
|
|
<h1><a class="anchor" id="autotoc_md140"></a>
|
|
How it works</h1>
|
|
<h2><a class="anchor" id="autotoc_md141"></a>
|
|
Context</h2>
|
|
<p>The parsing in simdjson is divided into 2 stages. First, in stage 1, we parse the document and find all the structural indexes (<code>{</code>, <code>}</code>, <code>]</code>, <code>[</code>, <code>,</code>, <code>"</tt>, ...) and validate UTF8. Then, in stage 2,
|
|
we go through the document again and build the tape using structural indexes found during stage 1.
|
|
Although stage 1 finds the structural indexes, it has no knowledge of the structure of the document
|
|
nor does it know whether it parsed a valid document, multiple documents, or even if the document is
|
|
complete.
|
|
|
|
Prior to parse_many, most people who had to parse a multiline JSON file would proceed by reading the
|
|
file line by line, using a utility function like <tt>std::getline</tt> or equivalent, and would then use
|
|
the <tt>parse</tt> on each of those lines. From a performance point of view, this process is highly
|
|
inefficient, in that it requires a lot of unnecessary memory allocation and makes use of the
|
|
<tt>getline</tt> function, which is fundamentally slow, slower than the act of parsing with simdjson
|
|
<a href="<a href="https://lemire.me/blog/2019/06/18/how-fast-is-getline-in-c/">https://lemire.me/blog/2019/06/18/how-fast-is-getline-in-c/</a>" >(more on this here)</a>.
|
|
|
|
Unlike the popular parser RapidJson, our DOM does not require the buffer once the parsing job is
|
|
completed, the DOM and the buffer are completely independent. The drawback of this architecture is
|
|
that we need to allocate some additional memory to store our ParsedJson data, for every document
|
|
inside a given file. Memory allocation can be slow and become a bottleneck, therefore, we want to
|
|
minimize it as much as possible.
|
|
|
|
@subsection autotoc_md142 Design
|
|
|
|
To achieve a minimum amount of allocations, we opted for a design where we create only one
|
|
parser object and therefore allocate its memory once, and then recycle it for every document in a
|
|
given file. But, knowing that they often have largely varying size, we need to make sure that we
|
|
allocate enough memory so that all the documents can fit. This value is what we call the batch size.
|
|
As of right now, we need to manually specify a value for this batch size, it has to be at least as
|
|
big as the biggest document in your file, but not too big so that it submerges the cached memory.
|
|
The bigger the batch size, the fewer we need to make allocations. We found that 1MB is somewhat a
|
|
sweet spot.
|
|
|
|
1. When the user calls <tt>parse_many</tt>, we return a <tt>document_stream</tt> which the user can iterate over
|
|
to receive parsed documents.
|
|
2. We call stage 1 on the first batch_size bytes of JSON in the buffer, detecting structural
|
|
indexes for all documents in that batch.
|
|
3. We call stage 2 on the indexes, reading tokens until we reach the end of a valid document (i.e.
|
|
a single array, object, string, boolean, number or null).
|
|
4. Each time the user calls <tt>++</tt> to read the next document, we call stage 2 to parse the next
|
|
document where we left off.
|
|
5. When we reach the end of the batch, we call stage 1 on the next batch, starting from the end of
|
|
the last document, and go to step 3.
|
|
|
|
@subsection autotoc_md143 Threads
|
|
|
|
But how can we make use of threads if they are available? We found a pretty cool algorithm that allows us to quickly
|
|
identify the position of the last JSON document in a given batch. Knowing exactly where the end of
|
|
the batch is, we no longer need for stage 2 to finish in order to load a new batch. We already know
|
|
where to start the next batch. Therefore, we can run stage 1 on the next batch concurrently while
|
|
the main thread is going through stage 2. Running stage 1 in a different thread can, in best
|
|
cases, remove almost entirely its cost and replaces it by the overhead of a thread, which is orders
|
|
of magnitude cheaper. Ain't that awesome!
|
|
|
|
Thread support is only active if thread supported is detected in which case the macro
|
|
SIMDJSON_THREADS_ENABLED is set. You can also manually pass <tt>SIMDJSON_THREADS_ENABLED=1</tt> flag
|
|
to the library. Otherwise the library runs in single-thread mode.
|
|
|
|
You should be consistent. If you link against the simdjson library built for multithreading
|
|
(i.e., with <tt>SIMDJSON_THREADS_ENABLED</tt>), then you should build your application with multithreading
|
|
system (setting <tt>SIMDJSON_THREADS_ENABLED=1</tt> and linking against a thread library).
|
|
|
|
A <tt>document_stream</tt> instance uses at most two threads: there is a main thread and a worker thread.
|
|
You should expect the main thread to be fully occupied while the worker thread is partially busy
|
|
(e.g., 80% of the time).
|
|
|
|
@section autotoc_md144 Support
|
|
|
|
|
|
Since we want to offer flexibility and not restrict ourselves to a specific file
|
|
format, we support any file that contains any amount of valid JSON document, <strong>separated by one
|
|
or more character that is considered whitespace</strong> by the JSON spec. Anything that is
|
|
not whitespace will be parsed as a JSON document and could lead to failure.
|
|
|
|
Whitespace Characters:
|
|
- <strong>Space</strong>
|
|
- <strong>Linefeed</strong>
|
|
- <strong>Carriage return</strong>
|
|
- <strong>Horizontal tab</strong>
|
|
- <strong>Nothing</strong>
|
|
|
|
Some official formats **(non-exhaustive list)**:
|
|
- <a href="<a href="https://github.com/ndjson/ndjson-spec">https://github.com/ndjson/ndjson-spec</a>" >Newline-Delimited JSON (NDJSON)</a>
|
|
- <a href="<a href="http://jsonlines.org/">http://jsonlines.org/</a>" >JSON lines (JSONL)</a>
|
|
- <a href="<a href="https://tools.ietf.org/html/rfc7464">https://tools.ietf.org/html/rfc7464</a>" >Record separator-delimited JSON (RFC 7464)</a> <- Not supported by simdjson!
|
|
- <a href="<a href="https://en.wikipedia.org/wiki/JSON_streaming">https://en.wikipedia.org/wiki/JSON_streaming</a>" >More on Wikipedia...</a>
|
|
|
|
@section autotoc_md145 API
|
|
|
|
|
|
See <a href="basics.md::newline-delimited-json-ndjson-and-json-lines" >basics.md</a> for an overview of the API.
|
|
|
|
@section autotoc_md146 Use cases
|
|
|
|
From <a href="<a href="http://jsonlines.org/examples/">http://jsonlines.org/examples/</a>" >jsonlines.org</a>:
|
|
|
|
- <strong>Better than CSV</strong>
|
|
@icode{json}
|
|
["Name", "Session", "Score", "Completed"]
|
|
["Gilbert", "2013", 24, true]
|
|
["Alexa", "2013", 29, true]
|
|
["May", "2012B", 14, false]
|
|
["Deloise", "2012A", 19, true]
|
|
@endicode
|
|
CSV seems so easy that many programmers have written code to generate it themselves, and almost every implementation is
|
|
different. Handling broken CSV files is a common and frustrating task. CSV has no standard encoding, no standard column
|
|
separator and multiple character escaping standards. String is the only type supported for cell values, so some programs
|
|
attempt to guess the correct types.
|
|
|
|
JSON Lines handles tabular data cleanly and without ambiguity. Cells may use the standard JSON types.
|
|
|
|
The biggest missing piece is an import/export filter for popular spreadsheet programs so that non-programmers can use
|
|
this format.
|
|
|
|
- <strong>Easy Nested Data</strong>
|
|
@icode{json}
|
|
{"name": "Gilbert", "wins": [["straight", "7♣"], ["one pair", "10♥"]]}
|
|
{"name": "Alexa", "wins": [["two pair", "4♠"], ["two pair", "9♠"]]}
|
|
{"name": "May", "wins": []}
|
|
{"name": "Deloise", "wins": [["three of a kind", "5♣"]]}
|
|
@endicode
|
|
JSON Lines' biggest strength is in handling lots of similar nested data structures. One .jsonl file is easier to
|
|
work with than a directory full of XML files.
|
|
|
|
|
|
@section autotoc_md147 Tracking your position
|
|
|
|
|
|
Some users would like to know where the document they parsed is in the input array of bytes.
|
|
It is possible to do so by accessing directly the iterator and calling its <tt>current_index()</tt>
|
|
method which reports the location (in bytes) of the current document in the input stream.
|
|
You may also call the <tt>source()</tt> method to get a <tt>std::string_view</tt> instance on the document.
|
|
|
|
Let us illustrate the idea with code:
|
|
|
|
|
|
@icode{cpp}
|
|
auto json = R"([1,2,3] {"1":1,"2":3,"4":4} [1,2,3] )"_padded;
|
|
simdjson::dom::parser parser;
|
|
simdjson::dom::document_stream stream;
|
|
auto error = parser.parse_many(json).get(stream);
|
|
if (error) { /* do something */ }
|
|
auto i = stream.begin();
|
|
size_t count{0};
|
|
for(; i != stream.end(); ++i) {
|
|
auto doc = *i;
|
|
if (!doc.error()) {
|
|
std::cout << "got full document at " << i.current_index() << std::endl;
|
|
std::cout << i.source() << std::endl;
|
|
count++;
|
|
} else {
|
|
std::cout << "got broken document at " << i.current_index() << std::endl;
|
|
return false;
|
|
}
|
|
}
|
|
|
|
@endicode
|
|
|
|
This code will print:
|
|
@icode
|
|
got full document at 0
|
|
[1,2,3]
|
|
got full document at 9
|
|
{"1":1,"2":3,"4":4}
|
|
got full document at 29
|
|
[1,2,3]
|
|
@endicode
|
|
|
|
|
|
|
|
<strong>Advanced feature:</strong>
|
|
On non-Windows systems, you can use memory-file mapping to create a <tt>simdjson::padded_string_view</tt>
|
|
from a file on disk.
|
|
|
|
@icode{cpp}
|
|
// If the macro _WIN32 is defined, this will not work since we do not support memory-file mapping
|
|
// under Windows at this time.
|
|
simdjson::padded_memory_map map(myfilename);
|
|
if (!map.is_valid()) { /* handle error */ }
|
|
simdjson::padded_string_view view = map.view(); // view is usable while padded_memory_map is in scope
|
|
ondemand::document doc = parser.iterate(view); // parse the JSON
|
|
@endicode
|
|
|
|
@section autotoc_md148 Incomplete streams
|
|
|
|
|
|
Some users may need to work with truncated streams. The simdjson may truncate documents at the very end of the stream that cannot possibly be valid JSON (e.g., they contain unclosed strings, unmatched brackets, unmatched braces). After iterating through the stream, you may query the <tt>truncated_bytes()</tt> method which tells you how many bytes were truncated. If the stream is made of full (whole) documents, then you should expect <tt>truncated_bytes()</tt> to return zero.
|
|
|
|
|
|
Consider the following example where a truncated document (<tt>{"key":"intentionally unclosed string</code>) containing 39 bytes has been left within the stream. In such cases, the first two whole documents are parsed and returned, and the <code>truncated_bytes()</code> method returns 39.</p>
|
|
<div class="fragment"><div class="line"><span class="keyword">auto</span> json = R<span class="stringliteral">"([1,2,3] {"1":1,"2":3,"4":4} {"key":"intentionally unclosed string )"_padded;</span></div>
|
|
<div class="line"><span class="stringliteral"><a class="code hl_class" href="classsimdjson_1_1dom_1_1parser.html">simdjson::dom::parser</a> parser;</span></div>
|
|
<div class="line"><span class="stringliteral"><a class="code hl_class" href="classsimdjson_1_1dom_1_1document__stream.html">simdjson::dom::document_stream</a> stream;</span></div>
|
|
<div class="line"><span class="stringliteral"></span><span class="keyword">auto</span> error = parser.<a class="code hl_function" href="classsimdjson_1_1dom_1_1parser.html#a5c658556dd9e9396e9ce44ba4b01f2d1">parse_many</a>(json,json.size()).get(stream);</div>
|
|
<div class="line"><span class="keywordflow">if</span> (error) { std::cerr << error << std::endl; <span class="keywordflow">return</span>; }</div>
|
|
<div class="line"><span class="keywordflow">for</span>(<span class="keyword">auto</span> doc : stream) {</div>
|
|
<div class="line"> std::cout << doc << std::endl;</div>
|
|
<div class="line">}</div>
|
|
<div class="line">std::cout << stream.<a class="code hl_function" href="classsimdjson_1_1dom_1_1document__stream.html#a6c2a07e08213dc9a51754940942f9e69">truncated_bytes</a>() << <span class="stringliteral">" bytes "</span><< std::endl; <span class="comment">// returns 39 bytes</span></div>
|
|
<div class="ttc" id="aclasssimdjson_1_1dom_1_1document__stream_html"><div class="ttname"><a href="classsimdjson_1_1dom_1_1document__stream.html">simdjson::dom::document_stream</a></div><div class="ttdoc">A forward-only stream of documents.</div><div class="ttdef"><b>Definition</b> <a href="dom_2document__stream_8h_source.html#l00072">document_stream.h:72</a></div></div>
|
|
<div class="ttc" id="aclasssimdjson_1_1dom_1_1document__stream_html_a6c2a07e08213dc9a51754940942f9e69"><div class="ttname"><a href="classsimdjson_1_1dom_1_1document__stream.html#a6c2a07e08213dc9a51754940942f9e69">simdjson::dom::document_stream::truncated_bytes</a></div><div class="ttdeci">size_t truncated_bytes() const noexcept</div><div class="ttdoc">After iterating through the stream, this method returns the number of bytes that were not parsed at t...</div><div class="ttdef"><b>Definition</b> <a href="dom_2document__stream-inl_8h_source.html#l00266">document_stream-inl.h:266</a></div></div>
|
|
<div class="ttc" id="aclasssimdjson_1_1dom_1_1parser_html"><div class="ttname"><a href="classsimdjson_1_1dom_1_1parser.html">simdjson::dom::parser</a></div><div class="ttdoc">A persistent document parser.</div><div class="ttdef"><b>Definition</b> <a href="dom_2parser_8h_source.html#l00030">parser.h:30</a></div></div>
|
|
<div class="ttc" id="aclasssimdjson_1_1dom_1_1parser_html_a5c658556dd9e9396e9ce44ba4b01f2d1"><div class="ttname"><a href="classsimdjson_1_1dom_1_1parser.html#a5c658556dd9e9396e9ce44ba4b01f2d1">simdjson::dom::parser::parse_many</a></div><div class="ttdeci">simdjson_result< document_stream > parse_many(const uint8_t *buf, size_t len, size_t batch_size=dom::DEFAULT_BATCH_SIZE) noexcept</div><div class="ttdoc">Parse a buffer containing many JSON documents.</div><div class="ttdef"><b>Definition</b> <a href="dom_2parser-inl_8h_source.html#l00172">parser-inl.h:172</a></div></div>
|
|
</div><!-- fragment --><p>Importantly, you should only call <code>truncated_bytes()</code> after iterating through all of the documents since the stream cannot tell whether there are truncated documents at the very end when it may not have accessed that part of the data yet. </p>
|
|
</div></div><!-- contents -->
|
|
</div><!-- PageDoc -->
|
|
</div><!-- doc-content -->
|
|
<!-- start footer part -->
|
|
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
|
|
<ul>
|
|
<li class="footer">Generated by <a href="https://www.doxygen.org/index.html"><img class="footer" src="doxygen.svg" width="104" height="31" alt="doxygen"/></a> 1.9.8 </li>
|
|
</ul>
|
|
</div>
|
|
</body>
|
|
</html>
|