Letterpress cheating in Rust 0.11.0, part 2

Posted on August 9, 2014 by Tommy McGuire
Labels: rust, toy problems, c, nimrod, programming language

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
Rust 0.7
Rust 0.8
Rust 0.9
Rust 0.11
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:

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.

active directory applied formal logic ashurbanipal authentication books c c++ comics conference continuations coq data structure digital humanities Dijkstra eclipse virgo electronics emacs goodreads haskell http java job Knuth ldap link linux lisp math naming nimrod notation OpenAM osgi parsing pony programming language protocols python quote quotes R random REST ruby rust SAML scala scheme shell software development system administration theory tip toy problems unix vmware yeti
Member of The Internet Defense League
Site proudly generated by Hakyll.