Implement compact byte code (CBC) support in Jerry

[zherczeg]

Compact byte code (CBC) is the next generation of byte code for Jerry, which can reduce the byte code size around 50%. It also solves parser memory issues, left-hand-side issues, etc. The project is in its early phase, but the following examples shows the idea. All values are stored on a stack, all operations happen there. Several byte codes are "complex", so they do multiple things.

// a + b

   0 : [  1] CBC_PUSH_IDENT 1:literal<b>
   2 : [  1] CBC_BINARY_ADD_LEFT_LITERAL 0:literal<a>
   4 : [  0] CBC_POP
Parse successfully completed. Generated byte code size: 5 bytes

In Jerry: 8 bytes (37.5% saving)

  2:           assignment  130    6    0     // tmp130 = a : TYPEOF(a);
  3:             addition  131  130    1     // tmp131 = tmp130 + b;


// a = b + -c * ((d.c)++ - e)

   0 : [  1] CBC_UNARY_NEGATE_LITERAL 2:literal<c>
   2 : [  2] CBC_PUSH_IDENT 3:literal<d>
   4 : [  2] CBC_POST_INCR_PROP_STRING_PUSH_RESULT 4:string<c>
   6 : [  2] CBC_BINARY_SUBTRACT_RIGHT_LITERAL 5:literal<e>
   8 : [  1] CBC_MULTIPLY
   9 : [  1] CBC_BINARY_ADD_LEFT_LITERAL 1:literal<b>
  11 : [  0] CBC_ASSIGN_IDENT 0:literal<a>
Parse successfully completed. Generated byte code size: 13 bytes

In Jerry: 36 bytes (63.8% saving)

  2:           assignment  130    6    0     // tmp130 = b : TYPEOF(b);
  3:          unary_minus  131    1          // tmp131 = -c;
  4:           assignment  132    5    1     // tmp132 = 'c': STRING;
  5:          prop_getter  133    2  132     // tmp133 = d[tmp132];
  6:            post_incr  134  133          // tmp134 = tmp133++;
  7:         substraction  135  134    3     // tmp135 = tmp134 - e;
  8:       multiplication  136  131  135     // tmp136 = tmp131 * tmp135;
  9:             addition  137  130  136     // tmp137 = tmp130 + tmp136;
 10:           assignment    4    6  137     // a = tmp137 : TYPEOF(tmp137);

Of course nothing is set in stone at the moment, all suggestion are welcome. Especially the byte code definitions, which is the most important part of the project.

See https://github.com/Samsung/jerryscript/tree/compact_byte_code_supp_dev

[zherczeg]

I continued this work, and the results are still promising. Some examples:

// x = a + x ? !b.x ? c("arg") : d - x : e

   0 : CBC_PUSH_IDENT literal<x>id:0
   2 : CBC_BINARY_ADD_LEFT_LITERAL literal<a>id:1
   4 : CBC_BRANCH_IF_FALSE_FORWARD offset:21(->25)
   6 : CBC_PUSH_IDENT literal<b>id:2
   8 : CBC_PROP_STRING_GET string<x>id:6
  10 : CBC_BRANCH_IF_TRUE_FORWARD offset:9(->19)
  12 : CBC_PUSH_LITERAL string<arg>id:7
  14 : CBC_CALL_IDENT_PUSH_RESULT byte_arg:1 literal<c>id:3
  17 : CBC_JUMP_FORWARD offset:6(->23)
  19 : CBC_PUSH_IDENT literal<x>id:0
  21 : CBC_BINARY_SUBTRACT_LEFT_LITERAL literal<d>id:4
  23 : CBC_JUMP_FORWARD offset:4(->27)
  25 : CBC_PUSH_IDENT literal<e>id:5
  27 : CBC_ASSIGN_IDENT literal<x>id:0
Parse successfully completed. Total byte code size: 29 bytes

  2:           assignment  130    6    0     // tmp130 = a : TYPEOF(a);
  3:             addition  131  130    1     // tmp131 = tmp130 + x;
  4:    is_false_jmp_down  131    0   15     // if (tmp131 == false) goto 19;
  5:           assignment  132    5    1     // tmp132 = 'x': STRING;
  6:          prop_getter  133    2  132     // tmp133 = b[tmp132];
  7:          logical_not  134  133          // tmp134 = ! tmp133;
  8:    is_false_jmp_down  134    0    6     // if (tmp134 == false) goto 14;
  9:               call_n  135    3    1     //
 10:           assignment  135    5    4     // tmp135 = 'arg': STRING;
 11:                 meta    2  135  255     // tmp135 = c (tmp135);
 12:           assignment  136    6  135     // tmp136 = tmp135 : TYPEOF(tmp135);
 13:             jmp_down    0    4          // goto 17;
 14:           assignment  137    6    5     // tmp137 = d : TYPEOF(d);
 15:         substraction  138  137    1     // tmp138 = tmp137 - x;
 16:           assignment  136    6  138     // tmp136 = tmp138 : TYPEOF(tmp138);
 17:           assignment  139    6  136     // tmp139 = tmp136 : TYPEOF(tmp136);
 18:             jmp_down    0    2          // goto 20;
 19:           assignment  139    6    6     // tmp139 = e : TYPEOF(e);
 20:           assignment    1    6  139     // x = tmp139 : TYPEOF(tmp139);

Result: 76 bytes -> 29 bytes (62% saving)

// x = new a(b)(new (!c)).d(c, d, "arg");

   0 : CBC_PUSH_IDENT literal<b>id:2
   2 : CBC_NEW_IDENT byte_arg:1 literal<a>id:1
   5 : CBC_LOGICAL_NOT_LITERAL literal<c>id:3
   7 : CBC_NEW byte_arg:0
   9 : CBC_CALL_PUSH_RESULT byte_arg:1
  11 : CBC_PUSH_IDENT literal<c>id:3
  13 : CBC_PUSH_IDENT literal<d>id:4
  15 : CBC_PUSH_LITERAL string<arg>id:6
  17 : CBC_CALL_PROP_STRING_PUSH_RESULT byte_arg:3 string<d>id:5
  20 : CBC_ASSIGN_IDENT literal<x>id:0
Parse successfully completed. Total byte code size: 22 bytes

  2:          construct_n  130    0    1     //
  3:                 meta    2    1  255     // tmp130 = new a (b);
  4:               call_n  131  130    1     //
  5:          logical_not  131    2          // tmp131 = ! c;
  6:          construct_n  132  131    0     // tmp132 = new tmp131;
  7:                 meta    2  132  255     // tmp132 = new tmp131 (tmp132);
  8:           assignment  132    5    3     // tmp132 = 'd': STRING;
  9:          prop_getter  133  131  132     // tmp133 = tmp131[tmp132];
 10:               call_n  134  133    3     //
 11:                 meta    1    1  131     //
 12:                 meta    2    2  255     //
 13:                 meta    2    3  255     //
 14:           assignment  134    5    4     // tmp134 = 'arg': STRING;
 15:                 meta    2  134  255     // tmp134 = tmp133 (this_arg = tmp131, c, d, tmp134);
 16:           assignment    5    6  134     // x = tmp134 : TYPEOF(tmp134);

Result 60 bytes -> 22 bytes (63% saving)

[zherczeg]

I made some measurements on x86-32. The test file was 10.3Kb, and contained expressions and while/do-while loops generated by a fuzzer tool.

Memory consumption results:

CBC parser:
peak memory consumption: 9.8Kb (actually a bit lower than the input size :) )
byte-code length: 3.4Kb

Jerry parser
peak memory consumption: 40.0Kb
byte-code length: 7.9Kb

Parser memory reduction: 1 - 9.8/40.0 = 75.5%
Byte code length reduction: 1 - 3.4/7.9 = 56.9%

So everything is very promising so far. I think we can safely expect at least 60-70% final parser memory reduction and 40-50% byte code length reduction when this project is done.

I have some questions about the future development directions.

• For named functions, shall we construct them in byte code, or simply provide a list?
• Shall break/continue/return byte-codes warn about crossing with/try statements? We could introduce separate byte codes when this happens.
• How var identifiers should behave inside a with statement?
• How for-in statement stack should look like?

[zherczeg]

Progress goes well, branch updated. This is really a promising work.
Tests added, they can be checked to see the generated byte code.

I have an issue: vera++ complains about continues in switch, and I have to add FALLTHRU after them:

continue;
/* FALLTHRU */

Could this be fixed?

[zherczeg]

I just updated the Compact Byte Code parser and would like to share some results.

I created a test file from all .js files in iotjs/src/js with a "cat *.js" command. I did not organized the files in any way so the order is decided by the cat command. However I added a true() statement at the beginning to prevent its execution by Jerry. The total file size is 92.8K. I did one modification: named function expressions are not yet supported by the CBC parser so I changed

exports.lookup = function lookup(hostname, options, callback) {

to

exports.lookup = function (hostname, options, callback) {

The following measurements are done on x86-32 (with Os optimization):

Jerry runtime: 120 ms
CBC parser runtime: 7 ms (94.1% reduction)

Jerry parser memory consumption: 212.3K
CBC parser memory consumption: 40.0K (81.1% reduction)

Jerry parser stack: 7.7K
CBC parser stack: 2.4K (68.8% reduction)

Jerry parser byte code size: 40.7K
CBC parser byte code size: 14.2K (65.1% reduction)

These are the memory and stack consumption of an empty.js:

Jerry parser memory consumption: 1.7K
CBC parser memory consumption: 0.1K

Jerry parser stack: 0.4K
CBC parser stack: 0.9K

I also added a documentation about the compact byte code:

https://github.com/Samsung/jerryscript/blob/compact_byte_code_supp_dev/jerry-core/parser/js/new-parser/doc/cbc_overview.txt

[egavrin]

However I added a true() statement at the beginning to prevent its execution by Jerry.

You can try passing --parse-only to Jerry to prevent execution.

[zherczeg]

Good to know. I don't see any difference in this case, but that argument simplifies things.

[zherczeg]

We had some success with the integration. The parser itself works, and some simple JS files can be executed now. Here are some results measuring the usual iotjs.js (concatenation of all iotjs js files) file on x86-32:

time build/bin/release.linux/jerry --parse-only iotjs.js

Old parser:

real 0m0.616s
user 0m0.615s
sys 0m0.000s

New parser:

real 0m0.060s
user 0m0.060s
sys 0m0.000s

build/bin/release.linux-mem_stats/jerry --mem-stats --parse-only iotjs.js

Old parser:

Heap stats:
Heap size = 260096 bytes
Chunk size = 64 bytes
Allocated chunks count = 0
Allocated = 0 bytes
Waste = 0 bytes
Peak allocated chunks count = 3355
Peak allocated = 211187 bytes
Peak waste = 3533 bytes

New parser:

Heap stats:
Heap size = 260096 bytes
Chunk size = 64 bytes
Allocated chunks count = 1817
Allocated = 105426 bytes
Waste = 10862 bytes
Peak allocated chunks count = 2986
Peak allocated = 166183 bytes
Peak waste = 31494 bytes

Could you explain the meaning of the waste sections, and how can we reduce it? Is it part of the "allocated" memory or not?

[zherczeg]

I checked the memory consumption with Freya and it revealed that there is a serious memory leak in function parsing. I fixed it and here is the new result:

Heap stats:
Heap size = 260096 bytes
Chunk size = 64 bytes
Allocated chunks count = 836
Allocated = 45258 bytes
Waste = 8246 bytes
Peak allocated chunks count = 2005
Peak allocated = 106015 bytes
Peak waste = 28910 bytes

Still no idea about the peak waste.

[zherczeg]

Replacing lit_create_literal_from_utf8_string to lit_find_or_create_literal_from_utf8_string tripled the speed and reduced the memory consumption by 38K

real 0m0.022s
user 0m0.022s
sys 0m0.000s

Heap stats:
Heap size = 260096 bytes
Chunk size = 64 bytes
Allocated chunks count = 836
Allocated = 45258 bytes
Waste = 8246 bytes
Peak allocated chunks count = 1645
Peak allocated = 78588 bytes
Peak waste = 28910 bytes

Ok, this is still in an early phase of the development, so probably there are other low-hanging fruits to improve the performance and memory consumption. E.g. I just saw that the literal pool can also store numbers.

[LaszloLango]

Related PR (#813) was landed.