fso_graph_builder/input/
graph500.rs

1use log::info;
2use std::{fs::File, marker::PhantomData, path::Path};
3
4use crate::prelude::*;
5use rayon::prelude::*;
6
7pub struct Graph500Input<NI> {
8    _phantom: PhantomData<NI>,
9}
10
11impl<NI> Default for Graph500Input<NI> {
12    fn default() -> Self {
13        Self {
14            _phantom: PhantomData,
15        }
16    }
17}
18
19impl<NI: Idx> InputCapabilities<NI> for Graph500Input<NI> {
20    type GraphInput = Graph500<NI>;
21}
22
23pub struct Graph500<NI: Idx>(pub EdgeList<NI, ()>);
24
25impl<NI: Idx> Edges for Graph500<NI> {
26    type NI = NI;
27
28    type EV = ();
29
30    type EdgeIter<'a>
31        = rayon::iter::Copied<rayon::slice::Iter<'a, (Self::NI, Self::NI, Self::EV)>>
32    where
33        Self: 'a;
34
35    fn edges(&self) -> Self::EdgeIter<'_> {
36        self.0.edges()
37    }
38
39    fn max_node_id(&self) -> Self::NI {
40        self.0.max_node_id()
41    }
42
43    #[cfg(test)]
44    fn len(&self) -> usize {
45        self.0.len()
46    }
47}
48
49impl<NI, P> TryFrom<InputPath<P>> for Graph500<NI>
50where
51    P: AsRef<Path>,
52    NI: Idx,
53{
54    type Error = Error;
55
56    fn try_from(path: InputPath<P>) -> Result<Self, Self::Error> {
57        let file = File::open(path.0.as_ref())?;
58        let mmap = unsafe { memmap2::MmapOptions::new().populate().map(&file)? };
59        Graph500::try_from(mmap.as_ref())
60    }
61}
62
63impl<NI> TryFrom<&[u8]> for Graph500<NI>
64where
65    NI: Idx,
66{
67    type Error = Error;
68
69    fn try_from(map: &[u8]) -> Result<Self, Self::Error> {
70        let start = std::time::Instant::now();
71
72        let file_size = map.len();
73        let edge_count = map.len() / std::mem::size_of::<PackedEdge>();
74        let node_count = edge_count / 16;
75
76        let map = map.as_ptr();
77        assert_eq!(map as usize % std::mem::align_of::<PackedEdge>(), 0);
78
79        let edges = unsafe { std::slice::from_raw_parts(map as *const PackedEdge, edge_count) };
80
81        let mut all_edges = Vec::with_capacity(edge_count);
82
83        edges
84            .par_iter()
85            .map(|edge| {
86                let source =
87                    usize::try_from(edge.source()).expect("Could not read source id as usize");
88                let target =
89                    usize::try_from(edge.target()).expect("Could not read target id as usize");
90
91                (NI::new(source), NI::new(target), ())
92            })
93            .collect_into_vec(&mut all_edges);
94
95        let edges = EdgeList::with_max_node_id(all_edges, NI::new(node_count - 1));
96
97        let elapsed = start.elapsed().as_millis() as f64 / 1000_f64;
98
99        info!(
100            "Read {} edges in {:.2}s ({:.2} MB/s)",
101            edge_count,
102            elapsed,
103            ((file_size as f64) / elapsed) / (1024.0 * 1024.0)
104        );
105
106        Ok(Self(edges))
107    }
108}
109
110// see https://github.com/graph500/graph500/blob/f89d643ce4aaae9a823d310c6ab2dd10e3d2982c/generator/graph_generator.h#L29-L33
111#[derive(Default, Copy, Clone, Debug)]
112#[repr(C)]
113struct PackedEdge {
114    v0_low: u32,
115    v1_low: u32,
116    high: u32,
117}
118
119impl PackedEdge {
120    fn source(&self) -> u64 {
121        self.v0_low as u64 | (self.high as u64 & 0xFFFF) << 32
122    }
123
124    fn target(&self) -> u64 {
125        self.v1_low as u64 | (self.high as u64 >> 16) << 32
126    }
127}
fso_graph_builder/input/graph500.rs

fso_graph_builder/input/
graph500.rs
