BartMassey / ttt-bench

Tic-Tac-Toe benchmark in various languages
Other
17 stars 4 forks source link

Tic-Tac-Toe Benchmarks

Copyright © 2012 Bart Massey

This is as direct as possible a translation of the same pseudocode into a variety of different imperative languages. The code is a Tic-Tac-Toe solver: i.e., a search that proves that Tic-Tac-Toe is a draw. The search is complete and completely unpruned, so it searches 549946 positions before proving the draw, calling the board evaluator from scratch at each position.

I split the program across several files, in order to:

I used standard language tools, and the fastest settings I could manage. Timing loops were adjusted to give runtimes of at least a few seconds to amortize overhead.

Results

Per-iteration timings on my home machine (AMD Ryzen 9 3900X CPU @ 3.8GHz) from a run 2022-07-14 are as follows:

    C[clang]:              0.0059s
    Rust:                  0.0060s
    C[gcc]:                0.014s
    Java[OpenJDK100]:      0.018s
    Java[OracleJDK100]:    0.019s
    Go:                    0.029s
    JavaScript[d8]:        0.061s
    Java[Oracle1]:         0.080s
    JavaScript[smjs]:      0.090s
    Haskell[bobw]:         0.14s
    PHP[8.1]:              0.15s
    Haskell[imperative]:   0.18s
    Haskell[functional]:   0.27s
    Python[pypy]:          0.28s
    JavaScript[rhino]:     0.75s
    COBOL:                 1.4s
    Python[nuitka]:        1.4s
    Erlang[hipe]:          1.6s
    Python[python3]:       2.2s
    Erlang[beam]:          2.5s
    Nickle:                4.7s

I have quit listing times for Octave and Matlab. Octave seems stuck at about 110s, which is a pain to deal with. I don't have convenient access to Matlab, and none at all on my hardware.

I am always surprised to see the differences in performance between languages. Slow recursion might be a problem for this code, but most of the time is expected to be spent in gamevalue() checking for wins. As such, it's running the most generic little for-loops ever.

Notes

Replication

To run this yourself, you'll first need to install the languages being measured. They are mostly available from stock Debian: if you are on a Debian-derived Linux distro, you can run

    sh install-languages.sh

as root to get these. Make sure unstable is in your apt sources: we want to use the latest tools.

Sadly, d8 is currently the fastest JavaScript interpreter I've found. It is not available in Debian, and building it is something of a project. Find current instructions on the interwebs, or just comment it out everywhere.

(If you are really interested in comparing JavaScript runtime runtimes with ttt-bench, you might want to install jsvu and go from there. I'm not up for making ttt-bench depend on node.js, but if there's a better way patches are welcome.)

For Rust it would probably be a good idea to use the latest version rather than the Debian-packaged one, since Debian doesn't keep up-to-date really well. Go to https://rustup.rs and follow those instructions, or uncomment the Rust line in install-languages.sh.

After that, things are straightforward: just compile and run the benchmarks and collect the results with

    sh benchmark.sh

You can then git diff the versions.txt and times.md files produced by this to see what's up.

When you are done, you may want to run

    sh clean.sh

to clean up the big binaries here.

Limitations

This code has a couple x86 of dependencies in it. Patches to fix this would be welcome: see Issue #7.

License

This code is made available under the "MIT License". Please see the file COPYING in this distribution for license details.