8000 Compile constant tuples to constant objects immediately in the parser by dpgeorge · Pull Request #8504 · micropython/micropython · GitHub
[go: up one dir, main page]
Skip to content

Compile constant tuples to constant objects immediately in the parser #8504

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 17 commits into from
Apr 14, 2022
Merged

Compile constant tuples to constant objects immediately in the parser #8504

merged 17 commits into from
Apr 14, 2022

Conversation

dpgeorge
Copy link
Member
@dpgeorge dpgeorge commented Apr 8, 2022

This PR adds support to the parser to "compile" tuples that contain only constant elements directly to a tuple object. This makes it more efficient to use constant tuples because they no longer need to be created at runtime by the bytecode (or native code).

This PR implements the following:

  • the parser turns const tuples into tuple objects
  • mpy-cross can save tuples in .mpy files
  • support for importing .mpy files with tuples
  • support for freezing tuples from .mpy files
  • further freezing optimisations in mpy-tool.py to get frozen code size down further

Code size change for this entire PR is:

   bare-arm:    +0 +0.000% 
minimal x86:    -2 -0.001% 
   unix x64:  +184 +0.035% [incl -128(data)]
unix nanbox:  +612 +0.133% [incl -124(data)]
      stm32:  +320 +0.081% PYBV10
     cc3200:  +456 +0.248% 
    esp8266:  +216 +0.031% GENERIC
      esp32:  +260 +0.017% GENERIC[incl -200(data)]
        nrf:  +284 +0.155% pca10040
        rp2:  +344 +0.068% PICO
       samd:  +364 +0.259% ADAFRUIT_ITSYBITSY_M4_EXPRESS

This size change is broken down into the following:

  • support in parser to constify tuples: about +400 bytes on Cortex-M4 (gated by new option MICROPY_COMP_TUPLE_FOLDING)
  • support in persistent code loader (.mpy loader) to load tuples: about +80 bytes on Cortex-M4 (always enabled)
  • frozen code size changes (the remaining +ve or -ve diff)

Some ports like unix 64 have a decrease in frozen code size which mostly offsets the increase due to the new feature. Others like cc3200 don't have much/any frozen code and so see a bigger increase. Bare-arm/minimal have no change because they don't enable the feature.

The main benefits of this change are:

  • const tuples no longer need to be created at runtime
  • const tuples are now in ROM for frozen code

The downsides are:

  • increased code size in the parser
  • frozen const tuples (in frozen code) are somewhat larger (in ROM) that they were before when encoded in bytecode

Although it's not a clear win on all fronts, IMO I think this feature is well worth it, mainly because it saves RAM / reduces heap allocations. It also addresses the long-standing issue #722.

@dpgeorge dpgeorge added the py-core Relates to py/ directory in source label Apr 8, 2022
@dpgeorge
Copy link
Member Author
dpgeorge commented Apr 8, 2022

One thing to decide is if MICROPY_COMP_TUPLE_FOLDING should always be enabled. The benefit of having it always on is that one can guarantee that the use of const tuples will never allocate on the heap (when executing). Eg:

def f():
    for x in (1, 2, 3):
        print(x)

With this PR, the above function can run with the heap locked. Would be nice to guarantee such things unconditionally (ie for all ports/builds).

@dpgeorge
Copy link
Member Author
dpgeorge commented Apr 8, 2022

As an example, consider this code:

x0 = (1,)
x1 = (1, 2)
x2 = (1, 1 << 100)
x3 = (None, False, True, ...)
x4 = ("str", b"bytes")
x5 = ((),)
x6 = ((1,),)
x7 = ((1, 2),)
x8 = (1, "str", (), ("nested", 2, ((False, True), None, ...)))

Prior to this PR

The .mpy file looks like this:

00000000: 4d06 021f 0d04 3674 6573 742d 6672 7a6d  M.....6test-frzm  test-frzmpy/frozen_const.py
00000010: 7079 2f66 726f 7a65 6e5f 636f 6e73 742e  py/frozen_const. 
00000020: 7079 000f 0478 3000 0478 3100 0478 3200  py...x0..x1..x2.  <module> x0 x1 x2
00000030: 0478 3300 822f 0478 3400 0478 3500 0478  .x3../.x4..x5..x  x3 str x4 x5 x6
00000040: 3600 0478 3700 0c6e 6573 7465 6400 0478  6..x7..nested..x  x7 nested x8
00000050: 3800 691f 3132 3637 3635 3036 3030 3232  8.i.126765060022  1267650600228229401496703205376
00000060: 3832 3239 3430 3134 3936 3730 3332 3035  8229401496703205 
00000070: 3337 3665 6205 6279 7465 7300 6585 6838  376eb.bytes.e.h8  b'bytes' <module>
00000080: 1401 4025 2627 2928 2627 2881 2a01 1602  ..@%&')(&'(.*... 
00000090: 8182 2a02 1603 8123 002a 0216 0451 5052  ..*....#.*...QPR 
000000a0: 2301 2a04 1605 1006 2302 2a02 1607 2a00  #.*.....#.*...*. 
000000b0: 2a01 1608 812a 012a 0116 0981 822a 022a  *....*.*.....*.* 
000000c0: 0116 0a81 1006 2a00 100b 8250 522a 0251  ......*....PR*.Q 
000000d0: 2303 2a03 2a03 2a04 160c 5163            #.*.*.*...Qc 

mpy_source_file: test-frzmpy/frozen_const.mpy
source_file: test-frzmpy/frozen_const.py
header: 4d:06:02:1f
qstr_table[13]:
    test-frzmpy/frozen_const.py
    <module>
    x0
    x1
    x2
    x3
    str
    x4
    x5
    x6
    x7
    nested
    x8
obj_table: [1267650600228229401496703205376, Ellipsis, b'bytes', Ellipsis]
simple_name: <module>
  raw bytecode: ...
  prelude: (8, 0, 0, 0, 0, 0)
  args: []
  line info: 40:25:26:27:29:28:26:27:28
  81          LOAD_CONST_SMALL_INT 1 
  2a:01       BUILD_TUPLE 1
  16:02       STORE_NAME x0
  81          LOAD_CONST_SMALL_INT 1 
  82          LOAD_CONST_SMALL_INT 2 
  2a:02       BUILD_TUPLE 2
  16:03       STORE_NAME x1
  81          LOAD_CONST_SMALL_INT 1 
  23:00       LOAD_CONST_OBJ 1267650600228229401496703205376
  2a:02       BUILD_TUPLE 2
  16:04       STORE_NAME x2
  51          LOAD_CONST_NONE 
  50          LOAD_CONST_FALSE 
  52          LOAD_CONST_TRUE 
  23:01       LOAD_CONST_OBJ Ellipsis
  2a:04       BUILD_TUPLE 4
  16:05       STORE_NAME x3
  10:06       LOAD_CONST_STRING str
  23:02       LOAD_CONST_OBJ b'bytes'
  2a:02       BUILD_TUPLE 2
  16:07       STORE_NAME x4
  2a:00       BUILD_TUPLE 0
  2a:01       BUILD_TUPLE 1
  16:08       STORE_NAME x5
  81          LOAD_CONST_SMALL_INT 1 
  2a:01       BUILD_TUPLE 1
  2a:01       BUILD_TUPLE 1
  16:09       STORE_NAME x6
  81          LOAD_CONST_SMALL_INT 1 
  82          LOAD_CONST_SMALL_INT 2 
  2a:02       BUILD_TUPLE 2
  2a:01       BUILD_TUPLE 1
  16:0a       STORE_NAME x7
  81          LOAD_CONST_SMALL_INT 1 
  10:06       LOAD_CONST_STRING str
  2a:00       BUILD_TUPLE 0
  10:0b       LOAD_CONST_STRING nested
  82          LOAD_CONST_SMALL_INT 2 
  50          LOAD_CONST_FALSE 
  52          LOAD_CONST_TRUE 
  2a:02       BUILD_TUPLE 2
  51          LOAD_CONST_NONE 
  23:03       LOAD_CONST_OBJ Ellipsis
  2a:03       BUILD_TUPLE 3
  2a:03       BUILD_TUPLE 3
  2a:04       BUILD_TUPLE 4
  16:0c       STORE_NAME x8
  51          LOAD_CONST_NONE 
  63          RETURN_VALUE 
  children: []

After this PR

The .mpy file looks like this:

00000000: 4d06 021f 0b09 3674 6573 742d 6672 7a6d  M.....6test-frzm  test-frzmpy/frozen_const.py
00000010: 7079 2f66 726f 7a65 6e5f 636f 6e73 742e  py/frozen_const. 
00000020: 7079 000f 0478 3000 0478 3100 0478 3200  py...x0..x1..x2.  <module> x0 x1 x2
00000030: 0478 3300 0478 3400 0478 3500 0478 3600  .x3..x4..x5..x6.  x3 x4 x5 x6
00000040: 0478 3700 0478 3800 0a01 0701 310a 0207  .x7..x8.....1...  x7 x8 1
00000050: 0131 0701 320a 0207 0131 071f 3132 3637  .1..2....1..1267  1 2 1 1267650600228229401496703205376
00000060: 3635 3036 3030 3232 3832 3239 3430 3134  6506002282294014 
00000070: 3936 3730 3332 3035 3337 360a 0401 0203  96703205376..... 
00000080: 040a 0205 0373 7472 0006 0562 7974 6573  .....str...bytes  str b'bytes'
00000090: 000a 010a 000a 010a 0107 0131 0a01 0a02  ...........1....  1
000000a0: 0701 3107 0132 0a04 0701 3105 0373 7472  ..1..2....1..str  1 2 1 str
000000b0: 000a 000a 0305 066e 6573 7465 6400 0701  .......nested...  nested
000000c0: 320a 030a 0202 0301 0483 1000 1401 4024  2.............@$  2 <module>
000000d0: 2424 2424 2424 2423 0016 0223 0116 0323  $$$$$$$#...#...# 
000000e0: 0216 0423 0316 0523 0416 0623 05
8000
16 0723  ...#...#...#...# 
000000f0: 0616 0823 0716 0923 0816 0a51 63         ...#...#...Qc 

mpy_source_file: test-frzmpy/frozen_const.mpy
source_file: test-frzmpy/frozen_const.py
header: 4d:06:02:1f
qstr_table[11]:
    test-frzmpy/frozen_const.py
    <module>
    x0
    x1
    x2
    x3
    x4
    x5
    x6
    x7
    x8
obj_table: [(1,), (1, 2), (1, 1267650600228229401496703205376), (None, False, True, Ellipsis), ('str', b'bytes'), ((),), ((1,),), ((1, 2),), (1, 'str', (), ('nested', 2, ((False, True), None, Ellipsis)))]
simple_name: <module>
  raw bytecode: ...
  prelude: (1, 0, 0, 0, 0, 0)
  args: []
  line info: 40:24:24:24:24:24:24:24:24
  23:00       LOAD_CONST_OBJ (1,)
  16:02       STORE_NAME x0
  23:01       LOAD_CONST_OBJ (1, 2)
  16:03       STORE_NAME x1
  23:02       LOAD_CONST_OBJ (1, 1267650600228229401496703205376)
  16:04       STORE_NAME x2
  23:03       LOAD_CONST_OBJ (None, False, True, Ellipsis)
  16:05       STORE_NAME x3
  23:04       LOAD_CONST_OBJ ('str', b'bytes')
  16:06       STORE_NAME x4
  23:05       LOAD_CONST_OBJ ((),)
  16:07       STORE_NAME x5
  23:06       LOAD_CONST_OBJ ((1,),)
  16:08       STORE_NAME x6
  23:07       LOAD_CONST_OBJ ((1, 2),)
  16:09       STORE_NAME x7
  23:08       LOAD_CONST_OBJ (1, 'str', (), ('nested', 2, ((False, True), None, Ellipsis)))
  16:0a       STORE_NAME x8
  51          LOAD_CONST_NONE 
  63          RETURN_VALUE 
  children: []

You can see that all these constant tuples are truly constants in the bytecode.

@codecov-commenter
Copy link
codecov-commenter commented Apr 8, 2022 •
edited
Loading

Codecov Report

Merging #8504 (bf20df4) into master (66b5c4c) will decrease coverage by 0.02%.
The diff coverage is 95.50%.

❗ Current head bf20df4 differs from pull request most recent head 1c9d055. Consider uploading reports for the commit 1c9d055 to get more accurate results

@@            Coverage Diff             @@
##           master    #8504      +/-   ##
==========================================
- Coverage   98.25%   98.22%   -0.03%     
==========================================
  Files         154      154              
  Lines       20288    20368      +80     
==========================================
+ Hits        19933    20006      +73     
- Misses        355      362       +7
Impacted Files Coverage Δ
py/parse.c 98.52% <94.44%> (-0.63%) ⬇️
py/compile.c 99.76% <100.00%> (-0.18%) ⬇️
py/parse.h 100.00% <100.00%> (ø)
py/persistentcode.c 97.28% <100.00%> (+0.10%) ⬆️

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update 66b5c4c...1c9d055. Read the comment docs.

@dpgeorge
Copy link
Member Author
dpgeorge commented Apr 8, 2022

Performance change with this PR, on PYBv1.0:

diff of scores (higher is better)
N=100 M=100                pyb-baseline ->  pyb-patch         diff      diff% (error%)
bm_chaos.py                    362.99 ->     363.16 :      +0.17 =  +0.047% (+/-0.01%)
bm_fannkuch.py                  78.02 ->      78.03 :      +0.01 =  +0.013% (+/-0.00%)
bm_fft.py                     2554.43 ->    2550.81 :      -3.62 =  -0.142% (+/-0.00%)
bm_float.py                   5891.85 ->    5880.47 :     -11.38 =  -0.193% (+/-0.04%)
bm_hexiom.py                    46.90 ->      47.06 :      +0.16 =  +0.341% (+/-0.00%)
bm_nqueens.py                 4388.78 ->    4398.00 :      +9.22 =  +0.210% (+/-0.00%)
bm_pidigits.py                 643.86 ->     637.58 :      -6.28 =  -0.975% (+/-0.26%)
core_import_mpy_multi.py       554.40 ->     537.96 :     -16.44 =  -2.965% (+/-0.01%)
core_import_mpy_single.py       68.46 ->      67.08 :      -1.38 =  -2.016% (+/-0.04%)
core_qstr.py                    63.62 ->      63.33 :      -0.29 =  -0.456% (+/-0.00%)
core_yield_from.py             356.29 ->     355.53 :      -0.76 =  -0.213% (+/-0.00%)
misc_aes.py                    418.63 ->     418.87 :      +0.24 =  +0.057% (+/-0.01%)
misc_mandel.py                3425.28 ->    3444.72 :     +19.44 =  +0.568% (+/-0.01%)
misc_pystone.py               2270.54 ->    2259.17 :     -11.37 =  -0.501% (+/-0.00%)
misc_raytrace.py               372.30 ->     373.73 :      +1.43 =  +0.384% (+/-0.00%)
viper_call0.py                 572.83 ->     572.83 :      +0.00 =  +0.000% (+/-0.00%)
viper_call1a.py                546.71 ->     546.71 :      +0.00 =  +0.000% (+/-0.00%)
viper_call1b.py                433.96 ->     433.97 :      +0.01 =  +0.002% (+/-0.21%)
viper_call1c.py                438.71 ->     439.99 :      +1.28 =  +0.292% (+/-0.22%)
viper_call2a.py                532.85 ->     532.82 :      -0.03 =  -0.006% (+/-0.01%)
viper_call2b.py                375.48 ->     375.75 :      +0.27 =  +0.072% (+/-0.14%)

You can see that it's mostly unchanged. Except for the import tests which are a bit slower because now the tuple are are being created on import, rather than it runtime (and in these tests the code that creates/uses the tuples is never run).

@dpgeorge dpgeorge force-pushed the py-parse-const-tuple branch from bf20df4 to 1c9d055 Compare April 8, 2022 05:07
@stephanelsmith
Copy link
Contributor
stephanelsmith commented Apr 8, 2022 •
edited
Loading

This is awesome. I make heavy use of constant tuples, and this is great! Possible naive question, but are there implications for named tuples here or is that different?

@dpgeorge
Copy link
Member Author

Possible naive question, but are there implications for named tuples here or is that different?

Namedtuple's are not impacted, they are still as they were. Although, it will be more efficient to create them if you use a tuple of strings like nt = namedtuple('nt', ('a', 'b')), because that tuple of a, b will now be a const.

@stinos
Copy link
Contributor
stinos commented Apr 11, 2022

One thing to decide is if MICROPY_COMP_TUPLE_FOLDING should always be enabled. The benefit of having it always on is that one can guarantee that the use of const tuples will never allocate on the heap (when executing)

Looks worth having it always on, but I'd add it explicitly to the relevant doc section(s) so it gets widely known then

@dpgeorge
Copy link
Member Author

Looks worth having it always on,

It's currently enabled at MICROPY_CONFIG_ROM_LEVEL_CORE_FEATURES and above, which matches other optional features that are "core". So this will be enabled by default unless a port explicitly disables it, or chooses MICROPY_CONFIG_ROM_LEVEL_MINIMUM as its feature level.

The only other option is to make it unconditional (ie non optional). But I think it makes sense to keep it optional. After all, we've lived this long without it 😄

@dpgeorge dpgeorge force-pushed the py-parse-const-tuple branch 2 times, most recently from 07e743e to 3bb8dd8 Compare April 14, 2022 06:24
dpgeorge added 17 commits April 14, 2022 22:44
@dpgeorge
py/persistentcode: Define enum values for obj types instead of letters.
42d0bd2 
To keep the separate parts of the code that use these values in sync.  And
make it easier to add new object types.

Signed-off-by: Damien George <damien@micropython.org>
@dpgeorge
py/parse: Factor obj extract code to mp_parse_node_extract_const_object.
e52f14d 
Signed-off-by: Damien George <damien@micropython.org>
@dpgeorge
py/parse: Print const object value in mp_parse_node_print.
24bc1f6 
To give more information when printing the parse tree.

Signed-off-by: Damien George <damien@micropython.org>
@dpgeorge
py/parse: Add MICROPY_COMP_CONST_TUPLE option to build const tuples.
35c0cff 
This commit adds support to the parser so that tuples which contain only
constant elements (bool, int, str, bytes, etc) are immediately converted to
a tuple object.  This makes it more efficient to use tuples containing
constant data because they no longer need to be created at runtime by the
bytecode (or native code).

Furthermore, with this improvement constant tuples that are part of frozen
code are now able to be stored fully in ROM (this will be implemented in
later commits).

Code size is increased by about 400 bytes on Cortex-M4 platforms.

See related issue micropython#722.

Signed-off-by: Damien George <damien@micropython.org>
@dpgeorge
py/persistentcode: Support loading and saving tuples in .mpy files.
4ca9698 
Signed-off-by: Damien George <damien@micropython.org>
@dpgeorge
tools/mpy-tool.py: Support loading tuples from .mpy files.
2a075cc 
Signed-off-by: Damien George <damien@micropython.org>
@dpgeorge
tools/mpy-tool.py: Support freezing tuples and other consts.
68b3aee 
This also simplifies how constants are frozen.

Signed-off-by: Damien George <damien@micropython.org>
@dpgeorge
ports: Recompile bytecode tests now that .mpy format changed.
24894f9 
Signed-off-by: Damien George <damien@micropython.org>
@dpgeorge
tests/perf_bench: Update import tests for changes to .mpy consts.
999abbb 
Signed-off-by: Damien George <damien@micropython.org>
@dpgeorge
qemu-arm/test-frzmpy: Add test for freezing constant tuples.
abdc4ec 
Signed-off-by: Damien George <damien@micropython.org>
@dpgeorge
tools/mpy-tool.py: Optimise freezing of ints that can fit a small int.
9c8a563 
Signed-off-by: Damien George <damien@micropython.org>
@dpgeorge
tools/mpy-tool.py: Optimise freezing of empty str and bytes objects.
dfc6c62 
Signed-off-by: Damien George <damien@micropython.org>
@dpgeorge
tools/mpy-tool.py: Make global qstr list a dedicated class.
e647966 
Signed-off-by: Damien George <damien@micropython.org>
@dpgeorge
tools/mpy-tool.py: Optimise freezing of str when str data is a qstr.
40d431d 
Signed-off-by: Damien George <damien@micropython.org>
@dpgeorge
tools/mpy-tool.py: Intern more strings when freezing.
07f5260 
Signed-off-by: Damien George <damien@micropython.org>
@dpgeorge
tests/micropython: Add tests that const tuples don't use the heap.
865b61d 
Signed-off-by: Damien George <damien@micropython.org>
@dpgeorge
docs/reference: Update constrained docs now that tuples can be const.
9ab66b5 
Signed-off-by: Damien George <damien@micropython.org>
@dpgeorge dpgeorge force-pushed the py-parse-const-tuple branch from 3bb8dd8 to 9ab66b5 Compare April 14, 2022 14:20
@dpgeorge dpgeorge merged commit 9ab66b5 into micropython:master Apr 14, 2022
@dpgeorge dpgeorge deleted the py-parse-const-tuple branch April 14, 2022 14:47
RetiredWizard pushed a commit to RetiredWizard/micropython that referenced this pull request Oct 24, 2023
@dhalbert
Merge pull request micropython#8504 from pedro-mancano/main
4a931dc 
Update pt_BR.po
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
py-core Relates to py/ directory in source
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
4 participants
@dpgeorge @codecov-commenter @stephanelsmith @stinos
0