trie_match! {}

This macro speeds up Rust's match expression for comparing strings by using a compact double-array data structure.

Usage

Simply wrap the existing match expression with the trie_match! {} macro as follows:

use trie_match::trie_match;

let x = "abd";

let result = trie_match! {
    match x {
        "a" => 0,
        "abc" => 1,
        pat @ ("abd" | "bcc") => pat.bytes()[0],
        "bc" => 3,
        _ => 4,
    }
};

assert_eq!(result, 3);

Why is it faster?

In a normal match expression, the string is compared for each pattern. It is equivalent to the following code:

if x == "a" {
    0
} else if x == "abc" {
    1
} else if x == "abd" || x == "bcc" {
    x.bytes()[0]
} else if x == "bc" {
    3
} else {
    4
}

The above code requires that string comparisons be made from the beginning of the string each time. The time complexity of the above code is O(mn), where m is the average pattern length, and n is the number of patterns.

In contrast, this macro builds the following trie structure to retrieve the index of the matched arm:

Furthermore, this implementation uses the compact double-array data structure to achieve efficient state-to-state traversal, and the time complexity becomes O(m).

cfg attribute

Only when using Nightly Rust, this macro supports conditional compilation with the cfg attribute. To use this feature, enable features = ["cfg_attribute"] in your Cargo.toml.

Example

trie_match! {
    match x {
        #[cfg(feature = "foo")]
        "a" => { .. }
        #[cfg(feature = "bar")]
        "b" => { .. }
        _ => { .. }
    }
}

Limitations

The followings are different from the normal match expression:

• Only supports strings, byte strings, and u8 slices as patterns.
• The wildcard is evaluated last. (The normal match expression does not match patterns after the wildcard.)
• Guards are unavailable.

Sometimes the normal match expression is faster, depending on how optimization is performed, so it is better to choose based on your speed experiments.

Benchmark

Run the following command:

cargo bench

Experimental results are as follows [μs]:

• AMD Ryzen 7 5700U with Radeon Graphics

  Bench name	Normal match	phf crate	trie-match crate
  100 words random	1.94	2.02	1.09
  HTML elements random	2.32	2.43	0.55

• 12th Gen Intel(R) Core(TM) i7-1270P

  Bench name	Normal match	phf crate	trie-match crate
  100 words random	1.13	1.29	0.61
  HTML elements random	1.24	1.51	0.36

phf crate: Compile time static maps using perfect hash functions.

License

Licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution

See the guidelines.