Sword York – Slinuxer

字节跳动搜索部门内推

2019/07/05 Sword York 评论

这是一个内推任务。我发不了朋友圈，微博没有影响力。各位走过路过不要错过。你有兴趣或者身边的人有兴趣，麻烦发简历到 echo emhhb3NoZW5qaWFuLjAxQGJ5dGVkYW5jZS5jb20= | base64 -d 。

非官方介绍

搜索目前在头条是比较投入的方向，也是刚刚起步，希望与更多的人一起做更多的事。个人认为头条还是不错的，有很大的发展空间，待遇也好，是技术导向的公司。优势有

丰富的数据，并且有机会接触这些第一线数据
充足的计算资源，10000块卡，BERT什么都不在话下
年轻的团队，大家都非常平等，沟通没有障碍，就像在学校实验室一样，头就像实验室的导师

官方介绍

【部门介绍】
字节跳动公司搜索部门汇聚了大量行业顶尖产品和技术精英，旨在从0到1打造一个用户体验更加理想的通用搜索引擎，支持公司所有产品的搜索功能，包括今日头条、抖音、西瓜、火山、懂车帝等多款备受欢迎的知名app。在这里你有机会参与工业级搜索引擎从无到有的研发工作，并在此过程中挑战大规模分布式存储和计算架构、NLP、人工智能、ranking等世界难题，很好地锻炼自己的工程能力、算法能力、业务能力。加入我们，参与并见证一个新产品的成长和成功，同大牛们一起完成最有挑战性的工作吧！

【部门亮点】
– 公司重视程度高，团队力量强
– 从0到1，技术成长大
– 搜索系统更加复杂，挑战更大：
1. 规模：搜索数据规模更大（搜索是千亿级），对工程和算法的挑战更大，能搞定搜索的话去搞别的都不怕。
2. 场景：搜索对精度的要求比推荐更高，用户已经明确表达需求、出现不相关结果用户会吐槽，所以除了关注pv级指标、对每个搜索请求都要求精度，挑战更大。
3. NLP：搜索场景下NLP更重，人类自然语言理解问题是终极难题；deep learning已经能很好解决图像和语音等问题，但是在NLP上还有很长路要走，足见其难度；我们恰好又处在技术变革的时代，有搜索这样一个场景来研究NLP问题，是个最棒的土壤。

【招聘岗位】
算法工程师
后端开发工程师

TensorFlow XLA初步接触

2019/06/022019/06/02 Sword York 2 条评论

Tensorflow越来越像一个编译器，把计算图编译为可执行代码。其中关键的部分就是XLA (Accelerated Linear Algebra)。我在实际使用中真切感受到了XLA带来的提升，希望对XLA能有更多的了解，因此花了点时间探索了一下。

XLA框架

关于XLA，Tensorflow给出了比较简略的说明。XLA主要是用来提升计算速度、节省内存（显存）等。XLA的输入语言称为“HLO (High Level Optimizer)”，HLO定义了整个计算图。随后，XLA对HLO进行一些机器无关、高层的优化，然后用LLVM等进行机器相关、底层的优化并生成代码。这个流程如下图所示。

描绘计算图HLO，这一步可以通过tf2xla、xla_client等完成
对HLO进行广义优化（机器无关），如CSE、Loop Fusion等编译常用优化策略
针对特定设备，对HLO进行优化
LLVM等生成可执行代码

XLA流程，见https://www.tensorflow.org/xla/overview

Operation Semantics

我不是非常理解Operation Semantics是什么意思，有兴趣可以看看。我只知道HLO支持很多操作，其中比较容易接受的是Element-wise unary functions（包括abs、cos等）、Element-wise binary arithmetic operations（如相加、相乘等）……

跟这一部分比较相似的是TensorRT定义的操作，如IActivationLayer、 IElementWiseLayer等。其实神经网络很简单，靠这25个操作就能定义大部分网络。
有了这些定义之后，我们就可以描述一个网络即计算图。有了精确定义的计算图，就可以对其进行优化。

计算图优化

前面也提过，XLA首先进行计算图优化主要是跟机器无关的、高层的。如CSE、Loop Fusion等编译常用优化策略。下面出现的XLA计算图和及其优化的中间结果，可以通过设置环境变量来导出，然后转换一下即可。

XLA_FLAGS="--xla_hlo_graph_path=/tmp/test_xla_opt_alg/ --xla_generate_hlo_graph=.*" 
find *.dot | xargs -I{} dot -Tpng {} -o {}.png

1 2	XLA_FLAGS="--xla_hlo_graph_path=/tmp/test_xla_opt_alg/ --xla_generate_hlo_graph=." find .dot \| xargs -I{} dot -Tpng {} -o {}.png

CSE

我们先看看CSE（Common subexpression elimination）。我也把这出成了Byte Camp的题，由于我难以描述清楚题目，没被采用。其实这题很能打“我是搞深度学习的，为什么让我做这么多编程题”的脸。

假设我们在使用Tensorflow等编写神经网络时，为了使代码逻辑清晰，可能会写出如下运行时低效的计算：

(p0 - (p1 / (p0 + (p3 - p4)))) + (p2 * (p1 / (p0 + (p3 - p4))))

1	(p0 - (p1 / (p0 + (p3 - p4)))) + (p2 * (p1 / (p0 + (p3 - p4))))

在Tensorflow中可以表示为如下左图，其中 p1 / (p0 + (p3 - p4)) 计算了两次。XLA就能对此进行了优化，只需计算一次，计算流程被优化为如下右图形式。

我们可以通过简单的程序来完成这一过程，可以看到真实的Tensorflow代码才200行不到。这也是ICPC的一道题，有兴趣可以尝试一下。

Fusion

Fusion可能带来提升，有可能会降低效率。这跟计算和架构相关。但在神经网络和Nvidia的GPU架构下，很难出现效率降低。看一个简单的例子， np.sin(np.cos(a * b) + c) ，其中 a,b,c 都是矩阵。显然通过fusion，我们可以，

节省存储，提高cache利用率
减少kernel数

Fusion后的计算表示为CUDA代码，大概是：

__global__
void t(int n, float *a, float *b, float *c, float *d)
{
    int i = blockIdx.x*blockDim.x + threadIdx.x;
    if (i < n) d[i] = sin(cos(a[i]*b[i]) + c[i]);
}

__global__

void t(int n, float *a, float *b, float *c, float *d)

{

int i = blockIdx.x*blockDim.x + threadIdx.x;

if (i < n) d[i] = sin(cos(a[i]*b[i]) + c[i]);

}

可以看到本来要4个CUDA Kernel要完成的计算，Fusion之后1个就行了。这提升还是非常靠谱的，XLA也对此做了优化，如下图所示。显然可以带来计算效率的提升 (gpu额外开销比较大)。

normal: 0.0152
xla: 0.0060
xla gpu: 0.0092

normal: 0.0152

xla: 0.0060

xla gpu: 0.0092

BERT XLA

前面的都是随便写的计算，现在可以看看BERT开启XLA后发生了什么。先放一张图。整个BERT的计算图太大了，放不下。这里是一层Transformer，不带训练的情况，其实也够看了（放大看）。

从上图，我们可以看到Layer norm、GELU都有很多细碎的操作，这如果没有优化会产生很多额外开销和中间结果，带来的后果就是显存占用高。而XLA将这些细碎操作都Fusion在一起了，形成了一个大的Kernel。开启XLA和FP16之后，训练效率是原来的4倍，直接起飞，可能这个加速比还不是理论极限。

XLA Client

还有一个比较有意思的是XLA Client。这非常硬核，我们可以直接将numpy代码转成在GPU上运行的代码，并且附带计算图优化，完成了下面几个项目大部分功能。

具体可以参考，

这里简单使用一下xla client（基于tf 1.13.1），由于这个功能还不稳定，这个代码随时跑不起来。

numpy:
np.tanh(np.tan(np.dot(np.sin(np.cos(np.dot(a, b)) + c), a)) + c)


XLA client:
computation_builder.Tanh(
	computation_builder.Add(
    	computation_builder.Tan(
        	computation_builder.Dot(
            	computation_builder.Sin(computation_builder.Add(
                	computation_builder.Cos(
                    	computation_builder.Dot(
                        	p,
                        	computation_builder.Constant(xla_b))),
                	computation_builder.Constant(xla_c)
            	)), p)), computation_builder.Constant(xla_c)))

numpy:

np.tanh(np.tan(np.dot(np.sin(np.cos(np.dot(a, b)) + c), a)) + c)

XLA client:

computation_builder.Tanh(

computation_builder.Add(

computation_builder.Tan(

computation_builder.Dot(

computation_builder.Sin(computation_builder.Add(

computation_builder.Cos(

computation_builder.Dot(

computation_builder.Constant(xla_b))),

computation_builder.Constant(xla_c)

)), p)), computation_builder.Constant(xla_c)))

计算速度如下，

normal: 0.265
xla: 0.037
xla gpu: 0.014

normal: 0.265

xla: 0.037

xla gpu: 0.014

计算图我就不放了，这个页面太大了，已经很卡了。。。有兴趣可以自己输出计算图看看。

参考链接

Go接触

2019/04/112019/04/12 Sword York 4 条评论

最近有时间也有必要接触了Go，也有很多原因

大三的时候就想学学Go，不过由于Python耽搁了
Python的并发让我头很疼，一点也不优雅，而Go的天然并发早声名在外
业务需求
多学一门语言，提升自己的竞争力

Go的特点

学习Go几乎没有阻碍，跟着A Tour of Go一步步学下来就行。光学怎么写Go就太枯燥了。我顺便了解了一下Go，很多内容在wiki中已经说得很清楚。总结一下，

Go是静态类型，与C/C++类似，不同于Python，因此性能肯定比基于解释器的Python高。Go有垃圾回收机制、天然并发，写起来就很舒服，代价是性能肯定没有C那么高，看到一句话很有意思：Informally, Go is 50% of C’s performance (which is still really good) for 0% of the headaches.
Go这个名字取得很好，Go由Google成员开发，Go是围棋，也是gopher(鼹鼠)，为什么gopher是吉祥物？只能解释为男人的浪漫了。
Go是面向多核的语言，也就是面向未来。Go在Google中也有不少应用，我只找到古老的资料，Rob Pike的演讲、Quora的问答、关于dl.google.com的故事也很有意思。
Go没有类，但有结构体，我喜欢这点。
Go有指针，太棒了。
Go的interface设计太巧妙了。
Go的goroutine就不用说了，强、优雅。但我目前不知道CSP的细节。
Go的包管理很出色。

体验了2天Go，我无法找到Go的缺点，即使是缺点在我看来也是优点（没有面向对象）。当然Go是否是面向对象的也很难说，可以看看这篇讨论，反正我是认为这是Go的优点。我已经把Go列为第二优先语言了，学了Go可能就不用再学C/C++了。

学习和使用Go的同时能开拓新的思考方式、思维模式，就像学外语一样，思维方式会得到提升。而Go带来的思维改变就是思考要并发。当然并发不是并行，这个可以看Rob Pike的演讲，还有关于并发模式的演讲。形象的说，并发是一个人可以一边吃饭一边喝水，可以随时切换，而并行一般是做同样的事，比如左手和右手同时转笔。我觉得并发有并行的意思，可能之后还要深入理解一下，不过理解了也没啥用。

Go的并发

Go其他部分比较简单，随便学学就行，我觉得并发是Go的精髓。Go的并发很好用很优雅，可以看看性能如何。我将Go与我常用，让我头疼的Python作了对比。首先是裸的并发，就算个加法，也不join，只看起并发的开销。

import threading
import time

def add(left, right):
    return left + right

def plain_thread(n):
    for i in range(n):
        t = threading.Thread(target=add, args=(0, 0))
        t.start()
    return 0

if __name__ == "__main__":
    n = 8000
    start_time = time.time()
    ret = plain_thread(n)
    total_time = (time.time() - start_time) * 1000
    print(ret, total_time, total_time / n)

import threading

import time

def add(left, right):

return left + right

def plain_thread(n):

for i in range(n):

t = threading.Thread(target=add, args=(0, 0))

t.start()

return 0

if __name__ == "__main__":

n = 8000

start_time = time.time()

ret = plain_thread(n)

total_time = (time.time() - start_time) * 1000

print(ret, total_time, total_time / n)

package main

import (
   "fmt"
   "time"
)

func add(left, right int) int {
   return left + right
}

func plainThread(n int) int {
   for i := 0; i < n; i++ {
      go add(0, 0)
   }
   return 0
}

func main() {
   const cs = 8000
   startTime := time.Now().UnixNano()
   finalV := plainThread(cs)
   totalTime := float64(time.Now().UnixNano() - startTime) / 1e6
   fmt.Println(finalV, totalTime, totalTime / cs)
}

package main

import (

"fmt"

"time"

)

func add(left, right int) int {

return left + right

}

func plainThread(n int) int {

for i := 0; i < n; i++ {

go add(0, 0)

}

return 0

}

func main() {

const cs = 8000

startTime := time.Now().UnixNano()

finalV := plainThread(cs)

totalTime := float64(time.Now().UnixNano() - startTime) / 1e6

fmt.Println(finalV, totalTime, totalTime / cs)

}

虽然这个比较不科学，但也可以跑一下试试。

接下来跑个需要同步的，用到了并发常用的queue或channel。

import queue
import threading
import time

def daisy_add(left, right):
    item = right.get()
    left.put(item + 1)

def daisy_chain(n):
    leftmost = queue.Queue()
    right = leftmost
    left = leftmost
    
    for i in range(n):
        right = queue.Queue()
        t = threading.Thread(target=daisy_add, args=(left, right))
        t.start()
        left = right
    
    right.put(1)
    r = leftmost.get()
    return r

if __name__ == "__main__":
    n = 8000
    start_time = time.time()
    ret = daisy_chain(n)
    total_time = (time.time() - start_time) * 1000
    print(ret, total_time, total_time / n)

import queue

import threading

import time

def daisy_add(left, right):

item = right.get()

left.put(item + 1)

def daisy_chain(n):

leftmost = queue.Queue()

right = leftmost

left = leftmost

for i in range(n):

right = queue.Queue()

t = threading.Thread(target=daisy_add, args=(left, right))

t.start()

left = right

right.put(1)

r = leftmost.get()

return r

if __name__ == "__main__":

n = 8000

start_time = time.time()

ret = daisy_chain(n)

total_time = (time.time() - start_time) * 1000

print(ret, total_time, total_time / n)

package main

import (
   "fmt"
   "time"
)

func daisyAdd(left, right chan int) {
   left <- 1 + <- right
}

func daisyChain(n int) int {
   leftmost := make(chan int)
   right := leftmost
   left := leftmost

   for i := 0; i < n; i++ {
      right = make(chan int)
      go daisyAdd(left, right)
      left = right
   }

   //go func(c chan int) { c <- 1}(right)
   right <- 1
   finalV := <- leftmost
   return finalV
}

func main() {
   const cs = 8000
   startTime := time.Now().UnixNano()
   finalV := daisyChain(cs)
   totalTime := float64(time.Now().UnixNano() - startTime) / 1e6
   fmt.Println(finalV, totalTime, totalTime / cs)
}

package main

import (

"fmt"

"time"

)

func daisyAdd(left, right chan int) {

left <- 1 + <- right

}

func daisyChain(n int) int {

leftmost := make(chan int)

right := leftmost

left := leftmost

for i := 0; i < n; i++ {

right = make(chan int)

go daisyAdd(left, right)

left = right

}

//go func(c chan int) { c <- 1}(right)

right <- 1

finalV := <- leftmost

return finalV

}

func main() {

const cs = 8000

startTime := time.Now().UnixNano()

finalV := daisyChain(cs)

totalTime := float64(time.Now().UnixNano() - startTime) / 1e6

fmt.Println(finalV, totalTime, totalTime / cs)

}

上面两段代码极其相似，这也让我对channel的理解深了一点，功能上就相当于Python中的queue。粗略一测，Go和Python时间性能相差30倍。另外，这段代码中，Python在我的电脑上起不了10000个线程，Go可以起1000000个，我还没测Go的上界。

为什么goroutine这么好用？我搜索了一下，发现很多好的资源，

goroutine和thread的对比，佩服写得好
goroutine不是轻量线程，Rob Pike也说了，理解这点很重要。看了这个说明，完全就理解了

总结

以上是我接触了2天Go写的胡言乱语，希望以后看到不会脸红。总之，Go是不错的语言，值得学习。特别是现在很多情景对并发的需求越来越大、C/C++等语言的设计考虑、硬件的分布式等，Go就是顺应时代潮流的产物，Google还是爸爸。

感叹一句，什么时候我才能那么屌？

参考

Analysis of the Go runtime scheduler，以后看
Five things that make Go fast，很有深度，看了之后脑子炸了，还有一系列

作者：Sword York