implement stack-based interpreter to improve performance #31

Siubaak · 2019-04-24T06:23:12Z

currently sval is a tree-walking interpreter and has a ordinary performance. compile the code into some kinds of intermediate representation based on stack to improve performance.

I have a demo as followed. it may be difficult and take some time to migrate.

const { parse } = require('acorn')
const { simple } = require('acorn-walk')

const ast = parse('1 + 8 * 2 / 2 + 1')

const stack = []

simple(ast, {
  Literal(node) {
    stack.push(node.value)
  },
  BinaryExpression(node) {
    const right = stack.pop()
    const left = stack.pop()
    const binaryOps = {
      '+': () => left + right,
      '-': () => left - right,
      '*': () => left * right,
      '/': () => left / right
    }
    const handler = binaryOps[node.operator]
    if (handler) {
      stack.push(handler())
    } else {
      throw new SyntaxError(`Unexpected token ${node.operator}`)
    }
  }
})

console.log(stack[0])

Siubaak · 2019-04-24T08:52:23Z

I just found an available register-based js vm, continuum. it did a great work, but unbelievable, its performance is even worse than sval. it makes me reconsider the performance of stack-based interperter written in js.

test case:

<!DOCTYPE html>
<html>
<body>
  <script src="https://unpkg.com/sval"></script>
  <script src="https://unpkg.com/continuum@0.3.5/continuum.js"></script>
  <script>
    const code = 'for(var i=0;i<100000;i++){}'
    for (let i = 0; i < 5; i++) {
      const interpreter = new Sval()
      console.time(`sval      ${i + 1}`)
      interpreter.run(code)
      console.timeEnd(`sval      ${i + 1}`)
      const realm = continuum.createRealm()
      console.time(`continuum ${i + 1}`)
      realm.evaluate(code)
      console.timeEnd(`continuum ${i + 1}`)
      console.log('')
    }
  </script>
</body>
</html>

result in chrome:

sval      1: 102.80810546875ms
continuum 1: 1341.805908203125ms

sval      2: 83.824951171875ms
continuum 2: 1551.010986328125ms

sval      3: 79.5869140625ms
continuum 3: 1698.853759765625ms

sval      4: 82.9951171875ms
continuum 4: 1470.83984375ms

sval      5: 83.164794921875ms
continuum 5: 1300.2099609375ms

bloody-ux · 2019-04-24T12:04:50Z

I don't think it's a good idea to create a VM with javascript. It just emits more code, needs more allocations and results in more GC.

Sval is great and easy. Firstly, we should try regular optimization ways such as cache critical paths, instead of rewriting the whole solution.

Take below case for example, it takes about 145ms on my Chrome 74.:

    const interpreter = new Sval();

    interpreter.run(`
    var x = 0;
    function functionOne() {
      x++;
    }
    
    var iterations = 100000;
    console.time('Function #1');
    for(var i = 0; i < iterations; i++ ){
      functionOne()
    };
    console.timeEnd('Function #1')
    
    console.log(x);
    `);

When optimizing with inline function, the time cost cuts down half to 75ms, one time faster!

  const interpreter = new Sval();

    interpreter.run(`
    var x = 0;
    function functionOne() {
      x++;
    }
    
    var iterations = 100000;
    console.time('Function #1');
    for(var i = 0; i < iterations; i++ ){
      x++;
    };
    console.timeEnd('Function #1')
    
    console.log(x);
    `);

By the way, I run the ES6 version of Sval, it's 20% ~ 25% faster than ES5 version

Siubaak · 2019-04-24T15:27:17Z

agree. I will think it over and try to cache something.

actually I don't mean to implement an entire vm. just to flatten the ast by compiling into ir or bytecode, in order to decrease the performance reduction caused by maintaining scopes.

bloody-ux · 2019-04-25T05:55:56Z

Top cost of the above for loop test case:

check property exists on object
get and set property to obj
get property from object
set property and create object
the updater cost a lot
get property from object

5/6 are about property setter/setter, it seems V8 doesn't have good property accessing performance, it should be faster, right? Let's take a look at below test case:

Accessing property with String key vs. number key:

const map = {};

const strKeys = new Array(100000);
const numKeys = new Array(100000);

for(var i=0; i< 100000; i++) {
  var key = 'Key' + i;
  strKeys[i] = key;
  numKeys[i] = i;
  map[key] = i;
  map[i] = i;
}

console.time('StrKey Lookup #1');

for(var i=0; i< 100000; i++) {
  var key = strKeys[i];
  var v = map[key];
  v = v + 1;
}
console.timeEnd('StrKey Lookup #1');

console.time('NumKey Lookup #1');

for(var i=0; i< 100000; i++) {
  var key = numKeys[i];
  var v = map[key];
  v = v + 1;
}
console.timeEnd('NumKey Lookup #1');

And here's the test result:

Surprise? Of course not, V8 blog gives us the explanation: named properties and indexed elements are different in V8.

For sval, we can build a data structure to deal with this, or use array instead of object to store data, and convert all string key(such as type) to number; And for those dynamic property setter, try to predefined the properties to reduce HiddenClass Generation. Say:

 var x  = {}
 x.a = 5;
 x.b = 6

=>

 var x  = {
  a: undefined,
  b: undefined
}
 x.a = 5;
 x.b = 6

Siubaak · 2019-04-25T06:38:02Z

cool

linear int keys allow us to malloc a linear continuous mem to store, and we can access the item by offsetting the pointer. but string keys need a hashtable to store the relationship between keys and indexes, in order to access the mem block by indexes to get the item. that's why int keys have a better performance.

so, to store a dict, we need a hashtable and an array actually. if we store the data in a array, we still need a map/hashtable/object to maintain the mapping relationship between keys and indexes, which takes the same time as we directly store at a object. to avoid this problem and just use a array to store data, we need a stack-based interpreter instead of register-based or tree-walking interpreter.

as you say, the predefinition of dynamic properties has a similar meaning of hoisting variables and functions. I am working on it now, predefining the variables and functions when creating scope, instead of mounting them on the scope context after creating.

Siubaak · 2019-05-08T09:18:18Z

fengari did a great job of running lua over js. mark for reference - Fengari

<script src="./fengari-web.js"></script>
<script type="application/lua">
  local start = os.time()
  for i=1, 10000000 do
  end
  print(os.time() - start) -- 0~1s cool :)
</script>
<script src="https://unpkg.com/sval"></script>
<script>
  const interpreter = new Sval()
  interpreter.run(`
    var start = Date.now()
    for (var i = 0; i < 10000000; i++) {}
    console.log((Date.now() - start) / 1000) // around 6s :(
  `)
</script>

Siubaak · 2019-06-22T15:47:15Z

currently a stack-based interpreter has been roughly accomplished. a brenchmark demo can be found in #3b660d4, and the interpreter has a great performance promotion lol.

const interpreter = new Sval()
interpreter.run(`
  var start = Date.now()
  for (var i = 0; i < 10000000; i++) {}
  console.log((Date.now() - start) / 1000) // 3.45s now :D
`)

Llorx · 2019-07-04T12:10:14Z

When will this performance improvements reach master branch? Any ETA? I'm looking into moving from Interpreter-JS to Sval.

PD: Quite a nice job.

Siubaak · 2019-07-04T15:20:22Z

When will this performance improvements reach master branch? Any ETA? I'm looking into moving from Interpreter-JS to Sval.

PD: Quite a nice job.

I will try to complete in August

etamponi · 2019-08-27T17:29:47Z

Hi :) sorry for the double post, I would love to use Sval too! Do you confirm end of August as a possible release date for the performance improvements? :)

Thank you and great job!!!

Siubaak · 2019-08-29T12:29:24Z

Hi :) sorry for the double post, I would love to use Sval too! Do you confirm end of August as a possible release date for the performance improvements? :)

Thank you and great job!!!

Nope. I don't have time to handle it this month, and I'm not sure when I can finish. :(

etamponi · 2019-08-29T13:25:16Z

That's fine anyway, thank you! :) Looking forward to seeing it completed!

brianjenkins94 · 2021-08-08T19:52:13Z

Any update? What's left to do? :)

Siubaak changed the title ~~implement stack-based interpreter instead of tree-walking interpreter to improve performance~~ implement stack-based interpreter to improve performance Apr 24, 2019

Siubaak pinned this issue Apr 24, 2019

Siubaak added the enhancement New feature or request label Apr 24, 2019

Siubaak self-assigned this Apr 24, 2019

Siubaak mentioned this issue Apr 24, 2019

performance issue for 'loop' #12

Closed

Siubaak closed this as completed Apr 24, 2019

Siubaak reopened this Apr 24, 2019

Siubaak added a commit that referenced this issue May 14, 2019

[Update] Improve performance (issue #31)

21f74ef

Siubaak added a commit that referenced this issue May 14, 2019

[Update] A for demo of stack-based interpreter #31

e1b3e36

Siubaak added a commit that referenced this issue Jun 22, 2019

[Update] Add a brenchmark for #31

3b660d4

Siubaak mentioned this issue Sep 5, 2019

Serializable interpreter? #45

Closed

Siubaak mentioned this issue Nov 4, 2019

ReferenceError xxx is not defined #49

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

implement stack-based interpreter to improve performance #31

implement stack-based interpreter to improve performance #31

Siubaak commented Apr 24, 2019 •

edited

Loading

Siubaak commented Apr 24, 2019

bloody-ux commented Apr 24, 2019 •

edited

Loading

Siubaak commented Apr 24, 2019 •

edited

Loading

bloody-ux commented Apr 25, 2019 •

edited

Loading

Siubaak commented Apr 25, 2019 •

edited

Loading

Siubaak commented May 8, 2019

Siubaak commented Jun 22, 2019

Llorx commented Jul 4, 2019 •

edited

Loading

Siubaak commented Jul 4, 2019

etamponi commented Aug 27, 2019

Siubaak commented Aug 29, 2019

etamponi commented Aug 29, 2019

brianjenkins94 commented Aug 8, 2021

implement stack-based interpreter to improve performance #31

implement stack-based interpreter to improve performance #31

Comments

Siubaak commented Apr 24, 2019 • edited Loading

Siubaak commented Apr 24, 2019

bloody-ux commented Apr 24, 2019 • edited Loading

Siubaak commented Apr 24, 2019 • edited Loading

bloody-ux commented Apr 25, 2019 • edited Loading

Siubaak commented Apr 25, 2019 • edited Loading

Siubaak commented May 8, 2019

Siubaak commented Jun 22, 2019

Llorx commented Jul 4, 2019 • edited Loading

Siubaak commented Jul 4, 2019

etamponi commented Aug 27, 2019

Siubaak commented Aug 29, 2019

etamponi commented Aug 29, 2019

brianjenkins94 commented Aug 8, 2021

Siubaak commented Apr 24, 2019 •

edited

Loading

bloody-ux commented Apr 24, 2019 •

edited

Loading

Siubaak commented Apr 24, 2019 •

edited

Loading

bloody-ux commented Apr 25, 2019 •

edited

Loading

Siubaak commented Apr 25, 2019 •

edited

Loading

Llorx commented Jul 4, 2019 •

edited

Loading