tinygo
tinygo copied to clipboard
tinygo-org
interp: add 'max depth' parameter to limit cost
Prototype of limiting max depth for interp evaluation (number of functions) as a way of keeping it's cost-to-execute down.
This should still have reproducible builds since the code structure (function call chains) is fixed for any given code being compiled.
Size difference with the dev branch:
Binary size difference
before after diff
60688 60688 0 0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/adt7410/main.go
9700 9700 0 0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/adxl345/main.go
13260 13260 0 0.00% tinygo build -size short -o ./build/test.hex -target=pybadge ./examples/amg88xx
8776 8776 0 0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/apa102/main.go
11716 11716 0 0.00% tinygo build -size short -o ./build/test.hex -target=nano-33-ble ./examples/apds9960/proximity/main.go
10392 10392 0 0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/apa102/itsybitsy-m0/main.go
8196 8196 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/at24cx/main.go
8308 8308 0 0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/bh1750/main.go
7608 7608 0 0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/blinkm/main.go
69540 69540 0 0.00% tinygo build -size short -o ./build/test.hex -target=pinetime ./examples/bma42x/main.go
63260 63260 0 0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/bmi160/main.go
27860 27860 0 0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/bmp180/main.go
63288 63288 0 0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/bmp280/main.go
12420 12420 0 0.00% tinygo build -size short -o ./build/test.hex -target=trinket-m0 ./examples/bmp388/main.go
8116 8116 0 0.00% tinygo build -size short -o ./build/test.hex -target=bluepill ./examples/ds1307/sram/main.go
22008 22008 0 0.00% tinygo build -size short -o ./build/test.hex -target=bluepill ./examples/ds1307/time/main.go
68964 68964 0 0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/ds3231/main.go
4708 4708 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/easystepper/main.go
24876 24876 0 0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/espat/espconsole/main.go
25104 25104 0 0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/espat/esphub/main.go
24860 24860 0 0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/espat/espstation/main.go
68684 68684 0 0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/flash/console/spi
64636 64636 0 0.00% tinygo build -size short -o ./build/test.hex -target=pyportal ./examples/flash/console/qspi
7052 7052 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/gc9a01/main.go
67956 67956 0 0.00% tinygo build -size short -o ./build/test.hex -target=feather-m0 ./examples/gps/i2c/main.go
68424 68424 0 0.00% tinygo build -size short -o ./build/test.hex -target=feather-m0 ./examples/gps/uart/main.go
8424 8424 0 0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/hcsr04/main.go
5712 5712 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/hd44780/customchar/main.go
5756 5756 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/hd44780/text/main.go
10616 10616 0 0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/hd44780i2c/main.go
14624 14624 0 0.00% tinygo build -size short -o ./build/test.hex -target=nano-33-ble ./examples/hts221/main.go
16904 16904 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/hub75/main.go
10048 10048 0 0.00% tinygo build -size short -o ./build/test.hex -target=pyportal ./examples/ili9341/basic
10884 10884 0 0.00% tinygo build -size short -o ./build/test.hex -target=xiao ./examples/ili9341/basic
29044 29044 0 0.00% tinygo build -size short -o ./build/test.hex -target=pyportal ./examples/ili9341/pyportal_boing
10076 10076 0 0.00% tinygo build -size short -o ./build/test.hex -target=pyportal ./examples/ili9341/scroll
10960 10960 0 0.00% tinygo build -size short -o ./build/test.hex -target=xiao ./examples/ili9341/scroll
263524 263524 0 0.00% tinygo build -size short -o ./build/test.hex -target=pyportal ./examples/ili9341/slideshow
12092 12092 0 0.00% tinygo build -size short -o ./build/test.hex -target=circuitplay-express ./examples/lis3dh/main.go
14012 14012 0 0.00% tinygo build -size short -o ./build/test.hex -target=nano-33-ble ./examples/lps22hb/main.go
26132 26132 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/lsm303agr/main.go
12572 12572 0 0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/lsm6ds3/main.go
10952 10952 0 0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/mag3110/main.go
10180 10180 0 0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/mcp23017/main.go
10608 10608 0 0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/mcp23017-multiple/main.go
9868 9868 0 0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/mcp3008/main.go
66772 66772 0 0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/mcp2515/main.go
22952 22952 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/microbitmatrix/main.go
22944 22944 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit-v2 ./examples/microbitmatrix/main.go
8532 8532 0 0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/mma8653/main.go
8316 8316 0 0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/mpu6050/main.go
74988 74988 0 0.00% tinygo build -size short -o ./build/test.hex -target=p1am-100 ./examples/p1am/main.go
12144 12144 0 0.00% tinygo build -size short -o ./build/test.hex -target=pico ./examples/pca9685/main.go
6084 6084 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/pcd8544/setbuffer/main.go
5104 5104 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/pcd8544/setpixel/main.go
2681 2681 0 0.00% tinygo build -size short -o ./build/test.hex -target=arduino ./examples/servo
7944 7944 0 0.00% tinygo build -size short -o ./build/test.hex -target=pybadge ./examples/shifter/main.go
56368 56368 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/sht3x/main.go
56424 56424 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/sht4x/main.go
56340 56340 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/shtc3/main.go
6464 6464 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/ssd1306/i2c_128x32/main.go
5940 5940 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/ssd1306/spi_128x64/main.go
5704 5704 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/ssd1331/main.go
6392 6392 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/st7735/main.go
6292 6292 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/st7789/main.go
17212 17212 0 0.00% tinygo build -size short -o ./build/test.hex -target=circuitplay-express ./examples/thermistor/main.go
10328 10328 0 0.00% tinygo build -size short -o ./build/test.hex -target=circuitplay-bluefruit ./examples/tone
10728 10728 0 0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/tm1637/main.go
9404 9404 0 0.00% tinygo build -size short -o ./build/test.hex -target=pyportal ./examples/touch/resistive/fourwire/main.go
12460 12460 0 0.00% tinygo build -size short -o ./build/test.hex -target=pyportal ./examples/touch/resistive/pyportal_touchpaint/main.go
15772 15772 0 0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/vl53l1x/main.go
13812 13812 0 0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/vl6180x/main.go
6460 6460 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/waveshare-epd/epd2in13/main.go
6012 6012 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/waveshare-epd/epd2in13x/main.go
6288 6288 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/waveshare-epd/epd4in2/main.go
137184 137184 0 0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/wifinina/ntpclient/main.go
137176 137176 0 0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/wifinina/udpstation/main.go
137500 137500 0 0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/wifinina/tcpclient/main.go
137600 137600 0 0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/wifinina/webclient/main.go
6976 6976 0 0.00% tinygo build -size short -o ./build/test.hex -target=circuitplay-express ./examples/ws2812
5326 5326 0 0.00% tinygo build -size short -o ./build/test.bin -target=m5stamp-c3 ./examples/ws2812
61648 61648 0 0.00% tinygo build -size short -o ./build/test.hex -target=feather-nrf52840 ./examples/is31fl3731/main.go
1565 1565 0 0.00% tinygo build -size short -o ./build/test.hex -target=arduino ./examples/ws2812
880 880 0 0.00% tinygo build -size short -o ./build/test.hex -target=digispark ./examples/ws2812
32296 32296 0 0.00% tinygo build -size short -o ./build/test.hex -target=trinket-m0 ./examples/bme280/main.go
16660 16660 0 0.00% tinygo build -size short -o ./build/test.hex -target=circuitplay-express ./examples/microphone/main.go
11336 11336 0 0.00% tinygo build -size short -o ./build/test.hex -target=circuitplay-express ./examples/buzzer/main.go
13044 13044 0 0.00% tinygo build -size short -o ./build/test.hex -target=trinket-m0 ./examples/veml6070/main.go
6868 6868 0 0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/l293x/simple/main.go
8788 8788 0 0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/l293x/speed/main.go
6832 6832 0 0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/l9110x/simple/main.go
9448 9448 0 0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/l9110x/speed/main.go
7344 7344 0 0.00% tinygo build -size short -o ./build/test.hex -target=nucleo-f103rb ./examples/shiftregister/main.go
7084 7084 0 0.00% tinygo build -size short -o ./build/test.hex -target=hifive1b ./examples/ssd1351/main.go
13224 13224 0 0.00% tinygo build -size short -o ./build/test.hex -target=circuitplay-express ./examples/lis2mdl/main.go
8472 8472 0 0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/max72xx/main.go
77416 77416 0 0.00% tinygo build -size short -o ./build/test.hex -target=feather-m0 ./examples/dht/main.go
36620 36620 0 0.00% tinygo build -size short -o ./build/test.hex -target=feather-rp2040 ./examples/pcf8523/
70928 70928 0 0.00% tinygo build -size short -o ./build/test.hex -target=xiao ./examples/pcf8563/alarm/
7452 7452 0 0.00% tinygo build -size short -o ./build/test.hex -target=xiao ./examples/pcf8563/clkout/
70440 70440 0 0.00% tinygo build -size short -o ./build/test.hex -target=xiao ./examples/pcf8563/time/
70800 70800 0 0.00% tinygo build -size short -o ./build/test.hex -target=xiao ./examples/pcf8563/timer/
12084 12084 0 0.00% tinygo build -size short -o ./build/test.hex -target=pico ./examples/qmi8658c/main.go
8980 8980 0 0.00% tinygo build -size short -o ./build/test.hex -target=feather-m0 ./examples/ina260/main.go
9280 9280 0 0.00% tinygo build -size short -o ./build/test.hex -target=nucleo-l432kc ./examples/aht20/main.go
72008 72008 0 0.00% tinygo build -size short -o ./build/test.hex -target=feather-m4 ./examples/sdcard/console/
82532 82532 0 0.00% tinygo build -size short -o ./build/test.hex -target=wioterminal ./examples/rtl8720dn/webclient/
71924 71924 0 0.00% tinygo build -size short -o ./build/test.hex -target=wioterminal ./examples/rtl8720dn/webserver/
98452 98452 0 0.00% tinygo build -size short -o ./build/test.hex -target=wioterminal ./examples/rtl8720dn/mqttsub/
60532 60532 0 0.00% tinygo build -size short -o ./build/test.hex -target=feather-m4 ./examples/i2csoft/adt7410/
10164 10164 0 0.00% tinygo build -size short -o ./build/test.elf -target=wioterminal ./examples/axp192/m5stack-core2-blinky/
8924 8924 0 0.00% tinygo build -size short -o ./build/test.uf2 -target=pico ./examples/xpt2046/main.go
14560 14560 0 0.00% tinygo build -size short -o ./build/test.hex -target=nucleo-wl55jc ./examples/sx126x/lora_rxtx/
25876 25876 0 0.00% tinygo build -size short -o ./build/test.uf2 -target=pico ./examples/ssd1289/main.go
11204 11204 0 0.00% tinygo build -size short -o ./build/test.hex -target=pico ./examples/irremote/main.go
11220 11220 0 0.00% tinygo build -size short -o ./build/test.hex -target=badger2040 ./examples/uc8151/main.go
10308 10308 0 0.00% tinygo build -size short -o ./build/test.uf2 -target=pico ./examples/scd4x/main.go
8744 8744 0 0.00% tinygo build -size short -o ./build/test.uf2 -target=circuitplay-express ./examples/makeybutton/main.go
9608 9608 0 0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/ds18b20/main.go
81220 81220 0 0.00% tinygo build -size short -o ./build/test.hex -target=nucleo-wl55jc ./examples/lora/lorawan/atcmd/
15740 15740 0 0.00% tinygo build -size short -o ./build/test.uf2 -target=pico ./examples/as560x/main.go
9800 9800 0 0.00% tinygo build -size short -o ./build/test.uf2 -target=pico ./examples/mpu6886/main.go
7892 7892 0 0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/ttp229/main.go
65856 65856 0 0.00% tinygo build -size short -o ./build/test.hex -target=pico ./examples/ndir/main_ndir.go
61168 61168 0 0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/ndir/main_ndir.go
64480 64480 0 0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/ndir/main_ndir.go
9232 9232 0 0.00% tinygo build -size short -o ./build/test.uf2 -target=pico ./examples/mpu9150/main.go
3822944 3822944 0 0.00% sum
![github-actions[bot] avatar](https://avatars.githubusercontent.com/in/15368?v=4 "Published by a pub.dev verified publisher"){kind=small}
See a previous approach on limiting interp time here: https://github.com/tinygo-org/tinygo/pull/2384
I think this is actually a really interesting solution! It's reproducible which is good, and at least according to the size difference bot there doesn't seem to be much of an impact on binary size for small programs.
(I do need to review the code still, though).
@dgryski what do you think? Also, would this help where you ran into interp limitations?
Interp has problems with the strings and bytes unit tests. We encounter interp issues mainly trying to construct regexps at the top level. I'll see if this patch solves these for us.
I've been thinking about some additional 'constraints' we could place...
Limit Instruction Count
Only evaluate X times the number of instructions in a given function. E.g. if a function is 200 instructions, only evaluate 20,000 instructions before declaring the function needs to be executed at run time. This could catch gross loop unrolling, like the tests which are iterating through every possible Unicode code-point to test character classification.
Limit Allocations
If more than X bytes allocated during the evaluation of a function, declare it to evaluate at run time.
Others?
So long as the conditions are repeatable (based on artifacts of the code, not on asynchronous stuff like wall time) we could look for other 'heuristics'.... maybe the number of function calls made?
Huh, interesting update. So strings and bytes no longer fail due to interp issues.
Previously we would time out trying to execute https://github.com/golang/go/blob/master/src/strings/strings_test.go#L1814 at compile time. I wonder what changed since they both pass now on dev without this patch.
Off to test regexps next...
Still can't run `cloudflare/ahocorasick'
~/go/src/github.com/cloudflare/ahocorasick $ time tinygo test
^C
real 5m22.539s
user 22m45.512s
sys 0m37.183s
but this regexp-at-compile-time example runs now:
~/go/src/github.com/dgryski/bug/re $ tinygo run main.go
true
true
false
false
~/go/src/github.com/dgryski/bug/re $ cat main.go
package main
import (
"fmt"
"regexp"
)
var validID = regexp.MustCompile(`^[a-z]+\[[0-9]+\]$`)
func main() {
fmt.Println(validID.MatchString("adam[23]"))
fmt.Println(validID.MatchString("eve[7]"))
fmt.Println(validID.MatchString("Job[48]"))
fmt.Println(validID.MatchString("snakey"))
}
(However, it also seems to run on the current dev branch -- what else did we change?)
@dgryski - I've pushed a change that 'fixes' cloudflare/ahocorasick - I think it amounts to interp is many, many, many times slower than native execution. The latest change adds a -interp-maxinstr (default 100_000) that if interp runs more than N instructions evaluating a function, it kicks it back to execute at runtime.
I really doubt this will impact baremetal targets very much since it's relatively unlikely this scenario of 'N' nested loops in a variable initializer will crop-up.