dirstate: Remove the flat Rust DirstateMap implementation Before this changeset we had two Rust implementations of `DirstateMap`. This removes the "flat" DirstateMap so that the "tree" DirstateMap is always used when Rust enabled. This simplifies the code a lot, and will enable (in the next changeset) further removal of a trait abstraction. This is a performance regression when: * Rust is enabled, and * The repository uses the legacy dirstate-v1 file format, and * For `hg status`, unknown files are not listed (such as with `-mard`) The regression is about 100 milliseconds for `hg status -mard` on a semi-large repository (mozilla-central), from ~320ms to ~420ms. We deem this to be small enough to be worth it. The new dirstate-v2 is still experimental at this point, but we aim to stabilize it (though not yet enable it by default for new repositories) in Mercurial 6.0. Eventually, upgrating repositories to dirsate-v2 will eliminate this regression (and enable other performance improvements). # Background The flat DirstateMap was introduced with the first Rust implementation of the status algorithm. It works similarly to the previous Python + C one, with a single `HashMap` that associates file paths to a `DirstateEntry` (where Python has a dict). We later added the tree DirstateMap where the root of the tree contains nodes for files and directories that are directly at the root of the repository, and nodes for directories can contain child nodes representing the files and directly that *they* contain directly. The shape of this tree mirrors that of the working directory in the filesystem. This enables the status algorithm to traverse this tree in tandem with traversing the filesystem tree, which in turns enables a more efficient algorithm. Furthermore, the new dirstate-v2 file format is also based on a tree of the same shape. The tree DirstateMap can access a dirstate-v2 file without parsing it: binary data in a single large (possibly memory-mapped) bytes buffer is traversed on demand. This allows `DirstateMap` creation to take `O(1)` time. (Mutation works by creating new in-memory nodes with copy-on-write semantics, and serialization is append-mostly.) The tradeoff is that for "legacy" repositories that use the dirstate-v1 file format, parsing that file into a tree DirstateMap takes more time. Profiling shows that this time is dominated by `HashMap`. For a dirstate containing `F` files with an average `D` directory depth, the flat DirstateMap does parsing in `O(F)` number of HashMap operations but the tree DirstateMap in `O(F × D)` operations, since each node has its own HashMap containing its child nodes. This slower costs ~140ms on an old snapshot of mozilla-central, and ~80ms on an old snapshot of the Netbeans repository. The status algorithm is faster, but with `-mard` (when not listing unknown files) it is typically not faster *enough* to compensate the slower parsing. Both Rust implementations are always faster than the Python + C implementation # Benchmark results All benchmarks are run on changeset 98c0408324e6, with repositories that use the dirstate-v1 file format, on a server with 4 CPU cores and 4 CPU threads (no HyperThreading). `hg status` benchmarks show wall clock times of the entire command as the average and standard deviation of serveral runs, collected by https://github.com/sharkdp/hyperfine and reformated. Parsing benchmarks are wall clock time of the Rust function that converts a bytes buffer of the dirstate file into the `DirstateMap` data structure as used by the status algorithm. A single run each, collected by running `hg status` this environment variable: RUST_LOG=hg::dirstate::dirstate_map=trace,hg::dirstate_tree::dirstate_map=trace Benchmark 1: Rust flat DirstateMap → Rust tree DirstateMap hg status mozilla-clean 562.3 ms ± 2.0 ms → 462.5 ms ± 0.6 ms 1.22 ± 0.00 times faster mozilla-dirty 859.6 ms ± 2.2 ms → 719.5 ms ± 3.2 ms 1.19 ± 0.01 times faster mozilla-ignored 558.2 ms ± 3.0 ms → 457.9 ms ± 2.9 ms 1.22 ± 0.01 times faster mozilla-unknowns 859.4 ms ± 5.7 ms → 716.0 ms ± 4.7 ms 1.20 ± 0.01 times faster netbeans-clean 336.5 ms ± 0.9 ms → 339.5 ms ± 0.4 ms 0.99 ± 0.00 times faster netbeans-dirty 491.4 ms ± 1.6 ms → 475.1 ms ± 1.2 ms 1.03 ± 0.00 times faster netbeans-ignored 343.7 ms ± 1.0 ms → 347.8 ms ± 0.4 ms 0.99 ± 0.00 times faster netbeans-unknowns 484.3 ms ± 1.0 ms → 466.0 ms ± 1.2 ms 1.04 ± 0.00 times faster hg status -mard mozilla-clean 317.3 ms ± 0.6 ms → 422.5 ms ± 1.2 ms 0.75 ± 0.00 times faster mozilla-dirty 315.4 ms ± 0.6 ms → 417.7 ms ± 1.1 ms 0.76 ± 0.00 times faster mozilla-ignored 314.6 ms ± 0.6 ms → 417.4 ms ± 1.0 ms 0.75 ± 0.00 times faster mozilla-unknowns 312.9 ms ± 0.9 ms → 417.3 ms ± 1.6 ms 0.75 ± 0.00 times faster netbeans-clean 212.0 ms ± 0.6 ms → 283.6 ms ± 0.8 ms 0.75 ± 0.00 times faster netbeans-dirty 211.4 ms ± 1.0 ms → 283.4 ms ± 1.6 ms 0.75 ± 0.01 times faster netbeans-ignored 211.4 ms ± 0.9 ms → 283.9 ms ± 0.8 ms 0.74 ± 0.01 times faster netbeans-unknowns 211.1 ms ± 0.6 ms → 283.4 ms ± 1.0 ms 0.74 ± 0.00 times faster Parsing mozilla-clean 38.4ms → 177.6ms mozilla-dirty 38.8ms → 177.0ms mozilla-ignored 38.8ms → 178.0ms mozilla-unknowns 38.7ms → 176.9ms netbeans-clean 16.5ms → 97.3ms netbeans-dirty 16.5ms → 98.4ms netbeans-ignored 16.9ms → 97.4ms netbeans-unknowns 16.9ms → 96.3ms Benchmark 2: Python + C dirstatemap → Rust tree DirstateMap hg status mozilla-clean 1261.0 ms ± 3.6 ms → 461.1 ms ± 0.5 ms 2.73 ± 0.00 times faster mozilla-dirty 2293.4 ms ± 9.1 ms → 719.6 ms ± 3.6 ms 3.19 ± 0.01 times faster mozilla-ignored 1240.4 ms ± 2.3 ms → 457.7 ms ± 1.9 ms 2.71 ± 0.00 times faster mozilla-unknowns 2283.3 ms ± 9.0 ms → 719.7 ms ± 3.8 ms 3.17 ± 0.01 times faster netbeans-clean 879.7 ms ± 3.5 ms → 339.9 ms ± 0.5 ms 2.59 ± 0.00 times faster netbeans-dirty 1257.3 ms ± 4.7 ms → 474.6 ms ± 1.6 ms 2.65 ± 0.01 times faster netbeans-ignored 943.9 ms ± 1.9 ms → 347.3 ms ± 1.1 ms 2.72 ± 0.00 times faster netbeans-unknowns 1188.1 ms ± 5.0 ms → 465.2 ms ± 2.3 ms 2.55 ± 0.01 times faster hg status -mard mozilla-clean 903.2 ms ± 3.6 ms → 423.4 ms ± 2.2 ms 2.13 ± 0.01 times faster mozilla-dirty 884.6 ms ± 4.5 ms → 417.3 ms ± 1.4 ms 2.12 ± 0.01 times faster mozilla-ignored 881.9 ms ± 1.3 ms → 417.3 ms ± 0.8 ms 2.11 ± 0.00 times faster mozilla-unknowns 878.5 ms ± 1.9 ms → 416.4 ms ± 0.9 ms 2.11 ± 0.00 times faster netbeans-clean 434.9 ms ± 1.8 ms → 284.0 ms ± 0.8 ms 1.53 ± 0.01 times faster netbeans-dirty 434.1 ms ± 0.8 ms → 283.1 ms ± 0.8 ms 1.53 ± 0.00 times faster netbeans-ignored 431.7 ms ± 1.1 ms → 283.6 ms ± 1.8 ms 1.52 ± 0.01 times faster netbeans-unknowns 433.0 ms ± 1.3 ms → 283.5 ms ± 0.7 ms 1.53 ± 0.00 times faster Differential Revision: https://phab.mercurial-scm.org/D11516

     1

#testcases dirstate-v1 dirstate-v2

     2

     3

#if dirstate-v2

     4

#require rust

     5

  $ echo '[format]' >> $HGRCPATH

     6

  $ echo 'exp-dirstate-v2=1' >> $HGRCPATH

     7

#endif

     8

     9

init

    10

    11

  $ hg init t

    12

  $ cd t

    13

    14

setup

    15

    16

  $ echo r1 > r1

    17

  $ hg ci -qAmr1 -d'0 0'

    18

  $ mkdir directory

    19

  $ echo r2 > directory/r2

    20

  $ hg ci -qAmr2 -d'1 0'

    21

  $ echo 'ignored' > .hgignore

    22

  $ hg ci -qAmr3 -d'2 0'

    23

    24

purge without the extension

    25

    26

  $ hg st

    27

  $ touch foo

    28

  $ hg purge

    29

  permanently delete 1 unkown files? (yN) n

    30

  abort: removal cancelled

    31

  [250]

    32

  $ hg st

    33

  ? foo

    34

  $ hg purge --no-confirm

    35

  $ hg st

    36

    37

now enabling the extension

    38

    39

  $ cat <<EOF >> $HGRCPATH

    40

  > [extensions]

    41

  > purge =

    42

  > EOF

    43

    44

delete an empty directory

    45

    46

  $ mkdir empty_dir

    47

  $ hg purge -p -v

    48

  empty_dir

    49

  $ hg purge --confirm

    50

  permanently delete at least 1 empty directories? (yN) n

    51

  abort: removal cancelled

    52

  [250]

    53

  $ hg purge -v

    54

  removing directory empty_dir

    55

  $ ls -A

    56

  .hg

    57

  .hgignore

    58

  directory

    59

  r1

    60

    61

delete an untracked directory

    62

    63

  $ mkdir untracked_dir

    64

  $ touch untracked_dir/untracked_file1

    65

  $ touch untracked_dir/untracked_file2

    66

  $ hg purge -p

    67

  untracked_dir/untracked_file1

    68

  untracked_dir/untracked_file2

    69

  $ hg purge -v

    70

  removing file untracked_dir/untracked_file1

    71

  removing file untracked_dir/untracked_file2

    72

  removing directory untracked_dir

    73

  $ ls -A

    74

  .hg

    75

  .hgignore

    76

  directory

    77

  r1

    78

    79

delete an untracked file

    80

    81

  $ touch untracked_file

    82

  $ touch untracked_file_readonly

    83

  $ "$PYTHON" <<EOF

    84

  > import os

    85

  > import stat

    86

  > f = 'untracked_file_readonly'

    87

  > os.chmod(f, stat.S_IMODE(os.stat(f).st_mode) & ~stat.S_IWRITE)

    88

  > EOF

    89

  $ hg purge -p

    90

  untracked_file

    91

  untracked_file_readonly

    92

  $ hg purge --confirm

    93

  permanently delete 2 unkown files? (yN) n

    94

  abort: removal cancelled

    95

  [250]

    96

  $ hg purge -v

    97

  removing file untracked_file

    98

  removing file untracked_file_readonly

    99

  $ ls -A

   100

  .hg

   101

  .hgignore

   102

  directory

   103

  r1

   104

   105

delete an untracked file in a tracked directory

   106

   107

  $ touch directory/untracked_file

   108

  $ hg purge -p

   109

  directory/untracked_file

   110

  $ hg purge -v

   111

  removing file directory/untracked_file

   112

  $ ls -A

   113

  .hg

   114

  .hgignore

   115

  directory

   116

  r1

   117

   118

delete nested directories

   119

   120

  $ mkdir -p untracked_directory/nested_directory

   121

  $ hg purge -p

   122

  untracked_directory/nested_directory

   123

  $ hg purge -v

   124

  removing directory untracked_directory/nested_directory

   125

  removing directory untracked_directory

   126

  $ ls -A

   127

  .hg

   128

  .hgignore

   129

  directory

   130

  r1

   131

   132

delete nested directories from a subdir

   133

   134

  $ mkdir -p untracked_directory/nested_directory

   135

  $ cd directory

   136

  $ hg purge -p

   137

  untracked_directory/nested_directory

   138

  $ hg purge -v

   139

  removing directory untracked_directory/nested_directory

   140

  removing directory untracked_directory

   141

  $ cd ..

   142

  $ ls -A

   143

  .hg

   144

  .hgignore

   145

  directory

   146

  r1

   147

   148

delete only part of the tree

   149

   150

  $ mkdir -p untracked_directory/nested_directory

   151

  $ touch directory/untracked_file

   152

  $ cd directory

   153

  $ hg purge -p ../untracked_directory

   154

  untracked_directory/nested_directory

   155

  $ hg purge --confirm

   156

  permanently delete 1 unkown files? (yN) n

   157

  abort: removal cancelled

   158

  [250]

   159

  $ hg purge -v ../untracked_directory

   160

  removing directory untracked_directory/nested_directory

   161

  removing directory untracked_directory

   162

  $ cd ..

   163

  $ ls -A

   164

  .hg

   165

  .hgignore

   166

  directory

   167

  r1

   168

  $ ls directory/untracked_file

   169

  directory/untracked_file

   170

  $ rm directory/untracked_file

   171

   172

skip ignored files if -i or --all not specified

   173

   174

  $ touch ignored

   175

  $ hg purge -p

   176

  $ hg purge --confirm

   177

  $ hg purge -v

   178

  $ touch untracked_file

   179

  $ ls

   180

  directory

   181

  ignored

   182

  r1

   183

  untracked_file

   184

  $ hg purge -p -i

   185

  ignored

   186

  $ hg purge --confirm -i

   187

  permanently delete 1 ignored files? (yN) n

   188

  abort: removal cancelled

   189

  [250]

   190

  $ hg purge -v -i

   191

  removing file ignored

   192

  $ ls -A

   193

  .hg

   194

  .hgignore

   195

  directory

   196

  r1

   197

  untracked_file

   198

  $ touch ignored

   199

  $ hg purge -p --all

   200

  ignored

   201

  untracked_file

   202

  $ hg purge --confirm --all

   203

  permanently delete 1 unkown and 1 ignored files? (yN) n

   204

  abort: removal cancelled

   205

  [250]

   206

  $ hg purge -v --all

   207

  removing file ignored

   208

  removing file untracked_file

   209

  $ ls

   210

  directory

   211

  r1

   212

   213

abort with missing files until we support name mangling filesystems

   214

   215

  $ touch untracked_file

   216

  $ rm r1

   217

   218

hide error messages to avoid changing the output when the text changes

   219

   220

  $ hg purge -p 2> /dev/null

   221

  untracked_file

   222

  $ hg st

   223

  ! r1

   224

  ? untracked_file

   225

   226

  $ hg purge -p

   227

  untracked_file

   228

  $ hg purge -v 2> /dev/null

   229

  removing file untracked_file

   230

  $ hg st

   231

  ! r1

   232

   233

  $ hg purge -v

   234

  $ hg revert --all --quiet

   235

  $ hg st -a

   236

   237

tracked file in ignored directory (issue621)

   238

   239

  $ echo directory >> .hgignore

   240

  $ hg ci -m 'ignore directory'

   241

  $ touch untracked_file

   242

  $ hg purge -p

   243

  untracked_file

   244

  $ hg purge -v

   245

  removing file untracked_file

   246

   247

skip excluded files

   248

   249

  $ touch excluded_file

   250

  $ hg purge -p -X excluded_file

   251

  $ hg purge -v -X excluded_file

   252

  $ ls -A

   253

  .hg

   254

  .hgignore

   255

  directory

   256

  excluded_file

   257

  r1

   258

  $ rm excluded_file

   259

   260

skip files in excluded dirs

   261

   262

  $ mkdir excluded_dir

   263

  $ touch excluded_dir/file

   264

  $ hg purge -p -X excluded_dir

   265

  $ hg purge -v -X excluded_dir

   266

  $ ls -A

   267

  .hg

   268

  .hgignore

   269

  directory

   270

  excluded_dir

   271

  r1

   272

  $ ls excluded_dir

   273

  file

   274

  $ rm -R excluded_dir

   275

   276

skip excluded empty dirs

   277

   278

  $ mkdir excluded_dir

   279

  $ hg purge -p -X excluded_dir

   280

  $ hg purge -v -X excluded_dir

   281

  $ ls -A

   282

  .hg

   283

  .hgignore

   284

  directory

   285

  excluded_dir

   286

  r1

   287

  $ rmdir excluded_dir

   288

   289

skip patterns

   290

   291

  $ mkdir .svn

   292

  $ touch .svn/foo

   293

  $ mkdir directory/.svn

   294

  $ touch directory/.svn/foo

   295

  $ hg purge -p -X .svn -X '*/.svn'

   296

  $ hg purge -p -X re:.*.svn

   297

   298

  $ rm -R .svn directory r1

   299

   300

only remove files

   301

   302

  $ mkdir -p empty_dir dir

   303

  $ touch untracked_file dir/untracked_file

   304

  $ hg purge -p --files

   305

  dir/untracked_file

   306

  untracked_file

   307

  $ hg purge -v --files

   308

  removing file dir/untracked_file

   309

  removing file untracked_file

   310

  $ ls -A

   311

  .hg

   312

  .hgignore

   313

  dir

   314

  empty_dir

   315

  $ ls dir

   316

   317

only remove dirs

   318

   319

  $ mkdir -p empty_dir dir

   320

  $ touch untracked_file dir/untracked_file

   321

  $ hg purge -p --dirs

   322

  empty_dir

   323

  $ hg purge -v --dirs

   324

  removing directory empty_dir

   325

  $ ls -A

   326

  .hg

   327

  .hgignore

   328

  dir

   329

  untracked_file

   330

  $ ls dir

   331

  untracked_file

   332

   333

remove both files and dirs

   334

   335

  $ mkdir -p empty_dir dir

   336

  $ touch untracked_file dir/untracked_file

   337

  $ hg purge -p --files --dirs

   338

  dir/untracked_file

   339

  untracked_file

   340

  empty_dir

   341

  $ hg purge -v --files --dirs

   342

  removing file dir/untracked_file

   343

  removing file untracked_file

   344

  removing directory empty_dir

   345

  removing directory dir

   346

  $ ls -A

   347

  .hg

   348

  .hgignore

   349

   350

  $ cd ..