| Ticket UUID: | 268108fc93e2869e890f2b5e8f9668bca5c3f24a | ||
| Title: | string map - Investigate Aho-Corasick as possible speed booster | ||
| Type: | Bug | Created on: | 2017-05-06 04:23:21 |
| Submitter: | aku | Assigned to: | nobody |
| Subsystem: | 18. Commands M-Z | Severity: | Important |
| Priority: | 5 Medium | Last modified: | 2017-05-06 04:33:59 |
| Status: | Open | Closed by: | nobody |
| Resolution: | None | Closed on: | |
| Version: | |||
| Description: | ||||
|
Due to the recent https://research.swtch.com/glob which pointed out that Looking at the code in I propose a spike which re-implements As a side note, the current implementation converts the various strings to Unicode rep, and I do not see why. Ok, for Note, with AC we might be able to handle With that we would also be rid of conversion times. The big issue, which needs measuring, is the time needed to compute the AC data structures. And how much we can amortize by using a custom int-rep for the map argument of `string map` which saves it. Or alternatively, a global hash-table of recent maps (we need only key that by the map-keys, the replacements do not matter for the search in hash table and string to process) As a(nother) side note, performance boosts here will help simple templating systems based on fixed strings for place-holders. Overall I consider this "Important". | ||||
| User Comments: | ||||
aku added on 2017-05-06 04:33:59:
See also https://en.wikipedia.org/wiki/Commentz-Walter_algorithm. | ||||
