Proposal: return value types in To*Node() to reduce allocations

[pwaller]

For sake of exposition I'm going to write in terms of the LLVM parser we're working on in llir/ll:

• factory.go
• ast.go

Please consider the ToLlvmNode function:

func ToLlvmNode(n *Node) LlvmNode {
	switch n.Type() {
	case ll.AShrExpr:
		return &AShrExpr{n}
	case ll.AShrInst:
		return &AShrInst{n}
	case ll.AddExpr:
[... many more elided ...]

At the moment, for parsing a large input with LLVM, this is one of the larger sources of allocations. (>30% of allocations from the parser) - see llir/llvm#55 for code to reproduce the measurement for yourself.

I note that the allocation can be completely eliminated by instead returning values of the node types (e.g, return AShrExpr{n}). This seems like a reasonable thing to do because all the node types do is embed a pointer to a node, and the value of the pointer doesn't ever need to be modified later, so it is fine to pass the pointer around by value. Because the node types structs only contain this pointer, they actually fit into the second value of the interface data, and therefore the returned value doesn't require an allocation either.

I did a brief experiment on the LLVM codebase a while back and observed about a 10% wall clock speedup and a significant reduction in allocations - giving (IIRC) a significant reduction in CPU and GC cost. The number of modifications I had to make to the LLIR parser was minimal.

I've run out of time for this moment. I intend to supply more (and more specific) details later, and perhaps a patch, if I get a spare moment. But for now I want to put this proposal out there and see what the response is.

For what it's worth I have some other tricks up my sleeve to reduce allocations, though they may be a bit too much of micro-optimization for some tastes. I'd be interested if you'd like to hear of these, but for now let's just consider this one which seems like the lowest hanging fruit.

[inspirer]

Because the node types structs only contain this pointer, they actually fit into the second value of the interface data, and therefore the returned value doesn't require an allocation either.

I'll try this out. The last time I checked, Go wanted the second value of the interface object to be a pointer to simplify garbage collection code. They stopped embedding small objects in interface objects around Go 1.5 (if I remember correctly), together with introducing proper data and stack maps. When you cast a value object to an interface, it gets copied to the heap, so allocating in advance is almost always better.

Sorry for the delayed response, I'll follow up on this soon.

[inspirer]

For what it's worth I have some other tricks up my sleeve to reduce allocations, though they may be a bit too much of micro-optimization for some tastes. I'd be interested if you'd like to hear of these, but for now let's just consider this one which seems like the lowest hanging fruit.

Ow, yeah. I like this topic. I think, allocation-wise we are quite good - the parser itself does not allocate (the listener does), except in tricky lookahead/backtracking situations. Lexers are tuned for branch prediction almost to the limits (of Go, of course). Boundary check elimination is not great in the current compiler, and we will probably see ~50% speed-up with the llvm backend. I have several pending commits improving the parsing tables layout (for better memory locality) and in one of them I get 2x speed-up in exchange for 10MB memory at runtime. If I had a way to convince Go that I don't need its boundary checks, I would be able to get to 30-80% performance increase without extra ram (right now I'm at 20% without extra ram).

[pwaller]

Update from my side. The project I was working on which used this got nix'd, so I ran out of steam for it for now.

The last time I checked, Go wanted the second value of the interface object to be a pointer to simplify garbage collection code.

I did just learn more about this: golang/go#5448 (comment)

However, since the embedded value is only a single-element struct which contains a pointer, putting that struct directly into the ifacedata doesn't violate the rule 'ifacedata must only contain pointers'. So maybe storing the node pointer directly in the iface data can still happen in this circumstance?

[pwaller]

Here is proof about my comment of it fitting in the interface data, btw: https://play.golang.org/p/aS5Ha7OxrUN