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

//! Cache prefetching benchmarks
//! Measures impact of prefetch hints on FST traversal

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

fn create_large_fst(states: usize) -> VectorFst<TropicalWeight> {
    let mut fst = VectorFst::new();
    let mut state_ids = Vec::new();

    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..5 {
            fst.add_arc(
                state_ids[i],
                Arc::new(
                    (j + 1) as u32,
                    (j + 1) as u32,
                    TropicalWeight::new((j + 1) as f32),
                    state_ids[i + 1],
                ),
            );
        }
    }

    fst
}

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

    for states in [1000, 5000, 10000, 50000].iter() {
        let fst = create_large_fst(*states);
        let state_list: Vec<u32> = fst.states().collect();

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

        group.bench_with_input(BenchmarkId::new("with_prefetch", states), states, |b, _| {
            b.iter(|| {
                let mut sum = TropicalWeight::zero();
                for (i, &state) in state_list.iter().enumerate() {
                    // Prefetch next few states
                    if i + 4 < state_list.len() {
                        prefetch_cache_line(&state_list[i + 4]);
                    }
                    for arc in fst.arcs(state) {
                        sum = sum.plus(&arc.weight);
                    }
                }
                black_box(sum);
            })
        });
    }

    group.finish();
}

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

    for states in [1000, 5000, 10000].iter() {
        let fst = create_large_fst(*states);

        // Create random access pattern
        let mut access_pattern: Vec<u32> = fst.states().collect();
        // Shuffle using a simple deterministic pattern
        for i in 0..access_pattern.len() {
            let j = (i * 7919 + 1234567) % access_pattern.len();
            access_pattern.swap(i, j);
        }

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

    group.finish();
}

criterion_group!(
    benches,
    bench_sequential_traversal_prefetch,
    bench_random_access_prefetch
);
criterion_main!(benches);