4
\$\begingroup\$

I am having performance problems with the following python function:

def remove_comments(buffer):
    new_buffer = ''
    lines = buffer.split('\n')
    for line in lines:
        line_wo_comments = line.split('--')[0] + '\n'
        new_buffer = new_buffer + line_wo_comments
    return new_buffer

When buffer is very large (thousands+ lines), the function gets slower and slower as it processes the buffer.

What techniques could I use to speed this function call up?

Assume that the input is a source code file. Lines of length 1 - ~120 characters. Lines may or may not have comments. The files could be many lines long. The especially problematic ones are machine generated (1-10k+ lines long).

Update: The intention is to use this as a "pre-processing" step for the buffer contents (a file). I guess I am not too interested in possibly ways to completely refactor this (i.e. methods to avoid needing to iterate through all the lines multiple times), but rather make the essence of buffer in / buffer out as fast as possible.

\$\endgroup\$
  • \$\begingroup\$ Where are you getting the first buffer and what are you doing with the second? \$\endgroup\$ – TheBlackCat Sep 3 '15 at 19:40
3
\$\begingroup\$

The function is slow because you are repeatedly doing of string concatenation with new_buffer = new_buffer + line_wo_comments. Since strings in Python are immutable, every concatenation requires copying the entire result up to that point for each line. The performance would be roughly O(n2), where n is the length of the text.

I think that even splitting up the text into a list of lines is too complicated. Just do a simple substitution:

import re

def remove_comments(buffer):
    return re.sub(r'--[^\n]*', '', buffer)
\$\endgroup\$
3
\$\begingroup\$

The Performance Tips section at python.org has comments about doing repeated string concatenation which you may find here:

https://wiki.python.org/moin/PythonSpeed/PerformanceTips#String_Concatenation

Specifically, it suggests using "".join(listOfStrings) instead of repeatedly appending to an accumulator with +=.

So I would try something like this, using re.finditer() to find all of the comments, and place the non-comment parts into a list:

import re

def removeComments(s):
  chunks = []
  offset = 0
  for m in re.finditer("--.*\n", s):
    chunks.append( s[offset: m.start(0)] )
    offset = m.end(0)-1
  chunks.append( s[offset:] )
  return "".join(chunks)

s = """
line 1
line 2  -- comment 2
line 3
line 4 -- comment 4
line 5
line 6 -- comment 6
line 7
"""
print removeComments(s)

An advantage of this approach over splitting each line is that if there are large chunks of your program which do not have any comments they will transferred to the chunks list in one piece instead of as separate lines.

Update

I would also try using a regexp replace approach - it could be even faster:

def removeComments(s):
  return re.sub('(?m)--.*$', '', s)
\$\endgroup\$
  • \$\begingroup\$ It's worth noting that page says "The accuracy of this section is disputed with respect to later versions of Python. In CPython 2.5, string concatenation is fairly fast, although this may not apply likewise to other Python implementations." \$\endgroup\$ – SuperBiasedMan Sep 3 '15 at 16:18
  • \$\begingroup\$ Have a look at the associated comments ConcatenationTestCode and the actual benchmarks they are running. += is faster for older versions of Python and for a situation that really isn't the same as this one. In the end you have to do your own benchmarking to see what works best. \$\endgroup\$ – ErikR Sep 3 '15 at 17:22
  • \$\begingroup\$ I'm not saying that your answer is wrong, I'm saying it would be good to note that the page is not 100% certain of performance as it varies from version to version and we didn't know OP's version at the time. \$\endgroup\$ – SuperBiasedMan Sep 4 '15 at 10:26
3
\$\begingroup\$

A few things:

  1. Follow pep8 style.
  2. As others have said, join is more efficient. However:
    1. You can use '\n'.join to avoid having to manually append the newline.
    2. If you are going to be working with lines individually, or are going to save the file, it is better to use a generator and not join at all.
  3. You can choose how many splits to do. It is much faster to do one split than an arbitrary number as you do. It is faster still to use partition, which always does only one split.
  4. If you are reading the buffer in, again it would be better to iterate over the lines rather than reading the whole thing in at once and splitting.

So, using your code, assuming we need a buffer in and out, this would be a much more efficient approach:

def remove_comments(buffer):
    lines = buffer.splitlines()
    return '\n'.join(line.partition('--')[0] for line in lines)

However, for example, lets say you want to read a file in, remove comments, then save it again. This would be a far, far more efficient approach:

with open(infile, 'r') as fin, open(outfile, 'w') as fout:
    for line in infile:
        newline = line.partition('--')[0]
        outfile.write(newline+'\n')

Or better yet:

with open(infile, 'r') as fin, open(outfile, 'w') as fout:
    outfile.writelines(line.partition('--')[0]+'\n' for line in infile)

They key point to these two approaches is that they only ever keep one line in memory at a time, which saves on memory enormously.

Or, if you want to do some other manipulation on the lines before saving, you could do something like this:

with open(infile, 'r') as fin, open(outfile, 'w') as fout:
   newlines1 = (line.partition('--')[0] for line in infile)
   newlines2 = (myfunc1(line) for line in newlines1)
   newlines3 = (myfunc2(line) for line in newlines2)
   fout.writelines(line+'\n' for line in newlines3)

In this case, mfunc1 and myfunc2 are functions that take a single string and return a single string. This approach will apply each operation to each line, but will only ever have one line in memory at a time.

It doesn't really matter what you ultimately do with the lines. You cold convert them to numbers or lists of numbers and do some calculation on them, send them over a network to another machine, or whatever. The point is that by doing it using generators, iterators, and generator expressions, you can save on memory and increase performance by a lot because it only ever has one line in memory at a time.

\$\endgroup\$
  • \$\begingroup\$ TIL: splitlines and partition - thanks for pointing those out. I would like my approach to stick as close to as the original buffer in / buffer out as possible. \$\endgroup\$ – Josh Sep 3 '15 at 20:38
1
\$\begingroup\$

Use join:

def remove_comments(buffer):
    return '\n'.join([line.split('--')[0] for line in buffer.split('\n')])

I'm not sure how much improvement this will offer as I can't test it now, but any serious python programmer will recommend join when it comes to string concatenation.

It is tempting to just supply join with a generator rather than a list, but the fact is that join will still created this list internally which actually turns out to be slower than supplying it with a list. You can test this yourself

Some timings (input file):

rc1 function; best of 10: 6.823 ms
rc2 function; best of 10: 18.241 ms
rc3 function; best of 10: 4.757 ms
rc4 function; best of 10: 7.715 ms
rc5 function; best of 10: 5.883 ms

Timing script:

import re
import sys
import time


def timing(func, repeat=10):
  def wrapper(*args, **kwargs):
    best = float('inf')

    for k in xrange(repeat):
        start = time.time()
        func(*args, **kwargs)
        end = time.time()

        best = min(best, (end - start) * 1000.0)
        time.sleep(0.1)

    print ('%s function; best of %d: %0.3f ms' % (func.func_name, repeat, (end - start) * 1000.0))
  return wrapper

@timing
def rc1(buffer):
    return '\n'.join([line.split('--')[0] for line in buffer.split('\n')])

@timing
def rc2(buffer):
    lines = buffer.splitlines()
    return '\n'.join(line.partition('--')[0] for line in lines)

@timing
def rc3(buffer):
    return re.sub(r'--[^\n]*', '', buffer)

@timing
def rc4(s):
  chunks = []
  offset = 0
  for m in re.finditer("--.*\n", s):
    chunks.append( s[offset: m.start(0)] )
    offset = m.end(0)-1
  chunks.append( s[offset:] )
  return "".join(chunks)

@timing
def rc5(s):
  return re.sub('(?m)--.*$', '', s)



if __name__ == '__main__':
    with open(sys.argv[1], 'r') as f:
        buffer = f.read()

    for f in [rc1, rc2, rc3, rc4, rc5]:
        f(buffer)
        time.sleep(1)
\$\endgroup\$
  • \$\begingroup\$ Does the list comprehension offer a performance improvement as well? Or is it just an alternate representation? \$\endgroup\$ – Josh Sep 3 '15 at 15:53
  • \$\begingroup\$ You know, I'm not too sure; But in this case you need to use list comprehension because join expects an iterable as arguement \$\endgroup\$ – smac89 Sep 3 '15 at 15:58
  • \$\begingroup\$ You could use a generator expression and save some time. @Josh Some rough tests suggest that it's actually slower (if neater) to do it this way. But it might depend a bit on your data, can you post any sample input? \$\endgroup\$ – SuperBiasedMan Sep 3 '15 at 16:23
  • \$\begingroup\$ @SuperBiasedMan See the timings above to see why I didn't just use a generator as arguement to join. Look at rc1 vs rc2 \$\endgroup\$ – smac89 Sep 4 '15 at 3:04
  • \$\begingroup\$ @Smac89 In your tests rc2 is faster than rc1 for me.This may vary based on Python version as me and OP are running 2.7, are you running 3? \$\endgroup\$ – SuperBiasedMan Sep 4 '15 at 9:49

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.