tiny_earley/
forest.rs

1// Forest
2
3// use std::{simd::{u64x4, Simd}};
4
5use super::*;
6
7#[derive(Clone)]
8pub struct Forest {
9    graph: Vec<u8>,
10    eval: Vec<Option<usize>>,
11}
12
13#[derive(Clone, Copy, Debug, Eq, PartialEq, Ord, PartialOrd)]
14pub struct NodeHandle(usize, usize);
15
16impl NodeHandle {
17    fn get(self) -> usize {
18        self.1 - self.0
19    }
20}
21
22#[derive(Clone, Copy)]
23enum Node {
24    Product {
25        action: u32,
26        left_factor: NodeHandle,
27        right_factor: Option<NodeHandle>,
28    },
29    Leaf {
30        terminal: Symbol,
31        values: u32,
32    },
33}
34
35// const fn gen() -> [(u8, u8, u8, bool); 8 * 8 * 8] {
36//     let mut result = [(0, 0, 0, false); 512];
37//     for
38//     result
39// }
40
41// static NODE_SIZES: [(u8, u8, u8, bool); 512] = gen();
42
43const NULL_ACTION: u32 = 1;
44
45impl Forest {
46    fn push_node(&mut self, node: Node) {
47        let size = |mut x: u64| {
48            let mut result = 0;
49            while x != 0 {
50                x = x >> 8;
51                result += 1;
52            }
53            result
54        };
55        let tup = match node {
56            Node::Product {
57                action,
58                left_factor,
59                right_factor,
60            } => (
61                action as u32,
62                (self.graph.len() - left_factor.get()) as u64,
63                right_factor.map_or(0, |f| (self.graph.len() - f.get()) as u64),
64            ),
65            Node::Leaf { terminal, values } => (0, terminal.0 as u64, values as u64),
66        };
67        let s = (size(tup.0 as u64), size(tup.1), size(tup.2));
68        let idx = s.0 + s.1 * 4 + s.2 * 4 * 8;
69        self.graph.push(idx);
70        self.graph.extend(&u32::to_le_bytes(tup.0)[0..s.0 as usize]);
71        self.graph.extend(&u64::to_le_bytes(tup.1)[0..s.1 as usize]);
72        self.graph.extend(&u64::to_le_bytes(tup.2)[0..s.2 as usize]);
73        // let (idx, size) = NODE_SIZES.iter().enumerate().find(|(_i, sizes)| s.0 <= sizes.0 && s.1 <= sizes.1 && s.2 <= sizes.2 && tup.3 == sizes.3).unwrap();
74        // // if idx.is_none() {
75        // //     panic!("wrong size for {:?} {:?}", tup, size(tup.1));
76        // // }
77        // // let idx = idx.unwrap();
78        // // let size = NODE_SIZES[idx];
79
80        // let mut result = [0u8; 24];
81        // let val = u64x4::from(0);
82
83        // let zeros = Simd::from_array([0, 0, 0, 0, 0, 0, 0, 0]);
84
85        // result[0 .. size.0 as usize / 8].copy_from_slice(&u32::to_le_bytes(tup.0)[0 .. size.0 as usize / 8]);
86        // result[size.0 as usize / 8 .. size.0 as usize / 8 + size.1 as usize / 8].copy_from_slice(&u64::to_le_bytes(tup.1)[0 .. size.1 as usize / 8]);
87        // result[size.0 as usize / 8 + size.1 as usize / 8 .. size.0 as usize / 8 + size.1 as usize / 8 + size.2 as usize / 8].copy_from_slice(&u64::to_le_bytes(tup.2)[0 .. size.2 as usize / 8]);
88        // self.graph.push(idx as u8);
89        // self.graph.extend(result[0 .. size.0 as usize / 8 + size.1 as usize / 8 + size.2 as usize / 8].into_iter().cloned());
90    }
91}
92
93impl Forest {
94    pub fn memory_use(&self) -> usize {
95        self.graph.len()
96    }
97
98    pub fn new<const S: usize>(grammar: &Grammar<S>) -> Self {
99        Self {
100            graph: vec![0, 0],
101            eval: grammar.rules.iter().map(|rule| rule.id).collect(),
102        }
103    }
104
105    pub fn leaf(&mut self, terminal: Symbol, _x: usize, values: u32) -> NodeHandle {
106        let handle = NodeHandle(0, self.graph.len());
107        self.push_node(Node::Leaf { terminal, values });
108        handle
109    }
110
111    pub fn push_summand(&mut self, item: CompletedItem) -> NodeHandle {
112        let handle = NodeHandle(0, self.graph.len());
113        let eval = self.eval[item.dot].map(|id| id as u32);
114        self.push_node(Node::Product {
115            action: eval.unwrap_or(NULL_ACTION),
116            left_factor: item.left_node,
117            right_factor: item.right_node,
118        });
119        handle
120    }
121
122    pub fn evaluator<T: Eval>(&mut self, eval: T) -> Evaluator<T> {
123        Evaluator { forest: self, eval }
124    }
125
126    fn get(&self, handle: NodeHandle) -> Node {
127        let slice = &self.graph[handle.get()..];
128        let size = slice[0];
129        let s = (size % 4, (size / 4) % 8, size / 4 / 8);
130        let all = &slice[1..(s.0 + s.1 + s.2) as usize + 1];
131        let (first, second) = all.split_at(s.0 as usize);
132        let (second, third) = second.split_at(s.1 as usize);
133        let mut a = [0; 4];
134        a[0..first.len()].copy_from_slice(first);
135        let mut b = [0; 8];
136        b[0..second.len()].copy_from_slice(second);
137        let mut c = [0; 8];
138        c[0..third.len()].copy_from_slice(third);
139        if s.0 != 0 {
140            Node::Product {
141                action: u32::from_le_bytes(a),
142                left_factor: NodeHandle(u64::from_le_bytes(b) as usize, handle.get()),
143                right_factor: if s.2 == 0 {
144                    None
145                } else {
146                    Some(NodeHandle(u64::from_le_bytes(c) as usize, handle.get()))
147                },
148            }
149        } else {
150            Node::Leaf {
151                terminal: Symbol(u64::from_le_bytes(b) as u32),
152                values: u64::from_le_bytes(c) as u32,
153            }
154        }
155    }
156}
157
158pub trait Eval {
159    type Elem: Send;
160    fn leaf(&self, terminal: Symbol, values: u32) -> Self::Elem;
161    fn product(&self, action: u32, list: Vec<Self::Elem>) -> Self::Elem;
162}
163
164pub struct Evaluator<'a, T> {
165    eval: T,
166    forest: &'a mut Forest,
167}
168
169struct Work<Elem> {
170    node: Node,
171    progress: u32,
172    parent: u32,
173    result: Vec<Elem>,
174}
175
176impl<'a, T: Eval + Send + Sync> Evaluator<'a, T>
177where
178    T::Elem: ::std::fmt::Debug,
179{
180    pub fn evaluate(&self, finished_node: NodeHandle) -> T::Elem {
181        let mut stack = vec![
182            Work {
183                node: Node::Leaf {
184                    terminal: Symbol(0),
185                    values: 0,
186                },
187                progress: 0,
188                parent: 0,
189                result: vec![],
190            },
191            Work {
192                node: self.forest.get(finished_node),
193                progress: 0,
194                parent: 0,
195                result: vec![],
196            },
197        ];
198        while stack.len() > 1 {
199            let mut work = stack.pop().expect("stack too small");
200            match (work.node, work.progress) {
201                (Node::Product {
202                    left_factor,
203                    right_factor,
204                    action,
205                }, 0) => {
206                    work.progress = 1;
207                    let new = Work {
208                        node: self.forest.get(left_factor),
209                        progress: 0,
210                        parent: if action == NULL_ACTION { work.parent } else { stack.len() as u32 },
211                        result: vec![],
212                    };
213                    stack.push(work);
214                    stack.push(new);
215                }
216                (Node::Product {
217                    left_factor,
218                    right_factor: Some(right),
219                    action,
220                }, 1) => {
221                    work.progress = 2;
222                    let new = Work {
223                        node: self.forest.get(right),
224                        progress: 0,
225                        parent: if action == NULL_ACTION { work.parent } else { stack.len() as u32 },
226                        result: vec![],
227                    };
228                    stack.push(work);
229                    stack.push(new);
230                }
231                (Node::Product {
232                    left_factor,
233                    right_factor,
234                    action: NULL_ACTION,
235                }, _) => {}
236                (Node::Product {
237                    left_factor,
238                    right_factor,
239                    action,
240                }, _) => {
241                    let evaluated = self.eval.product(action, work.result);
242                    stack[work.parent as usize].result.push(evaluated);
243                }
244                (Node::Leaf { terminal, values }, _) => {
245                    let evaluated = self.eval.leaf(terminal, values);
246                    stack[work.parent as usize].result.push(evaluated);
247                }
248            }
249        }
250        stack
251            .into_iter()
252            .next()
253            .unwrap()
254            .result
255            .into_iter()
256            .next()
257            .unwrap()
258    }
259}
260
261// test bench_c::bench_parse_c ... bench:  95,337,687.00 ns/iter (+/- 3,388,675.44) = 3 MB/s
262// test bench_parser           ... bench:       3,560.12 ns/iter (+/- 601.29) = 2 MB/s
263// test bench_parser2          ... bench:      19,440.32 ns/iter (+/- 2,518.07) = 3 MB/s
264// test bench_parser3          ... bench:      57,736.32 ns/iter (+/- 1,987.76) = 4 MB/s
tiny_earley/forest.rs

tiny_earley/
forest.rs
