runtime: copy and expand stacks instead of splitting them #4910
Description
Seemingly innocuous changes in recursive functions increased or decreased benchmark time dramatically. Sometimes, benchmark time would increase 20%-100%, when we changed the order of initialization of variables or declared a temporary variable explicitly. Further analysis showed that this was a side-effect of the segmented stacks splitting. During discussion, Russ mentioned that there was some work that could be done to try to alleviate this. Filing this issue to track it. ========== Russ message from Google Groups discussion ========== I think there could be some work done on choosing how big a stack to allocate, which would perhaps relieve some of the inner stack split checks. There was some work at Berkeley a few years ago [1] that looked at doing analysis of the program's call graph to remove some stack split checks and to choose stack sizes, and I've been meaning to look into whether we can do something smart like that in Go's split stacks. But ultimately if you end up triggering a stack split in a tight loop you're not going to run as fast as if you don't. Tail call optimization is not mandated by the spec, is not possible in functions with defer, and makes debugging harder. I'm glad that we don't have that in the 6g compiler. I've thought about runtime heuristics for stack sizes, but we don't have enough information at stack split time to move the stack, so by the time you realize 'it would be nice if the current frame were bigger' it's too late. Russ [1] http://capriccio.cs.berkeley.edu/pubs/capriccio-sosp-2003.pdf ========== More Context is at: https://groups.google.com/d/msg/golang-dev/6Vs1sxmSSb0/CtgsMHzAgZwJ https://groups.google.com/d/msg/golang-dev/vxRuA-gbwdw/xiaDzM586VMJ