PicoRuby Compiler

Page: 1

PicoRuby Compiler
Monstarlab
Ruby Association Grant 2020 Report
July 6, 2021

Page: 2

We are
Monstarlab
Established in 2006
85 Million USD of Capital (Nov. 2020)
1200+ Members in 25 Cities, 16 Countries
Full-Time Remoties in Japan even before the
pandemic
Now Hiring! Reach out to me

Page: 3

Page: 4

I am
HASUMI Hitoshi
Shimane development branch
hasumikin@GitHub
hasumikin@Twitter
hasumin（はすみん）
hasumikin（はすみきん）

Page: 5

PicoRuby Compiler
Why? What?

Page: 6

Ruby for embedded system

Page: 7

Ruby for embedded system
Doesn't make sense

Page: 8

Why doesn't it make sense?
mruby-compiler depends on mruby (mrb_state)
You can use mruby-compiler with mruby/c VM
However, the size of mruby-compiler spoils mruby/c's
small footprint
OK

Page: 9

Ruby for embedded system
Doesn't make sense

Page: 10

Ruby for embedded system
PicoRuby Compiler for one-chip microcontrollers

Page: 11

Possibilities of PicoRuby Compiler
REPL
Debugging on an actual device
Even with mruby VM
One stop solution with mruby/c VM
For newbies, education, Smalruby etc.
Copyright © Hikari Arakawa (Ruby Programming Shounendan and Smalruby) 2013

Page: 12

PicoRuby Compiler
History
July 2019 -

Page: 13

Page: 14

"Lemon would generate smaller binary than Bison."

Page: 15

Page: 16

github.com/hasumikin/mmrbc.gem
mini mruby compiler
Tokenizer and Generator
CRuby
Parser
C (Lemon) + ffi gem
Able to compile only `puts "Hello World!"`
`[Identifier] "[String literal]"`

Page: 17

Jan 2020 -
Writing `mmruby` in C
then, `mv mmruby picoruby`

Page: 18

RA Grant
Outcome

Page: 19

Goals
Sufficient portion of the Ruby syntax to write IoT
firmware
Reduce RAM usage to execute on microcontrollers

Page: 20

Syntax - before RA Grant
# larger_script.rb
ary = Array.new(3)
ary[0] = {a: 123e2}
ary[0][:key] = "string"
ary[1] = %w(abc ABC Hello)
ary[2] = 0x1f
ary[3] = !true
puts "my name is #{self.class}, result is #{ary[2] * ary[0][:a]}"
p ary
=> my name is Object, result is 381300
[{:a=>12300, :key=>"string"}, ["abc", "ABC", "Hello"], 31, false]
class, def, return, block, if/unless, case-when,
while/until, break, etc were unimplemented yet

Page: 21

Syntax - after RA Grant

Page: 22

RAM consumption
$ valgrind
--tool=massif
--stacks=yes
path/to/(mrbc|picorbc)
source.rb
\
\
\
\
$ ms_print massif.out.xxx | less

Page: 23

RAM consumption
----------------------------------------------------------------------------------
Command:
../picoruby/build/host-production/bin/picorbc larger_script.rb
Massif arguments:
--stacks=yes
ms_print arguments: massif.out.13414
----------------------------------------------------------------------------------
KB
53.20^
#
|
#
|
@# :::
|
@# : :
|
@# : :
|
@@# : :
|
@@# :: :
|
@@#::: :
|
@@#::: :
|
@@::@@#::: :
|
@@: @@#::: :
|
@@:@:::@::::@@: @@#::: ::
|
@::@::@ :@:: @:: :@@: @@#::: ::
|
@:::@@@:@::@: @ :@:: @:: :@@: @@#::: ::
|
@@:@::@:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
|
::@@@ :@: @:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
|
:::::: :::::@ @ :@: @:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
|
:::::@@:: :::::: ::@ @ :@: @:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
|
: :: @ :: :::::: ::@ @ :@: @:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
|
: :: @ :: :::::: ::@ @ :@: @:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
0 +----------------------------------------------------------------------->Mi
0
1.616

Page: 24

RAM consumption
#
before Grant
after Grant
mrbc
picorbc
mrbc(3.0.0) picorbc
==================================================================
puts "Hello World!" 157.8 KB 11.17 KB
133.6 KB
15.43 KB
------------------------------------------------------------------
larger_script.rb
162.9 KB 53.20 KB
135.2 KB
24.21 KB
Note:
using glibc and Linux file system
on 64-bit architecture
All figures should possibly be about 35% smaller on 32-bit

Page: 25

RAM consumption
#
before Grant
after Grant
mrbc
picorbc
mrbc(3.0.0) picorbc
==================================================================
puts "Hello World!" 157.8 KB 11.17 KB
133.6 KB
15.43 KB
------------------------------------------------------------------
larger_script.rb
162.9 KB 53.20 KB
135.2 KB
24.21 KB
picorbc made a great progress on larger_script.rb
53.20 KB -> 24.21 KB
but got worse on `puts "Hello World!"`
11.17 KB -> 15.43 KB ...
What happened?

Page: 26

PicoRuby Compiler
What happened?

Page: 27

What happened?
1. Reusing literal data as much as possible
2. Considering paddings & Pooled allocation
3. Freeing in loop instead of recursion

Page: 28

Reusing literal data as much as possible
There were many wasteful, duplicated memory
allocations of literal data
eg) Reallocates memory when Tokenizer gives data to
Parser
Refactored the code to keep data common in a
compilation cycle as much as possible
eg) Token data puts on memory should be reused as
it is until exactly before generating VM code

Page: 29

Reusing literal data as much as possible
array[0] = :data
Tokens
`array`, `[`, `0`, `]`, `=`, `:`, `data`
Method name should be `[]=`, but where? how?
Thus, some literal data should be exceptional
Kind of a strategic decision
Beware of memory leaks

Page: 30

Padding in a struct
struct LinkedList {
struct LinkedList *next; // 4 bytes (in 32-bit architecture)
uint8_t
value; // 1 byte
}
sizeof(LinkedList);
=> 5
=> 8
✔Data structure alignment (at least in C99)
pointer[4] + uint8_t[1] + padding[3] = sum[8]
You need to pack them well

Page: 31

Pooled allocation
LinkedList *top;
(...)
top->next->next->next->next; // 5 items in the list
Consumes 40 bytes to store 5 values of uint8_t
Total size of pointers will be 1 KB if there are 250
items in a list
Pooled allocation

Page: 32

Pooled allocation
typedef struct node_pool {
NodePool *next;
uint16_t size;
uint16_t index;
Node *nodes;
} NodePool;
NodePool *newNodePool() {
size_t size = sizeof(NodePool) + sizeof(Node) * POOL_SIZE;
NodePool *node_pool = (NodePool *)alloc(size);
memset(node_pool, 0, size);
node_pool->next = NULL;
node_pool->size = POOL_SIZE;
node_pool->index = 0;
return node_pool;
}
/* node_pool.nodes[index] */
(Node *)((Node *)(&node_pool->nodes) + node_pool->index);

Page: 33

Pooled allocation
[n]: bytes
*next[4] ----------->
size[2]
index[2]
node[sizeof(Node)]
node[sizeof(Node)]
...
node[sizeof(Node)]
*next[4] ----------->
size[2]
index[2]
node[sizeof(Node)]
node[sizeof(Node)]
...
node[sizeof(Node)]
*next[4] ------------>
size[2]
index[2]
node[sizeof(Node)]
node[sizeof(Node)]
...
node[sizeof(Node)]
Reduces paddings of data structure alignment
Reduces the number of pointers
Reduces fragmentation

Page: 34

Stack spike
Before RA Grant
--------------------------------------------------------------------------------
Command:
../picoruby/build/host-production/bin/picorbc larger_script.rb
Massif arguments: --stacks=yes
ms_print arguments: massif.out.13414
--------------------------------------------------------------------------------
KB
53.20^
#
|
#
|
@# :::
|
@# : :
|
@# : :
|
@@# : :
|
@@# :: :
|
@@#::: :
|
@@#::: :
|
@@::@@#::: :
|
@@: @@#::: :
|
@@:@:::@::::@@: @@#::: ::
|
@::@::@ :@:: @:: :@@: @@#::: ::
|
@:::@@@:@::@: @ :@:: @:: :@@: @@#::: ::
|
@@:@::@:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
|
::@@@ :@: @:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
|
:::::: :::::@ @ :@: @:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
|
:::::@@:: :::::: ::@ @ :@: @:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
|
: :: @ :: :::::: ::@ @ :@: @:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
|
: :: @ :: :::::: ::@ @ :@: @:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
0 +----------------------------------------------------------------------->Mi
0
1.616

Page: 35

Stack spike

Page: 36

Stack spike

Page: 37

Stack spike

Page: 38

Stack spike

Page: 39

Stack spike
Before RA Grant
--------------------------------------------------------------------------------
Command:
../picoruby/build/host-production/bin/picorbc larger_script.rb
Massif arguments: --stacks=yes
ms_print arguments: massif.out.13414
--------------------------------------------------------------------------------
KB
53.20^
#
|
#
|
@# :::
|
@# : :
|
@# : :
|
@@# : :
|
@@# :: :
|
@@#::: :
|
@@#::: :
|
@@::@@#::: :
|
@@: @@#::: :
|
@@:@:::@::::@@: @@#::: ::
|
@::@::@ :@:: @:: :@@: @@#::: ::
|
@:::@@@:@::@: @ :@:: @:: :@@: @@#::: ::
|
@@:@::@:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
|
::@@@ :@: @:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
|
:::::: :::::@ @ :@: @:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
|
:::::@@:: :::::: ::@ @ :@: @:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
|
: :: @ :: :::::: ::@ @ :@: @:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
|
: :: @ :: :::::: ::@ @ :@: @:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
0 +----------------------------------------------------------------------->Mi
0
1.616

Page: 40

Stack spike

Page: 41

Stack spike

Page: 42

Stack spike

Page: 43

Stack spike

Page: 44

Stack spike

Page: 45

Stack spike

Page: 46

Stack spike

Page: 47

Stack spike

Page: 48

Stack spike

Page: 49

Stack spike

Page: 50

Freeing in loop instead of recursion
// Recursion is elegant but a big eater
void freeList_in_recursion(List *list) {
if (!list) return;
freeList_in_recursion(list->next);
free(list);
}
// Loop is somehow clumsy but thrifty
void freeList_in_loop(List *list) {
List *next;
while (list) {
next = list->next;
free(list);
list = next;
}
}

Page: 51

Freeing in loop instead of recursion
before Grant
--------------------------------------------------------------------------------
Command:
../picoruby/build/host-production/bin/picorbc larger_script.rb
Massif arguments: --stacks=yes
ms_print arguments: massif.out.13414
--------------------------------------------------------------------------------
KB
53.20^
#
|
#
|
@# :::
|
@# : :
|
@# : :
|
@@# : :
|
@@# :: :
|
@@#::: :
|
@@#::: :
|
@@::@@#::: :
|
@@: @@#::: :
|
@@:@:::@::::@@: @@#::: ::
|
@::@::@ :@:: @:: :@@: @@#::: ::
|
@:::@@@:@::@: @ :@:: @:: :@@: @@#::: ::
|
@@:@::@:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
|
::@@@ :@: @:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
|
:::::: :::::@ @ :@: @:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
|
:::::@@:: :::::: ::@ @ :@: @:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
|
: :: @ :: :::::: ::@ @ :@: @:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
|
: :: @ :: :::::: ::@ @ :@: @:: @@ :@::@: @ :@:: @:: :@@: @@#::: ::
0 +----------------------------------------------------------------------->Mi
0
1.616

Page: 52

Freeing in loop instead of recursion
after Grant
--------------------------------------------------------------------------------
Command:
./build/host-production/bin/picorbc test/fixtures/larger_script.rb
Massif arguments: --stacks=yes
ms_print arguments: massif.out.3082
--------------------------------------------------------------------------------
KB
24.21^
#
|
@ @:@:@:#
|
@:@@@:@:@:@:#:
@
|
@@:::@:@@@:@:@:@:#::::::@
|
@ :::@:@@@:@:@:@:#::::::@
|
@ :::@:@@@:@:@:@:#::::::@
|
@ :::@:@@@:@:@:@:#::::::@
|
@ :::@:@@@:@:@:@:#::::::@
|
@@:::::::::::::::@::::: ::::@::@::::::@ :::@:@@@:@:@:@:#::::::@
|
@ ::::::: :::: : @:: ::@:: :@::@:: :: @ :::@:@@@:@:@:@:#::::::@
|
@ ::::::: :::: : @:: ::@:: :@::@:: :: @ :::@:@@@:@:@:@:#::::::@
|
@ ::::::: :::: : @:: ::@:: :@::@:: :: @ :::@:@@@:@:@:@:#::::::@
|
@ ::::::: :::: : @:: ::@:: :@::@:: :: @ :::@:@@@:@:@:@:#::::::@
|
@ ::::::: :::: : @:: ::@:: :@::@:: :: @ :::@:@@@:@:@:@:#::::::@
|
@ ::::::: :::: : @:: ::@:: :@::@:: :: @ :::@:@@@:@:@:@:#::::::@
|
@ ::::::: :::: : @:: ::@:: :@::@:: :: @ :::@:@@@:@:@:@:#::::::@
|
@ ::::::: :::: : @:: ::@:: :@::@:: :: @ :::@:@@@:@:@:@:#::::::@
|
@ ::::::: :::: : @:: ::@:: :@::@:: :: @ :::@:@@@:@:@:@:#::::::@
|
@ ::::::: :::: : @:: ::@:: :@::@:: :: @ :::@:@@@:@:@:@:#::::::@
|
::::@ ::::::: :::: : @:: ::@:: :@::@:: :: @ :::@:@@@:@:@:@:#::::::@
0 +----------------------------------------------------------------------->Mi
0
1.082

Page: 53

What happened?
RAM usage when compiling a very small statement
like `puts "Hello World!"` became bigger than before
due to Pooled allocation
Because Pooled allocation allocates a fixed size of array
of struct in advance
However, when a Ruby script becomes larger,
measures of reducing RAM consumption including
Pooled allocation work effectively

Page: 54

PicoRuby Compiler
Future work

Page: 55

Killer Application

Page: 56

Programming languages need
a killer application

Page: 57

C ... UNIX
PHP ... WordPress
CRuby ... Rails

Page: 58

How about PicoRuby?

Page: 59

Page: 60

To be continued on
RubyKaigi Takeout 2021
or RubyConf 2021
if proposals.any?(&:accepted?)

Page: 61

Thank you!