[go] runtime: unify memeq and memequal

193 views
Skip to first unread message

Keith Randall (Gerrit)

unread,
Feb 22, 2016, 4:34:13 PM2/22/16
to Brad Fitzpatrick, Ian Lance Taylor, Keith Randall, golang-co...@googlegroups.com
Reviewers: Brad Fitzpatrick

Keith Randall uploaded a change:
https://go-review.googlesource.com/19843

runtime: unify memeq and memequal

They do the same thing, except memequal also has the short-circuit
check if the two pointers are equal.

A) We might as well always do the short-circuit check, it is only 2
instructions.
B) The extra function call (memequal->memeq) is expensive.

benchmark old ns/op new ns/op delta
BenchmarkArrayEqual-8 8.56 5.31 -37.97%

No noticeable affect on the former memeq user (maps).

Fixes #14302

Change-Id: I85d1ada59ed11e64dd6c54667f79d32cc5f81948
---
M src/runtime/alg.go
M src/runtime/asm_386.s
M src/runtime/asm_amd64.s
M src/runtime/asm_amd64p32.s
M src/runtime/asm_arm.s
M src/runtime/asm_arm64.s
M src/runtime/asm_mips64x.s
M src/runtime/asm_ppc64x.s
M src/runtime/hashmap_fast.go
M src/runtime/string_test.go
M src/runtime/stubs.go
11 files changed, 70 insertions(+), 29 deletions(-)



diff --git a/src/runtime/alg.go b/src/runtime/alg.go
index 541649c..9e19119 100644
--- a/src/runtime/alg.go
+++ b/src/runtime/alg.go
@@ -172,13 +172,6 @@
}
}

-func memequal(p, q unsafe.Pointer, size uintptr) bool {
- if p == q {
- return true
- }
- return memeq(p, q, size)
-}
-
func memequal0(p, q unsafe.Pointer) bool {
return true
}
diff --git a/src/runtime/asm_386.s b/src/runtime/asm_386.s
index 4181859..9237d57 100644
--- a/src/runtime/asm_386.s
+++ b/src/runtime/asm_386.s
@@ -1239,12 +1239,18 @@
SETEQ ret+0(FP)
RET

-TEXT runtime·memeq(SB),NOSPLIT,$0-13
+// memequal(p, q unsafe.Pointer, size uintptr) bool
+TEXT runtime·memequal(SB),NOSPLIT,$0-13
MOVL a+0(FP), SI
MOVL b+4(FP), DI
+ CMPL SI, DI
+ JEQ eq
MOVL size+8(FP), BX
LEAL ret+12(FP), AX
JMP runtime·memeqbody(SB)
+eq:
+ MOVB $1, ret+12(FP)
+ RET

// memequal_varlen(a, b unsafe.Pointer) bool
TEXT runtime·memequal_varlen(SB),NOSPLIT,$0-9
diff --git a/src/runtime/asm_amd64.s b/src/runtime/asm_amd64.s
index 5094812..98a8e83 100644
--- a/src/runtime/asm_amd64.s
+++ b/src/runtime/asm_amd64.s
@@ -1269,12 +1269,18 @@
DATA shifts<>+0xf8(SB)/8, $0xff0f0e0d0c0b0a09
GLOBL shifts<>(SB),RODATA,$256

-TEXT runtime·memeq(SB),NOSPLIT,$0-25
+// memequal(p, q unsafe.Pointer, size uintptr) bool
+TEXT runtime·memequal(SB),NOSPLIT,$0-25
MOVQ a+0(FP), SI
MOVQ b+8(FP), DI
+ CMPQ SI, DI
+ JEQ eq
MOVQ size+16(FP), BX
LEAQ ret+24(FP), AX
JMP runtime·memeqbody(SB)
+eq:
+ MOVB $1, ret+24(FP)
+ RET

// memequal_varlen(a, b unsafe.Pointer) bool
TEXT runtime·memequal_varlen(SB),NOSPLIT,$0-17
diff --git a/src/runtime/asm_amd64p32.s b/src/runtime/asm_amd64p32.s
index ecbc597..ae7a538 100644
--- a/src/runtime/asm_amd64p32.s
+++ b/src/runtime/asm_amd64p32.s
@@ -573,13 +573,19 @@
MOVL AX, ret+16(FP)
RET

-TEXT runtime·memeq(SB),NOSPLIT,$0-17
+// memequal(p, q unsafe.Pointer, size uintptr) bool
+TEXT runtime·memequal(SB),NOSPLIT,$0-13
MOVL a+0(FP), SI
MOVL b+4(FP), DI
+ CMPL SI, DI
+ JEQ eq
MOVL size+8(FP), BX
CALL runtime·memeqbody(SB)
MOVB AX, ret+16(FP)
RET
+eq:
+ MOVB $1, ret+16(FP)
+ RET

// memequal_varlen(a, b unsafe.Pointer) bool
TEXT runtime·memequal_varlen(SB),NOSPLIT,$0-9
diff --git a/src/runtime/asm_arm.s b/src/runtime/asm_arm.s
index 07894a3..5d0206d 100644
--- a/src/runtime/asm_arm.s
+++ b/src/runtime/asm_arm.s
@@ -750,13 +750,16 @@
MOVW R0, ret+8(FP)
RET

-TEXT runtime·memeq(SB),NOSPLIT,$-4-13
+// memequal(p, q unsafe.Pointer, size uintptr) bool
+TEXT runtime·memequal(SB),NOSPLIT,$-4-13
MOVW a+0(FP), R1
MOVW b+4(FP), R2
MOVW size+8(FP), R3
ADD R1, R3, R6
MOVW $1, R0
MOVB R0, ret+12(FP)
+ CMP R1, R2
+ RET.EQ
loop:
CMP R1, R6
RET.EQ
@@ -779,7 +782,7 @@
MOVW R0, 4(R13)
MOVW R1, 8(R13)
MOVW R2, 12(R13)
- BL runtime·memeq(SB)
+ BL runtime·memequal(SB)
MOVB 16(R13), R0
MOVB R0, ret+8(FP)
RET
@@ -866,7 +869,7 @@
MOVB R8, v+16(FP)
RET

-// TODO: share code with memeq?
+// TODO: share code with memequal?
TEXT bytes·Equal(SB),NOSPLIT,$0-25
MOVW a_len+4(FP), R1
MOVW b_len+16(FP), R3
diff --git a/src/runtime/asm_arm64.s b/src/runtime/asm_arm64.s
index ab5d5b5..5a5c64c 100644
--- a/src/runtime/asm_arm64.s
+++ b/src/runtime/asm_arm64.s
@@ -765,13 +765,16 @@
MOVD R3, ret+16(FP)
RET

-TEXT runtime·memeq(SB),NOSPLIT,$-8-25
+// memequal(p, q unsafe.Pointer, size uintptr) bool
+TEXT runtime·memequal(SB),NOSPLIT,$-8-25
MOVD a+0(FP), R1
MOVD b+8(FP), R2
MOVD size+16(FP), R3
ADD R1, R3, R6
MOVD $1, R0
MOVB R0, ret+24(FP)
+ CMP R1, R2
+ BEQ done
loop:
CMP R1, R6
BEQ done
@@ -794,7 +797,7 @@
MOVD R3, 8(RSP)
MOVD R4, 16(RSP)
MOVD R5, 24(RSP)
- BL runtime·memeq(SB)
+ BL runtime·memequal(SB)
MOVBU 32(RSP), R3
MOVB R3, ret+16(FP)
RET
@@ -929,7 +932,7 @@
MOVD R0, ret+24(FP)
RET

-// TODO: share code with memeq?
+// TODO: share code with memequal?
TEXT bytes·Equal(SB),NOSPLIT,$0-49
MOVD a_len+8(FP), R1
MOVD b_len+32(FP), R3
diff --git a/src/runtime/asm_mips64x.s b/src/runtime/asm_mips64x.s
index 08482fe..80cea85 100644
--- a/src/runtime/asm_mips64x.s
+++ b/src/runtime/asm_mips64x.s
@@ -647,9 +647,11 @@
TEXT runtime·aeshashstr(SB),NOSPLIT,$-8-0
MOVW (R0), R1

-TEXT runtime·memeq(SB),NOSPLIT,$-8-25
+// memequal(p, q unsafe.Pointer, size uintptr) bool
+TEXT runtime·memequal(SB),NOSPLIT,$-8-25
MOVV a+0(FP), R1
MOVV b+8(FP), R2
+ BEQ R1, R2, eq
MOVV size+16(FP), R3
ADDV R1, R3, R4
loop:
@@ -666,6 +668,10 @@

MOVB R0, ret+24(FP)
RET
+eq:
+ MOVV $1, R1
+ MOVB R1, ret+24(FP)
+ RET

// memequal_varlen(a, b unsafe.Pointer) bool
TEXT runtime·memequal_varlen(SB),NOSPLIT,$40-17
@@ -676,7 +682,7 @@
MOVV R1, 8(R29)
MOVV R2, 16(R29)
MOVV R3, 24(R29)
- JAL runtime·memeq(SB)
+ JAL runtime·memequal(SB)
MOVBU 32(R29), R1
MOVB R1, ret+16(FP)
RET
@@ -710,7 +716,7 @@
MOVB R0, ret+32(FP)
RET

-// TODO: share code with memeq?
+// TODO: share code with memequal?
TEXT bytes·Equal(SB),NOSPLIT,$0-49
MOVV a_len+8(FP), R3
MOVV b_len+32(FP), R4
diff --git a/src/runtime/asm_ppc64x.s b/src/runtime/asm_ppc64x.s
index 50c4f26..f067b4a 100644
--- a/src/runtime/asm_ppc64x.s
+++ b/src/runtime/asm_ppc64x.s
@@ -795,9 +795,12 @@
TEXT runtime·aeshashstr(SB),NOSPLIT|NOFRAME,$0-0
MOVW (R0), R1

-TEXT runtime·memeq(SB),NOSPLIT|NOFRAME,$0-25
+// memequal(p, q unsafe.Pointer, size uintptr) bool
+TEXT runtime·memequal(SB),NOSPLIT|NOFRAME,$0-25
MOVD a+0(FP), R3
MOVD b+8(FP), R4
+ CMP R3, R4
+ BEQ eq
MOVD size+16(FP), R5
SUB $1, R3
SUB $1, R4
@@ -816,6 +819,10 @@

MOVB R0, ret+24(FP)
RET
+eq:
+ MOVD $1, R1
+ MOVB R1, ret+24(FP)
+ RET

// memequal_varlen(a, b unsafe.Pointer) bool
TEXT runtime·memequal_varlen(SB),NOSPLIT,$40-17
@@ -827,7 +834,7 @@
MOVD R3, FIXED_FRAME+0(R1)
MOVD R4, FIXED_FRAME+8(R1)
MOVD R5, FIXED_FRAME+16(R1)
- BL runtime·memeq(SB)
+ BL runtime·memequal(SB)
MOVBZ FIXED_FRAME+24(R1), R3
MOVB R3, ret+16(FP)
RET
@@ -864,7 +871,7 @@
MOVB R0, ret+32(FP)
RET

-// TODO: share code with memeq?
+// TODO: share code with memequal?
TEXT bytes·Equal(SB),NOSPLIT,$0-49
MOVD a_len+8(FP), R3
MOVD b_len+32(FP), R4
diff --git a/src/runtime/hashmap_fast.go b/src/runtime/hashmap_fast.go
index 519dc77..f95ea3e 100644
--- a/src/runtime/hashmap_fast.go
+++ b/src/runtime/hashmap_fast.go
@@ -216,7 +216,7 @@
if k.len != key.len {
continue
}
- if k.str == key.str || memeq(k.str, key.str, uintptr(key.len)) {
+ if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) {
return add(unsafe.Pointer(b),
dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize))
}
}
@@ -254,7 +254,7 @@
}
if keymaybe != bucketCnt {
k := (*stringStruct)(add(unsafe.Pointer(b),
dataOffset+keymaybe*2*sys.PtrSize))
- if memeq(k.str, key.str, uintptr(key.len)) {
+ if memequal(k.str, key.str, uintptr(key.len)) {
return add(unsafe.Pointer(b),
dataOffset+bucketCnt*2*sys.PtrSize+keymaybe*uintptr(t.valuesize))
}
}
@@ -284,7 +284,7 @@
if k.len != key.len {
continue
}
- if k.str == key.str || memeq(k.str, key.str, uintptr(key.len)) {
+ if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) {
return add(unsafe.Pointer(b),
dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize))
}
}
@@ -321,7 +321,7 @@
if k.len != key.len {
continue
}
- if k.str == key.str || memeq(k.str, key.str, uintptr(key.len)) {
+ if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) {
return add(unsafe.Pointer(b),
dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize)), true
}
}
@@ -357,7 +357,7 @@
}
if keymaybe != bucketCnt {
k := (*stringStruct)(add(unsafe.Pointer(b),
dataOffset+keymaybe*2*sys.PtrSize))
- if memeq(k.str, key.str, uintptr(key.len)) {
+ if memequal(k.str, key.str, uintptr(key.len)) {
return add(unsafe.Pointer(b),
dataOffset+bucketCnt*2*sys.PtrSize+keymaybe*uintptr(t.valuesize)), true
}
}
@@ -387,7 +387,7 @@
if k.len != key.len {
continue
}
- if k.str == key.str || memeq(k.str, key.str, uintptr(key.len)) {
+ if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) {
return add(unsafe.Pointer(b),
dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.valuesize)), true
}
}
diff --git a/src/runtime/string_test.go b/src/runtime/string_test.go
index 150a255..37b75c1 100644
--- a/src/runtime/string_test.go
+++ b/src/runtime/string_test.go
@@ -102,6 +102,17 @@
}
}

+func BenchmarkArrayEqual(b *testing.B) {
+ a1 := [16]byte{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}
+ a2 := [16]byte{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}
+ b.ResetTimer()
+ for i := 0; i < b.N; i++ {
+ if a1 != a2 {
+ b.Fatal("not equal")
+ }
+ }
+}
+
func TestStringW(t *testing.T) {
strings := []string{
"hello",
diff --git a/src/runtime/stubs.go b/src/runtime/stubs.go
index f060182..6c28fd2 100644
--- a/src/runtime/stubs.go
+++ b/src/runtime/stubs.go
@@ -85,7 +85,7 @@

// in asm_*.s
//go:noescape
-func memeq(a, b unsafe.Pointer, size uintptr) bool
+func memequal(a, b unsafe.Pointer, size uintptr) bool

// noescape hides a pointer from escape analysis. noescape is
// the identity function but escape analysis doesn't think the

--
https://go-review.googlesource.com/19843
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

Keith Randall (Gerrit)

unread,
Feb 22, 2016, 4:52:33 PM2/22/16
to Keith Randall, Brad Fitzpatrick, golang-co...@googlegroups.com
Keith Randall has posted comments on this change.

runtime: unify memeq and memequal

Patch Set 1: Run-TryBot+1

--
https://go-review.googlesource.com/19843
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Keith Randall <k...@golang.org>
Gerrit-HasComments: No

Gobot Gobot (Gerrit)

unread,
Feb 22, 2016, 4:53:25 PM2/22/16
to Keith Randall, Brad Fitzpatrick, golang-co...@googlegroups.com
Gobot Gobot has posted comments on this change.

runtime: unify memeq and memequal

Patch Set 1:

TryBots beginning. Status page: http://farmer.golang.org/try?commit=7f2cfda0

--
https://go-review.googlesource.com/19843
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Gerrit-Reviewer: Gobot Gobot <go...@golang.org>

Gobot Gobot (Gerrit)

unread,
Feb 22, 2016, 5:16:12 PM2/22/16
to Keith Randall, Brad Fitzpatrick, golang-co...@googlegroups.com
Gobot Gobot has posted comments on this change.

runtime: unify memeq and memequal

Patch Set 1: TryBot-Result+1

TryBots are happy.

--
https://go-review.googlesource.com/19843
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

Brad Fitzpatrick (Gerrit)

unread,
Feb 22, 2016, 7:02:49 PM2/22/16
to Keith Randall, Brad Fitzpatrick, Gobot Gobot, golang-co...@googlegroups.com
Brad Fitzpatrick has posted comments on this change.

runtime: unify memeq and memequal

Patch Set 1: Code-Review+2

--
https://go-review.googlesource.com/19843
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>

Keith Randall (Gerrit)

unread,
Feb 22, 2016, 7:15:41 PM2/22/16
to Keith Randall, golang-...@googlegroups.com, Brad Fitzpatrick, Gobot Gobot, golang-co...@googlegroups.com
Keith Randall has submitted this change and it was merged.

runtime: unify memeq and memequal

They do the same thing, except memequal also has the short-circuit
check if the two pointers are equal.

A) We might as well always do the short-circuit check, it is only 2
instructions.
B) The extra function call (memequal->memeq) is expensive.

benchmark old ns/op new ns/op delta
BenchmarkArrayEqual-8 8.56 5.31 -37.97%

No noticeable affect on the former memeq user (maps).

Fixes #14302

Change-Id: I85d1ada59ed11e64dd6c54667f79d32cc5f81948
Reviewed-on: https://go-review.googlesource.com/19843
Run-TryBot: Keith Randall <k...@golang.org>
TryBot-Result: Gobot Gobot <go...@golang.org>
Reviewed-by: Brad Fitzpatrick <brad...@golang.org>
---
M src/runtime/alg.go
M src/runtime/asm_386.s
M src/runtime/asm_amd64.s
M src/runtime/asm_amd64p32.s
M src/runtime/asm_arm.s
M src/runtime/asm_arm64.s
M src/runtime/asm_mips64x.s
M src/runtime/asm_ppc64x.s
M src/runtime/hashmap_fast.go
M src/runtime/string_test.go
M src/runtime/stubs.go
11 files changed, 70 insertions(+), 29 deletions(-)

Approvals:
Keith Randall: Run TryBots
Gobot Gobot: TryBots succeeded
Brad Fitzpatrick: Looks good to me, approved


--
https://go-review.googlesource.com/19843
Gerrit-Reviewer: Brad Fitzpatrick <brad...@golang.org>
Reply all
Reply to author
Forward
0 new messages