{"action":"opened","issue":{"url":"https://api.github.com/repos/atom/node-oniguruma/issues/45","labels_url":"https://api.github.com/repos/atom/node-oniguruma/issues/45/labels{/name}","comments_url":"https://api.github.com/repos/atom/node-oniguruma/issues/45/comments","events_url":"https://api.github.com/repos/atom/node-oniguruma/issues/45/events","html_url":"https://github.com/atom/node-oniguruma/issues/45","id":119474044,"number":45,"title":"Super slow tokenization of long strings containing multi-byte characters","user":{"login":"alexandrudima","id":5047891,"avatar_url":"https://avatars.githubusercontent.com/u/5047891?v=3","gravatar_id":"","url":"https://api.github.com/users/alexandrudima","html_url":"https://github.com/alexandrudima","followers_url":"https://api.github.com/users/alexandrudima/followers","following_url":"https://api.github.com/users/alexandrudima/following{/other_user}","gists_url":"https://api.github.com/users/alexandrudima/gists{/gist_id}","starred_url":"https://api.github.com/users/alexandrudima/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/alexandrudima/subscriptions","organizations_url":"https://api.github.com/users/alexandrudima/orgs","repos_url":"https://api.github.com/users/alexandrudima/repos","events_url":"https://api.github.com/users/alexandrudima/events{/privacy}","received_events_url":"https://api.github.com/users/alexandrudima/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":0,"created_at":"2015-11-30T11:30:16Z","updated_at":"2015-11-30T11:30:16Z","closed_at":null,"body":"From Microsoft/vscode#94\r\n\r\nI think this impacts also atom on Mac/Linux. Possible repro steps for atom / first-mate:\r\n* In first-mate/benchmark/large.min.js\r\n* on a long line (e.g. line 4)\r\n* insert a multi-byte character such as ü\r\n* run the benchmark\r\n* observe super slow times\r\n\r\nI believe the root cause of the slowness is the charOffset <-> byteOffset conversion:\r\n* https://github.com/atom/node-oniguruma/blob/master/src/onig-searcher.cc#L11\r\n* that goes into https://github.com/atom/node-oniguruma/blob/master/src/unicode-utils-posix.cc#L38\r\n* this makes any string containing multi-byte characters match in O(N^2), since at every advancing step, the code loops back to compute the conversion\r\n\r\nIn my opinion, the only way to make this conversion fast is to compute it once up-front and use memoization for the conversions. However, the current caching mechanism is sub optimal since each string is cached per `OnigScanner`. So, if a line needs 20 `OnigScanner`'s to tokenize, the conversion would still happen 20 times. The current caching mechanism is also \"leakish\" as each `OnigScanner` keeps references to the last matched string. Moreover, the current caching mechanism forces users of node-oniguruma to reuse to the maximum possible extent a certain `OnigScanner` instance in order to get caching.\r\n\r\nI think that the users of node-oniguruma know best when and how they want to match a certain string.\r\n\r\nI would like, when I get some free time, to work on a PR that does the following:\r\n * introduces & exposes to JS a new type called `OnigString`\r\n * the `OnigString` will compute the conversion up-front in its ctor.\r\n * the `OnigString` will provide cache slots for all `OnigRegExp`.\r\n * the `OnigString` has its lifecycle controlled by v8, so when javascript dereferences it, all cache slots and cached conversion is GCed.\r\n * make `OnigRegExp::Search` cached by only accepting an `OnigString`. We will therefore get that each individual regular expression is using the cache (no more need to do the trick with a `OnigScanner` with precisely one regular expression)\r\n * make `OnigScanner::FindNextMatchSync` accept a `v8String` or an `OnigString`. If it is called with a `v8String` it immediately constructs an `OnigString`, i.e. not doing any caching across calls.\r\n * remove all other caching done through `OnigStringContext`\r\n\r\nThis would change semantics & performance characteristics of node-oniguruma, requiring a new major version. After this change, the javascript users will be able to use the library with caching or without caching:\r\n * **with caching**\r\n```javascript\r\nvar scanner = new OnigScanner(...);\r\nvar str = new OnigString(\"my string\");\r\nvar results = scanner.FindNextMatchSync(str, 0)\r\n```\r\n * **without caching**\r\n```javascript\r\nvar scanner = new OnigScanner(...);\r\nvar results = scanner.FindNextMatchSync(\"my string\", 0);\r\n```\r\n\r\nI wanted to check with you @zcbenz @kevinsawicki if this is a change that takes node-oniguruma in a good direction and that you would agree with such a change ... before I invest time in it.\r\n\r\nThanks!"}}