4 posts tagged with "Rust"

Everyone says “Rust is fast” — but that alone isn’t enough.
Raw language speed can be dwarfed by the choice of algorithm for the underlying problem.

In this post, we’ll benchmark five different Rust Fibonacci implementations —
from textbook recursion to fast doubling with big integers —
to demonstrate how algorithmic complexity shapes real-world performance.

Why Benchmark​

Never trust assumptions about speed or complexity without benchmarking your actual use case. Even in a language like Rust, the difference between a naive and optimized algorithm can be millions of times faster.
This is the power of algorithmic thinking combined with Rust’s performance.

Note on Benchmarking Accuracy:
We use Criterion.rs for benchmarking, which leverages black_box to prevent compiler optimizations that could eliminate or inline computations, ensuring benchmarks measure true runtime costs.

Problem Definition​

Given an integer n, calculate the n-th Fibonacci number:

F(0) = 0, F(1) = 1
F(n) = F(n-1) + F(n-2) for n > 1

In practice, constraints drastically affect which approach is appropriate:

• Small n (≤ 40): recursion may suffice.
• Large n (≥ 10⁷): naive recursion is impossible; need iterative or advanced methods.
• Performance goals: is correctness enough, or do we require fastest possible?

Approaches​

1. Recursive O(2ⁿ)​

/// Naive recursive; Exponential time | O(2ⁿ)
pub fn fibo_1(n: u32) -> u32 {
    match n {
        0 => 0,
        1 => 1,
        n => fibo_1(n - 1) + fibo_1(n - 2),
    }
}

Benchmark​

2. Memoized Recursion O(n)​

/// Use cache to avoid recomputation | Linear | O(n) time & space
pub fn fibo_2(n: u32, cache: &mut Vec<u128>) -> u128 {
    if cache[n as usize] != u128::MAX {
        return cache[n as usize];
    }
    cache[n as usize] = fibo_2(n - 1, cache) + fibo_2(n - 2, cache);
    cache[n as usize]
}

Benchmark​

Big improvement — now n values into the thousands are feasible, but with some downsides::

• Recursion overhead remains.
• Cache initialization and maintenance cost exist.

3. Iterative O(n)​

/// Fast, simple iteration using u128 | Linear | O(n)
pub fn fibo_3(n: u64) -> u128 {
    if n < 2 { return n as u128; }
    let (mut prev, mut curr) = (0u128, 1u128);
    for _ in 2..=n {
        let next = prev + curr;
        prev = curr;
        curr = next;
    }
    curr
}

Benchmark​

4. Big Integer O(n), scalable to huge n​

/// Iterative (BigUint)
pub fn fibo_3_scaled(n: u64) -> BigUint {
    if n < 2 { return n.into(); }
    let (mut prev, mut curr) = (BigUint::ZERO, BigUint::ONE);
    for _ in 2..=n {
        let next = &prev + &curr;
        prev = curr;
        curr = next;
    }
    curr
}

Benchmark​

While the algorithm remains O(n), each addition involves expensive big-integer operations. This slows down performance compared to fixed-size integer arithmetic.

5. Fast Doubling O(log n)​

/// Logarithmic O(log n) using Fast Doubling
pub fn fibo_4(n: u64) -> BigUint {
    fn fib_pair(n: u64) -> (BigUint, BigUint) {
        if n == 0 {
            (BigUint::ZERO, BigUint::ONE)
        } else {
            let (a, b) = fib_pair(n >> 1);
            let two = BigUint::from(2u8);
            let c = &a * (&b * &two - &a);
            let d = &a * &a + &b * &b;
            if n & 1 == 0 { (c, d) } else { (d.clone(), &c + &d) }
        }
    }
    fib_pair(n).0
}

This method efficiently handles massive n values (millions or billions) — the runtime grows logarithmically with n, plus the cost of big-integer multiplications.

Benchmark​

Summary​

“–” indicates impractical runtime or integer overflow.

Takeaway​

1. Don’t trust raw language speed alone: algorithm complexity dominates runtime.
2. Recursion without memoization grows exponentially and quickly becomes unusable.
3. Iterative methods eliminate recursion overhead and scale much better.
4. Big integer arithmetic is costly but necessary for very large Fibonacci numbers.
5. Fast doubling (O(log n)) is the asymptotically fastest exact method and handles massive inputs.
6. Always benchmark with your real input sizes and constraints before choosing an approach.

Impossible → Instant​

Comparing runtimes for various inputs:

• fibo_1(40) → 184.4 ms
• fibo_3_scaled(40) → 100 ns
• fibo_4(1,000,000) → 8.34 ms

This means the optimized implementation (fibo_3) is over 22,000× faster than the naive recursive method on the same input, and orders of magnitude faster even when computing a problem 25,000 times larger.

If we compare computing n=1,000,000 using naive recursion (impossible in practice) vs. fast doubling, the theoretical speedup exceeds 10²⁰× — effectively turning a computation that would take longer than the age of the universe into milliseconds.

Reproduce & Explore​

Want to dive deeper or run the benchmarks yourself? Check out the full source code and Criterion benchmarks here:

GitHub repo: https://github.com/0xsecaas/algs

Benchmark code: benches/fib_bench.rs

Feel free to clone, experiment, and customize!

TL;DR​

• Abstract Factory is a higher-level pattern built on top of Factory Method.

• Factory Method is just one piece in the Abstract Factory toolkit.

• Factory Method = a single tool.

• Abstract Factory = a coordinated toolbox of creation strategies.

The Factory Method and Abstract Factory patterns are very similar — they’re easy to confuse but confusing them leads to either bloated complexity or broken consistency.

They’re both creational design patterns that help with object creation without specifying exact classes. But their power lies in different levels of abstraction.

The first question came to my mind when I learned about Factory Method and Abstract Factory design patterns, was:

Can't we always go with the Abstract Factory even if we only have one type of thing, because maybe someday in future we might need to add another type of related thing?

Engineering Discipline = Resisting the What if trap. You’re not rewarded for guessing the future — you’re rewarded for building code that’s clear, testable, and adaptable when the future arrives.

🧠 Core Difference:

• Factory Method: Creates one kind of product.

• Abstract Factory: Creates families of related products (i.e., multiple kinds that are meant to work together).

Factory Method​

✅ Use Factory Method when:

You have a single product type to produce, and its creation varies by context (e.g., OS/platform).

Rust example:

You want to create a Button, and that's it — just different for Mac and Windows.

trait Button {
    fn click(&self);
}

struct MacButton;
impl Button for MacButton {
    fn click(&self) { println!("Mac Button clicked!"); }
}

struct WinButton;
impl Button for WinButton {
    fn click(&self) { println!("Windows Button clicked!"); }
}

trait ButtonCreator {
    fn create_button(&self) -> Box<dyn Button>;
}

struct MacButtonCreator;
impl ButtonCreator for MacButtonCreator {
    fn create_button(&self) -> Box<dyn Button> {
        Box::new(MacButton)
    }
}


struct WinButtonCreator;
impl ButtonCreator for WinButtonCreator {
    fn create_button(&self) -> Box<dyn Button> {
        Box::new(WinButton)
    }
}

💡 Only one product (Button) is involved.

Abstract Factory​

Instead of scattering logic for each product, one factory keeps product creation cohesive and consistent.

When you need multiple, coordinated product types (e.g., Button, Checkbox, Dropdown) — all belonging to the same "theme" or "family".

Rust example:

You’re designing an entire GUI — the Button, Checkbox, and Dropdown must match in style per platform.

trait Button { fn click(&self); }
trait Checkbox { fn toggle(&self); }

struct MacButton; impl Button for MacButton {
    fn click(&self) { println!("Mac Button clicked!"); }
}
struct MacCheckbox; impl Checkbox for MacCheckbox {
    fn toggle(&self) { println!("Mac Checkbox toggled!"); }
}

trait GUIFactory {
    fn create_button(&self) -> Box<dyn Button>;
    fn create_checkbox(&self) -> Box<dyn Checkbox>;
}

struct MacFactory;
impl GUIFactory for MacFactory {
    fn create_button(&self) -> Box<dyn Button> {
        Box::new(MacButton)
    }
    fn create_checkbox(&self) -> Box<dyn Checkbox> {
        Box::new(MacCheckbox)
    }
}

💡 All created elements are stylistically related and meant to be used together.

Interchangeability​

Why we Can’t Swap Them?

Factory Method can't replace Abstract Factory: You’d need multiple separate creators. No guarantee their products match in theme/style.

Abstract Factory is overkill for a single product: You're paying for future-proofing that might never be needed.

Visual Distinction​

These ASCII diagrams highlight where each pattern shines — and where it breaks.

Factory Method — One Product

        Button (Product)
            ▲
      ┌─────┴─────┐
  MacButton   WinButton

        ButtonCreator (Creator)
             ▲
   ┌─────────┴─────────┐
MacCreator       WinCreator

    Client uses one creator

Abstract Factory — Multiple Coordinated Products

    Button (Product)     Checkbox (Product)
        ▲                   ▲
 ┌──────┴──────┐      ┌─────┴──────┐
MacButton   WinButton  MacCheckbox  WinCheckbox

         GUIFactory (Creator)
       ┌────────┴────────┐
  MacFactory        WinFactory
   └── creates ─────────┘
     [Button, Checkbox] ← grouped

      Client depends on factory
      to get all related widgets

Rule of Thumb​

Example Mapping​

Each method is a Factory Method, but the Abstract Factory binds them together so the client always gets products that match — e.g., Mac-styled UI components, not a WinButton + MacCheckbox mix.

Key Takeaway​

If you only ever need one kind of thing, stop at Factory Method. But if you ever need to guarantee consistency across multiple UI components or products, you must go up to Abstract Factory.

Ever wondered how Rust knows which function to run when you call a method? Or why sometimes we write dyn Trait and other times we use <T: Trait>?

Rust gives you zero-cost abstractions, but when it comes to polymorphism, choosing between dyn Trait and generics can be confusing.

This guide will take you from 0 to mastery on Rust dispatching.

This is all about dispatch—how Rust "dispatches" or routes your method calls.

Migrating a peer-to-peer chat app from UDP broadcast to mDNS for local peer discovery. The post covers architectural decisions, Rust async challenges, and practical lessons learned in real-world networking.