旭穹の陋室

前言 std::atomic模板的实例化或全特化可以定义一个原子的数据类型。它提供了多线程间的原子操作。所谓原子操作，一般是指在逻辑上的不可分割的操作（物理上并不一定只有一条指令）。原子操作是无锁类型，但不代表无需等待，当多个线程同时竞争同一原子变量时，仍要为了同步而等待。但原子操作的开销要低于加解锁。 原子操作（std::atomic） 原型 // since C++11// Defined in header <atomic> // 原始模板template< class T >struct atomic;// 裸指针类型偏特化template< class U >struct atomic<U*>;// since C++20// Defined in header <memory>// 智能指针类型的偏特化template< class U >struct atomic<std::shared_ptr<U>>;template< class U >struct atomi ...

前言 std::lock_guard类是C++11新加入的特性，它是一个mutex包装器，提供了一种方便的RAII风格机制，该包装器在构造时自动绑定传入的mutex并加锁，在其析构函数中解锁，从而实现在作用域块的持续时间内拥有mutex而无需手动解锁，从而大大减少了死锁的可能性。 使用示例 #include <thread>#include <mutex>#include <iostream> int g_i = 0;std::mutex g_i_mutex; // protects g_i void safe_increment(){ const std::lock_guard<std::mutex> lock(g_i_mutex); ++g_i; std::cout << "g_i: " << g_i << "; in thread #" << std::this_thread::get_i ...

编程语言 如果你正在读这本书，那么在你的CS旅程中的某个地方，你会有那么一刻，第一次开始关心代码的效率。 我在高中的时候，我意识到制作网站和做实用编程并不能让你获得大学的入场券，于是我进入了算法编程奥林匹克竞赛的世界。我是一个合格的程序员，尤其是对于一个高中生来说，但我之前从来没有想过我的代码需要多长时间才能执行完。但突然之间，问题开始变得重要了：现在竞赛中的每个问题都有严格的时间限制。我开始思考一秒钟能做多少操作。 在思考这个问题时，我还不太了解计算机架构。但我也不需要精确答案——我可以使用经验法则。我的想法是：“2-3GHz主频意味着每秒执行20到30亿条指令，在一个简单的循环中，对数组元素执行一些操作，我还需要增加循环计数器，检查循环结束条件，进行数组索引等这些辅助操作，因此，让我们为每一个有效指令增加3-5个指令的余量，最终我使用每秒5⋅1085\cdot10^85⋅108个操作作为估计值。上面这些陈述并不精确，但计算一下我的算法需要多少操作，并将其除以上面这个数字，对于我来说也是一个很好的经验法则。 当然，真正的答案要复杂得多，而且与操作类型本身强相关。对于指针追逐（poin ...

现代硬件 20世纪60年代的超级计算机的主要缺点并不是速度慢（相对而言），而是体积巨大、使用复杂，而且价格昂贵，以至于只有世界超级大国的政府才能负担得起。它们的尺寸是它们如此昂贵的原因：它们需要大量的定制组件，这些组件必须由持有电气工程高级学位的人在宏观世界中非常仔细地组装，而这一过程是无法大规模量产的。 转折点是芯片（microchips）（单个的、微小的、完整的电路）的出现和发展：它彻底改变了工业，可能称得上20世纪最重要的发明，没有之一。1965年的一个价值数百万美元的计算机柜，到了1975年可以装进一块4mm×4mm的硅片上，你可以花25美元买到它。在接下来的十年中，这种经济性的显著提高引发了家用电脑革命，Apple II、Atari 2600、Commodore 64和IBM PC等电脑开始走进寻常百姓家。 芯片是如何制造的 芯片是用一种叫做光刻的工艺将电路“印刷”在一片晶体硅上，这包括： 生长和切片非常纯的硅晶体，称为Wafer； 用一层称为光刻胶物质覆盖它，光刻胶会在光子击中它时溶解； 用光子以设计的特定图形样式撞击光刻胶； 化学刻蚀现在暴露出的部分； 去除剩余的光刻胶 ...

复杂度模型（Complexity Models） 如果你打开了一本计算机科学的教科书，它可能在一开始就介绍了计算复杂度（computational complexity）。简单地说，计算复杂度是在计算过程中执行的所有基本操作（诸如加法、乘法、读取、写入等）的总和，可以根据不同操作的耗时进行加权。 复杂度是一个不算新的概念。20世纪60年代初它被系统地制定出来，此后被普遍用作估计算法成本的代价函数。这个模型之所以被如此迅速地采用，是因为它很好地近似了当时计算机的工作方式。 经典复杂度理论 CPU的“基本操作”称为指令（instructions），其“成本”称为延迟（latencies）。指令存储在内存（memory）中，并由处理器逐一执行，处理器的一些内部状态（state）存储在一组寄存器（registers）中。其中一个寄存器是指令指针（instruction pointer），它指示要读取和执行的下一条指令的地址。每一条指令都会以某种方式改变处理器的状态（包括指令指针的移动），可能会修改主内存，并需要占用若干CPU周期（CPU cycles）执行完成，之后才能启动下一条指令。 要估计 ...

前言 最近准备开一个新坑，学习并翻译一下国外大神Sergey Slotin的关于高性能计算的新书Algorithms for Modern Hardware。当然，这必然是我消化过一轮的产物，其中夹杂这我个人的理解，难免会有纰漏和错误。所以，有能力的同学建议还是去看原文。 作者序（部分） 这是一本即将出版的高性能计算书籍，书名为《现代硬件算法》，由Sergey Slotin撰写。 它的目标受众不仅仅是性能工程师、实用算法研究人员，那些刚刚学完高级算法课程，了解了减少算法复杂度（如O(nlogn)O(nlogn)O(nlogn) to O(nloglogn)O(nloglogn)O(nloglogn)）可以提升程序性能，但希望学习到更为实用的性能优化技巧的CS本科学生，也是受众之一。 所有的书籍材料都在该github仓库中，相关代码则在另一个独立的仓库中。这不是一个合作的开源项目，但欢迎任何的贡献和反馈。 目录（updating） 复杂度模型 现代硬件 编程语言

前言 本文是阅读《Effective C++ 改善程序与设计的55个具体做法（第三版）》的心得笔记第七部分，文章也会按照原书的顺序依次记录各个条款。 第一部分的阅读笔记参见effective C++ 读书笔记01。 第二部分的阅读笔记参见effective C++ 读书笔记02。 第三部分的阅读笔记参见effective C++ 读书笔记03。 第四部分的阅读笔记参见effective C++ 读书笔记04。 第五部分的阅读笔记参见effective C++ 读书笔记05。 第六部分的阅读笔记参见effective C++ 读书笔记06。 定制 new 和 delete 条款49：了解 new-handler 的行为 当 operator new 无法满足某个内存分配需求时，一般会抛出 std::bad_alloc 异常。比如如下程序在VS x86环境下： int main() { int *p = new int[0x1fffffff]; return 0;} 用 std::nothrow 修饰 new 操作符，可以使内存分配阶段不会抛异常，失败了就返 ...

前言 GCC的--wrap=symbol或--wrap,symbol是一个链接器选项，可以重定向未定义的符号。要配合-Wl,<options>使用，表明是一个链接器选项。具体作用如下： 如果符号symbol未在当前编译单元中（一般为当前源文件）定义，则链接到符号__wrap_symbol; 如果符号__real_symbol未在当前编译单元中（一般为当前源文件）定义，则链接到符号symbol; 这方便我们在移植代码时，将已有的库函数（不兼容新平台）重定向到新的自定义函数，而又不需要对每处函数调用进行修改；或者在调试代码时，对目标函数包装一下，以监视其行为而又不需要修改函数本身。 重定向自定义函数 自定义的功能函数代码： // foo.c#include <stdio.h>#include "foo.h"void foo(void){ printf("call foo\n");}void call_foo(void){ foo();} // foo.hvoid foo(void); ...

获取用户进程的内核转储 获取内核转储（core dump）的最大好处是，能保存问题发生时的状态。 启用内核转储 ulimit -c # 查看转储文件大小限制ulimit -c unlimited # 不限制内核转储文件大小，开启内核转储，仅对当前shell有效 可以将ulimit -c unlimited添加到~/.bashrc中，使得每次打开shell都会生效。编写一个会产生Segmentation fault的代码文件segfault.c： #include <stdio.h>int main() { int *a = NULL; *a = 0x1; return 0;} 使用gcc编译并执行： gcc -g segfault.c # -g 可执行程序包含调试信息./a.out # Segmentation fault (core dumped) 当前目录下生成core文件，用GDB调试生成的core文件： gdb -c core ./a.out 有如下打印： … Reading symbols from ./a.o ...

前言 本文是阅读《Effective C++ 改善程序与设计的55个具体做法（第三版）》的心得笔记第六部分，文章也会按照原书的顺序依次记录各个条款。 第一部分的阅读笔记参见effective C++ 读书笔记01。 第二部分的阅读笔记参见effective C++ 读书笔记02。 第三部分的阅读笔记参见effective C++ 读书笔记03。 第四部分的阅读笔记参见effective C++ 读书笔记04。 第五部分的阅读笔记参见effective C++ 读书笔记05。 模板与泛型编程 条款41：了解隐式接口和编译期多态 classes和templates都支持接口（interfaces）和多态（polymorphism）。 对于classes而言，接口是显式的，多态是通过virtual函数实现的运行期多态： 显式接口由函数签名式（函数名称、参数类型、返回类型）构成，在源码中是明确可见的； 运行期多态基于virtual函数实现，具体调用哪一个virtual函数的重写，将在运行期根据对象的动态类型决定； 对于Templates而言，接口时隐式的，多态则是通过template具现化 ...