My regex to find illegal XML characters is very slow in Python

user_627492 0
Viewed 216

I am trying to identify if a string contains illegal XML characters.

To test, I create a 200K string of valid characters then add an invalid character to the end.

I then do a regex search with Python.

% time python3 temp.py
python3 temp.py  105.52s user 0.50s system 96% cpu 1:50.00 total

Should it take 105 seconds to run this 100,000 times? Seems slow to me.

Can anyone suggest what I can do to speed it up? The only thing I need is to know if the string contains > 0 illegal characters, nothing more.

Some more information - if I change the regex to:

_illegal_xml_chars_RE = re.compile(u'[\x00]')

then the time is 8 seconds:

python3 tmp.py  8.17s user 0.11s system 80% cpu 10.282 total

To answer a comment, I also timed the script but exited immediately after creating the random message, which seems to take about 1/3rd of a second:

python3 tmp.py  0.36s user 0.03s system 92% cpu 0.422 total

Here's the code:

import re
from random import choice
from string import ascii_letters, digits

# make a 200KB string of valid characters
random_message = ''.join(choice(ascii_letters + digits) for i in range(200000))
# add an illegal character to the end
random_message += '\x00'
_illegal_xml_chars_RE = re.compile(u'[\x00-\x08\x0b\x0c\x0e-\x1F\uD800-\uDFFF\uFFFE\uFFFF]')

for x in range(100000):
    result = _illegal_xml_chars_RE.search(random_message)

UPDATE: I've decided in the end that the code here is probably pretty quick all things considered, as pointed out by @sabik and @Maxt8r . It's about 1,000 every 1.3 seconds. That's pretty good. Interestingly, I am using an existing approach in which I feed the data into an XML parser via Python and let it tell me if there are invalid characters. Both the XML parser and the regex approach are almost exactly the same speed.

credit regex from: https://lsimons.wordpress.com/2011/03/17/stripping-illegal-characters-out-of-xml-in-python/

python-3.x python regex
1 Answers

The answer starts with the difficulty in the problem, and ends with an optional optimization

I tested, just for kicks, how does Numpy fare with your problem (using the Integer version of your problem, and numpy.isin). As Numpy is as a consensus fast, and surprisingly is much slower (not even close), I think you need to consider your problem. re Apparently is very optimized for this kind of problem, likely with ranges handles somewhat like done in the bottom of this answer.

Your Illegal character set is 2079, your test above has a message of length 200000, you compare 100000 times, and the example is worst case (all letters in the message are valid, so all comparisons must be done). This is a number you can't escape (up-to some optimizations, that still scale with this size):

2079*200000*100000 = 41580000000000

This means you need to reconsider your design, because I don't think you will do better the re (or re2) for class comparison methods. A couple of options

  1. Parallelize this algorithm, dividing the message into chunk
  2. If you read this xml from somewhere such as the web, read in a stream comparing each incoming character against the illegal set

For posterity I also checked using a list comprehension using enumerate and looking for each ordinal in a set, but this is still much slower than re.

Of course, the fact we use integers in this answer give a good hint to another optimization - we can do comparisons much more easily for consecutive ranges, saving a lot of comparisons:

msg_array = np.array([ord(x) for x in random_message])

result = np.where((msg_array < 10) | (msg_array == 11) |
                  (msg_array == 12) |
                  ((msg_array >= 14) & (msg_array <= 31)) |
                  ((msg_array >= 55296) & (msg_array <= 57344)) |
                  (msg_array == 65534) |
                  (msg_array == 65535))[0]

is about twice as fast for me than re. Unfortunately the message is looped for each boolean condition, so the fastest way would just to write a loop in C and import it.

user_68812400
Related