一道面试题: Top K 问题

最近在招一个Go开发工程师,面试中时候我会问一个Top K的问题,这个问题是一个经典的面试题。

有时候我不会要求面试者写出答案,首先我听一下他的思想,如果写代码困难的话我都允许可以上网查标准库的文档,看看heap的用法。

相对来说比Redis的作者antirez的面试要轻松些了,他的面试题是要求面试者写出一个二叉搜索树。

阅读全文

聊聊 Go 的边界检查消除技术

在翻译的从慢速到SIMD一文中, SourceGraph工程师其中的一个优化就是边界检查消除(BCE,bounds check elimination)技术,同时他也抛给了读者一个问题:

为啥在使用 a[i:i+4:i+4] 而不是 a[i:i+4]?

本文第一部分先回答这个问题。 第二部分介绍更好的边界检查消除方法。 第三部分再全面梳理Go的边界检查消除技术。

阅读全文

遍历函数?Go 1.22中隐藏的功能

Go 1.22中可以 range 一个整数,比如下面的代码:

1
2
3
for i := range 10 {
fmt.Println(i)
}

这个大家都已经知道了,其实对应的提案中还有一个隐藏的功能,就是可以 range 一个函数,比如下面的代码(摘自官方代码库internal/trace/v2/event.go):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Frames is an iterator over the frames in a Stack.
func (s Stack) Frames(yield func(f StackFrame) bool) bool {
if s.id == 0 {
return true
}
stk := s.table.stacks.mustGet(s.id)
for _, f := range stk.frames {
sf := StackFrame{
PC: f.pc,
Func: s.table.strings.mustGet(f.funcID),
File: s.table.strings.mustGet(f.fileID),
Line: f.line,
}
if !yield(sf) {
return false
}
}
return true
}

就少有介绍了。

本文尝试介绍它,让读者先了解一下,它在Go 1.22 中是一个实验性的功能,还不确定未来在哪个版本中会被正式支持。

官方wiki中也有一篇介绍: Rangefunc Experiment,类似问答的形式,也是必读的知识库。

阅读全文

高效I/O并发处理:双缓冲和Exchanger

双缓冲(double buffering)是高效处理I/O操作的一种并发技术,它使用两个buffer,一个goroutine使用其中一个buffer进行写,而另一个goroutine使用另一个buffer进行读,然后进行交换。这样两个goroutine可能并发的执行,减少它们之间的等待和阻塞。

本文还提供了一个类似Java的java.util.concurrent.Exchanger的Go并发原语,它可以用来在两个goroutine之间交换数据,快速实现双缓冲的模式。 这个并发原语可以在github.com/smallnest/exp/sync/Exchanger找到。

阅读全文