tinygo-org / tinygo

Go compiler for small places. Microcontrollers, WebAssembly (WASM/WASI), and command-line tools. Based on LLVM.
https://tinygo.org
Other
15.49k stars 913 forks source link

runtime: optimize findHead #4574

Closed aykevl closed 1 week ago

aykevl commented 3 weeks ago

This is similar to https://github.com/tinygo-org/tinygo/pull/3899, but smaller and hopefully just as efficient. Needs a bit of cleanup before being ready.

github-actions[bot] commented 3 weeks ago

Size difference with the dev branch:

Binary size difference
not the same command!
    tinygo build -size short -o ./build/test.hex -target=feather-rp2040 ./examples/adafruit4650
    go: downloading tinygo.org/x/tinyfont v0.3.0
not the same command!
    tinygo build -size short -o ./build/test.hex -target=nano-rp2040 -stack-size 8kb ./examples/net/websocket/dial/
    go: downloading golang.org/x/net v0.7.0
not the same command!
    tinygo build -size short -o ./build/test.hex -target=nano-rp2040 -stack-size 8kb ./examples/net/mqttclient/natiu/
    go: downloading github.com/soypat/natiu-mqtt v0.5.1
not the same command!
    tinygo build -size short -o ./build/test.hex -target=wioterminal -stack-size 8kb ./examples/net/mqttclient/paho/
    go: downloading github.com/eclipse/paho.mqtt.golang v1.2.0
 flash                          ram
 before   after   diff          before   after   diff
   2825    2825      0   0.00%     558     558      0   0.00% tinygo build -size short -o ./build/test.hex -target=arduino ./examples/servo
   1581    1581      0   0.00%     598     598      0   0.00% tinygo build -size short -o ./build/test.hex -target=arduino   ./examples/ws2812
   1056    1056      0   0.00%     180     180      0   0.00% tinygo build -size short -o ./build/test.hex -target=digispark ./examples/ws2812
  61344   61360     16   0.03%    6196    6196      0   0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/adt7410/main.go
  13548   13564     16   0.12%    6796    6796      0   0.00% tinygo build -size short -o ./build/test.hex -target=pybadge ./examples/amg88xx
  11784   11800     16   0.14%    6580    6580      0   0.00% tinygo build -size short -o ./build/test.hex -target=nano-33-ble ./examples/apds9960/proximity/main.go
  63868   63884     16   0.03%    6196    6196      0   0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/bmi160/main.go
  63920   63936     16   0.03%    6228    6228      0   0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/bmp280/main.go
   8164    8180     16   0.20%    3348    3348      0   0.00% tinygo build -size short -o ./build/test.hex -target=bluepill ./examples/ds1307/sram/main.go
  22152   22168     16   0.07%    3544    3544      0   0.00% tinygo build -size short -o ./build/test.hex -target=bluepill ./examples/ds1307/time/main.go
  65548   65564     16   0.02%    9012    9012      0   0.00% tinygo build -size short -o ./build/test.hex -target=pyportal ./examples/flash/console/qspi
  68092   68108     16   0.02%    6504    6504      0   0.00% tinygo build -size short -o ./build/test.hex -target=feather-m0 ./examples/gps/uart/main.go
  14708   14724     16   0.11%    6580    6580      0   0.00% tinygo build -size short -o ./build/test.hex -target=nano-33-ble ./examples/hts221/main.go
  10136   10152     16   0.16%    6916    6916      0   0.00% tinygo build -size short -o ./build/test.hex -target=pyportal ./examples/ili9341/basic
  29488   29504     16   0.05%   38076   38076      0   0.00% tinygo build -size short -o ./build/test.hex -target=pyportal ./examples/ili9341/pyportal_boing
  10156   10172     16   0.16%    6924    6924      0   0.00% tinygo build -size short -o ./build/test.hex -target=pyportal ./examples/ili9341/scroll
 263540  263556     16   0.01%   46760   46760      0   0.00% tinygo build -size short -o ./build/test.hex -target=pyportal ./examples/ili9341/slideshow
  14052   14068     16   0.11%    6580    6580      0   0.00% tinygo build -size short -o ./build/test.hex -target=nano-33-ble ./examples/lps22hb/main.go
  68512   68528     16   0.02%    6196    6196      0   0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/mcp2515/main.go
  27244   27260     16   0.06%    3648    3648      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/microbitmatrix/main.go
  26956   26972     16   0.06%    5696    5696      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit-v2 ./examples/microbitmatrix/main.go
  75792   75808     16   0.02%    7480    7480      0   0.00% tinygo build -size short -o ./build/test.hex -target=p1am-100 ./examples/p1am/main.go
   8064    8080     16   0.20%    6796    6796      0   0.00% tinygo build -size short -o ./build/test.hex -target=pybadge ./examples/shifter/main.go
  57324   57340     16   0.03%    3692    3692      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/sht3x/main.go
  16948   16964     16   0.09%    4748    4748      0   0.00% tinygo build -size short -o ./build/test.hex -target=circuitplay-express ./examples/thermistor/main.go
  10504   10520     16   0.15%    4540    4540      0   0.00% tinygo build -size short -o ./build/test.hex -target=circuitplay-bluefruit ./examples/tone
   9504    9520     16   0.17%    6788    6788      0   0.00% tinygo build -size short -o ./build/test.hex -target=pyportal ./examples/touch/resistive/fourwire/main.go
  12572   12588     16   0.13%    6984    6984      0   0.00% tinygo build -size short -o ./build/test.hex -target=pyportal ./examples/touch/resistive/pyportal_touchpaint/main.go
  24684   24700     16   0.06%   13892   13892      0   0.00% tinygo build -size short -o ./build/test.hex -target=feather-nrf52840-sense ./examples/waveshare-epd/epd1in54/main.go
  62332   62348     16   0.03%    5952    5952      0   0.00% tinygo build -size short -o ./build/test.hex -target=feather-nrf52840 ./examples/is31fl3731/main.go
  16420   16436     16   0.10%    4732    4732      0   0.00% tinygo build -size short -o ./build/test.hex -target=circuitplay-express ./examples/microphone/main.go
   7320    7336     16   0.22%    3320    3320      0   0.00% tinygo build -size short -o ./build/test.hex -target=nucleo-f103rb ./examples/shiftregister/main.go
  77204   77220     16   0.02%    6344    6344      0   0.00% tinygo build -size short -o ./build/test.hex -target=feather-m0 ./examples/dht/main.go
  70760   70776     16   0.02%    6340    6340      0   0.00% tinygo build -size short -o ./build/test.hex -target=xiao ./examples/pcf8563/time/
  71192   71208     16   0.02%    6352    6352      0   0.00% tinygo build -size short -o ./build/test.hex -target=xiao ./examples/pcf8563/timer/
   9312    9328     16   0.17%    5260    5260      0   0.00% tinygo build -size short -o ./build/test.hex -target=nucleo-l432kc ./examples/aht20/main.go
  72636   72652     16   0.02%   10748   10748      0   0.00% tinygo build -size short -o ./build/test.hex -target=feather-m4 ./examples/sdcard/console/
  61432   61448     16   0.03%    8232    8232      0   0.00% tinygo build -size short -o ./build/test.hex -target=feather-m4 ./examples/i2csoft/adt7410/
  10280   10296     16   0.16%    6796    6796      0   0.00% tinygo build -size short -o ./build/test.elf -target=wioterminal ./examples/axp192/m5stack-core2-blinky/
  13732   13748     16   0.12%    4940    4940      0   0.00% tinygo build -size short -o ./build/test.hex -target=nucleo-wl55jc ./examples/sx126x/lora_rxtx/
  31336   31352     16   0.05%    4548    4548      0   0.00% tinygo build -size short -o ./build/test.uf2 -target=pico ./examples/ssd1289/main.go
  83072   83088     16   0.02%    6588    6588      0   0.00% tinygo build -size short -o ./build/test.hex -target=nucleo-wl55jc ./examples/lora/lorawan/atcmd/
  65196   65212     16   0.02%    6260    6260      0   0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/ndir/main_ndir.go
 296572  296588     16   0.01%   13788   13788      0   0.00% tinygo build -size short -o ./build/test.hex -target=pyportal -stack-size 8kb ./examples/net/http-get/
 103040  103056     16   0.02%    9816    9816      0   0.00% tinygo build -size short -o ./build/test.hex -target=metro-m4-airlift -stack-size 8kb ./examples/net/socket/
 338372  338388     16   0.00%   15396   15396      0   0.00% tinygo build -size short -o ./build/test.hex -target=matrixportal-m4 -stack-size 8kb ./examples/net/webstatic/
 111508  111524     16   0.01%    7772    7772      0   0.00% tinygo build -size short -o ./build/test.hex -target=arduino-mkrwifi1010 -stack-size 8kb ./examples/net/tlsclient/
 116984  117000     16   0.01%   13132   13132      0   0.00% tinygo build -size short -o ./build/test.hex -target=wioterminal -stack-size 8kb ./examples/net/webclient/
 286072  286088     16   0.01%   17812   17812      0   0.00% tinygo build -size short -o ./build/test.hex -target=wioterminal -stack-size 8kb ./examples/net/webserver/
 287068  287084     16   0.01%   18212   18212      0   0.00% tinygo build -size short -o ./build/test.hex -target=wioterminal -stack-size 8kb ./examples/net/mqttclient/paho/
  16844   16864     20   0.12%    4324    4324      0   0.00% tinygo build -size short -o ./build/test.hex -target=feather-rp2040 ./examples/adafruit4650
   9548    9568     20   0.21%    4756    4756      0   0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/adxl345/main.go
   8660    8680     20   0.23%    4748    4748      0   0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/apa102/main.go
   9776    9796     20   0.20%    4768    4768      0   0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/apa102/itsybitsy-m0/main.go
   8348    8368     20   0.24%    2320    2320      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/at24cx/main.go
   8104    8124     20   0.25%    4748    4748      0   0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/bh1750/main.go
   7412    7432     20   0.27%    4748    4748      0   0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/blinkm/main.go
  12180   12200     20   0.16%    4820    4820      0   0.00% tinygo build -size short -o ./build/test.hex -target=trinket-m0 ./examples/bmp388/main.go
   4600    4620     20   0.43%    2280    2280      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/easystepper/main.go
   7192    7212     20   0.28%    2280    2280      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/gc9a01/main.go
   7852    7872     20   0.25%    4748    4748      0   0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/hcsr04/main.go
   5812    5832     20   0.34%    2280    2280      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/hd44780/customchar/main.go
   5764    5784     20   0.35%    2280    2280      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/hd44780/text/main.go
  10508   10528     20   0.19%    4756    4756      0   0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/hd44780i2c/main.go
  16128   16148     20   0.12%    2360    2360      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/hub75/main.go
  10624   10644     20   0.19%    4868    4868      0   0.00% tinygo build -size short -o ./build/test.hex -target=xiao ./examples/ili9341/basic
  10712   10732     20   0.19%    4876    4876      0   0.00% tinygo build -size short -o ./build/test.hex -target=xiao ./examples/ili9341/scroll
  11712   11732     20   0.17%    4788    4788      0   0.00% tinygo build -size short -o ./build/test.hex -target=circuitplay-express ./examples/lis3dh/main.go
  12428   12448     20   0.16%    4796    4796      0   0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/lsm6ds3/main.go
  10724   10744     20   0.19%    4748    4748      0   0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/mag3110/main.go
   9896    9916     20   0.20%    4780    4780      0   0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/mcp23017/main.go
  10348   10368     20   0.19%    4788    4788      0   0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/mcp23017-multiple/main.go
   9760    9780     20   0.20%    4748    4748      0   0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/mcp3008/main.go
   8220    8240     20   0.24%    4756    4756      0   0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/mma8653/main.go
   8128    8148     20   0.25%    4748    4748      0   0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/mpu6050/main.go
  12232   12252     20   0.16%    3352    3352      0   0.00% tinygo build -size short -o ./build/test.hex -target=pico ./examples/pca9685/main.go
   6208    6228     20   0.32%    3288    3288      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/pcd8544/setbuffer/main.go
   5240    5260     20   0.38%    2280    2280      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/pcd8544/setpixel/main.go
  10516   10536     20   0.19%    3328    3328      0   0.00% tinygo build -size short -o ./build/test.hex -target=feather-rp2040 ./examples/seesaw
  13748   13768     20   0.15%    3400    3400      0   0.00% tinygo build -size short -o ./build/test.hex -target=pico     ./examples/sgp30
   6668    6688     20   0.30%    2288    2288      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/ssd1306/i2c_128x32/main.go
   6120    6140     20   0.33%    2280    2280      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/ssd1306/spi_128x64/main.go
   5824    5844     20   0.34%    2280    2280      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/ssd1331/main.go
   6764    6784     20   0.30%    2280    2280      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/st7735/main.go
   6676    6696     20   0.30%    2280    2280      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/st7789/main.go
  10048   10068     20   0.20%    4748    4748      0   0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/tm1637/main.go
  10848   10868     20   0.18%    3340    3340      0   0.00% tinygo build -size short -o ./build/test.hex -target=pico ./examples/touch/capacitive
  14960   14980     20   0.13%    4756    4756      0   0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/vl53l1x/main.go
  13440   13460     20   0.15%    4756    4756      0   0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/vl6180x/main.go
   6468    6488     20   0.31%    2320    2320      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/waveshare-epd/epd2in13/main.go
   6156    6176     20   0.32%    2312    2312      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/waveshare-epd/epd2in13x/main.go
   6380    6400     20   0.31%    2320    2320      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/waveshare-epd/epd4in2/main.go
  26432   26452     20   0.08%   16732   16732      0   0.00% tinygo build -size short -o ./build/test.hex -target=pico ./examples/waveshare-epd/epd2in66b/main.go
   6828    6848     20   0.29%    4788    4788      0   0.00% tinygo build -size short -o ./build/test.hex -target=circuitplay-express ./examples/ws2812
   5744    5764     20   0.35%    9538    9538      0   0.00% tinygo build -size short -o ./build/test.bin -target=m5stamp-c3          ./examples/ws2812
  11060   11080     20   0.18%    4748    4748      0   0.00% tinygo build -size short -o ./build/test.hex -target=circuitplay-express ./examples/buzzer/main.go
  12768   12788     20   0.16%    4788    4788      0   0.00% tinygo build -size short -o ./build/test.hex -target=trinket-m0 ./examples/veml6070/main.go
   6732    6752     20   0.30%    4748    4748      0   0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/l293x/simple/main.go
   8644    8664     20   0.23%    4748    4748      0   0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/l293x/speed/main.go
   6700    6720     20   0.30%    4748    4748      0   0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/l9110x/simple/main.go
   9256    9276     20   0.22%    4756    4756      0   0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/l9110x/speed/main.go
   6992    7012     20   0.29%    2268    2268      0   0.00% tinygo build -size short -o ./build/test.hex -target=hifive1b ./examples/ssd1351/main.go
  12984   13004     20   0.15%    4748    4748      0   0.00% tinygo build -size short -o ./build/test.hex -target=circuitplay-express ./examples/lis2mdl/main.go
   8860    8880     20   0.23%    4764    4764      0   0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/max72xx/main.go
  36512   36532     20   0.05%    3988    3988      0   0.00% tinygo build -size short -o ./build/test.hex -target=feather-rp2040 ./examples/pcf8523/
   7256    7276     20   0.28%    4748    4748      0   0.00% tinygo build -size short -o ./build/test.hex -target=xiao ./examples/pcf8563/clkout/
  12164   12184     20   0.16%    3304    3304      0   0.00% tinygo build -size short -o ./build/test.hex -target=pico ./examples/qmi8658c/main.go
  10788   10808     20   0.19%    3288    3288      0   0.00% tinygo build -size short -o ./build/test.hex -target=feather-rp2040 ./examples/pcf8591/
   8724    8744     20   0.23%    4756    4756      0   0.00% tinygo build -size short -o ./build/test.hex -target=feather-m0 ./examples/ina260/main.go
  13176   13196     20   0.15%    4788    4788      0   0.00% tinygo build -size short -o ./build/test.hex -target=feather-m0 ./examples/ina219/main.go
   9008    9028     20   0.22%    3276    3276      0   0.00% tinygo build -size short -o ./build/test.uf2 -target=pico ./examples/xpt2046/main.go
  11236   11256     20   0.18%    4252    4252      0   0.00% tinygo build -size short -o ./build/test.hex -target=pico ./examples/irremote/main.go
  11932   11952     20   0.17%    3324    3324      0   0.00% tinygo build -size short -o ./build/test.hex -target=badger2040 ./examples/uc8151/main.go
  10408   10428     20   0.19%    3356    3356      0   0.00% tinygo build -size short -o ./build/test.uf2 -target=pico ./examples/scd4x/main.go
   8532    8552     20   0.23%    4748    4748      0   0.00% tinygo build -size short -o ./build/test.uf2 -target=circuitplay-express ./examples/makeybutton/main.go
   9644    9664     20   0.21%    4772    4772      0   0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/ds18b20/main.go
  15896   15916     20   0.13%    4880    4880      0   0.00% tinygo build -size short -o ./build/test.uf2 -target=pico ./examples/as560x/main.go
   9868    9888     20   0.20%    3296    3296      0   0.00% tinygo build -size short -o ./build/test.uf2 -target=pico ./examples/mpu6886/main.go
   7788    7808     20   0.26%    4748    4748      0   0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 ./examples/ttp229/main.go
   9296    9316     20   0.22%    3288    3288      0   0.00% tinygo build -size short -o ./build/test.uf2 -target=pico ./examples/mpu9150/main.go
  11376   11396     20   0.18%    3324    3324      0   0.00% tinygo build -size short -o ./build/test.hex -target=macropad-rp2040 ./examples/sh1106/macropad_spi
   8436    8456     20   0.24%    3760    3760      0   0.00% tinygo build -size short -o ./build/test.hex -target=macropad-rp2040 ./examples/encoders/quadrature-interrupt
  70472   70496     24   0.03%    3660    3660      0   0.00% tinygo build -size short -o ./build/test.hex -target=pinetime     ./examples/bma42x/main.go
  27388   27412     24   0.09%    4788    4788      0   0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/bmp180/main.go
  69616   69640     24   0.03%    6376    6376      0   0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/ds3231/main.go
  69168   69192     24   0.03%    6976    6976      0   0.00% tinygo build -size short -o ./build/test.hex -target=itsybitsy-m0 ./examples/flash/console/spi
  67556   67580     24   0.04%    6368    6368      0   0.00% tinygo build -size short -o ./build/test.hex -target=feather-m0 ./examples/gps/i2c/main.go
  26108   26132     24   0.09%    2328    2328      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/lsm303agr/main.go
  57380   57404     24   0.04%    3700    3700      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/sht4x/main.go
  57288   57312     24   0.04%    3692    3692      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/shtc3/main.go
  31832   31856     24   0.08%    4788    4788      0   0.00% tinygo build -size short -o ./build/test.hex -target=trinket-m0 ./examples/bme280/main.go
  71224   71248     24   0.03%    6344    6344      0   0.00% tinygo build -size short -o ./build/test.hex -target=xiao ./examples/pcf8563/alarm/
  66752   66776     24   0.04%    4816    4816      0   0.00% tinygo build -size short -o ./build/test.hex -target=pico ./examples/ndir/main_ndir.go
  62212   62236     24   0.04%    3788    3788      0   0.00% tinygo build -size short -o ./build/test.hex -target=microbit ./examples/ndir/main_ndir.go
  65720   65744     24   0.04%    4784    4784      0   0.00% tinygo build -size short -o ./build/test.uf2 -target=pico ./examples/mcp9808/main.go
  85868   85892     24   0.03%    5140    5140      0   0.00% tinygo build -size short -o ./build/test.hex -target=challenger-rp2040 ./examples/net/ntpclient/
 119296  119320     24   0.02%    7848    7848      0   0.00% tinygo build -size short -o ./build/test.hex -target=arduino-nano33 -stack-size 8kb ./examples/net/tcpclient/
 245452  245476     24   0.01%   10488   10488      0   0.00% tinygo build -size short -o ./build/test.hex -target=nano-rp2040 -stack-size 8kb ./examples/net/websocket/dial/
 154136  154160     24   0.02%    6540    6540      0   0.00% tinygo build -size short -o ./build/test.hex -target=nano-rp2040 -stack-size 8kb ./examples/net/mqttclient/natiu/
5327990 5330590   2600   0.00%  811790  811790      0   0.00%