实现 compressed pair

C++ 的 std::unique_ptr 有个神奇的特性:如果使用默认的 deleter(即使用 operator delete),或者 non-capturing lambda 作为 deleter,则有

1
sizeof(std::unique<T>) == sizeof(void*);

即整个对象的内存布局和 trivial pointer 一致,没有额外的开销。

这个特性的背后就是 compress-pair;这个设施能够在某个元素是一个 empty class 时避免为其分配内存。

注:这里假设你知道什么是 EBO,以及为什么会有 EBO。

这里自己动手实现一个 compressed pair:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
template<typename Tx, typename Ty, bool = std::is_empty<Tx>::value>
struct CompressedPair : Tx {
Ty second;

template<typename T>
explicit CompressedPair(T&& t)
: Tx(),
second(std::forward<T>(t))
{}

template<typename T, typename U>
CompressedPair(T&& t, U&& u)
: Tx(std::forward<T>(t)),
second(std::forward<U>(u))
{}

Tx& get_first() noexcept
{
return *this;
}

const Tx& get_first() const noexcept
{
return *this;
}
};

template<typename Tx, typename Ty>
struct CompressedPair<Tx, Ty, false> {
Tx first;
Ty second;

template<typename T, typename U>
CompressedPair(T&& t, U&& u)
: first(std::forward<T>(t)),
second(std::forward<U>(u))
{}

Tx& get_first() noexcept
{
return first;
}

const Tx& get_first() const noexcept
{
return first;
}
};

因为 EBO 是实现的核心,而父类的构造顺序先于子类的任何成员,上面将 Tx 作为可被优化的成员。

为 CommandLine 加上值指定类型转换以及一些扯淡

过去两周抽了点时间给 KBase::CommandLine 做了一个变更,重新设计了 parameter 和 switch 的用户访问接口。

变更的其中一个核心改动是:获取 parameter 或 switch value 时提供了值类型的转换。

有了这个 change 之后,使用者可以通过类似

1
2
3
auto port = cmdline.GetSwitchValueAs<int>("port", 9876);

auto limit = cmdline.GetParameterAs<long long>(2);

的方式直接获取目标值,免去了自己手动将 std::string convert 到指定类型的操作。

同时,这两个接口还支持自定义的 data type converter,用户只需要传入一个 function object 就可以定制转换过程。


和 Python 的 argparse;golang 的 flag 乃至 boost 的 program_options 这些需要在一开始“定义”程序使用的 switches(flags) 及其绑定的变量的库不同,CommandLine 对 switches 的使用更多的是一种辅助探测,非侵入式的。

这种设计是有意的,因为这符合我个人的设计哲学:低层次的设计尽量避免对高层次的约束依赖。

Golang 的 flags 在普通场景下看似使用便利,但是如果你在多个组件里定义了同一个名叫 conf 的flag,程序就会因为 redefined flags 而导致 panic。更不用提 panic 时甚至不会给出重复定义的上下文,只能靠你自己一个一个排查。

而避免这种问题的发生的唯一方法就是,人为的规定只允许程序主模块(func main())内才能定义 flag,第三方包千万不能定义flag。

如果做不到这点,哪怕不发生 redefined flags 的问题,你的程序也会因为引入了第三方包而“自发”的获得了这些 flags 的定义。

Python 的 argparse 设计上坑比 flag 稍少,但是在一些复杂的需求上也会让你有一种如鲠在喉的感觉。

本质上,这些库充当的都是 controller 或者 manager 的角色,为了完成他们的定位,不可避免会通过提供一些高层抽象来完成建模;但是 commandline 的作用大部分时候是给主程序提供支持,作为基础库,怎么可能知道主程序对命令行有什么样的需求呢?

灵活性和易用性绝大多数的时候都是相互冲突的。

抽象虽然能够简化细节,做到 selective ignorance,但是同时也增加了约束,这部分约束也是抽象的代价之一。

Monthly Read Posts in May 2019

Concurrency

Roll Your Own Lightweight Mutex

如何利用系统提供的 semaphore synchronization primitive 实现一个轻量级的 mutex


Review of many Mutex implementations

和上面类似,但是使用了 event pritimive 作为基本设施。

因为 event 不像 semaphore 自身能够控制 running count,一旦被 evnent 被 signal 则所有 waiter 会被唤醒。因此这个实现版本在一些 edge cases 上花了不少功夫。


Implementing a Recursive Mutex

如何让 mutex 支持 recursive mode

注:实际设计中,尽可能避免使用 recursive lock


Lockless Programming

微软官方出品的无锁编程介绍文章。

质量过硬,干货满满。


Memory Reordering Caught in the Act

构造一个触发经典 memory reordering 的场景

System Architect Design

哥们,你们的系统架构中为什么要引入消息中间件?

  • 多个组件/服务之间的解耦
  • 剥离耗时调用异步化
  • 高峰流量作为 buffer 屏障进行流量削峰

Circuit Breaker and Retry

what is circuit breaker and why would we use it

common design patterns of retry

Misc

Lightweight In-Memory Logging

一个针对特殊场景涉及的 in-memory logging facility。

尽量减少 logging 产生的指令级别开销(例如尽可能使用 intrinsic 获取相关信息)


Memory Ordering at Compile Time

How once upon a time does compiler reorder instructions.

基于 semaphore 实现轻量级 mutex

核心是 Jeff Preshing 大牛的两篇文章

讲述如何利用操作系统(Windows)提供的基础同步原语,例如 semaphore,实现一个轻量级的 mutex 同步原语。

这个 home-made mutex 有如下特点:

  • 支持常规的 lock(), unkock()try_lock()
  • 在没有 race 的情况下 lock/unlock 操作都是简单的 atomic operations,开销小
  • 支持 recursive mode(第二篇文章里阐述)

之所以说是轻量级,是因为这个实现缺少一些高级功能,例如 CRITICAL_SECTION 提供的多核环境下阻塞线程前会进入 spinning state;同时在 Linux 等系统下,缺少应对 thread priority inversion 的能力 .etc

在功能够用的情况下,根据 Jeff Preshing 给出的 benchmark,这个 Lightweight mutex 性能不俗。

前方大量评注(吐槽)

如果你看完了这两篇文章并且也大致上弄明白了文章里给出的实现代码,可以继续往下看。

0x00 事实上,Windows 的 CRITICAL_SECTION 也是类似的实现。当然附属功能多了不少就是。

0x01 第二篇文章里为了实现 recursive mode,给每个 mutex 增加了一个 owner-thread 的成员。实际上,哪怕是非 recursive 的实现都应该有这个成员:因为 mutex 区别于单纯的 semaphore 的一个核心特点是,它具有 ownership 的概念。

因此第一篇文章里的实现是有欠缺的,会导致线程 A 上的 lock 能被线程 B unlock。

这个行为直接暴露了底层 semaphore 的语义,但不是 mutex 自身的语义。

0x02 Golang 的 Mutex 实现上没有 ownership 的概念,选择了直接暴露了底层的 semaphore 语义。这是一个很迷的设计,GitHub 上有人提了 issue,但是官方给的回复非常的 interesting。

0x03 示例代码里,原子的增/减用的是 _InterlockedIncrement()_InterlockedDecrement();这两个 intrinsics 会返回更新后的值。所以相比下,使用 _InterlockedExchangeAdd() 会更加高效。

因为这三个 intrinsic 函数编译后同样生成 lock xadd 指令,但是后者返回的是 original value 指令相比下少一条。

0x04 try_lock() 的实现需要用到 CAS 指令,开销更大,因此在 recursive mode 的实现中,仅当当前线程不是 owning thread 时再去尝试改变 mutex 状态是一个更好的实现。

Anvil -- An Assistant For You CMake

0x00

前段时间专门抽空做了一个小工具,也就是这里要讲的主题:anvil

一开始做 anvil 的动力很简单:某次尝试体验一下 Linux SignalFD 功能时想直接使用 ezio 的 EventLoop 作为基础事件循环,同时项目使用 cmake 管理。

为了省事,我直接从 ezio 的项目里抠出来 CMakeLists.txt 和几个自己写的 .cmake 文件,就地修改

但事实证明哪怕这样,改动量也不小,原因大体是因为:cmake 里(非函数内定义的)变量作用域是全局的,通过 fetch-content 功能引入的依赖在 add_subdirectory() 后的模块里也能看到上一层定义的变量,因此为了防止一些控制型变量发生冲突,我都在前面加上了对应的模块前缀。

所以我面对的就是一大坨变量名的更换,以及少部分声明/属性的调整。

考虑到大部分的文件内容都是可以模板化的,而手动“实例化”不仅费事还很容易出错,所以我就很自然地萌生了写一个工具自动化这个过程的想法。

0x01

在经过一两天的短暂思考后,我大致确定了这个工具的定位和需要实现的基本目标,总结起来有三个核心点:

  1. 辅助 cmake 而不是试图替代它或深度封装
  2. 内建一个轻量型的依赖管理功能
  3. 配置化的生成 & 构建流程

首先,第一点是重中之重。

Monthly Read Posts in Apr 2019

Programming Languages

Destructors that throw

C++ 11之后的 destructor 默认是 noexcept,如果有 active exception 逃逸出 dtor 会直接触发 std::terminate(),即使外部有 catch handler。可以用 noexcept(false) 显式关闭。

因为 stack unwinding 是可以嵌套的,一个精心设计的场合下(见文中例子),可以做到多个 active exception 不在一个层次里,因此也不会触发 double-exception situation。


Who calls std::terminate?

an exception leaves out from main function

an exception leaves out from initial function of a thread

an exception leaves out from dtor (since c++ 11 with noexcept guarantee)

Write Your Own DNS Query

大部分人应该都知道 DNS 协议,以及它的用处。但是考虑过自己动手写 DNS message transmission 的应该不占多数。

我们不妨考虑如何自己实现一个简单的 DNS client,完成基本的 domain name query and response parsing。

因为 DNS 协议通常使用 UDP 作为其传输层协议,而且数据包是二进制包,所以实现一个这样简单的 demo 考虑用 golang 可能会省事儿不少。

DNS Message Format

大体上 DNS 不是一个复杂的协议(虽然各类坑实在不少),所有的消息,不管是 query 还是 reply,都共享一个消息格式:

1
2
3
4
5
6
7
8
9
10
11
+---------------------+
| Header |
+---------------------+
| Question | the question for the name server
+---------------------+
| Answer | Resource Records (RRs) answering the question
+---------------------+
| Authority | RRs pointing toward an authority
+---------------------+
| Additional | RRs holding additional information
+---------------------+
  • Header:消息头,包含一些参数、标志位
  • Question:包含 query 的信息,例如需要查询的 domain
  • Answer:reply 的信息
  • Authority:如果有信息,则表明应答的服务器是 ultimate authority server。别忘了 DNS 服务器是树形结构,通常终端用户查询的 DNS 服务器都是 local DNS server。
  • Additional:服务器传回的一些额外数据,非用户显式需要的

对于一个 query message,Answer section 是空的;而对于一个 reply message,Question 保存着对应 query 的数据。

一般而言,终端设备收到的 reply 消息里,AuthorityAdditional 是空的。所以下面会跳过这两个 section 的描述。