Tcl Source Code

View Ticket
Login
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 string match was exponential-time where it could be linear (See ticket [a4a7f2abd376b280]) I semi-remembered that Aho-Corasick (See https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm) is a fast string matching algorithm which matches a finite set of plain strings simultaneously. Exactly what is needed for string map. And wondered if string map was using it, suspecting that it would not.

Looking at the code in tclCmdMZ.c I confirm that string map does not use AC. It uses a simple nested loop over string positions and map-keys to locate where replacements should happen.

I propose a spike which re-implements string map using AC to compare performance with the current implementation before committing to the change.

As a side note, the current implementation converts the various strings to Unicode rep, and I do not see why. Ok, for -nocase we may be forced to at the moment. But without we can simply match on the UTF-8 bytes as they are. Due to the specific leading bit-patterns for the first byte of UTF-8 encoded chars (0, 10, 110, ...) we cannot match misaligned.

Note, with AC we might be able to handle -nocase in UTF-8 as well. Simply add all string variants to the trie/state machine. I.e. expand x in a pattern to effectively [xX] when extending AC's data structures. While the number of variants is O(2^n) in the length of the pattern the AC trie might keep from being exponential (parallel transitions in a linear sequence of states).

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.