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

## Results

Language Program Rust 0.6
Duration
(seconds)
Rust 0.7
Duration
(seconds)
Rust 0.8
Duration
(seconds)
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
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!

## Changes

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 enoughmk_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:8mk_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.

Site proudly generated by Hakyll.