Register-based virtual machine?

[bakery2k]

Has anybody thought about adding a register-based bytecode to MicroPython, either as a configuration option or as a replacement for the current stack-based bytecode?

I asked this question on the forum, but there wasn't much interest. This was prompted by a recent paper, which concludes:

Because of the advantages in speed and its small bytecode size, a register-based virtual machine can be best applied on systems where both computational and storage facilities are limited (e.g. embedded systems).

A register-based bytecode would probably be faster, and possibly be more compact, than MicroPython's current stack-based approach. The downside would be increased complexity of the compiler and VM.

Which of the following best describes the situation with register-based bytecode in MicroPython?

1. It is currently being worked on.
2. It is likely / possible that it will be supported in the future, but not currently being worked on.
3. It is unlikely to ever be supported. (For example, because the performance benefit is not worth the increased complexity and/or risk of increased bytecode size.)
4. It is not possible to support. (Why?)

[pfalcon]

This was prompted by a recent paper, which concludes:

That paper may be recent, but the whole dichotomy is well known and researched for decade(s), e.g. https://www.scss.tcd.ie/publications/theses/phd/TCD-SCSS-PHD-2007-04.pdf

It is unlikely to ever be supported. (For example, because the performance benefit is not worth the increased complexity and/or risk of increased bytecode size.)

Indeed, you pinpointed it - the forte of MicroPython is not performance, it's efficiency, that is, being able to do as much as possible with as little as possible resources. And one of the most precious resources is memory. And of course, register-based VM requires explicit register numbers to be stored in instructions, which requires precious bits. We aren't going to bloat bytecode size, given that it's actually the top real-world problem our users face: as soon as they start to write more complex apps, on smaller platforms, it's easy to get out of memory purely by bytecode size.

With that in mind (the MicroPython is a magic project, yeah), MicroPython does support register-based machines, albeit not virtual, but real ones - by the virtue of its "viper" native machine code generator. Currently, it's very simple and doesn't even have any real register allocator. But before that, it transcodes pretty small subset of the main VM functionality. So, if you're interested in register-based machines, you can find a lot of places to contribute to ;-).

[bakery2k]

That paper may be recent, but the whole dichotomy is well known and researched for decade(s), e.g. https://www.scss.tcd.ie/publications/theses/phd/TCD-SCSS-PHD-2007-04.pdf

Yunhe Shi's thesis agrees with most other work on the subject: it shows register-based bytecode providing better performance than stack-based code at the expense of increased size. Ruijie Fang & Siqi Liu's recent paper was interesting because it shows a register-based bytecode which is smaller than the equivalent stack-based code.

However on closer reading, this was achieved only for lightweight, domain-specific virtual machines. It seems unlikely that this result will extend to VMs like [Micro]Python's, which implement a full, general-purpose programming language. For these more complex VMs, register-based bytecode would almost certainly be larger than stack-based code.

Given this likelihood, and your comment that it is already "easy to get out of memory purely by bytecode size", it makes sense that register-based bytecode would not be a good fit for MicroPython.

[pfalcon]

Hopefully the above comments give enough food for thought for interested parties. Further discussion can happen in the dedicated forum: https://forum.micropython.org/viewforum.php?f=3 .