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
125
126

use log::info;
use std::{fs::File, marker::PhantomData, path::Path};

use crate::prelude::*;
use rayon::prelude::*;

pub struct Graph500Input<NI> {
    _phantom: PhantomData<NI>,
}

impl<NI> Default for Graph500Input<NI> {
    fn default() -> Self {
        Self {
            _phantom: PhantomData,
        }
    }
}

impl<NI: Idx> InputCapabilities<NI> for Graph500Input<NI> {
    type GraphInput = Graph500<NI>;
}

pub struct Graph500<NI: Idx>(pub EdgeList<NI, ()>);

impl<NI: Idx> Edges for Graph500<NI> {
    type NI = NI;

    type EV = ();

    type EdgeIter<'a> = rayon::iter::Copied<rayon::slice::Iter<'a, (Self::NI, Self::NI, Self::EV)>>
        where
            Self: 'a;

    fn edges(&self) -> Self::EdgeIter<'_> {
        self.0.edges()
    }

    fn max_node_id(&self) -> Self::NI {
        self.0.max_node_id()
    }

    #[cfg(test)]
    fn len(&self) -> usize {
        self.0.len()
    }
}

impl<NI, P> TryFrom<InputPath<P>> for Graph500<NI>
where
    P: AsRef<Path>,
    NI: Idx,
{
    type Error = Error;

    fn try_from(path: InputPath<P>) -> Result<Self, Self::Error> {
        let file = File::open(path.0.as_ref())?;
        let mmap = unsafe { memmap2::MmapOptions::new().populate().map(&file)? };
        Graph500::try_from(mmap.as_ref())
    }
}

impl<NI> TryFrom<&[u8]> for Graph500<NI>
where
    NI: Idx,
{
    type Error = Error;

    fn try_from(map: &[u8]) -> Result<Self, Self::Error> {
        let start = std::time::Instant::now();

        let file_size = map.len();
        let edge_count = map.len() / std::mem::size_of::<PackedEdge>();
        let node_count = edge_count / 16;

        let map = map.as_ptr();
        assert_eq!(map as usize % std::mem::align_of::<PackedEdge>(), 0);

        let edges = unsafe { std::slice::from_raw_parts(map as *const PackedEdge, edge_count) };

        let mut all_edges = Vec::with_capacity(edge_count);

        edges
            .par_iter()
            .map(|edge| {
                let source =
                    usize::try_from(edge.source()).expect("Could not read source id as usize");
                let target =
                    usize::try_from(edge.target()).expect("Could not read target id as usize");

                (NI::new(source), NI::new(target), ())
            })
            .collect_into_vec(&mut all_edges);

        let edges = EdgeList::with_max_node_id(all_edges, NI::new(node_count - 1));

        let elapsed = start.elapsed().as_millis() as f64 / 1000_f64;

        info!(
            "Read {} edges in {:.2}s ({:.2} MB/s)",
            edge_count,
            elapsed,
            ((file_size as f64) / elapsed) / (1024.0 * 1024.0)
        );

        Ok(Self(edges))
    }
}

// see https://github.com/graph500/graph500/blob/f89d643ce4aaae9a823d310c6ab2dd10e3d2982c/generator/graph_generator.h#L29-L33
#[derive(Default, Copy, Clone, Debug)]
#[repr(C)]
struct PackedEdge {
    v0_low: u32,
    v1_low: u32,
    high: u32,
}

impl PackedEdge {
    fn source(&self) -> u64 {
        self.v0_low as u64 | (self.high as u64 & 0xFFFF) << 32
    }

    fn target(&self) -> u64 {
        self.v1_low as u64 | (self.high as u64 >> 16) << 32
    }
}