A few numbers on allocation in dmd

Tue Jun 30 01:18:48 UTC 2020

I got a few numbers on what types dmd allocates the most while compiling 
a large project. The project is decently large (takes minutes to build) 
and uses a lot of compile-time stuff, but I'd think that'd be not 
atypical for a D program because people who wouldn't need that kind of 
stuff wouldn't derive much advantage from using D in the first place. So 
it seems a representative corpus.

The "-profile=gc" and "-lowmem" flags should help with all that, and 
they do work (thanks to all who hopped on 
https://issues.dlang.org/show_bug.cgi?id=20960 and helped). However, the 
inclusion of that profiling makes the compiler unbearably slow even for 
moderately-sized programs, so I resorted to a low-tech solution by means 
of inserting:

printf("%s\n", ci.info.name.ptr);

at 
https://github.com/dlang/dmd/blob/b6b0c0f41a476c4eaa88ba106fb4de1175d40440/src/dmd/root/rmem.d#L240 
(thanks @kinke for pointing me there).

That produces a hecatomb of output - we're talking tens of gigs for a 
large project. There are a lot of duplicates because there aren't that 
many distinct types, so the normal solution would be the classic:

dub build | sort | uniq -c | sort -nr >sorted.log

Problem being, of course, the temporary files would be huge and the 
extra time spent would be just crazy. A hashtable turned out to fix that 
problem:

dub build | awk '{ a[$0]++ }END{ for(i in a) print a[i],i }' \
     | sort -nr >sorted.log

(did I mention low-tech?) So at the end of all this I got the attached 
file containing the most allocated types by dmd while compiling. (It's 
number of allocations i.e. calls to new, not size allocated; collecting 
total bytes allocated would bring additional, but different, information).

Looking at the top offenders:

42634177 dmd.mtype.TypeIdentifier
20452075 dmd.dtemplate.TemplateInstance
20202329 dmd.dsymbol.DsymbolTable
18783004 dmd.declaration.AliasDeclaration
18224199 dmd.dsymbol.ScopeDsymbol
18172133 dmd.mtype.Parameter
14124126 dmd.expression.IntegerExp

The drop-off is fast, as expected, more than 2x from #1 to #2, and 3x 
from #1 to #7. That means any work that improves on TypeIdentifier is 
likely to greatly relieve the number of allocation calls. Here are a few 
thoughts on possible improvements:

* Any work that reduces the number of TypeIdentifier, TemplateInstance, 
etc. objects in the first place would help quite a bit.

* An object pooling approach may be helpful: have a pool broker all 
allocations of TypeIdentifier objects. If/when a TypeIdentifier object 
is no longer used, return it to the pool instead of deallocating. Next 
allocation request will retrieve it from the pool. That way the code is 
still safe even if by mistake the freed object continues to be used. 
(Bugs can be diagnosed by disabling pool allocation and testing again.)

* Interning: if many TypeIdentifier objects have the same content, it 
may be worthwhile tracking that and have the same reference shared from 
many places. Things like immutable and const can be of great help here.

* Layout: any improvement in the layout of TypeIdentifier (e.g. make it 
smaller and a multiple of cache line size) is likely to have large 
impact on fragmentation.

I'll look into also adding information on bytes allocated tomorrow.
-------------- next part --------------
42634177 dmd.mtype.TypeIdentifier
20452075 dmd.dtemplate.TemplateInstance
20202329 dmd.dsymbol.DsymbolTable
18783004 dmd.declaration.AliasDeclaration
18224199 dmd.dsymbol.ScopeDsymbol
18172133 dmd.mtype.Parameter
14124126 dmd.expression.IntegerExp
12155614 dmd.declaration.VarDeclaration
11041096 dmd.init.ExpInitializer
10731712 dmd.expression.VarExp
10376618 dmd.mtype.TypeInstance
8710508 dmd.expression.CastExp
8030163 dmd.expression.IsExp
7317859 dmd.expression.IdentifierExp
7096748 dmd.statement.CompoundStatement
6872527 dmd.expression.ScopeExp
6337308 dmd.mtype.TypeFunction
6004625 dmd.statement.ExpStatement
5912372 dmd.expression.CallExp
5104351 dmd.cond.StaticIfCondition
4019748 dmd.mtype.TypeTuple
3934639 dmd.func.FuncDeclaration
3876473 dmd.declaration.TupleDeclaration
3788939 dmd.mtype.TypeDArray
3779498 dmd.expression.ArrayExp
3729316 dmd.mtype.TypeSArray
3624396 dmd.mtype.TypeTypeof
3594043 dmd.attrib.StaticIfDeclaration
3322438 dmd.expression.DsymbolExp
3137354 dmd.expression.DotVarExp
3102907 dmd.identifier.Identifier
2939027 dmd.expression.DeclarationExp
2855791 dmd.expression.DotIdExp
2852440 dmd.dsymbol.ArrayScopeSymbol
2559709 dmd.statement.ReturnStatement
2438334 dmd.expression.TypeExp
2294086 dmd.expression.TupleExp
2238180 dmd.dtemplate.Tuple
1952465 dmd.mtype.TypePointer
1599249 dmd.statement.ConditionalStatement
1586703 dmd.expression.StringExp
1507598 dmd.statement.ScopeStatement
1456410 dmd.expression.TraitsExp
1388762 dmd.expression.FuncExp
1328129 dmd.dtemplate.TemplateTypeParameter
1299869 dmd.dtemplate.TypeDeduced
1247403 dmd.expression.TemplateExp
1220725 dmd.statement.IfStatement
1171558 dmd.mtype.TypeSlice
1108926 dmd.expression.IndexExp
1084963 dmd.dimport.Import
825535 dmd.expression.StructLiteralExp
814159 dmd.func.FuncLiteralDeclaration
800679 dmd.expression.ErrorExp
727592 dmd.staticassert.StaticAssert
716345 dmd.expression.NullExp
692472 dmd.dmodule.Module
670764 dmd.dtemplate.TemplateDeclaration
651442 dmd.expression.ConstructExp
621880 dmd.expression.EqualExp
567317 dmd.expression.ThisExp
556228 dmd.statement.ImportStatement
532429 dmd.expression.AssignExp
507409 dmd.attrib.StorageClassDeclaration
503981 dmd.expression.LogicalExp
461852 dmd.expression.IntervalExp
442280 dmd.func.UnitTestDeclaration
439241 dmd.expression.ArrayLengthExp
437223 dmd.mtype.TypeAArray
433265 dmd.expression.DotTemplateInstanceExp
390014 dmd.denum.EnumMember
382175 dmd.declaration.ThisDeclaration
346876 dmd.statement.ForwardingStatement
325777 dmd.statement.ForeachStatement
320313 dmd.expression.CmpExp
304314 dmd.dsymbol.ForwardingScopeDsymbol
301790 dmd.expression.AddExp
278624 dmd.mtype.TypeDelegate
277010 dmd.expression.AssertExp
265276 dmd.expression.PtrExp
247803 dmd.expression.NotExp
243404 dmd.attrib.ProtDeclaration
242997 dmd.dtemplate.TemplateValueParameter
236673 dmd.cond.VersionCondition
233437 dmd.statement.StaticAssertStatement
232824 dmd.statement.CaseStatement
229333 dmd.expression.CommaExp
227679 dmd.expression.ArrayLiteralExp
224379 dmd.attrib.ForwardingAttribDeclaration
217150 dmd.expression.NewExp
208497 dmd.attrib.ConditionalDeclaration
198574 dmd.expression.TypeidExp
193449 dmd.expression.SliceExp
170501 dmd.expression.CondExp
167784 dmd.expression.CatExp
167704 dmd.expression.MinExp
147340 dmd.expression.CompileExp
144547 dmd.init.VoidInitializer
138434 dmd.statement.ThrowStatement
136538 dmd.expression.AddrExp
135148 dmd.statement.BreakStatement
134159 dmd.statement.ForStatement
132482 dmd.mtype.TypeStruct
128999 dmd.cond.StaticForeach
128012 dmd.expression.RealExp
126925 dmd.statement.ForeachRangeStatement
124758 dmd.dstruct.StructDeclaration
120853 dmd.expression.AddAssignExp
116487 dmd.expression.DotTemplateExp
115181 dmd.mtype.TypeTraits
106244 dmd.func.CtorDeclaration
95487 dmd.expression.BlitExp
93526 dmd.expression.MulExp
93184 dmd.dtemplate.TemplateAliasParameter
83330 dmd.expression.NegExp
82175 dmd.statement.AsmStatement
80184 dmd.dtemplate.TemplateTupleParameter
78928 dmd.expression.AndExp
77121 dmd.expression.DollarExp
75005 dmd.statement.ErrorStatement
72855 dmd.statement.StaticForeachStatement
68719 dmd.expression.PreExp
68453 dmd.statement.CompoundDeclarationStatement
68093 dmd.statement.CompileStatement
60684 dmd.init.ArrayInitializer
58765 dmd.attrib.LinkDeclaration
57122 dmd.statement.UnrolledLoopStatement
56144 dmd.attrib.StaticForeachDeclaration
55882 dmd.expression.CatAssignExp
53978 dmd.expression.SymOffExp
49865 dmd.statement.ContinueStatement
49692 dmd.statement.WhileStatement
47191 dmd.expression.IdentityExp
47091 dmd.expression.DivExp
45122 dmd.mtype.TypeEnum
45122 dmd.denum.EnumDeclaration
38361 dmd.mtype.TypeReturn
36749 dmd.statement.SwitchStatement
33938 dmd.expression.PostExp
33449 dmd.dversion.VersionSymbol
31595 dmd.statement.DefaultStatement
27479 dmd.expression.OrExp
26780 dmd.expression.ShlExp
24806 dmd.attrib.CompileDeclaration
23771 dmd.expression.CatElemAssignExp
23400 dmd.expression.ShrExp
21246 dmd.statement.GotoStatement
20485 dmd.statement.LabelStatement
19890 dmd.declaration.SymbolDeclaration
19314 dmd.statement.Catch
19311 dmd.mtype.TypeClass
19060 dmd.expression.MinAssignExp
18900 dmd.statement.TryCatchStatement
17575 dmd.init.ErrorInitializer
17268 dmd.declaration.TypeInfoStructDeclaration
16937 dmd.dclass.ClassDeclaration
16183 dmd.expression.OrAssignExp
15279 dmd.attrib.PragmaDeclaration
14997 dmd.func.FuncAliasDeclaration
14495 dmd.statement.ScopeGuardStatement
14406 dmd.statement.GotoCaseStatement
14164 dmd.expression.ModExp
13856 dmd.statement.WithStatement
13423 dmd.mtype.TypeVector
13087 dmd.statement.PragmaStatement
11354 dmd.cond.DebugCondition
11090 dmd.aliasthis.AliasThis
9260 dmd.expression.LineInitExp
9077 dmd.dtemplate.TemplateMixin
8647 dmd.expression.ComExp
8549 dmd.statement.GotoDefaultStatement
8548 dmd.statement.CompoundAsmStatement
8365 dmd.statement.LabelDsymbol
7779 dmd.expression.FileInitExp
7724 dmd.dstruct.UnionDeclaration
7707 dmd.statement.TryFinallyStatement
7170 dmd.expression.SuperExp
7105 dmd.attrib.UserAttributeDeclaration
6977 dmd.expression.MulAssignExp
6928 dmd.declaration.TypeInfoConstDeclaration
6911 dmd.func.DtorDeclaration
6802 dmd.expression.AndAssignExp
6495 dmd.statement.DtorExpStatement
6432 dmd.statement.DoStatement
5983 dmd.dsymbol.WithScopeSymbol
5926 dmd.func.PostBlitDeclaration
5592 dmd.dtemplate.TemplateThisParameter
5123 dmd.expression.DelegateExp
5087 dmd.declaration.TypeInfoClassDeclaration
4465 dmd.attrib.DeprecatedDeclaration
4378 dmd.expression.XorExp
4363 dmd.attrib.AnonDeclaration
4182 dmd.expression.InExp
3414 dmd.dmodule.Package
3406 dmd.declaration.TypeInfoArrayDeclaration
3235 dmd.statement.PeelStatement
2760 dmd.mtype.TypeBasic
2553 dmd.expression.ShrAssignExp
2534 dmd.statement.SynchronizedStatement
2463 dmd.expression.UshrExp
2374 dmd.dclass.InterfaceDeclaration
2190 dmd.expression.PowExp
2116 dmd.expression.XorAssignExp
1908 dmd.statement.CaseRangeStatement
1836 dmd.expression.DivAssignExp
1642 dmd.expression.ShlAssignExp
1619 dmd.expression.ModAssignExp
1541 dmd.mtype.TypeMixin
1281 dmd.expression.UAddExp
1202 dmd.statement.SwitchErrorStatement
1202 dmd.init.StructInitializer
1167 dmd.dsymbol.OverloadSet
1148 dmd.statement.DebugStatement
1088 dmd.attrib.AlignDeclaration
1030 dmd.declaration.TypeInfoEnumDeclaration
1013 dmd.expression.OverExp
999 dmd.declaration.TypeInfoDeclaration
885 dmd.expression.FuncInitExp
764 dmd.statement.InlineAsmStatement
690 dmd.ctfeexpr.CTFEExp
641 dmd.declaration.TypeInfoPointerDeclaration
611 dmd.expression.UshrAssignExp
608 dmd.expression.PrettyFuncInitExp
483 dmd.expression.ModuleInitExp
444 dmd.func.InvariantDeclaration
380 dmd.declaration.TypeInfoInterfaceDeclaration
365 dmd.func.SharedStaticCtorDeclaration
348 dmd.expression.DotExp
310 dmd.declaration.TypeInfoAssociativeArrayDeclaration
276 dmd.declaration.TypeInfoStaticArrayDeclaration
263 dmd.declaration.TypeInfoInvariantDeclaration
247 dmd.expression.AssocArrayLiteralExp
240 dmd.func.StaticCtorDeclaration
184 dmd.dsymbol.Dsymbol
163 dmd.func.SharedStaticDtorDeclaration
130 dmd.expression.ImportExp
120 dmd.declaration.TypeInfoSharedDeclaration
120 dmd.declaration.OverDeclaration
115 dmd.objc.Unsupported
115 dmd.objc_glue.Unsupported
115 dmd.mtype.TypeNull
115 dmd.mtype.TypeError
113 dmd.libelf.LibElf
108 dmd.nspace.Nspace
82 dmd.expression.CatDcharAssignExp
80 dmd.declaration.TypeInfoWildDeclaration
77 dmd.func.StaticDtorDeclaration
64 dmd.expression.DelegateFuncptrExp
62 dmd.declaration.TypeInfoDelegateDeclaration
59 dmd.dversion.DebugSymbol
55 dmd.declaration.TypeInfoFunctionDeclaration
53 dmd.expression.DelegatePtrExp
51 dmd.expression.RemoveExp
33 dmd.expression.NewAnonClassExp
28 dmd.expression.PowAssignExp
24 dmd.expression.DeleteExp
10 dmd.attrib.CPPNamespaceDeclaration
9 dmd.expression.VectorExp
1 dmd.attrib.CPPMangleDeclaration