Letterpress cheating in Rust 0.8

Posted on October 6, 2013 by Tommy McGuire
Labels: rust, toy problems, programming language

Following the recent release of Rust 0.8, I have updated my ports of Jeff Knupp's Creating and Optimizing a Letterpress Cheating Program in Python and re-executed the crappy benchmarks.

As a reminder, this program looks for all of the words that can be made from a given set of letters, based on the system dictionary. The argument for all of these runs was "asdwtribnowplfglewhqagnbe", which produces 7440 results from my dictionary; I get 33,554,406 combinations out of those letters. I used Python 2.7.3; gcc 4.6.3 with -O3; and rustc 0.8 with -O.


Language Program Rust 0.6
Rust 0.7
Rust 0.8
Python alternatives/presser_one.py 49.1 48.6 47.8
Python alternatives/presser_two.py 12.8 12.6 12.3
Rust anagrams-vectors-wide 11.8 13.1 12.2
Rust anagrams-hashmap-wide 9.3 15.4 12.1
Rust anagrams-vectors 8.0 8.2 11.9
Rust anagrams-hashmap-mmap 4.8 10.6 7.3
Rust anagrams-hashmap 6.0 35.5 7.2
Python alternatives/presser_three.py 6.0 6.3 6.0
C alternatives/anagrams-vectors 8.0 5.8 5.8
Rust anagrams-vectors-tasks 27.1 13.8 4.2
C alternatives/anagrams-hash 0.9 1.0 1.0

The big winner here, and the only obviously important change, is anagrams-vectors-tasks, which has steadily gone from hideously slow, to decent-ish, to pretty nice. This version of the program copies the entire dictionary to 6 worker tasks and then sends batches of combinations from the input string to each worker, which use binary search to look for the combinations. This and the -wide programs are the only multi-threaded versions, and the -wide versions, which divide the dictionary and have each worker look for all combinations, are much less chatty. As a result, I suspect inter-task communication has gotten much faster. Yay!


The primary change is that for expressions now use the new external iterator protocol, although not all of the iterator functions in the standard library have been updated. (Specifically, I couldn't find a new-style iterator over the lines of a file.) Given this change, and my previous post, I have modified each_combination to a style usable with do expressions.

Speaking of do, the times() method in the num::Times trait now uses that protocol instead of for.

The Clone trait now replaces Copy, and calls for a clone() method rather than the copy keyword.

There have been some miscellaneous library changes; uint::range has been replaced by iter::range (and there is some fancy type-system magic behind that). num::sqrt has replaced float::sqrt in complex.rs, the example of operator overloading. The mmap.rs module used by anagrams-hashmap-mmap is obsolete, since a cross-platform version is now available in os::MemoryMap. I have continued to use my module, since it serves as an example of the foreign function interface.

The FFI itself has changed, requiring #[fixed_stack_segment] and suggesting #[inline(never)] for calling C functions. The declaration of C functions no longer needs unsafe, which they are assumed to be. The C string interfaces have changed, although the interface is not much different; filename.with_c_str instead of str::as_c_str(filename).

There still seems to be a problem with the lifetime of temporary values. If I write the following code:

for key in sorted_keys(dict).iter() { ... }

I then get something like the following error:

mk_anadict.rs:40:8: 40:26 error: borrowed value does not live long enough
mk_anadict.rs:40 for key in sorted_keys(dict).iter() {
mk_anadict.rs:43:4: 43:5 note: borrowed pointer must be valid for the method call at 43:4...
mk_anadict.rs:43 }
mk_anadict.rs:40:8: 40:33 note: ...but borrowed value is only valid for the method call at 40:8
mk_anadict.rs:40 for key in sorted_keys(dict).iter() {

However, if I give the temporary value a name then everything works as expected:

let skeys = sorted_keys(dict);
for key in skeys.iter() { ... }

Oh, and SipHash is still slow.

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 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.