Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

cmd/compile: improve inline memrun decision in generated alg eq routines #38494

Open
josharian opened this issue Apr 16, 2020 · 6 comments
Open

cmd/compile: improve inline memrun decision in generated alg eq routines #38494

josharian opened this issue Apr 16, 2020 · 6 comments

Comments

@josharian
Copy link
Contributor

@josharian josharian commented Apr 16, 2020

cmd/compile/internal/gc/alg.go func geneq contains this code:

// Find maximal length run of memory-only fields.
size, next := memrun(t, i)
if s := fields[i:next]; len(s) <= 2 {
	// Two or fewer fields: use plain field equality.
	for _, f := range s {
		and(eqfield(np, nq, f.Sym))
	}
} else {
	// More than two fields: use memequal.
	and(eqmem(np, nq, f.Sym, size))
}

The idea here is to inline small, simple memory comparisons instead of calling runtime.memequal.

However, using the number of fields isn't a great heuristic. If one of those fields is (say) [64]uint64, inlining it turns into a runtime call anyway. If one of those fields is (say) struct { x, y, z, w uint64 }, we end up inlining four comparisons instead of the intended one. The heuristic fails in the other direction too: If there are eight fields, but each has type byte, we'd be better off doing a single uint64 comparison than calling runtime.memequal.

A better plan would be to calculate how much work we actually have to do and then do it optimally, either with the minimal number of inlined comparisons or with a single runtime call.

Roughly, if we need to compare n bytes, figure out how many comparisons are required to accomplish that, and then use that as a threshold. (We already do something like that in walk.go's walkCompareString when comparing a non-constant string to a constant string.) One complication is alignment. On architectures with alignment requirements, comparing 8 bytes could require (say) a 2 byte comparison + a 4 byte comparison + a 2 byte comparison. The other thing that requires care is pointers: Given struct { f float32; p *int; u uint32 }, we don't want to pull half of p into one register and the other half of p into another register.

Ideally, we would also use this work calculation in our decision about whether to inline equality comparisons in the first place or call a generated routine (walk.go func walkcompare); we currently count fields there, too.

I believe that this would be challenging but possible for someone with relatively little compiler experience, so marking as help wanted (and spelling things out in more detail than usual).

@josharian josharian added this to the Unplanned milestone Apr 16, 2020
@renthraysk
Copy link

@renthraysk renthraysk commented Apr 17, 2020

For small n (<16), the minimum number of comparisons is the number of bits set in n.

@josharian
Copy link
Contributor Author

@josharian josharian commented Apr 17, 2020

@renthraysk I don't follow. What is n? Are you taking into account that some instructions can compare multiple bytes at once? And that there are alignment considerations?

@renthraysk
Copy link

@renthraysk renthraysk commented Apr 18, 2020

n is the number of bytes to compare. (Or size returned by memrun)
The number of comparisons (on 64 bit with no alignment requirements arch) would be

cost := n / 8 + bits.OnesCount(uint(n&7))

n / 8 is the number of full wide comparisons (eg x86 CMPQ)
Each of the lower 3 bits of n refers to CMPL, CMPW, CMPB respectively.

With alignment restrictions, means have to compare between [0, 7] bytes, w, first to gain alignment.

n -= w
cost := bits.OnesCount(w) + n / 8 + bits.OnesCount(uint(n&7))

Or am I missing something? (My familiarity with the go compiler internals is low)

@josharian
Copy link
Contributor Author

@josharian josharian commented Apr 18, 2020

You can do a bit better than that on unaligned arches using overlapping comparisons. E.g. you can do a 15 byte comparison by comparing bytes 0–7 and then bytes 8–15, instead of 0–7, 8–11, 12–14, 14–15. And even on unaligned arches, you need to treat pointers as having alignment requirements.

@gopherbot
Copy link

@gopherbot gopherbot commented Apr 26, 2020

Change https://golang.org/cl/230203 mentions this issue: cmd/compile: make runtime calls last in eq algs

@josharian
Copy link
Contributor Author

@josharian josharian commented Apr 26, 2020

Related (possibly a prerequisite?): #38674.

gopherbot pushed a commit that referenced this issue Apr 27, 2020
type T struct {
    f float64
    a [64]uint64
    g float64
}

Prior to this change, the generated equality algorithm for T was:

func eqT(p, q *T) bool {
    return p.f == q.f && runtime.memequal(p.a, q.a, 512) && p.g == q.g
}

In handwritten code, we would normally put the cheapest checks first.
This change takes a step in that direction. We now generate:

func eqT(p, q *T) bool {
    return p.f == q.f && p.g == q.g && runtime.memequal(p.a, q.a, 512)
}

For most types, this also generates considerably shorter code. Examples:

runtime
.eq."".mstats 406 -> 391  (-3.69%)
.eq.""._func 114 -> 101  (-11.40%)
.eq."".itab 115 -> 102  (-11.30%)
.eq."".scase 125 -> 116  (-7.20%)
.eq."".traceStack 119 -> 102  (-14.29%)
.eq."".gcControllerState 169 -> 161  (-4.73%)
.eq."".sweepdata 121 -> 112  (-7.44%)

However, for types in which we make unwise choices about inlining
memory-only comparisons (#38494), this generates longer code.

Example:

cmd/internal/obj
.eq."".objWriter 211 -> 214  (+1.42%)
.eq."".Addr 185 -> 187  (+1.08%)

Fortunately, such cases are not common.

Change-Id: I47a27da93c1f88ec71fa350c192f36b29548a217
Reviewed-on: https://go-review.googlesource.com/c/go/+/230203
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
xujianhai666 added a commit to xujianhai666/go-1 that referenced this issue May 21, 2020
type T struct {
    f float64
    a [64]uint64
    g float64
}

Prior to this change, the generated equality algorithm for T was:

func eqT(p, q *T) bool {
    return p.f == q.f && runtime.memequal(p.a, q.a, 512) && p.g == q.g
}

In handwritten code, we would normally put the cheapest checks first.
This change takes a step in that direction. We now generate:

func eqT(p, q *T) bool {
    return p.f == q.f && p.g == q.g && runtime.memequal(p.a, q.a, 512)
}

For most types, this also generates considerably shorter code. Examples:

runtime
.eq."".mstats 406 -> 391  (-3.69%)
.eq.""._func 114 -> 101  (-11.40%)
.eq."".itab 115 -> 102  (-11.30%)
.eq."".scase 125 -> 116  (-7.20%)
.eq."".traceStack 119 -> 102  (-14.29%)
.eq."".gcControllerState 169 -> 161  (-4.73%)
.eq."".sweepdata 121 -> 112  (-7.44%)

However, for types in which we make unwise choices about inlining
memory-only comparisons (golang#38494), this generates longer code.

Example:

cmd/internal/obj
.eq."".objWriter 211 -> 214  (+1.42%)
.eq."".Addr 185 -> 187  (+1.08%)

Fortunately, such cases are not common.

Change-Id: I47a27da93c1f88ec71fa350c192f36b29548a217
Reviewed-on: https://go-review.googlesource.com/c/go/+/230203
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
4 participants
You can’t perform that action at this time.