软件设计哲学(NOTE)

RED FLAGS

Shallow Module

A shallow module is one whose interface is complicated relative to the functionality it provides. Shallow modules don’t help much in the battle against complexity, because the benefit they provide (not having to learn about how they work internally) is negated by the cost of learning and using their interfaces. Small modules tend to be shallow.

Information Leakage

Information leakage occurs when the same knownledge is used in multiple places, such as two different classed that both understand the format of a particular type of file.

Temporal Decomposition

In temporal decomposition, execution order is reflected in the code structure: operations that happen at different times are in different methods or classes. If the same knowledge is used at different points in execution, it get encoded in multiple places, resulting in information leakage.

Overexposure

If the API for a commonly used feature forces users to learn about other features that are rarely used, this increases the cognitive load on users who don’t need the rarely used features.

Pass-Through Method

A pass-through method is one that does nothing except pass its arguments to another method, usually with the same API as the pass-through method. This typically indicates that there is not a clean division of respoinsibility between the classes.

Repetition

If the same piece of code (or code that is almost the same) appears over and over again, that’s a red flag that you haven’t found the right abstractions.

Special-General Mixture

This red flag occurs when a general-purpose mechanism also contains code specialized for a particular use of that mechanism. This makes the mechanism more complicated and creates information leakage between the 80 mechanism and the particular use case: future modifications to the use case are likely to require changes to the underlying mechanism as well.

Conjoined Methods

It should be possible to understand each method independently. If you can’t understand the implementation of one method without also understanding the implementation of another, that’s a red flag.

Comment Repeats Code

Red Flag: Comment Repeats Code If the information in a comment is already obvious from the code next to the comment, then the comment isn’t helpful. One example of this is when the comment uses the same words that make up the name of the thing it is describing.

Implementation Documentation Contaminates Interface

This red flag occurs when interface documentation, such as that for a method, describes implementation details that aren’t needed in order to use the thing being documented.

Vague Name

If a variable or method name is broad enough to refer to many different things, then it doesn’t convey much information to the developer and the underlying entity is more likely to be misused.

Hard to Pick Name

If it’s hard to find a simple name for a variable or method that creates a clear image of the underlying object, that’s a hint that the underlying object may not have a clean design.

Hard to Describe

The comment that describes a method or variable should be simple and yet complete. If you find it difficult to write such a comment, that’s an indicator that there may be a problem with the design of the thing you are describing.

EXCERPT

Definition

Complexity is anything related to the structure of a software system that makes it hard to understand and modify the system. $$ C = \sum_{p}c_pt_p $$ The overall complexity of a system $(C)$ is determined by the complexity of each part $p(c_p)$ weighted by the faction of time developers spend working on the part $(t_p)$.

Symptoms

  • Change amplification: The first symptom of complexity is that a seemingly simple change requires code modifications in many different places.
  • Cognitive load: The second symptom of complexity is cognitive load, which refers to how much a developer needs to know in order to complete a task.
  • Unknown unknowns: The third symptom of complexity is that it is not obvious which pieces of code must be modified to complete a task, or what information a developer must have to carry out the task successfully.

Modules

  • In this world, the complexity of a system would be the complexity of its worst module.
  • The interface describes what the module does but not how it does it.
  • The best modules are those whose interfaces are much simpler than their implementations.
  • An abstraction is a simplified view of an entity, which omits unimportant details.
  • Interface:
    • The interface to a module contains two kinds of information: formal and informal.
      • The formal parts of an interface are specified explicitly in the code, and some of these can be checked for correctness by the programming language.
      • The informal parts of an interface includes its high-level behavior, such as the fact that a function deletes the file named by one of its arguments.
    • In modular programming, each module provides an abstraction in form of its interface. The interface presents a simplified view of the module’s functionality; the details of the implementation are unimportant from the standpoint of the module’s abstraction, so they are omitted from the interface. A detail can only be omiited from an abstraction if it is unimportant.
  • The best modules are those that provide powerful functionality yet have simple interfaces: they have a lot of functionality hidden behind a simple interface. A deep module is a good abstraction because only a small fraction of its internal complexity is visible to its users.
  • Classitis may result in classes that are individually simple, but it increases the complexity of the overall system. Small classes don’t contribute much functionality, so there have to be a lot of them, each with its own interface. These interfaces accumulate to create tremendous complexity at the system level.
  • Provide choice is good, but interfaces should be designed to make the common case as simple as possible. If an interface has many features, but most developers only need to be aware of a few of them, the effective complexity of that interface is just the complexity of the commonly used features.
  • The most important (and perhaps surprising) benefit of the general- purpose approach is that it results in simpler and deeper interfaces than a special-purpose approach. The general-purpose approach can also save you time in the future, if you reuse the class for other purposes. However, even if the module is only used for its original purpose, the general-purpose approach is still better because of its simplicity.
  • Questions to ask yourself
    • What is the simplest interface that will cover all my current needs?
    • In how many situations will this method be used?
    • Is this API easy to use for my current needs?
  • Decorators
    • A decorator object takes an existing object and extends its functionality; it provides an API similar or identical to the underlying object, and its methods invoke the methods of the underlying object.
    • Before creating a decorator class, consider alternatives such as the following:
      • Could you add the new functionality directly to the underlying class, rather than creating a decorator class?
      • If the new functionality is specialized for a particular use case, would it make sense to merge it with the use case, rather than creating a separate class?
      • Could you merge the new functionality with an existing decorator, rather than creating a new decorator?
      • Finally, ask yourself whether the new functionality really needs to wrap the existing functionality: could you implement it as a stand-alone class that is independent of the base class?

Together vs Apart

  • Bring together if information is shared
  • Bring together if it will simplify the interface
  • Bring together to eliminate duplication

Comments

  • Documentation also plays an important role in abstraction; without comments, you can’t hide complexity.
  • If users must read the code of a method in order to use it, then there is no abstraction: all of the complexity of the method is exposed.
  • Many of the most important comments are those related to abstractions, such as the top-level documentation for classes and methods.
  • The overall idea behind comments is to capture information that was in the mind of the designer but couldn’t be represented in the code.
  • Comments should describe things that aren’t obvious from the code.
  • One of the most important reasons for comments is abstractions, which include a lot of information that isn’t obvious from the code.
  • Developers should be able to understand the abstraction provided by a module without reading any code other than its externally visible declarations.
  • Comments categories:
    • Interface: a comment block that immediately precedes the declaration of a module such as a class, data structure, function, or method. The comment describe’s the module’s interface.
    • Data structure member: a comment next to the declaration of a field in a data structure, such as an instance variable or static variable for a class.
    • Implementation comment: a comment inside the code of a method or function, which describes how the code works internally.
    • Cross-module comment: a comment describing dependencies that cross module boundaries.
  • After you have written a comment, ask yourself the following question: could someone who has never seen the code write the comment just by looking at the code next to the comment? If the answer is yes, as in the examples above, then the comment doesn’t make the code any easier to understand. Comments like these are why some people think that comments are worthless.
  • Comments augment the code by providing information at a different level of detail.
    • Precision is most useful when commenting variable declarations such as class instance variables, method arguments, and return values. The name and type in a variable declaration are typically not very precise. Comments can fill in missing details such as:
      • What are the units for this variable?
      • Are the boundary conditions inclusive or exclusive?
      • If a null value is permitted, what does it imply?
      • If a variable refers to a resource that must eventually be freed or closed, who is responsible for freeing or closing it?
      • Are there certain properties that are always true for the variable (invariants), such as “this list always contains at least one entry”?
    • When documenting a variable, think nouns, not verbs. In other words, focus on what the variable represents, not how it is manipulated.
  • The best time to write comments is at the beginning of the process, as you write the code. Writing the comments first makes documentation part of the design process. Not only does this produce better documentation, but it also produces better designs and it makes the process of writing documentation more enjoyable.

Interface Comments

The interface comment for a method includes both higher-level information for abstraction and lower-level details for precision:

  • The comment usually starts with a sentence or two describing the behavior of the method as perceived by callers; this is the higher-level abstraction.
  • The comment must describe each argument and the return value (if any). These comments must be very precise, and must describe any constraints on argument values as well as dependencies between arguments.
  • If the method has any side effects, these must be documented in the interface comment. A side effect is any consequence of the method that affects the future behavior of the system but is not part of the result. For example, if the method adds a value to an internal data structure, which can be retrieved by future method calls, this is a side effect; writing to the file system is also a side effect.
  • A method’s interface comment must describe any exceptions that can emanate from the method.
  • If there are any preconditions that must be satisfied before a method is invoked, these must be described (perhaps some other method must be invoked first; for a binary search method, the list being searched must be sorted). It is a good idea to minimize preconditions, but any that remain must be documented.

Implementation Comments

The main goal of implementation comments is to help readers understand what the code is doing (not how it does it).

Paxos Note

Symbols And Structure

  • 表决 $B$
    struct Ballot {
      dec: Decree,      // 表决的内容
      vot: Set<Node>,   // 表决投票通过的节点
      qrm: Set<Node>,   // 表决参与的节点
      bal: u64,         // 表决编号
    }
    
    A ballot is said to be successful, if every quorum member voted. In math: $$ B_{qrm} \subseteq B_{vot} $$
  • 投票 $v$
    struct Vote {
      pst: Node,        // 本投票的节点
      bal: u64,         // 本投票的表决编号
      dec: Decree,      // 本投票表决的内容
    }
    
  • 表决的集合 $\beta$

Define Some Useful functions

  • $Votes(\beta)$:所有在 $\beta$ 中的表决的投票的集合 $$Votes(\beta) = \{v:(v_{pst}\in B_{vot})\cap(v_{bal}=B_{bal}), B \in \beta\}$$
  • $Max(b, p, \beta)$:在由节点 $p$ 投给 $\beta$ 中的表决的投票中,编号小与等于 $b$ 的最大投票 $$Max(b, p,\beta)=max\{v \in Votes(\beta):(v_{pst}=p)\land(v_{bal}<b)\}\cup\{null_{p}\}$$
  • $MaxVote(b, Q, \beta)$:在集合 $Q$ 中的任意一个节点投给 $\beta$ 中的表决的投票中,编号小于等于 $b$ 的最大投票 $$MaxVote(b,Q,\beta)=max\{v\in Votes(\beta):(v_{pst}\in Q)\cap(v_{val}<b)\}\cup\{null_p\}$$

那么如果条件$B1(\beta)-B3(\beta)$满足的情况下,那么系统将满足一致性,并且是可进展的。

  • $B1(\beta) \triangleq \forall B,B' \in \beta:(B \ne B') \implies (B_{bal} \ne B'_{bal})$
  • $B2(\beta) \triangleq \forall B,B' \in \beta:B_{qrm}\cap B'_{qrm} \ne \emptyset $
  • $B3(\beta) \triangleq \forall B \in \beta: (MaxVote(B_{bal},B_{qrm},\beta)_{bal}\ne - \infty) \implies B_{dec} = MaxVote(B_{bal}, B_{qrm}, \beta)_{dec} $

Lemma 1

如果 $\beta$ 中的表决 $B$ 是成功的,那么 $\beta$ 中更大编号的表决和 $B$ 的表决内容相同。 $$ ((B_{qrm} \subseteq B_{vot})\land(B'_{bal}>B_{bal})) \implies (B'_{dec}=B_{dec}) $$

Proof

定义集合 $\Psi(B, \beta)$: $\Psi(B, \beta) \triangleq \{B'\in \beta:(B'_{bal}>B_{bal})\land(B'_{dec}\ne B_{dec}) \}$,表示 $\beta$ 中编号比 $B$ 大并且表决内容不相同的表决的集合。

  1. $ C = min\{B':B'\in \Psi(B, \beta)\} $
  2. $ C_{bal} < B_{bal} $
  3. $ C_{qrm} \cap B_{bot} \ne \emptyset $ 因为 $B2$ 和 假设中的 $B$ 表决是成功的,也就是 $ B_{qrm} \subseteq B_{vot} $
  4. $ MaxVote(C_{bal},C_{qrm},\beta)_{bal} \ge B_{bal} $ 因为 $C_{qrm}$ 和 $B$ 的投票者一定有交集
  5. $ MaxVote(C_{bal}, C_{qrm}, \beta)\in Votes(\beta)$
  6. $ MaxVote(C_{bal}, C_{qrm}, \beta)_{dec} = C_{dec} $
  7. $ MaxVote(C_{bal}, C_{qrm}, \beta)_{dec} \ne B_{dec} $
  8. $ MaxVote(C_{bal}, C_{qrm}, \beta)_{bal} > B_{bal} $
  9. $ MaxVote(C_{bal}, C_{qrm}, \beta) \in Votes(\Psi(B, \beta)) $
  10. $ MaxVote(C_{bal}, C_{qrm}, \beta)_{bal} < C_{bal} $
  11. 9, 10 和 1 矛盾。

定理 1

在满足 $B1(\beta)$,$B2(\beta)$,$B3(\beta)$ 的情况下, $$((B_{qrm} \subseteq B_{vot})\land(B'_{qrm}\subseteq B'_{vot})) \implies (B'_{dec} = B_{dec}) $$

定理 2

$$ \forall B\in\beta, b > B_{bal}, Q \cap B_{qrm} \ne \emptyset $$ 如果 $B1(\beta)$,$B2(\beta)$,$B3(\beta)$ 满足,那么存在一个 $ B', B'_{bal}=b, B'_{qrm}=B'_{vot}=Q $ 使得 $B1(\beta\cup\{B'\})$,$B2(\beta\cup\{B'\})$,$B3(\beta\cup\{B'\})$ 成立。

一个关于 private member function detect 的 SFINAE 模板

问题的开始

问题起源于,我要搞一个模板,来检查一个类,是不是有一个特定的回调接口 OnAlarm()。我显然希望在我的模板类里面,直接调用这个 OnAlarm 回调的。但是问题,就这么出现了。我需要一个模板,来检查一个传给构造函数的指针指向的类型,是不是有我需要的 OnAlarm 方法。如果没有的话,我需要使用另一套回调的机制。 问题就出在了这个检查上面。

问题的最初的样子

最开始的时候,我是写成了这个样子的。

template <typename T, typename = void>
struct HasAlarmCallback : std::false_type {};

template <typename T>
struct HasAlarmCallback<T, decltype(std::declval<T>().OnAlarm())>
    : std::true_type {};

这样看起来是没问题的(其实也是没问题的),但是我遇到了第一个问题。

class B {
  void OnAlarm() {}
};

这个模板在 T = B 的时候,会有编译错误,并不能成功的使用 SFINAE。错误的内容大概就是,这里用了一个 private 的函数,然后是不可见的。

曙光

(虽然也不知道为什么)

template <typename T, typename = void>
struct HasAlarmCallback : std::false_type {};

template <typename T>
struct HasAlarmCallback<T, decltype(static_cast<T*>(nullptr)->OnAlarm())>
    : std::true_type {};

struct A {
  void OnAlarm(){};
};

class B {
  void OnAlarm(){};
};

int main() {
  HasAlarmCallback<A> a;
  HasAlarmCallback<B> b;
}

在我这样写的时候,代码是可以完美通过编译,并且可以完美运行的。结果也是完美符合预期的。那我就会想呀,为啥我直接像下面样子写就不对了呢~

std::cout << HasAlarmCallback<A>::value << std::endl;
std::cout << HasAlarmCallback<B>::value << std::endl;

!!!这是我百思不得其解的要点!!! 在我这么写的时候,就不 work,会报像最开始那样的编译问题。

最后的方案

template<typename T, typename = void>
struct _HasAlarmCallback {
  static constexpr bool value = false;
};

template<typename T>
struct _HasAlarmCallback<T, decltype(static_cast<T *>(nullptr)->OnAlarm())> {
  static constexpr bool value = true;
};

template<typename T>
struct HasAlarmCallback {
 private:
  static constexpr _HasAlarmCallback<T> foo{};

 public:
  static constexpr bool value = _HasAlarmCallback<T>::value;
};

我最后发现,如果需要我构造一个实例才能解决这个问题的话,那我就构造一个。 嗯… 虽然… 不知道为啥… 反正是 work 了…

如果有人看到,然后知道为什么的话… 请告诉我!谢谢了!

User-defined conversion and Copy elision

问题的开始

问题的开始是同事聊到了我们笔试题的一个问题,是说下面这个代码其实在编译的时候是有问题的。

struct UserInfo {
  UserInfo(const std::string& name) : name_(name) {}

 private:
  std::string name_;
};

int main() {
  UserInfo u = "name";
}

最初的讨论和思考

显然在最开始的时候,我并没有发现这个代码的问题所在,并且被告知了在这段代码里面其实是有两个问题的。

在这个简单的例子里面,就涉及到了在规范里面两个很不容易注意到的行为,就像标题里聊的 UDC(user-defined conversion)copy-elision

关于隐式转换(implicit conversion)

main 函数里面唯一的语句,这首先是一个变量的声明和定义,同时还包括了这个变量的初始化(initialize)。在这个变量的初始化阶段,发生了几次类型转换,其中大部分都是隐式的(implicit conversion),并且调用到了不同的构造函数:

const char[5] =[implicit conversion(1)]=> std::string
              =[implicit conversion(2)]=> UserInfo
              =[copy/move(3)]=> UserInfo

第一次发生在字符串字面量(string literal)构造 std::string 的时候,显然这是一个隐式转换,因为并没有显式的调用 std::string 的构造函数,并且这个隐式转换显然是 user-defined 的。

第二次发生在 std::string 构造一个 UserInfo 的时候,这也是一个隐式转换,并且是 user-defined 的。

这两次隐式转换构成了一个隐式转换链(implicit-conversion sequence),问题就出在这个由两个 user-defined conversion 构成的隐式转换链上。在标准的 16.3.3.1 里讨论了有关于 implicit conversionuser-defined conversion 的部分,而在 15.3 里特别提到了:

At most one user-defined conversion (constructor or conversion functions) is implicitly applied to a single value.

在一个隐式转换序列里,只能存在最多一个用户定义的转换。这个条件在标准的隐藏的很深,我在通读标准的时候几次都错过了他们。(但是据说这个问题,曾经在邮件列表里有过蛮激烈的讨论的,但是可惜我那个时候还是个孩子hhh)

所以在这个问题里,发生 ill-formed 的第一个原因是,在一个 implicit conversion sequence 里面,存在多个 user-defined conversion。

关于复制消除(copy elision)

关于复制消除的部分,这里就要提到不同的两个版本,C++17 开始和 C++17 之前。

在 C++17 之前,并没有明确的提出在什么情况下,可以彻底进行复制消除(这里的彻底的指的是包括不进行是否有可用的 copy/move 构造函数的检查)。

所以在 C++17 之前,下面的这段代码是会有编译错误的:

struct Foo {
  Foo(int) {}
  Foo(Foo&&) = delete;
  Foo(const Foo&) = delete;
};

int main() {
  Foo a = 1;
}

可以考虑上面给出的上面那个问题的隐式转换链,这个首先出现的是 source type 的 target type 的不一致,所以出现了一次 user-defined 的 implicit conversion。从类型 int 得到了类型 Foo 的一个 prvalue(这里的 prvalue 很重要)。然后才是从一个 prvalue 构造一个类型 Foo 的对象。

其实我们显然可以知道,第二个过程是会被优化掉的,一般的编译器都会优化成原地构造的。但是标准在这个时候要求了,在这种时候,即使这部分的内容会优化,但是依旧要进行编译时的检查,检查 copy/move 构造函数是否可用,如果不可用,那这个代码依旧是 ill-formed。

但是事情在 C++17 中发成了一个很大的改变 11.6.4.3.9,在一个是 prvalue 的时候,这里会用 direct-initalize,而不是尝试使用 copy/move initialize。也就是说,上面例子的代码在 C++17 之后其实是可以通过编译的。

但是这里要注意,适用的规则是一个 prvalue 的对象,xrvalue 是不可以的。也就是说,下面这样的代码依旧是不能通过编译的:

struct Foo {
  Foo(int = 10) {}

  Foo(Foo&&) = delete;
  Foo(const Foo&) = delete;
};
struct Bar {
  operator Foo&& {
    return std::move(a);
  }
  
  Foo a;
};

int main() {
  Bar b;
  Foo a = b;
}

这里虽然做了一次隐式类型转换(从 BarFoo),但是得到的类型是一个 xrvalue,而 xrvalue 是不适合上面的拷贝消除规则的,所以还会尝试使用 copy/move 构造,得到 ill-formed 的结果。


文中提到的所有标准文档,都采用最新的 C++ 标准文档(ISO/IEC 14882 2017),除非特别指定此时讨论的C++版本。

VIM and Latex

起源

起源是在群里看到了有人分享的关于一个人用 vimlatex 的文章,但是它的做法是用了一个 vimtex 的独立插件。 我是个 language server 的狂热使用者,所以我就在找一个用 language server 的处理方案。回忆起来另一次在另一个群里看到的,一个叫做 texlab 的项目,就在 vim 里搞个配合。

vim 里的插件选择

vim 里的 language client 的实现用好几种:

用来用去还是 coc.nvim 在这里面不论是流畅度还是 feature 的丰富程度都是比较好的。所以我也一直在用。

Install

install coc.nvim:

call dein#add('neoclide/coc.nvim', {'build': 'yarn install'})

install texlab:

git clone https://github.com/latex-lsp/texlab
yarn install && yarn build

config

config in coc.nvim

"texlab": {
  "command": "node",
  "args": [
    "/path/to/texlab/dist/texlab.js", "--stdio"
  ],
  "filetypes": ["tex", "plaintex"],
  "trace.server": "verbose"
}

Compare Between CRTP and Virtual

我们平时都会使用虚函数来实现 C++ 里的运行时的多态,但是虚函数会带来很多性能上面的问题:

  1. 虚函数的调用需要额外的寻址
  2. 虚函数不能被 inline,当使用比较小的虚函数的时候会带来很严重的性能负担
  3. 需要在每个对象中维护一个额外的虚函数表

但是在有些情况下,我们就可以用一些静态的类型分发策略来带来一些性能上面的好处。

一个传统的例子

struct VirtualInterface {
  virtual void Skip(uint32_t steps) = 0;
};

struct VirtualImpl : public VirtualInterface {
  uint32_t index_;

  void Skip(uint32_t steps) override { index_ += steps; index_ %= INT_MAX; }
};

void VirtualRun(VirtualInterface* interface) {
  for (auto i = 0; i < N; i++) {
    for (auto j = 0; j < i; j++) {
      interface->Skip(j);
    }
  }
}

这里有一个很简单的例子,我们搞了一个简单的计数类来模拟这个过程。首先使用虚函数的方法去实现这个。在开了O2的情况下,运行了 3260628226 ns。

然后我们使用 CRTP 来实现:

template <typename Impl>
struct CrtpInterface {
  void Skip(uint32_t steps) { static_cast<Impl*>(this)->Skip(steps); }
};

struct CrtpImpl : public CrtpInterface<CrtpImpl> {
  void Skip(uint32_t steps) {
    index_ += steps;
    index_ %= INT_MAX;
  }

  uint32_t index_ = 0;
};

template <typename T>
void CrtpRun(CrtpInterface<T>* interface) {
  for (auto i = 0; i < N; i++) {
    for (auto j = 0; j < i; j++) {
      interface->Skip(j);
    }
  }
}

同样运行我们的代码, 29934437 ns。 显然在省去了查虚函数表,并且可以inline的情况下,程序有了更好的表现。

在具体的实现方式上,参考上面的实现就可以了…

Interface in C++

Interface In C++

问题提出

我记得我不止一次提到说,我更喜欢 golang 的泛型设计。一个优秀的泛型系统,我希望是来表示一个方法可以接受什么。应该是一个类似于 concept 的概念。我们都知道,在 C++ 里面,我们更多的使用虚函数来实现这个功能,就像下面这样:

struct IPerson {
  virtual std::string Name() = 0;
  virtual uint32_t Age() = 0;
};

我们搞了一个几个纯虚函数来表示一个接口类,然后我们都会搞一些类来继承这个类,就像下面这样:

struct Student : public IPerson {
  std::string Name() override;
  uint32_t Age() override;
};

那在使用的地方:

void Foo(IPerson*);

这已经是我们一般在写代码时候的常规做法了,但是在这样的情况下,我们要求了所有使用这个的地方,都只能使用指针或者引用。因为我们不能对一个对象来搞这些东西。

再回想一下,golang 的泛型的样子,我们有没有一个办法,可以搞一个类似于 interface 的东西来让一个对象也可以表示这些东西呢?

简单思考1

基于上面的问题,考虑这个问题的背后是表示的是个什么类型的多态问题。Ok,显然是个运行时多态。编译时多态的问题可以配合 template, constexpr 来解决。那么运行时多态在原本的 C++ 是通过虚函数来解决的。虚函数的实现,又是通过一个虚函数表来实现的。那么问题来了,我们可不可以自己来维护一个虚函数表来达到我们想要的效果呢? 上面我们需要的接口类,显然我们可以提炼出来一个这样的虚函数表:

struct vtable {
  std::string (*Name)(void*);
  uint32_t (*Age)(void*);
};

这个虚函数表表示了这个接口需要哪些接口,在这里使用 void* 来表示任意类型的指针。 那有了这个虚函数表之后,我们应该怎么使用这个呢?就像这个这样:

template<typename T>
vtable vtable_for = {
  [](void* p) {
    return static_cast<T*>(p)->Name();
  },
  [](void*) {
    return static_cast<T*>(p)->Age();
  },
};

这里用了 C++14 的新特性:变量模板,来构造了一个静态的全局变量,来表示对应的制定类型的虚函数表实现。 在有了上面两个东西的基础上,就得到了接口类的实现:

struct Person {
  template<typename T>
  Person(T t) : vtable_( &vtable_for<T> ), p(new T{t}) {}
 private:
  vtable* vtable_;
  void* p;
};

接下来,这个类就可以很棒了。你可以像下面这么定义:

std::vector<Person> persons;

persons.push_back(Student{});
persons.push_back(Teacher{});
...

用起来的时候,一切都看起来和 golang 的那个版本差不多了呢。


Reference:

  1. https://zh.wikipedia.org/wiki/C%2B%2B14#%E5%8F%98%E9%87%8F%E6%A8%A1%E6%9D%BF

Compile Time Reflection in C++11

故事背景

故事发生在遥远的我在使用C++来处理JSON和对象绑定的时候,我厌倦了写这样的代码:

class Foo {
  int bar1;
  int bar2;
  int bar3;
  std::string bar4;
  int bar5;
  std::string ToJsonString();
};
std::string Foo::ToJsonString() {
  Document doc;
  doc.SetObject();
  doc.AddMember("bar1", Value(bar1), doc.GetAllocator());
  doc.AddMember("bar2", Value(bar2), doc.GetAllocator());
  doc.AddMember("bar3", Value(bar3), doc.GetAllocator());
  doc.AddMember("bar4", Value(bar4), doc.GetAllocator());
  doc.AddMember("bar5", Value(bar5), doc.GetAllocator());
  ...
}

这样的代码又复杂又容易出错,所以我就在考虑一种可以自动的将这些东西都完成好的绑定方法。所以就有了文章写的内容。

预备部分

模板类

我们需要一个可以在编译时期被构造的字符串类,用于保存我们需要反射的类的类名和成员名。在C++17之后,我们可以使用标准库中提供的std::string_view来实现,但是在C++11中,我们没有这样的实现,就只能用constexpr的构造函数来实现一个我们自己的std::string_view类。 这部分在C++11中的实现可以参考我在另一篇文章中的实现。https://twistoy.com/post/compile-time-const-array 这里给出一个简单的实现:

class ConstString {
 public:
  template<uint32_t N>
  constexpr ConstString(const char (&arr)[N]) : begin_(arr), size_(N-1) {
    static_assert(N >= 1, "const string literal should not be empty");
  }

  constexpr ConstString(const char* buf, uint32_t len)
    : begin_(buf), size_(len) {}

  constexpr char operator[](uint32_t i) const {
    return begin_[RequiresInRange(i, size_)];
  }

  constexpr const char* Begin() const {
    return begin_;
  }

  constexpr const char* End() const {
    return begin_ + size_;
  }

  constexpr uint32_t Size() const {
    return size_;
  }

  constexpr ConstString SubString(int pos, int len) const {
    return RequiresInRange(pos, size_), RequiresInRange(pos + len, size_),
           ConstString(begin_ + pos, len);
  }

 private:
  const char* const begin_;
  uint32_t size_;
};

constexpr bool operator==(ConstString a, ConstString b) {
  return a.Size() != b.Size() ? false
       : StringEqual(a.Begin(), b.Begin(), a.Size());
}

这个实现提供了在字符串上的几个基本操作,后面的实现中可以根据自己的需要扩展。

宏(macro)

宏参数个数

我们都知道,在C++11中提供了变长参数模板,可以让我们接受任意个任意类型的参数:

template<typename... Args>
void fuck(Args... args);

还有技巧可以帮助我们写出类型处理正确的、零开销的完美转发;有扩展的用法sizeof...(Args)来帮助我们获得参数包中参数的个数。 但是,如果我们想得到一个宏的变长参数包中参数的个数呢?有什么宏展开的技巧可以帮助我们做到这一点呢。答案显然是有的,我们用两个宏来配合我们做到这一点:

#define __RSEQ_N() 5, 4, 3, 2, 1, 0
#define __ARG_N(_1, _2, _3, _4, _5, N, ...) N

上面的宏考虑其展开的过程:

__ARG_N(a, b, c, __RSEQ_N())  // 1:调用 
__ARG_N(a, b, c, 5, 4, 3, 2, 1, 0)  // 2:展开1

考虑展开后的形式:

   __ARG_N( a,  b,  c,  5,  4, 3, 2, 1, 0)
// __ARG_N(_1, _2, _3, _4, _5, N, ...) N

我们可以明显的得到__ARG_N这个宏在这种情况下展开的结果为3。我们再对这个宏进行简单的包装,就得到了一个易用的获得宏参数个数的宏。

#define __GET_ARG_COUNT_INNER(...) __ARG_N(__VA_ARGS__)
#define __GET_ARG_COUNT(...) __GET_ARG_COUNT_INNER(__VA_ARGS__, __RSEQ_N())

对这个宏进行一些简单的测试:

assert(__GET_ARG_COUNT(a,), 1);
assert(__GET_ARG_COUNT(a, b), 2);
assert(__GET_ARG_COUNT(a, b, c), 3);
assert(__GET_ARG_COUNT(a, b, c, d), 4);
assert(__GET_ARG_COUNT(a, b, c, d, e), 5);

通过扩展宏__RSEQ_N()和宏__ARG_N来扩展其所支持的参数个数。简单的增加宏里的参数个数和数值即可。

构造字符串序列

我们都知道,在宏里面可以通过使用#来将一个宏参数用引号来括起来,形成字符串的形式。那么利用这个特性,我们就可以得到一个参数的字符串形式和我们上面完成的常量字符串对象。

#define __ADD_VIEW(str) ConstString(#str)

并且通过宏的递归来实现生成一个常量字符串对象的序列:

#define __CONST_STR_1(str, ...) __ADD_VIEW(str)
#define __CONST_STR_2(str, ...) __ADD_VIEW(str), __CONST_STR_1(__VA_ARGS__)
#define __CONST_STR_3(str, ...) __ADD_VIEW(str), __CONST_STR_2(__VA_ARGS__)
...

以此类推可以得到你想要的个数的形式。【如果你在使用VIM的话,这里的代码可以简单的使用VIM的宏功能来完成。(使用q来录制一个宏,C-A来自增当前位置的数字)。VIM最棒啦。我就是这么完成的UoU】 上面的宏,将被展开成这样:

// __CONST_STR_3(a, b, c)
ConstString("a"), ConstString("b"), ConstString("c")

将参数序列转成字符串序列

先搞一个简单的宏把两个名字连起来成为一个名字:

#define __MACRO_CONCAT(m1, m2) __MACRO_CONCAT_IMPL(m1, m2)
#define __MACRO_CONCAT_IMPL(m1, m2) m1##_##m2

然后结合我们上面完成的两个宏,就可以啦:

#define __MAKE_STR_LIST(...) __MACRO_CONCAT(__CONST_STR, __GET_ARG_COUNT(__VA_ARGS__))(__VA_ARGS)

__CONST_STR这个名字和参数个数连起来,就是其在我们上面实现的第二个宏的名字,比如:__CONST_STR_1__CONST_STR_2等等。然后再调用这个宏即可。

将一个操作写入所有的宏参数

在这里使用类似字符串转换那里的技巧,可以很容易的得到一个宏:

#define __MAKE_ARG_LIST_1(op, arg, ...) op(arg)
#define __MAKE_ARG_LIST_2(op, arg, ...) op(arg), __MAKE_ARG_LIST_1(op, __VA_ARGS__)
...

上面的宏被使用时,将这样被展开:

#define __FIELD(t) t
// __MAKE_ARG_LIST_3(&Name::__FIELD, a, b, c)
&Name::a, &Name::b, &Name::c

使用一个类来保存这些宏信息

在这里我希望构造一个类似这样的结构体来保存一个类的成员的宏信息:

struct Name {
  char* rname;
};

struct __reflect_struct_Name {
  using size_type = std::integral_constant<size_t, 1>;
  constexpr static ConstString Name() {
    return ConstString("Name");
  }
  constexpr static size_t Value() {
    return size_type::value;
  }
  constexpr static std::array<ConstString, size_type::value> MembersName() {
    return std::array<ConstString, 1>{{ ConstString("rname") }};
  }
  constexpr decltype(std::make_tuple(&Name::rname)) static MembersPointer() {
    return std::make_tuple(&Name::rname);
  }
};

观察我们上面的几个宏,可以显然得到这样的一种写法:

#define __MAKE_REFLECT_CLASS(StructName, ...) \
  struct __reflect_struct_##StructName { \
    using size_type = std::integral_constant<size_t, __GET_ARG_COUNT(__VA_ARGS__)>; \
    constexpr static ConstString Name() { \
      return ConstString(#StructName); \
    } \
    constexpr static size_t Value() { \
      return size_type::value; \
    } \
    constexpr static std::array<ConstString, size_type::value> MembersName() { \
      return std::array<ConstString, size_type::value>{{ \
        __MACRO_CONCAT(__CONST_STR, __GET_ARG_COUNT(__VA_ARGS__))(__VA_ARGS__) \
      }}; \
    } \
    constexpr static decltype(std::make_tuple()) static MembersPointer() {
      return std::make_tuple( \
        __MACRO_CONCAT(__MAKE_ARG_LIST, &StructName::__FIELD, __VA_ARGS__) \
      ); \
    } \
  };

上面的这个宏可以帮助我们构造一个结构体,在结构体里的分别用Name()方法来返回其保存的元信息类型名,用MembersName()返回保存类型的所有成员名,用MembersPointer()返回保存类型的所有成员指针。 然后利用函数的重载来返回这个结构体:

__reflect_struct_##StructName __reflect_structs(StructName const&) { \
  return __reflect_struct##StructName{}; \
}

使用模板函数来获取这些元信息

template<typename T>
constexpr const ConstString GetName() {
  return decltype(__reflect_structs(std::declval<T>()))::Name();
}

template<typename T>
constexpr const ConstString GetName(size_t i) {
  return decltype(__reflect_structs(std::declval<T>)))::MembersName()[i];
}

后面的思想基本就都和这个类似,利用模板和函数重载来获取这些类型的元信息。

结合其他宏使用

在使用这种操作的时候,我们需要使用一个宏来构造我们上面提到的所有元信息,这个应该是一个没有办法的事情了。为了这个功能这些多出来的代码,我也是可以接受的。 当然如果这个类型本来就是使用宏构造出来的话,就可以把这两个宏很舒服的结合在一起啦~所以我也推荐你这么用哦。

C++11内存模型

Introduction

// cpp concurrency in action 里的例子

void undefined_behaviour_with_double_checked_locking() {
  if (!resource_ptr) { // 1
    std::lock_guard<std::mutex> lk(resource_mutex);
    if (!resource_ptr) { // 2
      resource_ptr.reset(new some_resource); // 3
    }
  }
  resource_ptr->do_something(); // 4
}

C++ Concurrency in Action 中提到过一段很有意思的代码,这段代码存在潜在的条件竞争。未被锁保护的操作①,没有与另一个线程中被锁保护了的操作③进行同步,在这样的情况下就有可能产生条件竞争。这个操作不光会覆盖指针本身,还有会影响到其指向的对象。所以在后面的操作④就有可能会导致不正确的结果。

Out-of-order process

让我们从一个稍微简单一点的例子聊起。考虑现在我们的程序有两个线程,他们持有共同的变量 ab,其中 ab 的初始值都是0,两个线程分别执行了这样的代码:

线程1

b = 1;  // 1
a = 1;   // 2

线程2:

int a = 0, b = 0;
while (a == 0);
assert(b == 1);  // 3

在这个例子里面,我们可以保证每次在位置①的断言都可以成功么? 显然我们没有办法预期位置③的断言每次都成功,因为我们没法保证操作①每次都在操作②之前完成。 这里有两个主要的原因:

  1. 编译器可能会对没有依赖的语句进行优化,重排他们的执行顺序
  2. CPU在执行字节码的时候,会对没有依赖关系的语句重排执行顺序 显然在上面的例子中,操作②就有可能被重排到操作①之前,在这种情况下我们在线程2就没法观测到正确的结果,从而导致位置③的断言失败。 考虑这样的一种情况:
L1: LDR R1, [R0]
L2: ADD R2, R1, R1
L3: ADD R4, R3, R3

在按序执行的情况下,我们预期的顺序应该是: L1->L2->L3

然而我们可以很容易的发现,语句3 和语句1 是没有依赖关系的,而语句2可以会依赖于语句1的执行结果,所以CPU经过乱序,并且可能将这三个操作发送到两个不同的CPU单元上,并且得到另一种执行顺序: L1->L2 L3

再就是现在的多核CPU带来的可能缓存不一致的问题,在一个CPU核心上后写入的数据在其他的地方未必是后写入的。所以就会出现我们最上面的例子中,我们尝试使用一个标记位用来标记其他的数据是否已经准备好了,然后我们可能会在另一个核心上来判断这个标志位来决定所需要的数据是否已经准备就位。这样的操作的风险就在于,可能在被乱序执行的情况下,标志位被先写入了,然后才开始准备数据,这样在另一个核心观测就会得到不一样的、错误的结果。所以我们就必须在我们的代码中做出一些保护机制。

在C++11之前,我们有一种普遍的用法,就是内存屏障。而在C++11中,我们有了另一个选择,就是atomic

atomic in C++11

atomic 是在 C++11 中被加入了标准库的,这个库提供了针对于布尔、整数和指针类型的原子操作。原子操作意味着不可分的最小执行单位,一个原子操作要么成功,要么失败,是不会被线程的切换多打断的执行片段。对于在不同的线程上访问原子类型上操作是well-defined的,是不具有数据竞争的。

模板类 atomic

模板类 atomic 是整个库的核心,标准库中提供了针对布尔类型、整数类型和指针类型的特化,除此之外的情况请保证用于特化模板的类型时一个平凡的(trivial)类型。 在原子类上,显然有两个基础操作:

void store(T, memory_order = memory_order_seq_cst) volatile noexcept;
void store(T, memory_order = memory_order_seq_cst) noexcept;
T load(memory_order = memory_order_seq_cst) const volatile noexcept;
T load(memory_order = memory_order_seq_cst) const noexcept;

用于更新原子对象当前值的 store 方法和读取原子对象当前值的 load 方法。对于 store 方法,指定的内存顺序必须是 std::memory_order_relaxedstd::memory_order_releasestd::memory_order_seq_cst其中的一个,指定为其他的内存顺序都是未定义行为;对于load方法,指定的内存顺序必须是 std::memory_order_relaxedstd::memory_order_consumestd::memory_order_acquirestd::memory_order_seq_cst其中的一个,其他的内存顺序同样都是未定义行为。 还有一个操作,原子的以新值替换旧值并返回旧值。

T exchange( T desired, std::memory_order order = std::memory_order_seq_cst ) noexcept;
T exchange( T desired, std::memory_order order = std::memory_order_seq_cst ) volatile noexcept;

这是一个读-修改-写的操作,类似的还有test-and-setfetch-and-addcompare-and-swap

Memory Model

C++中提供了六种内存模型,其中的一些通常会成对出现。

memory_order_relaxed:对操作的上下文没有要求,仅要求当前操作的原子性 memory_order_consume:当前的加载操作,在其影响的内存位置上进行 消费:当前线程中依赖于该值读或写的操作不能被重排到该操作之前;在其他线程中,该值所依赖的变量的写入都可以被当前线程正确的观测到 memory_order_acquire:当前的加载操作,在其影响的内存位置上进行 获取:当前线程的读或写都不能重排到该操作之前;在其他线程中的所有位于该操作之前的读或写都可以被当前线程正确的观测到 memory_order_release:当前的存储操作,在其影响的内存位置上进行 释放:当前线程的读或写都不能重排到该操作之前;在其他线程中的所有位于该操作之前的写都可以被当前线程正确的观测到 memory_order_acq_rel:当前的加载或是存储操作,既在其影响的内存位置上进行 获取 也进行 释放 memory_order_seq_cst:当前的加载操作在其影响的内存位置进行 获取,存储操作进行 释放,读-修改-写操作进行 获取释放

memory_order_relaxed

在这个内存模型中,不要求操作在访问同样内存时候的操作顺序,只保证了原子性和修改的一致性。考虑下面的例子,对于初值为0的两个原子量xy

// thread 1
r1 = y.load(memory_order_relaxed); // 1
x.store(r1, memory_order_relaxed); // 2
// thread 2
r2 = x.load(memory_order_relaxed); // 3 
y.store(42, memory_order_relaxed); // 4

这里是允许出现xy同时等于42的情况,因为我们即使知道操作①先于操作②,操作③先于操作④;但是我们没有约束操作④不能优先出现于操作①。所以我们可以观测到任何可能的结果。

memory_order_acquire && memory_order_consume

在这个顺序模型中,存储操作 释放 ;加载操作 消费 。如果线程1中的存储操作使用了 释放 标记;而线程2中的加载操作使用了 消费 标记。那么在线程1中的存储操作所依赖的所有内存写入都对在线程2中都可以被正确的观测到。这种同步仅仅建立在存储和加载的两个线程之间,对其他线程无效。

可以使用std::kill_dependency来消除从带有消费标记的加载操作开始的依赖树,不会讲依赖带入返回值。这个操作可以避免依赖链在离开函数作用域时,不必要的memory_order_acquire栅栏。

memory_order_acquire && memory_order_release

在这个顺序模型中,存储操作 释放;加载操作 获取。如果线程1中的存储操作使用了 释放 标记;而线程2中的加载操作使用了 获取 标记。那么在线程1中,所以先于存储操作的内存写入在线程2中都可以被正确的观测到。这种同步仅建立在存储和加载的两个线程之间,对其他的线程无效。 所以考虑最开始的代码,如果我们将变量a改为atomic<int>,并且使用 release-acquire 的内存模型,就可以保证断言③的绝对正确。

atomic<int> a;
int b;

线程1

b = 1;  // 1
a.store(1, std::memory_order_release);  // 2

线程2:

int a = 0, b = 0;
while (a.load(std::memory_order_acquire) == 0);
assert(b == 1);  // 3

memory_order_seq_cst

除了在进行 释放获取 操作外,还会的所有持有此标记的操作建立一个单独全序(single total modification order)。这个表示每个标记了memory_order_seq_cst的操作,都可以观测到在其之前发生的标记有memory_order_seq_cst;并且可能观测到在其之前的,未标记为memory_order_seq_cst的操作。

#include <thread>
#include <atomic>
#include <cassert>
 
std::atomic<bool> x = {false};
std::atomic<bool> y = {false};
std::atomic<int> z = {0};
 
void write_x() {
    x.store(true, std::memory_order_seq_cst);
}
 
void write_y() {
    y.store(true, std::memory_order_seq_cst);
}
 
void read_x_then_y() {
    while (!x.load(std::memory_order_seq_cst));
    if (y.load(std::memory_order_seq_cst)) {
        ++z;
    }
}
 
void read_y_then_x() {
    while (!y.load(std::memory_order_seq_cst));
    if (x.load(std::memory_order_seq_cst)) {
        ++z;
    }
}
 
int main(){
    std::thread a(write_x);
    std::thread b(write_y);
    std::thread c(read_x_then_y);
    std::thread d(read_y_then_x);
    a.join(); b.join(); c.join(); d.join();
    assert(z.load() != 0);  // 1
}

上面例子中操作①处的断言绝不可能失败。

使用此序列顺序在多核模式下要求完全内存栅栏的CPU指令,这可能会成为性能的瓶颈,因为它将其受影响的内存的影响传播到了每个核心。