commit 4d38849501ca09c2dcd9e778b59f9a4ec32180dd
author David 'Digit' Turner <digit@google.com> Mon Dec 04 22:47:37 2023 +0100
committer David 'Digit' Turner <digit+github@google.com> Thu Dec 07 19:55:05 2023 +0100
tree e92a09a54a4817b24416880a3457388d59449db9
parent 09b6b4e13a365ff04bc865fd6b4c6f1f52032617

CanonicalizePath: Remove kMaxComponents limit

This patch refactors the CanonicalizePath() to fix
two issues and improve performance. This is achieved
through the following:

- Remove the kMaxPathComponents limit entirely,
  which fixes ninja-build#1732, by dropping the
  `components` array entirely, in favor of
  back-tracking the destination pointer.

- Properly handle '/' and '\' which were incorrectly
  converted into an empty string. This fixes
  ninja-build#2008.

- Skip initial '../' components in relative paths,
  as these are common when referencing source files
  in build plans, and doing so make the loop after
  this step run faster in practice since most
  source files do not need adjustments.

- Simplify the inner loop logic by handling the
  last component (which is not followed by a
  trailing directory separator) separately.

  This noticeably improves performance because
  the inner loop becomes smaller with less branch
  mis-predictions in the general case.

- Never access or copy the caharacter after the
  end of the input string.

- Use memchr() to find the next '/' on Posix, which
  allows the use of SIMD implementations provided by
  the C runtime (e.g. through IFUNC functions on Linux),
  resulting in very noticeable speedup. This is also
  why a statically Ninja executable will be slower
  than one that links to the C library dynamically :-/

- Avoid performing any writes when the input path
  doesn't need any adjustment, which is also quite
  common.

Note that this patch does _not_ remove the 64-bit
limit for the `slash_bits`  value, which is only
used on Win32.

Benchmarking was done in several ways:

- On Linux, running `hyperfine canon-perftest` to run the
  canonicalization benchmark program and measure its total
  running time. Three compilers were used to generate
  dynamically-linked executables.

  ```
               BEFORE (ms)  AFTER (ms)

  GCC 13.2.0      651         369
  Clang 14.0      591         402
  Clang 18,0      653         400
  ```

- On Windows, running `canon-perftest` 5 times and keeping
  the best reported average result. The number are slower
  since they only measure the benched function.

  ```
                   BEFORE (ms)  AFTER (ms)

  Mingw64 GCC 12      246         195
  ```

- On Linux, run `hyperfine ninja -C out/default -n --quiet`
  on a large Fuchsia build plan, once with 70000+ pending
  commands, and once after the build (i.e. `ninja: no work to do`).

  ````
               BEFORE (s)  AFTER (s)

  pre_build       8.789    8.647
  post_build      6.703    6.590
  ```