classification
Title: JSON loads performance improvement for long strings
Type: performance Stage: resolved
Components: Library (Lib) Versions: Python 3.9, Python 3.8
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: christian.heimes, ezio.melotti, inada.naoki, miss-islington, mpaolini, ncoghlan, pablogsal, rhettinger, serhiy.storchaka, steve.dower
Priority: normal Keywords: patch

Created on 2019-07-13 14:42 by mpaolini, last changed 2019-10-17 08:30 by inada.naoki. This issue is now closed.

Files
File name Uploaded Description Edit
events.svg mpaolini, 2019-07-13 14:42 spy-py flamegraph
Pull Requests
URL Status Linked Edit
PR 14752 merged mpaolini, 2019-07-13 15:05
PR 15022 merged miss-islington, 2019-07-30 14:18
PR 15134 merged inada.naoki, 2019-08-05 10:01
PR 15591 merged inada.naoki, 2019-08-29 09:53
Messages (30)
msg347832 - (view) Author: Marco Paolini (mpaolini) * Date: 2019-07-13 14:42
I analysed the performance of json.loads in one production workload we have.

Spy-py tells me the majority of time is spent into C json module (see events.svg)

Digging deeper, linux perf tells me hottest loop (where 20%+ of the time is spent) in _json.scanstring_unicode, in this loop:

189:   movzx  eax,BYTE PTR [rbp+rbx*1+0x0]
       mov    DWORD PTR [rsp+0x44],eax
       cmp    eax,0x22
       je     22f
       cmp    eax,0x5c
       je     22f
       test   r13d,r13d
       je     180
       cmp    eax,0x1f

which is related to this code in Modules/_json.c


        /* Find the end of the string or the next escape */
        Py_UCS4 c = 0;
        for (next = end; next < len; next++) {
            c = PyUnicode_READ(kind, buf, next);
            if (c == '"' || c == '\\') {
                break;
            }
            else if (strict && c <= 0x1f) {
                raise_errmsg("Invalid control character at", pystr, next);
                goto bail;
            }
        }

Two optimisations can be done:

1. remove the mov entirely. It is not needed inside the loop and it is only needed later, outside the loop to access the variable
2. switch around the strict check (in the second if) because strict defaults to 1 so it will likely pass the test, while the likelyness of finding an invalid character is lower

Running the pyperformance json_loads benchmark I get:

+------------+----------------------+-----------------------------+
| Benchmark  | vanilla-pyperf-pgo38 | patched-pyperf-pgo38        |
+============+======================+=============================+
| json_loads | 54.9 us              | 53.9 us: 1.02x faster (-2%) |
+------------+----------------------+-----------------------------+


A micro benchmark on a 1MB long json string gives better results:

python -m pyperf timeit -s "import json; x = json.dumps({'k': '1' * 2 ** 20})" "json.loads(x)"

+-----------+------------+-----------------------------+
| Benchmark | vanilla-1m | patched-1m                  |
+===========+============+=============================+
| timeit    | 2.62 ms    | 2.39 ms: 1.10x faster (-9%) |
+-----------+------------+-----------------------------+
msg347839 - (view) Author: Marco Paolini (mpaolini) * Date: 2019-07-13 15:12
Also on my real workload (loading 60GB jsonl file containing mostly strings) I measured a 10% improvement
msg347854 - (view) Author: Marco Paolini (mpaolini) * Date: 2019-07-13 20:57
Here's the real world example

$ ls -hs events-100k.json 
84M events-100k.json

+-----------+-------------------------+-----------------------------+
| Benchmark | vanilla-bpo-events-100k | patched-bpo-events-100k     |
+===========+=========================+=============================+
| timeit    | 985 ms                  | 871 ms: 1.13x faster (-12%) |
+-----------+-------------------------+-----------------------------+
msg348112 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-07-18 12:24
> 1. remove the mov entirely. It is not needed inside the loop and it is only needed later, outside the loop to access the variable

How can we lazy "mov    DWORD PTR [rsp+0x44],eax"?
msg348114 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-07-18 13:25
Some compilers produce inefficient code for PR-14752.
I wrote another patch which is friendly to more compilers.


$ perf record ./python -m pyperf timeit  -s "import json; x = json.dumps({'k': '1' * 2 ** 20})" "json.loads(x)"

# PR-14752

gcc-7 (Ubuntu 7.4.0-8ubuntu1) 7.4.0
Mean +- std dev: 1.11 ms +- 0.01 ms

```
       │     scanstring_unicode():
       │                 c = PyUnicode_READ(kind, buf, next);
 11.92 │270:   movzbl (%r15,%r8,1),%eax
       │                 if (c == '"' || c == '\\') {
 27.97 │       cmp    $0x22,%eax
       │                 c = PyUnicode_READ(kind, buf, next);
 29.22 │       mov    %eax,0x34(%rsp)
       │                 if (c == '"' || c == '\\') {
  0.46 │     ↑ je     ef
  0.02 │       cmp    $0x5c,%eax
       │     ↑ je     ef
       │                 if (c <= 0x1f && invalid < 0) {
       │       cmp    $0x1f,%eax
  0.00 │     ↓ ja     297
       │       test   %rdx,%rdx
       │       cmovs  %r8,%rdx
       │             for (next = end; next < len; next++) {
 29.49 │297:   add    $0x1,%r8
       │       cmp    %r8,%r12
  0.92 │     ↑ jne    270
```

gcc-8 (Ubuntu 8.3.0-6ubuntu1) 8.3.0
Mean +- std dev: 712 us +- 1 us
```
       │                 c = PyUnicode_READ(kind, buf, next);
       │188:   movzbl 0x0(%rbp,%rbx,1),%eax
       │       mov    %eax,0x34(%rsp)
       │                 if (c == '"' || c == '\\') {
       │       cmp    $0x22,%eax
       │     ↓ je     1d0
       │       nop
  0.00 │1a0:   cmp    $0x5c,%eax
       │     ↓ je     1d0
       │                 if (c <= 0x1f && invalid < 0) {
       │       cmp    $0x1f,%eax
 49.84 │     ↓ ja     1b1
       │       test   %rdx,%rdx
       │       cmovs  %rbx,%rdx
       │             for (next = end; next < len; next++) {
       │1b1:   add    $0x1,%rbx
  0.00 │       cmp    %rbx,%r15
       │     ↑ je     ff
       │                 c = PyUnicode_READ(kind, buf, next);
  0.61 │       movzbl 0x0(%rbp,%rbx,1),%eax
 49.53 │       mov    %eax,0x34(%rsp)
       │                 if (c == '"' || c == '\\') {
  0.01 │       cmp    $0x22,%eax
       │     ↑ jne    1a0
  0.00 │       nop
```

clang version 7.0.1-8 (tags/RELEASE_701/final)
Mean +- std dev: 951 us +- 1 us

```
       │                 c = PyUnicode_READ(kind, buf, next);
  9.76 │110:   movzbl (%r12,%r13,1),%eax
  9.47 │       mov    %eax,0xc(%rsp)
  8.85 │       cmp    $0x22,%eax
       │                 if (c == '"' || c == '\\') {
       │     ↓ je     170
  8.78 │       cmp    $0x5c,%al
       │     ↓ je     170
       │                 if (c <= 0x1f && invalid < 0) {
  9.16 │       cmp    $0x20,%al
  9.09 │       mov    %rdx,%rcx
  9.16 │       cmovb  %r13,%rcx
  9.00 │       test   %rdx,%rdx
  8.78 │       cmovs  %rcx,%rdx
       │             for (next = end; next < len; next++) {
  9.09 │       add    $0x1,%r13
       │       cmp    %r15,%r13
  8.86 │     ↑ jl     110
       │     ↓ jmp    170
       │       nop
```

clang version 8.0.0-3 (tags/RELEASE_800/final)
Mean +- std dev: 953 us +- 0 us

```
       │                 c = PyUnicode_READ(kind, buf, next);
 10.04 │100:   movzbl (%r15,%r14,1),%eax
  9.27 │       mov    %eax,0x4(%rsp)
  8.87 │       cmp    $0x22,%eax
       │                 if (c == '"' || c == '\\') {
       │     ↓ je     160
  8.78 │       cmp    $0x5c,%al
       │     ↓ je     160
       │                 if (c <= 0x1f && invalid < 0) {
  8.97 │       cmp    $0x20,%al
  8.97 │       mov    %rdx,%rcx
  8.89 │       cmovb  %r14,%rcx
  8.81 │       test   %rdx,%rdx
  9.14 │       cmovs  %rcx,%rdx
       │             for (next = end; next < len; next++) {
  9.25 │       add    $0x1,%r14
       │       cmp    %rdi,%r14
  8.99 │     ↑ jl     100
       │     ↓ jmp    160
       │       nop
```

# modified

```
        /* Find the end of the string or the next escape */
        Py_UCS4 c;
        {
            Py_UCS4 d = 0;
            for (next = end; next < len; next++) {
                d = PyUnicode_READ(kind, buf, next);
                if (d == '"' || d == '\\') {
                    break;
                }
                if (d <= 0x1f && strict) {
                    raise_errmsg("Invalid control character at", pystr, next);
                    goto bail;
                }
            }
            c = d;
        }
```


gcc-7 (Ubuntu 7.4.0-8ubuntu1) 7.4.0
Mean +- std dev: 708 us +- 1 us

```
       │                 for (next = end; next < len; next++) {
 20.29 │170:   add    $0x1,%rbx
  0.31 │       cmp    %rbx,%r12
       │     ↓ je     1b0
       │                     d = PyUnicode_READ(kind, buf, next);
 44.48 │179:   movzbl 0x0(%rbp,%rbx,1),%eax
       │                     if (d == '"' || d == '\\') {
  5.38 │       cmp    $0x22,%eax
       │     ↓ je     2c0
 23.82 │       cmp    $0x5c,%eax
       │     ↓ je     2c0
       │                     if (d <= 0x1f && strict) {
       │       cmp    $0x1f,%eax
  5.68 │     ↑ ja     170
       │       test   %r13d,%r13d
       │     ↑ jne    ed
```

gcc-8 (Ubuntu 8.3.0-6ubuntu1) 8.3.0
Mean +- std dev: 708 us +- 1 us
```
       │                 for (next = end; next < len; next++) {
  6.54 │170:   add    $0x1,%rbx
 19.25 │       cmp    %rbx,%r12
       │     ↓ jle    341
       │                     d = PyUnicode_READ(kind, buf, next);
 13.89 │17d:   movzbl 0x0(%rbp,%rbx,1),%eax
       │                     if (d == '"' || d == '\\') {
 34.26 │       cmp    $0x22,%eax
       │     ↓ je     1e8
  6.88 │       cmp    $0x5c,%eax
       │     ↓ je     1e8
       │                     if (d <= 0x1f && strict) {
       │       cmp    $0x1f,%eax
 19.17 │     ↑ ja     170
       │       test   %r14d,%r14d
       │     ↑ je     170
       │     ↑ jmpq   ed
```

clang version 7.0.1-8 (tags/RELEASE_701/final)
Mean +- std dev: 722 us +- 10 us

```
       │                     d = PyUnicode_READ(kind, buf, next);
 11.62 │ c0:┌─→movzbl (%r12,%r13,1),%eax
 11.99 │    │  cmp    $0x22,%eax
       │    │                if (d == '"' || d == '\\') {
       │    │↓ je     1f0
  9.61 │    │  cmp    $0x5c,%al
 22.56 │    │↓ je     1f0
       │    │                    break;
       │    │                }
       │    │                if (d <= 0x1f && strict) {
  8.94 │    │  cmp    $0x20,%al
       │    │↓ jb     b4a
       │    │            for (next = end; next < len; next++) {
 12.53 │    │  add    $0x1,%r13
       │    ├──cmp    %r15,%r13
 22.72 │    └──jl     c0
       │     ↓ jmpq   1f0
```


clang version 8.0.0-3 (tags/RELEASE_800/final)
Mean +- std dev: 707 us +- 1 us

```
       │                     d = PyUnicode_READ(kind, buf, next);
  0.01 │ b0:   movzbl (%r12,%r13,1),%eax
 23.84 │       cmp    $0x22,%eax
       │                     if (d == '"' || d == '\\') {
  0.00 │     ↓ je     1c0
  0.01 │       cmp    $0x5c,%al
       │     ↓ je     1c0
       │                         break;
       │                     }
       │                     if (d <= 0x1f && strict) {
 26.23 │       cmp    $0x20,%al
       │     ↓ jb     b1e
       │                 for (next = end; next < len; next++) {
       │       add    $0x1,%r13
       │       cmp    %r15,%r13
 49.91 │     ↑ jl     b0
       │     ↓ jmpq   1c0
```
msg348336 - (view) Author: Steve Dower (steve.dower) * (Python committer) Date: 2019-07-23 15:41
Marco has a newer patch with better performance that we came up with at the sprints, but apparently it hasn't been pushed yet. Hopefully he'll get that up soon and we can review it instead - the current PR wasn't as reliably good as initial testing suggested.
msg348707 - (view) Author: Marco Paolini (mpaolini) * Date: 2019-07-30 00:44
On gcc, running the tests above, the only change that is relevant for speedup is switching around the strict check. Removing the extra MOV related to the outer "c" variable is not significant (at least on gcc and the few tests I did)

Unfortunately I had to change the patch we did together during the sprint because it was breaking the strict check logic...

I updated my PR accordingly, kept only the bare minimum.
msg348709 - (view) Author: Marco Paolini (mpaolini) * Date: 2019-07-30 00:57
I am also working on a different patch that uses the "pcmpestri" SSE4 processor instruction, it looks like this for now.

While at it I realized there is (maybe) another potential speedup: avoiding the ucs4lib_find_max_char we do for each chunk of the string ( that entails scanning the string in memory one more time)... anyways that's another (much longer) story, probably for another issue?


```
diff --git a/Modules/_json.c b/Modules/_json.c
index 38beb6f50d..25b1cf4a99 100644
--- a/Modules/_json.c
+++ b/Modules/_json.c
@@ -400,6 +400,38 @@ _build_rval_index_tuple(PyObject *rval, Py_ssize_t idx) {
         Py_CLEAR(chunk); \
     }
 
+
+inline unsigned int
+_fast_search(const void *needle, unsigned int needle_len, const void *haystack, unsigned int haystack_len)
+{
+  unsigned int pos;
+  __asm__ __volatile__("movq (%1), %%xmm1;\n"
+                       "mov %2, %%eax;\n"
+                       "movq %3, %%r8;\n"
+                       "mov %4, %%edx;\n"
+                       ".intel_syntax noprefix;\n"
+                       "loop: pcmpestri xmm1, [r8], 0;\n" /* 0 = equal any */
+                       /* "pcmpestri %%mm1, (%%r8), $0;\n" /\* 0 = equal any *\/ */
+                       ".att_syntax prefix;\n"
+                       "cmp $15, %%ecx;\n"
+                       "jbe found;\n"
+                       "sub $16, %%edx;\n"
+                       "jnge notfound;\n"
+                       "add $16, %%r8;\n"
+                       "jmp loop;\n"
+                       "notfound: movl %4, %%ecx;\n"
+                       "jmp exit;\n"
+                       "found: mov %4, %%eax;\n"
+                       "sub %%edx, %%eax;\n"
+                       "add %%eax, %%ecx;\n"
+                       "exit: mov %%ecx, %0;\n"
+                       :"=m"(pos)
+                       :"r"(needle), "r"(needle_len), "r"(haystack), "r"(haystack_len)
+                       :"%eax", "%edx", "%ecx", "%r8", "%xmm1");
+  return pos;
+}
+
+
 static PyObject *
 scanstring_unicode(PyObject *pystr, Py_ssize_t end, int strict, Py_ssize_t *next_end_ptr)
 {
@@ -431,17 +463,26 @@ scanstring_unicode(PyObject *pystr, Py_ssize_t end, int strict, Py_ssize_t *next
         PyErr_SetString(PyExc_ValueError, "end is out of bounds");
         goto bail;
     }
+    char needle[2];
+    needle[0] = '"';
+    needle[1] = '\\';
     while (1) {
         /* Find the end of the string or the next escape */
         Py_UCS4 c = 0;
-        for (next = end; next < len; next++) {
+        if (kind == PyUnicode_1BYTE_KIND) {
+          next = _fast_search(needle, 2, buf+end, len-end) + end;
+          if (next < len)
             c = PyUnicode_READ(kind, buf, next);
-            if (c == '"' || c == '\\') {
-                break;
-            }
-            else if (strict && c <= 0x1f) {
-                raise_errmsg("Invalid control character at", pystr, next);
-                goto bail;
+        } else {
+            for (next = end; next < len; next++) {
+                c = PyUnicode_READ(kind, buf, next);
+                if (c == '"' || c == '\\') {
+                    break;
+                }
+                else if (strict && c <= 0x1f) {
+                    raise_errmsg("Invalid control character at", pystr, next);
+                    goto bail;
+                }
             }
         }
         if (!(c == '"' || c == '\\')) {
```
msg348710 - (view) Author: Marco Paolini (mpaolini) * Date: 2019-07-30 01:00
I forgot to mention, I was inspired by @christian.heimes 's talk at EuroPython 2019 https://ep2019.europython.eu/talks/es2pZ6C-introduction-to-low-level-profiling-and-tracing/ (thanks!)
msg348743 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2019-07-30 14:16
New changeset 8a758f5b99c5fc3fd32edeac049d7d4a4b7cc163 by Nick Coghlan (Marco Paolini) in branch 'master':
bpo-37587: Make json.loads faster for long strings (GH-14752)
https://github.com/python/cpython/commit/8a758f5b99c5fc3fd32edeac049d7d4a4b7cc163
msg348744 - (view) Author: Nick Coghlan (ncoghlan) * (Python committer) Date: 2019-07-30 14:22
I went ahead and merged the minimal PR and flagged it for backporting to 3.8 - it's an obviously beneficial change, that clearly does less work on each pass through the loop.

Even if you are doing non-strict parsing of a string that consists entirely of invalid characters, you'll get the same level of performance that the previous code offered for all strict parsing.
msg348745 - (view) Author: miss-islington (miss-islington) Date: 2019-07-30 14:37
New changeset 9265a877426af4fa5c44cc8482e0198806889350 by Miss Islington (bot) in branch '3.8':
bpo-37587: Make json.loads faster for long strings (GH-14752)
https://github.com/python/cpython/commit/9265a877426af4fa5c44cc8482e0198806889350
msg348746 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-07-30 14:45
Wait... there is no benchmark for the "minimum change".

I tested 4 compilers, and provide much better patch in https://bugs.python.org/issue37587#msg348114
msg348748 - (view) Author: Steve Dower (steve.dower) * (Python committer) Date: 2019-07-30 15:18
While you're testing patches, can you try this version too?

        Py_UCS4 c = 0, minc = 0x20;
        for (next = end; next < len; next++) {
            c = PyUnicode_READ(kind, buf, next);
            if (c == '"' || c == '\\') {
                break;
            }
            minc = c < minc ? c : minc;
        }
        if (strict && minc <= 0x1f) {
            raise_errmsg("Invalid control character at", pystr, next);
            goto bail;
        }

When we tried this, the conditional expression became a "cmovl" operator which removed 3-4 branches from within the loop entirely, and it was 18% better than the baseline (which has now moved...)
msg348749 - (view) Author: Steve Dower (steve.dower) * (Python committer) Date: 2019-07-30 15:20
Oh, we also need to capture "next"... but then again, since the success case is far more common, I'd be okay with scanning again to find it.
msg348750 - (view) Author: Marco Paolini (mpaolini) * Date: 2019-07-30 15:32
@steve.dower yes, that's what made me discard that experiment we did during the sprint.

Ok will test your new patch soon
msg348751 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-07-30 15:35
Since scope of "c" is very wide, and there is even `&c` in the scope, compiler stores the `c` to stack every time on:

  c = PyUnicode_READ(kind, buf, next);

That is the bottleneck.  `if (strict && ...)` is not the bottleneck.

My patch used a new variable with tight scope so compiler can bypass store it to the stack.
msg348753 - (view) Author: Steve Dower (steve.dower) * (Python committer) Date: 2019-07-30 15:43
> compiler stores the `c` to stack every time

The disassembly we looked at didn't do this, so it may just be certain compilers. Perhaps we can actually use the register keyword to help them out? :)


Here's a slightly altered one that doesn't require rescanning for the sake of the error message:

        Py_UCS4 c = 0, minc = strict ? 0x20 : 0x00;
        for (next = end; next < len; next++) {
            c = PyUnicode_READ(kind, buf, next);
            if (c == '"' || c == '\\' || c < minc) {
                break;
            }
        }
        if (c < minc) {
            raise_errmsg("Invalid control character at", pystr, next);
            goto bail;
        }
msg348758 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-07-30 16:46
I tested before, after, Steve's patch, and my patch with gcc 8.3.0 and PGO+LTO.
https://gist.github.com/methane/f6077bd1b0b04d40a9c790d9ed670a44#file-gcc-8-3-0-pgo-md

Surprisingly, there is no difference.  Even my patch didn't help register allocation when PGO is enabled.

I will run same test with other compilers & PGO (enabled|disabled).
msg348759 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-07-30 16:52
I'm sorry, I was wrong.  PGO did very nice job on all cases.
gcc allocates `c` to register in the hot loop.
msg348762 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-07-30 17:30
This issue is very compiler sensitive.
Please don't report performance without compiler version and PGO option.

Now I'm facing strange behavior. pyperf reports slower time (1ms) for PGO builds, although disasm looks good.
But it's 2:30am already...  Please wait for a few days.
msg349040 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-08-05 09:53
I tried without PGO and confirmed performance improved on GCC 7.2.0.
No change on other compiler versions.


$ ./python -m pyperf timeit  -s "import json; x = json.dumps({'k': '1' * 2 ** 20})" "json.loads(x)"

old: 9211e2
new: 8a758f

gcc (Ubuntu 8.3.0-6ubuntu1) 8.3.0

old: Mean +- std dev: 721 us +- 0 us
new: Mean +- std dev: 722 us +- 0 us


gcc-7 (Ubuntu 7.4.0-8ubuntu1) 7.4.0

old: Mean +- std dev: 1.03 ms +- 0.00 ms
new: Mean +- std dev: 726 us +- 0 us


clang version 7.0.1-8 (tags/RELEASE_701/final)

old: Mean +- std dev: 721 us +- 1 us
new: Mean +- std dev: 722 us +- 0 us


clang version 8.0.0-3 (tags/RELEASE_800/final)

old: Mean +- std dev: 721 us +- 0 us
new: Mean +- std dev: 721 us +- 1 us
msg349042 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-08-05 10:02
And I confirmed performance improvement by my patch (GH-15134) on all of 4 compilers.

$ ./python -m pyperf timeit  -s "import json; x = json.dumps({'k': '1' * 2 ** 20})" "json.loads(x)"

old:  9211e2
new:  8a758f
opt2: 284e47

gcc (Ubuntu 8.3.0-6ubuntu1) 8.3.0

old:  Mean +- std dev: 721 us +- 0 us
new:  Mean +- std dev: 722 us +- 0 us
opt2: Mean +- std dev: 715 us +- 1 us


gcc-7 (Ubuntu 7.4.0-8ubuntu1) 7.4.0

old:  Mean +- std dev: 1.03 ms +- 0.00 ms
new:  Mean +- std dev: 726 us +- 0 us
opt2: Mean +- std dev: 715 us +- 0 us


clang version 7.0.1-8 (tags/RELEASE_701/final)

old:  Mean +- std dev: 721 us +- 1 us
new:  Mean +- std dev: 722 us +- 0 us
opt2: Mean +- std dev: 715 us +- 1 us


clang version 8.0.0-3 (tags/RELEASE_800/final)

old:  Mean +- std dev: 721 us +- 0 us
new:  Mean +- std dev: 721 us +- 1 us
opt2: Mean +- std dev: 715 us +- 0 us
msg349226 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-08-08 08:57
New changeset 2a570af12ac5e4ac5575a68f8739b31c24d01367 by Inada Naoki in branch 'master':
bpo-37587: optimize json.loads (GH-15134)
https://github.com/python/cpython/commit/2a570af12ac5e4ac5575a68f8739b31c24d01367
msg349823 - (view) Author: Marco Paolini (mpaolini) * Date: 2019-08-15 20:15
I also confirm Inada's patch further improves performance!

All my previous benchmarks were done with gcc and PGO optimizations performed only with test_json task... maybe this explains the weird results?

I tested the performance of new master 69f37bcb28d7cd78255828029f895958b5baf6ff with *all* PGO task reverting my original patch:

iff --git a/Modules/_json.c b/Modules/_json.c
index 112903ea57..9b63167276 100644
--- a/Modules/_json.c
+++ b/Modules/_json.c
@@ -442,7 +442,7 @@ scanstring_unicode(PyObject *pystr, Py_ssize_t end, int strict, Py_ssize_t *next
                 if (d == '"' || d == '\\') {
                     break;
                 }
-                if (d <= 0x1f && strict) {
+                if (strict && d <= 0x1f) {
                     raise_errmsg("Invalid control character at", pystr, next);
                     goto bail;
                 }

... and surprise...

Mean +- std dev: [69f37bcb28d7cd78255828029f895958b5baf6ff] 5.29 us +- 0.07 us -> [69f37bcb28d7cd78255828029f895958b5baf6ff-patched] 5.11 us +- 0.03 us: 1.04x faster (-4%)

should we revert my original patch entirely now? Or am I missing something?
msg349825 - (view) Author: Marco Paolini (mpaolini) * Date: 2019-08-15 20:41
also worth noting escape sequences for non-ascii characters are slower, even when encoded length is the same.

python -m pyperf timeit -s 'import json;' -s  'c = "€"; s = json.dumps(c * (2**10 // len(json.dumps(c)) - 2))' 'json.loads(s)' -o nonascii2k.json

python -m pyperf timeit -s 'import json;' -s  'c = "a"; s = json.dumps(c * (2**10 // len(json.dumps(c)) - 2))' 'json.loads(s)' -o ascii2k.json

Mean +- std dev: [ascii2k] 2.59 us +- 0.04 us -> [nonascii2k] 9.98 us +- 0.12 us: 3.86x slower (+286%)
msg349826 - (view) Author: Marco Paolini (mpaolini) * Date: 2019-08-15 20:46
ops sorry here's the right commands

python -m pyperf timeit -s 'import json;' -s  'c = "a"; s = json.dumps(c * (2**10 // (len(json.dumps(c)) - 2)))' 'json.loads(s)' -o ascii2k.json
python -m pyperf timeit -s 'import json;' -s  'c = "€"; s = json.dumps(c * (2**10 // (len(json.dumps(c)) - 2)))' 'json.loads(s)' -o nonascii2k.json

Mean +- std dev: [ascii2k] 3.69 us +- 0.05 us -> [nonascii2k] 12.4 us +- 0.1 us: 3.35x slower (+235%)
msg349830 - (view) Author: Marco Paolini (mpaolini) * Date: 2019-08-15 21:34
ujson (https://github.com/esnme/ultrajson) instead is faster when decoding non-ascii in the same example above, so it is likely there is room for improvement...
msg350761 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-08-29 09:55
@mpaolini  I don't have enough time in these weeks.  Would you try PR-15591?

I confirmed up to 4x speedup.  But I'm afraid about there is performance regression in simple cases.
msg354833 - (view) Author: Inada Naoki (inada.naoki) * (Python committer) Date: 2019-10-17 07:12
New changeset 9c11029bb41caab5576f354fbf808a5e91325bb0 by Inada Naoki in branch 'master':
bpo-37587: json: Use _PyUnicodeWriter when scanning string. (GH-15591)
https://github.com/python/cpython/commit/9c11029bb41caab5576f354fbf808a5e91325bb0
History
Date User Action Args
2019-10-17 08:30:11inada.naokisetstatus: open -> closed
resolution: fixed
stage: patch review -> resolved
2019-10-17 07:12:47inada.naokisetmessages: + msg354833
2019-08-29 09:55:38inada.naokisetmessages: + msg350761
2019-08-29 09:53:21inada.naokisetpull_requests: + pull_request15267
2019-08-15 21:34:36mpaolinisetmessages: + msg349830
2019-08-15 20:46:05mpaolinisetmessages: + msg349826
2019-08-15 20:41:17mpaolinisetmessages: + msg349825
2019-08-15 20:15:09mpaolinisetmessages: + msg349823
2019-08-08 08:57:13inada.naokisetmessages: + msg349226
2019-08-05 10:02:50inada.naokisetmessages: + msg349042
2019-08-05 10:01:23inada.naokisetpull_requests: + pull_request14873
2019-08-05 09:53:59inada.naokisetmessages: + msg349040
2019-07-30 17:30:09inada.naokisetmessages: + msg348762
2019-07-30 16:52:29inada.naokisetmessages: + msg348759
2019-07-30 16:46:33inada.naokisetmessages: + msg348758
2019-07-30 15:43:52steve.dowersetmessages: + msg348753
2019-07-30 15:35:10inada.naokisetmessages: + msg348751
2019-07-30 15:32:47mpaolinisetmessages: + msg348750
2019-07-30 15:20:05steve.dowersetmessages: + msg348749
2019-07-30 15:18:50steve.dowersetmessages: + msg348748
2019-07-30 14:45:37inada.naokisetmessages: + msg348746
2019-07-30 14:37:50miss-islingtonsetnosy: + miss-islington
messages: + msg348745
2019-07-30 14:22:29ncoghlansetmessages: + msg348744
2019-07-30 14:18:19miss-islingtonsetpull_requests: + pull_request14783
2019-07-30 14:16:49ncoghlansetnosy: + ncoghlan
messages: + msg348743
2019-07-30 01:00:46mpaolinisetmessages: + msg348710
2019-07-30 00:57:15mpaolinisetmessages: + msg348709
2019-07-30 00:44:20mpaolinisetmessages: + msg348707
2019-07-23 15:41:12steve.dowersetmessages: + msg348336
versions: + Python 3.8
2019-07-19 05:47:56inada.naokisetversions: - Python 3.6, Python 3.7, Python 3.8
2019-07-18 13:25:51inada.naokisetmessages: + msg348114
2019-07-18 12:24:34inada.naokisetnosy: + inada.naoki
messages: + msg348112
2019-07-14 07:35:24steve.dowersetnosy: + steve.dower
2019-07-13 20:57:24mpaolinisetmessages: + msg347854
2019-07-13 15:12:53mpaolinisetmessages: + msg347839
2019-07-13 15:08:29mpaolinisetnosy: + rhettinger, ezio.melotti
2019-07-13 15:05:22mpaolinisetkeywords: + patch
stage: patch review
pull_requests: + pull_request14547
2019-07-13 14:50:56xtreaksetnosy: + serhiy.storchaka
2019-07-13 14:42:02mpaolinicreate