• 1. Folly调研 SAT-李耀春 2012年7月30日
  • 2. Folly是什么Facebook Open-source Library Facebook在6月份开源基于C++11的C++基础库 主要作者: Andrei Alexandrescu 目的不是替代std和boost库,而是对其的补充和增强 特点 高效:速度上的提高、内存优化 易用:令一些组件更加易用,如Synchronized定义了类似于Java中的synchronized关键字,使用一个block处理同步2
  • 3. Folly是什么发布在github上https://github.com/facebook/folly/ 包括: 主要代码:53个h文件,12个cpp文件 包括约40个组件,涉及 内存管理:如Arena 高性能的数据结构:如string、vector 有用的数据结构:如直方图、延时队列 多线程相关的优化:如线程本地内存、旋转锁 工具:如Hash的实现3
  • 4. C++11特性Lambda表达式 [capture](parameters)->return-type {body}   auto类型自动推导 auto x=0;  //0 是 int 类型,所以 x 也是 int 类型   auto c='a'; //char   auto d=0.5; //double   delete、default关键字 int func()=delete;  //父类的func不可用 A()=default;  //使用默认的构造函数 nullptr关键字,空指针常量,代替NULL和0强类型 void f(int);    void f(char *); f(0); //调用f(int) f(nullptr) //调用那个f(char *) 4
  • 5. C++11特性std::move将右值引用赋值给左值,右值被析构并置空 X a;       X&& b = move(a); // a被析构 atomic 5 std::atomic x,y; std::atomic z; void write_x_then_y() { x.store(true,std::memory_order_relaxed); // #1             y.store(true,std::memory_order_release); //保证 第#1句的x写入在y的写入之前 }   void read_y_then_x() {     while(!y.load(std::memory_order_acquire)); //保证y的读取在第#4句x的读取之前。所以如果y看到修改后的值,肯定 第#4句看到的也是x的新的值了。     if(x.load(std::memory_order_relaxed))   // #4                 ++z; }
  • 6. C++11特性std::unordered_map优化的map 无序的map实现 Map的查找是NlogN的小于比较,um是一次哈希+多次相等比较 大量数据时um会快很多6
  • 7. 组件分类1. 内存管理 Arena ThreadCachedArena ThreadLocal 2. 字符串 FBString Range Malloc 3. 向量 FBVector Traits small_vector sorted_vector_types 4. 多线程数据结构 AtomicHashArray AtomicHashMap ThreadCachedInt ProducerConsumerQueue ConcurrentSkipList 5. 多线程锁 SmallLocks RWSpinLock7
  • 8. 组件分类6. 整型编码 DiscriminatedPtr GroupVarint PackedSyncPtr 7. 有用的数据结构 dynamic Histogram TimeoutQueue 8. 工具 Bits Conv Format String Unicode Synchronized json Random Hash 9. 简化编程 eventfd Foreach IntrusiveList Likely Preprocessor ScopeGuard StlAllocator8
  • 9. 1. 内存管理 Arena/ThreadCachedArena 内存块管理类 ThreadLocal 线程本地存储方案9
  • 10. 提供了一个内存管理的类: 提供了申请内存接口allocate 当Arena类被析构的时候,所有申请的内存被释放 Arena Folly-内存管理10
  • 11. Arena用法 void* allocate(size_t size) void merge(Arena&& other) 内存块存储方式   11  typedef boost::intrusive::slist<     Block,     boost::intrusive::member_hook,     boost::intrusive::constant_time_size,     boost::intrusive::cache_last> BlockList;boost的单向链表 cache最后一个节点,因此在最后加节点是常数时间
  • 12. ArenaPtr_end_数据结构内存块申请算法 当申请的内存块的size小于链表末端的空闲空间(即end_-ptr_),则直接插入到链表末端的空间(以加快内存分配),否则分配内存块 分配内存块: - 当申请的内存块的大小大于minBlockSize(4M),则直接插入到链表的前面 - 当申请的内存块的大小小于或者等于minBlockSize(4M),则插入到链表的末端,并调整ptr_和end_的指向12
  • 13. ThreadCachedArena封装了Arena,每个线程都能获得自己的Arena,以加快内存申请速度。 在Arena中申请内存,当线程退出的时,申请的内存并入zombie 析构ThreadCachedArena的时候释放zombie中的内存ArenaArenaArenaZombie ArenathreadthreadthreadThreadCachedArena13
  • 14. ThreadCachedArena实现代码14调用ThreadLocal的reset方法设定线程退出的时候将内存并入zombie
  • 15. Folly-内存管理线程的私有数据存储方案,类似boost::thread_specific_ptrThreadLocal15
  • 16. ThreadLocal线程私有数据 线程访问全局数据的缺陷 当一个线程挂掉时影响到其他线程 数据同步影响效率 可被线程内的所有函数访问,对其他线程屏蔽 每个线程指定一个pthread_key_t,每个线程的pthread_key_t都不同,做到屏蔽16
  • 17. ThreadLocal特点: 比boost::thread_specific_ptr快4倍(GCC内置函数的使用) 速度与pthread_getspecific相似,但每个模板参数Tag只使用一个pthread_key_t 提供了accessAllThreads和自定义的析构函数 主要功能: 遍历线程私有对象accessAllThreads 线程退出后自动析构线程的私有对象17pthread_key_t的个数是有上限的,一般是1024
  • 18. ThreadLocal自动调用析构函数 customDeleterB通过THIS_THREAD当单个线程退出的时候调用 custonDeleterA通过ALL_THREAD当所有线程退出的时候调用18
  • 19. ThreadLocal使用accessAllThread访问线程私有对象19
  • 20. ThreadLocal数据模型nextIdfreeIdsheadStaticMetanextprevelementsThreadEntryelementsCapacitynextprevelementsThreadEntryelementsCapacityDeleterElementWrapptrDeleterElementWrapptrnextprevelementsThreadEntryelementsCapacityobjobjThread 1Thread 2Thread N……全局静态变量ididid20用__thread修饰,比pthread_getspecific快
  • 21. ThreadLocal优化: 使用static __thread声明ThreadEntry,实现同一个名字在不同线程访问的是不同对象,由于直接访问对象,效率比pthread_getspecific更高 分开了单个线程退出和整体析构,便于用户区分 使用freeIds保存可用的id,避免线程不断增加的时候id不断增大21
  • 22. 2. 字符串FBString.h 优化的string类 Malloc.h 内存分配的优化工具 Range.h 封装了StringPiece类,实现字符串的随机访问22
  • 23. Folly调研优化的String类FBString23
  • 24. FBString对string类做优化,主要优化点有: 内存模型 数据存储 内存分配 常用算法的优化 find算法 其他优化24
  • 25. FBString-数据存储根据存储的string的size,分成三种存储方式: Small:0-22个字符,存储到栈中,char[24] Medium:23-254个字符,使用malloc分配内存,使用eager-copy方式,即字符串的复制总是重新分配并拷贝内容 Large:大于254个字符,存储方式与medium相同,在字符串之前存储了引用计数,使用lazy-copy,即copy-on-write小块内存分配的代价会远远小于大块内存的分配,因此尽量避免了大块内存分配销毁的操作25std::atomic refCount_; 线程安全
  • 26. FBString-数据存储Copy-on-Write 优势 减少内存拷贝操作,以降低性能 缺陷 当需“线程安全”的时,由于“共享”,影响性能多个线程同时操作一个string的时候由于同步问题会产生多次拷贝26
  • 27. FBString-数据存储27
  • 28. FBString-数据存储代码上的数据表示28
  • 29. FBString-内存分配依赖Malloc.h,主要的优化是: 内存分配的大小经过goodMallocSize的过滤, 形成64b / 256b / 4KB / 4MB对齐,以提高分配/回收效率,减少内存碎片。 Realloc优化: jemalloc的rallocm代替std的realloc方法(jemalloc是FreeBSD上默认的分配器,在多线程并发环境下表现更好) 当没有使用jemallc,需要realloc的时候,根据内存块使用率,分情处理当内存使用率低于50%的时候,放弃使用realloc,因为realloc可能会拷贝整块内存,会导致效率低下,使用malloc-copy-free的方法 否则使用realloc,因为realloc有一定的可能性是会在当内存之后扩展出一块内存,而不需要拷贝整块内存。29
  • 30. FBString-内存分配realloc优化原内存块新内存块原内存块新内存块原内存块占用率小于50%占用率大于50%realloc扩张失败realloc扩张成功30
  • 31. FBString-find算法优化简化的Boyer-Moore算法,测试显示当查找成功时相比string::find提高了30x,失败时提高了1.5x算法介绍例如:ABCDEFABCDEFGEFG中查找DEFGE31
  • 32. FBString-find算法优化4. 跳过skip(4)的距离ABCDEFABCDEFGEFG,即从B开始找下一个lastNeedle(E),为ABCDEFABCDEFGEFG1. 目标字符串(DEFGE)的最后一个字符是E,lastNeedle=’E’,找到源字符串lastNededle的位置,ABCDEFABCDEFGEFG2. 从后往前比较,发现D!=G,说明未找到,需要找下一个可能出现的地方。ABCDEFABCDEFGEFG DEFGE3. 找下一个E的时候之前可以跳过不可能找到子串的字符串,skip为目标字符串(DEFGE)两个E的距离,skip=35. 不断循环查找,直到找到或者失败 ABCDEFABCDEFGEFG DEFGE32
  • 33. FBString-其他优化‘\0’的处理 对于字符串预留末尾的’\0’,只在调用c_str()或者data()的时候添加,减少了操作无用字符的开销。 word-wise copy 当是类型是small的时候,每次拷贝64bits数据 33
  • 34. Range封装字符串的随机访问类StringPiece,与boost的Range相同。 实现 存储了两个指针b_和e_,分别为一个字符串片段的起始地址和结束地址,访问时访问地址偏移量34
  • 35. 3. 向量FBVector 优化的std::vector Small_vector 优化buffer的vector Sorted_vector_types 有序的vector35
  • 36. Folly-向量实现了类似于std::vector的容器,主要优化: 内存块扩张 内存分配 元素拷贝FBVector36
  • 37. FBVector实现 37b_e_z_b_e_z_b_e_z_insert & erasereserve先原地扩展,若失败使用malloc-copy-free判断是否带有trivial_destructorpush_back & pop_back
  • 38. FBVector-内存扩张指容器内元素的个数超过内存块限制时,需要对内存进行扩张(指数级) gcc使用指数系数2 FBVector选择系数1.5。 系数选择目标:希望第n次的扩张能够重用前n-2次释放的内存,而不至于内存永远向后扩展。38
  • 39. FBVector-内存扩张系数选择2的时候,无法重用之前释放的内存块如要重用需要满足:图形化求解得到: 当k取1.5的时候,在4次重分配内存之后就可以重用内存 k为1.45的时候,需要3次 k为1.3的时候只需要2次 FBVector选择1.539
  • 40. FBVector-内存分配使用jemalloc和Malloc.h 在reserve的时候尝试使用jemalloc做原地realloc,失败则使用malloc申请新的内存块 内存分配大小使用64B / 256B / 4KB / 4MB对齐,以提高分配/回收效率,减少内存碎片。40
  • 41. FBVector-对象重定位FBVector只支持isRelocatable(定义在Traits.h)的对象,目的: 当对象需要被移动的时候,只要移动内存即可,而不需要调用构造、析构函数,以提高数据拷贝的效率。 isRelocatable的定义:只需要拷贝内存就可以完成对象的拷贝和移动,而不需要调用构造/析构函数,只有两种: 使用内部指针 被别的对象指向41
  • 42. Folly-向量一种特殊的vector,对buffer进行优化Small_vector42
  • 43. Small_vector用法与std::vector几乎一样,buffer的优化: 先把元素存在栈中,当超过一定的上限,再放到heap上,以减少malloc,例如43
  • 44. Small_vector主要用于: 数据量较小并且只需要暂时放在vector中的数据,可以避免使用malloc Vector的大小的上限是确定的,并且经常需要查询 Vector数量比较大,并且不想浪费空间来跟踪vector的size。 支持了如下的vector策略: NoHeap:不使用heap,当溢出的时候抛出std::length_error OneBitMutex:使用size_type中的一个bit来提供spin lock :自定义跟踪vector的size的时候空间大小44
  • 45. Small_vector数据结构45
  • 46. Sorted_vector_types定义两个类(sorted_vector_set和sorted_vector_map),分别在sorted_vector上实现了类似于set和map的行为 特点: 有序的vector,insert和erase是O(N)的 find和[]方法采用二分法查找,因此速度较快 支持自定义扩张内存的函数,当insert的时候被调用 自定义的compare函数 内部实现是封装std::vector 适用于插入/删除操作远远少于查找的情况46
  • 47. 4. 多线程数据结构ThreadCachedInt 多线程自增整型变量 AtomicHashArray AtomicHashMap 高性能的原子Hash Map 47
  • 48. Folly-多线程数据结构一个整型的类,用于多线程同时操作这个自增的整型时,在保证精度不丢失的情况下提供极高的性能,比std::atomic_fetch_add快10倍。 ThreadCachedInt48
  • 49. ThreadCachedInt提供两种读的模式: readFast:load的时候可能数据是以前的,但是速度很快(使用single load)。 readFull:获得准确的值,但是相比readFast会慢很多。(获得一个互斥锁,然后从所有线程的local counters中遍历获得准确的值)49
  • 50. ThreadCachedInt用法多线程操作TCInt,readFast的值不一定是准确的值,而readFull是准确的值50
  • 51. ThreadCachedInt实现 readFast:直接调用load readFull:使用ThreadLocal遍历所有线程的私有变量求和51
  • 52. Folly-多线程数据结构几乎无锁的高性能原子Hash MapAtomicHashMap52
  • 53. AtomicHashMap优点: 高性能,特别是在多线程要求非常高的环境中 相比tbb::concurrent_has_map快2-5倍 好的内存利用率,容量不过估的前提下 良好的分散性能?( Good fragmentation properties ) 查找快速 缺陷: Key只支持int32、int64 必须指定empty、locked、erased的key 性能会随着初始尺寸的容量的增大线性降低 最大的size被限制在初始size的18倍 擦除的内存块不被释放 53
  • 54. AtomicHashMap数据结构nullnullnullnullnullnullnullAtomicHashMapnullnullnullnullnullnullnullnullAtomicHashArrayAomicHashArray的指针数组 开始初始化1个,其他都null存储数据的数组,因此cache性能好54
  • 55. AtomicHashMapInsert 从第一个SubMap查找位置,若满则找下一个 若全满,则申请新的SubMap,大小为 第一个SubMap的capacity * 1.8 ^ (nextIdx - 1) 冲突解决:线性 Find 从第一个SubMap开始,Hash-mod定位,线性无等待查找 Erase 标记位置为擦除,此位置不可用 查找位置:hash-mod找到位置,lock位置的数据,使用compare_and_swap比较key,unlock55
  • 56. Folly-多线程数据结构并发的SkipList56ConcurrentSkipList
  • 57. ConcurrentSkipList跳表57
  • 58. ConcurrentSkipList用法58
  • 59. ConcurrentSkipList特点: 较小的内存开销:比std::set小了~40% Read操作时无锁几乎无等待的 快速,多线程环境下比带有一个RWSpinLock的std::set快了10倍以上 支持GC 缺陷: 写操作比std::set慢30% 每一个跳表都需要一个4-word的头结点 当元素个数较小(<1000)时,比std::set慢 只支持x64 释放的节点不可被重用59
  • 60. ConcurrentSkipList数据结构60头结点FlagheightsplockdatasizerecyclerrefsdirtynodesConcurrentSkipListnullptrMicroLock用于保护nodes的访问每个node独立的锁
  • 61. ConcurrentSkipListGC实现: ConcurrentSkipList中包含Recycler,记录引用次数 每次调用Recycler的release减少一次引用 引用次数为1时,调用release,将nodes析构61
  • 62. Folly-多线程数据结构队列长度确定的无等待的只有单producer单consumer的生产者消费者队列ProducerConsumerQueue62
  • 63. ProducerConsumerQueuewrite,若满返回falseread,若空返回falseC++11:内存的原子操作顺序 Relaxed:任意顺序 Acquire:后面的load不会先于此 Release:前面的store不会后于此63
  • 64. 5. 多线程锁SmallLocks.h 很小的互斥锁 RWSpinLock.h 读写锁64
  • 65. Folly-多线程锁定义了两个非常小的互斥量类型,主要用于highly memory-constrained环境,有两个锁,分别是 MicroSpinLock是一个单字节的锁 PicoSpinLock使用一个整型(16,32,64位)中的一个未被使用的位(一般是最高位)作为锁SmallLocks65
  • 66. SmallLocks-MicroSpinLock一个8位的整型(uint8_t)表示锁,两种状态: FREE LOCKED 使用汇编进行原子操作66
  • 67. SmallLocks-PicoSpinLock保存一个整型,以它的最高位作为锁,通过高位读写进行获得和释放锁。 定义getData和setData的方法得到/设置存储的数据(data的高位必须是0)……lockdata67
  • 68. SmallLocks-PicoSpinLock调用”pause”让出CPU68
  • 69. Folly-多线程锁实现两个读写锁 RWSpinLock RWTicketSpinLock RWSpinLock69
  • 70. RWSpinLock两个读写锁,比pthread_rwlock快并且低开销: RWSpinLock: 当线程数量小于CPU数量的时候性能较好 线程数量大的时候会导致写饥饿(写锁获得必须在读锁都释放之后才能被获得) 最多支持2^30 – 1个reader RWTicketSpinLock 解决读写不平衡问题 支持32位和64位模式,32位支持2^8 – 1个reader,64支持2^16 – 1个reader70
  • 71. RWSpinLock30 bits1bit1bit读锁计数更新锁标记写锁标记数据结构:一个32位的整型表示锁支持: 写锁(Lockable):只有在读、写、更新素 读锁(SharedLockable):没有写锁的时候可以获得 更新锁(Upgradable):与读锁一样,但可以升级成写锁,或者降级成读锁71
  • 72. RWSpinLock写锁Lockable 上下文切换优化:不断尝试申请写锁,多次失败(1000次),主动让出CPU,并且,以后的每次申请失败都让出CPU好处:避免了过度频繁的上下文却换 缺点:加剧了写饥饿问题72
  • 73. RWSpinLock读锁SharedLockable 同样是不断尝试申请锁,多次申请失败让出CPU,当申请成功过的时候给lock加4,即在高30位的计数器上加1,当释放锁的时候减1。73
  • 74. RWSpinLock更新锁UpgradedLockable 申请更新锁,同样多次申请失败(已经拥有更新锁或者写锁)让出CPU。 能够被升级成写锁或者读锁,做法是先释放更新锁,再加锁,使用原子操作完成。74
  • 75. RWTicketSpinLock写优先的读写锁 解决方法 当有一个线程在等待写锁的时候,读锁是无法再被加上的,直到所有读锁被释放的时候,写锁就可以被加上,一定程度平衡了读写不平衡。75
  • 76. RWTicketSpinLock数据结构:一个32/64位的Union类型readWriteuserswritereadticketwhole根据write、read、user判断读写锁申请的条件76
  • 77. RWTicketSpinLock读锁 只有当users=read的时候,读锁才可以被加上,否则申请锁失败。 读锁被加上后,read++,users++,封锁了写锁的申请,但是读锁还是可以申请 Unlock的时候, write++写锁 只有当users=write的时候,写锁才可以被加上,否则申请锁失败。 写锁被加上后,users++,封锁了读锁和写锁的申请 Unlock的时候,read++,write++写锁等待 给users++,封锁了读锁的申请,然后等待user++之前的users==write的时候获取写锁。 77
  • 78. RWTicketSpinLockUsers=0 Read=0 Write=0申请读锁成功Users==read Users++ read++初始化1个读锁Users==read Users++ read++2个读锁Users=1 Read=1 Write=0Users=2 Read=2 Write=0申请读锁成功Users=2 Read=2 Write=0申请写锁失败Users≠writeUsers=2 Read=2 Write=1释放读锁Write++Users=3 oldUs=2 Read=2 Write=1Users≠write Users++等待write==oldUs申请写锁等待Users=3 oldUs=2 Read=2 Write=1Users≠read申请读锁失败Users=3 oldUs=2 Read=2 Write=2Write++释放读锁Users=3 Read=2 Write=2自动申请写锁Write==oldUs Users=3 Read=2 Write=2申请读锁失败Users≠readUsers=3 Read=3 Write=3释放写锁Read++ Write++2个读锁1个读锁1个读锁1个读锁0个锁1个写锁1个写锁0个锁算法举例说明释放成功失败78等待
  • 79. RWTicketSpinLock优化: 使用并行的SSE2并行指令,对多个连续地址的整数一个指令完成++操作 使用Pause指令让出,一方面可以降低CPU能耗,另外可以帮助CPU优化指令。 减少分支预测,令old.user=old.read,判断user和read是否相等的逻辑延迟到CAS操作。79
  • 80. 整型编码DiscriminatedPtr 类型安全的通用指针 GroupVarint 压缩整型变量 PackedSyncPtr 专业化的整型用法 80
  • 81. Folly-整型编码一种类型安全的通用指针,类似于boost::variant,只能用于指针,即可以指向有限个类型的指针 DiscriminatedPtr81
  • 82. DiscriminatedPtr用法举例限定只能指向 Void Int Foo Bar使用visitor处理重载82
  • 83. DiscriminatedPtr16 bits48 bits指针地址类型index数据结构:高16位表示指针类型,低48位表示地址 原因:在64位系统中,对于指针来说高16位是用不到的,对于内存是浪费的。Vistor:实现了一个visitor,当调用重载函数的时候选择存储在DiscriminatePtr中的适当的类型。83
  • 84. 6. Folly-整型编码将一组整型编码成一种变长的表示方式,以节省内存空间GroupVarint84
  • 85. GroupVarint将一组整型(4个32位或者5个64位整型)编码成一种变长的表示方式,以节省内存空间。 主要提供的编码形式: Encode 把一组4个32位的整型编码到变长的5到17个bytes中 第一个byte表示长度。 Encode 把一组5个64位的整型编码到变长的7到42个bytes中 前两个bytes表示长度。85
  • 86. GroupVarint使用方法86
  • 87. GroupVarintEncode 第一个字节表示每个整型需要的byte数量 00表示1字节,01表示2字节,10表示3字节,11表示4字节, 后面的每个整型采用1-4bytes变长的存储 00010010abcd87
  • 88. GroupVarintEncode 前两个字节表示每个整型需要的byte数量 000表示1字节,001表示2字节,010表示3字节,011表示4字节……111表示8字节 后面每个整型采用1-8个字节的变长表示00000100abcd0010000e88
  • 89. Folly-整型编码高度专业化的数据结构,由 旋转锁 + 整数 + 指针 组成PackedSyncPtr89
  • 90. PackedSyncPtr高度专业化的数据结构,其组成是:共64位,最高位是旋转锁,次15位作为一个整型使用,后48位为一个指针。 原因: 在实际应用中,所有的指针的高两个字节都被置为了0,为了减少内存的浪费 指针中直接存储lock提高了cache的性能。(没有额外的cache missing或者false sharing) 使用了简单的spinlock机制,获得/释放锁的代价很低 1b15 bits48 bits旋转锁整型指针90
  • 91. PackedSyncPtr用于多线程、需要size的容器,如vector。 实现: Get、Set:获得、设置低48位指针 Lock、unlock:锁操作 Extra、SetExtra:得到、设置15位整型,前提是高位是0。91
  • 92. PackedSyncPtr用法:例如vector把size存在extra的15位整数中取指针的地址指向的位置存储数据申请锁和释放锁快速获得开始和结束92
  • 93. 7. 有用的数据结构dynamic 类似于python的运行时动态类型 Histogram 直方图统计类 TimeoutQueue 延时队列93
  • 94. Folly-有用的数据结构类似于python的运行时动态类型,当赋值的时候确定类型dynamic94
  • 95. dynamic用法:主要目的:构造一个复杂类型,能方便地编程,用于json当使用时类型出错,抛出Type_Error95
  • 96. dynamic支持类型 fbvector bool double int64_t fbstring 复杂数据结构 map 方法 iterator Push、pop 运算符(如+-*/) as Find At [] 类型判断(如isString) 调用时,如果类型不支持,抛出异常Type_Error96
  • 97. dynamic数据结构 使用union保存数据dynamic d = 12 过程: 自动调用dynamic(T t),构造dynamic 调用构造函数dynamic(dynamic d)C++11:unordered_map 查找、插入、删除平均常数复杂度97
  • 98. dynamicdynamic(T t)获得数据类型 填入data中获得对应类型的地址 设置type_字段98
  • 99. Folly-有用的数据结构直方图工具类,用于跟踪数据的总体分布Histogram99
  • 100. Histogram特点: 只支持等宽的bucket(如定义一个间隔为100的,范围从0到400平均分布的直方图,bucket数量为4。 ) 查看每一个bucket数据(count) 估计第N个百分比的数据分布(如落在中间的值) bucketfolly::Histogram latencies(100, 0, 400); 100
  • 101. Histogram数据结构HistogramHistogramBucketsbucketSize_:bucket的个数Min_: 范围下限Max_:范围上限sumcountsumcountsumcountsumcountsumcountsumcountvectorSum:bucket中元素的和 Count:落在bucket的元素的个数101
  • 102. Histogram实现 addValue:直方图中插入数据 先定位到对应的bucket 再加入数据(sum+=val;count++) getPercentileEstimate:估计百分比 先找到百分比落在的bucket,可以得到 bucket里最小值low,最大值high,平均值avg,数据的个数count,百分比范围下限lowPct,百分比范围上限highPct 假设bucket里的数据分布式平均分布的,取到平均分布中的估计值。102
  • 103. Folly-有用的数据结构一个延时队列: 向队列中加入回调函数和执行时间,当调用run中指定的时间超过执行 时间时,按照顺序执行回调函数TimeoutQueue103
  • 104. TimeoutQueue支持事件类型 Once:执行一次,执行完之后剔除队列 Repeat:执行完之后,计算下次执行时间,重新加入队列 用法示例104
  • 105. TimeoutQueuecb19cb210cb311RepeatOnceOnceTypeCallbackExpirationrunOnce(10)cb19cb210cb311RepeatOnceOncerunOnce(20)cb311cb119OnceRepeatcb311cb119OnceRepeatcb129Repeat操作队列回调函数执行情况执行后队列105
  • 106. 8. 工具Bits Conv Format String Unicode Random Synchronized json dynamic Hash106
  • 107. BitsBits,底层的位操作工具类,提供了: findFirstSet(x),找到整型数据的第一位 findLastSet(x) ,找到整型数据的第一位 nextPowTwo(x),大于等于x的2的阶乘 Endian,native, big, and little的表示方法之间的转换BitIterator,整型数的位的遍历 iteratorfindFirstSet(BitIterator begin, BitIterator end),返回[begin, end)的第一个bit(1)107
  • 108. Conv一些类型转换函数: 整型 -> 整型 浮点 -> 浮点 任何 -> string 整型 <-> string 浮点 <-> string 整型 <-> 浮点 枚举 <-> 任何108
  • 109. Format数据格式化的工具 例如:format("The answers are {} and {}", 23, 42)为"The answers are 23 and 42"“提供了一个快速、强大、类型安全、灵活的文本格式方法,使用类python的str.format的格式语言,可格式化string、number、dynamic,能够从随机访问的容器中提取出值,很多情况下比sprintf快” 109
  • 110. String有用的string工具集合,主要有: std::string <=> FBstring 互转工具 C风格转义字符串工具 特殊字符的反斜杠转义,如”->\” 不可打印的ASCII字符转义到八进制表示方法,如->\376,原因是八进制表示法不会占用超过3个字符。 stringPrintf工具 类似于printf,不过将格式化的字符串返回给 stringprettyPrint (支持时间、容量等常见单位) hexDump工具 输入字符串,输出16byte每行的的16进制表示方式 errnoStr\exceptionStr 输入错误号,返回关于这个错误的描述 demangle(串化C++类型) 把类型转化成一个可读的字符串 Split (分拆字符串),字符串拆分成一个list110
  • 111. Unicode & RandomUnicode: 实现了一个codePointToUtf8的函数,实现unicode码点到utf-8编码的转换。 Random: 只定义了一个函数:randomNumberSeed()。使用当前时间和PID来产生随机数种子。111
  • 112. Synchronized一种好的同步编程范式,替换以前的复杂、适用性差、易出错的同步相关的编程方法,例如112
  • 113. json将dynamic类型序列化成json的fbstring形式,提供了如下接口: dynamic parseJson(StringPiece) 从json的StringPiece中转化成一个dynamic对象。 fbstring toJson(dynamic const&) 将dynamic对象转化成json的fbstring。 fbstring toPrettyJson(dynamic const&) 功能同上,但是有着比较好的格113
  • 114. Hash实现了一些流行的Hash函数: Hash_128_to_64:Google的cityhash函数Hash128to64,用于将多个64位的hash减少到单个的64位hash Twang_mix64:Thomas Wang 64 mix hash function twang_32from64:Thomas Wang downscaling hash function jenkins_rev_mix32:Robert Jenkins' reversible 32 bit mix hash function fnv32:Fowler / Noll / Vo (FNV) Hash(http://www.isthe.com/chongo/tech/comp/fnv/) hsieh_hash32:Paul Hsieh: http://www.azillionmonkeys.com/qed/hash.html114
  • 115. 9. 简化编程eventfd Foreach IntrusiveList Likely Preprocessor ScopeGuard StlAllocator 115
  • 116. Eventfd & Foreacheventfd 封装了与Linux内核系统调用相同的eventfd接口,用于并发服务器的通知(唤醒)其他进程(线程),实现与linux内核一样。 Foreach 封装一个 FOR_EACH (i, c) statement 替代原来for语句 for (Container::iterator i = c.begin(); i != c.end(); ++i) statement 116
  • 117. IntrusiveList对boost::intrusive_list做了一层封装,主要是简化变量名 封装两个类,分别是 IntrusiveList:一直使用auto_unlink的intrusive list,其size时间为Ncounted IntrusiveList:常量时间计算size的intrusive list117
  • 118. Likely利用GCC内建函数__builtin_expect做if条件的预测,以达到if判断的速度优化。 封装了LIKELY(x)和UNLIKELY(x): LIKELY(x)表示告诉编译器if语句是1的可能性比较大,返回依旧为x UNLIKELY(x)表示告诉编译器if语句是1的可能性比较小,返回依旧为x118
  • 119. Preprocessor一些程序上的宏的定义,获取可变参数的第1个或第2个参数,用于模板编程。 例如,提取出函数的第二个参数119
  • 120. ScopeGuard & StlAllocatorScopeGuard 保证当离开一个scope的时候一个函数(如资源释放函数)被执行,如 makeGuard([&] { friends_.pop_back(); }) 将friends.pop_back()函数声明为ScopeGuard对象,当这个对象被析构的时候,执行friends.pop_back StlAllocator STL分配器,包装简单的分配/取消分配接口。为了兼容gcc 4.6.2120
  • 121. Folly调研谢谢121