3
\$\begingroup\$

In order to create fast map/reduce processor for hadoop, I'm evaluating many languages. I'm learning python so I would like my python processor to go as fast as my perl processor.

So, for this question, the point is to increase the performance of simpleprocessor.py. To measure improvement, there is a benchmarking suite available there: https://github.com/Fade78/Stream-processing-benchmark

simpleprocessor.py

#!/usr/bin/python3    
import sys
import re

scripttitle="PYTHON SIMPLE PROCESSOR (regex parsing)"

linecount=0
commentary=0
unknownline=0
DATA={}

pattern_data=re.compile(r"^(\d+)\s+(\S+)\s+(\S+)\s+(\d+(?:\.\d+)?)")

print("#",scripttitle,"\n#TRANSFORMED INPUT",sep='')

for line in sys.stdin:
    linecount+=1
    if line.startswith("#"):
        commentary+=1
        continue
    line=line.replace(',','')
    m=re.match(pattern_data,line)
    if m:
        i,k1,k2,value = m.group(1,2,3,4)
        i=int(i)
        value=float(value)
        try:
            DATA[k1][k2]+=value
        except KeyError:
            if k1 not in DATA: # Can't automaticaly create missing key and do the insert?
                DATA[k1]={}
            if k2 not in DATA[k1]:
                DATA[k1][k2]=value
            else:
                DATA[k1][k2]+=value
        print("{0},{1:.0f},{2},{3}".format(i,value,k2,k1))
    else:
        unknownline+=1

print("#DATADUMP")

keystat=0

for k1 in sorted(DATA):
    print(k1,':',sep='',end='')
    for k2 in sorted(DATA[k1]):
        keystat+=1
        print(' (',k2,':',int(DATA[k1][k2]),')',sep='',end='')
    print()

report="#{0}\n#{1}\nparsed line: {2}, commentary line: {3}, unknown line: {4}, keystat: {5}.".format(
               scripttitle, sys.version.replace("\n"," "), linecount, commentary, unknownline, keystat)

print("#REPORT\n"+report,file=sys.stdout)
print(report,file=sys.stderr)

In the benchmark output you can see that the python processor is three time slower than the perl processor.

To test you can run the benchmark and directly test your own modification. You can also add other script (in other language). Please, read the README at github.

Regards.

Fade.

P.S.: You may write a processor in your favorite language too, I'll be glad to put it in the suite.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ Can I ask you strip this down? Having a complete ready-to-go benchmark is great. However, it makes it hard to see what you are actually asking for a review on. So I'd request that only put the file you want help with here, and host everything else off-site. \$\endgroup\$ Mar 24, 2012 at 1:34
  • \$\begingroup\$ Well, there is no problem per se, the script I "need help" is simpleprocessor.py. But it works well. The problem is that it run slower that the .pl one. So I have to put the full benchmark so people can test on their own computer. Unfortunately, I don't have another place to put these files. \$\endgroup\$
    – Fade
    Mar 24, 2012 at 9:45
  • \$\begingroup\$ Stick it in a free public repository on bitbucket. \$\endgroup\$ Mar 24, 2012 at 14:33
  • \$\begingroup\$ A couple of things about your benchmark: your keys are randomnly generated, and you aren't likely to get the same keys referenced twice, is that really typical of your actual data? Secondly, you produce a lot of output. That's gonna a pretty dominant portion of the execution time, is that really what you are concerned about? \$\endgroup\$ Mar 24, 2012 at 15:27
  • \$\begingroup\$ I made it available there: github.com/Fade78/Stream-processing-benchmark \$\endgroup\$
    – Fade
    Mar 25, 2012 at 14:02

2 Answers 2

2
\$\begingroup\$
#!/usr/bin/python3    
import sys
import re

scripttitle="PYTHON SIMPLE PROCESSOR (regex parsing)"

Python convention is to put constants in ALL_CAPS

linecount=0
commentary=0
unknownline=0
DATA={}

This isn't a constant, so it really shouldn't be all caps.

pattern_data=re.compile(r"^(\d+)\s+(\S+)\s+(\S+)\s+(\d+(?:\.\d+)?)")

print("#",scripttitle,"\n#TRANSFORMED INPUT",sep='')

Its best to put all your actual logic inside a function rather then at the main level of a script. It'll run a bit faster that way.

for line in sys.stdin:
    linecount+=1
    if line.startswith("#"):
        commentary+=1
        continue

I find code is almost always more readable when you put thing in the else block rather then use continue

    line=line.replace(',','')
    m=re.match(pattern_data,line)
    if m:

Typically we'd explicit check for none with if m is not None

        i,k1,k2,value = m.group(1,2,3,4)

Actually you could use m.groups() here. I'd also avoid such unhelpnames as i, k1, and k2

        i=int(i)

I'm not sure why you bother doing this if you are just going to print it out anyways

        value=float(value)
        try:
            DATA[k1][k2]+=value
        except KeyError:
            if k1 not in DATA: # Can't automaticaly create missing key and do the insert?
                DATA[k1]={}
            if k2 not in DATA[k1]:
                DATA[k1][k2]=value
            else:
                DATA[k1][k2]+=value

Python has a useful class called defaultdict. It lets you provide the default value for a dictionary. It also has a class called Counter for counting things So you could do this:

DATA = collections.defaultdict(collections.Counter)

Then

DATA[k1][k2] += value

will always work because the default cases are handled.

        print("{0},{1:.0f},{2},{3}".format(i,value,k2,k1))

It'd probably be easier to follow using sep=',' rather then what you've done here

    else:
        unknownline+=1

print("#DATADUMP")

keystat=0

for k1 in sorted(DATA):

Instead use for k1, items in sorted(DATA.items): Then items will be DATA[k1] and you can relooking up the data

    print(k1,':',sep='',end='')
    for k2 in sorted(DATA[k1]):

Same here, use the .items() to fetch keys and values together

        keystat+=1
        print(' (',k2,':',int(DATA[k1][k2]),')',sep='',end='')
    print()

report="#{0}\n#{1}\nparsed line: {2}, commentary line: {3}, unknown line: {4}, keystat: {5}.".format(
               scripttitle, sys.version.replace("\n"," "), linecount, commentary, unknownline, keystat)

print("#REPORT\n"+report,file=sys.stdout)
print(report,file=sys.stderr)

As for performance, remember that Perl is the practical extraction and report language. This kinda thing is perl's bread and butter, so its gonna be hard for python to win. Doesn't mean I'm not gonna try though.

EDIT: Performance

I've played with improving performance, a few points:

    m=re.match(pattern_data,line)

A better way is to use

    m = pattern_data.match(line)

They both do the same thing, but the first has a speed penalty associated with it.

        print(' (',k2,':',int(DATA[k1][k2]),')',sep='',end='')

The print function is expensive, probably due to its versatility. Rewriting your code to use sys.stdout.write() directly gave much better performance.

    try:
        DATA[k1][k2]+=value
    except KeyError:
        if k1 not in DATA: # Can't automaticaly create missing key and do the insert?
            DATA[k1]={}
        if k2 not in DATA[k1]:
            DATA[k1][k2]=value
        else:
            DATA[k1][k2]+=value

Replacing this with defaultdict or counter harmed performance. I rewrote it as

        try:
            row = DATA[k1]
        except KeyError:
            row = DATA[k1] = {}
        try:
            row[k2] += value
        except KeyError:
            row[k2] = value

Which gave me a speed boost because it avoids looking up the same values in the dictionary more then once.

With those changes I was able to get within one second of the speed of the perl script. But I was still slower. My semi-educated guess is that perl wins due to builtin support for sorting the keys of a hash during iteration. In python the sorting is done in an seperate function and may not be able to take advantage of the same things the perl version can.

FURTHER PERFORMANCE

Put everything in a function. Python optimizes functions more then other code outside of functions.

Replace

for key, value in sorted(data.items()):

with

for key in sorted(data):
    value = data[key]

The first looks nicer, but it requires python to sort a list of tuples rather then a list of strings which ends up more expensive.

Replace

sys.stdout.write(' ({}: {})'.format(k1, math.trunc(v)))

With

sys.stdout.write(''.join([' (', k1, ': ', str(math.trunc(v)), ')']))

String formatting is expensive since python has to parse through the string every time to find the formatting positions.

You can add

write = sys.stdout.write

And then use write instead of sys.stdout.write for a bit of a speed boost. See my tweaked version here: http://pastebin.com/wmaR2Bmx.

\$\endgroup\$
7
  • \$\begingroup\$ I implemented some of your suggestions into a simpleprocessor2.py (see repository). There is a performance boost but we are far from the perl script: (on my laptop) / perl script: 17 seconds / python3 old script: 56 seconds / python3 new script: 43 seconds Anyway, thanks for your answer. \$\endgroup\$
    – Fade
    Mar 25, 2012 at 20:53
  • \$\begingroup\$ Perl doesn't sort hash on input, nor during interation on a separate thread. The sort really happen here (sort keys %DATA). In fact you can provide a custom function to change defaut sort at this precise moment. \$\endgroup\$
    – Fade
    Mar 25, 2012 at 20:56
  • \$\begingroup\$ On my laptop, perl simple parser takes 3 seconds to only parse the data set, while the python script takes 21 seconds. If python could parse in 3 seconds, it will takes 18 seconds less for parsing, i.e., 43-18=25 seconds for the remaining of the work as a processor. The perl processor runs in 17 seconds. It means that with a better regexp library, there will be only 8 seconds to the perl script for the python script. \$\endgroup\$
    – Fade
    Mar 25, 2012 at 21:22
  • \$\begingroup\$ @Fade, yes the sort happened there, but you've missed my point. sorted(data) in python copies all the keys of the dictionary into a list and then sorts that. I'm guessing that perl does something more clever with its sort implementation that avoids some of the work python does copying stuff around. I've edited the post to include some additional stuff thats still killing your performance in your new version. \$\endgroup\$ Mar 25, 2012 at 21:40
  • \$\begingroup\$ @Fade, my profiling shows that even in the just parsing python script you are spending most of the time producing output. String formating + print function are expensive. So you aren't really measuring python's parsing abilities there. Even after my optimizations, the largest chunk is still dealing with the data dump at the end. If I take sorting out of both algorithms, they are both faster but perl is still in the lead. So my guess about key sorting being faster in perl was incorrect. \$\endgroup\$ Mar 25, 2012 at 21:48
0
\$\begingroup\$

Instead of your try-except in simpleprocessor.py, check out setdefault and defaultdict:

(untested code)

DATA = {}
DATA.setdefault(k1, defaultdict(int))[k2] += 1

I have no idea whether this will be faster or not (although I would guess it would). Since you said you care about performance, I strongly recommend checking out the timeit module; e.g. see http://pysnippet.blogspot.com/2010/01/lets-timeit.html

Finally, a minor style point: I wouldn't use CONSTANT-style uppercase for something that you actually change. (Although technically the var does not change, the dict it points to does, which is nonconventional...)

\$\endgroup\$
2
  • \$\begingroup\$ Since k2 may not be existing I also have to use sedefault for it. But it doesn't work since I can't make assignment to the returned values. I tried to assign the result of DATA.setdefault and then increment it but it doesn't seem to work (it should because it's reference right?) \$\endgroup\$
    – Fade
    Mar 25, 2012 at 14:40
  • \$\begingroup\$ @Fade, the defaultdict should take care of k2. Python doesn't have references in the sense of C++ if that's what you are thinking. \$\endgroup\$ Mar 25, 2012 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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