Grcov report - compressed

1

use std::fmt;

2

use std::marker::PhantomData;

3

4

use bitvec::bitvec;

5

use bitvec::order::Lsb0;

6

use delegate::delegate;

7

use log::trace;

8

9

use merc_io::BytesFormatter;

10

use merc_utilities::TagIndex;

11

use merc_utilities::debug_trace;

12

use merc_utilities::is_valid_permutation;

13

14

/// A copy of `vec![]` that can be used for the [`crate::ByteCompressedVec`].

15

#[macro_export]

16

macro_rules! bytevec {

17

    () => {

18

        $crate::ByteCompressedVec::new()

19

};

20

    ($elem:expr; $n:expr) => {

21

        $crate::ByteCompressedVec::from_elem($elem, $n)

22

};

23

24

25

/// A vector data structure that stores objects in a byte compressed format.

26

///

27

/// # Details

28

///

29

/// The basic idea is that elements of type `T` implement the `CompressedEntry`

30

/// trait which allows them to be converted to and from a byte representation.

31

/// The vector dynamically adjusts the number of bytes used per entry based on

32

/// the maximum size of the entries added so far.

33

///

34

/// For numbers this means that we only store the number of bytes required to

35

/// represent the largest number added so far. Note that the number of bytes

36

/// used per entry is only increased over time as larger entries are added.

37

///

38

/// Note that the `drop()` function of `T` is never called, but we cannot

39

/// require that `T: !Drop`.

40

#[derive(Default, PartialEq, Eq, Clone)]

41

pub struct ByteCompressedVec<T> {

42

    data: Vec<u8>,

43

    bytes_per_entry: usize,

44

    _marker: PhantomData<T>,

45

46

47

impl<T: CompressedEntry> ByteCompressedVec<T> {

48

293444

    pub fn new() -> ByteCompressedVec<T> {

49

293444

        ByteCompressedVec {

50

293444

            data: Vec::new(),

51

293444

            bytes_per_entry: 0,

52

293444

            _marker: PhantomData,

53

293444

54

293444

55

56

    /// Initializes a ByteCompressedVec with the given capacity and (minimal) bytes per entry.

57

552372

    pub fn with_capacity(capacity: usize, bytes_per_entry: usize) -> ByteCompressedVec<T> {

58

552372

        ByteCompressedVec {

59

552372

            data: Vec::with_capacity(capacity * bytes_per_entry),

60

552372

            bytes_per_entry,

61

552372

            _marker: PhantomData,

62

552372

63

552372

64

65

    /// This is basically the collect() of `Vec`.

66

///

67

    /// However, we use it to determine the required bytes per entry in advance.

68

200

    pub fn with_iter<I>(iter: I) -> ByteCompressedVec<T>

69

200

    where

70

200

        I: ExactSizeIterator<Item = T> + Clone,

71

72

200

        let bytes_per_entry = iter

73

200

            .clone()

74

1011

            .fold(0, |max_bytes, entry| max_bytes.max(entry.bytes_required()));

75

76

200

        let mut vec = ByteCompressedVec::with_capacity(iter.len(), bytes_per_entry);

77

1011

        for entry in iter {

78

1011

            vec.push(entry);

79

1011

80

200

vec

81

200

82

83

    /// Adds a new entry to the vector.

84

385074188

    pub fn push(&mut self, entry: T) {

85

385074188

        self.resize_entries(entry.bytes_required());

86

87

        // Add the new entry to the end of the vector.

88

385074188

        let old_len = self.data.len();

89

385074188

        self.data.resize(old_len + self.bytes_per_entry, 0);

90

385074188

        entry.to_bytes(&mut self.data[old_len..]);

91

385074188

92

93

    /// Removes the last element from the vector and returns it, or None if it is empty.

94

4409

    pub fn pop(&mut self) -> Option<T> {

95

4409

        if self.is_empty() {

96

            None

97

        } else {

98

4409

            let index = self.len() - 1;

99

4409

            let entry = self.index(index);

100

4409

            self.data.truncate(index * self.bytes_per_entry);

101

4409

            Some(entry)

102

103

4409

104

105

    /// Returns the entry at the given index.

106

14180824800

    pub fn index(&self, index: usize) -> T {

107

14180824800

        let start = index * self.bytes_per_entry;

108

14180824800

        let end = start + self.bytes_per_entry;

109

14180824800

        T::from_bytes(&self.data[start..end])

110

14180824800

111

112

    /// Sets the entry at the given index.

113

557408655

    pub fn set(&mut self, index: usize, entry: T) {

114

557408655

        self.resize_entries(entry.bytes_required());

115

116

557408655

        let start = index * self.bytes_per_entry;

117

557408655

        let end = start + self.bytes_per_entry;

118

557408655

        entry.to_bytes(&mut self.data[start..end]);

119

557408655

120

121

    /// Returns the number of elements in the vector.

122

162388583

    pub fn len(&self) -> usize {

123

162388583

        if self.bytes_per_entry == 0 {

124

770344

125

        } else {

126

161618239

            debug_assert!(self.data.len().is_multiple_of(self.bytes_per_entry));

127

161618239

            self.data.len() / self.bytes_per_entry

128

129

162388583

130

131

    /// Returns true if the vector is empty.

132

403682

    pub fn is_empty(&self) -> bool {

133

403682

        self.len() == 0

134

403682

135

136

    /// Returns metrics about memory usage of this compressed vector

137

    pub fn metrics(&self) -> CompressedVecMetrics {

138

        let element_count = self.len();

139

        let actual_memory =

140

            self.data.len() + std::mem::size_of_val(&self.bytes_per_entry) + std::mem::size_of::<PhantomData<T>>();

141

        let worst_case_memory = element_count * std::mem::size_of::<T>();

142

143

        CompressedVecMetrics {

144

            actual_memory,

145

            worst_case_memory,

146

147

148

149

    /// Returns an iterator over the elements in the vector.

150

120711

    pub fn iter(&self) -> ByteCompressedVecIterator<'_, T> {

151

120711

        ByteCompressedVecIterator {

152

120711

            vector: self,

153

120711

            current: 0,

154

120711

            end: self.len(),

155

120711

156

120711

157

158

    /// Returns an iterator over the elements in the vector for the begin, end range.

159

    pub fn iter_range(&self, begin: usize, end: usize) -> ByteCompressedVecIterator<'_, T> {

160

        ByteCompressedVecIterator {

161

            vector: self,

162

            current: begin,

163

            end,

164

165

166

167

    /// Updates the given entry using a closure.

168

38174470

    pub fn update<F>(&mut self, index: usize, mut update: F)

169

38174470

    where

170

38174470

        F: FnMut(&mut T),

171

172

38174470

        let mut entry = self.index(index);

173

38174470

        update(&mut entry);

174

38174470

        self.set(index, entry);

175

38174470

176

177

    /// Iterate over all elements and adapt the elements using a closure.

178

    pub fn map<F>(&mut self, mut f: F)

179

    where

180

        F: FnMut(&mut T),

181

182

        for index in 0..self.len() {

183

            let mut entry = self.index(index);

184

            f(&mut entry);

185

            self.set(index, entry);

186

187

188

189

    /// Folds over the elements in the vector using the provided closure.

190

59072

    pub fn fold<B, F>(&mut self, init: B, mut f: F) -> B

191

59072

    where

192

59072

        F: FnMut(B, &mut T) -> B,

193

194

59072

        let mut accumulator = init;

195

12910726

        for index in 0..self.len() {

196

12910726

            let mut element = self.index(index);

197

12910726

            accumulator = f(accumulator, &mut element);

198

12910726

            self.set(index, element);

199

12910726

200

59072

        accumulator

201

59072

202

203

    /// Permutes a vector in place according to the given permutation function.

204

///

205

    /// The resulting vector will be [v_p^-1(0), v_p^-1(1), ..., v_p^-1(n-1)] where p is the permutation function.

206

100

    pub fn permute<P>(&mut self, permutation: P)

207

100

    where

208

100

        P: Fn(usize) -> usize,

209

210

100

        debug_assert!(

211

100

            is_valid_permutation(&permutation, self.len()),

212

            "The given permutation must be a bijective mapping"

213

);

214

215

100

        let mut visited = bitvec![usize, Lsb0; 0; self.len()];

216

489

        for start in 0..self.len() {

217

489

            if visited[start] {

218

265

                continue;

219

224

220

221

            // Perform the cycle starting at 'start'

222

224

            let mut current = start;

223

224

            // Keeps track of the last displaced element

225

224

            let mut old = self.index(start);

226

227

224

            debug_trace!("Starting new cycle at position {}", start);

228

713

            while !visited[current] {

229

489

                visited.set(current, true);

230

489

                let next = permutation(current);

231

489

                if next != current {

232

381

                    debug_trace!("Moving element from position {} to position {}", current, next);

233

381

                    let temp = self.index(next);

234

381

                    self.set(next, old);

235

381

                    old = temp;

236

381

237

238

489

                current = next;

239

240

241

100

242

243

    /// Applies a permutation to a vector in place using an index function.

244

///

245

    /// The resulting vector will be [v_p(0), v_p(1), ..., v_p(n-1)] where p is the index function.

246

200

    pub fn permute_indices<P>(&mut self, indices: P)

247

200

    where

248

200

        P: Fn(usize) -> usize,

249

250

200

        debug_assert!(

251

200

            is_valid_permutation(&indices, self.len()),

252

            "The given permutation must be a bijective mapping"

253

);

254

255

200

        let mut visited = bitvec![usize, Lsb0; 0; self.len()];

256

1011

        for start in 0..self.len() {

257

1011

            if visited[start] {

258

584

                continue;

259

427

260

261

            // Follow the cycle starting at 'start'

262

427

            debug_trace!("Starting new cycle at position {}", start);

263

427

            let mut current = start;

264

427

            let original = self.index(start);

265

266

1204

            while !visited[current] {

267

1011

                visited.set(current, true);

268

1011

                let next = indices(current);

269

270

1011

                if next != current {

271

818

                    if next != start {

272

584

                        debug_trace!("Moving element from position {} to position {}", current, next);

273

584

                        self.set(current, self.index(next));

274

584

                    } else {

275

234

                        break;

276

277

193

278

279

777

                current = next;

280

281

282

427

            trace!("Writing original to {}", current);

283

427

            self.set(current, original);

284

285

200

286

287

    /// Applies a permutation to a vector in place using an index function.

288

///

289

    /// This variant is faster but requires additional memory for the intermediate result vector.

290

100

    pub fn permute_indices_fast<P>(&mut self, indices: P)

291

100

    where

292

100

        P: Fn(usize) -> usize,

293

294

        // `with_capacity` is in entries, not bytes, so pass the element count.

295

100

        let mut result = ByteCompressedVec::with_capacity(self.len(), self.bytes_per_entry);

296

522

        for index in 0..self.len() {

297

522

            result.push(self.index(indices(index)));

298

522

299

100

        *self = result;

300

100

301

302

    /// Swaps the entries at the given indices.

303

1

    pub fn swap(&mut self, index1: usize, index2: usize) {

304

1

        if index1 != index2 {

305

1

            let start1 = index1 * self.bytes_per_entry;

306

1

            let start2 = index2 * self.bytes_per_entry;

307

1

308

1

            // Create a temporary buffer for one entry

309

1

            let temp = T::from_bytes(&self.data[start1..start1 + self.bytes_per_entry]);

310

1

311

1

            // Copy entry2 to entry1's position

312

1

            self.data.copy_within(start2..start2 + self.bytes_per_entry, start1);

313

1

314

1

            // Copy temp to entry2's position

315

1

            temp.to_bytes(&mut self.data[start2..start2 + self.bytes_per_entry]);

316

1

317

1

318

319

    /// Resizes the vector to the given length, filling new entries with the provided value.

320

209505

    pub fn resize_with<F>(&mut self, new_len: usize, mut f: F)

321

209505

    where

322

209505

        F: FnMut() -> T,

323

324

209505

        let current_len = self.len();

325

209505

        if new_len > current_len {

326

            // Preallocate space for the additional entries.

327

208301

            self.data.reserve((new_len - current_len) * self.bytes_per_entry);

328

50420714

            for _ in current_len..new_len {

329

50420714

                self.push(f());

330

50420714

331

1204

        } else if new_len < current_len {

332

            if new_len == 0 {

333

                self.data.clear();

334

                self.bytes_per_entry = 0;

335

            } else {

336

                // It could be that the bytes per entry is now less, but that we never reduce.

337

                self.data.truncate(new_len * self.bytes_per_entry);

338

339

1204

340

209505

341

342

    /// Reserves capacity for at least additional more entries to be inserted with the given bytes per entry.

343

13227

    pub fn reserve(&mut self, additional: usize, bytes_per_entry: usize) {

344

13227

        self.resize_entries(bytes_per_entry);

345

13227

        self.data.reserve(additional * self.bytes_per_entry);

346

13227

347

348

    /// Resizes all entries in the vector to the given length.

349

942664121

    fn resize_entries(&mut self, new_bytes_required: usize) {

350

942664121

        if new_bytes_required > self.bytes_per_entry {

351

515672

            let mut new_data: Vec<u8> = vec![0; self.len() * new_bytes_required];

352

353

515672

            if self.bytes_per_entry > 0 {

354

                // Resize all the existing elements because the new entry requires more bytes.

355

68055748

                for (index, entry) in self.iter().enumerate() {

356

68055748

                    let start = index * new_bytes_required;

357

68055748

                    let end = start + new_bytes_required;

358

68055748

                    entry.to_bytes(&mut new_data[start..end]);

359

68055748

360

431738

361

362

515672

            self.bytes_per_entry = new_bytes_required;

363

515672

            self.data = new_data;

364

942148449

365

942664121

366

367

368

impl<T: CompressedEntry + Clone> ByteCompressedVec<T> {

369

533934

    pub fn from_elem(entry: T, n: usize) -> ByteCompressedVec<T> {

370

533934

        let mut vec = ByteCompressedVec::with_capacity(n, entry.bytes_required());

371

184567087

        for _ in 0..n {

372

184567087

            vec.push(entry.clone());

373

184567087

374

533934

vec

375

533934

376

377

378

/// Metrics for tracking memory usage of a ByteCompressedVec

379

#[derive(Debug, Clone)]

380

pub struct CompressedVecMetrics {

381

    /// Actual memory used by the compressed vector (in bytes)

382

    pub actual_memory: usize,

383

    /// Worst-case memory that would be used by an uncompressed vector (len * sizeof(T))

384

    pub worst_case_memory: usize,

385

386

387

impl CompressedVecMetrics {

388

    /// Calculate memory savings in bytes

389

    pub fn memory_savings(&self) -> usize {

390

        self.worst_case_memory.saturating_sub(self.actual_memory)

391

392

393

    /// Calculate memory savings as a percentage

394

    pub fn used_percentage(&self) -> f64 {

395

        if self.worst_case_memory == 0 {

396

0.0

397

        } else {

398

            (self.actual_memory as f64 / self.worst_case_memory as f64) * 100.0

399

400

401

402

403

impl fmt::Display for CompressedVecMetrics {

404

    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {

405

        write!(

406

f,

407

            "memory: {} ({:.1}%), saving: {} ",

408

            BytesFormatter(self.actual_memory),

409

            self.used_percentage(),

410

            BytesFormatter(self.memory_savings()),

411

412

413

414

pub struct ByteCompressedVecIterator<'a, T> {

415

    vector: &'a ByteCompressedVec<T>,

416

    current: usize,

417

    end: usize,

418

419

420

impl<T: CompressedEntry> Iterator for ByteCompressedVecIterator<'_, T> {

421

    type Item = T;

422

423

132272103

    fn next(&mut self) -> Option<Self::Item> {

424

132272103

        if self.current < self.end {

425

132175578

            let result = self.vector.index(self.current);

426

132175578

            self.current += 1;

427

132175578

            Some(result)

428

        } else {

429

96525

            None

430

431

132272103

432

433

    fn size_hint(&self) -> (usize, Option<usize>) {

434

        let remaining = self.end - self.current;

435

        (remaining, Some(remaining))

436

437

438

439

impl<T: CompressedEntry> ExactSizeIterator for ByteCompressedVecIterator<'_, T> {}

440

441

pub trait CompressedEntry {

442

    // Returns the entry as a byte vector

443

    fn to_bytes(&self, bytes: &mut [u8]);

444

445

    // Creates an entry from a byte vector

446

    fn from_bytes(bytes: &[u8]) -> Self;

447

448

    // Returns the number of bytes required to store the current entry

449

    fn bytes_required(&self) -> usize;

450

451

452

impl CompressedEntry for usize {

453

2307789460

    fn to_bytes(&self, bytes: &mut [u8]) {

454

2307789460

        let array = &self.to_le_bytes();

455

3304004127

        for (i, byte) in bytes.iter_mut().enumerate().take(usize::BITS as usize / 8) {

456

3304004127

            *byte = array[i];

457

3304004127

458

2307789460

459

460

25472940755

    fn from_bytes(bytes: &[u8]) -> Self {

461

25472940755

        let mut array = [0; 8];

462

38209070556

        for (i, byte) in bytes.iter().enumerate().take(usize::BITS as usize / 8) {

463

38209070556

            array[i] = *byte;

464

38209070556

465

25472940755

        usize::from_le_bytes(array)

466

25472940755

467

468

2163065861

    fn bytes_required(&self) -> usize {

469

        // Compute the bit width of the value directly. Using `self + 1` would

470

        // overflow at usize::MAX and overestimate by one byte at exact byte

471

        // boundaries (e.g. 255 would report 2 bytes instead of 1).

472

2163065861

        ((*self).max(1).ilog2() / u8::BITS) as usize + 1

473

2163065861

474

475

476

impl<T: CompressedEntry + fmt::Debug> fmt::Debug for ByteCompressedVec<T> {

477

400

    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {

478

400

        f.debug_list().entries(self.iter()).finish()

479

400

480

481

482

/// Implement it for the TagIndex for convenience.

483

impl<T: CompressedEntry + Copy, Tag> CompressedEntry for TagIndex<T, Tag> {

484

    delegate! {

485

        to self.value() {

486

541848033

            fn to_bytes(&self, bytes: &mut [u8]);

487

521974958

            fn bytes_required(&self) -> usize;

488

489

490

491

7092438619

    fn from_bytes(bytes: &[u8]) -> Self {

492

7092438619

        TagIndex::new(T::from_bytes(bytes))

493

7092438619

494

495

496

#[cfg(test)]

497

mod tests {

498

    use rand::RngExt;

499

    use rand::distr::Uniform;

500

    use rand::seq::SliceRandom;

501

502

    use merc_utilities::random_test;

503

504

    use super::ByteCompressedVec;

505

    use super::CompressedEntry;

506

507

    #[test]

508

1

    fn test_index_bytevector() {

509

1

        let mut vec = ByteCompressedVec::new();

510

1

        vec.push(1);

511

1

        assert_eq!(vec.len(), 1);

512

513

1

        vec.push(1024);

514

1

        assert_eq!(vec.len(), 2);

515

516

1

        assert_eq!(vec.index(0), 1);

517

1

        assert_eq!(vec.index(1), 1024);

518

1

519

520

    #[test]

521

1

    fn test_random_bytevector() {

522

1

        let rng = rand::rng();

523

524

1

        let range = Uniform::new(0, usize::MAX).unwrap();

525

1

        let expected_vector: Vec<usize> = rng.sample_iter(range).take(100).collect();

526

1

        let mut vector = ByteCompressedVec::new();

527

528

100

        for element in &expected_vector {

529

100

            vector.push(*element);

530

531

5050

            for (expected, element) in expected_vector.iter().zip(vector.iter()) {

532

5050

                assert_eq!(*expected, element);

533

534

535

1

536

537

    #[test]

538

1

    fn test_random_setting_bytevector() {

539

1

        let rng = rand::rng();

540

541

1

        let range = Uniform::new(0, usize::MAX).unwrap();

542

1

        let expected_vector: Vec<usize> = rng.sample_iter(range).take(100).collect();

543

1

        let mut vector = bytevec![0; 100];

544

545

100

        for (index, element) in expected_vector.iter().enumerate() {

546

100

            vector.set(index, *element);

547

100

548

549

100

        for (expected, element) in expected_vector.iter().zip(vector.iter()) {

550

100

            assert_eq!(*expected, element);

551

552

1

553

554

    #[test]

555

1

    fn test_bytes_required_boundaries() {

556

        // Exact byte boundaries must not be overestimated, and usize::MAX must not overflow.

557

1

        assert_eq!(0usize.bytes_required(), 1);

558

1

        assert_eq!(255usize.bytes_required(), 1);

559

1

        assert_eq!(256usize.bytes_required(), 2);

560

1

        assert_eq!(65535usize.bytes_required(), 2);

561

1

        assert_eq!(65536usize.bytes_required(), 3);

562

1

        assert_eq!(usize::MAX.bytes_required(), (usize::BITS / u8::BITS) as usize);

563

564

        // A round-trip through a vector with the maximum value must work.

565

1

        let mut vec = ByteCompressedVec::new();

566

1

        vec.push(usize::MAX);

567

1

        assert_eq!(vec.index(0), usize::MAX);

568

1

569

570

    #[test]

571

1

    fn test_random_usize_entry() {

572

100

        random_test(100, |rng| {

573

100

            let value = rng.random_range(0..1024);

574

100

            assert!(value.bytes_required() <= 2);

575

576

100

            let mut bytes = [0; 2];

577

100

            value.to_bytes(&mut bytes);

578

100

            assert_eq!(usize::from_bytes(&bytes), value);

579

100

});

580

1

581

582

    #[test]

583

1

    fn test_swap() {

584

1

        let mut vec = ByteCompressedVec::new();

585

1

        vec.push(1);

586

1

        vec.push(256);

587

1

        vec.push(65536);

588

589

1

        vec.swap(0, 2);

590

591

1

        assert_eq!(vec.index(0), 65536);

592

1

        assert_eq!(vec.index(1), 256);

593

1

        assert_eq!(vec.index(2), 1);

594

1

595

596

    #[test]

597

    #[cfg_attr(miri, ignore)] // bitvec violated Stacked Borrows.

598

1

    fn test_random_bytevector_permute() {

599

100

        random_test(100, |rng| {

600

            // Generate random vector to permute

601

100

            let elements = (0..rng.random_range(1..10))

602

489

                .map(|_| rng.random_range(0..100))

603

100

                .collect::<Vec<_>>();

604

605

100

            let vec = ByteCompressedVec::with_iter(elements.iter().cloned());

606

607

200

            for is_inverse in [false, true] {

608

200

                println!("Inverse: {is_inverse}, Input: {:?}", vec);

609

610

200

                let permutation = {

611

200

                    let mut order: Vec<usize> = (0..elements.len()).collect();

612

200

                    order.shuffle(rng);

613

200

                    order

614

};

615

616

200

                let mut permutated = vec.clone();

617

200

                if is_inverse {

618

1956

                    permutated.permute_indices(|i| permutation[i]);

619

                } else {

620

1956

                    permutated.permute(|i| permutation[i]);

621

622

623

200

                println!("Permutation: {:?}", permutation);

624

200

                println!("After permutation: {:?}", permutated);

625

626

                // Check that the permutation was applied correctly

627

978

                for i in 0..elements.len() {

628

978

                    let pos = if is_inverse {

629

489

                        permutation[i]

630

                    } else {

631

489

                        permutation

632

489

                            .iter()

633

1745

                            .position(|&j| i == j)

634

489

                            .expect("Should find inverse mapping")

635

};

636

637

978

                    debug_assert_eq!(

638

978

                        permutated.index(i),

639

978

                        elements[pos],

640

                        "Element at index {} should be {}",

641

i,

642

                        elements[pos]

643

);

644

645

646

100

});

647

1

648

649

    #[test]

650

    #[cfg_attr(miri, ignore)] // bitvec violated Stacked Borrows.

651

1

    fn test_random_bytevector_permute_indices_fast() {

652

100

        random_test(100, |rng| {

653

            // Generate a random vector to permute.

654

100

            let elements = (0..rng.random_range(1..10))

655

522

                .map(|_| rng.random_range(0..100))

656

100

                .collect::<Vec<_>>();

657

658

100

            let vec = ByteCompressedVec::with_iter(elements.iter().cloned());

659

660

100

            let permutation = {

661

100

                let mut order: Vec<usize> = (0..elements.len()).collect();

662

100

                order.shuffle(rng);

663

100

                order

664

};

665

666

100

            let mut fast = vec.clone();

667

522

            fast.permute_indices_fast(|i| permutation[i]);

668

669

            // The result must be [v_p(0), v_p(1), ..., v_p(n-1)].

670

522

            for i in 0..elements.len() {

671

522

                assert_eq!(

672

522

                    fast.index(i),

673

522

                    elements[permutation[i]],

674

                    "Element at index {} should be {}",

675

i,

676

                    elements[permutation[i]]

677

);

678

679

680

            // It must also agree with the slower `permute_indices`.

681

100

            let mut slow = vec.clone();

682

2088

            slow.permute_indices(|i| permutation[i]);

683

100

            assert_eq!(fast, slow, "fast and slow permutation must agree");

684

100

});

685

1

686