Grcov report - reorder.rs

1

use std::fs::File;

2

use std::io::ErrorKind;

3

use std::io::BufRead;

4

use std::io::BufReader;

5

use std::io::Write;

6

use std::path::Path;

7

8

use duct::cmd;

9

use itertools::Itertools;

10

use log::debug;

11

use log::trace;

12

13

use merc_utilities::MercError;

14

15

use crate::DependencyGraph;

16

17

/// Default implementation of reorder when `kahypar` feature is not enabled.

18

pub fn reorder(kahypar_path: &Path, graph: &DependencyGraph) -> Result<Vec<usize>, MercError> {

19

    debug!("Total span: {}", graph.total_span());

20

21

    let vertices = (0..graph.num_of_vertices()).collect::<Vec<usize>>();

22

    let result = mince(kahypar_path, &vertices, &[], graph)?;

23

    debug!("Reordered total span: {}", graph.reorder(&result).total_span());

24

    Ok(result)

25

26

27

/// The recursive MINCE algorithm to compute a partitioning of the given dependency graph.

28

///

29

/// # Details

30

///

31

/// The `vertices` are the indices of the subgraph that we are considering

32

fn mince(

33

    kahypar_path: &Path,

34

    vertices: &[usize],

35

    left_context: &[usize],

36

    graph: &DependencyGraph,

37

) -> Result<Vec<usize>, MercError> {

38

    trace!("MINCE called with vertices: {:?}", vertices);

39

    let partition = partition(kahypar_path, vertices, left_context, graph)?;

40

41

    if partition.len() <= 2 {

42

        // Base case: a single vertex is already "ordered"

43

        trace!("MINCE reached base case with vertices: {:?}", vertices);

44

        return Ok(partition);

45

46

47

    // We kept the indices of vertices in the hypergraph the same as `vertices`, so we can now

48

    // separate them according to the partitioning.

49

    let left_vertices: Vec<usize> = vertices

50

        .iter()

51

        .enumerate()

52

        .filter_map(|(i, &v)| if partition[i] == 0 { Some(v) } else { None })

53

        .collect();

54

55

    let right_vertices: Vec<usize> = vertices

56

        .iter()

57

        .enumerate()

58

        .filter_map(|(i, &v)| if partition[i] == 1 { Some(v) } else { None })

59

        .collect();

60

61

    if left_vertices.is_empty() || right_vertices.is_empty() {

62

        // Cannot partition further, return as is

63

        trace!("MINCE reached base case with vertices: {:?}", vertices);

64

        return Ok(vertices.to_vec());

65

66

67

    let mut left = mince(kahypar_path, &left_vertices, left_context, graph)?;

68

69

    let mut new_left_context = left_context.to_vec();

70

    new_left_context.extend(&left_vertices);

71

    let mut right = mince(kahypar_path, &right_vertices, &new_left_context, graph)?;

72

    left.append(&mut right);

73

74

    // Check that the result is a valid permutation

75

    if cfg!(debug_assertions) {

76

        let mut copy = left.clone();

77

        copy.sort();

78

79

        debug_assert_eq!(copy, vertices, "Resulting order is not a valid permutation");

80

81

82

    Ok(left)

83

84

85

/// A hypergraph representation with indices, edges, and vertex weights.

86

pub struct Hypergraph {

87

    /// Indices into the edges vector marking the start of each hyperedge.

88

    pub indices: Vec<usize>,

89

    /// The hyperedges, stored as a flat list of vertex indices.

90

    pub edges: Vec<usize>,

91

    /// Weights for each vertex in the hypergraph.

92

    pub weights: Vec<usize>,

93

94

95

/// Constructs a hypergraph from the given dependency graph.

96

///

97

/// # Details

98

///

99

/// The `vertices` are the indices of the subgraph that we are considering.

100

fn create_hypergraph(

101

    vertices: &[usize],

102

    left_context: &[usize],

103

    graph: &DependencyGraph,

104

) -> Result<Hypergraph, MercError> {

105

    let mut hyperedge_indices = Vec::with_capacity(graph.num_of_relations() + 1);

106

    let mut hyperedges = Vec::new();

107

    let mut weights = vec![1; vertices.len() + 2]; // +2 for the pseudo-vertices

108

    for (index, vertex) in vertices.iter().enumerate() {

109

        // Calculate the total number of edges that the vertex is involved in, and use it as the weight.

110

        weights[index] = graph

111

            .relations()

112

            .filter(|relation| {

113

                relation.read_vars().any(|j| j == *vertex) || relation.write_vars().any(|j| j == *vertex)

114

})

115

            .count();

116

117

118

    let mut offset = 0usize;

119

120

    // Add two pseudo-vertices to represent the "left" and "right" context of the partition.

121

    let left_pseudo_vertex = vertices.len();

122

    let right_pseudo_vertex = vertices.len() + 1;

123

124

    // They should not contribute to the cut cost.

125

    weights[left_pseudo_vertex] = 1;

126

    weights[right_pseudo_vertex] = 1;

127

128

    // Make a hyperedge for every relation

129

    // Track unique edges as sorted lists of local vertex indices

130

    let mut seen_edges: Vec<Vec<usize>> = Vec::new();

131

132

    for relation in graph.relations() {

133

        // Collect only variables that are in `vertices`, and use their local indices

134

        let edge_vars: Vec<usize> = relation

135

            .read_vars()

136

            .chain(relation.write_vars())

137

            .map(|j| {

138

                match vertices.iter().position(|i| *i == j) {

139

                    Some(local_index) => local_index,

140

                    None => {

141

                        // Variable is not in the current subgraph

142

                        // Check if it is in the left or right context

143

                        if left_context.contains(&j) {

144

                            left_pseudo_vertex

145

                        } else {

146

                            right_pseudo_vertex

147

148

149

150

})

151

            .collect();

152

153

        add_edge(

154

            &mut hyperedge_indices,

155

            &mut hyperedges,

156

            &mut offset,

157

            &mut seen_edges,

158

            edge_vars,

159

);

160

161

162

    hyperedge_indices.push(offset);

163

    Ok(Hypergraph {

164

        indices: hyperedge_indices,

165

        edges: hyperedges,

166

        weights,

167

})

168

169

170

/// Adds an edge to the hypergraph, while ensuring that it is not a self-loop, empty, or duplicated.

171

fn add_edge(

172

    hyperedge_indices: &mut Vec<usize>,

173

    hyperedges: &mut Vec<usize>,

174

    offset: &mut usize,

175

    seen_edges: &mut Vec<Vec<usize>>,

176

    mut edge_vars: Vec<usize>,

177

) {

178

    // Deduplicate within-edge vertices and normalize order

179

    edge_vars.sort_unstable();

180

    edge_vars.dedup();

181

182

    if edge_vars.len() <= 1 {

183

        // Ignore self-loops and empty edges

184

        return;

185

186

187

    if seen_edges.iter().any(|e| e == &edge_vars) {

188

        // Ignore duplicated edges

189

        return;

190

191

    seen_edges.push(edge_vars.clone());

192

    hyperedge_indices.push(*offset);

193

194

    // Add the edge to the hypergraph

195

    for j in edge_vars {

196

        hyperedges.push(j);

197

        *offset += 1;

198

199

200

201

/// Partitions the given hypergraph using the `kahypar` tool.

202

fn partition(

203

    kahypar_path: &Path,

204

    vertices: &[usize],

205

    left_context: &[usize],

206

    graph: &DependencyGraph,

207

) -> Result<Vec<usize>, MercError> {

208

    let hypergraph = create_hypergraph(vertices, left_context, graph)?;

209

210

    if vertices.len() <= 2 || hypergraph.edges.len() <= 1 {

211

        return Ok(vertices.to_vec());

212

213

214

    // Get path relative to the current executable, and obtain a path to the `kahypar.ini` configuration file.

215

    let mut kahypar_ini_path = std::env::current_exe()?;

216

    kahypar_ini_path.pop(); // remove the executable filename

217

    kahypar_ini_path.push("kahypar.ini");

218

219

    if !kahypar_ini_path.is_file() {

220

        return Err(format!(

221

            "Could not find '{}'. The 'kahypar.ini' file must be present next to the executable.",

222

            kahypar_ini_path.display()

223

224

        .into());

225

226

227

    run_kahypar(kahypar_path, &kahypar_ini_path, &hypergraph)?;

228

229

    let partition = read_partition_file()?;

230

231

    debug_assert!(partition.iter().all(|x| *x <= 1), "MINCE only supports bipartitioning");

232

    Ok(partition)

233

234

235

/// Writes `reorder.hgr`, runs KaHyPar, and removes the temporary file again.

236

fn run_kahypar(kahypar_path: &Path, kahypar_ini_path: &Path, hypergraph: &Hypergraph) -> Result<(), MercError> {

237

    const HYPERGRAPH_FILE: &str = "reorder.hgr";

238

239

    let result = (|| {

240

        // Create a file to write the hypergraph to disk in hMetis format.

241

        let mut file = File::create_new(HYPERGRAPH_FILE)

242

            .map_err(|e| format!("Failed to create file '{HYPERGRAPH_FILE}': {e}"))?;

243

244

        // Expected <num_hyperedges> <num_hypernodes> <type> (line 1)

245

        // type 10 is vertex weights only.

246

        writeln!(

247

            &mut file,

248

            "{} {} 10",

249

            hypergraph.indices.len() - 1,

250

            hypergraph.weights.len()

251

)?;

252

253

        for (from, to) in hypergraph.indices.iter().tuple_windows() {

254

            let edge = &hypergraph.edges[*from..*to];

255

            writeln!(&mut file, "{}", edge.iter().map(|i| i + 1).format(" "))?;

256

257

258

        for weight in &hypergraph.weights {

259

            writeln!(&mut file, "{} ", weight)?;

260

261

262

        file.flush()?;

263

        cmd!(

264

            kahypar_path,

265

            "-h",

266

            HYPERGRAPH_FILE,

267

            "-k",

268

            "2",

269

            "--objective",

270

            "cut",

271

            "--mode",

272

            "direct",

273

            "--epsilon",

274

            "0.01",

275

            "-w",

276

            "1",

277

            "-p",

278

            kahypar_ini_path

279

280

        .run()?;

281

282

        Ok::<(), MercError>(())

283

    })();

284

285

    remove_file_if_exists(HYPERGRAPH_FILE)?;

286

    result

287

288

289

/// Reads KaHyPar's partition output and removes the temporary file again.

290

fn read_partition_file() -> Result<Vec<usize>, MercError> {

291

    const PARTITION_FILE: &str = "reorder.hgr.part2.epsilon0.01.seed-1.KaHyPar";

292

293

    let result = (|| {

294

        let partition_file = File::open(PARTITION_FILE)?;

295

        let mut partition = Vec::new();

296

297

        for line in BufReader::new(partition_file).lines() {

298

            let line = line?;

299

            let block_id: usize = line.trim().parse()?;

300

            partition.push(block_id);

301

302

303

        Ok::<Vec<usize>, MercError>(partition)

304

    })();

305

306

    remove_file_if_exists(PARTITION_FILE)?;

307

    result

308

309

310

/// Removes the specified file if it exists, ignoring "file not found" errors.

311

fn remove_file_if_exists(path: &str) -> Result<(), MercError> {

312

    match std::fs::remove_file(path) {

313

        Ok(()) => Ok(()),

314

        Err(error) if error.kind() == ErrorKind::NotFound => Ok(()),

315

        Err(error) => Err(error.into()),

316

317