why the fastify (a new node web framework) is so fast?(为什么fastify这么快呢？)

have you ever thought about JSON.stringify?

Does JSON.stringify be fast enough? Can we improve the speed of it? The first idea comes into my mind is whether I can use C/C++ rewrite it? Cause there may be many redundant checks in V8 of it, whether I can discard them. But it may be wrong, stringify JSON object needs read it to judge the type of the JSON primitive type, may string, object or array etc.

Yeah, we must do that to analyze its typed to transform it to JSON string. But if we know the type, in another way that we have known the structure of the object. That means we don't need to analyze the type one by one anymore. Assume that we have a schema like below

{

    type: 'object',
    properties: {    
        firstName: {
          type: 'string'
        },
        lastName: {
          type: 'string'
        },
        age: {
          description: 'Age in years',
          type: 'integer'
        },
        reg: {
          type: 'string'
        }
  }
}

so we must know the JSON object of this schema is an object having a property of string named firstName. so when we stringify it, we only add "{" at the start and "}" at the end, and also can add ' \"fisrtName\": ' follow the "{" according to the schema. Analyze the schema is cheap. Analyzing the object without knowing anything is difficult. Oh yeah, that's amazing.

1. the first Engine accelerator of the fastify is the fast-json-stringify 2x than JSON.stringify

The main principle of this package is the seem as we are talking above.

const fastJson = require('fast-json-stringify')
const stringify = fastJson({
  title: 'Example Schema',
  type: 'object',
  properties: {
    firstName: {
      type: 'string'
    },
    lastName: {
      type: 'string'
    },
    age: {
      description: 'Age in years',
      type: 'integer'
    },
    reg: {
      type: 'string'
    }
  }
})

console.log(stringify({
  firstName: 'Matteo',
  lastName: 'Collina',
  age: 32,
  reg: /"([^"]|\\")*"/
}))

we can dig into the generated ‘stringify’ function

function $main(input) {
  var obj = typeof input.toJSON === 'function'
    ? input.toJSON()
    : input
  // it's object we can add '{' directly
  var json = '{'
  var addComma = false
  // whether has fisrtName
  if (obj[ 'firstName' ] !== undefined) {

    if (addComma) {
      json += ','
    }
    addComma = true

    json += '"firstName":'

    json += $asString(obj[ 'firstName' ])

  }
  // whether has lastName
  if (obj[ 'lastName' ] !== undefined) {

    if (addComma) {
      json += ','
    }
    addComma = true

    json += '"lastName":'

    json += $asString(obj[ 'lastName' ])

  }

  var rendered = false
  // whether has age
  var t = Number(obj[ 'age' ])
  if (!isNaN(t)) {

    if (addComma) {
      json += ','
    }
    addComma = true

    json += '"age":' + t
    rendered = true
  }

  if (rendered) {

  }
  // where has reg
  if (obj[ 'reg' ] !== undefined) {

    if (addComma) {
      json += ','
    }
    addComma = true

    json += '"reg":'

    json += $asString(obj[ 'reg' ])

  }

  json += '}'
  return json
}
// {"firstName":"Matteo","lastName":"Collina","age":32,"reg":"\"([^\"]|\\\\\")*\""}

As shown above， that's so simple. There is a benchmark on Node 10.4.0:

JSON.stringify array x 3,269 ops/sec ±1.48% (86 runs sampled)
fast-json-stringify array x 5,945 ops/sec ±1.51% (87 runs sampled)
fast-json-stringify-uglified array x 5,720 ops/sec ±1.18% (89 runs sampled)
JSON.stringify long string x 9,325 ops/sec ±1.22% (88 runs sampled)
fast-json-stringify long string x 9,678 ops/sec ±0.99% (92 runs sampled)
fast-json-stringify-uglified long string x 9,578 ops/sec ±1.12% (92 runs sampled)
JSON.stringify short string x 3,307,218 ops/sec ±1.54% (92 runs sampled)
fast-json-stringify short string x 28,213,341 ops/sec ±1.72% (83 runs sampled)
fast-json-stringify-uglified short string x 29,130,846 ops/sec ±1.34% (87 runs sampled)
JSON.stringify obj x 1,441,648 ops/sec ±2.14% (87 runs sampled)
fast-json-stringify obj x 5,345,003 ops/sec ±1.02% (91 runs sampled)
fast-json-stringify-uglified obj x 5,331,581 ops/sec ±0.73% (91 runs sampled)

It's extremely fast. The last question is where fastify use it. Obviously using it in validation and reply.

2. about how v8 stores string: the second acceleration engine

flatstr is a package that makes some string's operation so fast. The homepage's section 'how it works' has explained it very clear in English.

Next is Chinese translation:

v8里面有两种处理字符串的方式

作为一个数组
构造一颗树

当我们处理字符串连接的时候，v8使用的是树结构。对于连接操作（concat）, 构造一棵树明显比重新分配一块大的内存来的划算（大家可以思考一下为什么）。但是有一些其他操作树结构反而会带来更多的损耗（比如大量的字符串连接操作，大家又可以思考一下为什么了）。

V8里面有个内置函数叫String::Flatten, 它能够把树状的字符串结构再转化为C的数组形式。这个方法通常会在遍历字符串这个操作之前被调用(比如：测试一个正则表达式)。在多次使用一个字符串时也会调用这个方法来作为优化。但这个方法并不是在所有的字符串操作时都会调用，比如我们传递一个字符串给WriteStream这个方法，此时字符串会被转为buffer, 但如果字符串的底层结构是树的话，这个转换操作就会很昂贵（至于为什么昂贵？留待下次探查，或者你们谁来追查一下？）。

关键在于String::Flatten并不是js的内置方法其实是v8独有的，但我们还是有办法触发这个方法的。

在（alt-benchmark.js）里面列举了一些可以触发这个方法的调用。其中转换成Number是代价最小的了。

但是自从Node10开始刚才我们所说的那些能触发Flatten的调用的操作V8都不会再去调用Flatten了。但没关系我们还可以通过'--allow-natives-syntax'这个flag来手动调用


'use strict'

if (!process.versions || !process.versions.node || parseInt(process.versions.node.split('.')[0]) >= 10) {
  try { 
    var flatstr = Function('s', 'return typeof s === "string" ? %FlattenString(s) : s')
  } catch (e) {
    try { 
      // who can tell me why write 'v' + '8'?
      var v8 = require('v' + '8')
      v8.setFlagsFromString('--allow-natives-syntax')
      var flatstr = Function('s', 'return typeof s === "string" ? %FlattenString(s) : s')
      v8.setFlagsFromString('--no-allow-natives-syntax')
    } catch (e) {
      var flatstr = function flatstr(s) {
        Number(s)
        return s
      }
    }
  }
} else flatstr = function flatstr(s) {
  Number(s)
  return s
}

module.exports = flatstr

如上就是Flatten的调用方式以及Node10以下的触发方式。其实这也是这个包的所有代码（不含测试等其他）。。。(求解释上面那个v8的引用方式。。。)

benchmark （fs.WriteStream）

unflattenedManySmallConcats*10000: 147.540ms
flattenedManySmallConcats*10000: 105.994ms
unflattenedSeveralLargeConcats*10000: 287.901ms
flattenedSeveralLargeConcats*10000: 226.121ms
unflattenedExponentialSmallConcats*10000: 410.533ms
flattenedExponentialSmallConcats*10000: 219.973ms
unflattenedExponentialLargeConcats*10000: 2774.230ms
flattenedExponentialLargeConcats*10000: 1862.815ms

可以看出基本都是flatstr 胜出的

ManySmallConcats: 28%
SeveralLargeConcats: 21% 
ExponentialSmallConcats: 46%
ExponentialLargeConcats: 33%

最后需要注意的就是，物极必反，也不要太过于频繁的调用Flatten。毕竟他也是有性能损耗的。V8已经替我们做了很多的优化，我们就不要随便插手了。因此Flatten的正确使用方式应该是在传递字符串给非V8的代码：比如fs.WriteStream, xhr, DOM api等等。

V8内置函数列表

So where fastify use flatstr? in the http reply, cause the data will be passed to WriteSteam

3. the third Engine accelerator: radix tree--router matching

Fastify's router package is find-my-way based on radix tree akka compact Prefix Tree

Three picture explains radix clearly

Yeah every route path is mapped to a branch of the tree.

Insert 'water' at the root

Insert 'slower' while keeping 'slow'

insert 'tester' which is a prefix of 'tester'

Insert 'team' while splitting 'test' and creating a new edge label 'st'

Insert 'toast' while splitting 'te' and moving previous strings a level lower

Search for 'toasting'

Clearly radix tree is not a balanced trees so the cost is O(k) rather then O(log n), an K >= log n and K <= M(total of words or routes)

Compared to Array[M] (koa-router & express-router) it will be more efficient. Cause it needs lower comparison.

Compared to hash router it will be efficient too, even though hash time is O(1). Cause we need compute hash of the routes when use it. The most drawbacks of hash are that it does not support params and any (*) matches.

Another radix-router impletion in go echo

Conclusion

That's all? no

Far from enough. We still need to dig into fastify deeper

References

radix tree wiki

take-your-http-server-to-ludicrous-speed

hello2dj / blog