Aug
10
# 背景
有一个 python 脚本调用 A 服务的 x 接口获取若干 GB 的数据（大量对象），读取和解析大约需要 5 分钟。
由于 x 接口的改造，需要改成调用 B 服务的 y 接口。
A、B 服务都是基于字节跳动的 KITE 框架开发的（今日头条Go建千亿级微服务的实践），通信协议是 thrift 0.9.2 。
# 现象
改成调用 B 服务，在测试过程中发现，每次大约到 3 分钟以后就会出现报错 TTransportException(TSocket read 0 bytes)；之后会重试，但第一次报错后，之后每次大约1分钟内就会再次报同样的错误，重试 3 次后放弃、进程退出。
# 排查
1. 由于测试的时间是晚高峰，初步判断可能是晚高峰服务端压力太大导致。次日平峰期测试仍然复现。
2. 搜索，发现有人遇到类似问题，是从 thrift 0.9 升级到 1.0，服务端没有进行 utf8 编码导致客户端的解析问题，他通过修改服务端代码解决。然而服务端显然不存在问题，因为其他的服务调用该接口表现稳定。此外我遇到的问题并没有升级thrift版本。
3. 还是从报错信息入手，在代码里搜索 "TSocket read 0 bytes"，来自于 python2.7/site-packages/thrift/transport/TSocket.py
4. 通过插入调试代码，发现并没有抛出异常，说明确实只读到了 0 字节，因此可以大致判断问题发生在 server 端。
5. 查看 B 服务的 log，发现确实有“客户端超时” 的报错信息。通过查看 KITE 框架的文档，发现默认的超时时间是 3 秒，A服务在配置文件里指定了 20s 的超时时间，而 B 服务没有指定。
6. 通过修改 B 服务的超时时间，调用成功。但为什么 python 作为一个客户端，会出现长达 3s 的停顿导致超时呢，尤其是在局域网甚至本机环境，不可能是网络原因。
7. 联想到曾经踩过的一个坑（详见：https://www.felix021.com/blog/read.php?2142），猜测是python的gc导致。虽然python是引用计数，但为了避免循环引用导致的内存泄漏，还是有一个 stw 的 gc 扫描。通过关闭这个扫描，就解决了这个超过 3s 的停顿
# 吐槽
python真是慢。同样一个api，golang只要17s就完成了调用、反序列化，而python需要长达5分钟。
# 吐槽 #2
大概过了半个月，python把内存用爆了，最后只好用 go 重写了。
有一个 python 脚本调用 A 服务的 x 接口获取若干 GB 的数据（大量对象），读取和解析大约需要 5 分钟。
由于 x 接口的改造，需要改成调用 B 服务的 y 接口。
A、B 服务都是基于字节跳动的 KITE 框架开发的（今日头条Go建千亿级微服务的实践），通信协议是 thrift 0.9.2 。
# 现象
改成调用 B 服务，在测试过程中发现，每次大约到 3 分钟以后就会出现报错 TTransportException(TSocket read 0 bytes)；之后会重试，但第一次报错后，之后每次大约1分钟内就会再次报同样的错误，重试 3 次后放弃、进程退出。
# 排查
1. 由于测试的时间是晚高峰，初步判断可能是晚高峰服务端压力太大导致。次日平峰期测试仍然复现。
2. 搜索，发现有人遇到类似问题，是从 thrift 0.9 升级到 1.0，服务端没有进行 utf8 编码导致客户端的解析问题，他通过修改服务端代码解决。然而服务端显然不存在问题，因为其他的服务调用该接口表现稳定。此外我遇到的问题并没有升级thrift版本。
3. 还是从报错信息入手，在代码里搜索 "TSocket read 0 bytes"，来自于 python2.7/site-packages/thrift/transport/TSocket.py
def read(self, sz):
try:
buff = self.handle.recv(sz)
except socket.error, e:
if (e.args[0] == errno.ECONNRESET and
(sys.platform == 'darwin' or sys.platform.startswith('freebsd'))):
self.close()
buff = ''
elif e.args[0] == errno.EINTR:
buff = self.handle.recv(sz)
if len(buff) > 0:
return buff
else:
raise
if len(buff) == 0:
raise TTransportException(type=TTransportException.END_OF_FILE, message='TSocket read 0 bytes')
return buff
try:
buff = self.handle.recv(sz)
except socket.error, e:
if (e.args[0] == errno.ECONNRESET and
(sys.platform == 'darwin' or sys.platform.startswith('freebsd'))):
self.close()
buff = ''
elif e.args[0] == errno.EINTR:
buff = self.handle.recv(sz)
if len(buff) > 0:
return buff
else:
raise
if len(buff) == 0:
raise TTransportException(type=TTransportException.END_OF_FILE, message='TSocket read 0 bytes')
return buff
4. 通过插入调试代码，发现并没有抛出异常，说明确实只读到了 0 字节，因此可以大致判断问题发生在 server 端。
5. 查看 B 服务的 log，发现确实有“客户端超时” 的报错信息。通过查看 KITE 框架的文档，发现默认的超时时间是 3 秒，A服务在配置文件里指定了 20s 的超时时间，而 B 服务没有指定。
6. 通过修改 B 服务的超时时间，调用成功。但为什么 python 作为一个客户端，会出现长达 3s 的停顿导致超时呢，尤其是在局域网甚至本机环境，不可能是网络原因。
7. 联想到曾经踩过的一个坑（详见：https://www.felix021.com/blog/read.php?2142），猜测是python的gc导致。虽然python是引用计数，但为了避免循环引用导致的内存泄漏，还是有一个 stw 的 gc 扫描。通过关闭这个扫描，就解决了这个超过 3s 的停顿
import gc
gc.disable()
gc.disable()
# 吐槽
python真是慢。同样一个api，golang只要17s就完成了调用、反序列化，而python需要长达5分钟。
# 吐槽 #2
大概过了半个月，python把内存用爆了，最后只好用 go 重写了。
Aug
10
1. 现象
某日线上服务报警（基于时序数据库做的），请求量大幅下滑。
观察ganglia监控图表，发现有部分机器CPU占用率断崖式下跌，从原先的1000%+下降到100%（20核40线程的CPU），通过内存监控可以确认服务本身并未重启。
登录异常机器，用 lsof -i :PORT1 也可以看到端口号仍被占用，但是却无法接受请求；同样，该服务的 pprof 监听端口 PORT2 能接受请求，但无响应请求。
2. 排查
在异常机器上通过 "netstat -antpl | grep CLOSE_WAIT | grep PORT1 | wc -l" 可以看到有大量连接等待关闭，达到连接上限，所以无法接受请求，PORT2 则正常。
挑一台机器重启后服务恢复正常。为了恢复业务，重启了大部分异常机器上的服务，保留两台持续排查。
使用 top 查看cpu占用率，如上所述，始终保持在 100% 左右，说明有一个线程在全速运行。
通过 perf top （注：也可以使用pstack，能看到更详细的调用栈），发现是某一个二分查找的函数在占用cpu。
经过对代码的分析，发现是传入的值小于有效查找范围，代码实现不完善，导致出现了死循环。
进一步排查发现某个api未做好数据有效性保护，导致出现无效数据。
3. 分析
问题的直接原因已经定位，但是不明确的是，为什么一个 goroutine 死循环会导致进程整体hang住？
cpu 占用率只有100%，说明只有一个 goroutine 死循环，根据 Go 的 GMP 模型，理论上应该可以schedule其他的 goroutine 继续接受请求。
查看该进程的线程数（cat /proc/PID/status），看到开启了80+系统线程，说明不是线程数量的问题。
尝试查看该进程的 goroutine 数，但 pprof 不可用，而负责这个 metrics 打点的 goroutine 自从异常以后也未再上报数据。
写了一个简单的样例代码，开启一个简单死循环的goroutine，并不会阻碍其他goroutine的执行。
有一位同学根据现象搜到了这篇文章： 如何定位 golang 进程 hang 死的 bug
根据这篇文章的分析，在有死循环goroutine的情况下，其他goroutine主动调用 runtime.GC() 会出现 hang 住的情况。
验证代码如下，确实符合预期，和前述事故的表现一致。
综合以上分析可知，当 golang 中出现一个死循环的 goroutine、该 goroutine 就会一直占用 cpu，无法被调度；而需要 STW 的 gc 又无法暂停该 goroutine，因此出现了一个调度上的死锁。
另外，根据那篇文章的说法，在 for 循环中没有函数调用的话，编译器不会插入调度代码，所以无法完成抢占式调用。《深入解析Go - 抢占式调度》中也有具体的说明 https://tiancaiamao.gitbooks.io/go-internals/content/zh/05.5.html
实际测试发现，如果是调用自己写的另外一个简单函数，仍然会出现死锁，而调用注入 fmt.Println 之类的函数，则不会出现死锁，说明Go并不是在函数调用的时候插入调度检测代码（这也不符合直觉，每次函数调用都有额外性能开销，不太划算），而是在某些库函数中增加了调度检测。
完。
某日线上服务报警（基于时序数据库做的），请求量大幅下滑。
观察ganglia监控图表，发现有部分机器CPU占用率断崖式下跌，从原先的1000%+下降到100%（20核40线程的CPU），通过内存监控可以确认服务本身并未重启。
登录异常机器，用 lsof -i :PORT1 也可以看到端口号仍被占用，但是却无法接受请求；同样，该服务的 pprof 监听端口 PORT2 能接受请求，但无响应请求。
2. 排查
在异常机器上通过 "netstat -antpl | grep CLOSE_WAIT | grep PORT1 | wc -l" 可以看到有大量连接等待关闭，达到连接上限，所以无法接受请求，PORT2 则正常。
挑一台机器重启后服务恢复正常。为了恢复业务，重启了大部分异常机器上的服务，保留两台持续排查。
使用 top 查看cpu占用率，如上所述，始终保持在 100% 左右，说明有一个线程在全速运行。
通过 perf top （注：也可以使用pstack，能看到更详细的调用栈），发现是某一个二分查找的函数在占用cpu。
经过对代码的分析，发现是传入的值小于有效查找范围，代码实现不完善，导致出现了死循环。
进一步排查发现某个api未做好数据有效性保护，导致出现无效数据。
3. 分析
问题的直接原因已经定位，但是不明确的是，为什么一个 goroutine 死循环会导致进程整体hang住？
cpu 占用率只有100%，说明只有一个 goroutine 死循环，根据 Go 的 GMP 模型，理论上应该可以schedule其他的 goroutine 继续接受请求。
查看该进程的线程数（cat /proc/PID/status），看到开启了80+系统线程，说明不是线程数量的问题。
尝试查看该进程的 goroutine 数，但 pprof 不可用，而负责这个 metrics 打点的 goroutine 自从异常以后也未再上报数据。
写了一个简单的样例代码，开启一个简单死循环的goroutine，并不会阻碍其他goroutine的执行。
func test1() {
fmt.Println("test1")
i := 0
for {
i++
}
}
func main() {
go test1()
for i := 0; i < 100; i++ {
time.Sleep(1 * time.Second)
fmt.Printf("i = %d\n", i)
}
}
fmt.Println("test1")
i := 0
for {
i++
}
}
func main() {
go test1()
for i := 0; i < 100; i++ {
time.Sleep(1 * time.Second)
fmt.Printf("i = %d\n", i)
}
}
有一位同学根据现象搜到了这篇文章： 如何定位 golang 进程 hang 死的 bug
根据这篇文章的分析，在有死循环goroutine的情况下，其他goroutine主动调用 runtime.GC() 会出现 hang 住的情况。
验证代码如下，确实符合预期，和前述事故的表现一致。
func test1() {
fmt.Println("test1")
i := 0
for {
i++
}
}
func main() {
go test1()
for i := 0; i < 100; i++ {
time.Sleep(1 * time.Second)
fmt.Printf("i = %d\n", i)
if i == 3 {
runtime.GC()
}
}
}
fmt.Println("test1")
i := 0
for {
i++
}
}
func main() {
go test1()
for i := 0; i < 100; i++ {
time.Sleep(1 * time.Second)
fmt.Printf("i = %d\n", i)
if i == 3 {
runtime.GC()
}
}
}
综合以上分析可知，当 golang 中出现一个死循环的 goroutine、该 goroutine 就会一直占用 cpu，无法被调度；而需要 STW 的 gc 又无法暂停该 goroutine，因此出现了一个调度上的死锁。
另外，根据那篇文章的说法，在 for 循环中没有函数调用的话，编译器不会插入调度代码，所以无法完成抢占式调用。《深入解析Go - 抢占式调度》中也有具体的说明 https://tiancaiamao.gitbooks.io/go-internals/content/zh/05.5.html
实际测试发现，如果是调用自己写的另外一个简单函数，仍然会出现死锁，而调用注入 fmt.Println 之类的函数，则不会出现死锁，说明Go并不是在函数调用的时候插入调度检测代码（这也不符合直觉，每次函数调用都有额外性能开销，不太划算），而是在某些库函数中增加了调度检测。
完。
Aug
2
- 堆和栈有什么区别？
- 什么分配在堆上，什么分配在栈上？
- 为什么有了堆还需要栈/有了栈还需要堆？
- 效率差别在哪儿？如何优化？
- 有哪些常见的内存分配算法？
- 内存分配算法的主要挑战是什么？如何解决？
继续引申还有gc的一系列问题
这一篇写得还蛮好的：https://blog.csdn.net/jiahehao/article/details/1842234 ，但是注意不要被最后一段话洗脑。
- 什么分配在堆上，什么分配在栈上？
- 为什么有了堆还需要栈/有了栈还需要堆？
- 效率差别在哪儿？如何优化？
- 有哪些常见的内存分配算法？
- 内存分配算法的主要挑战是什么？如何解决？
继续引申还有gc的一系列问题
这一篇写得还蛮好的：https://blog.csdn.net/jiahehao/article/details/1842234 ，但是注意不要被最后一段话洗脑。
Jul
2
线上服务Panic，部分日志如下
放狗搜了一下：math.Rand is not safe for concurrent use
from: https://github.com/golang/go/issues/3611
这个 issue 的 4 楼还提到 "top-level functions like strings.Split or fmt.Printf or rand.Int63 may be called from any goroutine at any time"
翻了一下源码，rand.Int() 用是自带 lock 的 globalRand 对象
看了下调用代码，之前的实现为了避免多个 goroutine 竞争同一个锁，所以 new 了一个 rand.Rand 对象，但没考虑到这个对象不支持并发。
最终的解决方案，是实现了一个 safeRander 。
具体代码不适合贴，核心逻辑是初始化 N 个 rand.Rand 对象和对应的 N 个锁，以及一个 index，每次调用 Int() 时，先 atomic.AddUint32(&index, 1) % N，加上对应的锁，再用对应的 rand.Rand 对象。
这样只要并发使用的goroutine不超过N个，就不会出现竞争；就算超过，竞争出现的频率也大幅减少了，而且也可以通过增加 N 来优化。
引用
err: runtime error: index out of range
Traceback:
goroutine 19209941 [running]:
...
panic(0x191d0e0, 0x2e078d0)
/usr/local/go/src/runtime/panic.go:502 +0x229
math/rand.(*rngSource).Uint64(...)
/usr/local/go/src/math/rand/rng.go:246
math/rand.(*rngSource).Int63(0xc438bb2a00, 0x0)
/usr/local/go/src/math/rand/rng.go:231 +0x8a
math/rand.(*Rand).Int63(0xc4279b3a70, 0x0)
/usr/local/go/src/math/rand/rand.go:82 +0x33
math/rand.(*Rand).Int(0xc4279b3a70, 0x0)
/usr/local/go/src/math/rand/rand.go:100 +0x2b
...
Traceback:
goroutine 19209941 [running]:
...
panic(0x191d0e0, 0x2e078d0)
/usr/local/go/src/runtime/panic.go:502 +0x229
math/rand.(*rngSource).Uint64(...)
/usr/local/go/src/math/rand/rng.go:246
math/rand.(*rngSource).Int63(0xc438bb2a00, 0x0)
/usr/local/go/src/math/rand/rng.go:231 +0x8a
math/rand.(*Rand).Int63(0xc4279b3a70, 0x0)
/usr/local/go/src/math/rand/rand.go:82 +0x33
math/rand.(*Rand).Int(0xc4279b3a70, 0x0)
/usr/local/go/src/math/rand/rand.go:100 +0x2b
...
放狗搜了一下：math.Rand is not safe for concurrent use
from: https://github.com/golang/go/issues/3611
这个 issue 的 4 楼还提到 "top-level functions like strings.Split or fmt.Printf or rand.Int63 may be called from any goroutine at any time"
翻了一下源码，rand.Int() 用是自带 lock 的 globalRand 对象
func Int() int { return globalRand.Int() }
...
var globalRand = New(&lockedSource{src: NewSource(1).(Source64)})
...
type lockedSource struct {
lk sync.Mutex
src Source64
}
...
func (r *lockedSource) Uint64() (n uint64) {
r.lk.Lock()
n = r.src.Uint64()
r.lk.Unlock()
return
}
...
var globalRand = New(&lockedSource{src: NewSource(1).(Source64)})
...
type lockedSource struct {
lk sync.Mutex
src Source64
}
...
func (r *lockedSource) Uint64() (n uint64) {
r.lk.Lock()
n = r.src.Uint64()
r.lk.Unlock()
return
}
看了下调用代码，之前的实现为了避免多个 goroutine 竞争同一个锁，所以 new 了一个 rand.Rand 对象，但没考虑到这个对象不支持并发。
最终的解决方案，是实现了一个 safeRander 。
具体代码不适合贴，核心逻辑是初始化 N 个 rand.Rand 对象和对应的 N 个锁，以及一个 index，每次调用 Int() 时，先 atomic.AddUint32(&index, 1) % N，加上对应的锁，再用对应的 rand.Rand 对象。
这样只要并发使用的goroutine不超过N个，就不会出现竞争；就算超过，竞争出现的频率也大幅减少了，而且也可以通过增加 N 来优化。
Jun
3
1. vscode 有一个特性, workbench.editor.enablePreview
当一个文件被(单击)打开、且没有被修改的情况下, tab上的 filename 是斜体, 意味着这是一个临时tab, 会被下一个打开的文件覆盖.
在打开前双击文件, 或者打开后双击 tab 上的文件名, 可以把这个 tab 固定住.
另外就是修改 workbench.editor.enablePreview 这个属性, 关闭掉.
2. vscode 还有另一个特性, workbench.editor.showTabs
当这个选项为 false 的时候, 永远只有一个 tab
这个情况我遇到过两次, 上一次倒腾了半天, 直接reset vscode了
这次又遇到, 搜 "vscode only showing one tab" 找到这个 issue
https://github.com/Microsoft/vscode/issues/51649
这才知道了解决方案
但我不知道是怎么触发的, 我并没有刻意去设置, 初步怀疑是有一个很奇怪的快捷键, 不小心打开了吧
不能理解这个选项存在的意义, 会有人需要吗?
当一个文件被(单击)打开、且没有被修改的情况下, tab上的 filename 是斜体, 意味着这是一个临时tab, 会被下一个打开的文件覆盖.
在打开前双击文件, 或者打开后双击 tab 上的文件名, 可以把这个 tab 固定住.
另外就是修改 workbench.editor.enablePreview 这个属性, 关闭掉.
2. vscode 还有另一个特性, workbench.editor.showTabs
当这个选项为 false 的时候, 永远只有一个 tab
这个情况我遇到过两次, 上一次倒腾了半天, 直接reset vscode了
这次又遇到, 搜 "vscode only showing one tab" 找到这个 issue
https://github.com/Microsoft/vscode/issues/51649
这才知道了解决方案
但我不知道是怎么触发的, 我并没有刻意去设置, 初步怀疑是有一个很奇怪的快捷键, 不小心打开了吧
不能理解这个选项存在的意义, 会有人需要吗?
Apr
24
这是罗凯同学内部《Go 快速入门》课程第五讲的作业。
第一题：使用 channel 完成打印1000以内的素数
第二题：等价二叉查找树，来自 Go tour：https://tour.go-zh.org/concurrency/7
原题使用 tree.New(1) 来生成一个包含10个元素的二叉查找树，简单的实现可以基于这一点，正好从channel里读出10个数字。
以下这个版本的实现更复杂一些，不假定二叉查找树的长度，所以加一个 wrapper，用来 close channel 。
第一题：使用 channel 完成打印1000以内的素数
package main
import "fmt"
func prime(c chan<- int) {
i := 2
for {
isPrime := true
for j := 2; j < i; j += 1 {
if i % j == 0 {
isPrime = false
}
}
if isPrime {
c <- i
}
i += 1
}
}
func main() {
c := make(chan int)
go prime(c)
for {
p := <-c
if p >= 1000 {
break
}
fmt.Println(p)
}
}
import "fmt"
func prime(c chan<- int) {
i := 2
for {
isPrime := true
for j := 2; j < i; j += 1 {
if i % j == 0 {
isPrime = false
}
}
if isPrime {
c <- i
}
i += 1
}
}
func main() {
c := make(chan int)
go prime(c)
for {
p := <-c
if p >= 1000 {
break
}
fmt.Println(p)
}
}
第二题：等价二叉查找树，来自 Go tour：https://tour.go-zh.org/concurrency/7
原题使用 tree.New(1) 来生成一个包含10个元素的二叉查找树，简单的实现可以基于这一点，正好从channel里读出10个数字。
以下这个版本的实现更复杂一些，不假定二叉查找树的长度，所以加一个 wrapper，用来 close channel 。
package main
import (
"fmt"
"golang.org/x/tour/tree"
)
// Walk 步进 tree t 将所有的值从 tree 发送到 channel ch。
func Walk(t *tree.Tree, ch chan int) {
if t == nil {
return
}
Walk(t.Left, ch)
ch <- t.Value
Walk(t.Right, ch)
}
func WalkWrapper(t *tree.Tree, ch chan int) {
Walk(t, ch)
close(ch)
}
// Same 检测树 t1 和 t2 是否含有相同的值。
func Same(t1, t2 *tree.Tree) bool {
c1 := make(chan int)
c2 := make(chan int)
go WalkWrapper(t1, c1)
go WalkWrapper(t2, c2)
for {
v1, ok1 := <-c1
v2, ok2 := <-c2
if ok1 == false && ok2 == false {
return true
} else if ok1 == false || ok2 == false {
return false
} else {
if v1 != v2 {
return false
}
}
}
}
func main() {
t1 := &tree.Tree{&tree.Tree{nil, 1, nil}, 2, &tree.Tree{nil, 3, nil}}
t2 := &tree.Tree{&tree.Tree{&tree.Tree{nil, 1, nil}, 2, nil}, 3, &tree.Tree{nil, 4, nil}}
fmt.Println(t1)
fmt.Println(t2)
fmt.Println(Same(t1, t2))
t3 := tree.New(1)
t4 := tree.New(1)
fmt.Println(t3)
fmt.Println(t4)
fmt.Println(Same(t3, t4))
}
import (
"fmt"
"golang.org/x/tour/tree"
)
// Walk 步进 tree t 将所有的值从 tree 发送到 channel ch。
func Walk(t *tree.Tree, ch chan int) {
if t == nil {
return
}
Walk(t.Left, ch)
ch <- t.Value
Walk(t.Right, ch)
}
func WalkWrapper(t *tree.Tree, ch chan int) {
Walk(t, ch)
close(ch)
}
// Same 检测树 t1 和 t2 是否含有相同的值。
func Same(t1, t2 *tree.Tree) bool {
c1 := make(chan int)
c2 := make(chan int)
go WalkWrapper(t1, c1)
go WalkWrapper(t2, c2)
for {
v1, ok1 := <-c1
v2, ok2 := <-c2
if ok1 == false && ok2 == false {
return true
} else if ok1 == false || ok2 == false {
return false
} else {
if v1 != v2 {
return false
}
}
}
}
func main() {
t1 := &tree.Tree{&tree.Tree{nil, 1, nil}, 2, &tree.Tree{nil, 3, nil}}
t2 := &tree.Tree{&tree.Tree{&tree.Tree{nil, 1, nil}, 2, nil}, 3, &tree.Tree{nil, 4, nil}}
fmt.Println(t1)
fmt.Println(t2)
fmt.Println(Same(t1, t2))
t3 := tree.New(1)
t4 := tree.New(1)
fmt.Println(t3)
fmt.Println(t4)
fmt.Println(Same(t3, t4))
}
Mar
31
这是罗凯同学布置的 Golang 学习作业。
这题之前用 Python 刷过，用的是二分法，在 [1, n / 2] 区间内，找到第一个 x，使得 x ^ 2 <= n < (x + 1) ^ 2 ，用的是 STL 中 lowerbound 的算法。
罗凯同学提到，应该使用牛顿迭代法来完成。这个方法是听说过的，但是早就忘了，于是到 wikipedia 去找了一下：
https://zh.wikipedia.org/wiki/%E7%89%9B%E9%A1%BF%E6%B3%95
求函数 f(x) 的零点，可以通过选取曲线上的任意一个点 x0 开始，然后计算 x1 = x0 - f(x1) / f'(x1) 的方式迭代，通常得到一个比 x0 更接近零点的 x1 。通过不断迭代，最终我们能找到一个零点 xn 。
对于求平方根，我们是要找到一个 x，使得 x ^2 - n = 0，也就是这里的 f(x) = x ^ 2 - n, f'(x) = 2 * x （勉强还记得这个求导公式……）
有了这个，答案就呼之欲出了：
做完以后，我想起 Quake III 的作者 John Carmack 的 平方根倒数速算法，摘录一段内容：( src: https://blog.csdn.net/zyex1108/article/details/53540824 )
Quake-III Arena (雷神之锤3)是90年代的经典游戏之一。该系列的游戏不但画面和内容不错，而且即使计算机配置低，也能极其流畅地运行。这要归功于它3D引擎的开发者约翰-卡马克（John Carmack）。事实上早在90年代初DOS时代，只要能在PC上搞个小动画都能让人惊叹一番的时候，John Carmack就推出了石破天惊的Castle Wolfstein, 然后再接再励，doom, doomII, Quake...每次都把3-D技术推到极致。他的3D引擎代码资极度高效，几乎是在压榨PC机的每条运算指令。
这个平方根倒数算法正是其中的一个例子。在3D游戏引擎中，求取照明和投影的波动角度与反射效果时，常需计算平方根倒数，而求平方根的常用算法效率较低。
Carmack 通过使用一个惊为天人的魔术常量 0x5f3759df，只需要做 1 次迭代（Quaker III源码中的为了提高精度的第二次迭代被注视掉了），就能得到一个足够精度的平方根，大幅提高了 3D 引擎的运行效率。
关于这个魔术常量，Carmack 表示并不是他自己发明的，至今为止仍未能确切知晓算法中所使用的特殊常数的起源。但 Carmack 凭一己之力，撑起了一个 3D 引擎的时代，以至于在1999年，登上了美国时代杂志评选出来的科技领域50大影响力人物榜单，并且名列第10位。
感兴趣的同学，可以在 Wikipedia 的 平方根倒数速算法 了解更多细节：
https://zh.wikipedia.org/wiki/%E5%B9%B3%E6%96%B9%E6%A0%B9%E5%80%92%E6%95%B0%E9%80%9F%E7%AE%97%E6%B3%95
这题之前用 Python 刷过，用的是二分法，在 [1, n / 2] 区间内，找到第一个 x，使得 x ^ 2 <= n < (x + 1) ^ 2 ，用的是 STL 中 lowerbound 的算法。
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x < 0:
raise Exception("invalid input")
if x < 2:
return x
left = 1
length = x / 2
while length > 1:
half = length / 2
middle = left + half
if middle * middle > x:
length = half
else:
left = middle
length = length - half
return left
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x < 0:
raise Exception("invalid input")
if x < 2:
return x
left = 1
length = x / 2
while length > 1:
half = length / 2
middle = left + half
if middle * middle > x:
length = half
else:
left = middle
length = length - half
return left
罗凯同学提到，应该使用牛顿迭代法来完成。这个方法是听说过的，但是早就忘了，于是到 wikipedia 去找了一下：
https://zh.wikipedia.org/wiki/%E7%89%9B%E9%A1%BF%E6%B3%95
求函数 f(x) 的零点，可以通过选取曲线上的任意一个点 x0 开始，然后计算 x1 = x0 - f(x1) / f'(x1) 的方式迭代，通常得到一个比 x0 更接近零点的 x1 。通过不断迭代，最终我们能找到一个零点 xn 。
对于求平方根，我们是要找到一个 x，使得 x ^2 - n = 0，也就是这里的 f(x) = x ^ 2 - n, f'(x) = 2 * x （勉强还记得这个求导公式……）
有了这个，答案就呼之欲出了：
import "math"
func mySqrt(x int) int {
f := func (i float64) float64 {
return i * i - float64(x)
}
g := func (i float64) float64 {
return 2 * i
}
var i float64 = 1.0
for math.Abs(f(i)) > 1e-6 {
i = i - f(i) / g(i)
}
return int(math.Floor(i))
}
func mySqrt(x int) int {
f := func (i float64) float64 {
return i * i - float64(x)
}
g := func (i float64) float64 {
return 2 * i
}
var i float64 = 1.0
for math.Abs(f(i)) > 1e-6 {
i = i - f(i) / g(i)
}
return int(math.Floor(i))
}
做完以后，我想起 Quake III 的作者 John Carmack 的 平方根倒数速算法，摘录一段内容：( src: https://blog.csdn.net/zyex1108/article/details/53540824 )
引用
Quake-III Arena (雷神之锤3)是90年代的经典游戏之一。该系列的游戏不但画面和内容不错，而且即使计算机配置低，也能极其流畅地运行。这要归功于它3D引擎的开发者约翰-卡马克（John Carmack）。事实上早在90年代初DOS时代，只要能在PC上搞个小动画都能让人惊叹一番的时候，John Carmack就推出了石破天惊的Castle Wolfstein, 然后再接再励，doom, doomII, Quake...每次都把3-D技术推到极致。他的3D引擎代码资极度高效，几乎是在压榨PC机的每条运算指令。
这个平方根倒数算法正是其中的一个例子。在3D游戏引擎中，求取照明和投影的波动角度与反射效果时，常需计算平方根倒数，而求平方根的常用算法效率较低。
Carmack 通过使用一个惊为天人的魔术常量 0x5f3759df，只需要做 1 次迭代（Quaker III源码中的为了提高精度的第二次迭代被注视掉了），就能得到一个足够精度的平方根，大幅提高了 3D 引擎的运行效率。
关于这个魔术常量，Carmack 表示并不是他自己发明的，至今为止仍未能确切知晓算法中所使用的特殊常数的起源。但 Carmack 凭一己之力，撑起了一个 3D 引擎的时代，以至于在1999年，登上了美国时代杂志评选出来的科技领域50大影响力人物榜单，并且名列第10位。
感兴趣的同学，可以在 Wikipedia 的 平方根倒数速算法 了解更多细节：
https://zh.wikipedia.org/wiki/%E5%B9%B3%E6%96%B9%E6%A0%B9%E5%80%92%E6%95%B0%E9%80%9F%E7%AE%97%E6%B3%95
Mar
20
困扰了很久的问题，搜了一下才发现解决起来很简单：
将 ESC 映射为 “ESC 并且设置关闭 IM ”
感谢：Tony's blog
将 ESC 映射为 “ESC 并且设置关闭 IM ”
引用
inoremap <ESC> <ESC>:set iminsert=0<CR>
感谢：Tony's blog
