(译)编译器是如何处理没用到的代码的?


原文链接

作者整理了一份测试的表格(这个大哥是真爱c++啊这种细节都要扣我感觉魔怔了有点)

编译器是否会对没被用到的___ 发出警告 Clang GCC ICC MSVC
static function -Wall -Wall   -W4
static variable -Wall -Wall    
private data member -Wall      
private static data member        
private member function        
private static member function        
data member of private class        
static data member of private class        
member function of private class        
static member function of private class        
anonymous-namespaced function -Wall -Wall    
anonymous-namespaced variable -Wall -Wall    
data member of anonymous-namespaced class        
static data member of anonymous-namespaced class -Wall -Wall    
member function of anonymous-namespaced class   -Wall    
static member function of anonymous-namespaced class   -Wall    
function taking anonymous-namespaced class -Wall -Wall    
编译器是否会优化掉未使用的____ Clang GCC ICC MSVC
static function -O0 -O1 -O0 -Od
static variable -O0 -O0 -O1 -Od
private data member
private static data member
private member function
private static member function
static data member of private class
member function of private class
static member function of private class
anonymous-namespaced function -O0 -O1 -O0  
anonymous-namespaced variable -O0 -O0 -O1 -Od
static data member of anonymous-namespaced class -O0 -O0 -O1  
member function of anonymous-namespaced class -O0 -O1 -O1  
static member function of anonymous-namespaced class -O0 -O1 -O1  
function taking anonymous-namespaced class -O0 -O1 -O1  

还有很多优化空间

注意 没用到的私有函数是不回被删掉的,所以有个hack: 模版参数是私有函数指针,通过显式实例化绕开private限制,实现静态注入/调用,详情看这篇文章


Read More

(译)socket in your shell


整理自这篇博客

简单说,就是基本工具shell也可以用socket来做服务/客户端(尤其是在没有nc/telnet的场景下)

作者列了普通bash和zsh下两种用法

bash

echo "text!" > /dev/$PROTO/$HOST/$PORT

一个检测例子

#!/bin/bash
if exec 3>/dev/tcp/localhost/4000 ; then
	echo "server up!"
else
	echo "server down."
fi

我以前都用netcat检测

也可以用exec检测

samplecurl

#!/bin/bash
exec 3<>/dev/tcp/"$1"/80
echo -e "GET / HTTP/1.1\n" >&3
cat <&3

使用

$ ./simplecurl www.google.com
HTTP/1.1 200 OK
Date: Thu, 03 Dec 2020 00:57:30 GMT
Expires: -1
....
<google website>

zsh

有内建模块支持

zmodload zsh/net/tcp

这行放到.zshrc ,或者shell里执行,就加载了ztcp

# host machine:
lfd=$(ztcp -l 7128)
talkfd=$(ztcp -a $lfd)

# client machine
talkfd=$(ztcp HOST 7128)

这样客户端服务端的fd有了,就可以通话了

# host machine
echo -e "hello!" >&$talkfd

# client machine
read -r line <&$talkfd; print -r - $line
> hello!

Read More


(译)现代存储硬件足够快啦就是老api不太好用


这里存储设备指的optane这种 原文

简单整理,用deepl翻译的

作者是老工程师了,列出了常见的几种对存储的误解

  • IO比复制更重,所以复制数据代替直接读是合理的,因为省了一次IO
  • “我们设计的系统要非常快,所以全放在内存里是必须的”
  • 文件拆分成多个反而会慢,因为会产生随机IO 不如直接从一个文件里读,顺序的
  • Direct IO非常慢,只适用于特殊的设备,如果没有对应的cache支持,会很糟糕

作者的观点是,现在设备非常牛逼,以前的api有很多设计不合理的地方,各种拷贝,分配 ,read ahead等等操作过于昂贵

即:传统api的设计是因为IO昂贵,所以做了些昂贵的动作来弥补

  • 读没读到 cache-miss -> 产生page-fault 加载数据到内存 -> 读好了,产生中断
    • 如果是普通用户态进程,再拷贝一份给进程
    • 如果用了mmap,要更新虚拟页

在以前,IO很慢,对比来说这些更新拷贝要慢一百倍,所以这些也无足轻重,但是现在IO延迟非常低,可以看三星nvme ssd指标,基本上耗时数量级持平

简单计算,最坏情况,设备耗时也没占上一半,时间都浪费在哪里了?这就涉及到第二个问题 读放大

操作系统读数据是按照页来读,每次最低4k,如果你读一个1k的数据,这个文件分成了两个,那也就是说,你要用8k的页读1k的数据,浪费87%,实际上,系统也预读(read ahead) 每次默认预读128k,方便后面继续读,那也就是说相当于用256k来读1k,非常恐怖的浪费

那么 用direct IO直接读怎么样,不会有页浪费了吧

问题还在,老api并不是并发读,尽管读的快但是比cpu还是慢,阻塞,还是要等待

所以又变成多文件,提高吞吐,但是

  • 多文件又有多的read ahead浪费,
  • 而且多文件可能就要多线程,还是放大,如果你并没有那么多文件,这个优化点也用不上

新的api

io_uring是革命性的,但还是低级的api:

  • io_uring的IO调度还是会收到之前提到的各种缓存问题影响
  • Direct IO有很多隐藏的条件(caveats 注释事项) 比如只能内存对齐读,io_uring作为新api对于类似的问题没有任何改进

为了使用io_uring你需要分批积累和调度,这就需要一个何时做的策略,以及某种事件循环

为此,作者设计了一个io框架glommio Direct IO,基于轮训,无中断 register-buffer

Glommio处理两种文件类型

  • 随机访问文件
    • 不需要缓冲区,直接用io_uring注册好的缓冲区拿过来用,没有拷贝,没有内存映射,用户拿到一个引用计数指针
    • 因为指导这是随机IO,要多少读多少
  • 流文件
    • 设计的和rust的asyncread一样,多一层拷贝,也有不用拷贝的api

作者列出了他的库做的抽象拿到的数据,和bufferred io做比较

  bufferred IO DirectIO(glommed) +开启预读 read ahead 提高并发度 +使用避免拷贝的api + 增大buffer
53G 2x内存 顺序读sequential 56s, 945.14 MB/s 115s, 463.23 MB/s 22s, 2.35 GB/s 21s, 2.45 GB/s 7s, 7.29 GB/s

注意,随机读+ scan对内存page cache污染比较严重

在小的数据集下

Buffered I/O: size span of 1.65 GB, for 20s, 693870 IOPS
Direct I/O: size span of 1.65 GB, for 20s, 551547 IOPS

虽然慢了一点,但是内存占用上有优势

对于大的数据,优势还是比较明显的,快三倍

Buffered I/O: size span of 53.69 GB, for 20s, 237858 IOPS
Direct I/O: size span of 53.69 GB, for 20s, 547479 IOPS

作者的结论是 新时代新硬件direct IO还是非常可观的,建议相关的知识复习一下


ref/ps

  • https://github.com/DataDog/glommio 有时间仔细看看 这个作者之前是做seastar的,seastar是DirectIO+Future/Promise
  • 详细介绍的文档 https://www.datadoghq.com/blog/engineering/introducing-glommio/
  • 代码文档 https://docs.rs/glommio/0.2.0-alpha/glommio/

Read More

(译)用std::list的splice接口来实现LRU Cache

原文 splice拼接

这是老考试题了,实现一个查O1 插入O1的LRU cache

首先,要保证O1查找,必然需要一个hash表存key,可以用unordered_map unordered_map性能表现特别差,暂且不讨论

然后,保证O1插入 hash表/链表页满足条件

但是,要实现LRU排序,必须要引入list来维护插入顺序

是cache,要有大小限定,过期淘汰最后元素,就需要list的顺序性

get, 要刷新状态,把对应的元素提到链表头,也就是用到splice的地方

存两份不合理,保证查找,hash存key 指针,指针指向链表,淘汰的时候移除指针的同时,把hashmap的元素删掉, 这样就维护起来了

代码接口

template<typename K, typename V, size_t Capacity>
class LRUCache {
public:

 //Assert that Max size is > 0
 static_assert(Capacity > 0);

 /*Adds a key=>value item
  Returns false if key already exists*/
 bool put(const K& k, const V& v);

 /*Gets the value for a key.
  Returns empty std::optional if not found.
  The returned item becomes most-recently-used*/
 std::optional<V> get(const K& k);

 //Erases an item
 void erase(const K& k);

 //Utility function.
 //Calls callback for each {key,value}
 template<typename C>
 void forEach(const C& callback) const {
   for(auto& [k,v] : items) {
    callback(k, v);
   }
 }

private:
 /*std::list stores items (pair<K,V>) in
 most-recently-used to least-recently-used order.*/
 std::list<std::pair<K,V>> items;

 //unordered_map acts as an index to the items store above.
 std::unordered_map<K, typename std::list<std::pair<K,V>>::iterator> index;
};

put简单,两个表加一下就行了,如果慢了,拿到表尾,删两个表中的元素

template<typename K, typename V, size_t Capacity>
bool
LRUCache<K,V,Capacity>::put(const K& k, const V& v) {
 //Return false if the key already exists
 if(index.count(k)) {
  return false;
 }

 //Check if cache is full
 if(items.size() == Capacity) {
  //Delete the LRU item
  index.erase(items.back().first); //Erase the last item key from the map
  items.pop_back(); //Evict last item from the list 
 }

 //Insert the new item at front of the list
 items.emplace_front(k, v);

 //Insert {key->item_iterator} in the map 
 index.emplace(k, items.begin());

 return true;
}

get要做的,拼链表,因为访问到了,要刷新一下

template<typename K, typename V, size_t Capacity>
std::optional<V>
LRUCache<K,V,Capacity>::get(const K& k) {
 auto itr = index.find(k);
 if(itr == index.end()) {
  return {}; //empty std::optional
 }

 /*Use list splice to transfer this item to
  the first position, which makes the item
  most-recently-used. Iterators still stay valid.*/
 items.splice(items.begin(), items, itr->second);
 //从items.begin()这里开始拼接,拼接 items的 itr->second节点 就相当于抽出来拼上

 //Return the value in a std::optional
 return itr->second->second;
}

erase非常简单,和put差不多,逆向的

template<typename K, typename V, size_t Capacity>
void
LRUCache<K,V,Capacity>::erase(const K& k) {
 auto itr = index.find(k);
 if(itr == index.end()) {
  return;
 }

 //Erase from the list
 items.erase(itr->second);

 //Erase from the  map
 index.erase(itr);
}

这种splice的用法,就是从xx上把iter指向的node偷出来拼到参数指定的位置上,说是拼接,不如说是偷

c++17中,map引入来新方法,extract,也是偷节点

用法

//Ascending order
std::map<int, std::string> m1 = {
  {1, "One"}, {2, "Two"}, {3, "Three"} \
};
//Descending order
std::map<int, std::string, std::greater<>> m2 = {
  {4, "Four"}, {5, "Five"} \
};

//Print both maps
for(auto [k, v] : m1)
 std::cout << v << " "; //One Two Three

for(auto [k, v] : m2)
 std::cout << v << " "; //Five Four

//extract from m1 and insert to m2
m2.insert(m1.extract(3));

//get another node from the above node factory
m2.insert(generateNode(6, "Six"));

//Now print m2
for(auto [k, v] : m2)
 std::cout << v << " "; //Six Five Four Three

看上去和splice非常像。splice说实话这个参数设计比较复杂,应该设计成extract这样的组合小函数,更清晰一些


参考资料/链接

  • https://zh.cppreference.com/w/cpp/container/list/splice
  • splice和list::size 有一段历史
    • 可以看这篇吐槽 https://blog.csdn.net/russell_tao/article/details/8572000
    • 作者实现上的取舍 https://howardhinnant.github.io/On_list_size.html
  • 介绍extract https://www.nextptr.com/question/qa1532449120/update-keys-of-map-or-set-with-node-extract

Read More

(译) 为啥select*性能差


原文链接

作者这个经验是放在oracle上的,其他的关系型数据库有类似的判断

增加了网络的流量

那肯定啊,不需要的列/行被搜出来丢弃了,没有意义占用带宽影响延迟

增加调用方的CPU

计算量上去了

可能失去优化器优化的机会

SQL> @xi f2czqvfz3pj5w 0

SELECT * FROM soe_small.customers

---------------------------------------------------------------------------
| Id | Operation         | Name      | Starts | A-Rows | A-Time   | Reads |
---------------------------------------------------------------------------
|  0 | SELECT STATEMENT  |           |      1 |   1699K| 00:00.57 | 28475 |
|  1 |  TABLE ACCESS FULL| CUSTOMERS |      1 |   1699K| 00:00.57 | 28475 |
---------------------------------------------------------------------------
SQL> @xi 9gwxhcvwngh96 0

SELECT customer_id, dob FROM soe_small.customers

---------------------------------------------------------------------------------------
| Id  | Operation            | Name              | Starts | A-Rows | A-Time   | Reads |
---------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT     |                   |      1 |   1699K| 00:00.21 |  5915 |
|   1 |  INDEX FAST FULL SCAN| IDX_CUSTOMER_DOB2 |      1 |   1699K| 00:00.21 |  5915 |
---------------------------------------------------------------------------------------

一个是全表扫一个是索引扫,效率肯定不一样

省内存

SELECT * FROM soe_small.customers ORDER BY customer_since

Plan hash value: 2792773903

----------------------------------------------------------------------------------
| Id  | Operation          | Name      | Starts | A-Rows |   A-Time   | Used-Mem |
----------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |           |      1 |   1699K|00:00:02.31 |          |
|   1 |  SORT ORDER BY     |           |      1 |   1699K|00:00:02.31 |  232M (0)|
|   2 |   TABLE ACCESS FULL| CUSTOMERS |      1 |   1699K|00:00:00.24 |          |
----------------------------------------------------------------------------------

效果显而易见

SELECT customer_id,dob FROM soe_small.customers ORDER BY customer_since

Plan hash value: 2792773903

----------------------------------------------------------------------------------
| Id  | Operation          | Name      | Starts | A-Rows |   A-Time   | Used-Mem |
----------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |           |      1 |   1699K|00:00:00.59 |          |
|   1 |  SORT ORDER BY     |           |      1 |   1699K|00:00:00.59 |   67M (0)|
|   2 |   TABLE ACCESS FULL| CUSTOMERS |      1 |   1699K|00:00:00.13 |          |
----------------------------------------------------------------------------------

增加服务端cpu占用

首先,大量的数据的parse要浪费cpu,优化也要浪费cpu

SQL> SET AUTOTRACE TRACE STAT

SQL> SELECT * FROM widetable /* test100 */;

100 rows selected.

Statistics
----------------------------------------------------------
       2004  recursive calls
       5267  db block gets
       2458  consistent gets
          9  physical reads
    1110236  redo size
     361858  bytes sent via SQL*Net to client
        363  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
        100  rows processed
        
        
SQL> SELECT id,col1 FROM widetable /* test101 */;

100 rows selected.

Statistics
----------------------------------------------------------
          5  recursive calls
         10  db block gets
         51  consistent gets
          0  physical reads
       2056  redo size
       1510  bytes sent via SQL*Net to client
        369  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
        100  rows processed

作者写了个插件,Session Snapper ,可以抓时间

SQL> SELECT * FROM widetable /* test1 */;

SQL> @snapper stats,gather=t 5 1 1136
Sampling SID 1136 with interval 5 seconds, taking 1 snapshots...

-- Session Snapper v4.30 - by Tanel Poder ( http://blog.tanelpoder.com/snapper )

-----------------------------------------------------------------------------
    SID, USERNAME  , TYPE, STATISTIC                          ,         DELTA
-----------------------------------------------------------------------------
   1136, SYSTEM    , TIME, hard parse elapsed time            ,         78158
   1136, SYSTEM    , TIME, parse time elapsed                 ,         80912
   1136, SYSTEM    , TIME, PL/SQL execution elapsed time      ,           127
   1136, SYSTEM    , TIME, DB CPU                             ,         89580
   1136, SYSTEM    , TIME, sql execute elapsed time           ,          5659
   1136, SYSTEM    , TIME, DB time                            ,         89616


SQL> SELECT id,col1 FROM widetable /* test2 */;

-----------------------------------------------------------------------------
    SID, USERNAME  , TYPE, STATISTIC                          ,         DELTA
-----------------------------------------------------------------------------
   1136, SYSTEM    , TIME, hard parse elapsed time            ,          1162
   1136, SYSTEM    , TIME, parse time elapsed                 ,          1513
   1136, SYSTEM    , TIME, PL/SQL execution elapsed time      ,           110
   1136, SYSTEM    , TIME, DB CPU                             ,          2281
   1136, SYSTEM    , TIME, sql execute elapsed time           ,           376
   1136, SYSTEM    , TIME, DB time                            ,          2128

能看得出来这个parse时间上的节省

缓存的cursor 浪费内存

SQL> SELECT sharable_mem, sql_id, child_number, sql_text FROM v$sql 
     WHERE sql_text LIKE 'SELECT % FROM widetable';

SHARABLE_MEM SQL_ID        CHILD_NUMBER SQL_TEXT
------------ ------------- ------------ -------------------------------------
       19470 b98yvssnnk13p            0 SELECT id,col1 FROM widetable
      886600 c4d3jr3fjfa3t            0 SELECT * FROM widetable

作者还有个插件 sqlmem.sql ,可以看具体的浪费(作者有点东西)

SQL> @sqlmem c4d3jr3fjfa3t
Show shared pool memory usage of SQL statement with SQL_ID c4d3jr3fjfa3t

CHILD_NUMBER SHARABLE_MEM PERSISTENT_MEM RUNTIME_MEM
------------ ------------ -------------- -----------
           0       886600         324792      219488


TOTAL_SIZE   AVG_SIZE     CHUNKS ALLOC_CL CHUNK_TYPE STRUCTURE            FUNCTION             CHUNK_COM            HEAP_ADDR
---------- ---------- ---------- -------- ---------- -------------------- -------------------- -------------------- ----------------
    272000        272       1000 freeabl           0 kccdef               qkxrMem              kccdef: qkxrMem      000000019FF49290
    128000        128       1000 freeabl           0 opn                  qkexrInitO           opn: qkexrInitO      000000019FF49290
    112568         56       2002 freeabl           0                      qosdInitExprCtx      qosdInitExprCtx      000000019FF49290
     96456         96       1000 freeabl           0                      qosdUpdateExprM      qosdUpdateExprM      000000019FF49290
     57320         57       1000 freeabl           0 idndef*[]            qkex                 idndef*[]: qkex      000000019FF49290
     48304         48       1000 freeabl           0 qeSel                qkxrXfor             qeSel: qkxrXfor      000000019FF49290
     40808         40       1005 freeabl           0 idndef               qcuAll               idndef : qcuAll      000000019FF49290
     40024      40024          1 freeabl           0 kafco                qkacol               kafco : qkacol       000000019FF49290
     37272        591         63 freeabl           0                      237.kggec            237.kggec            000000019FF49290
     16080       8040          2 freeabl           0 qeeRwo               qeeCrea              qeeRwo: qeeCrea      000000019FF49290
      8032       8032          1 freeabl           0 kggac                kggacCre             kggac: kggacCre      000000019FF49290
      8024       8024          1 freeabl           0 kksoff               opitca               kksoff : opitca      000000019FF49290
      3392         64         53 freeabl           0 kksol                kksnsg               kksol : kksnsg       000000019FF49290
      2880       2880          1 free              0                      free memory          free memory          000000019FF49290
      1152        576          2 freeabl           0                      16751.kgght          16751.kgght          000000019FF49290
      1040       1040          1 freeabl           0 ctxdef               kksLoadC             ctxdef:kksLoadC      000000019FF49290
       640        320          2 freeabl           0                      615.kggec            615.kggec            000000019FF49290
       624        624          1 recr           4095                      237.kggec            237.kggec            000000019FF49290
       472        472          1 freeabl           0 qertbs               qertbIAl             qertbs:qertbIAl      000000019FF49290
...

53 rows selected.

对比

SQL> @sqlmem b98yvssnnk13p
Show shared pool memory usage of SQL statement with SQL_ID b98yvssnnk13p

CHILD_NUMBER SHARABLE_MEM PERSISTENT_MEM RUNTIME_MEM
------------ ------------ -------------- -----------
           0        19470           7072        5560


TOTAL_SIZE   AVG_SIZE     CHUNKS ALLOC_CL CHUNK_TYPE STRUCTURE            FUNCTION             CHUNK_COM            HEAP_ADDR
---------- ---------- ---------- -------- ---------- -------------------- -------------------- -------------------- ----------------
      1640       1640          1 free              0                      free memory          free memory          00000001AF2B75D0
      1152        576          2 freeabl           0                      16751.kgght          16751.kgght          00000001AF2B75D0
      1040       1040          1 freeabl           0 ctxdef               kksLoadC             ctxdef:kksLoadC      00000001AF2B75D0
       640        320          2 freeabl           0                      615.kggec            615.kggec            00000001AF2B75D0
       624        624          1 recr           4095                      237.kggec            237.kggec            00000001AF2B75D0
       544        272          2 freeabl           0 kccdef               qkxrMem              kccdef: qkxrMem      00000001AF2B75D0
       472        472          1 freeabl           0 qertbs               qertbIAl             qertbs:qertbIAl      00000001AF2B75D0
       456        456          1 freeabl           0 opixpop              kctdef               opixpop:kctdef       00000001AF2B75D0
       456        456          1 freeabl           0 kctdef               qcdlgo               kctdef : qcdlgo      00000001AF2B75D0
       328         54          6 freeabl           0                      qosdInitExprCtx      qosdInitExprCtx      00000001AF2B75D0
       312        312          1 freeabl           0 pqctx                kkfdParal            pqctx:kkfdParal      00000001AF2B75D0
       296        296          1 freeabl           0                      unmdef in opipr      unmdef in opipr      00000001AF2B75D0
       256        128          2 freeabl           0 opn                  qkexrInitO           opn: qkexrInitO      00000001AF2B75D0
       256         42          6 freeabl           0 idndef               qcuAll               idndef : qcuAll      00000001AF2B75D0
       208         41          5 freeabl           0                      kggsmInitCompac      kggsmInitCompac      00000001AF2B75D0
       192         96          2 freeabl           0                      qosdUpdateExprM      qosdUpdateExprM      00000001AF2B75D0
       184        184          1 freeabl           0                      237.kggec            237.kggec            00000001AF2B75D0
...

1000:2

大对象LOB

浪费更多,(延迟上,带宽上,cpu上等等)

另外,不要在select *上select

SELECT
    id, a 
FROM (
    SELECT * FROM tl
)

SELECT * FROM (
    SELECT id, a FROM tl
)

PS作者还有很多工具 https://tanelpoder.com/psnapper/ https://0x.tools/ 有点意思,定位问题专家了学习关注一波


Read More

(译)std::any和void*的对比

翻译整理自这篇文章

std::any不是替代void*的产物,但是在某些场景下确实是更安全的替代品,并且 std::any也是构建在void*之上的

实际上就是记住类型信息的void* (type-aware void *)

struct any {
 void* object;
 type_info tinfo;
};

由于不是模版,不能携带类型信息,所以要有额外的绑定信息

而且 std::any还要做small object optimization, SOO (也叫SBO, small buffer optimization), 如果存个int/double指针只有两三个,不需要堆分配,直接SBO

此外,std::any还支持移动语义,偷数据

std::any a = std::string("Hello");

//value cast creates a copy
std::cout << std::any_cast<std::string>(a) << "\n"; //Hello

//reference cast
std::any_cast<std::string&>(a)[0] = 'h'; //cast as reference and change

//value is changed to "hello" now

//cast as const reference and print
std::cout << std::any_cast<const std::string&>(a) << "\n"; //hello

//  --- prints "Wrong Type!" below ---
try {
 std::cout << std::any_cast<double>(a) << "\n";
}catch(const std::bad_any_cast&) {
 std::cout << "Wrong Type!\n";
}

//Pointer cast example
//    ---     prints "hello" below   ---
if(auto* ptr = std::any_cast<std::string>(&a)) {
 std::cout << *ptr << "\n";
} else {
 std::cout << "Wrong Type!\n";
}

//move example
auto str = std::any_cast<std::string&&>(std::move(a));

//std::string in 'a' is moved
std::cout << str << "\n"; //hello

//string in 'a' is moved but it is not destroyed
//therefore 'a' is not empty.
std::cout << std::boolalpha << a.has_value() <<  "\n"; //true

//but should print ""
std::cout << std::any_cast<std::string>(a) << "\n"; //should be ""

std::any的一个典型应用场景

假设我们要实现一个带TTL的cache, key是string,值可以是任意

class TTLCache {
public:

 //Initializes with a given ttl (in seconds)
 TTLCache(uint32_t ttl):ttlSeconds(ttl){}

 //Adds an item to the cache along with the current timestamp
 bool add(const std::string& key, const std::any& value);

 //Gets a value from cache if exists
 // - otherwise returns empty std::any
 std::any get(const std::string& key);

 //Erases an item for a given key if exists
 void erase(const std::string& key);

 // Fires periodically in a separate thread and erases the items
 //  - from cache that are older than the ttlSeconds
 void onTimer();

 //...more interfaces...

private:

 //Values stored along with timestamp
 struct Item {
  time_t timestamp;
  std::any value;
 };

 //Expire time (ttl) of items in seconds
 uint32_t ttlSeconds;

 //Items are stored against keys along with timestamp
 std::unordered_map<std::string, Item> items;
};

暂时不考虑什么O1效率之类的问题

void *的一个典型应用场景

网络传输数据,user data,用void *表达任意二进制/字符串/协议数据

//Clients send requests to servers
struct Request {
 /*..Request fields..*/

 //User data can be set by clients
 void* userData;
};

//When a response comes to the client, it has
// - same user data that was attached to the Request
struct Response {
 /*..Response fields..*/

 //User data copied from Request
 void* userData;
};


void sendRequest() {
 Request req;
 //Prepare request
 req.userData = new std::string("state data"); //Attach user data
 //Send request to server...
}

//Process response 
void processResponse(Response& res) {
 auto state = (std::string*)(res.userData); //cast not type-safe
 //Process response using state data....
 delete state;  // delete state
}

发送数据new出来,处理数据知道数据是new的,处理后删掉

这种场景下,不类型安全且需要堆分配,没有SBO优化

可以用std::any轻松替换

//--- Suppose userData is std::any ---

void sendRequest() {
 Request req;
 req.userData = std::string("state data"); //attach user data
 //send request to server
}

void processResponse(Response& res) {
 auto& state = std::any_cast<std::string&>(res.userData); //throws if type does not match
 //Process response using state data....
 //No need to explicitly delete the user data.
}

优化也用上了,也不用担心类型的问题,也不用担心释放的问题,一箭三雕

这种user data之前有一种解决方案,std::shared_ptr<void> 这里有文章介绍, 简单说,就是利用shared_ptr构造的时候会记录类型,保证析构

译者注: 之前比较无知还反驳过同事不能这么用

std::shared_ptr<void> vps = std::make_shared<std::string>(); //OK 
vps.reset();  //Appropriate destructor is called

auto sps = std::static_pointer_cast<std::string>(vps); //OK with typecast
//sps is std::shared_ptr<std::string>

针对user data场景,直接把userdata类型换成shared_ptr<void>就行了

缺点在于用不上SBO优化,也有多余的记录开销,也没有移动内部对象的能力, 如果用不上c++17,临时用用也可以,最佳方案还是这个std::any


Read More

(译)搞定深度递归


原文链接

简单来说,作者写sql parse代码,可能需要分析表达式,但是表达式特别多,parse代码一半都是遍历二叉树,有递归的,这样递归深度就上去了

unique_ptr<Expression> analyzeExpression(AST* astNode) {  
   switch (astNode->getType()) {  
    case AST::BinaryExpression: return analyzeBinaryExpression(astNode->as<BinaryExpAST>());  
    case AST::CaseExpression: return analyzeCaseExpression(astNode->as<CaseExpAST>());  
    ...  
   }  
 }  
 unique_ptr<Expression> analyzeBinaryExpression(BinaryExpAST* astNode) {  
   auto left = analyzeExpression(astNode->left);  
   auto right = analyzeExpression(astNode->right);  
   auto type = inferBinaryType(astNode->getOp(), left, right);  
   return make_unique<BinaryExpression>(astNode->getOp(), move(left), move(right), type);  
 }  

表达式规模300000个,直接栈溢出了,不得不探索解决办法

__builtin_frame_address(0)

抓到堆栈溢出直接抛异常,解决的比较恶心

  • 表达式太大,直接这个查询就挂了
  • 其次,很多地方都这样遍历,不能确定哪里会有这种较大的场景,
  • 在优化的过程中,树的结构可能会调整,说不定更深了,表达式更大了,为了优化作出的努力反而因为栈溢出停了

指定堆栈?更恶心了

-fsplit-stack

编译器帮忙维护堆栈吧,这个flag就相当于编译器自动的分堆栈,但是实际测试中,编译器直接内部错误(ICE) ,也没有别人使用过的案例,放弃

boost.context

最终解决方案,用户态堆栈,且不用自己维护,代码改成这个样子

 unique_ptr<Expression> analyzeExpression(AST* astNode) {  
   if (StackGuard::needsNewStack())  
    return StackGuard::newStack([=]() { return analyzeExpression(astNode); });  
   ... // unchanged  
 }  

靠boost.context来切换堆栈,降低心智负担,代码也没有那么丑陋,可维护


ref

  • 他们还发了论文 https://db.in.tum.de/~radke/papers/hugejoins.pdf 这个论文内容说优化的,不是上面的工程实践内容

Read More

miniselect 一个选择算法库


原文链接 这个是作者用在clickhouse上的,抽出来做成公共库了。借着这个库重新复习一下选择/排序算法

选择算法,见图

Name Average Best Case Worst Case Comparisons Memory
pdqselect \large O(n) \large O(n) \large O(n\log n) At least \large 2n. Random data \large 2.5n \large O(1)
Floyd-Rivest \large O(n) \large O(n) \large O(n^2 ) Avg: \large n + \min(k, n - k) + O(\sqrt{n \log n}) \large O(\log \log n)
Median Of Medians \large O(n) \large O(n) \large O(n) Between \large 2n and \large 22n. Random data \large 2.5n \large O(\log n)
Median Of Ninthers \large O(n) \large O(n) \large O(n) Between \large 2n and \large 21n. Random data \large 2n \large O(\log n)
Median Of 3 Random \large O(n) \large O(n) \large O(n^2 ) At least \large 2n. Random data \large 3n \large O(\log n)
HeapSelect \large O(n\log k) \large O(n) \large O(n\log k) \large n\log k on average, for some data patterns might be better \large O(1)
libstdc++ (introselect) \large O(n) \large O(n) \large O(n\log n) At least \large 2n. Random data \large 3n \large O(1)
libc++ (median of 3) \large O(n) \large O(n) \large O(n^2 ) At least \large 2n. Random data \large 3n \large O(1)

作者总结了这些快速选择的使用特点

  • pdqselect 改自pdqsort 使用场景 Use it when you need to sort a big chunk so that \large k is close to \large n.
  • FR 快速选择算法,非常牛逼,大部分场景性能都很好,除非重复元素多
  • Median Of Medians,别用
  • Median Of Ninthers , AA大作,除非非常悲观,追求保底性能,否则别用
  • Median Of 3Random,别用
  • introselect ,也就是标准库的nth_select,别用
  • Median Of 3 别用
  • std::partial_sort or HeapSelect 非常随机的数据,用,否则别用

复习一下各种排序算法

排序算法 最好时间 平均时间 最坏时间 辅助空间
归并排序 \large O(n\log n) \large O(n\log n) \large O(n\log n) \large O(n)
堆排序 \large O(n\log n) \large O(n\log n) \large O(n\log n) \large O(1)
快速排序 \large O(n\log n) \large O(n\log n) \large O(n^2 ) O(logn) O(n)
自省排序 \large O(n\log n) \large O(n\log n) \large O(n\log n) -
PDQSort \large O(n) \large O(n\log n) \large O(n\log n) -
K路归并 - O(nklogk)) or O(nk^2) - -
并行归并 O((log n)^2) O((log n )^2) O((logn)3) -

简单原理归纳见参考链接,这里简单说一下

  • 归并,两指针比较移动 比较经典
  • 堆,构造一个最小堆/最大堆,然后重复构造交换节点等
  • 快排,选定一个pivot点,左边小于P右边大于P 子区间重复划分
    • 这个效率取决于P的选取,如果P选的不好,那就是最差的冒泡
    • 一般有三分采样 Median of three,也可以算个平均值,还有什么好的P选取法?
    • java DualPivotQuickSort,取两个Pivot,实现快速三向切分的快速排序,也是个有意思的点子
    • 数据集小,不如插入排序,也就产生了自省排序,也就是快排+插入+堆排序组合
  • pdqsort Pattern-defeating Quicksort,这也是主要说的,rust库用的sort_unstable就是这个,也是当前发展上最快的sort,论文关键字 BlockQuicksort: Avoiding Branch Mispredictions in Quicksort 实现看参考链接 是快排的优化版,参考链接的实现是std::sort的优化版,其中快排部分采用了论文提到的优化:部分打乱,小范围内交换位置等等避免分支预测

pdqsort gets a great speedup over the traditional way of implementing quicksort when sorting large arrays (1000+ elements). This is due to a new technique described in “BlockQuicksort: How Branch Mispredictions don’t affect Quicksort” by Stefan Edelkamp and Armin Weiss. In short, we bypass the branch predictor by using small buffers (entirely in L1 cache) of the indices of elements that need to be swapped. We fill these buffers in a branch-free way that’s quite elegant (in pseudocode):

buffer_num = 0; buffer_max_size = 64;
for (int i = 0; i < buffer_max_size; ++i) {
    // With branch:
    if (elements[i] < pivot) { buffer[buffer_num] = i; buffer_num++; }
    // Without:
    buffer[buffer_num] = i; buffer_num += (elements[i] < pivot);
}

上文作者介绍原理

  1. If there are n < 24 elements, use insertion sort to partition or even sort them. As insertion sort is really fast for a small amount of elements, it is reasonable
  2. If it is more, choose pivot:
    1. If there are less or equal than 128 elements, choose pseudomedian (or “ninther”, or median of medians which are all them same) of the following 3 groups:
      1. begin, mid, end
      2. begin + 1, mid – 1, end – 1
      3. begin + 2, mid + 1, end – 2
    2. If there are more than 128 elements, choose median of 3 from begin, mid, end
  3. Partition the array by the chosen pivot with avoiding branches
    1. The partition is called bad if it splits less than 1/8n elements
    2. If the total number of bad partitions exceeds \log n, use std::nth_element or any other fallback algorithm and return
    3. Otherwise, try to defeat some patterns in the partition by (sizes are l_size and r_size respectively):
      1. Swapping begin, begin + l_size / 4
      2. Swapping p – 1 and p – l_size / 4
      3. And if the number of elements is more than 128
        1. begin + 1, begin + l_size / 4 + 1
        2. begin + 2, begin + l_size / 4 + 2
        3. p – 2, p – l_size / 4 + 1
        4. p – 3, p – l_size / 4 + 2
      4. Do the same with the right partition
  4. Choose the right partition part and repeat like in QuickSelect
  • k路归并就是归并个数增加,并行归并就是开并发,不表

多提一点,基数排序 Radix Sort在某些场景上要比快排快的。当然,只能用于整数

n std::sort radix_sort
10 3.3 ns 284.2 ns
100 6.1 ns 91.6 ns
1 000 19.3 ns 59.8 ns
10 000 54.8 ns 46.8 ns
100 000 66.9 ns 40.1 ns
1 000 000 81.1 ns 40.8 ns
10 000 000 95.1 ns 40.7 ns
100 000 000 108.4 ns 40.6 ns

ref

  • 作者还提到了learned sort,机器学习真牛逼啊 https://blog.acolyer.org/2020/10/19/the-case-for-a-learned-sorting-algorithm/ 看不太懂
  • FR select https://zhuanlan.zhihu.com/p/109385885
  • https://rongyi.blog/fast-sorting
  • https://github.com/orlp/pdqsort/blob/master/pdqsort.h
  • sound of sorting https://panthema.net/2013/sound-of-sorting/
  • 基数排序快过std::sort https://sortingsearching.com/2015/09/26/radix-sort.html
    • 作者提到快过基数排序的 Kirkpatrick-Reisch 排序,感觉是基数排序的优化版https://sortingsearching.com/2020/06/06/kirkpatrick-reisch.html

Read More

flatbuffers使用细节以及和PB做一下对比


关注了anna用的也是fbs, smf rpc框架用的也是fbs

anna感觉技术更像是seastar那套

类似protobuf的介绍,先关注一下使用细节

// Example IDL file for our monster's schema.
namespace MyGame.Sample;
enum Color:byte { Red = 0, Green, Blue = 2 }
union Equipment { Weapon } // Optionally add more tables.
struct Vec3 {
  x:float;
  y:float;
  z:float;
}
table Monster {
  pos:Vec3; // Struct.
  mana:short = 150;
  hp:short = 100;
  name:string;
  friendly:bool = false (deprecated);
  inventory:[ubyte];  // Vector of scalars.
  color:Color = Blue; // Enum.
  weapons:[Weapon];   // Vector of tables.
  equipped:Equipment; // Union.
  path:[Vec3];        // Vector of structs.
}
table Weapon {
  name:string;
  damage:short;
}
root_type Monster;

Tables

  • 新增字段只能增加在table定义末尾, 比如旧版本schema定义 table { a:int; b:int;},新版本新增一个字段在末尾table { a:int; b:int; c:int; },那么

    • 用旧版本schema读取新的数据结构会忽略新字段 c 的存在,因为新增字段在末尾。
    • 用新版本schema读取旧的数据结构,将会取到新增字段的默认值。

    如果新增字段出现在中间,会导致版本不兼容问题。 table { a:int; c:int; b:int; } - 用旧版本schema读取新的数据结构,读取b字段的时候,会读取到c字段 - 用新版本schema读取旧的数据结构,读取c字段的时候,会读取到b字段

    如果不想新增字段到末尾,用id属性可以实现 table { c:int (id: 2); a:int (id: 0); b:int (id: 1); } 引入 id 以后,table 中的字段顺序就无所谓了,新的与旧的 schema 完全兼容,只要我们保留 id 序列即可。

    用id的方案和PB一致

  • schema不能删除任何字段,写数据的时候可以不再写废弃字段的值,在schema中把这个字段标记为deprecated,那么生成的代码里就不会出现废弃字段。table { a:int (deprecated); b:int; }

    • 用旧版本schema读取新的数据结构,将会取到字段a的默认值,因为不存在。
    • 用新版本schema不能读取也不能写入字段a,会导致编译错误
  • 可以改变字段类型,在类型大小相同情况下代码随之改动,是ok的。比如 table { a:uint; b:uint; } -> table { a:int = 1; b:int = 2; } 代码必须保证正确性。

Structs

和Table类似,区别是没有字段是optional的,字段不能增加或者废弃deprecation。Structs只接受标量或者其他Structs。使用这个对象的时候,必须是非常确定这个结构将来不会任何改动。Structs比Table内存占用更少,检索速度更快。

Types

build-in标量类型有

  • 8 bit: byte (int8), ubyte (uint8), bool
  • 16 bit: short (int16), ushort (uint16)
  • 32 bit: int (int32), uint (uint32), float (float32)
  • 64 bit: long (int64), ulong (uint64), double (float64) 括号内名称可以相互替换,不会影响代码生成。

build-in非标量类型有

  • 任何类型的数组。不过不支持嵌套数组,可以用 table 内定义数组的方式来取代嵌套数组。
  • UTF-8 和 7-bit ASCII 的字符串。其他格式的编码字符串或者二进制数据,需要用 [byte] 或者 [ubyte] 来替代。
  • table、structs、enums、unions

这些字段的类型一旦使用之后就无法再更改,可以用reinterpret_cast强转,比如如果当前数据的最符号位没有值得话,可以将uint强转成int

Attributes

Attributes 可以附加到字段声明,放在字段后面或者 table/struct/enum/union 的名称之后。这些字段可能有值也有可能没有值。

一些 Attributes 只能被编译器识别,比如 deprecated。用户也可以定义一些 Attributes,但是需要提前进行 Attributes 声明。声明以后可以在运行时解析 schema 的时候进行查询。这个对于开发一个属于自己的代码编译/生成器来说是非常有用的。或者是想添加一些特殊信息(一些帮助信息等等)到自己的 FlatBuffers 工具之中。

目前最新版能识别到的 Attributes 有 11 种。

  • id:n (on a table field) id 代表设置某个字段的标识符为 n 。一旦启用了这个 id 标识符,那么所有字段都必须使用 id 标识,并且 id 必须是从 0 开始的连续数字。需要特殊注意的是 Union,由于 Union 是由 2 个字段构成的,并且隐藏字段是排在 union 字段的前面。(假设在 union 前面字段的 id 排到了6,那么 union 将会占据 7 和 8 这两个 id 编号,7 是隐藏字段,8 是 union 字段)添加了 id 标识符以后,字段在 schema 内部的相互顺序就不重要了。新字段用的 id 必须是紧接着的下一个可用的 id(id 不能跳,必须是连续的)。
  • deprecated (on a field) deprecated 代表不再为此字段生成访问器,代码应停止使用此数据。旧数据可能仍包含此字段,但不能再通过新的代码去访问这个字段。请注意,如果您弃用先前所需的字段,旧代码可能无法验证新数据(使用可选验证器时)。
  • required (on a non-scalar table field) required 代表该字段不能被省略。默认情况下,所有字段都是可选的,即可以省略。这是可取的,因为它有助于向前/向后兼容性以及数据结构的灵活性。这也是阅读代码的负担,因为对于非标量字段,它要求您检查 NULL 并采取适当的操作。通过指定 required 字段,可以强制构建 FlatBuffers 的代码确保此字段已初始化,因此读取的代码可以直接访问它,而不检查 NULL。如果构造代码没有初始化这个字段,他们将得到一个断言,并提示缺少必要的字段。请注意,如果将此属性添加到现有字段,则只有在现有数据始终包含此字段/现有代码始终写入此字段,这两种情况下才有效。
  • force_align: size (on a struct) force_align 代表强制这个结构的对齐比它自然对齐的要高。如果 buffer 创建的时候是以 force_align 声明创建的,那么里面的所有 structs 都会被强制对齐。(对于在 FlatBufferBuilder 中直接访问的缓冲区,这种情况并不是一定的)
  • bit_flags (on an enum) bit_flags 这个字段的值表示比特,这意味着在 schema 中指定的任何值 N 最终将代表1 « N,或者默认不指定值的情况下,将默认得到序列1,2,4,8 ,…
  • nested_flatbuffer: "table_name" (on a field) nested_flatbuffer 代表该字段(必须是 ubyte 的数组)嵌套包含 flatbuffer 数据,其根类型由 table_name 给出。生成的代码将为嵌套的 FlatBuffer 生成一个方便的访问器。
  • flexbuffer (on a field) flexbuffer 表示该字段(必须是 ubyte 的数组)包含 flexbuffer 数据。生成的代码将为 FlexBuffer 的 root 创建一个方便的访问器。
  • key (on a field) key 字段用于当前 table 中,对其所在类型的数组进行排序时用作关键字。可用于就地查找二进制搜索。
  • hash (on a field) 这是一个不带符号的 32/64 位整数字段,因为在 JSON 解析过程中它的值允许为字符串,然后将其存储为其哈希。属性的值是要使用的散列算法,即使用 fnv1_32、fnv1_64、fnv1a_32、fnv1a_64 其中之一。
  • original_order (on a table) 由于表中的元素不需要以任何特定的顺序存储,因此通常为了优化空间,而对它们大小进行排序。而 original_order 阻止了这种情况发生。通常应该没有任何理由使用这个标志。
  • ‘native_*’ 已经添加了几个属性来支持基于 C++ 对象的 API,所有这些属性都以 “native_” 作为前缀。具体可以点链接查看支持的说明,native_inlinenative_defaultnative_custom_allocnative_typenative_include: "path"

Enums

enum Color : byte { Red = 1, Green, Blue } 定义一系列命名常量,每个命名常量可以分别给一个定值,也可以默认的从前一个值增加一。默认的第一个值是 0。enum声明的时候可以指定底层的整数类型,只能指定整数类型。 enum只能增加,不能删除或者废弃deprecation,因此代码必须保证兼容性,处理未知的枚举值。

Unions

Unions和Enums有很多类似之处,但是union包含的是table,enum包含的是scalar或者 struct。 可以声明一个 Unions 字段,该字段可以包含对这些类型中的任何一个的引用,即这块内存区域只能由其中一种类型使用。另外还会生成一个带有后缀 _type 的隐藏字段,该字段包含相应的枚举值,从而可以在运行时知道要将哪些类型转换为类型。

Namespaces

C++代码中生成namespace,Java代码中生成package

Includes

包含另一个schama文件,保证每个文件可以不被多次引用,但是只被解析一次。

Root type

声明序列化数据中的根表root table,在解析JSON数据时尤为重要,因为他们不包含对象信息。

设计建议

由于 FlatBuffers 的灵活性和可扩展性,将任何类型的数据表示为字典(如在 JSON 中)是非常普遍的做法。尽管可以在 FlatBuffers(作为具有键和值的表的数组)中模拟这一点,但这对于像 FlatBuffers 这样的强类型系统来说,这样做是一种低效的方式,会导致生成相对较大的二进制文件。在大多数系统中,FlatBuffer table 比 classes/structs 更灵活,因为 table 在处理 field 数量非常多,但是实际使用只有其中少数几个 field 这种情况,效率依旧非常高。因此,组织数据应该尽可能的组织成 table 的形式。

同样,如果可能的话,尽量使用枚举的形式代替字符串。

FlatBuffers 中没有继承的概念,所以想表示一组相关数据结构的方式是 union。但是,union 确实有成本,另外一种高效的做法就是建立一个 table 。如果这些数据结构有很多相似或者可以共享的 field ,那么建议一个 table 是非常高效的。在这个 table 中包含所有数据结构的所有字段即可。高效的原因就是 optional 字段是非常廉价的,消耗少。

FlatBuffers 默认可以支持存放的下所有整数,因此尽量选择所需的最小大小,而不是默认为 int/long。

可以考虑用 buffer 中一个字符串或者 table 来共享一些公共的数据,这样做会提高效率,因此将重复的数据拆成共享数据结构 + 私有数据结构,这样做是非常值得的。

CURD

// 写
flatbuffers::FlatBufferBuilder builder(1024);
// 用builder.createxx创建基本类型
auto weapon_one_name = builder.CreateString("Sword");
short weapon_one_damage = 3;
auto weapon_two_name = builder.CreateString("Axe");
short weapon_two_damage = 5;
// Use the `CreateWeapon` shortcut to create Weapons with all the fields set.
auto sword = CreateWeapon(builder, weapon_one_name, weapon_one_damage);
auto axe = CreateWeapon(builder, weapon_two_name, weapon_two_damage);

// Create the position struct
auto position = Vec3(1.0f, 2.0f, 3.0f);
// Set his hit points to 300 and his mana to 150.
int hp = 300;
int mana = 150;
// Finally, create the monster using the `CreateMonster` helper function
// to set all fields.
auto orc = CreateMonster(builder, &position, mana, hp, name, inventory,
                        Color_Red, weapons, Equipment_Weapon, axe.Union(),
                        path);
// You can use this code instead of `CreateMonster()`, to create our orc
// manually.
MonsterBuilder monster_builder(builder);
monster_builder.add_pos(&position);
monster_builder.add_hp(hp);
monster_builder.add_name(name);
monster_builder.add_inventory(inventory);
monster_builder.add_color(Color_Red);
monster_builder.add_weapons(weapons);
monster_builder.add_equipped_type(Equipment_Weapon);
monster_builder.add_equipped(axe.Union());
auto orc = monster_builder.Finish();
builder.Finish(orc);
// This must be called after `Finish()`.
uint8_t *buf = builder.GetBufferPointer();
int size = builder.GetSize(); // Returns the size of the buffer that
                              // `GetBufferPointer()` points to.
//这一套下来就可以直接拷贝/传range了



// 读
uint8_t *buffer_pointer = /* the data you just read */;
// Get a pointer to the root object inside the buffer.
auto monster = GetMonster(buffer_pointer);
auto hp = monster->hp();
auto mana = monster->mana();
auto name = monster->name()->c_str();
auto pos = monster->pos();
auto x = pos->x();
auto y = pos->y();
auto z = pos->z();

// 原地改,接口类似pb的mutable_xx

auto monster = GetMutableMonster(buffer_pointer);  // non-const
monster->mutate_hp(10);                      // Set the table `hp` field.
monster->mutable_pos()->mutate_z(4);         // Set struct field.
monster->mutable_inventory()->Mutate(0, 1);  // Set vector element.


参考链接

  • 教程 https://google.github.io/flatbuffers/flatbuffers_guide_tutorial.html
  • https://halfrost.com/flatbuffers_schema/

Read More

^