It failed on names like '/nix/store/9ip48nkc9rfy0a4yaw98lp6gipqlib1a-'.

The evaluator was spending about 1% of its time compiling a small
number of regexes over and over again.

In

  nix-instantiate --dry-run '<nixpkgs/nixos/release-combined.nix>' -A nixos.tests.simple.x86_64-linux

this reduces time spent in unparse() from 9.15% to 4.31%. The main
culprit was appending characters one at a time to the destination
string. Even though the string has enough capacity, push_back() still
needs to check this on every call.

…t/nix-1

This was broken by 22a754c.

https://hydra.nixos.org/eval/1573669

We now parse function applications as a vector of arguments rather
than as a chain of binary applications, e.g. 'substring 1 2 "foo"' is
parsed as

  ExprCall { .fun = <substring>, .args = [ <1>, <2>, <"foo"> ] }

rather than

  ExprApp (ExprApp (ExprApp <substring> <1>) <2>) <"foo">

This allows primops to be called immediately (if enough arguments are
supplied) without having to allocate intermediate tPrimOpApp values.

On

  $ nix-instantiate --dry-run '<nixpkgs/nixos/release-combined.nix>' -A nixos.tests.simple.x86_64-linux

this gives a substantial performance improvement:

  user CPU time:      median =      0.9209  mean =      0.9218  stddev =      0.0073  min =      0.9086  max =      0.9340  [rejected, p=0.00000, Δ=-0.21433±0.00677]
  elapsed time:       median =      1.0585  mean =      1.0584  stddev =      0.0024  min =      1.0523  max =      1.0623  [rejected, p=0.00000, Δ=-0.20594±0.00236]

because it reduces the number of tPrimOpApp allocations from 551990 to
42534 (i.e. only small minority of primop calls are partially
applied) which in turn reduces time spent in the garbage collector.

Previously an expression like 'x: y: ...' would create two
environments with one value. Now it creates one environment with two
values. This reduces the number of allocations and the distance in the
environment chain that variable lookups need to traverse.

On

  $ nix-instantiate --dry-run '<nixpkgs/nixos/release-combined.nix>' -A nixos.tests.simple.x86_64-linux

this gives a ~30% reduction in the number of Env allocations.