[m-dev.] speeding up the handling of code with large ground terms

[Zoltan Somogyi]

I am just finishing work on a change that special-cases the compiler's handling
of scopes that result from the expansion into superhomogeneous form of large
ground terms. I looked at every part of the compiler that handles scopes,
and was able to avoid scanning the (possibly huge) code inside those scopes
in most cases.

This diff speeds up the compilation time of the training_cars_full stress
test by more than a factor of three: on my laptop, compilation time goes
from 97.5 seconds to 31.5, mostly in the two passes I did not look at:
type checking and code generation. (I am attaching the output of mmc -vS
for the comparison.) There is no meaningful impact on the speed of
compilation for other code; the difference in the times returned by
tools/speedtest, which compiles six of the compiler's own modules,
is in the noise.

Due to the extensive nature of the changes, I will run lots of bootchecks
in different grades and at different optimization levels before committing
this change (it has already passed bootcheck in asm_fast.gc at -O6).

I expect to post the diff later today. Since the changes affect most parts
of the compiler, I would like Julien, Mark and Ralph to each review some
parts of the diff, preferably including the modules each of you know best.
I am away the first three days of next week, so there is no hurry.

Zoltan.
-------------- next part --------------
% Parsing file `training_cars_full' and imported interfaces...
% Module qualifying items...
% done.
[User time: +0.309s, 0.309s, Real time: +0.471s, 0.471s, D Stack: 0.375k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 3, Heap used since last GC: 20903.836k, Total used: 50420.000k]
% Expanding equivalence types... done.
[User time: +0.000s, 0.309s, Real time: +0.002s, 0.473s, D Stack: 0.375k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 3, Heap used since last GC: 21146.898k, Total used: 50420.000k]
% Converting parse tree to hlds...
% Processed all items in pass 1
[User time: +0.010s, 0.319s, Real time: +0.013s, 0.486s, D Stack: 0.422k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 3, Heap used since last GC: 22917.375k, Total used: 50420.000k]
% Processed all items in pass 2
[User time: +0.000s, 0.319s, Real time: +0.003s, 0.489s, D Stack: 0.422k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 3, Heap used since last GC: 23289.711k, Total used: 50420.000k]
% done.
[User time: +7.290s, 7.609s, Real time: +7.338s, 7.827s, D Stack: 0.379k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 23, Heap used since last GC: 17608.562k, Total used: 115956.000k]
% Writing auto-dependency file `training_cars_full.d'... done.
% Checking typeclasses...
% Checking instance declaration types...
% Checking typeclass instances...
% Checking for cyclic classes...
% Checking for missing concrete instances...
% Checking functional dependencies on instances...
% Checking typeclass constraints...
% Checking that insts have matching types... done.
% Type-checking...
% Type-checking clauses...
[User time: +9.040s, 16.649s, Real time: +9.110s, 16.937s, D Stack: 0.305k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 31, Heap used since last GC: 71703.953k, Total used: 197908.000k]
% Program is type-correct.
% Purity-checking clauses...
[User time: +1.020s, 17.669s, Real time: +1.030s, 17.967s, D Stack: 0.348k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 32, Heap used since last GC: 28709.633k, Total used: 197908.000k]
% Program is purity-correct.
[User time: +0.000s, 17.669s, Real time: +0.000s, 17.967s, D Stack: 0.328k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 32, Heap used since last GC: 28709.656k, Total used: 197908.000k]
% Substituting implementation-defined literals...
% done.
[User time: +0.040s, 17.709s, Real time: +0.035s, 18.002s, D Stack: 0.320k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 32, Heap used since last GC: 30562.258k, Total used: 197908.000k]
% Transforming polymorphic unifications... done.
[User time: +0.330s, 18.039s, Real time: +0.335s, 18.337s, D Stack: 0.359k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 32, Heap used since last GC: 56665.664k, Total used: 197908.000k]
% Mode-checking clauses...
[User time: +15.990s, 34.029s, Real time: +16.059s, 34.396s, D Stack: 0.379k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 38, Heap used since last GC: 38978.469k, Total used: 296212.000k]
% Program is mode-correct.
[User time: +0.000s, 34.029s, Real time: +0.000s, 34.396s, D Stack: 0.363k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 38, Heap used since last GC: 38978.477k, Total used: 296212.000k]
% Detecting switches...
% done.
[User time: +0.250s, 34.279s, Real time: +0.255s, 34.651s, D Stack: 0.355k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 38, Heap used since last GC: 81524.281k, Total used: 312596.000k]
% Detecting common deconstructions...
% done.
[User time: +1.690s, 35.969s, Real time: +1.702s, 36.353s, D Stack: 0.355k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 39, Heap used since last GC: 6766.961k, Total used: 312596.000k]
% Doing determinism checking...
% done.
% Program is determinism-correct.
[User time: +0.470s, 36.439s, Real time: +0.472s, 36.825s, D Stack: 0.359k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 39, Heap used since last GC: 83698.273k, Total used: 312596.000k]
% Checking for backtracking over unique modes...
% Program is unique-mode-correct.
[User time: +10.250s, 46.689s, Real time: +10.298s, 47.123s, D Stack: 0.359k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 42, Heap used since last GC: 146054.523k, Total used: 394516.000k]
% Simplifying goals...
% done.
[User time: +9.030s, 55.719s, Real time: +9.079s, 56.202s, D Stack: 0.379k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 44, Heap used since last GC: 50664.344k, Total used: 443668.000k]
% Transforming tabled predicates... done.
[User time: +0.000s, 55.719s, Real time: +0.001s, 56.203s, D Stack: 0.285k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 44, Heap used since last GC: 50684.930k, Total used: 443668.000k]
% Transforming lambda expressions... done.
[User time: +0.060s, 55.779s, Real time: +0.056s, 56.259s, D Stack: 0.285k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 44, Heap used since last GC: 59160.477k, Total used: 443668.000k]
% Transforming stm expressions... done.
[User time: +0.220s, 55.999s, Real time: +0.221s, 56.480s, D Stack: 0.285k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 44, Heap used since last GC: 99214.844k, Total used: 443668.000k]
% Fully expanding equivalence types... done.
[User time: +10.540s, 66.539s, Real time: +10.538s, 67.018s, D Stack: 0.285k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 45, Heap used since last GC: 80867.922k, Total used: 443732.000k]
% Generating type_ctor_info structures... done.
[User time: +0.000s, 66.539s, Real time: +0.000s, 67.018s, D Stack: 0.285k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 45, Heap used since last GC: 80869.953k, Total used: 443732.000k]
% Specializing higher-order and polymorphic predicates...
% done.
[User time: +2.910s, 69.449s, Real time: +2.910s, 69.928s, D Stack: 0.293k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 46, Heap used since last GC: 33740.188k, Total used: 443732.000k]
% Inlining...
% done.
[User time: +0.070s, 69.519s, Real time: +0.075s, 70.003s, D Stack: 0.297k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 46, Heap used since last GC: 37100.852k, Total used: 443732.000k]
% Eliminating dead procedures...
% done.
[User time: +0.020s, 69.539s, Real time: +0.026s, 70.029s, D Stack: 0.285k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 46, Heap used since last GC: 37108.656k, Total used: 443732.000k]
% Updating interface:
% training_cars_full.mh' has not changed.
% Mapping args to regs... done.
[User time: +0.010s, 69.549s, Real time: +0.031s, 70.060s, D Stack: 0.281k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 46, Heap used since last GC: 37586.641k, Total used: 443732.000k]
% Migrating branch code... done.
[User time: +0.020s, 69.569s, Real time: +0.020s, 70.080s, D Stack: 0.289k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 46, Heap used since last GC: 40883.000k, Total used: 443732.000k]
% Simplifying goals...
% done.
[User time: +3.370s, 72.939s, Real time: +3.386s, 73.466s, D Stack: 0.312k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 47, Heap used since last GC: 94454.562k, Total used: 476500.000k]
% Computing liveness...
% done.
[User time: +16.980s, 89.919s, Real time: +17.063s, 90.529s, D Stack: 0.297k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 52, Heap used since last GC: 79235.312k, Total used: 574804.000k]
% Computing stack vars... done.
[User time: +0.140s, 90.059s, Real time: +0.136s, 90.665s, D Stack: 0.289k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 52, Heap used since last GC: 88532.594k, Total used: 574804.000k]
% Allocating store map... done.
[User time: +0.100s, 90.159s, Real time: +0.107s, 90.772s, D Stack: 0.289k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 52, Heap used since last GC: 101187.773k, Total used: 574804.000k]
% Generating code...
% done.
[User time: +7.040s, 97.199s, Real time: +7.041s, 97.813s, D Stack: 0.293k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 53, Heap used since last GC: 194819.086k, Total used: 591188.000k]
% Generating call continuation information... done.
[User time: +0.000s, 97.199s, Real time: +0.000s, 97.813s, D Stack: 0.297k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 53, Heap used since last GC: 194819.086k, Total used: 591188.000k]
% Doing optimizations...
% done.
[User time: +0.000s, 97.199s, Real time: +0.001s, 97.814s, D Stack: 0.293k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 53, Heap used since last GC: 194927.391k, Total used: 591188.000k]
% Writing output to `training_cars_full.c'... done.
[User time: +0.310s, 97.509s, Real time: +0.330s, 98.144s, D Stack: 0.312k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 53, Heap used since last GC: 200071.312k, Total used: 591188.000k]
% Updating interface:
% training_cars_full.mh' has not changed.
% Touching `training_cars_full.c_date'...  done.
-------------- next part --------------
% Parsing file `training_cars_full' and imported interfaces...
% Module qualifying items...
% done.
[User time: +0.340s, 0.340s, Real time: +0.369s, 0.369s, D Stack: 0.375k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 3, Heap used since last GC: 20849.398k, Total used: 50420.000k]
% Expanding equivalence types... done.
[User time: +0.000s, 0.340s, Real time: +0.002s, 0.371s, D Stack: 0.375k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 3, Heap used since last GC: 21092.461k, Total used: 50420.000k]
% Converting parse tree to hlds...
% Processed all items in pass 1
[User time: +0.010s, 0.350s, Real time: +0.012s, 0.383s, D Stack: 0.422k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 3, Heap used since last GC: 22862.938k, Total used: 50420.000k]
% Processed all items in pass 2
[User time: +0.000s, 0.350s, Real time: +0.003s, 0.386s, D Stack: 0.422k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 3, Heap used since last GC: 23235.273k, Total used: 50420.000k]
% Processed all items in pass 3
% done.
[User time: +2.860s, 3.210s, Real time: +2.906s, 3.292s, D Stack: 0.379k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 11, Heap used since last GC: 12963.984k, Total used: 99572.000k]
% Writing auto-dependency file `training_cars_full.d'... done.
% Checking typeclasses...
% Checking instance declaration types...
% Checking typeclass instances...
% Checking for cyclic classes...
% Checking for missing concrete instances...
% Checking functional dependencies on instances...
% Checking typeclass constraints...
% Checking that insts have matching types... done.
% Type-checking...
% Type-checking clauses...
[User time: +8.620s, 11.830s, Real time: +8.696s, 11.988s, D Stack: 0.305k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 19, Heap used since last GC: 69025.625k, Total used: 197908.000k]
% Program is type-correct.
% Purity-checking clauses...
[User time: +0.990s, 12.820s, Real time: +0.995s, 12.983s, D Stack: 0.348k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 20, Heap used since last GC: 27589.141k, Total used: 197908.000k]
% Program is purity-correct.
[User time: +0.000s, 12.820s, Real time: +0.000s, 12.983s, D Stack: 0.328k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 20, Heap used since last GC: 27589.164k, Total used: 197908.000k]
% Substituting implementation-defined literals...
% done.
[User time: +0.030s, 12.850s, Real time: +0.033s, 13.016s, D Stack: 0.320k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 20, Heap used since last GC: 29441.766k, Total used: 197908.000k]
% Transforming polymorphic unifications... done.
[User time: +0.330s, 13.180s, Real time: +0.327s, 13.343s, D Stack: 0.359k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 20, Heap used since last GC: 55545.172k, Total used: 197908.000k]
% Mode-checking clauses...
[User time: +1.270s, 14.450s, Real time: +1.277s, 14.620s, D Stack: 0.379k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 21, Heap used since last GC: 41941.156k, Total used: 214292.000k]
% Program is mode-correct.
[User time: +0.000s, 14.450s, Real time: +0.000s, 14.620s, D Stack: 0.363k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 21, Heap used since last GC: 41941.164k, Total used: 214292.000k]
% Detecting switches...
% done.
[User time: +0.020s, 14.470s, Real time: +0.017s, 14.637s, D Stack: 0.355k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 21, Heap used since last GC: 44006.281k, Total used: 214292.000k]
% Detecting common deconstructions...
% done.
[User time: +0.000s, 14.470s, Real time: +0.007s, 14.644s, D Stack: 0.355k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 21, Heap used since last GC: 44934.648k, Total used: 214292.000k]
% Doing determinism checking...
% done.
% Program is determinism-correct.
[User time: +0.030s, 14.500s, Real time: +0.023s, 14.667s, D Stack: 0.359k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 21, Heap used since last GC: 47670.961k, Total used: 214292.000k]
% Checking for backtracking over unique modes...
% Program is unique-mode-correct.
[User time: +0.100s, 14.600s, Real time: +0.106s, 14.773s, D Stack: 0.359k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 21, Heap used since last GC: 57339.766k, Total used: 214292.000k]
% Simplifying goals...
% done.
[User time: +0.080s, 14.680s, Real time: +0.082s, 14.855s, D Stack: 0.379k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 21, Heap used since last GC: 63498.820k, Total used: 230676.000k]
% Transforming tabled predicates... done.
[User time: +0.000s, 14.680s, Real time: +0.001s, 14.856s, D Stack: 0.285k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 21, Heap used since last GC: 63519.406k, Total used: 230676.000k]
% Transforming lambda expressions... done.
[User time: +0.010s, 14.690s, Real time: +0.004s, 14.860s, D Stack: 0.285k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 21, Heap used since last GC: 64275.016k, Total used: 230676.000k]
% Transforming stm expressions... done.
[User time: +0.000s, 14.690s, Real time: +0.008s, 14.868s, D Stack: 0.285k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 21, Heap used since last GC: 65481.508k, Total used: 230676.000k]
% Fully expanding equivalence types... done.
[User time: +0.230s, 14.920s, Real time: +0.231s, 15.099s, D Stack: 0.285k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 21, Heap used since last GC: 75872.789k, Total used: 230676.000k]
% Generating type_ctor_info structures... done.
[User time: +0.000s, 14.920s, Real time: +0.000s, 15.099s, D Stack: 0.285k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 21, Heap used since last GC: 75874.820k, Total used: 230676.000k]
% Specializing higher-order and polymorphic predicates...
% done.
[User time: +0.000s, 14.920s, Real time: +0.006s, 15.105s, D Stack: 0.293k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 21, Heap used since last GC: 76445.758k, Total used: 230676.000k]
% Inlining...
% done.
[User time: +0.010s, 14.930s, Real time: +0.006s, 15.111s, D Stack: 0.297k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 21, Heap used since last GC: 76671.422k, Total used: 230676.000k]
% Eliminating dead procedures...
% done.
[User time: +0.000s, 14.930s, Real time: +0.001s, 15.112s, D Stack: 0.285k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 21, Heap used since last GC: 76679.227k, Total used: 230676.000k]
% Updating interface:
% training_cars_full.mh' has not changed.
% Mapping args to regs... done.
[User time: +0.000s, 14.930s, Real time: +0.005s, 15.117s, D Stack: 0.281k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 21, Heap used since last GC: 77157.211k, Total used: 230676.000k]
% Migrating branch code... done.
[User time: +0.010s, 14.940s, Real time: +0.002s, 15.119s, D Stack: 0.289k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 21, Heap used since last GC: 77318.570k, Total used: 230676.000k]
% Simplifying goals...
% done.
[User time: +0.050s, 14.990s, Real time: +0.057s, 15.176s, D Stack: 0.312k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 21, Heap used since last GC: 82341.695k, Total used: 247060.000k]
% Computing liveness...
% done.
[User time: +1.630s, 16.620s, Real time: +1.651s, 16.827s, D Stack: 0.297k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 22, Heap used since last GC: 82009.141k, Total used: 263444.000k]
% Computing stack vars... done.
[User time: +0.000s, 16.620s, Real time: +0.004s, 16.831s, D Stack: 0.289k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 22, Heap used since last GC: 82227.984k, Total used: 263444.000k]
% Allocating store map... done.
[User time: +0.010s, 16.630s, Real time: +0.006s, 16.837s, D Stack: 0.289k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 22, Heap used since last GC: 82774.227k, Total used: 263444.000k]
% Generating code...
% done.
[User time: +14.060s, 30.690s, Real time: +14.101s, 30.938s, D Stack: 0.293k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 27, Heap used since last GC: 9554.820k, Total used: 296656.000k]
% Generating call continuation information... done.
[User time: +0.000s, 30.690s, Real time: +0.000s, 30.938s, D Stack: 0.297k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 27, Heap used since last GC: 9554.820k, Total used: 296656.000k]
% Doing optimizations...
% done.
[User time: +0.370s, 31.060s, Real time: +0.369s, 31.307s, D Stack: 0.293k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 27, Heap used since last GC: 27893.141k, Total used: 296656.000k]
% Writing output to `training_cars_full.c'... done.
[User time: +0.380s, 31.440s, Real time: +0.381s, 31.688s, D Stack: 0.312k, ND Stack: 0.039k, C Stack: 10.302k,
#GCs: 27, Heap used since last GC: 35465.609k, Total used: 296656.000k]
% Updating interface:
% training_cars_full.mh' has not changed.
% Touching `training_cars_full.c_date'...  done.