Algorithms

Shuffling

class MessageLoop

Version: r70_3538
File: base/message_loop/message_loop.{h, cc}

A MessageLoop is used to process events for a particular thread, i.e. the core infrastructure for implementing Communicating Sequential Process (CSP) model.

There is at most one MessageLoop instance on a thread.

MessageLoop is a farily complex class, it driveds from multiple base classes:

1
2
3
4
5

class BASE_EXPORT MessageLoop : public MessagePump::Delegate,
                                public RunLoop::Delegate,
                                public MessageLoopCurrent {
    // omitted...
};

MessageLoop Type

A MessageLoop has a particular type, differred by the set of asynchronous events it is capable of handling.

在 cmder 里如果不指定运行的 terminal 则会默认使用 windows cmd，而这在使用 git-bash 或者 wsl 时会经常遇到问题：

1. 性能底下导致交互出现显著延迟（这个发生在使用 tig 等重型 bash 命令或者使用 wsl中）
2. 容易因为环境属性问题导致乱码，比如 cmder 里直接运行 git-bash 的 tig 会发现提交历史的分割线都乱码了

首先简单介绍一下 EBO（Empty Base Class Optimization）。

因为 C++ 规定，任何一个 instance 在内存中必须要有唯一的地址，因此一个空的 class/struct 会在编译时被偷偷插入一个外人看不到的 char mem;，于是这个空类的每一个 instance 都可以有一个唯一的地址了。

但是如果将这个空类作为某个类的成员时，这个隐藏的成员会被计入内存布局之中，考虑到 memory padding，有时候会导致类对象体积膨涨一倍。

例如考虑：

1
2
3
4
5
6
7
8
9

class E {};

class A1 {
    E e;
    int i;
};

assert(sizeof(E) == 1);
assert(sizeof(A1) == 8);

我们会发现每一个 A1 的 instance 都占了 8-byte，比起 4-byte 足足翻了一倍。

占用内存无端变大导致 cache 问题啥的就不讲了，这方面的内容任何讲 computer architecture 的书应该都会有。

Our fancy star in this post is class base::MessageLoopCurrent.

MessageLoopCurrent

Version: r70_3538
File: base/message_loop/message_loop_current.{h, cc}

MessageLoopCurernt is a proxy class for interactions with the MessageLoop bound to the current thread.

It is introduced to avoid direct uses of MessageLoop::current(), quoting from original comments:

Why: Historically MessageLoop::current() gave access to the full MessageLoop API, preventing both addition of powerful owner-only APIs as well as making it harder to remove callers of deprecated APIs (that need to stick around for a few owner-only use cases and re-accrue callers after cleanup per remaining publicly available).

Because it is a light-weight proxy, it contains only a single pointer to the MessageLoop bound to the current thread.

Concurrency

C11 Lock-free Stack

使用C 11 atomic operations 实现一个轻量的 lock-free stack

• pre-allocation，不需要考虑单个节点的销毁问题，所以不需要使用 hazard pointer
• free 和 head 两个列表，两个单独的 head 均可用做 sentinel
• 使用 aba counter 来避免 ABA problem

MySQL/InnoDB中，乐观锁、悲观锁、共享锁、排它锁、行锁、表锁、死锁概念的理解

感觉这篇讲的好混乱，几个概念是明显正交的都混在一起了。

瞄了一眼，基本脑子里都在找平常 locking mechanism 里的概念做映射了。

The method to epoll’s madness

总体写的一般，而且内容有点乱。

madness 应该指的就是 epoll 对外表现的是引用 file descriptor 但是内部维护的确实 file descrption。

这是我在实现 ezio connector 时遇到的一个比较有意（keng）思（die）的问题。

在使用 non-blocking 的 connect(2) 时，按照 manual 的说法，如果调用的返回被认为是合理的（例如 EINPROGRESS），那么就需要：