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

use std::path::PathBuf;

8

9

use duct::cmd;

10

use itertools::Itertools;

11

use log::debug;

12

use log::trace;

13

14

use merc_utilities::MercError;

15

16

use crate::DependencyGraph;

17

18

/// Bipartitions a [Hypergraph] into two blocks.

19

trait Partitioner {

20

    /// Returns the block id (`0` or `1`) of every real vertex of `hypergraph`.

21

    fn partition(&self, hypergraph: &Hypergraph) -> Result<Vec<usize>, MercError>;

22

23

24

/// Computes a variable order for the given dependency graph using the MINCE

25

/// algorithm and the KaHyPar partitioning tool.

26

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

27

    reorder_with(&KaHyParPartitioner::new(kahypar_path, kahypar_ini_path), graph)

28

29

30

/// Computes a variable order using the MINCE algorithm with the given [Partitioner].

31

201

fn reorder_with<P: Partitioner>(partitioner: &P, graph: &DependencyGraph) -> Result<Vec<usize>, MercError> {

32

201

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

33

34

201

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

35

201

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

36

201

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

37

201

    Ok(result)

38

201

39

40

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

41

///

42

/// # Details

43

///

44

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

45

/// order is always a permutation of `vertices`; whenever the subgraph cannot be split

46

/// (too few vertices, no connecting hyperedge, or a degenerate one-sided partition) the

47

/// vertices are returned in their current order.

48

1367

fn mince<P: Partitioner>(

49

1367

    partitioner: &P,

50

1367

    vertices: &[usize],

51

1367

    left_context: &[usize],

52

1367

    graph: &DependencyGraph,

53

1367

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

54

1367

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

55

56

    // Base case: at most two vertices are already "ordered".

57

1367

    if vertices.len() <= 2 {

58

698

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

59

698

        return Ok(vertices.to_vec());

60

669

61

62

669

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

63

64

    // Without a connecting hyperedge there is nothing to optimize, so keep the order.

65

669

    if hypergraph.edges.len() <= 1 {

66

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

67

        return Ok(vertices.to_vec());

68

669

69

70

    // `partition[i]` is the block id (0 or 1) of the i-th vertex of `vertices`; the

71

    // hypergraph keeps the vertex indices aligned with `vertices`.

72

669

    let partition = partitioner.partition(&hypergraph)?;

73

669

    debug_assert_eq!(

74

669

        partition.len(),

75

669

        vertices.len(),

76

        "Partitioner must assign a block to every vertex"

77

);

78

3199

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

79

80

669

    let left_vertices: Vec<usize> = vertices

81

669

        .iter()

82

669

        .zip(&partition)

83

3199

        .filter_map(|(&v, &block)| if block == 0 { Some(v) } else { None })

84

669

        .collect();

85

86

669

    let right_vertices: Vec<usize> = vertices

87

669

        .iter()

88

669

        .zip(&partition)

89

3199

        .filter_map(|(&v, &block)| if block == 1 { Some(v) } else { None })

90

669

        .collect();

91

92

669

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

93

        // Degenerate partition with everything on one side; cannot split further.

94

86

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

95

86

        return Ok(vertices.to_vec());

96

583

97

98

583

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

99

100

583

    let mut new_left_context = left_context.to_vec();

101

583

    new_left_context.extend(&left_vertices);

102

583

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

103

583

    left.append(&mut right);

104

105

    // Check that the result is a valid permutation of the input vertices.

106

583

    if cfg!(debug_assertions) {

107

583

        let mut result = left.clone();

108

583

        result.sort_unstable();

109

583

        let mut expected = vertices.to_vec();

110

583

        expected.sort_unstable();

111

112

583

        debug_assert_eq!(result, expected, "Resulting order is not a valid permutation");

113

114

115

583

    Ok(left)

116

1367

117

118

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

119

pub struct Hypergraph {

120

    /// The number of real vertices, excluding the two pseudo-vertices.

121

    pub num_vertices: usize,

122

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

123

    pub indices: Vec<usize>,

124

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

125

    pub edges: Vec<usize>,

126

    /// Weights for each vertex in the hypergraph (real vertices followed by the two pseudo-vertices).

127

    pub weights: Vec<usize>,

128

129

130

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

131

///

132

/// # Details

133

///

134

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

135

669

fn create_hypergraph(

136

669

    vertices: &[usize],

137

669

    left_context: &[usize],

138

669

    graph: &DependencyGraph,

139

669

) -> Result<Hypergraph, MercError> {

140

669

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

141

669

    let mut hyperedges = Vec::new();

142

669

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

143

3199

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

144

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

145

3199

        weights[index] = graph

146

3199

            .relations()

147

17983

            .filter(|relation| {

148

30694

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

149

17983

})

150

3199

            .count();

151

152

153

669

    let mut offset = 0usize;

154

155

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

156

669

    let left_pseudo_vertex = vertices.len();

157

669

    let right_pseudo_vertex = vertices.len() + 1;

158

159

    // They should not contribute to the cut cost.

160

669

    weights[left_pseudo_vertex] = 1;

161

669

    weights[right_pseudo_vertex] = 1;

162

163

    // Make a hyperedge for every relation

164

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

165

669

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

166

167

3744

    for relation in graph.relations() {

168

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

169

3744

        let edge_vars: Vec<usize> = relation

170

3744

            .read_vars()

171

3744

            .chain(relation.write_vars())

172

10293

            .map(|j| {

173

35367

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

174

6855

                    Some(local_index) => local_index,

175

                    None => {

176

                        // Variable is not in the current subgraph

177

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

178

3438

                        if left_context.contains(&j) {

179

1677

                            left_pseudo_vertex

180

                        } else {

181

1761

                            right_pseudo_vertex

182

183

184

185

10293

})

186

3744

            .collect();

187

188

3744

        add_edge(

189

3744

            &mut hyperedge_indices,

190

3744

            &mut hyperedges,

191

3744

            &mut offset,

192

3744

            &mut seen_edges,

193

3744

            edge_vars,

194

);

195

196

197

669

    hyperedge_indices.push(offset);

198

669

    Ok(Hypergraph {

199

669

        num_vertices: vertices.len(),

200

669

        indices: hyperedge_indices,

201

669

        edges: hyperedges,

202

669

        weights,

203

669

})

204

669

205

206

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

207

3744

fn add_edge(

208

3744

    hyperedge_indices: &mut Vec<usize>,

209

3744

    hyperedges: &mut Vec<usize>,

210

3744

    offset: &mut usize,

211

3744

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

212

3744

    mut edge_vars: Vec<usize>,

213

3744

) {

214

    // Deduplicate within-edge vertices and normalize order

215

3744

    edge_vars.sort_unstable();

216

3744

    edge_vars.dedup();

217

218

3744

    if edge_vars.len() <= 1 {

219

        // Ignore self-loops and empty edges

220

784

        return;

221

2960

222

223

4600

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

224

        // Ignore duplicated edges

225

560

        return;

226

2400

227

2400

    seen_edges.push(edge_vars.clone());

228

2400

    hyperedge_indices.push(*offset);

229

230

    // Add the edge to the hypergraph

231

6849

    for j in edge_vars {

232

6849

        hyperedges.push(j);

233

6849

        *offset += 1;

234

6849

235

3744

236

237

/// Bipartitions hypergraphs by invoking the external KaHyPar tool.

238

pub struct KaHyParPartitioner {

239

    kahypar_path: PathBuf,

240

    kahypar_ini_path: PathBuf,

241

242

243

impl KaHyParPartitioner {

244

    /// Creates a partitioner that runs the `kahypar` binary at `kahypar_path` with

245

    /// the configuration file `kahypar_ini_path`.

246

    pub fn new(kahypar_path: &Path, kahypar_ini_path: &Path) -> Self {

247

        KaHyParPartitioner {

248

            kahypar_path: kahypar_path.to_path_buf(),

249

            kahypar_ini_path: kahypar_ini_path.to_path_buf(),

250

251

252

253

254

impl Partitioner for KaHyParPartitioner {

255

    fn partition(&self, hypergraph: &Hypergraph) -> Result<Vec<usize>, MercError> {

256

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

257

258

        let mut partition = read_partition_file()?;

259

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

260

261

        // KaHyPar also assigns a block to the two pseudo-vertices, which trail the real

262

        // vertices in the output; drop them so the result lines up with the real vertices.

263

        if partition.len() < hypergraph.num_vertices {

264

            return Err(format!(

265

                "KaHyPar returned {} blocks for {} vertices",

266

                partition.len(),

267

                hypergraph.num_vertices

268

269

            .into());

270

271

        partition.truncate(hypergraph.num_vertices);

272

        Ok(partition)

273

274

275

276

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

277

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

278

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

279

280

    let result = (|| {

281

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

282

        let mut file =

283

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

284

285

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

286

        // type 10 is vertex weights only.

287

        writeln!(

288

            &mut file,

289

            "{} {} 10",

290

            hypergraph.indices.len() - 1,

291

            hypergraph.weights.len()

292

)?;

293

294

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

295

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

296

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

297

298

299

        for weight in &hypergraph.weights {

300

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

301

302

303

        file.flush()?;

304

        cmd!(

305

            kahypar_path,

306

            "-h",

307

            HYPERGRAPH_FILE,

308

            "-k",

309

            "2",

310

            "--objective",

311

            "cut",

312

            "--mode",

313

            "direct",

314

            "--epsilon",

315

            "0.01",

316

            "-w",

317

            "1",

318

            "-p",

319

            kahypar_ini_path

320

321

        .run()?;

322

323

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

324

    })();

325

326

    remove_file_if_exists(HYPERGRAPH_FILE)?;

327

    result

328

329

330

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

331

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

332

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

333

334

    let result = (|| {

335

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

336

        let mut partition = Vec::new();

337

338

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

339

            let line = line?;

340

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

341

            partition.push(block_id);

342

343

344

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

345

    })();

346

347

    remove_file_if_exists(PARTITION_FILE)?;

348

    result

349

350

351

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

352

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

353

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

354

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

355

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

356

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

357

358

359

360

#[cfg(test)]

361

mod tests {

362

    use std::cell::RefCell;

363

364

    use rand::RngExt;

365

    use rand::SeedableRng;

366

    use rand::rngs::StdRng;

367

368

    use merc_utilities::MercError;

369

    use merc_utilities::random_test;

370

371

    use super::Hypergraph;

372

    use super::Partitioner;

373

    use super::reorder_with;

374

    use crate::DependencyGraph;

375

    use crate::Relation;

376

377

    /// A [Partitioner] for tests that ignores the hypergraph structure and assigns each

378

    /// vertex to a random block. This exercises the MINCE recursion (including its

379

    /// degenerate-partition branches) without depending on the external KaHyPar tool.

380

    struct RandomPartitioner {

381

        rng: RefCell<StdRng>,

382

383

384

    impl RandomPartitioner {

385

201

        fn new(seed: u64) -> Self {

386

201

            RandomPartitioner {

387

201

                rng: RefCell::new(StdRng::seed_from_u64(seed)),

388

201

389

201

390

391

392

    impl Partitioner for RandomPartitioner {

393

669

        fn partition(&self, hypergraph: &Hypergraph) -> Result<Vec<usize>, MercError> {

394

669

            let mut rng = self.rng.borrow_mut();

395

669

            Ok((0..hypergraph.num_vertices)

396

3199

                .map(|_| rng.random_range(0..2usize))

397

669

                .collect())

398

669

399

400

401

    /// Builds a dependency graph with `num_vertices` vertices and the given read/write relations.

402

201

    fn graph_from(num_vertices: usize, relations: &[(Vec<usize>, Vec<usize>)]) -> DependencyGraph {

403

201

        let mut rels: Vec<Relation> = relations

404

201

            .iter()

405

903

            .map(|(read, write)| Relation::new(read.clone(), write.clone()))

406

201

            .collect();

407

        // Make sure the highest index is present so num_of_vertices matches num_vertices.

408

201

        if num_vertices > 0 {

409

201

            rels.push(Relation::new(vec![num_vertices - 1], vec![]));

410

201

411

201

        DependencyGraph::new(rels)

412

201

413

414

    /// Asserts that `order` is a permutation of `0..num_vertices`.

415

201

    fn assert_permutation(order: &[usize], num_vertices: usize) {

416

201

        let mut sorted = order.to_vec();

417

201

        sorted.sort_unstable();

418

201

        assert_eq!(

419

            sorted,

420

201

            (0..num_vertices).collect::<Vec<usize>>(),

421

            "MINCE must return a permutation of all vertices"

422

);

423

201

424

425

    #[test]

426

1

    fn test_mince_random_partition_is_permutation() {

427

100

        random_test(100, |rng| {

428

            // A handful of overlapping relations so the hypergraph has connecting edges.

429

100

            let num_vertices = 8;

430

100

            let graph = graph_from(

431

100

                num_vertices,

432

100

&[

433

100

                    (vec![0, 1], vec![2]),

434

100

                    (vec![2, 3], vec![4]),

435

100

                    (vec![4, 5], vec![6]),

436

100

                    (vec![1, 6], vec![7]),

437

100

                    (vec![0, 7], vec![3, 5]),

438

100

],

439

);

440

441

100

            let partitioner = RandomPartitioner::new(rng.random());

442

100

            let order = reorder_with(&partitioner, &graph).unwrap();

443

100

            assert_permutation(&order, num_vertices);

444

100

});

445

1

446

447

    #[test]

448

1

    fn test_mince_disconnected_subgraph_is_permutation() {

449

        // Two clusters {0,1,2} and {3,4,5} with no hyperedge between them. A random

450

        // bipartition can therefore split a cluster into a side that, recursively, has

451

        // more than two vertices but no connecting hyperedge — the C1 regression case.

452

100

        random_test(100, |rng| {

453

100

            let num_vertices = 6;

454

100

            let graph = graph_from(

455

100

                num_vertices,

456

100

&[

457

100

                    (vec![0, 1], vec![2]),

458

100

                    (vec![1, 2], vec![0]),

459

100

                    (vec![3, 4], vec![5]),

460

100

                    (vec![4, 5], vec![3]),

461

100

],

462

);

463

464

100

            let partitioner = RandomPartitioner::new(rng.random());

465

100

            let order = reorder_with(&partitioner, &graph).unwrap();

466

100

            assert_permutation(&order, num_vertices);

467

100

});

468

1

469

470

    #[test]

471

1

    fn test_create_hypergraph_dedups_and_skips_self_loops() {

472

        // Duplicate relations and a single-variable relation (self-loop) must not create edges.

473

1

        let graph = graph_from(

474

4,

475

1

&[

476

1

                (vec![0, 1], vec![2]),

477

1

                (vec![0, 1], vec![2]), // duplicate of the previous edge

478

1

                (vec![3], vec![3]),    // collapses to a single vertex -> self-loop

479

1

],

480

);

481

482

        // Round-trip through reorder_with to make sure the disconnected vertex 3 is kept.

483

1

        let partitioner = RandomPartitioner::new(0);

484

1

        let order = reorder_with(&partitioner, &graph).unwrap();

485

1

        assert_permutation(&order, 4);

486

1

487