{"action":"created","issue":{"url":"https://api.github.com/repos/svaarala/duktape/issues/411","labels_url":"https://api.github.com/repos/svaarala/duktape/issues/411/labels{/name}","comments_url":"https://api.github.com/repos/svaarala/duktape/issues/411/comments","events_url":"https://api.github.com/repos/svaarala/duktape/issues/411/events","html_url":"https://github.com/svaarala/duktape/pull/411","id":112876063,"number":411,"title":"Add an optional 128kB lookup to optimize regexp canonicalization","user":{"login":"svaarala","id":6377415,"avatar_url":"https://avatars.githubusercontent.com/u/6377415?v=3","gravatar_id":"","url":"https://api.github.com/users/svaarala","html_url":"https://github.com/svaarala","followers_url":"https://api.github.com/users/svaarala/followers","following_url":"https://api.github.com/users/svaarala/following{/other_user}","gists_url":"https://api.github.com/users/svaarala/gists{/gist_id}","starred_url":"https://api.github.com/users/svaarala/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/svaarala/subscriptions","organizations_url":"https://api.github.com/users/svaarala/orgs","repos_url":"https://api.github.com/users/svaarala/repos","events_url":"https://api.github.com/users/svaarala/events{/privacy}","received_events_url":"https://api.github.com/users/svaarala/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/svaarala/duktape/labels/performance","name":"performance","color":"fbca04"}],"state":"open","locked":false,"assignee":null,"milestone":{"url":"https://api.github.com/repos/svaarala/duktape/milestones/13","html_url":"https://github.com/svaarala/duktape/milestones/v1.4.0","labels_url":"https://api.github.com/repos/svaarala/duktape/milestones/13/labels","id":1225990,"number":13,"title":"v1.4.0","description":"Call handling, Emscripten performance","creator":{"login":"svaarala","id":6377415,"avatar_url":"https://avatars.githubusercontent.com/u/6377415?v=3","gravatar_id":"","url":"https://api.github.com/users/svaarala","html_url":"https://github.com/svaarala","followers_url":"https://api.github.com/users/svaarala/followers","following_url":"https://api.github.com/users/svaarala/following{/other_user}","gists_url":"https://api.github.com/users/svaarala/gists{/gist_id}","starred_url":"https://api.github.com/users/svaarala/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/svaarala/subscriptions","organizations_url":"https://api.github.com/users/svaarala/orgs","repos_url":"https://api.github.com/users/svaarala/repos","events_url":"https://api.github.com/users/svaarala/events{/privacy}","received_events_url":"https://api.github.com/users/svaarala/received_events","type":"User","site_admin":false},"open_issues":66,"closed_issues":33,"state":"open","created_at":"2015-07-26T04:06:08Z","updated_at":"2015-10-22T19:40:16Z","due_on":null,"closed_at":null},"comments":2,"created_at":"2015-10-22T19:40:16Z","updated_at":"2015-10-22T20:28:36Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/svaarala/duktape/pulls/411","html_url":"https://github.com/svaarala/duktape/pull/411","diff_url":"https://github.com/svaarala/duktape/pull/411.diff","patch_url":"https://github.com/svaarala/duktape/pull/411.patch"},"body":"In Duktape 1.3.0 and prior case-insensitive RegExps with large unicode ranges have serious performance issues. Example regexp:\r\n\r\n```js\r\nvar re = /[\\u0000-\\uffff]/i;\r\n```\r\n\r\nThis is most likely the root cause behind this Netsurf issue (and at least another similar one):\r\n\r\n- http://bugs.netsurf-browser.org/mantis/view.php?id=2366\r\n\r\nThe performance issue is caused by two algorithms interacting (neither alone would be a major issue):\r\n\r\n- A continuous Unicode range may be split into multiple discontinuous ranges when it is canonicalized, so it's not enough to canonicalize the endpoints. The current simple approach is to run through the range codepoints, normalize each, and then detect the canonicalized ranges from the conversion output. This is a loop of ~64k canonicalizations for each `[\\u0000-\\uffff]` range in the case insensitive regexp source.\r\n- Each canonicalization in turn runs through the size-optimized bit-packed Unicode data which doesn't have an index, so potentially hundreds of ranges are scanned. This exacerbates the problem quite a bit.\r\n\r\nThis branch has a very simple fix where a 65536-entry lookup table is used for the canonicalization operation, which should fix the immedate issue for environments where this is a practical issue:\r\n\r\n```\r\n$ time ./duk.O2.130 tests/perf/test-regexp-case-insensitive.js\r\n\r\nreal\t0m23.962s\r\nuser\t0m23.918s\r\nsys\t0m0.003s\r\n\r\n$ time ./duk.O2 tests/perf/test-regexp-case-insensitive.js\r\n\r\nreal\t0m0.019s\r\nuser\t0m0.018s\r\nsys\t0m0.003s\r\n```\r\n\r\nThis is a short term solution and the lookup table won't be enabled by default because the footprint impact is quite large.\r\n\r\nA proper medium term solution is to use a better algorithm for handling case-insensitive RegExp ranges, and to make the Unicode data indexed and faster to work with for non-low-memory targets. It should be possible to get a similar improvement with much, much smaller footprint impact.\r\n\r\nTasks:\r\n\r\n- [ ] Add a config option, disabled by default\r\n- [ ] Ensure the change fixes the original Netsurf issue (also validates that root cause is understood)\r\n- [ ] Try to find a better short term solution without reworking the Unicode tables yet\r\n- [ ] Resolve FIXMEs\r\n- [ ] Releases entry"},"comment":{"url":"https://api.github.com/repos/svaarala/duktape/issues/comments/150347370","html_url":"https://github.com/svaarala/duktape/pull/411#issuecomment-150347370","issue_url":"https://api.github.com/repos/svaarala/duktape/issues/411","id":150347370,"user":{"login":"svaarala","id":6377415,"avatar_url":"https://avatars.githubusercontent.com/u/6377415?v=3","gravatar_id":"","url":"https://api.github.com/users/svaarala","html_url":"https://github.com/svaarala","followers_url":"https://api.github.com/users/svaarala/followers","following_url":"https://api.github.com/users/svaarala/following{/other_user}","gists_url":"https://api.github.com/users/svaarala/gists{/gist_id}","starred_url":"https://api.github.com/users/svaarala/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/svaarala/subscriptions","organizations_url":"https://api.github.com/users/svaarala/orgs","repos_url":"https://api.github.com/users/svaarala/repos","events_url":"https://api.github.com/users/svaarala/events{/privacy}","received_events_url":"https://api.github.com/users/svaarala/received_events","type":"User","site_admin":false},"created_at":"2015-10-22T20:28:36Z","updated_at":"2015-10-22T20:28:36Z","body":"The footprint impact is 64k entries of 16-bit codepoints -> 128kB."}}