Strategy Pattern

help
1

Hello Rustaceans,

I'm currently investigating how the Strategy Pattern can be implemented in Rust. I've always been interested in reducing branches in my program's processing pipeline.

To illustrate why this frustrates me, here's an analogy:

When you go to the supermarket, you choose either a shopping cart or a bag. Then, as you pick up items in the store, you just put them in your container. You choose your container type once. What you don't do is pick up an item, check what type of container you have, and then put it in—for every single item. You already know what container you have. You don't need to check on every item; you just put it in.

Yet somehow, when it comes to programming, this pattern is never intuitive.

What follows is an example as to how I would implement the Strategy Pattern using function pointers and how I would it with simple branches during my process pipeline. However this has a fatal flaw as using function pointers wont allow the compiler for function inlining.

Are there any fans of the Strategy Pattern in Rust and do you have any suggestions how I can implement it without losing any compiler optimizations? And btw I am not a huge fan of generics and I am also fairly new to Rust programming.

pub struct StrategyOutput {
    pub text: String,
    pub score: f32,
    pub array: Option<Vec<f32>>,
}

pub struct StrategyExecuter {
    config: String,
    execute: fn(&StrategyExecuter, u32) -> StrategyOutput,
}

impl StrategyExecuter {
    pub fn new(use_strategy_a: bool, config: String) -> Self {
        Self {
            config,
            execute: if use_strategy_a {
                Self::strategy_a
            } else {
                Self::strategy_b
            },
        }
    }

    pub fn process(&self, amount: u32) -> StrategyOutput {
        (self.execute)(self, amount)
    }

    fn strategy_a(&self, amount: u32) -> StrategyOutput {
        StrategyOutput {
            text: format!("StrategyA: {}", self.config),
            score: amount as f32,
            array: Some((0..amount).map(|i| i as f32).collect()),
        }
    }

    fn strategy_b(&self, amount: u32) -> StrategyOutput {
        StrategyOutput {
            text: format!("StrategyB: {}", self.config),
            score: amount as f32,
            array: None,
        }
    }
}

pub struct NormalExecuter {
    config: String,
}

impl NormalExecuter {
    pub fn new(config: String) -> Self {
        Self { config }
    }

    pub fn process(&self, amount: u32, use_strategy_a: bool) -> StrategyOutput {
        let array = if use_strategy_a {
            Some((0..amount).map(|i| i as f32).collect())
        } else {
            None
        };

        StrategyOutput {
            text: format!("StrategyA: {}", self.config),
            score: amount as f32,
            array: array,
        }
    }
}
2

Usually, the strategy pattern is implemented in Rust using generics (and traits); personally, I've never once had to use a function pointer as far as I remember. As you note, function pointers can't be inlined. I get that using generics can be annoying, and for a while after starting Rust I hardly used them. I think it's perfectly fine to avoid certain parts of Rust while ramping up, but that also means avoiding some tasks that would necessitate using tools that I or you don't yet want to mess with.

I think it'd be reasonable to not allow passing generic strategies to your struct, and just store an enum Strategy { A, B } (or a boolean use_strategy_a, though that's less ideal); then, in process, match on that enum to decide what strategy to use. It's arguably less extensible and perhaps marginally less performant, but absent generics, I think it's the best option. If you control all the code - that is, if you're making an application rather than a library - this approach will work just fine. (I'd maybe even encourage you to start with runnable binaries / applications rather than library code when learning Rust, since making a library with intent for it to be used by / useful for other people seems more difficult to me than making something that you can use yourself.)

Also, I feel obligated to link to this blog post; I recognize the strategy pattern more readily as "the use of interfaces". Interfaces / the strategy pattern are, in my opinion, central in Rust's type and trait system. (Thus why there's so many generics in most Rust code, or at least most libraries.)

Note that for the first... I don't know... year (at least) of using Rust, I wrote maybe a dozen generic functions, total, all of them trivial (functions with a T parameter with no trait bounds, and a few functions with an F: Fn(_) -> _ parameter). I was performing a large amount of computations on concrete types, and even made a working GUI frontend with the egui crate, all with minimal generics.

1 Like
3

Have you looked at traits?
When you look at the Strategy Pattern as described in the GoF book then Strategy is a trait (many of the inheritances used in the book can be done with traits)

4

you can have something like

struct Executor<Strategy>{
//....
strategy:Strategy,
}

impl<Strategy:FnMut(Input)->(Output)> Executor<Strategy>{
pub fn new(strat:Strategy)->Self{
Self{
strategy:strat
}
pub fn do stuff(&self){
let input =....
 let output=self.strategy(input);
}
}
5

I generally would suggest that you think of function pointers as a code smell. Why? Because dyn Trait is function pointers but better :slight_smile:

I would say that usually you do struct Executor<S> { strategy: S, ... other fields ... }, then bound various methods on S: MyStrategyTrait, and also have forwarding impls like impl<'a, S: ?Sized + MyStrategyTrait> MyStrategyTrait for &'a S { ... } and impl<S: ?Sized + MyStrategyTrait> MyStrategyTrait for Box<S> { ... }.

That way if you don't need anything dynamic, you can have struct SimpleStrategy; and it's a ZST, where you're never actually use the &self in the various strategy methods, so it'll not take up any space and you'll get full static dispatch.

But also you have the option of using Executor<&dyn MyStrategyTrait> or Executor<Box<dyn MyStrategyTrait>> if you need it, with way more flexibility.

1 Like
6

The "checking of the cart" you refer to is probably about enums. The thing is, for each cart you need a different way to put the item in.

  • Generics + Trait will make different version of the code that exactly knows the cart, they sound the closest to what you described.
  • Function pointer (or dyn) is like indexing into a giant array (memory) to find out how to put the item inside the cart. This doesn't solve the issue you have, just pushed the "checking" onto CPU, and with function pointer it indexes into a HUGE array, so CPU is having hard time predicting it and often has to wait until the memory responds.
  • Enum is manually checking which cart is it, not by indexing into that huge array and waiting but by checking the discriminant that you already have around. With something like enum_dispatch - Rust you get both ergonomics and 10x performance over function pointers.
2 Likes
7

Where did you get your receipt?

1 Like