[MLton-devel] allocation performance improvements

[Stephen Weeks]

After some more work, I've gotten the total allocation of a self
compile down to about 25G, which is about where it used to be at the
last release.  So I'm happy enough with it.

In looking at the profiling, the current hottest allocation spot is
x86-allocate-registers.fun, which is responsible for about 25% of
allocation during a self compile.  I glanced through it, and it seems
to me that one way to get a big win, maybe almost a factor of half, is
to replace various list operations that are doing an extra reversal
with the version that doesn't.  More specifically, the following
replacements:

		List.keepAll -> List.revKeepAll
		List.keepAllMap -> List.revKeepAllMap
		List.map -> List.revMap
		List.removeAll -> List.revRemoveAll

Of course, this are only valid if list order doesn't matter.  It seems
like it often doesn't to me, but I'd rather get the advice of an
expert :-).  Matthew, could you take a look through
x86-allocate-registers.fun and do those replacements when possible?
I'm hoping for a 10% or so decrease in total self-compile allocation.

Here is a graph showing the relevant hotspots, produced with -graph
'(and "x86-allocate-registers.fun" (thresh-stack 1))'

digraph "call-stack graph" {
label = "call-stack graph"
n0 [shape = "box", label = "codegen/x86-codegen/x86-allocate-registers.fun: 636\n0.3% 4.5% 0.0%\n"]
n0 -> n1 []
n1 [shape = "box", label = "livenessAssembly\ncodegen/x86-codegen/x86-allocate-registers.fun: 553\n0.5% 4.2% 0.0%\n"]
n1 -> n2 []
n2 [shape = "box", label = "livenessInstruction\ncodegen/x86-codegen/x86-allocate-registers.fun: 430\n0.0% 1.8% 0.0%\n"]
n2 -> n3 []
n3 [shape = "box", label = "liveness\ncodegen/x86-codegen/x86-allocate-registers.fun: 369\n0.0% 1.5% 0.0%\n"]
n4 [shape = "box", label = "codegen/x86-codegen/x86-allocate-registers.fun: 583\n0.9% 1.3% 0.0%\n"]
n5 [shape = "box", label = "codegen/x86-codegen/x86-allocate-registers.fun: 3960\n1.0% 1.2% 0.0%\n"]
n6 [shape = "box", label = "chooseRegister\ncodegen/x86-codegen/x86-allocate-registers.fun: 1308\n0.0% 2.6% 0.0%\n"]
n7 [shape = "box", label = "toAddressMemLoc\ncodegen/x86-codegen/x86-allocate-registers.fun: 3522\n0.2% 1.2% 0.0%\n"]
n7 -> n8 []
n9 [shape = "box", label = "commitRegisters\ncodegen/x86-codegen/x86-allocate-registers.fun: 1871\n0.0% 1.0% 0.0%\n"]
n10 [shape = "box", label = "valueMap\ncodegen/x86-codegen/x86-allocate-registers.fun: 892\n0.0% 4.3% 0.0%\n"]
n11 [shape = "box", label = "toRegisterMemLoc'\ncodegen/x86-codegen/x86-allocate-registers.fun: 4449\n0.0% 2.8% 0.0%\n"]
n11 -> n8 []
n12 [shape = "box", label = "pre\ncodegen/x86-codegen/x86-allocate-registers.fun: 3830\n0.7% 3.2% 0.0%\n"]
n12 -> n9 []
n12 -> n10 []
n13 [shape = "box", label = "freeRegister\ncodegen/x86-codegen/x86-allocate-registers.fun: 1565\n0.1% 2.8% 0.0%\n"]
n13 -> n9 []
n13 -> n6 []
n13 -> n10 []
n14 [shape = "box", label = "allocateSrcDst\ncodegen/x86-codegen/x86-allocate-registers.fun: 6232\n0.1% 3.2% 0.0%\n"]
n14 -> n11 []
n15 [shape = "box", label = "codegen/x86-codegen/x86-allocate-registers.fun: 5206\n0.0% 3.6% 0.0%\n"]
n15 -> n16 []
n16 [shape = "box", label = "computeEdges'\ncodegen/x86-codegen/x86-allocate-registers.fun: 5166\n0.0% 3.6% 0.0%\n"]
n17 [shape = "box", label = "cache\ncodegen/x86-codegen/x86-allocate-registers.fun: 5153\n0.0% 4.9% 0.0%\n"]
n17 -> n18 []
n17 -> n19 []
n18 [shape = "box", label = "computeEdges\ncodegen/x86-codegen/x86-allocate-registers.fun: 5203\n0.0% 3.8% 0.0%\n"]
n8 [shape = "box", label = "toRegisterMemLoc\ncodegen/x86-codegen/x86-allocate-registers.fun: 2767\n0.5% 4.1% 0.0%\n"]
n8 -> n7 []
n8 -> n8 []
n8 -> n13 []
n8 -> n6 []
n19 [shape = "box", label = "doitHard\ncodegen/x86-codegen/x86-allocate-registers.fun: 5307\n0.0% 1.2% 0.0%\n"]
n19 -> n18 []
n19 -> n8 []
n20 [shape = "box", label = "post\ncodegen/x86-codegen/x86-allocate-registers.fun: 4050\n0.8% 3.8% 0.0%\n"]
n20 -> n9 []
n20 -> n10 []
n21 [shape = "box", label = "allocateRegisters\ncodegen/x86-codegen/x86-allocate-registers.fun: 10655\n0.0% 6.6% 0.0%\n"]
n21 -> n17 []
n22 [shape = "box", label = "allocateRegisters\ncodegen/x86-codegen/x86-allocate-registers.fun: 6573\n0.2% 6.3% 0.0%\n"]
n22 -> n14 []
n22 -> n11 []
n22 -> n20 []
n22 -> n12 []
n22 -> n13 []
n23 [shape = "box", label = "default\ncodegen/x86-codegen/x86-allocate-registers.fun: 7791\n0.0% 1.7% 0.0%\n"]
n23 -> n14 []
n23 -> n20 []
n24 [shape = "box", label = "default''\ncodegen/x86-codegen/x86-allocate-registers.fun: 7898\n0.1% 3.9% 0.0%\n"]
n24 -> n14 []
n24 -> n20 []
n25 [shape = "box", label = "codegen/x86-codegen/x86-allocate-registers.fun: 10755\n0.6% 19.4% 0.0%\n"]
n25 -> n20 []
n25 -> n21 []
n25 -> n22 []
n25 -> n23 []
n25 -> n24 []
n26 [shape = "box", label = "allocateRegisters\ncodegen/x86-codegen/x86-allocate-registers.fun: 10884\n0.0% 24.3% 0.0%\n"]
n27 [shape = "box", label = "allocateRegisters\ncodegen/x86-codegen/x86-allocate-registers.fun: 10747\n0.0% 19.6% 0.0%\n"]
n28 [shape = "box", label = "toLiveness\ncodegen/x86-codegen/x86-allocate-registers.fun: 630\n0.0% 4.7% 0.0%\n"]
n29 [shape = "box", label = "codegen/x86-codegen/x86-allocate-registers.fun: 10903\n0.0% 24.3% 0.0%\n"]
n29 -> n27 []
n29 -> n28 []
}





-------------------------------------------------------
This SF.NET email is sponsored by:
SourceForge Enterprise Edition + IBM + LinuxWorld = Something 2 See!
http://www.vasoftware.com
_______________________________________________
MLton-devel mailing list
MLton-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mlton-devel