arcweight 0.3.0

A high-performance, modular library for weighted finite state transducers with comprehensive examples and benchmarks
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

//! SmallVec vs Vec benchmark for arc storage
//! Tests the performance impact of inline arc storage

use arcweight::prelude::*;
use criterion::{criterion_group, criterion_main, BenchmarkId, Criterion};
use std::hint::black_box;
use std::time::Duration;

// Helper to create FST with varying arcs per state
fn create_fst_with_arcs_per_state(
    states: usize,
    arcs_per_state: usize,
) -> VectorFst<TropicalWeight> {
    let mut fst = VectorFst::new();
    let mut state_ids = Vec::with_capacity(states);

    for _ in 0..states {
        state_ids.push(fst.add_state());
    }

    fst.set_start(state_ids[0]);
    fst.set_final(state_ids[states - 1], TropicalWeight::one());

    for i in 0..states - 1 {
        for j in 0..arcs_per_state {
            fst.add_arc(
                state_ids[i],
                Arc::new(
                    (j + 1) as u32,
                    (j + 1) as u32,
                    TropicalWeight::new(j as f32),
                    state_ids[i + 1],
                ),
            );
        }
    }

    fst
}

pub fn bench_fst_construction_varying_arcs(c: &mut Criterion) {
    let mut group = c.benchmark_group("fst_construction_arcs_per_state");
    group.measurement_time(Duration::from_secs(10));

    // Test with 1-8 arcs per state (SmallVec sweet spot)
    for arcs_per_state in [1, 2, 4, 8, 16, 32].iter() {
        group.bench_with_input(
            BenchmarkId::new("arcs_per_state", arcs_per_state),
            arcs_per_state,
            |b, &aps| {
                b.iter(|| {
                    let fst = create_fst_with_arcs_per_state(1000, aps);
                    black_box(fst);
                })
            },
        );
    }

    group.finish();
}

pub fn bench_arc_iteration_varying_arcs(c: &mut Criterion) {
    let mut group = c.benchmark_group("arc_iteration_arcs_per_state");
    group.measurement_time(Duration::from_secs(10));

    for arcs_per_state in [1, 2, 4, 8, 16, 32].iter() {
        let fst = create_fst_with_arcs_per_state(1000, *arcs_per_state);

        group.bench_with_input(
            BenchmarkId::new("arcs_per_state", arcs_per_state),
            arcs_per_state,
            |b, _| {
                b.iter(|| {
                    let mut sum = TropicalWeight::zero();
                    for state in fst.states() {
                        for arc in fst.arcs(state) {
                            sum = sum.plus(&arc.weight);
                        }
                    }
                    black_box(sum);
                })
            },
        );
    }

    group.finish();
}

pub fn bench_arc_modification_varying_arcs(c: &mut Criterion) {
    let mut group = c.benchmark_group("arc_modification_arcs_per_state");
    group.measurement_time(Duration::from_secs(10));

    for arcs_per_state in [1, 2, 4, 8, 16, 32].iter() {
        let template_fst = create_fst_with_arcs_per_state(500, *arcs_per_state);

        group.bench_with_input(
            BenchmarkId::new("clone_and_modify", arcs_per_state),
            arcs_per_state,
            |b, _| {
                b.iter(|| {
                    let mut fst = template_fst.clone();
                    // Add one more arc to each state
                    for state in 0..fst.num_states() - 1 {
                        fst.add_arc(
                            state as u32,
                            Arc::new(99, 99, TropicalWeight::new(99.0), state as u32 + 1),
                        );
                    }
                    black_box(fst);
                })
            },
        );
    }

    group.finish();
}

criterion_group!(
    benches,
    bench_fst_construction_varying_arcs,
    bench_arc_iteration_varying_arcs,
    bench_arc_modification_varying_arcs
);
criterion_main!(benches);