6
\$\begingroup\$

I came across this blog post by Adam Drake from around a year ago which is now making the rounds again.

I made some improvements to his code, but wish to see if there are additional tweaks that could be made to make it run even faster.

The task is to extract chess game results from PGN files. The files contain sequences of games, where each has a header which contains a "Result" line like this:

[Result "1-0"]
[Result "0-1"]
[Result "1/2-1/2"]

These three results indicate a white win, a black win, and a draw, respectively. The task is to simply collect and report a summary of these results.

Here is my solution to be reviewed:

find . -type f -name '*.pgn' -print0 |
 xargs -0 mawk -F '[-"]' '/Result/ { ++a[$2]; }
   END { print a["1"]+a["0"]+a["1/2"], a["1"], a["0"], a["1/2"] }'

I was skeptical of using find over just listing the files in the reference data set, but my timings indicate that this is actually faster than a shell wildcard (Bash 4.3.11(1)-release).

tripleee@xvbvntv:ChessData$ time find . -type f a-name '*.pgn' | wc -l
3025

real    0m0.014s
user    0m0.008s
sys     0m0.011s

tripleee@xvbvntv:ChessData$ time printf '%s\n' */*.pgn | wc -l
3025

real    0m0.037s
user    0m0.032s
sys     0m0.010s

The optimization I originally had in mind was to close the data file after reading the Result line, but as it turns out, the reference data set files contain multiple games, and thus multiple results (and the game portion is a lot smaller than I thought it would be).

tripleee@xvbvntv:ChessData$ time find . -type f -name '*.pgn' -print0 |
> xargs -0 mawk -F '[-"]' '/Result/ { ++a[$2]; }
>   END { print a["1"]+a["0"]+a["1/2"], a["1"], a["0"], a["1/2"] }'
6829065 2602614 1974505 2251946

real    0m50.232s
user    0m19.820s
sys     0m2.542s

This is as far as I got. (An earlier version, based on the blog post, attempted parallel processing, but removing that was the biggest performance improvement I made.) I don't think switching from Awk to a "bigger" language would buy me any serious benefits -- one of the strengths of Awk is that it's quick to write, parse, and execute. (Compiled code would probably be a tad faster, but I don't think I want to go there; let's try to keep a realistic cost/benefit ratio.) Are there any additional improvements to be made, to make it go even faster?

Here is the data set referenced in the blog, which I used to obtain my results.

(Another, slightly smaller data set is available from here.)

Sadly, the Hadoop experiment which is linked from Adam's blog is now a 404. He quotes the original author as clocking 26 minutes to process the (smaller?) data set on seven c1.medium instances. His own code took 12 seconds, but I was unable to reproduce that -- with this data set, it took 2 minutes and 30 seconds on my computer, so I have improved over that by some 60%.

\$\endgroup\$
  • \$\begingroup\$ Tangentially, see also this meta discussion \$\endgroup\$ – tripleee Jan 20 '15 at 7:42
  • 3
    \$\begingroup\$ Note that the shell glob needs to sort its results, whereas find can just print matching paths as it encounters them. That would likely explain why find is faster. \$\endgroup\$ – 200_success Jan 20 '15 at 7:45
3
\$\begingroup\$

I don't see the reason for chaining with -print0 | xargs -0. It's better and simpler to use -exec:

find . -type f -name '*.pgn' -exec mawk -F '[-"]' '...' {} +

I don't see a way to make the AWK code faster, but:

  • Some of the double-quoting is unnecessary
  • I would add a space around operators for somewhat better readability
  • A semicolon can be dropped

Like this:

/Result/ { ++a[$2] }
   END { print a[1] + a[0] + a["1/2"], a[1], a[0], a["1/2"] }
| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ -exec \; runs the command once for every file so that will be many more awk processes being run. -exec + will behave more like xargs and bunch them up so that might be an improvement but I doubt it will be a significant one as the single process is likely not a major contributing factor to the runtime. \$\endgroup\$ – Etan Reisner Jan 20 '15 at 20:56
  • \$\begingroup\$ @EtanReisner You're right, I changed \; to + \$\endgroup\$ – janos Jan 20 '15 at 20:59
  • 1
    \$\begingroup\$ I kept all array keys quoted for consistency and legibility. I doubt it matters for performance; but if it does, I would guess that explicit strings are faster (integer keys would have to be coerced to strings, then converted to hashes for associative array lookup). It's just the final END calculation so it's not going to be measurable. \$\endgroup\$ – tripleee Jan 21 '15 at 4:36
2
\$\begingroup\$

It might be interesting to see if instead of using xargs you passed the filenames directly to awk as input and then manually used getline on them (or added them to ARGV and let awk handle them normally) if that helps any.

I assume from your explanation that xargs is only spawning one command to handle the files but I wonder how much time and effort it is putting into doing that work and whether that would exceed the extra processing time awk requires to replace it.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ xargs doesn't process files, per se. It just converts lines from stdin to command-line arguments — just string processing and command launching. \$\endgroup\$ – 200_success Jan 20 '15 at 17:55
  • \$\begingroup\$ @200_success I know. (Did I write something that indicated otherwise?) But it needs to read all the input and assemble the entire command line before it can even start running awk and that is going to take a bit of time and memory that piping straight to awk does not. Hence the idea. \$\endgroup\$ – Etan Reisner Jan 20 '15 at 17:57
1
\$\begingroup\$

I noticed the result lines we're interested in only comprise a small fraction of the contents in those files, so I figured that filtering the input files first for the result lines via the expert tool grep might be more efficient than feeding them directly to awk, which I recall splits each line into fields, so that might incur significant but unnecessary overhead.

I obtained these benchmark results on my first logon session with some missing data (7.5 GB only, due to a full disk):

  • Adam Drake's solution: 1m39s

    find . -type f -name '*.pgn' -print0 | 
        xargs -0 -n4 -P4 mawk '/Result/ { split($0, a, "-");
            res = substr(a[1], length(a[1]), 1);
            if (res == 1) white++; if (res == 0) black++; if (res == 2) draw++ } 
            END { print white+black+draw, white, black, draw }' | 
        mawk '{games += $1; white += $2; black += $3; draw += $4; } 
            END { print games, white, black, draw }'
    
  • OP's solution and janos' improvement: 1m22s-1m30s

  • My improvement: 1m8s-1m18s

    export LC_ALL=C
    find . -type f -name '*.pgn' -execdir grep -hE '^\[Result' {} + | 
        mawk -F '[-"]' '{ ++a[$2] }
            END { print a[1] + a[0] + a["1/2"], a[1], a[0], a["1/2"] }'
    

Here I used a little known trick to speed up grep. I also toyed with grep -r, grep -F and grep -P, which seemed to make no difference at all, but YMMV.

However, after a reboot, I could no longer reproduce those results and was getting 1m11s as the run time for both OP/janos' and my code.

Then I downloaded the whole dataset (8.8 GB) and followed the steps provided in this answer (except the last step which seemed dangerous) to purge disk I/O caches between each run of commands, and was still getting the same time, now 1m30s.

Then I read somewhere that grep may perform faster on compressed files, so I tried it with gzip, xz, lzma, bzip2 and lzop, and low and behold, the gzip one finished in 1m1s and lzop was even faster, in 43s.

# Replace $1 with the compressed tar file
xzgrep -ahE '^\[Result' "$1" |
    mawk -F '[-"]' '{ ++a[$2] }
        END { print a[1] + a[0] + a["1/2"], a[1], a[0], a["1/2"] }'

The mawk-only version can also be made faster (49s for lzop and 1m12s for gzip):

mawk -F '[-"]' '/Result/ { ++a[$2] }
    END { print a[1] + a[0] + a["1/2"], a[1], a[0], a["1/2"] }' \
        <(lzop --decompress --stdout "$1")

If one obtained the data on GitHub by downloading it as a GZip file and still has it around, or could tolerate the roughly 10 minutes re-compression time and an additional 2.7 GB disk usage (4.5 GB for lzop at default settings), this is a faster alternative.

| improve this answer | |
\$\endgroup\$

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.