我想在Go Lang中编写线性搜索算法的有效实现。该算法的关键功能是从主循环中删除数组范围检查。我的源代码是:
func Contains(a []int, x int) bool {
var t, i = a[0], len(a) - 1
a[0] = x
for a[i] != x {
i--
}
a[0] = t
return a[i] == x
}
但是Go Lang编译器(go版本为go1.12.11 linux / 386)将数组范围检查汇编程序指令插入到生成的可执行文件中:
Dump of assembler code for function main.Contains:
0x080c1ed0 <+0>: mov ecx,DWORD PTR gs:0x0
0x080c1ed7 <+7>: mov ecx,DWORD PTR [ecx-0x4]
0x080c1edd <+13>: cmp esp,DWORD PTR [ecx+0x8]
0x080c1ee0 <+16>: jbe 0x80c1f24 <main.Contains+84>
0x080c1ee2 <+18>: mov eax,DWORD PTR [esp+0x8]
0x080c1ee6 <+22>: test eax,eax
0x080c1ee8 <+24>: jbe 0x80c1f1d <main.Contains+77>
0x080c1eea <+26>: mov ecx,DWORD PTR [esp+0x4]
0x080c1eee <+30>: mov edx,DWORD PTR [ecx]
0x080c1ef0 <+32>: mov ebx,DWORD PTR [esp+0x10]
0x080c1ef4 <+36>: mov DWORD PTR [ecx],ebx
0x080c1ef6 <+38>: lea ebp,[eax-0x1]
0x080c1ef9 <+41>: jmp 0x80c1efc <main.Contains+44>
## BEGIN OF MAIN LOOP
0x080c1efb <+43>: dec ebp
!!!! UNNECESSARY ARRAY RANGE CHECK
!! 0x080c1efc <+44>: cmp ebp,eax
!! 0x080c1efe <+46>: jae 0x80c1f16 <main.Contains+70>
!!!!
0x080c1f00 <+48>: mov esi,DWORD PTR [ecx+ebp*4]
0x080c1f03 <+51>: cmp esi,ebx
0x080c1f05 <+53>: jne 0x80c1efb <main.Contains+43>
## END OF MAIN LOOP
0x080c1f07 <+55>: mov DWORD PTR [ecx],edx
0x080c1f09 <+57>: mov eax,DWORD PTR [ecx+ebp*4]
0x080c1f0c <+60>: cmp eax,ebx
0x080c1f0e <+62>: sete al
0x080c1f11 <+65>: mov BYTE PTR [esp+0x14],al
0x080c1f15 <+69>: ret
0x080c1f16 <+70>: call 0x806b270 <runtime.panicindex>
0x080c1f1b <+75>: ud2
0x080c1f1d <+77>: call 0x806b270 <runtime.panicindex>
0x080c1f22 <+82>: ud2
0x080c1f24 <+84>: call 0x808fc30 <runtime.morestack_noctxt>
0x080c1f29 <+89>: jmp 0x80c1ed0 <main.Contains>
End of assembler dump.
如何获得期望的二进制文件-不检查数组范围? go lang编译器是否可以关闭此检查?有没有一种方法可以重写源代码以获取预期的二进制代码?
用Go编程语言编写代码:
The Go Programming Language Specification
对于惯用代码,Go优化编译器通常会消除不必要的边界检查。
例如,
func Contains(a []int, x int) bool {
for _, y := range a {
if y == x {
return true
}
}
return false
}
$ go version
go version devel +71239b4f49 Mon Jan 20 15:06:42 2020 +0000 linux/amd64
$
00000000004583b0 <main.Contains>:
package main
func Contains(a []int, x int) bool {
for _, y := range a {
4583b0: 48 8b 44 24 10 mov rax,QWORD PTR [rsp+0x10]
4583b5: 48 8b 4c 24 20 mov rcx,QWORD PTR [rsp+0x20]
4583ba: 48 8b 54 24 08 mov rdx,QWORD PTR [rsp+0x8]
4583bf: 31 db xor ebx,ebx
4583c1: eb 03 jmp 4583c6 <main.Contains+0x16>
4583c3: 48 ff c3 inc rbx
4583c6: 48 39 c3 cmp rbx,rax
4583c9: 7d 0f jge 4583da <main.Contains+0x2a>
4583cb: 48 8b 34 da mov rsi,QWORD PTR [rdx+rbx*8]
if y == x {
4583cf: 48 39 ce cmp rsi,rcx
4583d2: 75 ef jne 4583c3 <main.Contains+0x13>
return true
4583d4: c6 44 24 28 01 mov BYTE PTR [rsp+0x28],0x1
4583d9: c3 ret
}
}
return false
4583da: c6 44 24 28 00 mov BYTE PTR [rsp+0x28],0x0
4583df: c3 ret
00000000004583e0 <main.main>:
}
$ go version
go version go1.12.15 linux/386
$
0808e9a0 <main.Contains>:
package main
func Contains(a []int, x int) bool {
808e9a0: 65 8b 0d 00 00 00 00 mov ecx,DWORD PTR gs:0x0
808e9a7: 8b 89 fc ff ff ff mov ecx,DWORD PTR [ecx-0x4]
808e9ad: 3b 61 08 cmp esp,DWORD PTR [ecx+0x8]
808e9b0: 76 28 jbe 808e9da <main.Contains+0x3a>
for _, y := range a {
808e9b2: 8b 44 24 08 mov eax,DWORD PTR [esp+0x8]
808e9b6: 8b 4c 24 10 mov ecx,DWORD PTR [esp+0x10]
808e9ba: 8b 54 24 04 mov edx,DWORD PTR [esp+0x4]
808e9be: 31 db xor ebx,ebx
808e9c0: eb 01 jmp 808e9c3 <main.Contains+0x23>
808e9c2: 43 inc ebx
808e9c3: 39 c3 cmp ebx,eax
808e9c5: 7d 0d jge 808e9d4 <main.Contains+0x34>
808e9c7: 8b 2c 9a mov ebp,DWORD PTR [edx+ebx*4]
if y == x {
808e9ca: 39 cd cmp ebp,ecx
808e9cc: 75 f4 jne 808e9c2 <main.Contains+0x22>
return true
808e9ce: c6 44 24 14 01 mov BYTE PTR [esp+0x14],0x1
808e9d3: c3 ret
}
}
return false
808e9d4: c6 44 24 14 00 mov BYTE PTR [esp+0x14],0x0
808e9d9: c3 ret
func Contains(a []int, x int) bool {
808e9da: e8 21 af ff ff call 8089900 <runtime.morestack_noctxt>
808e9df: eb bf jmp 808e9a0 <main.Contains>
808e9e1: cc int3
808e9e2: cc int3
808e9e3: cc int3
808e9e4: cc int3
808e9e5: cc int3
808e9e6: cc int3
808e9e7: cc int3
808e9e8: cc int3
808e9e9: cc int3
808e9ea: cc int3
808e9eb: cc int3
808e9ec: cc int3
808e9ed: cc int3
808e9ee: cc int3
808e9ef: cc int3
0808e9f0 <main.main>:
}
请注意,如果切片的长度最初为零,则代码将立即使用边界越界的数组索引。因此,Go编译器进行边界检查可能会很好。
即使长度为非零,如果切片与其他用户共享,您在a[0]
中放置的哨兵值也可以由其他值代替。如果找不到该值,则循环将从数组的开头开始。
((如果基础数组不共享,并且长度至少为1,则代码是有效的,但是我想如果希望编译器做出“未共享”的假设,则期望编译器会占用很多内容。 )