Repository: delvedor/find-my-way (js)

Issue:
fast-decode-uri-component isn't really fast
### fast-decode-uri-component isn't really fast

During my investigation of #206 problem I was playing with `fast-decode-uri-component` in order to create `fast-decode-uri` that would work exactly as `decodeURI`. During my own benchmarking I was never able to beat the standard `decodeURI`. The reason for that, as I found later, was the test data. 

In `fast-decode-uri-component` they use a lot of malformed URIs for benchmarking. The standard `decodeURIComponent` processes malformed URIs extremely slow. But when you use proper URIs the default function works 2-3 times faster than the "fast" one. 

How many URIs are malformed on a highly loaded API? The only way to get malformed URI is to manually mess it up in browser or misconfigure a new integration (which eventually will be fixed). It's quite counterproductive to optimize the framework to process malformed URIs faster and process proper URIs slower.

My suggestion is to get rid of the `fast-decode-uri-component` and use safe and a little fastified version of the standard function like I show in benchmark below. That will work 2-3 times faster on properly formatted URIs.

The benchmark:
```js
const bench = require('nanobench')
const fastDecode = require('fast-decode-uri-component')

const uri = [ 
  encodeURIComponent(' /?!#@=[](),\'"'),
  encodeURIComponent('много русских букв'),
  encodeURIComponent('acde=bdfd'),
  encodeURIComponent('這裡有些話'),
  encodeURIComponent('कुछ शब्द यहाँ'),
  encodeURIComponent('algunas palabras aquí'),
  encodeURIComponent('✌👀🎠🎡🍺')
]

function safeDecodeURIComponent(uri) {
  if (uri.indexOf('%') < 0) return uri
  try {
    return decodeURIComponent(uri)
  } catch (e) {
    return uri // or it can be null
  }
}

const uriLen = uri.length

bench('fast-decode-uri-component', b => {
  b.start()
  for (var round = 0; round < 100000; round++) {
    for (var i = 0; i < uriLen; i++) {
      fastDecode(uri[i])
    }
  }
  b.end()
})

bench('decodeURIComponent', b => {
  b.start()
  for (var round = 0; round < 100000; round++) {
    for (var i = 0; i < uriLen; i++) {
      safeDecodeURIComponent(uri[i])
    }
  }
  b.end()
})
```

As a result the standard function works 2.8 times faster:
```
# fast-decode-uri-component
ok ~512 ms (0 s + 511994600 ns)

# decodeURIComponent
ok ~182 ms (0 s + 182000400 ns)

all benchmarks completed
ok ~694 ms (0 s + 693995000 ns)
```

Pull request description:
feat: decodeUriParameters option
Closes #208 

The bench show how the `decodeURIComponent` vs `fast-decode-uri-component` has big differences based on the string that is being decoded.

I think `fast-decode-uri-component` is the best default for most use cases, but when the encoded character is more than 1 byte (UTF8) the `fast-decode-uri-component` performance drop.

This happens for no [Basic Latin](https://en.wikipedia.org/wiki/List_of_Unicode_characters#Basic_Latin) chars mainly.

It depends on the dev's implementation, of course, using alphanumeric IDs as path parameters do not decrease performance.

```

safeDecodeURIComponent(0) [' /?!#@=[](),\'"'] x 5,267,664 ops/sec ±0.23% (596 runs sampled)
fastDecode(0) [' /?!#@=[](),\'"'] x 3,136,283 ops/sec ±0.14% (596 runs sampled)
safeFastDecode(0) [' /?!#@=[](),\'"'] x 3,050,964 ops/sec ±0.17% (593 runs sampled)

safeDecodeURIComponent(1) [algunas palabras aqu%C3%AD] x 4,035,201 ops/sec ±0.14% (596 runs sampled)
fastDecode(1) [algunas palabras aqu%C3%AD] x 7,370,159 ops/sec ±0.14% (593 runs sampled)
safeFastDecode(1) [algunas palabras aqu%C3%AD] x 7,266,197 ops/sec ±0.24% (594 runs sampled)

safeDecodeURIComponent(2) [acde=bdfd] x 5,861,834 ops/sec ±0.16% (595 runs sampled)
fastDecode(2) [acde=bdfd] x 18,022,100 ops/sec ±0.20% (590 runs sampled)
safeFastDecode(2) [acde=bdfd] x 17,798,798 ops/sec ±0.24% (588 runs sampled)

safeDecodeURIComponent(3) [много русских букв] x 3,069,028 ops/sec ±0.17% (595 runs sampled)
fastDecode(3) [много русских букв] x 872,223 ops/sec ±0.18% (593 runs sampled)
safeFastDecode(3) [много русских букв] x 862,030 ops/sec ±0.29% (593 runs sampled)

safeDecodeURIComponent(4) [這裡有些話] x 5,252,010 ops/sec ±0.18% (594 runs sampled)
fastDecode(4) [這裡有些話] x 2,170,177 ops/sec ±0.15% (594 runs sampled)
safeFastDecode(4) [這裡有些話] x 2,153,915 ops/sec ±0.18% (594 runs sampled)

safeDecodeURIComponent(5) [कुछ शब्द यहाँ] x 3,520,488 ops/sec ±0.19% (595 runs sampled)
fastDecode(5) [कुछ शब्द यहाँ] x 842,579 ops/sec ±0.26% (595 runs sampled)
safeFastDecode(5) [कुछ शब्द यहाँ] x 837,686 ops/sec ±0.18% (595 runs sampled)

safeDecodeURIComponent(6) [✌👀🎠🎡🍺] x 4,212,286 ops/sec ±0.23% (593 runs sampled)
fastDecode(6) [✌👀🎠🎡🍺] x 1,650,773 ops/sec ±0.15% (595 runs sampled)
safeFastDecode(6) [✌👀🎠🎡🍺] x 1,691,189 ops/sec ±0.14% (596 runs sampled)

```

The nice-to-have would be optimizing the `fast-decode-uri-component` for this use case.

Patch:
diff --git a/README.md b/README.md
index d7f8146..b54b4f7 100644
--- a/README.md
+++ b/README.md
@@ -323,6 +323,20 @@ Having a route with multiple parameters may affect negatively the performance, s
 
 **Note** that you must encode the parameters containing [reserved characters](https://www.rfc-editor.org/rfc/rfc3986#section-2.2).
 
+If your routes' parameters are not Basic Latin charaters, you may face a performance drop. To avoid it, you can customize the way the parameters are parsed by passing a custom decoding function. Read more about it [here](https://github.com/delvedor/find-my-way/pull/211).
+The parsing function is called when the request URL contains one or more encoded special characters: `# $ & + , / : ; = ? @`.
+
+```js
+const router = require('find-my-way')({
+  decodeUriParameters: (stringToDecode) => {
+    // called when the request URL contains st least one special character: `# $ & + , / : ; = ? @`
+    return decodeURIComponent(stringToDecode)
+  }
+})
+```
+
+By default, this module relies on [fast-decode-uri-component`](https://www.npmjs.com/package/fast-decode-uri-component) to parse the encoded path parameters.
+
 <a name="match-order"></a>
 ##### Match order
 
diff --git a/bench-decoding.js b/bench-decoding.js
new file mode 100644
index 0000000..83ee3a3
--- /dev/null
+++ b/bench-decoding.js
@@ -0,0 +1,55 @@
+'use strict'
+
+const fastDecode = require('fast-decode-uri-component')
+
+const Benchmark = require('benchmark')
+Benchmark.options.minSamples = 500
+
+const suite = Benchmark.Suite()
+
+const uri = [
+  encodeURIComponent(' /?!#@=[](),\'"'),
+  encodeURIComponent('algunas palabras aquí'),
+  encodeURIComponent('acde=bdfd'),
+  encodeURIComponent('много русских букв'),
+  encodeURIComponent('這裡有些話'),
+  encodeURIComponent('कुछ शब्द यहाँ'),
+  encodeURIComponent('✌👀🎠🎡🍺')
+]
+
+function safeFastDecode (uri) {
+  if (uri.indexOf('%') < 0) return uri
+  try {
+    return fastDecode(uri)
+  } catch (e) {
+    return null // or it can be null
+  }
+}
+
+function safeDecodeURIComponent (uri) {
+  if (uri.indexOf('%') < 0) return uri
+  try {
+    return decodeURIComponent(uri)
+  } catch (e) {
+    return null // or it can be null
+  }
+}
+
+uri.forEach(function (u, i) {
+  suite.add(`safeDecodeURIComponent(${i}) [${u}]`, function () {
+    safeDecodeURIComponent(u)
+  })
+  suite.add(`fastDecode(${i}) [${u}]`, function () {
+    fastDecode(u)
+  })
+  suite.add(`safeFastDecode(${i}) [${u}]`, function () {
+    safeFastDecode(u)
+  })
+})
+suite
+  .on('cycle', function (event) {
+    console.log(String(event.target))
+  })
+  .on('complete', function () {
+  })
+  .run()
diff --git a/index.js b/index.js
index 9bfd2c4..aa4bbad 100644
--- a/index.js
+++ b/index.js
@@ -73,6 +73,11 @@ function Router (opts) {
     this.buildPrettyMeta = defaultBuildPrettyMeta
   }
 
+  if (opts.decodeUriParameters) {
+    assert(typeof opts.decodeUriParameters === 'function', 'decodeUriParameters must be a function')
+    this.decodeUriParameters = opts.decodeUriParameters
+  }
+
   this.caseSensitive = opts.caseSensitive === undefined ? true : opts.caseSensitive
   this.ignoreTrailingSlash = opts.ignoreTrailingSlash || false
   this.maxParamLength = opts.maxParamLength || 100
@@ -402,7 +407,7 @@ Router.prototype.find = function find (method, path, derivedConstraints) {
 
   let sanitizedUrl
   try {
-    sanitizedUrl = sanitizeUrl(path)
+    sanitizedUrl = sanitizeUrl(path, this.decodeUriParameters)
     path = sanitizedUrl.path
   } catch (error) {
     return this._onBadUrl(path)
diff --git a/lib/url-sanitizer.js b/lib/url-sanitizer.js
index 3fba906..a0ef94c 100644
--- a/lib/url-sanitizer.js
+++ b/lib/url-sanitizer.js
@@ -29,7 +29,7 @@ uriComponentsCharMap[51][102] = true // ? '%3f'
 uriComponentsCharMap[52] = new Array(49).fill(0x00)
 uriComponentsCharMap[52][48] = true // @ '%40'
 
-function sanitizeUrl (url) {
+function sanitizeUrl (url, customDecoder) {
   let originPath = url
   let shouldDecode = false
   let containsEncodedComponents = false
@@ -70,14 +70,14 @@ function sanitizeUrl (url) {
       ? sliceAndDecode
       : slicePath
   }
+
+  function sliceAndDecode (from, to) {
+    return (customDecoder || fastDecode)(this.originPath.slice(from, to))
+  }
 }
 
 module.exports = sanitizeUrl
 
-function sliceAndDecode (from, to) {
-  return fastDecode(this.originPath.slice(from, to))
-}
-
 function slicePath (from, to) {
   return this.path.slice(from, to)
 }


Test patch:
diff --git a/test/custom-decode-uri.test.js b/test/custom-decode-uri.test.js
new file mode 100644
index 0000000..b00b6da
--- /dev/null
+++ b/test/custom-decode-uri.test.js
@@ -0,0 +1,69 @@
+'use strict'
+
+const t = require('tap')
+const test = t.test
+const FindMyWay = require('../')
+
+test('decodeUriParameters wrong setup', t => {
+  t.plan(1)
+
+  try {
+    FindMyWay({
+      decodeUriParameters: 'not a function'
+    })
+  } catch (error) {
+    t.equal(error.message, 'decodeUriParameters must be a function')
+  }
+})
+
+test('decodeUriParameters called when needed 1', t => {
+  t.plan(2)
+
+  const findMyWay = FindMyWay({
+    decodeUriParameters: (stringToDecode) => {
+      t.fail('the function is not called')
+    }
+  })
+
+  findMyWay.on('GET', '/foo bar', () => {})
+  findMyWay.on('GET', '/:foo/bar', () => {})
+
+  t.ok(findMyWay.find('GET', '/foo%20bar').handler)
+  t.ok(findMyWay.find('GET', '/ci@o/bar').handler)
+})
+
+test('decodeUriParameters called when needed 2', t => {
+  t.plan(10)
+
+  const results = [
+    'ci%40o',
+    'foo%23bar',
+    '%23%F'
+  ]
+  const findMyWay = FindMyWay({
+    decodeUriParameters: (stringToDecode) => {
+      t.equal(stringToDecode, results.shift(), `decoding ${stringToDecode}`)
+      return 'crazy'
+    }
+  })
+
+  const notCrazy = () => {}
+  const paramHandler = () => {}
+
+  findMyWay.on('GET', '/foo bar', notCrazy)
+  findMyWay.on('GET', '/foo#bar', notCrazy)
+  findMyWay.on('GET', '/:param/bar', paramHandler)
+  findMyWay.on('GET', '/:param', paramHandler)
+
+  t.equal(findMyWay.find('GET', '/foo%20bar').handler, notCrazy)
+  t.equal(findMyWay.find('GET', '/ci%40o/bar').handler, paramHandler)
+  t.equal(findMyWay.find('GET', '/foo%23bar').handler, paramHandler)
+
+  const bananaRoute = findMyWay.find('GET', '/%F0%9F%8D%8C')
+  t.equal(bananaRoute.handler, paramHandler)
+  t.same(bananaRoute.params, { param: '🍌' })
+
+  const crazyRoute = findMyWay.find('GET', '/%23%F0%9F%8D%8C')
+  t.equal(crazyRoute.handler, paramHandler)
+  t.same(crazyRoute.params, { param: 'crazy' })
+})