Letterpress cheating in Rust 0.11.0, part 2
I have finally completed upgrading all of the assorted toy Rust programs, my ports of Jeff Knupp's Creating and Optimizing a Letterpress Cheating Program in Python, to 0.11. I also re-executed the notoriously crappy benchmarks.
These programs look for all of the words that can be made from a given set of letters, based on the system dictionary. The argument was "asdwtribnowplfglewhqagnbe", which produces 7440 results from my dictionary with a possible 33,554,406 combinations made from those letters.
Language | Program | Rust 0.6 Duration (seconds) | Rust 0.7 Duration (seconds) | Rust 0.8 Duration (seconds) | Rust 0.9 Duration (seconds) | Rust 0.11 Duration (seconds) |
---|---|---|---|---|---|---|
Python | alternatives/presser_one.py | 49.1 | 48.6 | 47.8 | 39.0 | 59.4 |
Nimrod | alternatives/nimrod_anagrams | 12.3 | 18.0 | |||
Python | alternatives/presser_two.py | 12.8 | 12.6 | 12.3 | 11.6 | 17.2 |
Rust | anagrams-hashmap-wide | 9.3 | 15.4 | 12.1 | 19.6 | 15.7 |
Rust | anagrams-vectors-wide | 11.8 | 13.1 | 12.2 | 16.8 | 12.4 |
Rust | anagrams-vectors | 8.0 | 8.2 | 11.9 | 8.1 | 11.0 |
Rust | anagrams-hashmap | 6.0 | 35.5 | 7.2 | 7.0 | 9.3 |
C | alternatives/anagrams-vectors | 8.0 | 5.8 | 5.8 | 6.0 | 9.6 |
Python | alternatives/presser_three.py | 6.0 | 6.3 | 6.0 | 5.8 | 8.3 |
Rust | anagrams-vectors-tasks | 27.1 | 13.8 | 4.2 | 4.6 | 7.7 |
Rust | anagrams-djbhash-tasks | 6.2 | 5.5 | |||
Rust | anagrams-hashmap-mmap | 4.8 | 10.6 | 7.3 | 6.3 | 2.9 |
Rust | anagrams-djbhashmap | 2.8 | 2.5 | |||
C | alternatives/anagrams-hash | 0.9 | 1.0 | 1.0 | 0.9 | 1.4 |
The programming languages and versions for this run are:
- Python: Python 2.7.6, with Python 2.7.3 and 2.7.5 for previous versions.
- C: gcc 4.8.2, with 4.6.3 and 4.8.1 for the prior runs, all with -O3.
- Nimrod: Nimrod 0.9.4 this time, 0.9.2 last, compiled with -d:release.
- Rust: Rust 0.11.0, compiled with -O.
The various versions of the programs take slightly different approaches. Those with hashmap use a hashtable to store the anagram dictionary while those with vector use a sorted array and binary search to look up anagrams. Those with djbhash use an alternative hashtable implementation, based on the DJB hash algorithm and Python's dictionary implementation. The mmap version, as well as both of the C versions, import the dictionary via mmap rather than reading. All of the programs are single threaded, except for the wide and tasks versions. The wide versions split the dictionary into segments and have each thread search all of the possible combinations in its reduced dictionary. The tasks versions allow each task to have a copy of the full dictionary and the master process divides round-robins the combinations to the tasks. The parameters of each were tuned a while back and have not been adjusted.