6
\$\begingroup\$

I have a module in Python for dealing with SVG paths. One of the problems with this is that the SVG spec is obsessed with saving characters to a pointless extent. As such, this path is valid:

"M3.4E-34-2.2e56L23-34z"

And should be parsed as follows:

"M", "3.4E-34", "-2.2e56", "L", "23", "-34", "z"

As you see, anything non-ambiguous is allowed, including separating two numbers only by a minus sign, as long as that minus-sign is not preceded by an "E" or an "e", in which case it should be interpreted as an exponent of the first number. Letters are commands (except "E" and "e" of course), and both comma and any sort of whitespace is allowed as separators.

My module currently uses a rather ugly way of tokenizing the SVG path by multiple string replacements and then a split:

COMMANDS = set('MmZzLlHhVvCcSsQqTtAa')

def _tokenize_path_replace(pathdef):
    # First handle negative exponents:
    pathdef = pathdef.replace('e-', 'NEGEXP').replace('E-', 'NEGEXP')
    # Commas and minus-signs are separators, just like spaces.
    pathdef = pathdef.replace(',', ' ').replace('-', ' -')
    pathdef = pathdef.replace('NEGEXP', 'e-')
    # Commands are allowed without spaces around. Let's insert spaces so it's
    # easier to split later.
    for c in COMMANDS:
        pathdef = pathdef.replace(c, ' %s ' % c)

    # Split the path into elements
    return pathdef.split()

This in fact is doing a total of 23 string replacements on the path, and this is easy, but seems like it should be slow. I tried doing this other ways, but to my surprise they were all slower. I did a character by character tokenizer, which took around 30-40% more time. A user of the module also suggested a regex:

import re
TOKEN_RE = re.compile("[MmZzLlHhVvCcSsQqTtAa]|[-+]?[0-9]*\.?[0-9]+(?:[eE]
[-+]?[0-9]+)?")

def _tokenize_path_replace(pathdef):
    return TOKEN_RE.findall(pathdef)

To my surprise this was also slower than doing 23 string replacements, although just 20-30%.

One thing that could speed up this is if the two expressions in the regex could be merged to one, but I can't find a way of doing that. If some regex guru can, that would improve things.

Any other way of making a speedy parsing of SVG paths that I haven't though about would also be appreciated.

\$\endgroup\$
  • 1
    \$\begingroup\$ It's not just you having trouble with slow parsing of paths: svgwrite has the same problem. \$\endgroup\$ – Gareth Rees Jul 15 '13 at 10:26
  • \$\begingroup\$ Since you're asking us to try to improve the speed of your code, it's important to have a standard test suite for comparison. Can you post or link to your test suite? \$\endgroup\$ – Gareth Rees Jul 15 '13 at 11:55
  • 1
    \$\begingroup\$ Maybe re.split('([MmZzLlHhVvCcSsQqTtAa])', "M3.4E-34-2.2e56L23-34z") and then parsing the coordinates separately (with a smaller regex) would speed things up? \$\endgroup\$ – Vedran Šego Jul 15 '13 at 12:45
  • \$\begingroup\$ @GarethRees: The module includes a full test suite. The test_parsing.py is the testcases for parsing. \$\endgroup\$ – Lennart Regebro Jul 16 '13 at 16:21
  • \$\begingroup\$ @VedranŠego: Well, geez, I was gonna prove to you that it wasn't gonna help because you can't do a smaller regex. It helped anyway. :-) \$\endgroup\$ – Lennart Regebro Jul 16 '13 at 16:53
7
\$\begingroup\$

Actually, the problem at hand might not be ideally addressed by replacements or regular expressions. The way how SVG path data is designed, seems to make going through the path string character by character more efficient.

There are essentially five different cases one has to examine. This is a direct consequence of the BNF of SVG Paths (http://www.w3.org/TR/SVG/paths.html#PathDataBNF). When looping over the string, the next character could be

  1. a digit or one of the letters 'e' and 'E',
  2. a comma or a whitespace,
  3. a command letter, i.e. one of the letters 'MmZzLlHhVvCcSsQqTtAa',
  4. the dot '.',
  5. a sign, i.e. '+' or '-'.

In these five cases the following things are done:

  1. We are inside a number and can simply append the character to the current entity.
  2. We have encountered a separator and if not already done in the last step, a new empty entity is started.
  3. We found a command. This command is added as a separate entity and a new empty one is started.
  4. In this case it could be that we were already inside a float (if the flag 'float' is True). Then the dot starts a new entity. Otherwise the dot indicates that we are now in a float. The flag 'float' is then set to True and we stay in the current entity.
  5. In this case it could be that the sign is the one of an exponent. Then it is just appended to the current entity. Otherwise a new one is started.

A code example might look like this:

def parse_path(path_data):
    digit_exp = '0123456789eE'
    comma_wsp = ', \t\n\r\f\v'
    drawto_command = 'MmZzLlHhVvCcSsQqTtAa'
    sign = '+-'
    exponent = 'eE'
    float = False
    entity = ''
    for char in path_data:
        if char in digit_exp:
            entity += char
        elif char in comma_wsp and entity:
            yield entity
            float = False
            entity = ''
        elif char in drawto_command:
            if entity:
                yield entity
                float = False
                entity = ''
            yield char
        elif char == '.':
            if float:
                yield entity
                entity = '.'
            else:
                entity += '.'
                float = True
        elif char in sign:
            if entity and entity[-1] not in exponent:
                yield entity
                float = False
                entity = char
            else:
                entity += char
    if entity:
        yield entity

I've run some tests with the above code and it was mostly twice as fast as the regexp version.

In addition, due to the clear cases it is relativly easy to understand what's going on here. This is also helpful for finding and correcting errors.

The problem in the regexp version Peter Taylor pointed to is not severe in most cases. But it might actually lead to wrong parsing. If one considers for example the coordinate 2.e2, the regexp version leads to the two coordinates '2','2'.

\$\endgroup\$
  • \$\begingroup\$ I did try that, but stopped because if the complexity. Although it might be twice as fast, compare it to the 6 lines in my code above. :-) But if the current speed would be an issue (which I don't think), then it's good to know that I can try this. \$\endgroup\$ – Lennart Regebro Apr 29 '15 at 13:49
  • \$\begingroup\$ Of course by using reg exps, you can safe many lines of code because all the different comparisions one has to make are included in one line of reg exp. But this makes this one line quite complicated. And the complexity is just hidden inside the re module you have to import. With a module built from my code you could import it and do parsing just with 2 lines of code ;-) So what's more complex in total is perhaps a matter of the point of view. But notice that the reg exp in your code may lead to wrong parsing and correcting this would probably make it more complicated and slow it down. \$\endgroup\$ – Peter Stangl Apr 30 '15 at 15:25
  • \$\begingroup\$ Really wants to upvote this answer as it detailed the flow of processing svg path. The article by itself is a treasure to understand SVG. Though I prefer the regex solution better as it is neat and clean. Anyway thanks for your great effort Peter. \$\endgroup\$ – Shi B. Feb 18 '16 at 5:33
3
\$\begingroup\$

With cred to @VedranŠego for kicking me in the right direction, my current solution is simply to split the two regex-parts into separate parsings, the first one a split (instead of a match) and the second one a findall on the floats (because doing a split is near impossible, as - both should and should not be a separator, depending on context).:

import re

COMMANDS = set('MmZzLlHhVvCcSsQqTtAa')
COMMAND_RE = re.compile("([MmZzLlHhVvCcSsQqTtAa])")
FLOAT_RE = re.compile("[-+]?[0-9]*\.?[0-9]+(?:[eE][-+]?[0-9]+)?")

def _tokenize_path(pathdef):
    for x in COMMAND_RE.split(pathdef):
        if x in COMMANDS:
            yield x
        for token in FLOAT_RE.findall(x):
            yield token

I times this with:

from timeit import timeit
num = 1000000

a = timeit("_tokenize_path('M-3.4e38 3.4E+38L-3.4E-38,3.4e-38')", 
             "from svg.path.parser import _tokenize_path", number=num)
b = timeit("_tokenize_path('M600,350 l 50,-25 a25,25 -30 0,1 50,-25 l 50,-25 a25,50 -30 0,1 50,-25 l 50,-25 a25,75 -30 0,1 50,-25 l 50,-25 a25,100 -30 0,1 50,-25 l 50,-25')",
           "from svg.path.parser import _tokenize_path", number=num)
c = timeit("_tokenize_path('M3.4E-34-2.2e56L23-34z')",
           "from svg.path.parser import _tokenize_path", number=num)

print a + b + c

And it runs an astonishing 23 times faster than the "replace" based tokenizer above, and 30 times faster then the regex based tokenizer, even though it essentially does the same thing. :-) I really did not think it would be faster to run this "dual" regex in two separate steps, and I have tried other "two-stage" variations before that was even slower, but this time I arrived at the right combination.

\$\endgroup\$
  • \$\begingroup\$ I'm glad I've helped. The splitter is a simple regex, by which I mean that there is no quantifiers * and +, so it runs straightforward. These quantifiers make regexes slow because they often have to try-and-fail before doing a match. With this approach, you've significantly shortened the strings being matched with the more complicated (meaning it has quantifiers) FLOAT_RE. Doing one match on a long string often takes much more time than doing n similar matches on strings of approximately 1/n length of a long string. Although, I have to admit I didn't expect this much of a speedup. \$\endgroup\$ – Vedran Šego Jul 16 '13 at 18:58
  • 2
    \$\begingroup\$ FWIW, the regex is slightly wrong. If you look at the definition of fractional-constant you'll see that it permits digit-sequence "." (i.e. [0-9]+\.), which isn't compatible with the regex [0-9]*\.?[0-9]+. That portion should be replaced with e.g. (?:[0-9]*\.?[0-9]+|[0-9]+\.?). \$\endgroup\$ – Peter Taylor Jul 17 '13 at 14:08
  • \$\begingroup\$ Also, my reading of the BNF is that the following is a valid path: M.4.4.4.4z. The regex-based approach in this answer handles it correctly, but the multiple-replace approach of the question doesn't. \$\endgroup\$ – Peter Taylor Jul 17 '13 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.