Grcov report - mince_variable

1

use std::fs::File;

2

use std::io::BufRead;

3

use std::io::BufReader;

4

use std::io::ErrorKind;

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, kahypar_ini_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, kahypar_ini_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

    kahypar_ini_path: &Path,

35

    vertices: &[usize],

36

    left_context: &[usize],

37

    graph: &DependencyGraph,

38

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

39

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

40

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

41

42

    if partition.len() <= 2 {

43

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

44

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

45

        return Ok(partition);

46

47

48

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

49

    // separate them according to the partitioning.

50

    let left_vertices: Vec<usize> = vertices

51

        .iter()

52

        .enumerate()

53

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

54

        .collect();

55

56

    let right_vertices: Vec<usize> = vertices

57

        .iter()

58

        .enumerate()

59

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

60

        .collect();

61

62

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

63

        // Cannot partition further, return as is

64

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

65

        return Ok(vertices.to_vec());

66

67

68

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

69

70

    let mut new_left_context = left_context.to_vec();

71

    new_left_context.extend(&left_vertices);

72

    let mut right = mince(

73

        kahypar_path,

74

        kahypar_ini_path,

75

        &right_vertices,

76

        &new_left_context,

77

        graph,

78

)?;

79

    left.append(&mut right);

80

81

    // Check that the result is a valid permutation

82

    if cfg!(debug_assertions) {

83

        let mut copy = left.clone();

84

        copy.sort();

85

86

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

87

88

89

    Ok(left)

90

91

92

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

93

pub struct Hypergraph {

94

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

95

    pub indices: Vec<usize>,

96

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

97

    pub edges: Vec<usize>,

98

    /// Weights for each vertex in the hypergraph.

99

    pub weights: Vec<usize>,

100

101

102

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

103

///

104

/// # Details

105

///

106

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

107

fn create_hypergraph(

108

    vertices: &[usize],

109

    left_context: &[usize],

110

    graph: &DependencyGraph,

111

) -> Result<Hypergraph, MercError> {

112

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

113

    let mut hyperedges = Vec::new();

114

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

115

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

116

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

117

        weights[index] = graph

118

            .relations()

119

            .filter(|relation| {

120

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

121

})

122

            .count();

123

124

125

    let mut offset = 0usize;

126

127

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

128

    let left_pseudo_vertex = vertices.len();

129

    let right_pseudo_vertex = vertices.len() + 1;

130

131

    // They should not contribute to the cut cost.

132

    weights[left_pseudo_vertex] = 1;

133

    weights[right_pseudo_vertex] = 1;

134

135

    // Make a hyperedge for every relation

136

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

137

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

138

139

    for relation in graph.relations() {

140

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

141

        let edge_vars: Vec<usize> = relation

142

            .read_vars()

143

            .chain(relation.write_vars())

144

            .map(|j| {

145

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

146

                    Some(local_index) => local_index,

147

                    None => {

148

                        // Variable is not in the current subgraph

149

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

150

                        if left_context.contains(&j) {

151

                            left_pseudo_vertex

152

                        } else {

153

                            right_pseudo_vertex

154

155

156

157

})

158

            .collect();

159

160

        add_edge(

161

            &mut hyperedge_indices,

162

            &mut hyperedges,

163

            &mut offset,

164

            &mut seen_edges,

165

            edge_vars,

166

);

167

168

169

    hyperedge_indices.push(offset);

170

    Ok(Hypergraph {

171

        indices: hyperedge_indices,

172

        edges: hyperedges,

173

        weights,

174

})

175

176

177

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

178

fn add_edge(

179

    hyperedge_indices: &mut Vec<usize>,

180

    hyperedges: &mut Vec<usize>,

181

    offset: &mut usize,

182

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

183

    mut edge_vars: Vec<usize>,

184

) {

185

    // Deduplicate within-edge vertices and normalize order

186

    edge_vars.sort_unstable();

187

    edge_vars.dedup();

188

189

    if edge_vars.len() <= 1 {

190

        // Ignore self-loops and empty edges

191

        return;

192

193

194

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

195

        // Ignore duplicated edges

196

        return;

197

198

    seen_edges.push(edge_vars.clone());

199

    hyperedge_indices.push(*offset);

200

201

    // Add the edge to the hypergraph

202

    for j in edge_vars {

203

        hyperedges.push(j);

204

        *offset += 1;

205

206

207

208

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

209

fn partition(

210

    kahypar_path: &Path,

211

    kahypar_ini_path: &Path,

212

    vertices: &[usize],

213

    left_context: &[usize],

214

    graph: &DependencyGraph,

215

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

216

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

217

218

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

219

        return Ok(vertices.to_vec());

220

221

222

    run_kahypar(kahypar_path, kahypar_ini_path, &hypergraph)?;

223

224

    let partition = read_partition_file()?;

225

226

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

227

    Ok(partition)

228

229

230

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

231

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

232

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

233

234

    let result = (|| {

235

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

236

        let mut file =

237

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

238

239

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

240

        // type 10 is vertex weights only.

241

        writeln!(

242

            &mut file,

243

            "{} {} 10",

244

            hypergraph.indices.len() - 1,

245

            hypergraph.weights.len()

246

)?;

247

248

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

249

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

250

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

251

252

253

        for weight in &hypergraph.weights {

254

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

255

256

257

        file.flush()?;

258

        cmd!(

259

            kahypar_path,

260

            "-h",

261

            HYPERGRAPH_FILE,

262

            "-k",

263

            "2",

264

            "--objective",

265

            "cut",

266

            "--mode",

267

            "direct",

268

            "--epsilon",

269

            "0.01",

270

            "-w",

271

            "1",

272

            "-p",

273

            kahypar_ini_path

274

275

        .run()?;

276

277

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

278

    })();

279

280

    remove_file_if_exists(HYPERGRAPH_FILE)?;

281

    result

282

283

284

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

285

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

286

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

287

288

    let result = (|| {

289

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

290

        let mut partition = Vec::new();

291

292

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

293

            let line = line?;

294

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

295

            partition.push(block_id);

296

297

298

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

299

    })();

300

301

    remove_file_if_exists(PARTITION_FILE)?;

302

    result

303

304

305

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

306

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

307

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

308

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

309

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

310

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

311

312