DEV Community: Bob Fang

Retrofitting Async/Await in Go 1.18

Bob Fang — Tue, 22 Mar 2022 17:05:32 +0000

TL; DR: Why I think async/await might have a place in Golang, and we don't even need a new syntax.

A mistake

Let me start this blog by observing one common mistake I found among people who are new to Golang, say if we have an API that sets some data from a data store:

func SetKeyValue(key string, value string) error

And you want to write to the data store unblockingly in your program. What do you do? Like this?

go SetKeyValue("hello", "world")

It seems natural, right? Yeah, I have seen this in actual production code. But this irritates me a bit because we ignore potential errors that this function might return. Shouldn't we at least log the error if we ever encounter any? This requires us to wrap the above call into an IIFE.

go func() {
   err := setKeyValue("hello", "world")
   if err != nil {
       logs.Error("error happened: %v", err) 
   } 
}()

So here is the mistake: I rarely think it is okay to call a function with just a go keyword. In the real world of a backend engineer, you are almost always calling a function that might return an error. We need to treat them with respect.

Getting Data Asyncly

Now, what about getting data from some data store? For example, if you need to query two or three data sources, you typically do not want to write sync code that reads them one by one. Instead, you use goroutine to help you parallelise the queries.

// signature of the get data api
func GetDataAsInt(key string) (int, error)

// Sync code
hello, err := GetDataAsInt("hello")
if err != nil {
  // logging error 
}
foo, err := GetDataAsInt("foo")
if err != nil {
  // logging error
}

And to make this block of code async we usually do:

resultChan := make(chan int)
errChan := make(chan error)

var wg sync.WaitGroup()
wg.Add(2)

go func() {
  defer wg.Done()
  hello, err := GetDataAsInt("hello")
  resultChan <- hello
  errChan <- err
}()

go func() {
  defer wg.Done()
  foo, err := GetDataAsInt("foo")
  resultChan <- foo
  errChan <- err
}()

wg.Wait()

This is a simplification. I have left out the code that reads the errors and results out of the channels. But you can already see this is quite a bit more complex than the sync version. There is a lot of syntactic noise, we need to wrap the function we want to call in an IIFE or a function, we need to attach the go keyword to indicate we want to call this function asyncly, and then we need to use channels to collect the result. On top of this, we need to add a WaitGroup so we are sure both goroutines finished their work.

Wait, wait... getting data asyncly should be easy right? This pattern is so common that some other languages have a special syntax for it -- async/await! The equivalent of the above program in Javascript will look like this:

async function GetDataAsIntAsync(key) {
  ...
}

// inside an async function
const [hello, foo] = await Promise.all([GetDataAsIntAsync("hello"), GetDataAsIntAsync("foo")]);

I feel this is much cleaner. Can we have this in Golang? Probably not before Golang 1.18, but with the introduction of Go Generics, I feel we might be onto something. We've already talked about the Result type in Golang, but can we take it further? Luckily someone already did! I recently found this repo and I think it is promising.

Aync/Awit in Go

Let's first look at some examples:

import (
    "context"
    "code.nkcmr.net/async"
)

type MyData struct {/* ... */}

func AsyncFetchData(ctx context.Context, dataID int64) async.Promise[MyData] {
    return async.NewPromise(func() (MyData, error) {
        /* ... */
        return myDataFromRemoteServer, nil
    })
}

func DealWithData(ctx context.Context) {
    myDataPromise := AsyncFetchData(ctx, 451)
    // do other stuff while operation is not settled
    // once your ready to wait for data:
    myData, err := myDataPromise.Await(ctx)
    if err != nil {/* ... */}
}

So this library introduced a new interface Promise and a function, NewPromise, to turn a sync function to a promise which can be awaited. Using these tools we can turn the above code of ours to:

func AsyncGetDataAsInt(ctx context.Context, key string) async.Promise[int] {
  return async.NewPromise(func() (int, error) {
    return GetDataAsInt(key)
  })
}

helloPromise := AsyncGetDataAsInt(ctx, "hello")
fooPromise := AsyncGetDataAsInt(ctx, "foo")

hello, err := helloPromise.Await(ctx)
if err != nil { /* ... */ }
foo, err := fooPromise.Await(ctx)
if err != nil { /* ... */ }

Obviously, this is less verbose than the channel version. How does this work? Internally the NewPromise function is actually calling our function asyncly, and everything is stored in a internal type called syncPromise:

// Taken from: https://github.com/nkcmr/async/blob/main/async.go
// NewPromise wraps a function in a goroutine that will make the result of that
// function deliver its result to the holder of the promise.
func NewPromise[T any](fn func() (T, error)) Promise[T] {
    c := &syncPromise[T]{
        done: make(chan struct{}),
    }
    go func() {
        c.v, c.err = fn()
        close(c.done)
    }()
    return c
}

Definition of syncPromise:

// Taken from: https://github.com/nkcmr/async/blob/main/async.go

type syncPromise[T any] struct {
    done chan struct{}
    v    T
    err  error
}

func (s *syncPromise[T]) Await(ctx context.Context) (T, error) {
    select {
    case <-ctx.Done():
        var zerov T
        return zerov, ctx.Err()
    case <-s.done:
        return s.v, s.err
    }
}

func (s *syncPromise[T]) Settled() bool {
    select {
    case <-s.done:
        return true
    default:
        return false
    }
}

Note that when the function finished its work, it close the channel c.done. This will mean c.done is immediately ready for communication. Thus the select statements in Await and Settled will be using the clause in case <-s.done.

Conclusion

Although this library is still experimental, I feel it has great potential. I will invest time to play around it. And I hope one day its usage will be common in Golang's world.

The Async Story -- Motivation (Chinese)

Bob Fang — Tue, 22 Mar 2022 17:05:01 +0000

这是我vlog的文字稿，vlog可以在这里观看：https://www.youtube.com/watch?v=eoJUmM7O8-A

开场

大家好，之前因为一些个人原因，一直没能及时更新这个频道。最近生活逐渐稳定下来。终于有时间来跟大家讲一讲我一直很关注的一个业界趋势了。
在我刚开始工作的时候，大概是15-16年，初出茅庐的我注意到工业界慢慢掀起了一场关于async programming（也就是我们中文中所说的异步编程）的革命。到现在为止，我自己所常用的语言已经都有了相对成熟的异步编程的解决方案。

我经常看到有些同学，特别是转码和刚工作的朋友，在这方面了解不深，不能完全理解异步编程的动机，适用范围和使用方法。所以我想开一个新坑，专门聊聊这方面的话题。主要会包括：异步编程是什么，为了什么，怎么用，以及最后可能会深入讲一讲背后的实现原理。但是我不会把这个系列做成只讲异步编程的专题，而是会在讲异步编程的时候顺便带一些其他的相关概念，这也是我自己对知识的一个梳理。

今天这期，我们先抛开那些关于异步编程的晦涩难懂的名词，来聊聊为什么我们要用异步编程。

Blocked IO and scalability

让我们回到2007年，也就是iPhone发布的那一年，随着web2.0和移动互联网的出现，越来越多的应用程序从简单的单机程序变成了需要和远端服务器进行通讯的客户端程序。在这个大的时代背景下，人们逐渐意识到大多数程序的瓶颈在与IO。为什么这么说呢？让我们先来看几个例子：

读取一个文件，相信大家都写过和图里类似的code，从文件中读取一些数据到内存中进行处理，大家一般会注意到如果文件越大，那么这段代码执行的时间会越长。而且程序会在readlines这里暂停，后面的code会只有在readlines结束后才运行

  with open('readme.txt') as f:
      lines = f.readlines()

第二个例子：一个TCP的echo server, 我们用Python的socket library来监听一个端口，然后持续的接受新的信息，并把这个信息写回给客户端。大家可以注意到，这个程序会在两个地方暂停，一个是接受数据的地方，我们会1）等待客户端发送数据；2）因为linux的架构，我们接收到数据后需要把数据从内核空间拷贝到用户空间。在发送时也需要做相反的工作 -- 把数据从用户空间拷贝到内核空间，并等待网卡把我们的数据发送出去。所有的这些操作都会造成程序”空转“，在程序进行IO的时候我们的CPU其实没有利用起来，而是在等待IO操作的完成。

  #!/usr/bin/env python3

  import socket

  HOST = '127.0.0.1'  # Standard loopback interface address (localhost)
  PORT = 65432        # Port to listen on (non-privileged ports are > 1023)

  with socket.socket(socket.AF_INET, socket.SOCK_STREAM) as s:
      s.bind((HOST, PORT))
      s.listen()
      conn, addr = s.accept()
      with conn:
          print('Connected by', addr)
          while True:
              data = conn.recv(1024)
              if not data:
                  break
              conn.sendall(data)

IO会暂时中断程序运行，这一个特性，给我们的客户端和服务端开发都带来了挑战。

客户端

在客户端，如果应用程序需要在获取远端数据时暂停执行，那么很可能这个暂停会影响到程序界面的渲染。我们拿一个简单的blog网站举例，网站在渲染过程中，我们有时候需要从服务器获取图片，或者通过一些API拿到渲染网站UI需要的数据。如果我们的程序需要在所有的IO处等待，用户将不能看到一个流畅的网站渲染过程。比如这里，如果页面在获取我的头像时卡住，那么后面的博客列表将不能及时显示给用户，用户必须等待我的头像出现后才能看到博客列表，这样的用户体验并不是最优的。

大部分的现代应用程序的渲染都采取这样一种策略，就是无论现在客户端有什么数据，都先渲染已经可以渲染的部分，其他部分可以用占位符代替，同时程序会异步请求需要完整渲染页面的数据，然后在数据到来后重新渲染之前用占位符替代的部分。

我们这里可以看一下知名网站Quora的渲染慢放，可以注意到网站一开始是只有一个大的框架的，浏览器在渲染页面的过程中可以同时异步获取数据，等获取数据成功后才把相对应的网页部件重新进行渲染。这样的网页设计是相对更responsive的，能提供比等待所有数据加载后然后一次性渲染网页给用户更好的体验。

聪明的小伙伴肯定已经发现了，在这里我们运用异步编程时，其实是为了实现所谓的“concurrency”，就是当使用异步编程时我们的程序能在同一时间内其实在同时做着几件不同的事情。比如还是回到网页页面渲染的例子，在不使用异步编程的时候，我们的code需要先获取所有需要的数据，然后渲染整个页面。但是如果我们正确的使用了异步编程，可以达到程序同时请求三个不同组件的数据，然后分别渲染每个组件的效果，大大减小了用户看到第一个渲染出来的UI的时间。其实这和我们日常生活中的道理是类似的，我们不会在等外卖的时候只等外卖，而是会看书，学习，打打游戏。而浏览器也不应该在等待数据时空闲，我们的程序应该能够在等待其他组件的数据返回时渲染已经可以渲染的组件。

服务端

from flask import Flask
from db import get_data_from_db

app = Flask(__name__)


@app.route('/')
def hello():
    data = get_data_from_db()
    return data

在服务端我们面临着类似的情况。相信很多小伙伴也都写过类似的程序（这里用Flask举例），如图中所示的程序，它在处理http request时的流程是：

先接受从客户端发来的http请求
根据request到db里面取得相应的数据
把数据返回给用户

那么如果在程序正在处理第一个请求时，同时有另一位用户发出另一个请求呢？不难看出，因为我们的程序是没有任何concurrency的，那么请求2只有等待请求1彻底执行完后才能开始被处理。这无疑增加了用户2的等待时间，带给用户的是不友好的用户体验，这是不可以接受的。

但是如果我们仔细分析，在我们的程序和数据库进行IO的时候，其实我们的程序会因为等待数据库返回数据进行同步IO而暂停。这个时间是不是可以利用起来处理请求2呢？答案是可以的，只要我们能够正确的使用异步编程，那么我们的服务端程序也可以实现concurrency，同时处理多个请求。

总结

相信小伙伴们到这里已经大概有些朦胧的感觉，知道异步编程是为了解决同步IO带来的挑战而出现的一种新的编程模式，但是我知道一定会有小伙伴更疑惑了：

当我们平时讨论concurrency的时候，不是一般都在讨论进程（也就是我们所说的process）和线程（thread）么？为什么异步编程也在讨论concurrency？这些concurrency之间有什么区别？
异步编程到底是怎么在底层实现的？我们怎么知道什么时候要用异步编程？为什么我在网络上看到谈论异步编程时会谈到libuv，select和epoll？它们到底是什么？
异步编程里为什么会有协程这个概念？协程有几种？我们用的协程是哪一种？
都说异步编程是有传染性的，那么这种传染性体现在什么地方？对我们的code会造成什么样的影响？
Go也是用异步编程么?

这些问题，我都会在后面的视频中一一解答。敬请期待。但是在我们离开这个视频前，我想现就后面的内容做一些说明:

视频会以用Python展示为主，间或会用一些C，Javascript或者其他比较典型的语言来说明举例。使用Python的主要原因是因为Python的code一般比较直观，更容易懂，但是Python也有不适合用来说明异步编程的地方，比如Python里既有thread 又有subprocess，还有async/await，更要命的是Python还有个GIL作怪，所以有些时候我们可能会用其他一些语言辅助。需要用到C来展示system call的时候，我会展示一些C的code。
这个系列形式会比较散，我想更多的讨论不同情况下不同技术选择带来的trade off，以及不同技术后面的实现原理。所以我不会讲太高深的异步编程技巧，而是专注用我们最基本的一些计算机科学的概念来还原业界从同步IO到异步IO这个变化潮流的始末，让我们的小伙伴更好地理解异步编程带来的好处，希望能给大家在实际工作中带来便利。

谢谢大家收看！我们下期见！

Why Go?

Bob Fang — Tue, 14 Dec 2021 11:00:12 +0000

💡 I am going to use Golang to refer to what is known as the Go programming language, simply because it is more search engine friendly.

There are two new languages¹, that comes out of the 2010s era as strong winners, Golang and Rust. While Rust is apparently the new lover of the developer community, I think Golang has enjoyed more commercial success. For example some of the biggest unicorns coming out of this age are using Golang as their main language: Coinbase, Twitch, Uber and where I work: Tiktok.

But why? Why Golang? Obviously Golang is very opinionated language. One has to admit that some choices Golang made are not not appealing to everyone. A few problems are mentioned repeatably, which nonetheless will be reiterated here as I personally find them hard to swallow as well.

Generics

Supporting generics is so essential in building modern software, but Golang only plans to start supporting them in the upcoming release, 1.18. That is almost a decade after its initial release. I think no one enjoys writing the following code when other languages can provide similar functionality easily with parametric polymorphism.

func MinInt(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func MinInt32(a, b int32) int32 {
    if a < b {
        return a
    }
    return b
}

func MinInt64(a, b int64) int64 {
    if a < b {
        return a
    }
    return b
}

Image Source ²

Error handling

I am not going to say that exception is a wonderful thing, and every language should have them. Also Option or Maybe types have their own pros and cons, and may not be suitable for every scenario. But Golang community's choice of using if err != nil just seems pretty primitive these days. I think the Golang community even tried to compensate the lack of proper error handling by inventing a new coding style, called "the happy path". It is a nice try, and maybe to some extend it make sense, but still I would prefer we are not forced to check error codes for every single function call...

No default or optional arguments

So people start using pointers to represent an optional argument. I think I have seen and even written a number of functions that looks like this:

func doSomething(..., int* mode) {
    if mode == nil {
        mode = 1    
    }
    ...
}

Just so that the caller can optionally choose to not pass in a parameter, but still this is unsatisfying, user still need to pass nil for mode here to actually make their code compiles, but this is already much better than other options listed in this SO answer, like making your function to accept variadic args, an map of interface{} or a special struct.

No dedicated enum types

Again, Golang community will come up (or has already come up) with all sorts of excuses that why this is not needed. But I think this example has perfectly summed up the problem with not having a syntax construct for defining "clean" enums. I just cannot understand why we still need to deal with C-style unscoped enums in 2021.

Arrogant library design

Can you guess what does this line do?

fmt.Println(t.Format("20060102150405"))

It formats a datetime object to yyyyMMddHHmmss format. But what is the deal with that special number? It seems that Golang core team has decided a specific time point, "2006-01-02T15:04:05Z07:00" is more readable than universal "yyyyMMddHHmmss" as a time format directive. Why? I can hardly imagine. But I can only underestimate how much energy are wasted to adopt to this style, which are forced upon many programmers through the standard library.

The list can go on, but let me stop here, as no programming language is perfect. I think you got the idea, Golang has some real issues it needs to deal with, but still it has become very successful. So why? What's the benefit? Why people like/still uses it despite its flaws?

Money

One factor that should not go unnoticed it that it has a trillion-dollar company's backing. I think it should be universally acknowledged by now that not every language are created equal. Apple has Objective-c/Swift, and Google itself has backed Kotlin and Dart. These languages all enjoyed some level of popularity. Are they the best languages? Maybe, maybe not. But if you want a language that are well maintained, and has the possibility of evolving, you would choose one that has some commercial backing, right?

Concurrency

Some would argue that Golang has been successful for concurrency. The appeal comes from being able to launch thousands of goroutines, each serving one user, without running into major memory or CPU limitations. In the beginning of the decade the industry were facing the C10k problem. Golang cleverly provided an escape from this, by providing a new primitive, goroutines, that:

are fast to launch, usually an order of magnitude faster than OS-level threads
have smaller memory foot-print, only 4k stack size initially but can grow as needed
have little need for manual control: users are not required to manually join a goroutine, GC will take care of most of the work when a goroutine finishes its work.

These options, when provided in the early 2010s, are much better than the alternatives, where the only option to get some kind of concurrency is to use low-level OS threads, possibly forcing you to implement a thread-pool so your service does not blow up the memory usage when there are many connections.

But are goroutines so special that it makes Golang the only scalable language? I think not. Recent years has seen the rise of async programming, notably first in node.js but later in Python and C++. More and more languages are incorporating coroutines natively and goroutines are nothing but just another type of them, see below excerpt from the Golang doc.

Goroutines are part of making concurrency easy to use. The idea, which has been around for a while, is to multiplex independently executing functions—coroutines—onto a set of threads. When a coroutine blocks, such as by calling a blocking system call, the run-time automatically moves other coroutines on the same operating system thread to a different, runnable thread so they won't be blocked. The programmer sees none of this, which is the point. The result, which we call goroutines, can be very cheap: they have little overhead beyond the memory for the stack, which is just a few kilobytes.

To make the stacks small, Go's run-time uses resizable, bounded stacks. A newly minted goroutine is given a few kilobytes, which is almost always enough. When it isn't, the run-time grows (and shrinks) the memory for storing the stack automatically, allowing many goroutines to live in a modest amount of memory. The CPU overhead averages about three cheap instructions per function call. It is practical to create hundreds of thousands of goroutines in the same address space. If goroutines were just threads, system resources would run out at a much smaller number.

So IMO basically Golang is just one step ahead of other language on this front, by providing a cheap and easy-to-use coroutine primitive that none other languages were providing. And there is no deny that Golang's goroutine implementation is outstanding, the goroutine scheduler works like a charm specially. I think this is the reason that Golang has won a large user base who has the need to write concurrent code, especially for things like networking or distributed systems. It is then no wonder that this is the area where Golang has enjoyed a great success, building cloud native infra like docker, kubernetes and online real-time services like Uber, Twitch or Tiktok.

Many would argue that first class channels, or the general adoption of CSP has made writing concurrent code easier in Golang, I am not going to say that I disagree, because I do not think I have enough experience against the claim. But I would not say I support it either. For two major reasons:

We are still using a fair bit share-memory communication in Golang still. The sync package can be seen used very commonly in any Golang repo, where people use concurrency primitives like Lock or Waitgroup to coordinate goroutines.
For myself, when using a goroutine, the most common use case would be to fetch something from a remote http/rpc service, so there is not much need to do inter-goroutine coordination using channels as no data is shared. Usually we just need to use one channel to get the result back. So I have not faced a scenario where I can use channels to simply the logic. And often in this case I will miss more widely adopted async/await pattern where the result can be just returned by the goroutine like a normal function.

So I am not convinced that channels make everything better. I see why they are useful, but I do not see why they cannot be implemented as libraries in other languages.

Build, Performance and Deployment

Golang's compiler is unreasonably fast. Compiling a project with 131 files and more than 26k lines of code only take less than 5 seconds on my local machine. This is much much better than any C++ compilers out there, and although I am not a Java™ user I am pretty certain that none of the Java compilers can achieve the same level of performance either.

How about interpreted language, you ask, as they do not need to be compiled. Well, that's true but they have a much slower run-time performance, and larger memory foot-print. I am not going to bore you with just another benchmark which make no sense in real world, but from my experience Golang do have an edge here.

Golang has another advantage over interpreted languages which is when deploying, you often just need to send one binary file to the server, without needing to install a number of dependencies first. This may seems trivial but if you have tried package a Python service into a docker container, you will often be amazed the (large) disk space you need.

Conclusion

I have some mixed feeling of Golang at this moment, on the one hand it is really primitive. Using it feels like using a knife in a battle field when everyone else are already using laser guns. But it do has something that other language cannot offer at this moment: a fast compiler, a very performant coroutine implementation (special call out to its GMP scheduler), an active community and a few killer apps like docker and k8s.

I guess ultimately the big question is that if I am just building a web service that does not need to serve millions of users at the same time, will I choose Golang? Probably not as then Python is much more ergonomic (with its async support) and I am pretty sure the developer productivity boost will outweigh the run-time performance degradation. But if you are a large company and you do need to think about the money saved on using less memory and CPU? Maybe, just maybe, Golang will make it worthwhile for you.

Some may argue the most successful language of this era is Python, because of the rise of machine learning and data science. But remember Python is an "old" language, it just celebrated its 30th birthday. Here we emphasis the real new languages of the past decade. ↩
Go and generics : ProgrammerHumor ↩

Performance issue of unordered_map

Bob Fang — Tue, 14 Dec 2021 10:59:41 +0000

注：这只是我视频内容的底稿，有些细节只在视频内容里呈现了，所以有不清楚的地方请先看视频！

大家好，欢迎来到 Let’s C++的第三期，在这一起里我想和大家探讨一下关于 STL 里面的一个著名的容器类，std::unordered_map 的性能问题。

std::unordered_map 也会有性能问题？

很多小伙伴都知道，我们一般不推荐大家使用 std::map，这是因为 std::map 会自动把你插入的元素按照他们的键值排序，为了实现这样的 interface(interface 有好的中文翻译么?)，一般的 C++实现会用红黑树或者 AVL 树这样的自平衡二叉树。这样的话每次插入新的元素，查找元素和删除元素的操作都是 O(logn),所以从原理上讲 std::map 就是比较慢的。所以当我们需要一个类似 python 里的 dictionary 的数据结构时，我们一般会使用 std::unordered_map，std::unordered_map 和 python 里的 dictionary 一样，都可以理解为一个哈希表的具体实现。它的插入，查找，删除都是 O(1)的，比 std::map 好了不少。

那么，std::unordered_map 已经用上了理论上讲操作最优的实现，为什么我们还在谈它的性能问题呢？

我曾在一家 hedge fund 工作，当时在我们内部的代码库中用 C++实现了一个像 Python Pandas 一样的 dataframe 类，我在这个 hedge fund 的第一个 project 就是为这个 C++ dataframe 做性能调优。在这个 dataframe 内部我们保存数据时用到的就是 std::unordered_map。也就是在我做性能调优的过程中通过不断地 profiling 发现很多 dataframe 的瓶颈其实是在 std::unordered_map。

给大家举个例子，我们参考这个简单的面试题：给你一个整数 vector，请你返回一个 bool，告诉我这个 vector 里有没有重复的元素。

加入我们不考虑 hash_set 一个简单的实现可以写成这样：

#include <unordered_map>

using namespace std;

class UnorderedMapSolution {
public:
  bool containsDuplicate(const vector<int> &nums) {
    unordered_map<int, int> m;
    for (auto i : nums) {
      m[i] += 1;
    }

    for (auto i : m) {
      if (i.second > 1)
        return true;
    }

    return false;
  }
};

这里的 unordered_map 其实可以替换成任何一个 hash table 的实现，包括我们刚刚谈到的 std::map。不久前 google 开源了他们内部的 abesil flat hash map 类，这也是一个 hash table，我在网上还找到了一些 C++爱好者的作品，那么我们可以看一下他们之间的对比。

我们可以看到，同样的算法，如果我们用 std::map 比 std::unordered_map 大约慢了三倍，然而如果我们用 Google 的实现，那么他们比 STL 又快了 3 倍，就连社区里的爱好者自己写的，也比 clang/gcc 这些“久经考验”的开源库自带的 C++ STL 实现快，那么这是为什么呢？

hash table 的实现

在我们的算法和数据结构的课程里我们一般会介绍下面这样的一种哈希表的实现，每个哈希表都是一个定长的数组，每个 key 可以用一个 hash function 被影射到这个数组中的一个 cell，每个 cell 其实包含了一个链表。

当我们插入一个元素的时候，我们会根据它的 key 算出相对的哈希值，如果两个元素的哈希值是相同的，那么我们就会把后插入的元素加入在它哈希值对应的那个链表的最后。这种处理哈希碰撞的办法我们一般叫做 open hashing，或者叫做 closed addressing。

但是我们其实还有另一种处理哈希碰撞的办法，与 open hashing 相对应，可以叫做 closed hashing，也可以叫做 open addressing。

在两个元素的哈希值相同时，与其我们把后插入的这个元素放在一个链表中，我们可以把这个元素放在哈希表本来就有的这个数组当中，只要我们能够找到一个还没有被使用的 cell，那么我们就可以把后插入的元素放在这个空的 cell 当中。至于怎么找这个 cell，一般使用的办法有三种：

linear probing: h(x, k+1) = a * h(x, k) + c
qudatic probing: h(x, k+1) = a _ h(x, k) ^ 2 + b _ h(x, k) + c
double hash probing: h(x, k+1) = h(h(x, k))

这里 k 代表我们调用这个哈希函数的次数。如果一个元素在第一次哈希之后的 cell 不是空的，那么我们就用上面的 probing 技巧为这个元素再找一个新的 cell。

最简单的 linear probing function 可以是 h(x, k+1) = h(x, k) + 1。

大家可以猜一下：Google 的实现用了那种哈希碰撞的解决办法？

答案是第二种，也就是我们说的 open addressing，而且 Google 用的就是最简单的 linear probing。那么为什么这样写出来的哈希表比较快呢？给大家一点提示-->从硬件的角度考虑考虑？

答案是缓存，我们都知道如果我们的程序如果是顺序处理连续的内存，那么 CPU 会把我们正在处理的内存附近的内容读到他自己的缓存当中，下次如果 CPU 需要处理已经在缓存中的内容时，它就不需要从系统的主存重新读取相同的内容。

因为 Google 的哈希表用没有使用链表，而是采用了 open addressing+用一个 array 保存所有的键值对的方案，所以它的 performance 才远好于使用了传统的基于链表的实现。

那么 std::unordered_map 是不是可以改成这种实现呢？答案是暂时不行：如果我们看 STL 的文档，那么我们会发现 unordered_map 把它内部试用 buckets+linked list 的细节也暴露在了它的 API 当中。

Hyrum's Law:
With a sufficient number of users of an API, it does not matter what you promise in the contract, all observable behaviors of you system will be depended on by somebody

问题

那么 Google flat_hash_map 是不是没有缺点呢？Pointer Invalidation。提一句。

更深一点

对我们普通程序员了解这些有什么用呢：

junior: cache matters! use continuous data structure if possible
senior: open source matters! without open source what can we do?
all: API design matters, the reason to have an API is to hide implementation details!

Fun fact

At every moment in Google:

1% CPU is consumed by a C++ hash table
4% RAM is consumed by a C++ hash table

Reference

New Blog 新博客

Bob Fang — Tue, 14 Dec 2021 10:59:10 +0000

This is a my new blog. It is mainly about CS, but sometimes I will cover other things I found interesting, like history/politics/science etc.

这是我的新博客。我大部分时候会更新和计算机科学相关的内容，但是有的时候也会覆盖一些跟历史，政治或者其他科技类我觉得感兴趣的话题。

Now some tests I want to run.

Embed a youtube video

Write some code?

C++

#include <iostream>
int main() {
    std::cout << "Hello world" << std::end;
}

Python

print("hello world")

A simple result type in Golang 1.18

Bob Fang — Tue, 14 Dec 2021 10:58:39 +0000

With the introduction of generics in Go 1.18. One of the pain point I had with Golang has been finanly resolved.

In my day job, there are a lot of times I need to implement a "map-reduce" style algorithm using goroutines. Some thing like this:

func processing() {
    works := []Work{
        {
            Name: "John",
            Age:  30,
        },
        {
            Name: "Jane",
            Age:  25,
        },
        ...
    }

    var wg sync.WaitGroup

    result := make(chan ProcessedWork, len(works))
    for _, work := range works {
        wg.Add(1)
        go func(work Work) {
            defer wg.Done()
            // do something
            newData, err := doSomething(work)
            result <- newData
        }(work)
    }

    wg.Wait()
    close(result)

    for r := range result {
        // combine results in some way
    }
    return ...
}

This may looks like all good, but there is a problem. What if one of the sub goroutine failed, what if this line actually return an error?

newData, err := doSomething(work)

So usually you have two options, one is to simply introduce a seperate error channel, and the next is to introduce a new Result type locally and change the result channel here to accept the Result type. In this example we can do this:

type Result struct {
    Data ProcessedWork
    Err  error
}
result := make(chan Result, len(works))

I usually opt for the second solution, but having to define this type every time is a pain. There were some suggestions to use interface{} to represent the Data and do type assertion when using the data, but generally I am not a big fan of using interface{} in Go.

Luckily we got generics in Go 1.18, so our Result type can be defined using this feature.

type Result[T any] struct {
    value T
    err   error
}

Having this type is much better than using ad-hoc Result types for each processing function in the code base.

A number of useful methods can be added to the Result type, for example

func (r Result[T]) Ok() bool {
    return r.err == nil
}

func (r Result[T]) ValueOr(v T) T {
    if r.Ok() {
        return r.value
    }
    return v
}

func (r Result[T]) ValueOrPanic() T {
    if r.Ok() {
        return r.value
    }
    panic(r.err)
}

There are some obvious things I want to point out though.

Golang does not do sum type yet, there are proposals to add this, but I think it will come much later. Currenlty the best way to emulate a sum type in Golang is to simply use a struct and remeber which field you have used, like what we did here with the Result type. Other languages call this discrimated union if you include a special field which denote the field being used.
Result type, no matter what method you use to implement it, is not a new concept. C++ has std::optional since C++17. Rust, the golden boy of this era, has Result<T, E>. Haskell, where I first learned the conecpt of using types to represent the outcome of an operation that may or may not success, has Maybe.

Further to point 2, another thing to notice is that Result is actually a monad, C++23 recently added monadic operation for std::optional, and Hasekll has the following functions in its stdlib since long before this conecpt is popular.

return :: a -> Maybe a
return x  = Just x

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
(>>=) m g = case m of
                Nothing -> Nothing
                Just x  -> g x

The nice thing about these two functions, especially for the second function (>>=), is that it allows you to easily combine/chain multiple operations that may or may not yield a result together without the need to keep using if to check if the result of last operation is Ok or not. I am not going to enumerate an example, but if you are curious you can look at the Hasekll example here.

But Golang is a bit lacking, at this moment, if everything goes according to the plan, then we will not be able to have another idependent type variable in a generic type's method. So we cannot have something like this:

func (r Result[T]) Then(f func(T) Result[S]) Result[S] { // <-- S is not allowed, we can only use T
    if r.Ok() {
        return f(r.value)
    }
    return r
}

IMO, this restriction quite serverly limited the usefulness of the result type.

Another thing I wish we had is C++ style "partial specialization" in Go's generics. For now the constraints for Result is any, but I do want to provide a function like this for user:

func (r Result[T]) Eq(v T) bool {
    if r.Ok() {
        return r.value == v
    }
    return false
}

But since T is not comparable, the == operatior will not work. If Go can provide a way to refine the constraints for some methods of a generic type, then it would be a nice feature. E.g.

// here we refined the T type from any to comparable by providing a more precise constraints in the method receiver type
// now only Result that holds a T that are in the constraint comparable will have this method enabled.
func (r Result[T comparable]) Eq(v T) bool {

    if r.Ok() {
        return r.value == v
    }

    return false
}

Sample code can be found here

Async Programming: faster, but how much faster?

Bob Fang — Tue, 14 Dec 2021 10:56:01 +0000

TL;DR: Python asyncio is about 3.5 times faster than threading. Golang is very performant and has better scalability. It is curious to see why.

In recent years we have seen the rise of async programming in mainstream programming languages. Constructs like promises, async/await, and coroutines can now be found in Javascript, Python and even good old C++. As we all know, this is a side effect of another trend -- more and more applications now rely on network IO, and IO takes time. Instead of wasting your precious CPU cycles waiting for the servers to get back to you, it is wiser to continue other essential tasks, like UI rendering, and resume what you were doing when the data is available.

Lately, I have been working on a project suitable for applying async programming. Part of the requirement of this project is to query a list of HTTP endpoints simultaneously, get the responses and combine them to produce the result. I think this use case is a good playground for demonstrating the usefulness of async programming. Moreover, it would be interesting to test different programming languages' choices of async primitives and their implementation to see how well they perform in real-world scenarios. The main metrics I concern myself most are 1) the ergonomics of using these async programming primitives and 2) the performance gain we get from using async programming in these languages.

Python

Threads?

As a long time user, the first language that comes to my mind is Python. Traditionally, Python has limited concurrency support. It has a threading library, but in Python, there should be only one thread running at each given time because of the Global Interpreter Lock (GIL), thus limiting the usefulness of threads ¹. Python also has a multiprocessing module in the standard library. However, its drawback is that it forces the programmers to deal with Inter-Process Communication (IPC) — the default choice is too restricting (pickles).

Even if Python had good support of threading and (sub)processes, I am not too keen to use them because they are often too low-level to be helpful. You need to handle communication and synchronisation. Threads/processes are system-level resources, so proper clean up is always required, adding unnecessary complexity to application code. Plus, compared to other concurrency models like coroutines, threads and processes are always more expensive -- they consume more memory and are slower to start.

Asyncio!

Fortunately, from Python 3.6 on, we have the new asyncio standard library baked into the language ².

Let's demonstrate the benefits of async programming by walking through an example: I want to get a list of Pokemon's names through the Pokemon API. Here is how I would do it in traditional Python:



BASE_URL = "https://pokeapi.co/api/v2/pokemon/"
result = []
for i in range(1, number+1):
    r = httpx.get(BASE_URL + str(i))
    result.append(r)
        jsons = []
for r in result:
    try:
        jsons.append(r.json())
    except json.decoder.JSONDecodeError:
        print(r.text)
print(f"Got {len(jsons)} pokemons")

The above code is easy to understand; the only thing to notice here is that http.get is synchronous. Python interpreter will block further execution if the HTTP client has not got a response. Time, your precious time, is wasted!

Below code achieves the same effect, but using asyncio:



async def get_pokemons(number: int):
    tasks = []

    async with httpx.AsyncClient() as client:
        for i in range(1, number+1):
            r = client.get(BASE_URL + str(i))
            tasks.append(r)
        result = await asyncio.gather(*tasks)

    return result

result = asyncio.run(get_pokemons(number))
jsons = []
for r in result:
    try:
        jsons.append(r.json())
    except json.decoder.JSONDecodeError:
        print(r.text)

Admittedly, the code becomes slightly more complex. But we programmers know we must pay a little bit price for concurrency, right? Compared to the threading version³, which is the "old" way of achieving concurrency, the asyncio code is very readable -- it hides details an application developer does not care about.

So how does asyncio perform?

It is no doubt that the sync and wait version is slow, but what this graph does not tell you is that the threading pool version is much slower than the async one; let's zoom in a little bit:

And plotting for only asyncio:

In general, even when using multi-threading in Python, getting all the responses we need is slower by 3.5 times than using asyncio. This might be unintuitive, as asyncio uses only one thread. But as mentioned previously, the GIL is playing a role here, so there is no concurrency, although we have multiple threads. In contrast, in asyncio, the concurrency is achieved through OS-provided IO multiplexing -- a single thread can wait on multiple IO events simultaneously using the epoll system call and schedule its work using an event loop.

But I am not satisfied. Although asyncio is faster, if we look at the blue line, the total time to get all the response has a linear relationship with the number of requests we sent. My theory was that when using asyncio, since the GIL does not bound us, we simultaneously established many TCP connections to the server. Assuming the server itself is concurrent, we should get all the responses back at an almost identical time. Thus the blue line's slope should not be that obvious.

Like sprinters racing to cross the finish line, our HTTP responses should arrive at almost the same time.

Somehow this is not the case. I have several theories, but none of them can fully explain this issue at this moment.

But what about other languages? Do their implementation of asyncio suffer the same issue?

Golang

A Golang implementation of the same idea we use in Python looks

Note that in Golang, we do not have the concept of a coroutine; goroutine is a special primitive that can only be found in Golang. The code here may give you the impression that function getPokemon seems to be running in a thread, but there are two essential things to remember:

goroutines are green threads; they are not OS-level threads, so they are cheaper to launch
HTTP or any networking IO calls in Golang is async, but Golang has made them look synchronous to be easily used in goroutines ⁴.

Let's look at the performance:

Ignoring the apparent outliers, we can see that the line is almost flat. This is what I have expected, and it shows that Golang's implementation has better scalability than Python when using async IO.

Also, to note: the y-axis's unit for Golang is milliseconds, not seconds, and the x-axis's maximum value is almost 1600, twice as many as Python's. Compared to Python, Golang is much faster.

Food for thought

Given that we know that Golang and Python are all using epoll internally for IO multiplexing, and we understand from libevent's benchmark below that epoll has an almost O(1) scalability. Python's linear scalability seems rather strange and suggests that asyncio has some optimisation awaiting.

Special thanks for Pokemon API. I have spaced out my experiments, so it should be well in the range of their fair use policy's tolerance.

Some C extensions can bypass the GIL, but they are not relevant to our discussion. ↩
The Python community had numerous previous attempts to fit async programming into the languages with third-party libraries, like twisted or tornado. But I came to the part too late; my only exposure to async in Python is via newer iterations like asyncio or trio. ↩
Here, we use concurrent.futures to automatically handle creating and joining threads. So the code already reads better than a pure threading implementation but still falls behind the asyncio version. ↩
See the explanation here for more details: https://morsmachine.dk/netpoller ↩

Career Changes 近期职业发展

Bob Fang — Tue, 14 Dec 2021 10:55:59 +0000

我已经在 2021 年三月暂时离开了对冲基金这个行业。现在在伦敦的 Tiktok 工作。

I have left the hedge fund industry temporarily since March 2021, and now I work at Tiktok London.

TOML Parser Online

Bob Fang — Sun, 12 Jul 2020 07:48:10 +0000

I maintain this website for parsing TOML into json objects.

Please let me know if you need any features or found any bugs.