优化思维【3】消除没必要步骤

故事

四月底给 EOSIO / eos 提了一个优化 MongoDB 插件性能的 PR,被连续感谢好几个 Release

分析

原先的流程:fc::variant -> JSON string -> BSON,实现起来很简单,因为 JSON 是很常见的,fc::variant 和 BSON 都有到 JSON 的转化,所以实现代码很简单,一行两个函数。

但数据大时,性能问题就暴露了,这个过程先把 fc::variant 对象序列化为 JSON 字符串,然后反序列化到 BSON 对象。两步都是 CPU 密集型操作,由于 nodeos 及其插件暂时对多核支持不好,导致单核跑爆。

两个过程都要用递归实现,调用栈可能很深。调用函数可能有入栈出栈的消耗,有一种优化思路正是用 inline 减少函数的频繁调用

回归到本质,fc::variant 和 BSON 都是对象,应该直接转化才对。只是实现起来就不是一行能搞定的。先挑简单的方式实现,后期再优化,这是一种挺常规的做法。

优化思维【2】有符号和无符号的本质区别

做题

以下代码打印什么?

1
2
3
4
5
6
7
auto count = sizeof (int);
if (count > -1) {
std::cout << "> -1";
}
else {
std::cout << "<= -1";
}

答案是:<= -1,因为 sizeof (int) 是无符号的,把 auto 改为 int 则结果是 > -1

本质论

当我们声明 unsigned/signed int count 时,unsigned/signed 是变量 count 的使用属性,int 是其容量属性。

所谓使用属性,就是当它存在寄存器或内存时,不管是 unsigned 还是 signed 本质是一样的,但对它进行访问时,就区别对待。

比如对 count 进行加法,unsigned 时用的是 ADD 指令,signed 时用的是 ADC 指令,其余减乘除也都类似地使用不同指令。

再来一个问题:把一个变量保存到文件里,再读出来,怎么知道它是有符号还是无符号?

答案是:如果你不在序列化时考虑符号,则反序列化时,无法知道原来的符号,把它赋值给什么类型的变量它就变成什么类型。

这也是 JSON 文本转对象后,要自己选择数据类型的原因,因为 JSON 文本没表示符号的语法。

结论

优化思路:理解本质,就能了解限制和优化方向。

修复 Clang 编译错误:error: expected unqualified-id

问题

今天编译 EOSIO/eos 出现一些 error: expected unqualified-id

环境

  • 操作系统:macOS Mojave
  • 编译器:AppleClang 10.0.1.10010046
  • SDK:MacOSX10.14.sdk
  • Boost:1.69.0(1.67.0 也有问题,干脆用这个版本)

验证问题

1
2
3
4
5
6
7
8
9
#include <signal.h>

int main() {
::sigset_t sigset;

::sigemptyset(&sigset);
::sigaddset(&sigset, SIGCHLD);
return 0;
}

编译输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Scanning dependencies of target signal
[ 50%] Building CXX object CMakeFiles/signal.dir/signal.cpp.o
/Users/umu/umutech/macos-cpp/source/study/posix/signal/signal.cpp:6:5: error: expected unqualified-id
::sigemptyset(&sigset);
^
/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.14.sdk/usr/include/signal.h:125:26: note: expanded from macro 'sigemptyset'
#define sigemptyset(set) (*(set) = 0, 0)
^
/Users/umu/umutech/macos-cpp/source/study/posix/signal/signal.cpp:7:5: error: expected unqualified-id
::sigaddset(&sigset, SIGCHLD);
^
/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.14.sdk/usr/include/signal.h:122:31: note: expanded from macro 'sigaddset'
#define sigaddset(set, signo) (*(set) |= __sigbits(signo), 0)
^
2 errors generated.
make[2]: *** [CMakeFiles/signal.dir/signal.cpp.o] Error 1
make[1]: *** [CMakeFiles/signal.dir/all] Error 2
make: *** [all] Error 2

解决

去掉 sigemptysetsigaddset 前面的 :: 即可。因为他们是宏,宏都是全局的,用 :: 修饰反而错了,严格!

Boost 开发分支上已经修复:

https://github.com/boostorg/process/blob/develop/include/boost/process/detail/posix/wait_for_exit.hpp#L60

https://github.com/boostorg/process/blob/develop/include/boost/process/detail/posix/wait_group.hpp#L65

《Effective C++》读书笔记

第一章 让自己习惯 C++

1. 视 C++ 为一个语言联邦

C++ 是个多重范型编程语言:面向过程、面向对象、函数式、泛型、原编程式,所以他的规约很多,记住四个次语言可以帮助了解 C++:C、Object-Oriented C++、Template C++、STL。

2. 尽量以 const、enum、inline 替换 #define

他们的根本差别是:前三者是编译器处理的,最后者是预处理器处理的。enum 比 const 更像 #define,比如说 const 定义通常可以求地址或引用,而 enum 不行。

inline 函数比宏多了类型安全和可预料性,一个例子是将 i++ 或 ++i 当参数传给宏时,可能导致 ++ 了多次,而传给 inline 函数则不会。

3. 尽可能使用 const

const 可以帮助编译器侦测错误的用法。例如,令函数返回一个常量值,往往可降低因调用者错误而造成的意外,而又不至于放弃安全性和高效性。比如当比较语句少写了一个 = 时:

1
2
// 本意是 ==,结果导致在 a * b 的临时变量上调用 operator=
if (a * b = c) ...

如果 operator= 返回值不是 const 会导致以上错误代码编译通过!

bitwise constness 认为 const 成员函数不可以更改对象内任何 non-static 成员变量,logical constness 主张在调用者侦测不出的前提下可以修改对象内某些 bits,可以利用 mutable 释放掉 non-static 成员变量的 bitwise constness 约束。

在 const 和 non-const 成员函数中避免重复的做法是:让 non-const 成员函数调用 const 成员函数,而不要反过来。

4. 确定对象被使用前已被初始化

为内置型对象进行手工初始化,因为 C++ 不保证初始化它们。

构造函数最好使用成员初值列,而不是赋值操作,排列顺序最好和声明次序想同。

为避免跨编译单元的初始化次序问题,用 local static 对象代替 non-local static 对象,参考 Singleton 模式常见实现。

1
2
3
4
5
XClass& GetInstance()
{

static XClass instance;
return instance;
}

第二章 构造/析构/赋值运算

5. 了解 C++ 默默编写并调用哪些函数

编译器可以隐式为类创建:默认构造函数、复制构造函数、赋值构造函数、析构函数。

6. 若不想使用编译器自动产生的函数,就应该明确拒绝

拒绝的普遍方法是:把函数设为 private,只有声明没有实现。但 member 函数和 friend 函数还是可以调用 private 函数,由于没有实现,会在连接期报错,不利排插,将错误移至编译期的方法是:private 继承 Uncopyable 类,Boost 也有个类,名为 noncopyable。

更新式的做法是把函数声明为 = delete。

7. 为多态基类声明 virtual 析构函数

任何类只要带有 virtual 函数,都几乎确定应该有一个 virtual 析构函数。但有 virtual 函数会降低调用效率和可优化性,所以能不用则不用,比如说,某个类没有考虑作为基类(base class)被继承,则没有必要有 virtual 析构函数,STL 的容器大多如此。

8. 别让异常逃离析构函数

如果一个被析构函数调用的函数可能抛出异常,析构函数应该捕捉任何异常,然后吞下他们或者结束程序。

如果客户需要对某个函数运行期间抛出的异常做出反应,那么类应该提供一个普通函数执行该操作,而非在析构函数中。

9. 绝不在构造和析构过程中调用 virtual 函数

因为这类调用从不降至派生类(derived class),它将调用本层的函数。

10. 令 operator= 返回一个 reference to *this

这样才能支持连锁赋值,a = b = c = d。

11. 在 operator= 中处理“自我赋值”

方法有:比较来源和目标对象的地址、精心周到的语句顺序、copy-and-swap。要考虑自我赋值的概率,如果很小,则比较地址的方式可能并不好,因为无视它效率更高。

12. 复制对象时勿忘其每一个成分

复制函数应该保证复制“对象内的所有成员变量”及“所有基类成分”。当你编写一个复制函数,请确保(1)复制所有 local 成员变量,(2)调用所有基类内的适当的复制函数。

不要尝试以某个复制函数实现另一个复制函数。应该将共同机能放进第三个函数中,并由两个复制函数共同调用。

第三章 资源管理

13. 以对象管理资源

获得资源后立刻放进对象(managing object)内。“以对象管理资源”又称“资源取得时机就是初始化时机”(Resource Acquisition Is Initialization; RAII)

管理对象(managing object)运用析构函数确保资源被释放。

为防止资源泄漏,请使用 RAII 对象,它们在构造函数中获得资源并在析构函数中释放资源。

常被使用的 RAII class 是 std::shared_ptr,它是“引用计数器型智能指针”(Reference-counting smart pointer; RCSP),它无法打破环形引用(cycles of reference)。

不要用智能指针管理动态分配的数组,因为会导致错误形式的释放。参考《[C++ 学习笔记 1] delete 和 delete [] 的本质区别》。

14. 在资源管理类中小心 coping 行为

复制 RAII 对象必须一并复制它管理的资源,常见的 RAII class copying 行为是:

(1)禁止复制;

(2)对底层资源祭出“引用计数法”(reference-count);

(3)复制底部资源;

(4)转移底部资源的拥有权。

15. 在资源管理类中提供对原始资源的访问

APIs 往往要求访问原始资源(raw resource),所以每一个 RAII class 应该提供一个“取得其所管理之资源”的方法,比如 .get()。

对原始资源的访问可能经由显式转换或隐式转换。一般而言,显式转换比较安全,但隐式转换对客户比较方便。

16. 成对使用 new 和 delete 时要采取相同形式

如果你在 new 表达式中使用 [],必须在相应的 delete 表达式中也使用 []。如果你在 new 表达式中不使用 [],一定不要在相应的 delete 表达式中使用 []。参考《[C++ 学习笔记 1] delete 和 delete [] 的本质区别》。

17. 以独立语句将 newed 对象置入智能指针

以独立语句将 newed 对象存储于(置入)智能指针内。如果不这么做,一旦异常被抛出,有可能导致难以察觉的资源泄漏。

1
2
3
4
5
6
7
// 编译器可能为了产生更高效代码,而弹性地改变三个元语句的执行顺序
// 如果 priority() 抛出异常,可能导致 new Widget 返回的指针遗失
processWidget(std::shared_ptr<Widget>(new Widget), priority());

// 以下独立语句可行,因为编译器对“跨越语句的各项操作”没有重新排序的自由。
std::shared_ptr<Widget> pw(new Widget);
processWidget(pw, priority());

第四章 设计与声明

18. 让接口容易被正确使用,不易被误用

“促进正确使用”的办法包括接口的一致性,以及与内置类型的行为兼容。一致性的例子:STL 容器都有 size 成员函数。不一致性对开发人员造成的心理负担,没有任何一个 IDE 可以完全抹除。

“阻止误用”的办法包括建立新类型、限制类型上的操作,束缚对象值,以及消除客户的资源管理责任。

std::shared_ptr 使用每个指针专属的删除器,消除“cross-DLL problem”;它还支持定制删除器,可被用来自动解除互斥锁(mutexes,见条款 14)。

19. 设计 class 犹如设计 type

Class 设计就是 type 的设计,在定义一个新 type 之前,要考虑以下主题:

(1)新 type 的对象应该如何被创建和销毁?

(2)对象的初始化和赋值该有什么差别?

(3)新 type 的对象如果被以值传递(pass by value),意味着什么?

(4)什么的新 type 的合法值?setter 函数要检查错误。

(5)新 type 需要配合某个继承图系(inheritance graph)吗?这影响函数——尤其是析构函数,是否为 virtual(见条款 7)。

(6)新 type 需要什么样的转换?如果希望 T1 被隐式转换为 T2,必须在 class T1 内写一个类型转换函数(operator T2)或在 class T2 内写一个可被单一实参调用(non-explicit-one-argument)的构造函数。如果只允许 explicit 构造函数存在,就得写出专门负责转换的函数,且不得为类型转换操作符(type conversion perators)或 non-explicit-one-argument 构造函数。(条款 15 有隐式和显式转换函数的范例,https://my.oschina.net/umu618/blog/839649

(7)什么样的操作符和函数对此新 type 而言是合理的?这决定你的 class 有哪些函数,其中哪些是 member 函数,哪些则否。(参考条款 23, 24, 26)

(8)什么样的标准函数应该驳回?声明为 private。(见条款 6

(9)谁该取用新 type 的成员?这个问题帮你决定成员的可见性(public、protected、private)。也帮你决定哪个 classes 和/或 functions 应该是 friends,以及将它们嵌套于另一个之内是否合理。

(10)什么是新 type 的未声明接口(undeclared interface)?它对效率、异常安全性(见条款 29)以及资源运用(例如多任务锁定和动态内存)提供何种保证?你在这些方面提供的保证,将为你的 class 实现代码加上相应的约束条件。

(11)新 type 有多么一般化?new class or new class template?

(12)真的需要一个新 type 吗?如果只是定义新的子类(derived class)以便为既有 class 添加机能,那么也许单纯定义一或多个 non-member 函数或

20. 宁以 pass-by-reference-to-const 替换 pass-by-value

尽量以 pass-by-reference-to-const 替换 pass-by-value。前者通常比较高效,并可避免切割问题(slicing problem,即派生类被转化成基类时丢失派生类特有的成分)。

以上规则并不适用于内置类型,以及 STL 的迭代器和函数对象。对它们而言,pass-by-value 往往比较适当。

21. 必须返回对象时,别妄想返回其 reference

不要返回 pointer 或 reference 指向一个 local stack 对象,因为离开作用域即被销毁。

不要返回 reference 指向一个 heap-allocated 对象,因为无法保证配套 delete。

不要返回 pointer 或 reference 指向一个 local static 对象而有可能同时需要多个这样的对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>

#define _WINSOCK_DEPRECATED_NO_WARNINGS // to use inet_ntoa
#include <winsock2.h>

#pragma comment(lib, "ws2_32.lib")

int main()
{

in_addr a1 = {1, 2, 3, 4};
in_addr a2 = {5, 6, 7, 8};
printf_s("You think it's: %s, ", inet_ntoa(a1));
printf_s("%s\n", inet_ntoa(a2));
printf_s("But in fact it's: %s, %s\n", inet_ntoa(a1), inet_ntoa(a2));
return 0;
}

以上代码输出为:

You think it’s: 1.2.3.4, 5.6.7.8
But in fact it’s: 1.2.3.4, 1.2.3.4

22. 将成员变量声明为 private

切记将成员变量声明为 private。这可赋予客户访问数据的一致性、可细微划分访问控制、允诺约束条件获得保证,并提供 class 作者以充分的实现弹性。

protected 并不比 public 更具封装型。

23. 宁以 non-member、non-friend 替换 member 函数

宁可拿 non-member non-friend 函数替换 member 函数。这样做可以增加封装型、包裹弹性(packaging flexibility)和技能扩充性。

24. 若所有参数皆需类型转换,请为此采用 non-member 函数

member 函数的反面是 non-member 函数,而不是 friend 函数。

设计 operator * 时,要能支持乘法交换律。

如果你需要为某个函数的所有参数(包括 this 指针所指的那个隐喻参数)进行类型转换,那么这个函数必须是个 non-member。从 Object-Oriented C++ 跨进 Template C++ 时,会有新争议和解法,参考条款 46。

25. 考虑写出一个不抛异常的 swap 函数

通常我们不能改变 std 命名空间内的任何东西,但可以为 temlates 制造特化版本。

C++ 只允许对 class templates 偏特化(partially specialize),而对 function templates 则不许。

当 std::swap 对你的类型效率不高时,提供一个 swap 成员函数,并确定这个函数不抛出异常。因为成员 swap 的一个最好应用是帮助 classes 和 class templates 提供强烈的异常安全性(exception-safety)保障。条款 29 细说。

如果你提供了一个 member swap,也该提供一个 non-member swap 用来调用前者。对于 classes(而非 templates),也请特化 std::swap。

调用 swap 时应针对 std::swap 使用 using 声明式,然后调用 swap 并不带任何“命名空间资格修饰”。

为“用户定义类型”进行 std templates 全特化是好的,但千万不要尝试在 std 内加入某些对 std 而言全新的东西。

第五章 实现

26. 尽可能延后变量定义式的出现时间

太早出现,可能因为下面出现异常,导致构造白白浪费。

延后可以增加程序的清晰度、改善效率。

27. 尽量少做转型动作

dynamic_casts 有性能代价,应该尽量避免。绝对要避免“连串动态转型”(cascading dynamic casts)。

如果转型是必要的,试着将它隐藏于某个函数。客户可以条用该函数,而不需要讲转型放进他们的代码内。

宁可使用 C++-style 转型,不要使用旧式转型。前者很容易辨识出来,而且有分门别类的职掌。

28. 避免返回 handles 指向对象内部成分

避免返回 handles(包括 reference、指针、迭代器)指向对象内部,可以增加封装型,帮助 const 成员函数的行为像个 const,将发生“虚吊号码牌”(dangling handles)的可能性降至最低。

反之,传出去的 handles 可能让你暴露在“handles ”的风险下。

29. 为“异常安全”而努力是值得的

当异常被抛出时,异常安全的函数会:(1)不泄漏任何资源;(2)不允许数据败坏。

异常安全函数(Exception-safe functions)提供这三个保证之一:(1)基本承诺,如果异常抛出,程序内的任何事物仍然保持在有效状态下。(2)强烈保证,如果异常抛出,程序状态不改变。(3)不抛掷(nothrow)保证,承诺绝不抛出异常。

“强烈保证”往往能够以 copy-and-swap 实现出来,但“强烈保证”并非对所有函数都可以实现或具备现实意义。

木桶原理:函数提供的“异常安全保证”通常最高只等于其所调用的各个函数的“异常安全保证”中的最弱者。

30. 透彻了解 inlining 的里里外外

将大多数 inlining 限制在小型、被频繁调用的函数身上。这可使日后的调试过程和二进制升级(binary upgradability)更容易,也可使潜在的代码膨胀问题最小化,使程序的速度提升机会最大化。

定义于 class 内的函数都隐性成为 inline,包括像 operator* 这样的 friend 函数。

不要只因为 function templates 出现在头文件,就将它们声明为 inline。

所有对 virtual 函数的调用(除非是最平淡无奇的)都会使 inlining 落空。

编译器通常不对“通过函数指针而进行的调用”实施 inlining,这意味着对 inline 函数的调用最终是否 inlined 由编译器决定。

构造函数和析构函数往往是 inlining 的糟糕候选,因为他们隐含一些由编译器产生的代码。

inline 函数的风险:它们无法随着程序库的升级而升级,必须重新编译。

31. 将文件间的编译依存关系降至最低

支持“编译依存性最小化”的一般构想是:相依于声明式,不要相依于定义式。基于此构想的两个手段是 Handle classes 和 Interface classes。

程序库头文件应该以“完全且仅有声明式”(full and declaration-only forms)的形式存在。这种做法适用于 templates。

(1)如果使用 object references 或 object pointers 可以完成任务,就不要使用 object。

(2)如果可以,尽量以 class 声明式替换 class 定义式。

(3)为声明式和定义式提供不同的头文件。

Java 和 .NET 都不允许在 Interfaces 内实现成员变量或成员函数,但 C++ 可以。

Handle classes 和 Interface classes 有微小的性能损失,但为了降低 classes 之间的耦合性是值得的。如果性能比耦合性重要,才用具象类(concrete )替换它们。

第六章 继承与面向对象设计

32. 确定你的 public 继承塑模出 is-a 关系

“public 继承”意味 is-a。适用于 base classes 身上的每一件事一定也适用于 derived classes 身上,因为每一个 derived classes 对象也都是一个 base class 对象。

classes 之间的关系除了 is-a 之外,还有 has-a(有一个)和 is-implemented-in-terms-of(根据某物实现出)两种常见的关系。

33. 避免遮掩继承而来的名称

derived classes 内的名称会掩盖 base classes 内的名称。在 public 继承下从来没有人希望如此。

为了让被掩盖的名称再见天日,可使用 using 声明式或转交函数(forwarding function)。

34. 区分接口继承和实现继承

接口继承和实现继承不同。在 public 继承之下,derived classes 总是继承 base class 的接口。

成员函数的接口总是会被继承。

pure virtual 函数有两个最突出的特征:他们必须被任何“继承了它们”的具象 class 重新声明,而且它们在抽象 class 中通常没有定义。

声明一个 pure virtual 函数的目的是为了让 derived classes 只继承函数接口。

声明简朴的(非纯)impure virtual 函数的目的,是让 derived classes 继承该函数的接口和缺省实现。

声明 non-virtual 函数的目的是为了令 derived classes 继承函数的接口及一份强制性实现。

35. 考虑 virtual 函数以外的其它选择

藉由 Non-Virtual 手法实现 Template Method 模式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class GameCharacter {
public:
int HealthValue() const // derived classes 不重新定义它
{

...
int value = DoHealthValue();
...
return value;
}
...
private: // 不是必须 private
virtual int DoHealthValue() const // derived classes 可重新定义它
{

... // 缺省算法
}
};

令客户通过 public non-virtual 成员函数间接调用 private virtual 函数,称之为 non-virtual interface(NVI)手法。它是 Template Method 设计模式的一个独特表现形式。non-virtual 函数称为 virtual 函数的外覆器(wrapper)。

藉由 Function Pointers 手法实现 Strategy 模式

缺点:将机能从成员函数移到 class 外部函数,导致非成员函数无法访问 class 的 non-public 成员。

藉由 std::function 手法实现 Strategy 模式

古典的 Strategy 模式

古典的 Strategy 模式会将健康函数做成一个分离的继承体系中的 virtual 成员函数。

36. 绝不重新定义继承而来的 non-virtual 函数

  • class 内声明一个 non-virtual 函数会为该 class 建立起一份不变性(invariant),凌驾其特异性(specialization)。

37. 绝不重新定义继承而来的缺省参数值

  • 本条款的讨论局限于“继承一个带有缺省参数值的 virtual 函数”,绝对不要新定义继承而来的缺省参数值,因为缺省参数都是静态绑定,而 virtual 函数——你唯一应该复写的东西——却是动态绑定。

38. 通过复合塑模出 has-a 或“根据某物实现出”

  • 复合(composition)的意义和 public 继承完全不同。

  • 在应用域(application domain),复合意味 has-a(有一个)。在实现域(implementation domain),复合意味 is-implemented-in-terms-of(根据某物实现出)。

39. 明智而审慎地使用 private 继承

  • Private 继承意味 is-implemented-in-terms-of(根据某物实现出)。它通常比复合(composition)的级别低。但是当 derived class 需要访问 protected base class 的成员,或需要重新定义继承而来的 virtual 函数时,这么设计是合理的。

  • 和复合(composition)不同,private 继承可以造成 empty base 最优化。这对致力于“对象尺寸最小化”的程序库开发者而言,可能很重要。

40. 明智而审慎地使用多重继承

  • 多重继承比单一继承复杂。它可能导致新的歧义性,以及对 virtual 继承的需要。

  • virtual 继承会增加大小、速度、初始化(及赋值)复杂度等等成本。如果 virtual base classes 不带任何数据,将是最具实用价值的情况。

  • 多重继承的确有正当用途。其中一个情节涉及“public 继承某个 Interface class”和“private 继承某个协助实现的 class”的两相组合。

第七章 模板与泛型编程

41. 了解隐式接口和编译期多态

  • class 和 template 都支持接口(interface)和多态(polymorphism)。

  • 对 class 而言接口是显示(explicit)的,以函数签名为中心。多态则是通过 virtual 函数发生于运行期。

  • 对 template 参数而言,接口是隐式的(implicit),奠基于有效表达式。多态则是通过 template 具现化和函数重载解析(function overloading resolution)发生于编译期。

42. 了解 typename 的双重意义

  • 声明 template 参数时,前缀关键字 class 和 typename 可互换。

  • 请使用关键字 typename 标识嵌套从属类型名称;但不得在 base class lists(基类列)或 member initialization list(成员初值列)内以它作为 base class 修饰符。

43. 学习处理模板化基类内的名称

  • 当我们从 Object Oriented C++ 跨进 Template C++,继承就不像以前那么畅行无阻了。面对一些编译不通过的情况,可在 derived class templates 内通过 “this->” 指涉 base class templates 内的成员名称,或藉由一个明白写出的 “base class 资格修饰符” 完成。

44. 将与参数无关的代码抽离 templates

  • Templates 生成多个 classes 和多个函数,所以任何 template 代码都不该与某个造成膨胀的 template 参数产生相依关系。

  • 因非类型模板参数(non-type template parameters)而造成的代码膨胀,往往可消除,做法是以函数参数或 class 成员变量替换 template 参数。

  • 因类型参数(type parameters)而造成的代码膨胀,往往可降低,做法是让带有完全相同二进制表述(binary representations)的具现类型(instantiation types)共享实现码。

45. 运用成员函数模板接受所有兼容类型

  • 请使用成员函数模板(member function templates)生成“可接受所有兼容类型”的函数。

  • 如果你声明 member templates 用于“泛化 copy 构造”或“泛化 assignment 操作”,你还是需要声明正常的 copy 构造函数和 copy assignment 操作符。

46. 需要类型转换时请为模板定义非成员函数

函数的参数可以隐式转换,函数模板不行。

friend 的传统用途是“访问 class 的 non-public 成分”。

在 class 内部声明 non-member 函数的唯一办法就是:令它成为一个 friend。

  • 当我们编写一个 class template,而它所提供之“于此 template 相关的”函数支持“所有参数之隐式类型转换”时,请将那些函数定义为“class templdate 内部的 friend 函数”。

人工神经网络训练方法——后向传播

人工神经网络训练方法——随机查找》介绍的随机查找方法,有点盲人摸象,所以继续介绍主流的后向传播(BackPropagation)算法。

填坑

先给随机查找做个优化!上篇中的激活函数统一使用 ReLU,其实这是不好的,输出层可以改为 Sigmoid 或 Tanh:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
inline double ActivationFunction_ReLU(double x) {
return std::max(0.0, x);
}
inline double ActivationFunction_Sigmoid(double x) {
return 1.0 / (1 + exp(-x));
}
inline double ActivationFunction_Tanh(double x) {
return (tanh(x) + 1.0) / 2;
}

double AnnRun(const double x[2], double* w) {
double f = ActivationFunction_ReLU(x[0] * w[0] + x[1] * w[1] - w[2]);
double g = ActivationFunction_ReLU(x[0] * w[3] + x[1] * w[4] - w[5]);
return ActivationFunction_Sigmoid(f * w[6] + g * w[7] - w[8]);
}

原因很简单,我们已经知道 Xor 的结果不是 0 就是 1,用 ReLU 是可能大于 1 的,而 Sigmoid 和 Tanh 不会大于 1。

后向传播

理论学习:《如何直观地解释 back propagation 算法?》

原理:求导

训练时,x 和 y 都是固定的,要求的是 a 和 b,所以问题是:当 y 偏离了 delta_y,求 a 和 b 应该修正多少?

分别对 a 和 b 求偏导,则:

1
2
dy/da = x
dy/db = 1

所以

1
2
delta_a = delta_y / x
delta_b = delta_y

代码不会骗人,来一个简化的例子:

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
// BackPropagation.cpp
//

#include <iostream>

void Train(double& a,
double& b,
double input,
double expect_output,
double learning_rate)
{

double delta_y = expect_output - (input * a + b);
if (input != 0) {
a += (delta_y / input) * learning_rate;
}
b += delta_y * learning_rate;
}

int main() {
// 要求的函数是:y = 2 * x + 3
const double input[4] = {0, 1, 2, 3};
const double expect_output[4] = {3, 5, 7, 9};

// 初始化状态是:y = 1 * x + 4
double a = 1.0;
double b = 4.0;

std::cout << "Initial: y = " << a << " * x + " << b << "\n";

// 两轮就搞定了
for (int t = 0; t < 2; ++t) {
for (int i = 0; i < 4; ++i) {
Train(a, b, input[i], expect_output[i], 1);
}
}
std::cout << "Trained: y = " << a << " * x + " << b << "\n";

return 0;
}

人工神经网络训练方法——随机查找

人工神经网络究竟是什么鬼?》中没有讲到如何训练神经网络,本篇延续用 XOR 运算为例,介绍一种随机查找的训练方式,主要原理是:随机初始化 w,计算错误率,在循环中,保存错误率小的 w,直到错误率小于等于 0.01 为止。

代码不会骗人,简单的实现如下:

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// TrainXor_RandomSearch.cpp
// UMUTech @ 2018-07-05 23:45:52
// Be aware that I'm only a novice to ANN. My apologies for any wrong info.
//
#include <algorithm>
#include <iostream>
#include <random>

std::default_random_engine random_engine;

void RandomizeW(double* w, size_t size) {
std::uniform_real_distribution<double> r(0, 1);
for (size_t i = 0; i < size; ++i) {
w[i] = r(random_engine);
}
}

void PrintW(double* w, size_t size) {
for (size_t i = 0; i < size; ++i) {
std::cout << i << "\t" << w[i] << "\n";
}
}

double ActivationFunction(double x) {
// ReLU
return std::max(0.0, x);
}

double AnnRun(const double x[2], double* w) {
// bias 乘了 -1,让结果更好地收敛到 [0, 1]
double f = ActivationFunction(x[0] * w[0] + x[1] * w[1] - w[2]);
double g = ActivationFunction(x[0] * w[3] + x[1] * w[4] - w[5]);
return ActivationFunction(f * w[6] + g * w[7] - w[8]);
}

int main() {
const double input[4][2] = {{0, 0}, {0, 1}, {1, 0}, {1, 1}};
const double expect_output[4] = {0, 1, 1, 0};

double last_error = 1000;

double w[3 * 3];
double w_copy[3 * 3];

std::random_device rd;
random_engine.seed(rd());

int train_count = 0;
for (; last_error > 0.01; ++train_count) {
if (train_count % 10000 == 0) {
std::cout << "Randomize\n";
RandomizeW(w, _countof(w));
}

memcpy(w_copy, w, sizeof(w));

// 随机改变 w
std::uniform_real_distribution<double> r(-0.5, 0.5);
for (int i = 0; i < 3 * 3; ++i) {
w[i] += r(random_engine);
}

double error = pow(AnnRun(input[0], w) - expect_output[0], 2.0);
error += pow(AnnRun(input[1], w) - expect_output[1], 2.0);
error += pow(AnnRun(input[2], w) - expect_output[2], 2.0);
error += pow(AnnRun(input[3], w) - expect_output[3], 2.0);

if (error < last_error) {
// 错误率更小,保存
last_error = error;
} else {
// 恢复 w
memcpy(w, w_copy, sizeof(w));
}
}

printf("Finished in %d loops.\n", train_count);

PrintW(w, _countof(w));

/* Run the network and see what it predicts. */
printf("Output for [%1.f, %1.f] is %1.f.\n", input[0][0], input[0][1],
AnnRun(input[0], w));
printf("Output for [%1.f, %1.f] is %1.f.\n", input[1][0], input[1][1],
AnnRun(input[1], w));
printf("Output for [%1.f, %1.f] is %1.f.\n", input[2][0], input[2][1],
AnnRun(input[2], w));
printf("Output for [%1.f, %1.f] is %1.f.\n", input[3][0], input[3][1],
AnnRun(input[3], w));

return 0;
}

效果主要看人品,可能跑个不停,也可能几乎立刻完成。一次运行结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Randomize
Finished in 344 loops.
0 -1.18943
1 -1.60685
2 -0.848489
3 1.28751
4 1.21697
5 0.532657
6 -2.27322
7 -0.77646
8 -1.57966
Output for [0, 0] is 0.
Output for [0, 1] is 1.
Output for [1, 0] is 1.
Output for [1, 1] is 0.

另一次:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Randomize
Finished in 444 loops.
0 1.6138
1 1.4345
2 1.33925
3 1.50895
4 1.09461
5 -0.283878
6 -2.37528
7 1.08117
8 0.239626
Output for [0, 0] is 0.
Output for [0, 1] is 1.
Output for [1, 0] is 1.
Output for [1, 1] is 0.

求模版函数地址

最近用 WTL 写 Ribbon 界面,发现一个坑。

先看 WTL9.1 的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static void (CharFormat::*Getk_[])(IPropertyStore*) = 
{
&CharFormat::Getk_Family,
&CharFormat::Getk_FontProperties_Size,
&CharFormat::Getk_MaskEffect<CFM_BOLD, CFE_BOLD, UI_PKEY_FontProperties_Bold>,
&CharFormat::Getk_MaskEffect<CFM_ITALIC, CFE_ITALIC, UI_PKEY_FontProperties_Italic>,
&CharFormat::Getk_MaskEffect<CFM_UNDERLINE, CFE_UNDERLINE, UI_PKEY_FontProperties_Underline>,
&CharFormat::Getk_MaskEffect<CFM_STRIKEOUT, CFE_STRIKEOUT, UI_PKEY_FontProperties_Strikethrough>,
&CharFormat::Getk_VerticalPositioning,
&CharFormat::Getk_Color<CFM_COLOR, UI_PKEY_FontProperties_ForegroundColor>,
&CharFormat::Getk_Color<CFM_BACKCOLOR, UI_PKEY_FontProperties_BackgroundColor>,
&CharFormat::Getk_ColorType<CFM_COLOR, CFE_AUTOCOLOR, UI_SWATCHCOLORTYPE_AUTOMATIC, UI_PKEY_FontProperties_ForegroundColorType>,
&CharFormat::Getk_ColorType<CFM_BACKCOLOR, CFE_AUTOBACKCOLOR, UI_SWATCHCOLORTYPE_NOCOLOR, UI_PKEY_FontProperties_BackgroundColorType>,
};

其中 Getk_MaskEffect 是个模版函数,实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
template <DWORD t_dwMask, DWORD t_dwEffects, REFPROPERTYKEY key>
void Getk_MaskEffect(IPropertyStore* pStore)
{
if (SUCCEEDED(pStore->GetValue(key, &propvar)))
{
UIPropertyToUInt32(key, propvar, &uValue);
if ((UI_FONTPROPERTIES)uValue != UI_FONTPROPERTIES_NOTAVAILABLE)
{
dwMask |= t_dwMask;
dwEffects |= ((UI_FONTPROPERTIES) uValue == UI_FONTPROPERTIES_SET) ? t_dwEffects : 0;
}
}
}

然后,在 VS2017 编译失败了……

1>X:\WTL91_5321_Final\Include\atlribbon.h(422): error C2440: ‘initializing’: cannot convert from ‘overloaded-function’ to ‘void (__thiscall WTL::RibbonUI::CharFormat:: )(IPropertyStore )’

1>X:\WTL91_5321_Final\Include\atlribbon.h(422): note: None of the functions with this name in scope match the target type

然后根据错误提示搜到:Cannot take address of template function,https://gcc.gnu.org/bugzilla/show_bug.cgi?id=39018,翻译一下:模版函数的地址转化,分两步走,第一步先转具化,第二步转目标类型,这样可以;直接转过去不可以!

再来看看 WTL10 怎么解决这个问题的!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static void (CharFormat::*Getk_[])(IPropertyStore*) = 
{
&CharFormat::Getk_Family,
&CharFormat::Getk_FontProperties_Size,
&CharFormat::Getk_MaskEffectBold,
&CharFormat::Getk_MaskEffectItalic,
&CharFormat::Getk_MaskEffectUnderline,
&CharFormat::Getk_MaskEffectStrikeout,
&CharFormat::Getk_VerticalPositioning,
&CharFormat::Getk_Color,
&CharFormat::Getk_ColorBack,
&CharFormat::Getk_ColorType,
&CharFormat::Getk_ColorTypeBack,
};

原来的模版函数,已经替换成普通函数了……

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
void Getk_MaskEffectBold(IPropertyStore* pStore)
{
Getk_MaskEffectAll(pStore, CFM_BOLD, CFE_BOLD, UI_PKEY_FontProperties_Bold);
}

void Getk_MaskEffectItalic(IPropertyStore* pStore)
{
Getk_MaskEffectAll(pStore, CFM_ITALIC, CFE_ITALIC, UI_PKEY_FontProperties_Italic);
}

void Getk_MaskEffectUnderline(IPropertyStore* pStore)
{
Getk_MaskEffectAll(pStore, CFM_UNDERLINE, CFE_UNDERLINE, UI_PKEY_FontProperties_Underline);
}

void Getk_MaskEffectStrikeout(IPropertyStore* pStore)
{
Getk_MaskEffectAll(pStore, CFM_STRIKEOUT, CFE_STRIKEOUT, UI_PKEY_FontProperties_Strikethrough);
}

void Getk_MaskEffectAll(IPropertyStore* pStore, DWORD _dwMask, DWORD _dwEffects, REFPROPERTYKEY key)
{
if (SUCCEEDED(pStore->GetValue(key, &propvar)))
{
UIPropertyToUInt32(key, propvar, &uValue);
if ((UI_FONTPROPERTIES)uValue != UI_FONTPROPERTIES_NOTAVAILABLE)
{
dwMask |= _dwMask;
dwEffects |= ((UI_FONTPROPERTIES)uValue == UI_FONTPROPERTIES_SET) ? _dwEffects : 0;
}
}
}