Open tedinski opened 6 years ago
Some data on generated files:
cd generated/bin
SAMPLE=$(find -name "*.class" | shuf -n 1000)
javap -c $SAMPLE | grep -o -P "(?<=implements |[^\?] extends )[^\{ <>]+" | sort | uniq -c | sort -n
18 common.PatternLazy
19 common.Terminal
23 common.Node
33 common.FunctionNode
99 common.NodeFactory
302 common.Lazy
450 common.Thunk$Evaluable
So a random sample suggest 45% thunks, 30% lazys. That's more lazys than I expected, so putting common cases in the runtime is possibly a better plan than I anticipated.
That 10% are NodeFactory
was surprising to me, but after some napkin math, it seems right. There's one for every production and function. This is a potential candidate for using Java 8 Lambdas, actually... Unlike the nested thunk situation, we're unlikely to make javac
crash unable to deal with the nesting. These are always top-level. WELP, except that I went looking and now we have getType
on them in addition to invoke
, so they're not eligible. Oh well.
Some more data. First: a java heap profile:
java -Xss8M -Xmx3000M -Xrunhprof:heap=sites,depth=2 -jar ../jars/silver.composed.Default.jar --clean silver:composed:Default
Top 50:
SITES BEGIN (ordered by live bytes) Fri Dec 14 23:04:29 2018
percent live alloc'ed stack class
rank self accum bytes objs bytes objs trace name
1 13.81% 13.81% 189687720 2985093 549203608 8263711 317189 java.lang.Object[]
2 10.44% 24.25% 143434080 2988210 397011888 8271081 317187 common.DecoratedNode
3 9.57% 33.82% 131414784 2737808 848969712 17686869 316605 common.DecoratedNode
4 5.42% 39.24% 74475472 2804573 205202808 7723797 317188 java.lang.Object[]
5 4.95% 44.19% 68060816 2737808 443454016 17686869 316606 java.lang.Object[]
6 2.96% 47.15% 40712456 269429 46784240 318827 300193 char[]
7 2.82% 49.98% 38757664 1154855 100658072 3284503 317238 java.lang.Object[]
8 2.30% 52.28% 31607472 1316978 180117000 7504875 316604 silver.util.Pcontains
9 2.11% 54.39% 29027640 1209485 66991176 2791299 317145 common.AppendCell
10 1.71% 56.10% 23521128 980047 57372648 2390527 317140 common.ConsCell
11 1.35% 57.45% 18532272 1158267 110647792 6915487 318297 silver.util.Pcontains$1
12 1.35% 58.80% 18532272 1158267 110647792 6915487 318298 common.Thunk
13 1.04% 59.84% 14289720 357243 14289720 357243 317092 java.util.TreeMap$Entry
14 1.03% 60.87% 14169528 590397 157010928 6542122 318836 java.lang.Object[]
15 0.88% 61.75% 12061480 470998 26464904 1071136 317529 java.lang.Object[]
16 0.86% 62.61% 11849320 296233 15173600 379340 318112 core.Ploc
17 0.77% 63.38% 10536528 439022 10536528 439022 321211 silver.definition.flow.ast.PconsFlow
18 0.72% 64.10% 9866280 411095 9866280 411095 318834 common.ConsCell
19 0.69% 64.78% 9413600 574 23222400 1416 324900 char[]
20 0.62% 65.40% 8477200 529825 12109424 756839 300005 java.lang.Integer
21 0.60% 66.00% 8283232 150894 19025416 264383 300012 char[]
22 0.53% 66.54% 7333392 305558 53573280 2232220 317185 common.AppendCell$$Lambda$5.389464548
23 0.49% 67.03% 6726240 121066 12029752 161986 317344 java.lang.Object[]
24 0.47% 67.50% 6466296 269429 7651848 318827 300194 java.lang.String
25 0.47% 67.96% 6417912 55480 21748768 170932 300010 char[]
26 0.45% 68.42% 6213528 258897 59545488 2481062 317580 common.DecoratedNode$$Lambda$10.818609427
27 0.42% 68.84% 5811168 121066 7775328 161986 317342 common.DecoratedNode
28 0.40% 69.24% 5523480 120295 6554104 153473 318540 java.lang.Object[]
29 0.39% 69.63% 5344512 222688 12045624 501901 316604 core.monad.PbindEither
30 0.39% 70.02% 5340624 222526 12041736 501739 324983 core.monad.PbindEither$1$3
31 0.39% 70.41% 5340600 222525 12041712 501738 324985 core.monad.PbindEither$1$4
32 0.39% 70.80% 5340600 222525 12041712 501738 324989 java.lang.Object[]
33 0.39% 71.18% 5330400 222100 5330400 222100 325037 common.StringCatter
34 0.39% 71.57% 5315472 221478 10621248 442552 317184 core.Ppair
35 0.37% 71.94% 5075056 177365 7569104 261458 300055 char[]
36 0.36% 72.30% 4888928 305558 35715520 2232220 317186 common.Thunk
37 0.35% 72.65% 4863856 303991 39696992 2481062 317581 common.Thunk
38 0.35% 73.00% 4784040 199335 40579872 1690828 316604 core.Pmap
39 0.35% 73.35% 4753848 198077 5261712 219238 321123 common.StringCatter
40 0.35% 73.69% 4743456 98822 13571328 282736 300009 char[]
41 0.34% 74.03% 4711392 574 11622528 1416 324898 byte[]
42 0.31% 74.34% 4256760 177365 6273768 261407 318106 java.lang.String
43 0.31% 74.65% 4256760 177365 6251328 260472 318110 common.StringCatter
44 0.31% 74.96% 4256760 177365 6251328 260472 318111 common.StringCatter
45 0.27% 75.24% 3739392 155808 86947080 3622795 317453 common.DecoratedNode$$Lambda$8.176320504
46 0.27% 75.50% 3660728 150725 22912536 948092 316613 java.lang.Object[]
47 0.26% 75.77% 3617872 226117 15922288 995143 317149 common.Thunk
48 0.26% 76.03% 3614176 225886 57964720 3622795 317454 common.Thunk
49 0.26% 76.29% 3563008 222688 8030416 501901 324979 core.monad.PbindEither$1
50 0.26% 76.55% 3560560 222535 8029568 501848 317359 core.Pright
Here are some thoughts on the above:
char[]
should be so prevalent. silver:util:contains
has 7.5M calls. Granted, it's recursive, but that's a LOT, especially since Silver calls are allocation heavy. map
is up at 1.7M. foldr
is 1.5M. flatMap
300K. implode
200K. lookupBy
380K. These may all be good candidates for special-casing?goodSubst
is allocated 200K times. searchEnvTree
has 700K. performSubstitution
250K. tyVarEqual
350K. bindEither
is there, much less called 500K times. I thought this stuff wasn't used in the Silver compiler.skipNulls
which is some weird thing in the driver. That's probably evidence that bit of code is quite suboptimal.Not sure about most of the other stuff, but bindEither
is used in the reflection library to allow monadic error handling during serialization. Since reflection is now used by Silver for interface files, this I suppose would end up being called quite a lot during interface file generation.
This time, a crummy CPU profile. Please note that these numbers are essentially "time spent with this function at top of stack" so if a function takes a long time, but because it calls other functions, then it could easily not be listed. So this is places where the instruction pointer was "caught" inside that function, not having called others.
java -Xss8M -Xmx3000M -Xrunhprof:cpu=samples,depth=1,interval=1 -jar ../jars/silver.composed.Default.jar --clean silver:composed:Default
CPU SAMPLES BEGIN (total = 9715) Fri Dec 14 21:14:09 2018
rank self accum count trace method
1 9.03% 9.03% 877 300755 common.DecoratedNode.childAsIsLazy
2 8.11% 17.14% 788 300102 java.lang.ClassLoader.defineClass1
3 4.24% 21.38% 412 300942 common.DecoratedNode.evalSyn
4 2.90% 24.28% 282 300994 common.Thunk.eval
5 2.48% 26.76% 241 300693 common.DecoratedNode.childAsIs
6 1.56% 28.33% 152 300122 java.util.zip.Inflater.inflateBytes
7 1.45% 29.78% 141 300941 common.DecoratedNode.createDecoratedChild
8 1.39% 31.17% 135 301125 common.AppendCell.append
9 1.34% 32.51% 130 300143 java.lang.Throwable.fillInStackTrace
10 1.28% 33.78% 124 300679 java.io.FileOutputStream.writeBytes
11 1.12% 34.90% 109 300982 silver.util.Pcontains.invoke
12 1.01% 35.91% 98 301061 common.Node.decorate
13 1.00% 36.91% 97 300149 java.util.zip.ZipFile.getEntry
14 0.93% 37.84% 90 300664 edu.umn.cs.melt.copper.runtime.engines.single.SingleDFAEngine.runEngine
15 0.82% 38.66% 80 300954 core.Pnull.invoke
16 0.78% 39.44% 76 301431 common.DecoratedNode.evalSyn
17 0.74% 40.19% 72 300717 edu.umn.cs.melt.copper.runtime.engines.single.SingleDFAEngine.simpleScan
18 0.71% 40.90% 69 300916 common.DecoratedNode.evalLocalAsIs
19 0.67% 41.56% 65 301192 java.util.TreeMap.getEntryUsingComparator
20 0.64% 42.20% 62 300929 common.AppendCell.head
21 0.63% 42.83% 61 302857 sun.nio.cs.UTF_8$Encoder.encodeLoop
22 0.62% 43.45% 60 301388 common.DecoratedNode.createDecoratedChild
23 0.60% 44.05% 58 300115 java.lang.Object.<init>
24 0.58% 44.62% 56 300938 common.Thunk.transformUndecorate
25 0.57% 45.19% 55 300109 java.lang.ClassLoader.findBootstrapClass
26 0.55% 45.73% 53 300921 common.FunctionNode.decorate
27 0.51% 46.25% 50 300113 java.util.zip.ZipFile.read
28 0.51% 46.76% 50 301046 common.DecoratedNode.lambda$childDecoratedSynthesizedLazy$3
29 0.49% 47.26% 48 301075 common.Node.decorate
30 0.45% 47.71% 44 301235 core.PcompareString.invoke
31 0.43% 48.14% 42 301238 core.PcompareString.invoke
32 0.42% 48.56% 41 300162 java.lang.ClassLoader.loadClass
33 0.42% 48.99% 41 301191 java.util.TreeMap.put
34 0.42% 49.41% 41 302879 java.io.FileOutputStream.open0
35 0.38% 49.79% 37 300774 common.Util.demand
36 0.37% 50.16% 36 300384 java.lang.Object.clone
37 0.37% 50.53% 36 301186 common.Node.decorate
38 0.34% 50.87% 33 300053 java.security.AccessController.doPrivileged
39 0.30% 51.17% 29 300382 java.lang.Class.getField
40 0.28% 51.45% 27 300142 java.lang.ClassLoader.loadClass
41 0.28% 51.72% 27 300144 java.net.URLClassLoader.findClass
42 0.27% 51.99% 26 301651 common.DecoratedNode.inheritedForwarded
43 0.27% 52.26% 26 302822 java.io.UnixFileSystem.delete0
44 0.26% 52.52% 25 301600 common.DecoratedNode.childAsIsSynthesizedLazy
45 0.25% 52.76% 24 300230 java.lang.ClassLoader.findLoadedClass0
46 0.25% 53.01% 24 301340 common.Node.decorate
47 0.23% 53.24% 22 301220 silver.definition.env.PfreshenNamedSignature$1.eval
48 0.17% 53.41% 17 303048 core.monad.PbindEither.invoke
49 0.16% 53.58% 16 301271 common.Node.decorate
50 0.16% 53.74% 16 301346 common.DecoratedNode.lambda$childDecoratedLazy$0
Thoughts:
fillInStackTrace
is showing up there. That seems to suggest we spend a lot of time throwing and catching exceptions? That shouldn't be happening?FileOutputStream.writeByets
is a phantom: probably that blocks while writing, and so garnered more CPU profile samples than it really deserved.null
shows up a lot, so you might think "lol null is slow," but that's because it gets called uniquely a lot, and... it amounts to 0.8% of runtime, so, not really an optimization opportunity, there.Ok. A much more useful kind of CPU profile. CPU profiles run fast, while heap are slow, but the aggregate data we get isn't helpful at the end. But the profiling SITES... with deep stack traces, when we're trying to track things down:
java -Xss8M -Xmx3000M -Xrunhprof:cpu=samples,depth=12 -jar ../jars/silver.composed.Default.jar --clean silver:composed:Default
Get us some interesting information about when certain things are getting called:
TRACE 301014:
java.lang.Throwable.fillInStackTrace(Throwable.java:Unknown line)
java.lang.Throwable.fillInStackTrace(Throwable.java:783)
java.lang.Throwable.<init>(Throwable.java:265)
java.lang.Exception.<init>(Exception.java:66)
java.lang.RuntimeException.<init>(RuntimeException.java:62)
common.exceptions.SilverException.<init>(SilverException.java:29)
common.exceptions.SilverError.<init>(SilverError.java:12)
common.Reflection.reify(Reflection.java:254)
common.Reflection.reifyChecked(Reflection.java:122)
silver.extension.silverconstruction.Init$16$1$2$1.invoke(Init.java:265)
silver.extension.silverconstruction.Init$16$1$2.eval(Init.java:273)
silver.extension.silverconstruction.Init$16$1.eval(Init.java:273)
TRACE 300211:
java.lang.Throwable.fillInStackTrace(Throwable.java:Unknown line)
java.lang.Throwable.fillInStackTrace(Throwable.java:783)
java.lang.Throwable.<init>(Throwable.java:265)
java.lang.Exception.<init>(Exception.java:66)
java.lang.ReflectiveOperationException.<init>(ReflectiveOperationException.java:56)
java.lang.NoSuchFieldException.<init>(NoSuchFieldException.java:50)
java.lang.Class.getField(Class.java:1703)
common.Decorator.decorateAutoCopy(Decorator.java:60)
silver.definition.env.DcompiledGrammars.decorate(DcompiledGrammars.java:10)
common.Decorator.applyDecorators(Decorator.java:22)
silver.modification.collection.Init.postInit(Init.java:87)
silver.analysis.warnings.flow.Init.postInit(Init.java:77)
TRACE 300575:
java.lang.Throwable.fillInStackTrace(Throwable.java:Unknown line)
java.lang.Throwable.fillInStackTrace(Throwable.java:783)
java.lang.Throwable.<init>(Throwable.java:287)
java.lang.Exception.<init>(Exception.java:84)
java.lang.ReflectiveOperationException.<init>(ReflectiveOperationException.java:75)
java.lang.ClassNotFoundException.<init>(ClassNotFoundException.java:82)
java.net.URLClassLoader.findClass(URLClassLoader.java:382)
java.lang.ClassLoader.loadClass(ClassLoader.java:424)
java.lang.ClassLoader.loadClass(ClassLoader.java:411)
sun.misc.Launcher$AppClassLoader.loadClass(Launcher.java:349)
java.lang.ClassLoader.loadClass(ClassLoader.java:357)
silver.definition.env.PtoEnv$1.eval(PtoEnv.java:92) (A WHOLE BUNCH WHERE THIS LAST LINE VARIES)
So that's three sources:
if (!TypeRep.unify(resultType, givenType)) { throw new SilverError("reify is constructing " + resultType.toString() + ", but found " + givenType.toString() + " AST."); }
Actually, this is a clean run of the silver compiler. Shouldn't we be reifying nothing at all?Also I've tracked down the HeapCharBuffer problem to an obvious bug caused (presumably) by misleading documentation. Pursuing this one immediately...
Interesting, I'll take a look at what's going on with reification.
OK, I remember what is going on here. There is also the silver construction extension that I added, that is basically the same as silver-ableC but for Silver itself, for use by other Silver extensions. I think it's only used in a couple of places, at the moment. Part of the translation involves being able to extract the location at any point in an AST
. In ableC there are a few productions on nonterminals lacking a location annotation that have Location
as the rightmost child, so I made this into a general check that works by attempting to reify the last child and failing if it isn't actually a Location
. This got copied as part of the silver construction extension, but seeing as there aren't any such productions in Silver's abstract syntax, this check can be removed.
There's a bunch of different categories of things that could use improvement. This is just a thought-collection list.
Startup time
I'm retiring issue #30 and reformatting those ideas here:
debuggingInit
function, and move this static list initialization step until later, when it's needed. (Major culprit: names of attributes.) (Alternative possibility: In future JVMs, class files may gain the ability to store "lists of strings" as constants. So if we just do nothing long enough...) (This fix already is done for terminal lexer classes. This is initialized to null, and then an accessor can fill it in later, in the unlikely event it's needed. Perhaps we could do the same for things on productions, functions, and nonterminals.)Silver in general
Issue #206 tracks some thoughts on memory usage. That issue should possibly be folded into this one.
Interface files
Compilation process
MWDA
Type checking
Generated files
DecoratedNode.java
), but we should profile thunk generation more to find additional candidates for moving into the runtime.Lazy
s too. Here are some examples from real code:We copy inherited attributes down (manually) a lot:
Or the synthesized version, too:
So this would be a simple Lazy to create an abstract version of in the standard library. Then this line could become:
And spare us one more generated class file.