{"id":5828,"date":"2021-04-05T07:00:08","date_gmt":"2021-04-05T14:00:08","guid":{"rendered":"http:\/\/writeasync.net\/?p=5828"},"modified":"2021-04-02T19:42:09","modified_gmt":"2021-04-03T02:42:09","slug":"letter-boxed-rust-impl-part-3-modules-trie-i-o","status":"publish","type":"post","link":"https:\/\/writeasync.net\/?p=5828","title":{"rendered":"Letter Boxed: Rust impl, part 3 (modules, trie, I\/O)"},"content":{"rendered":"

Our Rust-based Letter Boxed code<\/a> so far has just the core character-based data types. Today we’ll add the trie<\/a>.<\/p>\n

Before we move on, we need to keep our house in order. Rather than have one massive lib.rs file, we should start splitting out some modules<\/a>. The current lib.rs which has St<\/code> and Ch<\/code> will move to a module called core<\/code>: [see commit on GitHub]<\/a>.<\/p>\n

With that out of the way, we can begin a new module trie<\/code> to hold our next chunk of code for StTrie<\/code>: [see commit on GitHub]<\/a><\/p>\n

The trie implementation is pretty much a straight port from the C# version<\/a>. After several incremental TDD steps, we land on the following implementation<\/a>:<\/p>\n

\r\nuse crate::core::St;\r\nuse std::collections::HashMap;\r\n\r\n#[derive(Debug, PartialEq)]\r\npub enum NodeKind {\r\n    None,\r\n    Prefix,\r\n    Terminal,\r\n}\r\n\r\npub struct StTrie {\r\n    nodes: HashMap<St, bool>,\r\n    count: usize,\r\n}\r\n\r\nimpl StTrie {\r\n    fn new() -> StTrie {\r\n        let nodes = HashMap::new();\r\n        let count = 0;\r\n        StTrie { nodes, count }\r\n    }\r\n\r\n    fn len(&self) -> usize {\r\n        self.count\r\n    }\r\n\r\n    fn insert(&mut self, value: St) {\r\n        if value.len() == 0 {\r\n            return;\r\n        }\r\n\r\n        if let Some(&true) = self.nodes.get(&value) {\r\n            return;\r\n        }\r\n\r\n        self.count += 1;\r\n        self.nodes.insert(value, true);\r\n        let mut value = value;\r\n        for _ in 1..value.len() {\r\n            value = value.chop();\r\n            if let Some(_) = self.nodes.get(&value) {\r\n                return;\r\n            }\r\n\r\n            self.nodes.insert(value, false);\r\n        }\r\n    }\r\n\r\n    fn find(&self, value: St) -> NodeKind {\r\n        match self.nodes.get(&value) {\r\n            None => NodeKind::None,\r\n            Some(&true) => NodeKind::Terminal,\r\n            Some(&false) => NodeKind::Prefix,\r\n        }\r\n    }\r\n}\r\n<\/pre>\n
There’s nothing too special here, other than maybe the if let expression<\/a> when checking if the node already exists.<\/p>\n
The last big feature for StTrie<\/code> is the ability to load words from a stream of text. Thus, we need to get familiar with the Read trait<\/a>, roughly analogous to the read side of System.IO.Stream<\/code> in .NET<\/a>. Of course, the API is rather primitive, so let’s instead start with the easier BufRead derived trait<\/a>. Most notably, it allows us to use the lines()<\/code> iterator<\/a> for a much nicer experience<\/a>:<\/p>\n
\r\nimpl StTrie {\r\n    \/\/ . . .\r\n    fn load<B: BufRead>(stream: &mut B) -> StTrie {\r\n        let mut trie = StTrie::new();\r\n        for line in stream.lines() {\r\n            let word = line.unwrap();\r\n            if word.len() >= 3 && word.len() <= 12 {\r\n                let value = word.parse::<St>().unwrap();\r\n                trie.insert(value);\r\n            }\r\n        }\r\n\r\n        trie\r\n    }\r\n    \/\/ . . .\r\n}\r\n<\/pre>\n
You might wonder what the MemoryStream<\/code><\/a> equivalent is for the purposes of unit testing. It turns out we can use Cursor<\/code><\/a> for that, as demonstrated in this test helper which converts a bunch of string slices to a big block of bytes:<\/p>\n
\r\n    fn load_trie(lines: Vec<&str>) -> StTrie {\r\n        let lines = lines.join("\\r\\n").as_bytes().to_vec();\r\n        let mut stream = Cursor::new(lines);\r\n        StTrie::load(&mut stream)\r\n    }\r\n<\/pre>\n
At this point, we have enough code to write the trie-loading portion of the solver app. So let’s go ahead and do that<\/a>:<\/p>\n
\r\nuse letter_boxed_solver::trie::StTrie;\r\nuse std::{env::args, fs::File, time::Instant};\r\n\r\nfn main() {\r\n    let start = Instant::now();\r\n    let args = args();\r\n    if args.len() != 3 {\r\n        println!("Please specify a Letter Boxed puzzle and a word list file.");\r\n        return;\r\n    }\r\n\r\n    log(start, "Loading trie...");\r\n    let path = args.skip(2).next().unwrap();\r\n    let mut stream = File::open(path).unwrap();\r\n    let trie = StTrie::load(&mut stream);\r\n    log(start, format!("Loaded {} words.", trie.len()).as_str());\r\n}\r\n\r\nfn log(start: Instant, message: &str) {\r\n    println!("[{:07.3}] {}", start.elapsed().as_secs_f64(), message);\r\n}\r\n<\/pre>\n
We’re doing basic measurement with std::time::Instant<\/code><\/a> to see how fast this app really is! Let’s give it a spin now:<\/p>\n
\r\n[000.000] Loading trie...\r\n[000.059] Loaded 162309 words.\r\n<\/pre>\n
Hmm… this is a problem. The C++ implementation (after some tricky optimizations<\/a>) was able to finish the trie load in ~45 ms as of the last benchmark<\/a>. Even the C# implementation got to 52 ms… so honestly 59 ms seems quite slow. Could it be another case of slowdowns due to buffered I\/O<\/a>?<\/p>\n
The only way to find out is to write the ugly raw implementation<\/a>:<\/p>\n
\r\n    \/\/ . . . \r\n    pub fn load<R: Read>(stream: &mut R) -> StTrie {\r\n        let mut trie = StTrie::new();\r\n        let mut buf = [0u8; 1024];\r\n        let mut s = St::empty();\r\n        loop {\r\n            let result = stream.read(&mut buf[..]);\r\n            match result {\r\n                Ok(n) => {\r\n                    s = StTrie::process_chunk(&buf[0..n], s, &mut trie);\r\n                    if n == 0 {\r\n                        return trie;\r\n                    }\r\n                }\r\n                Err(e) => panic!(e),\r\n            }\r\n        }\r\n    }\r\n\r\n    fn process_chunk(chunk: &[u8], mut s: St, trie: &mut StTrie) -> St {\r\n        let mut skip = false;\r\n        for b in chunk {\r\n            match *b as char {\r\n                '\\r' | '\\n' => {\r\n                    if !skip && s.len() > 2 {\r\n                        trie.insert(s);\r\n                    }\r\n\r\n                    skip = false;\r\n                    s = St::empty();\r\n                }\r\n                c => {\r\n                    if skip || s.len() == 12 {\r\n                        skip = true;\r\n                        s = St::empty();\r\n                    } else {\r\n                        s = s + Ch::from(c);\r\n                    }\r\n                }\r\n            }\r\n        }\r\n\r\n        if chunk.len() == 0 && !skip && s.len() > 2 {\r\n            trie.insert(s);\r\n        }\r\n\r\n        s\r\n    }\r\n    \/\/ . . .\r\n<\/pre>\n
It just goes to show that you can write assembly code in any language<\/a>. Though I have to admit it isn’t as bad as it could be — all hail Rust’s safe slice type<\/a>. This would have all been for nothing if we can’t squeeze a bit more perf out of the app, though:<\/p>\n
\r\n[000.000] Loading trie...\r\n[000.040] Loaded 162309 words.\r\n<\/pre>\n
We won again! The Rust solver is now a full 5 ms faster than C++ — so far. Even better, we didn’t have to write a custom hash table this time.<\/p>\n
We’ll pick this up again later with the end-to-end solution. Until then, I wish you happy and safe systems programming<\/a>!<\/p>\n","protected":false},"excerpt":{"rendered":"
Our Rust-based Letter Boxed code so far has just the core character-based data types. Today we’ll add the trie. Before we move on, we need to keep our house in order. Rather than have one massive lib.rs file, we should… <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[91,101,41],"tags":[],"class_list":["post-5828","post","type-post","status-publish","format-standard","hentry","category-design","category-native","category-tdd"],"_links":{"self":[{"href":"https:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5828","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5828"}],"version-history":[{"count":3,"href":"https:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5828\/revisions"}],"predecessor-version":[{"id":5831,"href":"https:\/\/writeasync.net\/index.php?rest_route=\/wp\/v2\/posts\/5828\/revisions\/5831"}],"wp:attachment":[{"href":"https:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5828"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5828"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/writeasync.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5828"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}