diff options
Diffstat (limited to 'benches/sheet_tree_benchmark.rs')
| -rw-r--r-- | benches/sheet_tree_benchmark.rs | 222 |
1 files changed, 222 insertions, 0 deletions
diff --git a/benches/sheet_tree_benchmark.rs b/benches/sheet_tree_benchmark.rs new file mode 100644 index 0000000..375b064 --- /dev/null +++ b/benches/sheet_tree_benchmark.rs @@ -0,0 +1,222 @@ +use std::hint::black_box; + +use criterion::{Criterion, criterion_group, criterion_main}; +use sheet_system::{ + index_source::IndexSource, + mapping::{LocalMapping, LocalMappingForward}, + sheet::SheetData, + sheet_tree::SheetDataTree, +}; + +fn sheet_tree_benchmark(c: &mut Criterion) { + c.bench_function("tree build 10 mappings", |b| { + b.iter(|| build_and_bench_tree(10)) + }); + + c.bench_function("tree build 100 mappings", |b| { + b.iter(|| build_and_bench_tree(100)) + }); + + c.bench_function("tree build 1000 mappings", |b| { + b.iter(|| build_and_bench_tree(1000)) + }); + + c.bench_function("tree build 10000 mappings", |b| { + b.iter(|| build_and_bench_tree(10000)) + }); + + c.bench_function("tree find shallow path (10 mappings)", |b| { + let sheet_data = create_sheet_data(10); + let tree = SheetDataTree::from(&sheet_data); + b.iter(|| find_shallow_path(&tree)) + }); + + c.bench_function("tree find shallow path (100 mappings)", |b| { + let sheet_data = create_sheet_data(100); + let tree = SheetDataTree::from(&sheet_data); + b.iter(|| find_shallow_path(&tree)) + }); + + c.bench_function("tree find shallow path (1000 mappings)", |b| { + let sheet_data = create_sheet_data(1000); + let tree = SheetDataTree::from(&sheet_data); + b.iter(|| find_shallow_path(&tree)) + }); + + c.bench_function("tree find deep path (10 mappings)", |b| { + let sheet_data = create_sheet_data(10); + let tree = SheetDataTree::from(&sheet_data); + b.iter(|| find_deep_path(&tree)) + }); + + c.bench_function("tree find deep path (100 mappings)", |b| { + let sheet_data = create_sheet_data(100); + let tree = SheetDataTree::from(&sheet_data); + b.iter(|| find_deep_path(&tree)) + }); + + c.bench_function("tree find deep path (1000 mappings)", |b| { + let sheet_data = create_sheet_data(1000); + let tree = SheetDataTree::from(&sheet_data); + b.iter(|| find_deep_path(&tree)) + }); + + c.bench_function("tree find in flat structure (1000 mappings)", |b| { + let sheet_data = create_flat_structure_sheet_data(1000); + let tree = SheetDataTree::from(&sheet_data); + b.iter(|| find_in_flat_structure(&tree)) + }); + + c.bench_function("tree find in deep structure (100 mappings)", |b| { + let sheet_data = create_deep_structure_sheet_data(100); + let tree = SheetDataTree::from(&sheet_data); + b.iter(|| find_in_deep_structure(&tree)) + }); + + c.bench_function("direct mapping find (1000 mappings)", |b| { + let sheet_data = create_sheet_data(1000); + b.iter(|| direct_mapping_find(&sheet_data)) + }); +} + +fn build_and_bench_tree(count: u32) { + let sheet_data = create_sheet_data(count); + let tree = SheetDataTree::from(&sheet_data); + black_box(tree); +} + +fn create_sheet_data(count: u32) -> SheetData { + let mut sheet = SheetData::empty().pack("benchmark_sheet"); + + for n in 0..count { + let depth = (n % 3) + 1; + let mut path_parts = Vec::new(); + + for d in 0..depth { + path_parts.push(format!("dir_{}", d)); + } + path_parts.push(format!("file_{}.txt", n)); + + sheet + .insert_mapping( + LocalMapping::new( + path_parts, + IndexSource::new(true, n as u32, 1), + LocalMappingForward::Latest, + ) + .unwrap(), + ) + .unwrap(); + } + + sheet.apply().unwrap(); + sheet.unpack() +} + +fn create_flat_structure_sheet_data(count: u32) -> SheetData { + let mut sheet = SheetData::empty().pack("flat_structure_sheet"); + + for n in 0..count { + sheet + .insert_mapping( + LocalMapping::new( + vec![format!("file_{}.txt", n)], + IndexSource::new(true, n as u32, 1), + LocalMappingForward::Latest, + ) + .unwrap(), + ) + .unwrap(); + } + + sheet.apply().unwrap(); + sheet.unpack() +} + +fn create_deep_structure_sheet_data(count: u32) -> SheetData { + let mut sheet = SheetData::empty().pack("deep_structure_sheet"); + + for n in 0..count { + let mut path_parts = Vec::new(); + for d in 0..5 { + path_parts.push(format!("level_{}", d)); + } + path_parts.push(format!("file_{}.txt", n)); + + sheet + .insert_mapping( + LocalMapping::new( + path_parts, + IndexSource::new(true, n as u32, 1), + LocalMappingForward::Latest, + ) + .unwrap(), + ) + .unwrap(); + } + + sheet.apply().unwrap(); + sheet.unpack() +} + +fn find_shallow_path(tree: &SheetDataTree) { + let root = tree.root(); + if let Some(dir_node) = root.next("dir_0") { + if let Some(file_node) = dir_node.next("file_0.txt") { + black_box(file_node.mapping()); + } + } +} + +fn find_deep_path(tree: &SheetDataTree) { + let root = tree.root(); + if let Some(dir0) = root.next("dir_0") { + if let Some(dir1) = dir0.next("dir_1") { + if let Some(dir2) = dir1.next("dir_2") { + if let Some(file_node) = dir2.next("file_0.txt") { + black_box(file_node.mapping()); + } + } + } + } +} + +fn find_in_flat_structure(tree: &SheetDataTree) { + let root = tree.root(); + if let Some(file_node) = root.next("file_500.txt") { + black_box(file_node.mapping()); + } +} + +fn find_in_deep_structure(tree: &SheetDataTree) { + let root = tree.root(); + if let Some(level0) = root.next("level_0") { + if let Some(level1) = level0.next("level_1") { + if let Some(level2) = level1.next("level_2") { + if let Some(level3) = level2.next("level_3") { + if let Some(level4) = level3.next("level_4") { + if let Some(file_node) = level4.next("file_50.txt") { + black_box(file_node.mapping()); + } + } + } + } + } + } +} + +/// 直接使用映射查找（作为对比基准） +fn direct_mapping_find(sheet_data: &SheetData) { + let key = vec![ + "dir_0".to_string(), + "dir_1".to_string(), + "dir_2".to_string(), + "file_0.txt".to_string(), + ]; + if let Some(mapping) = sheet_data.mappings().get(&key) { + black_box(mapping); + } +} + +criterion_group!(benches, sheet_tree_benchmark); +criterion_main!(benches); |