Using a worker instead of a thread per batch by lemire · Pull Request #920 · simdjson/simdjson

lemire · 2020-06-09T02:09:05Z

In the parse_many function, we have one thread doing the stage 1, while the main thread does stage 2. So if stage 1 and stage 2 take half the time, the parse_many could run at twice the speed. It is unlikely to do so. Still, we see benefits of about 40% due to threading.

To achieve this interleaving, we load the data in batches (blocks) of some size. In the current code (master), we create a new thread for each batch. Thread creation is expensive so our approach only works over sizeable batches. This PR improves things and makes parse_many faster when using small batches.

This fixes our parse_stream benchmark which is just busted.
This replaces the one-thread per batch routine by a worker object that reuses the same thread. In benchmarks, this allows us to get the same maximal speed, but with smaller processing blocks. It does not help much with larger blocks because the cost of the thread create gets amortized efficiently.

This PR makes parse_many beneficial over small datasets. It also makes us less dependent on the thread creation time.

Unfortunately, it is going to be difficult to say anything definitive in general. The cost of creating a thread varies widely depending on the OS. On some systems, it might be cheap, in others very expensive. It should be expected that the new code will depend less drastically on the performances of the underlying system, since we create juste one thread.

Fixes #529

lemire · 2020-06-09T20:16:38Z

(comment updated)

This is master...

$ ./benchmark/parse_stream bar.ndjson
parse_many: Speed per batch_size... from 10000 bytes to 10000000 bytes...
Batch Size	Gigabytes/second	Nb of documents parsed
10000		0.843				793000
109900		3.191				793000
209800		3.411				793000
309700		3.492				793000
409600		3.455				793000
509500		3.498				793000
609400		3.517				793000
709300		3.468				793000
809200		3.519				793000
909100		3.490				793000
1009000		3.524				793000
1108900		3.455				793000
1208800		3.503				793000
1308700		3.474				793000
1408600		3.533				793000
1508500		3.489				793000
1608400		3.520				793000
1708300		3.531				793000
1808200		3.532				793000
1908100		3.529				793000
2008000		3.418				793000
2107900		3.526				793000
2207800		3.461				793000
2307700		3.456				793000
2407600		3.519				793000
2507500		3.478				793000
2607400		3.521				793000
2707300		3.513				793000
2807200		3.529				793000
2907100		3.454				793000
3007000		3.487				793000
3106900		3.515				793000
3206800		3.519				793000
3306700		3.514				793000
3406600		3.482				793000
3506500		3.526				793000
3606400		3.425				793000
3706300		3.519				793000
3806200		3.507				793000
3906100		3.525				793000
4006000		3.494				793000
4105900		3.518				793000
4205800		3.514				793000
4305700		3.480				793000
4405600		3.502				793000
4505500		3.464				793000
4605400		3.470				793000
4705300		3.503				793000
4805200		3.500				793000
4905100		3.497				793000
5005000		3.497				793000
5104900		3.476				793000
5204800		3.411				793000
5304700		3.489				793000
5404600		3.462				793000
5504500		3.457				793000
5604400		3.501				793000
5704300		3.491				793000
5804200		3.485				793000
5904100		3.467				793000
6004000		3.479				793000
6103900		3.463				793000
6203800		3.456				793000
6303700		3.454				793000
6403600		3.460				793000
6503500		3.467				793000
6603400		3.471				793000
6703300		3.435				793000
6803200		3.449				793000
6903100		3.469				793000
7003000		3.462				793000
7102900		3.455				793000
7202800		3.441				793000
7302700		3.438				793000
7402600		3.462				793000
7502500		3.455				793000
7602400		3.421				793000
7702300		3.428				793000
7802200		3.457				793000
7902100		3.434				793000
8002000		3.454				793000
8101900		3.427				793000
8201800		3.457				793000
8301700		3.444				793000
8401600		3.416				793000
8501500		3.403				793000
8601400		3.386				793000
8701300		3.392				793000
8801200		3.403				793000
8901100		3.385				793000
9001000		3.404				793000
9100900		3.402				793000
9200800		3.376				793000
9300700		3.387				793000
9400600		3.273				793000
9500500		3.385				793000
9600400		3.367				793000
9700300		3.374				793000
9800200		3.383				793000
9900100		3.376				793000
10000000		3.309				793000
Starting speed test... Best of 5 iterations...
Seemingly optimal batch_size: 1408600...
Min:  0.079 bytes read: 277673000 Gigabytes/second: 3.505

with the following patch:

$ git diff
diff --git a/benchmark/parse_stream.cpp b/benchmark/parse_stream.cpp
index dee81c2..fb9ddbf 100755
--- a/benchmark/parse_stream.cpp
+++ b/benchmark/parse_stream.cpp
@@ -81,7 +81,7 @@ int main (int argc, char *argv[]){

                 auto start = std::chrono::steady_clock::now();
                 count = 0;
-                for (auto result : parser.parse_many(p, 4000000)) {
+                for (auto result : parser.parse_many(p, i)) {
                     error = result.error();
                     count++;
                 }
@@ -120,7 +120,7 @@ int main (int argc, char *argv[]){

             auto start = std::chrono::steady_clock::now();
             // TODO this includes allocation of the parser; is that intentional?
-            for (auto result : parser.parse_many(p, 4000000)) {
+            for (auto result : parser.parse_many(p, optimal_batch_size)) {
                 error = result.error();
             }
             auto end = std::chrono::steady_clock::now();

I verified that it has the threading code enabled.

This is this PR:

$ ./benchmark/parse_stream bar.ndjson
parse_many: Speed per batch_size... from 10000 bytes to 10000000 bytes...
Batch Size	Gigabytes/second	Nb of documents parsed
10000		1.661				793000
109900		3.496				793000
209800		3.582				793000
309700		3.559				793000
409600		3.537				793000
509500		3.493				793000
609400		3.536				793000
709300		3.515				793000
809200		3.523				793000
909100		3.518				793000
1009000		3.513				793000
1108900		3.494				793000
1208800		3.520				793000
1308700		3.512				793000
1408600		3.508				793000
1508500		3.507				793000
1608400		3.507				793000
1708300		3.510				793000
1808200		3.508				793000
1908100		3.509				793000
2008000		3.470				793000
2107900		3.510				793000
2207800		3.503				793000
2307700		3.496				793000
2407600		3.507				793000
2507500		3.496				793000
2607400		3.505				793000
2707300		3.490				793000
2807200		3.505				793000
2907100		3.452				793000
3007000		3.472				793000
3106900		3.504				793000
3206800		3.495				793000
3306700		3.484				793000
3406600		3.493				793000
3506500		3.492				793000
3606400		3.461				793000
3706300		3.508				793000
3806200		3.495				793000
3906100		3.465				793000
4006000		3.476				793000
4105900		3.483				793000
4205800		3.486				793000
4305700		3.485				793000
4405600		3.487				793000
4505500		3.467				793000
4605400		3.457				793000
4705300		3.477				793000
4805200		3.470				793000
4905100		3.466				793000
5005000		3.447				793000
5104900		3.468				793000
5204800		3.473				793000
5304700		3.464				793000
5404600		3.457				793000
5504500		3.468				793000
5604400		3.467				793000
5704300		3.442				793000
5804200		3.464				793000
5904100		3.443				793000
6004000		3.440				793000
6103900		3.438				793000
6203800		3.427				793000
6303700		3.432				793000
6403600		3.421				793000
6503500		3.418				793000
6603400		3.439				793000
6703300		3.408				793000
6803200		3.423				793000
6903100		3.394				793000
7003000		3.443				793000
7102900		3.438				793000
7202800		3.421				793000
7302700		3.391				793000
7402600		3.433				793000
7502500		3.422				793000
7602400		3.398				793000
7702300		3.427				793000
7802200		3.426				793000
7902100		3.418				793000
8002000		3.424				793000
8101900		3.416				793000
8201800		3.385				793000
8301700		3.429				793000
8401600		3.391				793000
8501500		3.388				793000
8601400		3.382				793000
8701300		3.372				793000
8801200		3.389				793000
8901100		3.387				793000
9001000		3.377				793000
9100900		3.385				793000
9200800		3.380				793000
9300700		3.372				793000
9400600		3.340				793000
9500500		3.365				793000
9600400		3.358				793000
9700300		3.305				793000
9800200		3.361				793000
9900100		3.363				793000
10000000		3.296				793000
Starting speed test... Best of 5 iterations...
Seemingly optimal batch_size: 209800...
Min:  0.079 bytes read: 277673000 Gigabytes/second: 3.530

The bar.ndjson is just a concatenated version of the amazon*ndjson file (so that it is sizeable).

We have a nice performance curve that peaks at just about the L2 cache size.

This is on one particular machine (GNU GCC 8, Skylake, Linux) but the point is that the code in master for parse_many is "bad" over small batches.

I think that the gist of the difference with the new code is that instead of using a thread per batch, we use a single thread. This helps tremendously. The new code reaches more or less the same best speed, but with 5x smaller batches. Evidently, this translates into lower memory usage, but importantly, in less stress on the cache.

Seemingly optimal batch_size: 1408600.
Seemingly optimal batch_size: 209800...

The downside is that the new code is more complicated and harder to get right.

jkeiser

I don't see anything particularly concerning, and acquiring resources less often seems like a positive thing in any case :) A few questions/comments in there.

lemire · 2020-06-09T22:54:31Z

BTW here are the speeds without threading...

buildnothread $ ./benchmark/parse_stream ../build/bar.ndjson 
parse_many: Speed per batch_size... from 10000 bytes to 10000000 bytes...
Batch Size      Gigabytes/second        Nb of documents parsed
10000           2.338                           793000
109900          2.436                           793000
209800          2.427                           793000
309700          2.442                           793000
409600          2.394                           793000
509500          2.442                           793000
609400          2.438                           793000
709300          2.424                           793000
809200          2.435                           793000
909100          2.437                           793000
1009000         2.410                           793000
1108900         2.417                           793000
1208800         2.428                           793000
1308700         2.413                           793000

and with threading...

$ ./benchmark/parse_stream ../build/bar.ndjson 
parse_many: Speed per batch_size... from 10000 bytes to 10000000 bytes...
Batch Size      Gigabytes/second        Nb of documents parsed
10000           1.205                           793000
109900          3.645                           793000
209800          3.702                           793000
309700          3.375                           793000
409600          3.374                           793000
509500          3.543                           793000
609400          3.402                           793000
709300          3.540                           793000
809200          3.361                           793000
909100          3.618                           793000
1009000         3.590                           793000
1108900         3.609                           793000
1208800         3.742                           793000
1308700         3.650                           793000
1408600         3.640                           793000

So we get a clean 50% boost in the speed when using a second thread. That's not new to this PR but it important as a motivation. We are not using a thread for fun... it definitively buys us performance. Going 1.5 x faster when using two cores is pretty much what you'd hope for in general.

jkeiser

Woo!

lemire · 2020-06-12T20:50:53Z

Ok. Let us merge.

jkeiser and others added 11 commits June 7, 2020 16:26

Fix fallback implementation

c86fb2e

base

8decf00

It works slowly

1198469

Ok.

f496f25

Merge branch 'master' into dlemire/worker

a52023f

More cleaning

bb6618c

Avoiding deadlocks.

8686471

More tweaking.

68c9d87

Moving the mutex

4b2dedd

More tuning.

0b5a7be

You should never need to use the assignment operator.

bc90296

lemire marked this pull request as ready for review June 9, 2020 20:36

lemire requested a review from jkeiser June 9, 2020 20:37

Simplifying the logic somewhat.

2aac68f

jkeiser reviewed Jun 9, 2020

View reviewed changes

Comment thread benchmark/parse_stream.cpp Outdated

jkeiser reviewed Jun 9, 2020

View reviewed changes

Comment thread include/simdjson/inline/document_stream.h Outdated

Cleaning it up.

ac9591e

jkeiser reviewed Jun 9, 2020

View reviewed changes

Comment thread include/simdjson/inline/document_stream.h Outdated

Fixing the issue with the non-moveable mutex.

33ffe30

jkeiser reviewed Jun 9, 2020

View reviewed changes

Comment thread include/simdjson/inline/document_stream.h Outdated

lemire commented Jun 9, 2020

View reviewed changes

Comment thread include/simdjson/dom/document_stream.h Outdated

jkeiser approved these changes Jun 9, 2020

View reviewed changes

lemire requested a review from jkeiser June 9, 2020 21:39

Daniel Lemire added 4 commits June 9, 2020 17:50

Tuning.

33876a3

More exception-less.

57c1736

Duh.

ba9c88b

This makes it much harder to start two threads.

552c06a

jkeiser approved these changes Jun 9, 2020

View reviewed changes

lemire mentioned this pull request Jun 10, 2020

Using a spinlock worker instead of a thread per batch #924

Closed

lemire added this to the 0.4 milestone Jun 10, 2020

lemire added 2 commits June 12, 2020 15:12

Better doc.

47ea67d

Extra tests.

0407f70

lemire merged commit 4dfbf98 into master Jun 12, 2020

lemire deleted the dlemire/worker branch June 12, 2020 20:51

Navigation Menu

Using a worker instead of a thread per batch - #920

Using a worker instead of a thread per batch#920
lemire merged 20 commits into
masterfrom
dlemire/worker

lemire commented Jun 9, 2020 •

edited

Loading

Uh oh!

lemire commented Jun 9, 2020 •

edited

Loading

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

jkeiser left a comment

Uh oh!

lemire commented Jun 9, 2020 •

edited

Loading

Uh oh!

jkeiser left a comment

Uh oh!

lemire commented Jun 12, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

Conversation

lemire commented Jun 9, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

lemire commented Jun 9, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

jkeiser left a comment

Choose a reason for hiding this comment

Uh oh!

lemire commented Jun 9, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jkeiser left a comment

Choose a reason for hiding this comment

Uh oh!

lemire commented Jun 12, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

lemire commented Jun 9, 2020 •

edited

Loading

lemire commented Jun 9, 2020 •

edited

Loading

lemire commented Jun 9, 2020 •

edited

Loading