Why qstr is passed by handle (instead of pointer)? #4
Comments
|
In an early version, qstr's were exactly their pointer. The main reason to make them an index into a table was to make them smaller. In the byte code, constants (like qstr's) are encoded with a variable width encoding (like UTF-8). Thus, smaller numbers lead to smaller byte code. Pointers are not small, they have high-bits set. |
|
Another place where I see that pointers won't fit is parse.h/mp_parse_node_t, which uses 4 tag bits. But well, what we can do about this is to use pointers when possible, and when not, use handles. For example, with qstr pools, handle lookup is no longer O(1). Yeah, with exponential pool size growth it's O(log N), but exponential growth is greedy on memory, and why look up at all, if we can use pointer right away? |
I was just pondering this exact point. I think it would be better to have qstrs as direct pointers to their data (their hash, len and bytes). But how to compress them in the byte code? CPython uses a table of strings, and byte codes index that table. |
|
Well, first of all, static qstr table should be much bigger than it is now - include builtin functions/objects/their methods, etc. For other strings, compiler will intern them unconditionally so far, so you'll get qstr index, and can store it varlen in bytecode. On interpreting bytecode, just applies qstr_str() immediately and store ptr in all structures. Do I miss some additional issues? |
That's going to have a big performance penalty. Eg LOAD_ATTR, you would need to convert qstr_idx to qstr_ptr, requiring a very complex operation to search the qstr pools. Then you do a dictionary lookup to find the attribute you wanted (insignificant compared with qstr_str call). This would happen each time the byte code was executed. |
How is it very complex? And how dictionary lookup is insignificant? Exponential pool look up will have worst-case complexity O(log N) (N - total number of items). For dictionary, worst case is O(N). Realistically, 5-10 backtracks thru pools will be enough (well, it should improve once we make not all string intern), once pool is found, it's O(1). Dictionary of some class can easily have 20 attributes ;-), and due to algorithm used, even on average you'll need to loop thru 1/2 of items. But all in all, if it's clear that some operation requires speed, we should use ptr (even in bytecode I mean). (And as it can't be that clearly really, having configurable even better ;-) ). |
|
Ok, I still fill slight intuitive dissatisfaction with this extra indirection design, but it's pretty deep into interpreter now, and any resolution should take #222 needs into account (and that either means sticking with handles, or have different format for persistable and loaded bytecode, which is bloat). So, closing for now. |
|
I don't mind leaving this open, since it reminds me to think deeply about the problem :) |
|
Ok, let's keep open, but #386 would be still more important to resolve sooner. |
*: Heading to 2015-07-31
This prevents corrupting previous functional objects by stealing their pins out from under them. It prevents this by ensuring that pins are in default state before claiming them. It also verifies pins are released correctly and reset on soft reset. Fixes #4, instantiating a second class will fail. Fixes micropython#29, pins are now reset too.
Make function names for width()/height() consistent
|
I don't see a reason to keep this open anymore. Having small bytecode size (and hence compressed/indexed qstrs) is much more important than optimising for speed. And there are places now in the code which assume only 16-bit of storage for qstrs (especially when persistent bytecode is enabled). |
|
Ack. I try to to old ticket cleanup myself from time to time, and wanted to close these my "green naive" tickets too, but wanted to re-read them first to see what direction we went since then, but that doesn't happen for months, so just closing them sounds good. |
Allow litex leds to build without cas
Update README.md, Update lv_bindings module
merge from upstream
merge from adafruit
It was incorrect to NULL out the pointer to our heap allocated buffer in `reset`, because subsequent to framebuffer_reset, but while the heap was still active, we could call `get_bufinfo` again, leading to a fresh allocation on the heap that is about to be destroyed. Typical stack trace: ``` #1 0x0006c368 in sharpdisplay_framebuffer_get_bufinfo #2 0x0006ad6e in _refresh_display #3 0x0006b168 in framebufferio_framebufferdisplay_background micropython#4 0x00069d22 in displayio_background micropython#5 0x00045496 in supervisor_background_tasks micropython#6 0x000446e8 in background_callback_run_all micropython#7 0x00045546 in supervisor_run_background_tasks_if_tick micropython#8 0x0005b042 in common_hal_neopixel_write micropython#9 0x00044c4c in clear_temp_status micropython#10 0x000497de in spi_flash_flush_keep_cache micropython#11 0x00049a66 in supervisor_external_flash_flush micropython#12 0x00044b22 in supervisor_flash_flush micropython#13 0x0004490e in filesystem_flush micropython#14 0x00043e18 in cleanup_after_vm micropython#15 0x0004414c in run_repl micropython#16 0x000441ce in main ``` When this happened -- which was inconsistent -- the display would keep some heap allocation across reset which is exactly what we need to avoid. NULLing the pointer in reconstruct follows what RGBMatrix does, and that code is a bit more battle-tested anyway. If I had a motivation for structuring the SharpMemory code differently, I can no longer recall it. Testing performed: Ran my complicated calculator program over multiple iterations without observing signs of heap corruption. Closes: micropython#3473
Merging 11/11 changes
asan considers that memcmp(p, q, N) is permitted to access N bytes at each
of p and q, even for values of p and q that have a difference earlier.
Accessing additional values is frequently done in practice, reading 4 or
more bytes from each input at a time for efficiency, so when completing
"non_exist<TAB>" in the repl, this causes a diagnostic:
==16938==ERROR: AddressSanitizer: global-buffer-overflow on
address 0x555555cd8dc8 at pc 0x7ffff726457b bp 0x7fffffffda20 sp 0x7fff
READ of size 9 at 0x555555cd8dc8 thread T0
#0 0x7ffff726457a (/usr/lib/x86_64-linux-gnu/libasan.so.5+0xb857a)
#1 0x555555b0e82a in mp_repl_autocomplete ../../py/repl.c:301
#2 0x555555c89585 in readline_process_char ../../lib/mp-readline/re
#3 0x555555c8ac6e in readline ../../lib/mp-readline/readline.c:513
#4 0x555555b8dcbd in do_repl /home/jepler/src/micropython/ports/uni
#5 0x555555b90859 in main_ /home/jepler/src/micropython/ports/unix/
#6 0x555555b90a3a in main /home/jepler/src/micropython/ports/unix/m
#7 0x7ffff619a09a in __libc_start_main ../csu/libc-start.c:308
#8 0x55555595fd69 in _start (/home/jepler/src/micropython/ports/uni
0x555555cd8dc8 is located 0 bytes to the right of global variable
'import_str' defined in '../../py/repl.c:285:23' (0x555555cd8dc0) of
size 8
'import_str' is ascii string 'import '
Signed-off-by: Jeff Epler <jepler@gmail.com>
asan considers that memcmp(p, q, N) is permitted to access N bytes at each
of p and q, even for values of p and q that have a difference earlier.
Accessing additional values is frequently done in practice, reading 4 or
more bytes from each input at a time for efficiency, so when completing
"non_exist<TAB>" in the repl, this causes a diagnostic:
==16938==ERROR: AddressSanitizer: global-buffer-overflow on
address 0x555555cd8dc8 at pc 0x7ffff726457b bp 0x7fffffffda20 sp 0x7fff
READ of size 9 at 0x555555cd8dc8 thread T0
#0 0x7ffff726457a (/usr/lib/x86_64-linux-gnu/libasan.so.5+0xb857a)
micropython#1 0x555555b0e82a in mp_repl_autocomplete ../../py/repl.c:301
micropython#2 0x555555c89585 in readline_process_char ../../lib/mp-readline/re
micropython#3 0x555555c8ac6e in readline ../../lib/mp-readline/readline.c:513
micropython#4 0x555555b8dcbd in do_repl /home/jepler/src/micropython/ports/uni
micropython#5 0x555555b90859 in main_ /home/jepler/src/micropython/ports/unix/
micropython#6 0x555555b90a3a in main /home/jepler/src/micropython/ports/unix/m
micropython#7 0x7ffff619a09a in __libc_start_main ../csu/libc-start.c:308
micropython#8 0x55555595fd69 in _start (/home/jepler/src/micropython/ports/uni
0x555555cd8dc8 is located 0 bytes to the right of global variable
'import_str' defined in '../../py/repl.c:285:23' (0x555555cd8dc0) of
size 8
'import_str' is ascii string 'import '
Signed-off-by: Jeff Epler <jepler@gmail.com>
mimxrt/1170evk: Initial upgrade of linker scripts and SDK - DOES NOT COMPILE.
* [Add Ameba port] Add Ameba specific port src and dependency [Update linker] Update linker to resolve RAM shortage * [Add ignored files] add archive lib and pre-built binaries * [Multiple updates] Add ameba sdk as submodule, add postbild tool src, add amebad_tool, update makefile, relocate linker script * [Update Makefile] Update makefile to be compatible with all OS when extracting embedded toolchain * [Support and API] Add support for AMB23 RTL8722DM and update peripheral APIs - Add hardware support for AMB23 RTL8722DM (Previously known as RTL8722DM_MINI) - Update peripheral API for standardization - - timer - - ADC - - PWM(WIP) - Add Flash module to the port * [Pin/GPIO] Standardize Pin module API - Add new API and constants - Fix a bug found with REPL under readline.c * [PWM] Standardize PWM module API - Add machine_pwm.c from extmod as the micropython pwm binding - Add and update API to work like RP2 port * [UART] Standardize UART module API - Add new API and removing some existing ones - Update API to comply with RP2 style * [I2C] Standardize I2C module API - Re-structure the I2C module to make use of the generic I2C MicroPython binding - Add, remove and update API with be like RP2 style * [SPI] Standardize SPI module API - Re-structure the SPI module to make use of the MicroPython generic bindings - Add, remove and update API to be like RP2 style * [Readme] Update Readme to include more details - Update README.md to include more details - minor updates to i2c and timer module API * [README] Update README.md to provide more info about AMB23 * Pre Release Ameba MicroPython V1.1.0 - v2 - Update SDK and libs - Optimize memory usage and eliminate dependency on PSRAM Co-authored-by: ambiot <ambiot123@gmail.com>
* [Add Ameba port] Add Ameba specific port src and dependency [Update linker] Update linker to resolve RAM shortage * [Add ignored files] add archive lib and pre-built binaries * [Multiple updates] Add ameba sdk as submodule, add postbild tool src, add amebad_tool, update makefile, relocate linker script * [Update Makefile] Update makefile to be compatible with all OS when extracting embedded toolchain * [Support and API] Add support for AMB23 RTL8722DM and update peripheral APIs - Add hardware support for AMB23 RTL8722DM (Previously known as RTL8722DM_MINI) - Update peripheral API for standardization - - timer - - ADC - - PWM(WIP) - Add Flash module to the port * [Pin/GPIO] Standardize Pin module API - Add new API and constants - Fix a bug found with REPL under readline.c * [PWM] Standardize PWM module API - Add machine_pwm.c from extmod as the micropython pwm binding - Add and update API to work like RP2 port * [UART] Standardize UART module API - Add new API and removing some existing ones - Update API to comply with RP2 style * [I2C] Standardize I2C module API - Re-structure the I2C module to make use of the generic I2C MicroPython binding - Add, remove and update API with be like RP2 style * [SPI] Standardize SPI module API - Re-structure the SPI module to make use of the MicroPython generic bindings - Add, remove and update API to be like RP2 style * [Readme] Update Readme to include more details - Update README.md to include more details - minor updates to i2c and timer module API * [README] Update README.md to provide more info about AMB23 * Pre Release Ameba MicroPython V1.1.0 - v2 - Update SDK and libs - Optimize memory usage and eliminate dependency on PSRAM Co-authored-by: ambiot <ambiot123@gmail.com>
Pull in the latest main branch from adafruit
* [Add Ameba port] Add Ameba specific port src and dependency [Update linker] Update linker to resolve RAM shortage * [Add ignored files] add archive lib and pre-built binaries * [Multiple updates] Add ameba sdk as submodule, add postbild tool src, add amebad_tool, update makefile, relocate linker script * [Update Makefile] Update makefile to be compatible with all OS when extracting embedded toolchain * [Support and API] Add support for AMB23 RTL8722DM and update peripheral APIs - Add hardware support for AMB23 RTL8722DM (Previously known as RTL8722DM_MINI) - Update peripheral API for standardization - - timer - - ADC - - PWM(WIP) - Add Flash module to the port * [Pin/GPIO] Standardize Pin module API - Add new API and constants - Fix a bug found with REPL under readline.c * [PWM] Standardize PWM module API - Add machine_pwm.c from extmod as the micropython pwm binding - Add and update API to work like RP2 port * [UART] Standardize UART module API - Add new API and removing some existing ones - Update API to comply with RP2 style * [I2C] Standardize I2C module API - Re-structure the I2C module to make use of the generic I2C MicroPython binding - Add, remove and update API with be like RP2 style * [SPI] Standardize SPI module API - Re-structure the SPI module to make use of the MicroPython generic bindings - Add, remove and update API to be like RP2 style * [Readme] Update Readme to include more details - Update README.md to include more details - minor updates to i2c and timer module API * [README] Update README.md to provide more info about AMB23 * Pre Release Ameba MicroPython V1.1.0 - v2 - Update SDK and libs - Optimize memory usage and eliminate dependency on PSRAM Co-authored-by: ambiot <ambiot123@gmail.com>
Is there any special design decisions why qstr's are referenced by index in a table, instead of direct pointers? Having extra indirection of course affects performance, especially for cached archs.
My first thought was about limiting value domain, but "qstr" type is still defined as uint, so generally takes same size as a pointer. Though I found that qstr's are stored in parse nodes as MP_PARSE_NODE_LEAF_ARG(pn), which takes 4 bits for kind. But for pointer that would mean that qstr should be 16-byte aligned. Probably too harsh for strings in constrained environment indeed. But on the other hand, if this is only required for parsing source code...
So, I wonder is there're more tricks/optimizations which assume that qstr's have limited value domain, of that's the only one?
The text was updated successfully, but these errors were encountered: