Back to Basics -- c++ move sematics

1.3 Copying as a Fallback 1.4 const Return Values const std::string get_value();不再是guideline,因为const disables 移动语义 例如: const std::string getValue(); std::vector<std::string> coll; coll.push_back(getValue()); // copies(because the return value is const) const std::string getValue(); // BAD: disables move semantics for return values const std::string& getRef(); // OK const std::string* getPtr(); // OK Summary Move semantics allows us to optimize the copying of objects, where we no longer need the value. It can be used implicitly (for unnamed temporary objects or local return values) or explicitly (with std::move()). std::move() means I no longer need this value here. It marks the object as movable. An object marked with std::move() is not (partially) destroyed (the destructor still will be called). By declaring a function with a non-const rvalue reference (such as std::string&&), you define an interface where the caller semantically claims that it no longer needs the passed value. The implementer of the function can use this information to optimize its task by “stealing” the value or do any other modification with the passed argument. Usually, the implementer also has to ensure that the passed argument is in a valid state after the call. Moved-from objects of the C++ standard library are still valid objects, but you no longer know their value. Copy semantics is used as a fallback for move semantics (if copy semantics is supported). If there is no implementation taking an rvalue reference, any implementation taking an ordinary const lvalue reference (such as const std::string&) is used. This fallback is then used even if the object is explicitly marked with std::move(). Calling std::move() for a const object usually has no effect. If you return by value (not by reference), do not declare the return value as a whole to be const. Moved-from objects Valid but Unspecified State ...

October 17, 2023 · 2 min

Computer Architecture —— 分支预测

H&P那本关于分支预测的部分比较简短且表述有点晦涩,(顺便吐槽一下第五版的中文翻译,建议看英文原版)本文主要参考超标量处理器设计,国人写的,用语符合习惯,强烈推荐! Motivation 在处理器中,除了cache之外,另一个重要的内容就是分支预测,它和cache一起左右处理器的性能。以SPECint95作为benchmark,完美的cache和BP(branch-predictor)能使IPC提高两倍左右: 图片来自论文SSMT。当然,这是21世纪之前的结果了。现代处理器分支预测普遍能达到97%~98%以上的精度,在多数浮点benchmark中基本都是99%的准确率。 为什么需要这么高的精度呢? 一般情况下,分支指令的占比通常在 15% 到 30% 之间。对于经典五级流水线无分支预测cpu,一个branch会造成一次stall;而对于现代的superscalar且流水线级数远高于5的(一般是二十级以上)cpu,其misprediction penalty是 $M * N$ 的(M = fetch group内指令数, N = branch resolution latency,就是决定分支最终是否跳转需要多少周期)。如下图所示: 我们再做一个定量实验: 假设我们有一个 $ N = 20 (20\ pipe stages), W = 5 (5\ wide fetch) $ 1 out of 5 instructions is a branch Each 5 instruction-block ends with a branch 的CPU,那么我们取出500条指令需要多少个周期呢? 100% 预测正确率 100 个时钟周期 (all instructions fetched on the correct path) 无额外工作 99% 预测正确率 100 (correct path) + 20 (wrong path) = 120 个时钟周期 20% 额外指令被取出 98% 预测正确率 100 (correct path) + 20 * 2 (wrong path) = 140 个时钟周期 40% 额外指令被取出 95% 预测正确率 100 (correct path) + 20 * 5 (wrong path) = 200 个时钟周期 100% 额外指令被取出 可以看出,分支预测失败在现代的超标量多流水线cpu中的penalty被极大的放大了。所以分支预测的正确性就显得额外重要。 ...

October 17, 2023 · 3 min

C++内存模型 —— 现代Architecture的妥协

介绍 什么是内存模型(Memory Model)呢?这里介绍的内存模型并非C++对象的内存排布模型,而是一个非编程语言层面的概念。我们知道在C++11中,标准引入了 std::atomic<>原子对象,同时还引入了 memory_order_relaxed memory_order_consume memory_order_acquire memory_order_release memory_order_acq_rel memory_order_seq_cst 这六种 memory order。引入可以让我们进行无锁编程,而如果你想要更高性能的程序,你就必须深挖这六种内存模型的含义并正确应用。(当然,在不显式指明memory order的情况下,你能保证获得正确的代码,但存在性能损失) 内存模型 在介绍C++ memory order之前,我们先回答另一个问题。你的计算机执行的程序就是你写的程序吗? —— 显然不是的。 原因也很简单,为了更高效的执行指令,编译器、CPU结构、缓存及其他硬件系统都会对指令进行增删,修改,重排。但要回答具体进行了什么样的修改,又是一个极其复杂的问题。或者说,整个现代体系结构,就是在保证程序正确性的前提下利用各种手段对程序优化。我们可以粗略的将其分成几个部分: source code order: 程序员在源代码中指定的顺序 program code order: 基本上可以看成汇编/机器码的顺序,它可以由编译器优化后得到 execution code order: CPU执行指令顺序也不见得与汇编相同,不同CPU在执行相同机器码时任然存在优化空间。 perceived order/physical order: 最终的执行顺序。即便CPU按照某种确定指令执行,物理时间上的执行顺序仍然可能不同。例如,在超标量CPU中,一次可以fetch and decode多个指令,这些指令之间的物理执行顺序就是不确定的;由于不同层级缓存之间延时不同,以及缓存之间的通信需要等带来的不确定的执行顺序等 上图简要说明了你的源代码可能经历的优化步骤。 这些优化的一个主要原因在于 掩盖memory access操作与CPU执行速度上的巨大鸿沟。如果没有cache,CPU每个访存指令都需要stall一两百个时钟周期,这是不可接受的。但是引入cache的同时又会带来 cache coherence等问题,这也是造成x初始为0,两个线程同时执行 x++,而x最终不一定为 2的元凶。而一个内存模型则对上述并发程序的同一块内存进行了一定的限制,它给出了在并发程序下,任意一组写操作时,可能读到的值。 不同体系结构(x86, arm, power…)通过不同的内存模型来保证程序的正确性。 bonus question: 不同等级的cache latency? answer: l1: 1ns, l2: 5ns, l3: 50~100ns, main memory: 200ns ...

September 1, 2023 · 3 min

Computer Architecture —— 高级缓存技术

本文不会介绍cache的组织形式等基本内容,但也算不上什么"Advanced"。主要包含一些从硬件层面优化cache的手段。 优化cache的几种方法 pipeline caches 上图为教科书上经常出现的cache形式(2-way associative为例),它很精炼的解释了cache的实现。但也稍微引入了些“误导”: 图中v、tag和data部分画在连续的一行上,仿佛硬件上他们就是同一块 SRAM 的不同bit 图中识别tag与data是并行完成的,这很好,某种意义上能降低时延;但我们经常遗忘一个事实,只有读cache的时候我们才能这么操作(或者说在写cache时,读取data block是没有意义的) 对于第一点,在实际的实现当中,tag和data部分都是分开放置的,tag一般是由一种叫CAM(Context-Addressable Memory)的材料构成。当然,这与pi不pipeline没什么关系; 读cache主要就两个部分:比较tag,获取data;我们暂且不考虑以pipeline的方式优化,那么serial的先比较tag再读data一定不如parallel的方式进行吗?当我们并行的读取tag和data的时候,我们会发现,读出来的data有可能没用(没有匹配的tag);并且,在n-way set associate cache中,我们会浪费的读出$n-1$个data项;这给我们什么启示呢?如果我们串行的读cache,那么我们可以在比较tag阶段就知道我们想要的数据在不在cache当中;更有意义的是,根据tag比较的结果,我们就知道哪一路的数据是需要被访问的(提前知道了在n-way中的哪一way),那么我们访问data block时,就无需多路选择器,直接访问指定的way,将其他way的data访问的使能信号置为无效,这种做法的优点在于有效减小功耗。 serial的做法肯定比parallel的延时要大,若这时访问cache处于处理器的critical path(关键路径)上,我们可以再将其进行流水线化。 我们现在再来看看写cache时的情况: 写cache时,只有通过tag比较,确认要写的地址在cache中后,才可以写data SRAM,在主频较高的处理器中,这些操作很难在一个周期内完成,这也要求我们将其流水线化。下图为对cache进行写操作使用的流水线示意图: 在上图的实现方式中,store第一个周期读取Tag并进行比较,根据比较的结果,在第二个周期选择是否将数据写到Data SRAM中。还需要注意的是,当执行load指令时,它想要的数据可能正好在store指令的流水线寄存器中(RAW的情况;上图中的DelayedStoreData寄存器),而不是来自于Data SRAM。因此需要一种机制检测这种情况,这需要将load指令所携带的地址和store指令的流水线寄存器(即DelayedStoreAddr寄存器)进行比较,如果相等,那么就将store指令的数据作为load指令的结果。 由此可以看出,对写D-Cache使用流水线之后,不仅增加了流水线本身的硬件,也带来了其他一些额外的硬件开销。其实。不仅在Cache中有这种现象,在处理器的其他部分增加流水线的级数,也会伴随着其他方面的硬件需求,因此过深的流水线带来的硬件复杂度是非常高的,就像Intel的Pentium 4处理器,并不会从过深的流水线中得到预想的好处。当然,cache的流水线化已经是一种广泛使用的用于降低latency的方法了。 write buffers 我愿称之为buffer of buffer,本来cache就起buffer的作用了,但我们再加一个buffer,如下图所示: 这和多一级的cache有什么不同呢?这是一个专门为写操作设计的buffer(注意:load也可能造成写操作)。原因在于我们知道写通常比读更慢,特别对于write-through来说;其次,当上层cache满后,需要先将dirty cache line写回下层cache,再读取下层cache中的数据。若下层cache只有一个读写端口,那么这种串行的过程导致D-Cache发生缺失的处理时间变得很长,此时就可以采用write buffer来解决这个问题。脏状态的cache-line会首先放到写级存中,等到下级存储器有空闲的时候,才会将写缓存中的数据写到下级存储器中。 对于write buffer,我们还可以对其进行 合并(merging) 操作。所谓merging,指的是将在同一个cache-line上的数据一并写入下层cache中,而非多次写入同一个cache-line。 上图中的右侧表示了一个采用了merging write buffer策略的写缓冲区。 critial word first and early restart 先来看一下cache miss时的cpu: 图中展示了一个blocking cache在cache miss时,cpu stall,而后cache将需要取得的cache-line放入后,cpu resume的timeline。我们可以发现,若我们只需要cache-line中的第3个word,cpu完全可以提早resume。如下图所示: ...

August 23, 2023 · 2 min

phmap —— 缓存友好的高效hashtable

众所周知,C++标准库的 unordered_map在性能上向来不是一个好的选择。开源市场上有非常多的高性能哈希表可供选择,phmap继承自 absl-hashmap,有着非常好的插入、查找性能。在著名的Comprehensive C++ Hashmap Benchmarks 2022榜单中名列前茅。事实上,我比对了 phmap::flat_hash_map与榜单中综合性能第一的 ankerl::unordered_dense::map,我的benchmark中只有遍历哈希表时,flat_hash_map的性能低于 unordered_dense::map,其余无论是插入还是随即查找,大部分情况下 flat_hash_map的性能都更优。本文简单介绍了 flat_hash_map相关情况,以及一些使用上的建议与坑点。 flat_hash_map 和 node_hash_map区别 phmap中有提供了两类哈希表,其内部布局示意图如下: 由上图(忽略了bucket的细节)可以看出,flat_hash_map的最大的优点在于 node之间的内存是连续的(虽然可能中间存在空node),遍历的时候对cache更加友好 并且相比于 node_hash_map版少一次寻址过程(std::unordered_map的设计与 node_hash_map)相同。 而 flat_*系列的缺点就是在 rehash的时候: 会引发原来的value失效(这里的失效指的是原来的那个对象所对应的内存失效,而不是value所包含的内容失效,例如,value是一个指针,那它的值——所指向的对象,不会受到影响)。举个例子: flat_hash_map<int, Data> mp; node_hash_map<int, Data> nodemp; mp[0] = Data(); nodemp[0] = Data(); auto& mp0 = mp[0]; auto& nodemp0 = nodemp[0]; // tigger rehash for (int i = 1; i <= 10; i ++) { mp[i] = Data(); nodemp[i] = Data(); } assert(std::addressof(mp[0]) != std::addressof(mp0)); assert(std::addressof(nodemp[0]) == std::addressof(nodemp0)); 原因就是 flat_hash_map的内存布局导致的。而 node_hash_map或者 std::unordered_map就保证不会出现这种情况,因为当他们rehash的时候,只需要将bucket内的指针重新分配,指针的值还是指向原来的 node<key, value>. ...

July 23, 2023 · 3 min

ICPC西安游记

没写记录,学弟写了,直接用 ICPC西安邀请赛

May 29, 2023 · 1 min

C++ CRTP

原先只是了解这个名词,想着C++20后静态多态直接用 concept来实现就好了就没细看,没必要整这些模板元编程的奇技淫巧。没想到面试某量化C++开发的时候被狠狠拷打……. CRTP (curiously recurring template pattern) 一般认为,CRTP可以用来实现静态多态 template <typename T> class Base { void func() { static_cast<T*>(this)->funcImpl(); } }; class Derived : public Base<Derived> { void funcImpl() { // do works here } }; 通过CRTP可以使得类具有类似于虚函数的效果,同时又没有虚函数调用时的开销(虚函数调用需要通过虚函数指针查找虚函数表进行调用),同时类的对象的体积相比使用虚函数也会减少(不需要存储虚函数指针),但是缺点是无法动态绑定,感觉有点过于鸡肋。 有什么用呢?可以用来向纯虚类一样做接口:(以下类似的代码在大量数学库中出现) template <typename ChildType> struct VectorBase { ChildType &underlying() { return static_cast<ChildType &>(*this); } inline ChildType &operator+=(const ChildType &rhs) { this->underlying() = this->underlying() + rhs; return this->underlying(); } }; struct Vec3f : public VectorBase<Vec3f> { float x{}, y{}, z{}; Vec3f() = default; Vec3f(float x, float y, float z) : x(x), y(y), z(z) {} }; inline Vec3f operator+(const Vec3f &lhs, const Vec3f &rhs) { Vec3f result; result.x = lhs.x + rhs.x; result.y = lhs.y + rhs.y; result.z = lhs.z + rhs.z; return result; } 定义好VectorBase后,Vec3f, Vec4f等直接实现接口就好。相比虚函数的形式,在空间和runtime都有优势。 ...

May 20, 2023 · 2 min

轻量级高并发网络库+httpserver

本博客部署在两个服务器上,其中一个的 HTTP 服务就是由本文介绍的 FalconLink 提供。你可以通过IP地址 101.34.211.126:20080 尝试访问。 项目地址 https://github.com/caaatch22/FalconLink Overview FalconLink是一个轻量级的高并发网络库。它封装了网络编程套接字API,将其抽象成一个易用,可拓展框架。用户只需通过设置回调函数的形式注入业务逻辑。它同时也具有 HTTP 服务请求与解析的功能。 上图是FalconLink系统架构的一个简单概括性图示。 采用非阻塞socket配合边缘触发,及one loop per thread的主从 reactor设计 Acceptor 是专门用于处理接受新用户连接请求的模块。它守候在监听端口。收到请求后建立 Connection 分配给 EventLoop。 FalconLink 将每个 TCP连接抽象成一个 Connection,一个 Connection对应一个连接 socket 套接字。用户可以为每一条Connection注册回调函数。 每个 EventLoop 都拥有一个 Poller。 Poller 负责监听已连接的套接字,将有事件触发的连接反馈给 EventLoop。 EventLoop是该系统的核心组件, 每个都单独运行在一个线程中. 它从 Poller 中接收到有事件触发的用户连接后, 会获取并执行它们的回调函数. ThreadPool 线程池管理着系统中有多少个 EventLoop 在运行,并调度线程,防止注册过多线程导致性能下降。 支持 HTTP(GET,HEAD)请求的解析与回复,支持挂载静态 html 文件(本博客使用FalconLink的 HTTP 服务) 实现异步logger API 使用falconlink,可以轻易且优雅的在20行内实现一个 echo server。 #include "falconlink.hpp" int main() { falconlink::InetAddr local_address("0.0.0.0", 8090); falconlink::Server echo_server(local_address); echo_server .onHandle([&](falconlink::Connection* client_conn) { int from_fd = client_conn->fd(); auto [read, exit] = client_conn->recv(); if (exit) { client_conn->getEventLoop()->deleteConnection(from_fd); // client_conn ptr is invalid below here, do not touch it again return; } // 只有以下四行是业务逻辑 if (read) { client_conn->WriteToWriteBuffer(client_conn->ReadAsString()); client_conn->send(); client_conn->clearReadBuffer(); } }) .start(); return 0; } Build & Test 将代码 clone 到本地,进入主目录 ...

March 1, 2023 · 1 min

CMU15445-project3 Query Excution

Overview 在这次实验写完后,我们已经能使用bustub-shell完成执行 sql 语句了,还是挺有成就感的。同时,TA 为我们准备了浏览器上的bustub ,方便和我们写的对比调试。你也可以使用 explain 来查看他的优化策略与执行步骤。 这次实验的主要难点在于读代码,理清 bustub 的执行引擎的数据流以及代码中的实现。搞懂了之后各个算子的实现就很简单了(相对 B+树)。 上图是 bustub 的整体架构。 Parser sql 语句的解析就像其他编程语言一样,同样需要翻译成比较结构化的东西。Parser 阶段会生成一个抽象语法树(AST, Abstract Syntax Tree)。 这并不是数据库核心部分,bustub 直接使用了 PostgreSQL 的 parser 库 libpg_query。 Binder 得到 AST 后,需要将这些词语绑定到数据库实体上,这就是 Binder 的工作。例如有这样一条 sql: SELECT table1.y, table2.x FROM table1 INNER JOIN table2 ON table1.x = table2.y; 其中 SELECT 和 FROM 是关键字,x 和 table1 是标识符。我们可以使用 explain 来看看 binder 层(bustub-shell 未完成时也可以使用 explain): === BINDER === BoundSelec { table=BoundJoin { type=Inner, left=BoundBaseTableRef { table=table1, oid=25 }, right=BoundBaseTableRef { table=table2, oid=26 }, condition=(table1.x=table2.y) }, columns=[table1.y, table2.x], groupBy=[], having=, where=, limit=, offset=, order_by=[], is_distinct=false, ctes=, } 可以看出,binder的作用就是对AST的各个节点绑定一个(物理)实体。 ...

January 17, 2023 · 4 min

将Wavelet Tree用于算法竞赛

Wavelet Tree for Competitive Programming 最近在学FM-Index相关算法用于数据库,了解到Wavelet Tree这一数据结构,发现其还可以应用在算法竞赛中。网上相关中文资料比较少,权当自己做个学习笔记 开始之前 在学习wavelet tree前,不妨看看他能解决什么样的问题。 假设我们有一长为 $n$ 的序列 $A[0…n - 1]$ 。在算法竞赛中,典型的数据量是 $n = 1e5, |A[i]| <= 1e9$ 区间 $[L, R)$ 中元素$x$的出现次数 区间 $[L, R)$ 中的第k小数 区间 $[L, R)$ 上 小于等于x的数的个数 … 以上问题都可以通过可持久化线段树在解决。那为什么还需要wavelet tree呢,我们都知道可持久化线段树的常数很大,并且十分消耗空间,在有些苛刻的题目下可能会被卡 好吧应该都是金牌题,不是我该考虑的 。利用wavelet tree可以在$log(\sigma)$时间内完成的同时(且优秀的常数),若使用bitvector优化空间,空间上大概比可持久化线段树少一个量级。最重要的一点是,我个人觉得他比主席树更加直观易懂。 $\sigma$ = | $\Sigma = {1, 2, \cdots, \sigma}$| (用于序列上时是值域大小)。 用wavelet tree的缺点就是带修改操作比较难写,码量较大,一般不会在比赛时使用。 Wavelet Tree 该图给出了用序列 $A = [7, 3, 5, 6, 1, 3, 2, 7, 8, 4]$ 构建的wavelet tree的形态。对于树上的每个节点,我们会将其按照值域分成两个部分$[low, mid), [mid, high)$。通过 稳定划分(stable_partition,即不改变相对顺序的情况下划分)将该节点上的序列中小于 $mid$的划分到左子树中,大于等于mid的划分到右子树中,递归直至节点中只有一种值时为叶节点。需要注意的是,我们并不会在叶子节点中直接存储序列的值,而是通过某个方法使得我们能够使用较小的空间的情况下得到足够的信息。 ...

January 10, 2023 · 4 min