分类: 技术

  • 文件系统对比 btrfs vs zfs

    btrfs vs zfs

    btrfs是一个支持写时复制的文件系统,同时zfs是另外一个也被广泛使用的文件系统。

    btrfs使用红黑树,zfs使用另外一套技术,zfs在大型机器上似乎是被广泛使用,处理大型文件的性能上优于btrfs,并且存储文件没有上限,btrfs文件数量上有上限,同时处理小文件更快。

    具体来说优劣势:

    btrfs在Linux内核直接有支持,内存使用更小

    zfs更适合大负载场景,支持数据自动还原,跨平台。

    btrfs vs ext4

    因为btrfs支持COW,所以在写入小文件时效率可能更低。相比ext4,btrfs更适用于需要快照、数据完整性检查和内置RAID等功能的高级用户。

    ext4是使用日志记录,在每次写入都会记录,虽然如此,但是ext4在日常使用效率比btrfs要好。所以如果对于快照和RAID支持没有需求的人应该选择Ext4。

  • python 源码路径组织

    python源码路径组织:

    • Include: 包含了python提供的头文件,如果需要自己编写扩展python,需要用到这里的头文件;
    • Lib: 包含python自带的标准库,都是用python写的。
    • Modules: 包含所有C语言编写的模块,都是对速度要求比较高的模块。
    • Parser: 包含解释器的Scanner和Parser的部分,对python源代码进行词法分析和语法分析的部分;
    • Objects: 该目录包含了所有Pyhotn的内建对象,包括整数、list、dict等。同时,还包括了python在运行时需要的所有内部使用对象的实现。
    • Python: 包含解释器中Compiler和执行部分,是python运行核心所在。
  • 垃圾回收算法总结

    垃圾回收算法笔记

    一、标记清除:

    分为两个阶段:标记阶段和清除阶段;从根节点标记所有未被引用的垃圾对象,然后清除阶段删除。

    优点:

    • 存活对象较多的情况下高效
    • 适用于年老代
    • 实现简单, 容易和其他算法组合

    缺点:

    • 容易产生内存碎片
    • 分配速度不理想,每次分配都需要遍历空闲列表找到足够大的分块
    • 与写时复制技术不兼容,因为每次都会在活动对象上打上标记
    • 大量的内存碎片会导致大对象分配时可能失败,从而提前触发了另一次垃圾回收动作
    • 具有引用关系的对象可能会被分配在堆中较远的位置,这会增加程序访问所需的时间,即「访问的局部性(Locality)」较差。

    二、复制算法:

    从根节点扫描,标记所有存活对象,并且复制到新的内存,回收旧内存。现在的商业虚拟机都采用这种收集算法来回收新生代。

    优点:

    • 存活对象比较少的情况下高效
    • 良好的局部性
    • 不会发生碎片化
    • 适用于年轻代(即新生代):基本98%的对象都是“朝生夕死”

    缺点:

    • 最多只能使用一半的堆空间,因此堆的使用率不高;
    • 需要一块空的内存空间;需要复制移动对象;

    三、标记压缩

    标记压缩算法是一种老年代的回收算法,它在标记清除算法的基础上做了一些优化。从根节点对所有可达对象做一次标记,然后将存活的对象压缩到内存的一段,之后清理边界空间。

    优点:

    • 这种算法避免了碎片产生
    • 也不需要两块相同的内存空间

    缺点:

    • 压缩的过程需要多次搜索

    四、分代收集算法

    分代收集算法是目前JVM虚拟机使用的回收算法。它将内存分为各个年代。一般情况下将堆区划分为老年代和新生代,在堆区之外还有一个代就是永久代。

    在不同的代使用不同的算法,从而使用最适合的算法。

    • 新生代 = 生成空间 + 2 * 幸存区 复制算法
    • 老年代 标记-清除算法

    五、引用计数

    引用计数,就是记录每个对象被引用的次数,每次新建对象、赋值引用和删除引用的同时更新计数器,如果计数器值为0则直接回收内存。

    优点:

    • 可即可回收垃圾
    • 最大暂停时间短

    缺点:

    • 计数器的增删处理重,除了数量多,而且在删除容器的时候,需要遍历所有的对象修改引用计数。
    • 计数器需要占用很多空间
    • 循环引用无法回收

    六、增量式GC

    将GC的阻塞任务拆分成少量多次,减少暂停用户程序的执行。

    三色标计算法:

    • 白色:还未搜索过的对象
    • 灰色:正在搜索的对象
    • 黑色:搜索完成的对象

    三色过程:

    • 根查找阶段:对能直接引用的对象打上标记,堆放到标记栈里
    • 标记阶段:从标记栈中取出对象,将其子对象涂成灰色;这个阶段不是一下子处理所有的灰色对象;
    • 清除阶段:将没被标记的白色连接到空闲链表,并重置已标记的对象标记。

    读屏障和写屏障

    原因:

    • 多标:在对象被标记为灰色之后,父节点解除了引用关系,那本来应该被删除的对象就会被延迟删除;
    • 漏标:在对象被标记之后,对象断开子节点A同时A被父节点引用,但父节点已经被标记为黑色,不会再重新访问,因此A节点会被标记成白色删除,这是不可接受的。

    漏标的充分必要条件是:

    • 应用线程插入了一个从黑色对象(A)到白色对象(E)的新引用。
    • 应用线程删除了从灰色对象(C)到白色对象(E)的直接或者间接引用。

    避免漏标打破上述任何一个条件即可:

    • 这里在第一个条件触发时增加写屏障,修改黑色或者白色为灰色;并且在渐进式GC里对白色对象触发度屏障。
    • 第二个条件触发写屏障,当删除关系时触发写屏障,将这些关系都记录下来,最后重新扫一次。

    优点:缩短最大暂停时间

    缺点:降低了吞吐量

    JVM垃圾回收有两种类型:Minor GC和Full GC。

    Minor GC

    只回收新生代,这里非常频繁且对象大多数死亡频繁,所以选择速度快效率高的算法。

    Full GC

    对整个堆进行回收,包括新生代和老年代,所以比Minor GC要慢,应该尽可能减少Full GC的次数。

    python垃圾回收

    python分配<512btype的内存时使用内存池,释放时不会还给系统;分配>512字节的对象时会直接使用C的allocate分配和管理。

    标准CPython实现的垃圾收集器有两部分组件构成,一部分为引用计数模块(reference counting collector), 另一部分为分代垃圾回收器(generational garbage collector)。

    引用计数是本意,但是无法处理循环引用,所以补充了分代垃圾回收器。

    有三种情况会触发垃圾回收:

    • 调用gc.collect(),需要先导入gc模块。
    • 当gc模块的计数器达到阀值的时候。
    • 程序退出的时候。

    当循环引用的两个对象都有del时,python不知道先调用哪个导致不会释放,把它们标记为:uncollectable。

      这个方法涉及到之前说过的分代回收的策略。python中默认把所有对象分成三代。第0代包含了最新的对象,第2代则是最早的一些对象。在一次垃圾回收中,所有未被回收的对象会被移到高一代的地方。

    gc.get_threshold()
    这个方法返回的是(700,10,10),这也是gc的默认值。这个值的意思是说,在第0代对象数量达到700个之前,不把未被回收的对象放入第一代;而在第一代对象数量达到10个之前也不把未被回收的对象移到第二代。可以是使用gc.set_threshold(threashold0,threshold1,threshold2)来手动设置这组阈值。

    Unreal GC

    虚幻的GC挺复杂的,因为虚幻本身提供了一套非常复杂且自由的系统。

    只看UObject类的话就会简单一些,它是Unreal的基础类,它使用的是标记-清除算法,而不是传统类似于shared_ptr这样的引用计数。

    学习文档:

    https://aijishu.com/a/1060000000080557

    https://www.jianshu.com/p/a8a04fd00c3c

    https://developer.aliyun.com/article/777750

    https://zhuanlan.zhihu.com/p/83251959

    https://dreamgoing.github.io/Python%E5%9E%83%E5%9C%BE%E5%9B%9E%E6%94%B6.html

    https://testerhome.com/topics/16556

  • C++ 继承和虚拟继承的内存分布

    菱形继承

    菱形继承:菱形继承的问题在于数据冗余和二义性。

    将子类转化成爷爷类的时候会报错,因为不知道要转化到哪个类上去,这里需要加入static_cast才行。爷爷类会在两个父类中都被定义,解决的办法是:虚拟继承。

    虚拟继承让被菱形继承的父类只会存在一份,消除数据冗余,那这里就得问一下,内存是如何布局的呢?如何访问内存呢?

    虚拟继承跟普通的继承不一样,普通的继承是通过将父类的内存放在子类的前面来实现,但虚拟继承父类的内存是放在后面的,那菱形继承会让父类和爷爷类的偏移不一致,那如何寻找爷爷类呢?

    虚拟继承依然会前置一个值,只是不再是前置父类而是前置一个虚基表指针,指向的是内存中,父类相对于自己的偏移量。

    虚继承支持基类的常规转换,主要是解决了多个派生类对基类的拷贝问题,并没有解决多重继承的二义性问题。

    然后关于vs和g++的实现是不完全一样的,g++的实现是虚函数和虚基类地址偏移共享一个虚表,类的实例开始处即为所属类的虚指针。因为存在虚基类地址偏移,所以几乎每个类都会有一张独一无二的虚表。

    虽然有一些大概的了解了,但是能不用就别用,这个机制很慢,内存很大,并且很违反直觉。

    继承的内存分布

    然后在实际实验的时候一直有一个不太理解的地方,就是虚函数表似乎总是对不上:

    class A
    {
    public:
        virtual void Test(){return;}
        int _a;
    };
    
    class B
    {
    public:
        virtual int Test2(){return 1;}
        int _b;
    };
    
    class C : public A, public B
    {
    public:
        virtual int Test2(){return 2;}
        virtual void Test(){return;}
        int _c;
    };
    
    int main()
    {
        C *c = new C();
        c->_a = 1;
        c->_b = 2;
        c->_c = 3;
    
        return 0;
    }
    

    然后我打开gdb去分析,去看具体的内存布局:

    (gdb) start
    Temporary breakpoint 1 at 0x400666: file test.cpp, line 25.
    Starting program: /tmp/test
    Missing separate debuginfos, use: debuginfo-install glibc-2.17-326.el7_9.x86_64
    n
    Temporary breakpoint 1, main () at test.cpp:25
    25          C *c = new C();
    Missing separate debuginfos, use: debuginfo-install libgcc-4.8.5-44.el7.x86_64 libstdc++-4.8.5-44.el7.x86_64
    (gdb) n
    26          c->_a = 1;
    (gdb)
    27          c->_b = 2;
    (gdb)
    28          c->_c = 3;
    (gdb)
    30          return 0;
    (gdb) x /16wa c
    0x602010:       0x400830 <_ZTV1C+16>    0x0     0x1     0x0
    0x602020:       0x400850 <_ZTV1C+48>    0x0     0x2     0x3
    (gdb) x /8wa 0x400830
    0x400830 <_ZTV1C+16>:   0x400702 <C::Test()>    0x0     0x4006ec <C::Test2()>   0x0
    0x400840 <_ZTV1C+32>:   0xfffffffffffffff0      0xffffffffffffffff      0x4008a0 <_ZTI1C>       0x0
    (gdb) x /8wa 0x400850
    0x400850 <_ZTV1C+48>:   0x4006fb <_ZThn16_N1C5Test2Ev>  0x0     0x0     0x0
    0x400860 <_ZTV1B>:      0x0     0x0     0x4008e0 <_ZTI1B>       0x0

    其实很好理解的,0x400830是A类的虚函数指针指向虚函数表,虚函数表第一项是A的Test,第二项是B的Test2,那如果转化成A类也能按照同样的规则获取到Test这个虚函数。

    那0x400850是什么呢?它所指向的0x4006fb <_ZThn16_N1C5Test2Ev>是什么意思呢?真的琢磨了很久,然后想起来gdb 的x指令里/i是可以输出汇编指令。

    再进一步查看这个地址的汇编:

    (gdb) x /2wi 0x4006fb
       0x4006fb <_ZThn16_N1C5Test2Ev>:      sub    $0x10,%rdi
       0x4006ff <_ZThn16_N1C5Test2Ev+4>:    jmp    0x4006ec <C::Test2()>

    忽然就理解了,0x400850地址依然是一个虚函数表,第一项仍然是虚函数,并且就是C::Test2,那为什么不是直接指向C::Test2呢?

    因为C::Test2()是C这个类的函数,它的this应该要指向一个C的类,但是使用0x400850虚表的对象偏移是不对的,所以这个函数在实际执行C::Test2()之前要将this向前挪16个字节。

    至此,我觉得我比较深刻的理解了C++的虚函数机制。

    菱形继承的内存分布

    之前没完全看懂的,现在我觉得又可以了,然后再回头看一次。

    class A
    {
    public:
        virtual int Test(){return 1;}
        int _a;
    };
    
    class B: virtual public A
    {
    public:
        virtual int Test(){return 2;}
        int _b;
    };
    
    class C : virtual public A
    {
    public:
        virtual int Test(){return 3;}
        int _c;
    };
    
    class D : public B, public C
    {
    public:
        virtual int Test(){return 4;}
        int _d;
    };
    
    int main()
    {
        D *d = new D();
        d->_a = 1;
        d->_b = 2;
        d->_c = 3;
        d->_d = 4;
    
        return 0;
    }

    这是一个经典的菱形继承,再来看一下内存分布就比较清晰了:

    (gdb) start
    Temporary breakpoint 1 at 0x400666: file test.cpp, line 31.
    Starting program: /tmp/test
    Missing separate debuginfos, use: debuginfo-install glibc-2.17-326.el7_9.x86_64
    
    Temporary breakpoint 1, main () at test.cpp:31
    31          D *d = new D();
    Missing separate debuginfos, use: debuginfo-install libgcc-4.8.5-44.el7.x86_64 libstdc++-4.8.5-44.el7.x86_64
    (gdb) n
    32          d->_a = 1;
    (gdb)
    33          d->_b = 2;
    (gdb)
    34          d->_c = 3;
    (gdb)
    35          d->_d = 4;
    (gdb)
    37          return 0;
    (gdb) p *d
    $1 = {<B> = {<A> = {_vptr.A = 0x400958 <vtable for D+88>, _a = 1}, _vptr.B = 0x400918 <vtable for D+24>, _b = 2}, <C> = {_vptr.C = 0x400938 <vtable for D+56>, _c = 3}, _d = 4}
    (gdb) print sizeof(D)
    $2 = 48
    (gdb) x /16wa d
    0x603010:       0x400918 <_ZTV1D+24>    0x0     0x2     0x0
    0x603020:       0x400938 <_ZTV1D+56>    0x0     0x3     0x4
    0x603030:       0x400958 <_ZTV1D+88>    0x0     0x1     0x0
    (gdb) x /16wa 0x400918
    0x400918 <_ZTV1D+24>:   0x400722 <D::Test()>    0x0     0x10    0x0
    (gdb) x /16wa 0x400938
    0x400938 <_ZTV1D+56>:   0x400731 <_ZThn16_N1D4TestEv>   0x0     0xffffffffffffffe0      0xffffffffffffffff
    (gdb) x /16wi 0x400731
       0x400731 <_ZThn16_N1D4TestEv>:       sub    $0x10,%rdi
       0x400735 <_ZThn16_N1D4TestEv+4>:     jmp    0x400722 <D::Test()>
    (gdb) x /16wa 0x400958
    0x400958 <_ZTV1D+88>:   0x400737 <_ZTv0_n24_N1D4TestEv> 0x0     0x400918 <_ZTV1D+24>    0x0
    (gdb) x /16wi 0x400737
       0x400737 <_ZTv0_n24_N1D4TestEv>:     mov    (%rdi),%r10
       0x40073a <_ZTv0_n24_N1D4TestEv+3>:   add    -0x18(%r10),%rdi
       0x40073e <_ZTv0_n24_N1D4TestEv+7>:   jmp    0x400722 <D::Test()>

    file

    如前文所述,g++的实现是将虚函数表和虚基地址偏移量一起在虚表里,通过虚指针表明,虚基地址偏移量在虚表的最后一项。

    详细内容可以看一下下面引用的百科。

    参考

    https://www.sandordargo.com/blog/2020/12/23/virtual-inheritance
    https://zh.wikipedia.org/zh-sg/%E8%99%9A%E7%BB%A7%E6%89%BF

  • 编译优化PGO

    PGO的介绍

    基本概念

    PGO是一个可以平均提高任何程序5%~8%性能的技术,全称是Profile Guided Optimization,它的思路其实很简单,就是编译器在对变量和函数如何放置排布和使用问题上,其实是有很大的自由权利的。

    这里没有一个绝对的最优解,同一段代码,在对于不同应用场景的最优排布方式可能是不同的,传统编译方式都是以块代码进行排布和优化。

    而PGO技术就是自适应编译,通过对程序增加探针进行profile,运行程序之后,再在下一次编译时根据profile结果进行结构的优化调整。

    具体优化

    在开始介绍PGO的过程之前,先介绍一下作为一个编译器,有哪些决定可以去做,并且会怎样影响到程序的效率。

    • Inlining – 根据函数的调用数量和频次,编译器可以做出更好的内联决定。
    • Virtual Call Speculation – 如果一个特定的继承类经常被传递给一个函数,那么它的重载函数可以被inline(内联),这会减少虚表(vtable)的查询次数。
    • Basic Block Reordering(基础结构重新排序) – 尽量将执行顺序最多的路径的代码块放在一起,这样可以提高指令缓存的命中来实现。同时将使用较少的代码挪到最底部,结合下面的“function layout”一起可以显著减少大型应用程序的工作集(一个时间间隔内使用的页面数)。
    • Size/Speed Optimization – 根据profile信息,编译器可以找到常用的函数的使用情况,可以将常用的函数进行加速,不常用的函数的代码体积减少。
    • Function Layout – 将经常被关联调用的函数放在同一个代码段落里,来减少工作集。
    • Conditional Branch Optimization – 比如if/else,如果条件经常为false,则else的代码块会放置在if代码块之前,提高指令缓存命中。

    PGO的阶段

    PGO分为三个阶段:

    instrumental phase

    file

    在这个阶段链接器将cli文件传递给Bakend编译器,Bakend编译器会插入一些探针指令,并且会和可执行文件一起生成一个.pgd文件,这是一个后续其他阶段会用到的数据库文件。

    training phase

    第二阶段是训练阶段,在具体场景下运行程序,前面插入的探针将会记录运行时的信息,数据会被存放在.pgc文件中,每次运行都会产生一个appname!#.pgc的文件,如上图,第一次运行会产生App!1.pgc,第n次会产生App!n.pgc。

    在这里训练时要注意,训练时的场景要尽量和实际使用场景相同。

    PG Optimization Phase

    第3部分是PG优化部分,会将pgc文件合并成pgd文件,被Bakend编译器做决策时提供数据支持,生成更高效的可执行文件。

    PGO如何使用

    在windows, mac, ad, ios不同平台下的编译工具和使用方式不同,但整体的步骤如前文所述,不同的工具都是这样异曲同工。

    等后面实际应用到这个技术的时候再添加具体的步骤吧。

    引用

    https://devblogs.microsoft.com/cppblog/pogo/

  • 现代C++教程 读书笔记

    习题答案:https://github.com/changkun/modern-cpp-tutorial/tree/master/exercises

    序言

    本文传统C++ 是指C++ 98及之前的标准。

    C++ 14/17是对C++ 11的重要补充和优化;而C++ 20则将这门语言领进了现代化的大门。

    关于一些特性的初探:

    • auto关键字语义给操纵极为复杂的模板类型提供了底层支持;
    • lambda表达式基于C++匿名函数的闭包特性;
    • 右值引用的出现解决了C++长期被人诟病的临时对象效率问题;

    第一章迈向现代C++

    被弃用的特性

    弃用并非不能用,只是暗示这些特性将从未来的标准消失。

    • 不允许使用字符串面值常量赋值给char *,如果使用应该是用const char**或者auto。
    • C++98异常说明、unexpected_handler, set_unexpected()等特性被弃用,应该使用noexcept。
    • auto_ptr被弃用,用使用unique_ptr。
    • register关键词被弃用。
    • bool类型的++操作被弃用
    • 如果一个类有析构函数,为其生成拷贝构造函数和拷贝复制运算符的特性被弃用了。
    • C风格的类型转换被弃用了(即在变量前是用(convert_type)),应该使用static_cast、reinterpret_cast、const_cast来进行类型转换。
    • ……等等

    与C的兼容

    C++不是C的一个超集。

    用extern "C"特性时,将C语言代码和C++语言进行分离编译,再统一链接。

    第二章语言可用性的强化

    变量/常量/流程

    nullptr

    nullptr的是替代NULL,C++不允许将void *隐式转换到其他类型。

    void foo(char *);
    void foo(int);
    
    //直接调用将会调用void foo(int);;这违反常理
    foo(NULL);

    所有的空指针一律使用nullptr,而不要用NULL。

    constexpr

    修饰变量,const并未区分编译器常量和运行期常量,constexpr限定编译器常量。

    修饰函数,constexpr修饰的函数返回值不一定是编译期常量,这个有点像inline。

    只读的语义用const,常量的语义用constexpr。

    if/switch变量声明强化

    C++中可以将变量声名放在if和switch中,作用于就从函数下降到本身的作用域中。

        if (int a = f(); a != 1) {
            // 代码块A
            cout << a << endl;
        } else if (int b = g(); b != 2) {
            // 代码块B
            a += b;
            cout << a << endl;
        } else {
            // 代码块C
            a -= b;
            cout << a << endl;
        }

    初始化列表

    用initializer_list的构造函数被称为初始化列表构造函数,具有这种构造函数的类型将在初始化时被特殊处理。

    结构化绑定

    std::tuple<int, double, std::string> f(){
        return std::make_tuple(1, 2.3, "456");
    }
    
    int main(void){
        auto [x, y, z] = f();
        std::cout << x << ", " << y << ", " << z << std::endl;
        return 0;
    }

    auto,decltype

    用于类型推导。

    auto:

    • 当类型不为引用时,auto 的推导结果将不保留表达式的 const 属性;
    • 当类型为引用时,auto 的推导结果将保留表达式的 const 属性;
    • auto 关键字不能定义数组。

    还有一个尾返回类型(C++11),利用auto关键字将返回类型后置,但是在C++14中,可以让普通函数具备返回值推导:

    // C++ 11
    template<typename T, typename U>
    auto add(T x, U y) -> decltype(x+y){
        return x + y;
    }
    
    // C++ 14
    template<typename T, typename U>
    auto add2(T x, U y){
        return x + y;
    }

    decltype(auto)

    C++ 14开始提供的用法,和直接使用auto相比最大的区别在于这个能够自动识别是否是引用&,auto只能识别到数据类型,demo:

    std::string lookup1();
    std::string& lookup2();
    
    // C++ 11的封装形式如下:
    std::string look_up_string_1(){ return lookup1(); }
    std::string& look_up_string_2(){ return lookup2(); }
    
    // C++ 14可以如下:
    decltype(auto) look_up_string_1(){ return lookup1(); }
    decltype(auto) look_up_string_2(){ return lookup2(); }

    if constexpr

    C++ 17将constexpr关键字引入if判断,在编译期完成判断。

    template<typename T>
    auto print_type_info(const T& t){
        if constexpr(std::istegral<T>::value){
            return t + 1;
        } else {
            return t + 0.001;
        }
    }
    int main() {
        std::cout << print_type_info(5) << std::endl;
        std::cout << print_type_info(3.14) << std::endl;
    }

    会被编译成这样:

    int print_type_info(const int& t){
        return t + 1;
    }
    double print_type_info(const double& t){
        return t + 0.001;
    }
    //...

    其实这个语法糖…我不太能明白用处,写成两个函数不行吗,可能因为我对模板编程接触实在少。

    区间for迭代

    像python的for循环,要注意的主要是使用auto想修改的话,需要使用auto &。

    std::vector<obj_class> vec;
    //...
    for(auto &v: vec){
      // do sth
    }

    对象/模板

    外部模板

    传统C++中,模板只有使用时才会被实例化。并且每个编译单元(文件)都会被实例化,这增加了时间,C++11引入了外部模板:

    template class std::vector<bool>;                   // 强制实例化
    extern template class std::vector<double>;          // 不在当前编译文件中实例化模板

    类型别名模板

    模板和类型是不同的,模板是用来生产类型的。

    typedef可以为类型定义一个新的名称,但没法为模板定义一个新名称,因为木板不是类型,C++ 11引入了using解决这个问题。

    所以typedef给类型定义别名,using除了typedef能做的,还能够给模板定义别名。

    总结一下using的三个用途:

    • 引入命名空间
    • 指定别名(对比typedef 有两个好处,第一更加清晰,第二可以对模板)
    • 在之类中引用基类成员

    默认模板参数

    template<typename T = int, typename U = int>
    auto add(T x, U y){
        return x + y;
    }

    变长参数模板

    这个好像篡改了语法,所有的关键词后面加上…就变成了这个相关的功能,感觉还挺复杂的,列一下demo:

    template<typename... Ts> class Magic;      // 其中Ts就是变长模板的“类型名”,可以接受0~n个
    template<typename... Args> void printf(const std::string &str, Args... args);  // 有类型安全的printf
    template<typename... Ts>
    void magic(Ts... args){
        std::cout << sizeof...(args) << std::endl;
    }
    // 参数解包,1. 递归模板函数
    template<typename T0>
    void printf1(T0 value){
        std::cout << value << std::endl;
    }
    template<typename T, typename... Ts>
    void printf1(T value, Ts... args){
        std::cout << value << std::endl;
        printf1(args...);
    }
    // 参数解包,2. 变参模板展开
    template<typename T0, typename... T>
    void printf2(T0 t0, T... t){
        std::cout << t0 << std::endl;
        if constexpr(sizeof...(t) > 0) printf2(t...);
    }
    // 参数解包,3. 初始化列表展开
    template<typename T, typename... Ts>
    auto printf3(T value, Ts... args){
        std::cout << value << std::endl;
        (void) std::initializer_list<T>{([&args]{
            std::cout << args << std::endl;
        }(), value)...};
    }

    折叠表达式

    template<typename... T>
    auto sum(T... t){
        return (t + ...);
    }

    非类型模板参数推导

    template <auto value>
    void foo() {
        std::cout << value << std::endl;
    }
    
    int main() {
        foo<10>();     // value被推导为int类型
    }

    委托构造

    构造函数可以在同一个类的一个构造函数中调用另一个构造函数。

    class Base{
    public:
      int value1;
      int value2;
      Base() {
        value1 = 1;
      }
      Base(int value): Base() {
        value2 = value;
      }
    };

    使用委托构造函数,就不能再使用初始化列表构造其他成员了。

    继承构造

    class Base{
    public:
        Base();
        Base(int);
    }:
    
    class SubClass: public Base{
        using Base::Base;    // 继承构造
    };

    假设一旦使用了继承构造函数,编译器就不会为派生类生成默认构造函数。这样,我们得注意继承构造函数无參版本号是不是有须要。

    显示虚函数重载

    override显示告诉编译器这个函数是重载虚函数。

    final是显示告诉编译器,防止被继承这个函数。

    显示禁用默认函数

    传统C++中,如果程序员没有提供,编译器会为对象生成默认构造、复制构造、赋值算符以及析构函数,同时也为所有类定义了注入new delete这些运算符。

    C++ 11的解决方案:

    class Magic {
    public:
        Magic() = default;                        // 显式使用编译器生成的构造
        Magic& operator=(const Magic&) = delete;  // 显示声明拒绝编译器生成构造
        Magic(int magic_number);
    };

    强类型枚举

    C++ 11引入了枚举类,使用enum class的语法进行声名:

    enum class new_enum: unsigned int {
        value1,
        value2,
        value3 = 100,
        value4 = 100
    };

    这样的枚举不能被隐式转化为整数,不能与整数进行比较,不能与不同枚举类型的值进行比较。

    也解决了传统C++中,同一个命名空间的不同枚举类型的枚举值名字不能相同的问题。

    第三章 语言运行期的强化

    lambda表达式

    值拷贝:被捕获的变量在lambda表达式创建时拷贝,而非调用时才拷贝;

    1. 引用拷贝:和正常引用无异;
    2. 隐私捕获:直接填[=]或者[&]让编译器自行推导;
    3. 表达式捕获:有些变量不允许复制和引用,C++提供了表达式捕获可以进行任意的初始化,让我们可以把这些变量变成右值。

    其中当lambda表达式的捕获列表为空时,闭包对象还能够转换为函数指针值进行传递。

    using foo = void(int);
    void functional(foo f){ f(1); }
    int main() {
        auto f = [](int value) { std::cout << value << std::endl; };
        functional(f);
    }

    泛型lambda

    C++ 14支持lambda使用auto作为类型,提供泛型lambda:

    auto add = [](auto x, auto y){
        return x + y;
    }
    add(1, 2);
    add(1.1, 2.2);

    std::function

    函数的容器,对可调用实体的一种类型安全的包裹(函数指针的调用不是类型安全的)。

    std::bind和std::placeholder

    • 其中std::placeholder::_1表示bind对象调用时的第一个参数;
    • std::bind支持嵌套绑定,如下demo
    int foo(int a, int b, int c) { return a + b + c; }
    int g(int n) { return n + 2; }
    
    int main(){
        auto bindFoo = std::bind(foo, std::placeholders::_1, 1, std::bind(g, 3));
        bindFoo(3);
    }

    右值引用

    关于左值、右值、将亡值的概念我大概清楚了,但是书中这个例子我没理解清楚:

    #include <iostream>
    
    using namespace std;
    
    class ClassA{
    public:
        int *pointer;
        ClassA(): pointer(new int(1)){
            cout << " 构造" << pointer << endl;
        }
        ClassA(ClassA& a): pointer(new int(*a.pointer)){
            cout << " 拷贝构造" << pointer << endl;
        }
        ClassA(ClassA&& a): pointer(a.pointer) {
            a.pointer = nullptr;
            cout << " 移动" << pointer << endl;
        }
        ~ClassA(){
            cout << " 析构" << pointer << endl;
            delete pointer;
        }
    };
    
    ClassA return_rvalue(bool test){
        ClassA a, b;
        if(test) return a;
        else return b;
    }
    
    int main(void){
        ClassA obj = return_rvalue(false);
        cout << "obj: " << endl;
        cout << obj.pointer << endl;
        cout << *obj.pointer << endl;
    }
    
    /* 打印结果如下:
     构造0x555b80d39e70
     构造0x555b80d3a2a0
     移动0x555b80d3a2a0
     析构0
     析构0x555b80d39e70
    obj:
    0x555b80d3a2a0
    1
     析构0x555b80d3a2a0
    */

    这里我觉得移动构造应该会执行两次才对,return_rvalue从b对象到将亡值一次复制,从将亡值到main函数中的obj一次复制,实在不解为什么只执行了一次,就深入看了一下汇编,便有了本笔记的最后一章。

    我不放汇编代码,直接给出看汇编的结论:

    main函数在调用return_rvalue函数时,除了传递参数false,还传递了一个8字节的内存地址进去,return_rvalue在返回时并不是创建了一个新的对象返回给上一层,而是直接把b移动给了上一层传进来的对象里。

    换句话说,obj内存开辟是在main函数里做的,但拷贝构造函数发生在return_rvalue返回之前。

    在这里我还做了几个测试,在C中,当返回的对象内存大于4字节时,返回值是通过调用者提供的内存返回的。C++是的规则好像特殊一点,跟引用和右值有关系。

    右值引用

    T&& a是一个右值引用,它引用的对象是一个右值,但是它本身是一个左值,可以继续引用其他对象。

    移动语义:std::move

    会将参数的内容“移动”到左边,参数的对象会被清空。

    完美转发

    引用坍缩规则:在传统C++中,不能对一个引用类型继续进行引用,但右值引用的出现放宽了这一做法,从而引起坍缩规则。无论模板参数是什么类型的引用,当且仅当实参类型为右引用的时候,模板参数才能被推到位右引用类型。

    第四章 容器

    std:array

    • 相比vector,array大小是固定的,空间消耗可控;
    • 相比传统数组,array封装的更加安全。

    和C风格的接口兼容时:

    void foo(int *p, int len){ return ; }
    std::array<int, 4> arr = {1, 2, 3, 4};
    
    // foo(arr, arr.size());  // 非法,无法隐式转换
    foo(&arr[0], arr.size());
    foo(arr.data(), arr.size());

    std:forward_list

    std::list是双向链表,这个是单向链表,不展开

    std::unordered_map, std::unorder_set, std::unordered_multimap, …

    std::map和std::set都是用红黑树实现的;

    这里unordered_xx都是用hash表实现的;

    元组

    元组的三个核心函数:

    1. std::make_tuple: 构造元组
    2. std::get: 获得元祖某个位置的值
    3. std::tie: 元祖拆包
    auto student = std::make_tuple(1.7, 'D', "张三");
    auto lv = std::get<2>(student);
    auto score = std::get<1>(student);
    double gpa;
    char grade;
    std::string name;
    std::tie(gpa, grade, name) = student;

    运行期索引

    上面的例子中,std::get 其中index必须是常量,不能是变量。

    C++ 17 引入了variant<>,但用起来还挺复杂的,用到再深究吧。

    元组的合并与遍历

    std::tuple_cat(student1, student2);可以合并两个元组

    遍历需要用到上面variant和元组模板的::value属性。

    书里没写,我在这多插嘴一句,元组的实现在底层其实是多个类的继承,所以每个元组类型都是通过变长参数模板+继承来做的,因为继承内存其实非常紧凑,而每个元组本质上是一个对象,每个元组的类的长度是固定的,所以有一个value的静态变量来获取长度。

    从这里向下的内容严格来说,只算是库的内容,不算是语言层面的内容了

    从这里向下的内容严格来说,只算是库的内容,不算是语言层面的内容了

    第五章 智能指针与内存管理

    RAII和引用计数

    RAII是指在析构函数中释放资源,就不会忘记释放资源了。

    引用计数是指,记录对象被引用的次数。

    这俩是所有智能指针实现的低层级制。

    std::shared_ptr, std::make_shared

    引用计数变为0时,对象会被delete。

    std::unique_ptr

    禁止与其他的智能指针共享一个对象,从而保证代码的安全。

    不可复制,但可以移动。

    std::weak_ptr

    weak_ptr不会引起计数增加

    第六章 正则表达式

    std::regex

    之前一般的解决方案是使用boost的正则表达式库。

    C++ 11 将正则表达式引入了标准库的支持。

    第七章 并行与并发

    线程基础

    std::thread 用于创建一个执行的线程实例。

    get_id() 可以获得所创建线程的线程ID,使用join() 来等待一个线程结束。

    #include <iostream>
    #include <thread>
    
    int main() {
        std::thread t([](){
            std::cout << "hello world." << std::endl;
        });
        t.join();
        return 0;
    }

    互斥量与临界区

    std::mutex是最基本的mutex类,实例化可以创建互斥量,然后通过lock()上锁,unlock()解锁。还有一个RAI语法的模板类std::lock_guard和std::unique_lock。

    std::unique_lock更自由,可以主动lock和unlock。

    std::future

    跟python里的future挺像的,通过回调的形式来给予异步线程的返回值。

    条件变量

    std::condition_variable是为了解决死锁而生,实例被创建主要就是用于唤醒等待线程。std::conditioin_variable的notify_one()用于唤醒一个线程;notify_all()用于唤醒所有线程。

    原子操作与内存模型

    a=1, b=3; 因为CPU可能乱序,可能导致另外一个线程看到b先为3;

    mutex可以解决这个问题,因为mutex是操作系统级别的功能;

    同时C++11还引入了std::automic模板,为浮点整数提供了基本的数据成员函数。

    一致性模型

    当多个线程对一个变量v操作时,每个线程都能感受到v的变化,但对于v而言,表现为顺序执行的程序,v并没有因为引入多线程而得到任何效率上的收益。如何适当加速呢?削弱原子操作在进程间的同步调节。

    • 线性一致性;
    • 顺序一致性;
    • 因果一致性;
    • 最终一致性;

    内存顺序

    为了追求极致的性能,实现各种强度要求的一致性,C++为原子操作定义了六种不同的内存顺序std::memory_order的选项,表达了四种多线程间的同步模型:

    1. 宽松模型:std::memory_order_relaxed
    2. 释放/消费模型:std::memory_order_consume, std::memory_order_release
    3. 释放/获取模型:std::memory_order_acquire, std::memory_order_acq_rel, std::memory_order_release
    4. 顺序一致模型:std::memroy_order_seq_cst

    第八章 其他杂项

    long long in

    C99就已经引入了,C++ 11中也引入了,至少是一个64位的比特数。

    noexcept的修饰和操作

    C++11将异常声明简化为以下两种情况,并用noexcept进行限制:

    1. 函数可能抛出异常;
    2. 函数不能抛出异常;

    noexcept还能做操作符,用于操作一个表达式,无异常时返回true,否则返回false。

    noexcept(may_throw())
    noexcept(no_throw())

    noexcept修饰完函数之后,外部不会捕获到异常。

    自定义字面量

    没想到使用场景,demo:

    std::string operator"" _wow1(const char *wow1, size_t len){
        return std::string(wow1) + "woooooow, amazing!";
    }
    
    std::string operator"" _wow2(unsigned long long i){
        return std::to_string(i) + "woooooooooooow, amazing!!";
    }
    
    int main(){
        auto str = "abc"_wow1;
        auto num = 1_wow2;
        std::cout << str << std::endl << num << std::endl;
    }

    内存对齐

    C++11引入了两个新的关键字alignof和alignas来支持内存对齐进行控制。

    alignof类似于sizeof,获取跟平台相关的std::size_t类型的值,用于查询该平台的对齐方式。

    alignas用于修饰某个结构的对齐方式。

    第九章 展望:C++20简介

    诸如Concept/Module/Coroutine/Ranges等特性的提案都蓄势待发。

    概念与约束

    int main() {
        std::list<int> l = {1, 2, 3};
        std::sort(l.begin(), l.end());
    }

    上面的例子会产生不可读的编译错误,因为std::sort对排序容器必须提供随机迭代器,但std::list是不支持随机访问的。引入概念之后,我们可以对模板进行约束:

    template<typename T>
    requires Sortable<T>  // Sortable 是一个概念
    void sort(T& c);

    还有模块、合约、范围、协程、事务内存等。

    其他部分作者还没写完,就到这吧。

    汇编学习

    这一部分不是书里的内容,是在学C++右值引用的时候对一些细节不理解,但没找到相关的资料,只能深入汇编去看实现细节,这里也记录一下相关的信息:

    ELF文件格式

    ELF文件主要有四种类型:

    1. 可重定位文件(Relocatable File),可以用来和其他目标文件链接,即xx.o文件。
    2. 可执行文件(Executable File),规定了exec() 如何创建程序的进程印象。
    3. 共享目标文件(Shared Object File),可以和其他的可重定位文件一起链接成另一个目标文件;链接器可以将它与某个可执行文件组合,创建成可执行文件,即xx.so。
    4. 内核转储(core dumps),存放当前进程执行上下文,用于dump信号触发。

    ELF提供两种视图,分别是链接视图和执行视图:

    链接视图:以节(section)为单位,在连接时用到的视图。

    执行视图:以段(segment)为单位,在执行时用到的视图。

    可以这样来理解,在链接时,会将文件的相同的节组成一个段,在执行时把对应的段载入内存即可。

    比较重要的一些节:

    系统固定的section

    1. .text 代码段
      可以通过objdump -d 反汇编查看ELF文件代码段的内容。
    2. .strtab/.shstrtab 字符串表
      所有使用到的字符串都放在这里,以’\0’分隔。
    3. .symtab 符号表
      在链接的过程中需要把多个不同的目标文件合并在一起,不同的目标文件相互之间会引用变量和函数。在链接过程中,我们将函数和变量统称为符号,函数名和变量名就是符号名。
      这里的每个符号对应一个地址。
    4. .eh_frame / .eh_frame_hdr
      在调试程序的时候经常需要进行堆栈回溯,早期使用通用寄存器(ebp)来保存每层函数调用的栈帧地址,但局限性很大。后来现代Linux操作系统在LSB(Linux Standard Base)标准中定义了一个.eh_frame section,用来描述如何去unwind the stack。
      GAS(GCC Assembler)汇编编译器定义了一组伪指令来协助eh_frame生成调用栈信息CFI(Call Frame Information)。
    5. 重定位表(.relname)
      链接器在处理目标文件时,需要对目标文件中的某些部位进行重定位,即代码段和数据中中那些绝对地址引用的位置。对于每个需要重定位的代码段或数据段,都会有一个相应的重定位表。比如”.rel.text”就是针对”.text”的重定位表,”.rel.data”就是针对”.data”的重定位表。

    GOT是全局偏移表( Global Offset Table),用于存储外部符号地址;PLT是程序链接表(Procedure Link Table),用于存储记录定位信息的额外代码。

    寄存器

    常用寄存器:

    EAX:一般用作累加器
    EBX:一般用作基址寄存器(Base)
    ECX:一般用来计数(Count)
    EDX:一般用来存放数据(Data)
    ESP:一般用作堆栈指针(Stack Pointer)
    EBP:一般用作基址指针(Base Pointer)
    ESI:一般用作源变址(Source Index)
    EDI:一般用作目标变址(Destinatin Index)

    其中esp是栈顶,但是低地址;ebp是栈底,是高地址。

    关于x86平台寄存器使用的一些约定:

    • 当该函数是处于调用者角色时,如果该函数执行过程中产生的临时数据会已存储在%eax,%edx,%ecx这些寄存器中,那么在其执行call指令之前会将这些寄存器的数据写入其栈帧内指定的内存区域,这个过程叫做调用者保存约定(英文原名称:Caller Save)。
    • 当该函数是处于被调用者角色时,那么在其使用这些寄存器%ebx,%esp,%edi之前,那么该函数会保存这些寄存器中的信息到其栈帧指定的内存区域,这个过程叫被调用者保存约定。
    • %eax总会被用作返回整数值。
    • %esp,%ebp总被分别用着指向当前栈帧的顶部和底部,主要用于在当前函数推出时,将他们还原为原始值

    X86_64平台的约定

    相比于寄存器而言,存储器的访问太慢了,因为X86_64有16个通用寄存器,当函数调用时少于6个参数是直接通过寄存器来存储参数的,多于6个还是依然通过入栈实现。

    所以需要注意两点:

    • 为了效率,函数参数尽量少于6个;
    • 寄存器只有64位,传递较大参数时,尽量使用指针。

    帧栈原理

    32位帧栈:

    主要依靠的汇编指令:call和ret。前者跳转到函数入口执行,后者处理函数返回。

    call _func做了两件事:

    1. pushl %eip // 保存下一条指令的地址,用于函数返回继续执行
    2. jmp _func // 跳转到函数_func

    ret指令的作用相当于

    1. popl %eip // 将栈中的地址复制到eip寄存器中,返回前一个函数的上下文执行

    leave指令相当于下面两条:

    1. moveq %rbp, %rsp // 将现在的栈底赋值给栈顶
    2. popq %rbp // 将前一个栈底弹出

    x86_64帧栈

    通常情况下,x86_64函数简化了帧栈,不再将x86中的%rbp寄存器作为栈底寄存器,只是用%rsp记录当前栈顶。唯一写入栈的操作就是执行到call时会push返回地址 8字节,但是以下情况需要用到帧栈:

    1. 局部变量太多,64位寄存器处理不过来;
    2. 局部变量中存在数组或者结构体(或者叫做类类型)的变量;
    3. 使用取址操作符&就计算局部变量的的内存地址;
    4. 调用另外一个超过6个参数的函数;
    5. 需要在修改它们之前保存被调用者保存寄存器的状态;

    栈回溯

    在早期技术中,栈回溯是通过(%ebp)获得上一个栈的地址,再对上一个地址取值就是上上个地址;但现代Linux放弃了这个技术,节省出了一个ebp寄存器,原有的栈调用被放在eh_frame这个专用于存储栈回溯相关的段中。

    CFI伪指令生成在汇编文件中,根据链接选项(是否开启debug以及是否使用eh_frame段)来确定指令的执行内容,形式如下:

    cfi_startproc
    pushl %ebp
    .cfi_def_cfa_offset 8
    .cfi_offset ebp, -8

    CFI(calling frame info)的作用是出现异常时stack的回滚(unwind),回滚的过程是一级级CFA往上回退,直到异常被catch。

    其中eh_frame是编译完就静态生成好的,这个点困扰了我好久,现在大概理解了回溯的要点,eh_frame是根据汇编代码生成的一张表,运行时汇编对cfi的修改实际上就是在改动eh_frame中的索引。

    引用:

    https://zhuanlan.zhihu.com/p/286088470

    https://blog.csdn.net/a568921915/article/details/103427976

    https://zhuanlan.zhihu.com/p/288636064

    https://stackoverflow.com/questions/7534420/gas-explanation-of-cfi-def-cfa-offset

    https://www.jianshu.com/p/e7e21a51093e

    https://zhuanlan.zhihu.com/p/290689333

    https://zhuanlan.zhihu.com/p/302726082

  • TCP拥塞控制算法的实现

    基于对google提出的bbr算法源码阅读的一些学习:

    https://github.com/torvalds/linux/blob/master/net/ipv4/tcp_bbr.c#L39

    并不详细介绍bbr的原理,也不逐行解释

    拥塞接口

    TCP底层的拥塞控制通过若干个定义在TCP层的接口被模块化了,不同的算法就可以直接hook对应需要的回调来实现不同的TCP拥塞控制算法。

    Linux内核机制

    • 内核模块化,通过module_init和module_exit来初始化和卸载一个模块。
    • 模块开发不能使用常规的库函数,例如printf, malloc,需要使用内核提供的:printk, kmalloc。
    • 模块是系统的一部分,所以模块卸载需要自己卸载干净,系统不会帮忙进行回收。
    • 模块内开发不能直接对用户指针的对象取值或者复制,因为那是用户空间的地址,在内核空间会没有映射导致有问题,需要使用put_user给用户空间的内存地址复制。
    • 与上类似的函数还有:copy_to_user,copy_from_user,get_user,put_user。
    • 拥塞控制的结构体是:tcp_congestion_ops,定义了一系列的事件函数,通过hook这些函数实现不同的TCP拥塞控制算法。
    static struct tcp_congestion_ops tcp_bbr_cong_ops __read_mostly = {
        .flags      = TCP_CONG_NON_RESTRICTED,
        .name       = "bbr",
        .owner      = THIS_MODULE,
        .init       = bbr_init,                         // 初始化函数
        .cong_control   = bbr_main,                   // 在拥塞状态下,发包前的回调,用于更新拥塞窗口和传输速度
        .sndbuf_expand  = bbr_sndbuf_expand,        // 返回给tcp_sndbuf_expand使用的乘数
        .undo_cwnd  = bbr_undo_cwnd,                // 损失后cwnd的新值
        .cwnd_event = bbr_cwnd_event,               // 当发生拥塞时的回调
        .ssthresh   = bbr_ssthresh,                   // 返回慢启动的阈值
        .min_tso_segs   = bbr_min_tso_segs,           // 系统sysctl_tcp_min_tso_segs的重写
        .get_info   = bbr_get_info,                   // 获取inet的日志信息
        .set_state  = bbr_set_state,                // ca_state变化前会调用
    };
    
    static int __init bbr_register(void)
    {
        BUILD_BUG_ON(sizeof(struct bbr) > ICSK_CA_PRIV_SIZE);
        return tcp_register_congestion_control(&tcp_bbr_cong_ops);
    }
    
    static void __exit bbr_unregister(void)
    {
        tcp_unregister_congestion_control(&tcp_bbr_cong_ops);
    }
    
    module_init(bbr_register);
    module_exit(bbr_unregister);
    • BUILD_BUG_ON是编译时的检测,为了保证bbr的结构体小于等于内核准备的空间大小。
    • 不同的机器的ICSK_CA_PRIV_SIZE值可能不同,但是编译确定下来还有bbr的空间大小和分布,所以一个系统编译,其他系统也是能够使用的。
    • do_div表示除法函数mod = do_div(x, y),结果存储在x中,余数存储在mod中。
  • TCP-Jersey拥塞控制介绍

    介绍

    TCP-Jersey拥塞控制算法在中文世界里的描述非常的少,有点好奇信号和丢包共同控制的算法是怎样的,就翻译了这篇论文,链接在最后。

    传统TCP拥塞控制

    传统TCP的拥塞控制算法是使用拥塞控制窗口来实现的,TCP发送端在发送时除了要兼容接收端的接收窗口,自己这边的发送窗口,还需要考虑拥塞控制窗口。在发送时,取min(w_{r}, w_{s}, w_c),其中w_r是接收窗口,w_s是发送窗口,w_c是拥塞窗口。

    发生丢包事件时,拥塞控制窗口的长度会缩小到一半,然后线性增加逐步增加,即加性增,乘性减(AIMD),这样的设计维护了网络的相对公平和稳定,但是在当今的环境下,移动网络占了互联网流量的很大一部分,移动网络有一个特点就是存在一定的信道丢包,即在发送消息时,本身可能因为信号和干扰的原因,导致发送失败。

    在传统TCP拥塞控制算法里会认为这次丢包是发生了拥塞,进而会缩小拥塞窗口,进而降低TCP的发送速度,但实际情况只是发生了一次丢包,而并没有拥塞。

    TCP-Jersey拥塞控制算法

    这个算法的设计初衷是为了提高无线网络以及无线-有线混合网络通信的传输速度,TCP主要慢的原因是无法区分网络拥塞和无线链接原因的丢包。本协议具有区分这两者的能力,TCP-Jersey包含两个关键部分,可用带宽估计(ABE)算法和拥塞警告(CW)路由配置。

    ABE是一个在发送端持续估计连接的可用带宽,并且在发生拥塞时指导传输速率的算法。

    CW是一个在有迹象发生网络拥塞时,在终端警告的网络路由的配置。CW网络配置对封包进行的标记,可以帮助TCP连接的发送方区分丢包是网络拥塞导致的还是无线链路有问题导致的。

    对比

    在NS-2网络模拟中,当无线网络拥有1%的丢包率,无拥塞的情况下,TCP-Jersey对比TCP-Westwood和TCP-Reno,吞吐量分别提升了17%和85%。

    在发生拥塞,丢包率为1%的无线网络中,TCP-Jersey对比TCP-Westwood和TCP-Reno,吞吐量分别提升了9%和76%。

    TCP-Jersey

    本协议的目标就是将丢包的原因细化,从由拥塞导致的丢包和无线网传输导致的丢包区分开。

    A.可用带宽预估(ABE)

    传统TCP是通过增大窗口,直到发生丢包来判断可用带宽大小。

    TCP-Westwood协议提出了一个有效的办法,在当发送端在t_k时刻收到ACK,记录带宽的采样为:

    b_k=\frac{d_k}{t_k-t_{k-1}}

    其中d_k是ACK确认的数据长度,t_{k-1}是前一个ACK收到的时间。然后再使用Tustin双线性方法近似计算低通滤波,公式如下:

    \hat {b_{k}}=\frac{\frac{2\tau}{t_k-t_{t-1}} - 1}{\frac{2\tau}{t_k+t_{t-1}}+1} \hat b_{k-1}+\frac{b_k+b_{k-1}}{\frac{2\tau}{t_k-t_{k-1}}+1}

    其中\hat b_k表示在t_k时刻的平滑后的预估可用带宽,其中1/\tau是低通频率的截止频率。此外,TCP-Westwood还是用了一个定时器,如果\tau/m(m>2)时间内没有收到ACK则相当于收到了一个b_k = 0的采样。同时受到三个重复的ACK时被TCP-Westwood判定为发生拥塞,将TCP拥塞控制中的ssthreshold设置为:

    ssthresh=\frac{BWE\times RTT_{min}}{seg\_size}

    其中BWE就是预估的带宽,RTT_{min}是TCP预估的最小往返延时,seg\_size是分段大小(segment size,就是MSS中的SS)。如果cwnd>ssthresh并且不在慢启动状态里,拥塞窗口cwnd的被设置为ssthresh,然后并没有明确的指导如何设置\tau和m。

    这里TCP-Jersey采用了相同的估计最大可用带宽的方法:发送方通过观察ACK返回速度,但是采用了一个更加简单的预估。我们提出的方法是基于时间滑动窗口做预估的(TCP-Westwood使用的近似低通滤波器)。

    TCP-Jersey通过监控收到ACK的速度来预估TCP连接的可用带宽,然后是用这个预估来优化拥塞窗口。我们在每个RTT计算一次最佳拥塞窗口,当CW通知需要减小窗口时,TCP-Jersey将cwnd和ssthresh设置为最佳拥塞窗口,ABE的公式如下:

    R_n=\frac{RTT/times R_{n-1}+L_n}{(t_n-t_{n-1})+RTT}

    其中R_n表示在t_n时刻收到第n个ACK之后预估的带宽,t_{n-1}表示前一个ACK到达时间,L_n是第n个ACK确认的数据长度,RTT是TCP估计的往返时间。最佳拥塞控制窗口(ownd)公式如下:

    ownd_n=\frac{RTT\times R_n}{seg\_size}

    其中seg\_size表示分段大小。

    我们的模型有几个优点:

    • 我们对带宽估计的计算很快
    • 不需要配置参数;
    • 同窗口滤波器一样,会随着时间衰减,适合非静态的带宽延迟网络,这是有线-无线混合网络的特性。

    在文中的模拟里,TCP-Jersey的预估带宽对比TCP-Westwood的更加准确。

    B.拥塞警报

    现在的ECN协议会在平均队列长度在min_{th}到max_{th}之间会随机标记封包,路由器不仅会通知发送者发生了拥塞,并且会通过随机标记封包进而影响连接的拥塞控制窗口。

    ECN信息的往返需要时间,而网络情况变化很快,尽管ECN提供了宝贵的信息,但是就在几乎所有的情况下此信息不够及时,使得发送方无法准确快速的应对网络状态变化。而且RED和ECN对参数设置都非常敏感,错误的参数会降低TCP的性能。因此我们提出了一种更简单的通知方案,即拥塞警告(CW),具有更少需要配置的参数,同样能给发送方提供敏感准确的拥塞状况。

    我们建议当平均队列大于某个阈值时,路由器标记所有的封包,并由TCP的发送方来决定如何控制窗口策略。使用IP帧头中的CE位和TCP报头中的ECE和CWR位来传递拥塞信息。这样兼容自1990s时定制的这几个标志位的含义,可以和其他没有CW功能的路由器共同工作。

    后面就不继续翻译了,主要的思路已经描述完了。

    引用

  • Unix编程艺术 读书笔记

    1 哲学

    • 性能—时间的指数曲线对软件开发过程所引发的结果,就是每过18个月,就有一半的知识会过时。Unix并不承诺让你免遭此劫,只是让你的知识投资更趋稳定
    • 策略相对短寿,而机制才会长存
    • 对于程序员和开发人员来说,如果完成某项任务所需要付出的努力对他们是个挑战却又恰好还在力所能及的范围内,他们就会觉得很有乐趣。
    • 那些毫无动力、松松垮垮而且薪水微薄的程序员们,能在短短期限内,如同神灵附体般造出稳定而新颖的软件——这只不过是经理人永远的梦呓罢了。
    • 让每个程序就做好一件事。如果有新任务,就重新开始,不要往原程序中加入新功能而搞得复杂。
    • Unix哲学是这样的:一个程序只做一件事,并做好。程序要能协作。程序要能处理文本流,因为这是最通用的接口。
    • 你无法断定程序会在什么地方耗费运行时间。瓶颈经常出现在想不到的地方,所以别急于胡乱找个地方改代码,除非你已经证实那儿就是瓶颈所在。
    • 估量。在你没对代码进行估量,特别是没找到最耗时的那部分之前,别去优化速度。

      所以实际投入使用的排序算法,都是分层的,在n小时用冒泡,复杂的时候才考虑快排或者并归。

    • 花哨的算法在n 很小时通常很慢,而n通常很小。花哨算法的常数复杂度很大。除非你确定n总是很大,否则不要用花哨算法(即使n很大,也优先考虑原则2)。
    • 其中一种压力就是来自技术上的虚荣心理。
    • 在设计中,你应该主动将代码的复杂度转移到数据之中去。
    • 还不知道瓶颈所在就匆忙进行优化,这可能是唯一一个比乱加功能更损害设计的错误。
    • 先制作原型,再精雕细琢。优化之前先确保能用
    • 如果可能,用C编写前,先用解释性语言搭建原型
    • 看到该做的就去做——短期来看似乎是多做了,但从长期来看,这才是最佳捷径。
    • 一旦某人已经解决了某个问题,就直接拿来利用,不要让骄傲或偏见拽住你又去重做一遍。永远不要蛮干;要多用巧劲,省下力气到需要的时候再用,好钢用在刀刃上。善用工具,尽可能将一切都自动化。
    • 软件设计和实现应该是一门充满快乐的艺术,一种高水平的游戏。

    2 历史——双流记

    现代操作系统虽然很复杂,但确实也就是一个分时系统,在任何时间段让程序独立的运行而已。

    • 如果有足够多眼睛的关注,所有的bug都无处藏身
    • 距开源越近就越繁荣。任何将Unix专有化的企图,只能陷入停滞和衰败。

    3 对比:Unix哲学同其他哲学的比较

    • Unix系统拥有抢先式多任务(preemptive multitasking)能力。在Unix中,时间片由调度程序来分配,这个调度程序定期中断或抢断正在运行的进程而把控制权交给下一个进程。几乎所有的现代操作系统都支持抢占
    • 多用户的概念除了多进程还需要一套权限隔离的系统来维护。
    • 因为Windows没有处理好程序库的版本控制问题,所以长期备受被称为“DLL地狱(DLL hell)”配置问题的折磨,在这个问题中,安装新程序可以任意升级(或降级)现有程序运行依赖的库文件。专用的应用程序库和厂商提供的系统库都存在这个问题:应用程序和特定版本的系统库一起发布非常普遍,一旦没有特定的系统库,应用程序就会无声无息地垮掉。
    • MVS的统一性理念是:一切皆批处理。

    4 模块性:保持清晰,保持简洁

    • 软件设计有两种方式:一种是设计得极为简洁,没有看得到的缺陷;另一种是设计得极为复杂,有缺陷也看不出来。第一种方式的难度要大得多
    • 一些最有能力的开发者,一开始总是定义接口,然后编写简要注释,对其进行描述,最后才编写代码——因为编写注释的过程就阐明了代码必须达到的目的。
    • 假设其它所有因素(如程序员能力)都相同,200 到 400 之间逻辑行的代码是“最佳点”,可能的缺陷密度达到最小。这个大小与所使用的语言无关——这个结论有力支持了本书中其它地方提出的建议
    • 紧凑性就是一个设计是否能装进人脑中的特性。
    • C++是反紧凑性的——该语言的设计者已经承认,他根本不指望有哪个程序员能够完全理解C++。
    • 合理对待紧凑性,设计中尽量考虑,决不随意抛弃。

    5 文本化:好协议产生好实践

    • 当你很想设计一个复杂的二进制文件格式,或一个复杂的二进制应用协议时,通常,明智的做法是躺下来等待这种感觉过去。
    • 使用二进制协议的唯一正当理由是:如果要处理大批量的数据集,因而确实关注能否在介质上获得最大位密度,或是非常关心将数据转化为芯片核心结构所必须的时间或指令开销。
    • 这件事很浅显很正确,却是违反直觉的。设计一个精良的二进制结构存储效率可能不如明文+压缩。

      创建一个简单的工具来做好压缩,要比仅对文件某些部分进行特别压缩更有效,原因在于,压缩工具可以扫描所有数据,然后找到信息中的所有重复部分进行压缩。

    • 创建一个简单的工具来做好压缩,要比仅对文件某些部分进行特别压缩更有效,原因在于,压缩工具可以扫描所有数据,然后找到信息中的所有重复部分进行压缩。
    • 因为网络带宽要比存储昂贵得多,所以需更加重视事务处理的经济性。但如今的宽带费用都很低了。

    6 透明性:来点儿光

    • 透明性和可显性对用户和软件开发人员都很重要。但是重要性体现在不同的方面。用户喜欢 UI 中的这些特性,是因为这意味着学习曲线比较平缓。
    • 这个说法我好喜欢,优雅的代码除了一种自我实现感还有很重要很基础的一点是程序就是面向代码的。

      软件开发者喜欢代码本身(用户不可见部分)的这些品质,因为他们经常需要对代码有很好理解后才能进行修改和调试。

    • 软件开发者喜欢代码本身(用户不可见部分)的这些品质,因为他们经常需要对代码有很好理解后才能进行修改和调试。
    • GCC由一系列处理阶段组成,并由一个驱动程序将其紧密结合在一起。它们是:预处理器、解析器、代码生成器、汇编器和链接器。
    • 要追求代码的透明,最有效的方法很简单,就是不要在具体操作的代码上叠放太多的抽象层。
    • Unix 程序员学到了一种品性,就是宁愿抛弃、重建代码也不愿修补那些蹩脚的代码

    7 多道程序设计:分离进程为独立的功能

    • 总的来说,线程不是降低而是提高了全局复杂度,因此,除非万不得已,尽量避免使用线程。
      -这本书真的好反感使用线程啊,不过想想确实也有合理性。

      通常,你可以发现避免使用线程是可能的。

    8 微型语言:寻找歌唱的乐符

    • 对软件错误模式进行的大量研究得出的一个最一致的结论是,程序员每百行代码出错率和所使用的编程语言在很大程度上无关。[1]更高级的语言可以用更少的行数完成更多的任务,也意味着更少的bug。
    • 美是抵御复杂的最后武器。

    9 生成:提升规格说明的层次

    数据比程序逻辑更易驾驭。

    10 配置:迈出正确的第一步

    -如果有绝对最优解,就不必让用户选择

    首先,对于能够可靠地进行自动检测的东西,就不要提供配置开关。

    • 首先,对于能够可靠地进行自动检测的东西,就不要提供配置开关。

    11 接口:Unix环境下的用户接口设计模式

    • 我们将使用五种度量标准对接口风格进行分类:简洁、表现力、易用、透明和脚本化能力。
    • 当人们说一个用户接口是直观的,他们的意思是(a)它是可显的,(b)用法是透明的,(c)遵循最小立异原则
    • 在Unix传统中,已经形成了良好的接口设计模式,可以完成以上讨论的权衡。
    • 理由三:垃圾信息是对用户带宽的无谓消耗。在屏幕上,这又增加了一个分心的来源,往往让人们不得不在处理更重要的前台工作(例如同他人的交流)的同时耗费心力。

    12 优化

    • 通常,指令加载要比执行花费的时间更多。
    • 例如,在3D图形引擎中,优化旋转操作的sin(x)函数表在现代机器中占据365×4字节的空间。在处理器缓冲速度没有内存查询快时,这显然是个速度优化。但是现在,比起函数表产生的附加缓存击不中的可能开销,每次重新计算可能更快。
    • 实际上,经验法则是尽可能低的时延设计,和忽略带宽成本

    13 复杂度:尽可能简单,但别简单过了头

    • Unix程序员已学到了一种世界观:简单即美即雅即善,而复杂即丑即怪即恶。
      Gabriel 在更关注接口简单性的“MIT”哲学和更重视实现简单性的“New Jersey”哲学之间进行了比较,然后提出,尽管MIT哲学能够引导软件在抽象上做到更好,但New Jersey模型(差者)更具传播特质。
      -原来很多库接口的设计还有这样的考虑

      在MIT哲学中,应该暂停系统调用,伺中断处理完成之后自动恢复之——这较难实现,但接口更为简单;而在New Jersey哲学下,系统调用会返回一个错误表明已被中断,用户必须重新执行——这实现起来非常简单,但编程接口却较难使用。

    • 他所采用的简单实现就是允许“404:Not Found”可以作为一个响应,这使得万维网非常轻便,并获得了广泛的传播和巨大的成功。
    • 重点划一下

      在理想世界,Unix程序员只愿意手工打造小巧完美的软件宝石,每个都那么小巧、那么优雅、那么完美。然而现实中很不幸的是,太多复杂问题需要复杂的解决方案。仅仅十行的程序,再优雅也无法控制喷气客机。

    • 计算资源以及人类的思考,同财富一样,不是靠储藏而是靠消费来证明其价值的
    • 作为vim的信徒必须捍卫,你凭啥这么说!!

      比较而言,vi 看起来相当臃肿而不紧凑。

    14 语言:C还是非C

    • 我语言的极限便是我世界的极限。
    • 这一点确实如此,用C/C++高效但开发维护成本高,但很多时候主要的消耗还是在io和网络

      使用脚本语言的性能损失对真实世界的程序来说经常微不足道,因为真实世界的程序往往受I/O事件等待、网络延迟以及缓存列填充等限制,而非CPU的自身效率。

    • 使用脚本语言的性能损失对真实世界的程序来说经常微不足道,因为真实世界的程序往往受I/O事件等待、网络延迟以及缓存列填充等限制,而非CPU的自身效率。
    • 非常非常认同,因为开发的本质是硬件设备,所有的高级语言虽然屏蔽了硬件体系,但如果要优化还是逃不开的

      即使更高级的语言能够满足编程的要求,我们仍然要学习C,其中一个充分理由就是C能帮助我们学会在硬件体系层次上考虑问题。

    • 即使更高级的语言能够满足编程的要求,我们仍然要学习C,其中一个充分理由就是C能帮助我们学会在硬件体系层次上考虑问题。
    • 总结:C 语言最佳之处是资源效率和接近机器语言。而最糟糕的地方是其编程简直就是资源管理的炼狱。
    • 总结:C++的最佳之处是编译效率以及面向对象和泛型编程的结合。最糟之处是它非常怪异复杂,往往鼓励过分复杂的设计。
    • Java编程语言的设计目标是“write once,run anywhere(一次编写,到处运行)”

    15 工具:开发的战术

    • 作为通用法则,程序90%的执行时间都耗费在10%的代码上。

    19 开放源码:在Unix新社区中编程

    • 多数人在发布自己的项目之前,都是从修补他人的软件而开始接触开源软件开发的。
    • 如果档案文件都是类似GNU风格的名称,主干前缀全小写且只包含字母和数字,后接连字号,后再接版本号、扩展和其它后缀,对大家都有帮助。

    20 未来:危机与机遇

    • Plan 9还有许多其它值得推荐的地方,包括一些问题重重Unix系统调用接口的再造、摒弃了超级用户概念的,以及许多其它有趣的再思考。它的血统没有污点,设计优雅,而且揭露了Unix设计中的一些严重错误。
  • Python高性能编程 读书笔记

    主题

    在当python的函数越短,通常意味着性能越高!

    这不是笑话,在不改变算法的情况下,同一个功能是一定存在一个最短指令集的,当python代码变短意味着指令码变少,那多的指令码就在底层以CPU指令码的形式转移了。

    这叫做同算法指令集数量守恒。 ——本人

    第二章 通过性能分析找到瓶颈

    python可用的分析工具:

    • cProfile:自带的运行分析工具,可以计算函数的执行次数和时间;
    • runsnakerun: 可视化cProfile的内容;
    • link_profile: 分析的更加细致,但是执行效率会变慢,要增加修饰符;
    • memory_profiler:诊断内存的用量
    • heapy:调查堆上的对象
    • dis模块:生成CPython字节码

    heapy模块

    • guppy.hpy() – 获得heapy对象,作为操作接口。
    • heap() – 获得堆中的可见对象(reachable and visible),这些对象并不包含guppy库使用和创建的对象。
    • setref() – 设置一个参考点,下一次调用heap()函数会计算这个参考点之后创建的。
    • heapu() – 获得不可见(循环引用)的对象的状态和列表,heapu()返回一个状态(guppy.heapy.Part.Stat)标明不可见对象。

    dis模块

    获得python的字节码

    def myfunc(alist):
        return len(alist)
    
    >>> dis.dis(myfunc)
      2           0 LOAD_GLOBAL              0 (len)
                  3 LOAD_FAST                0 (alist)
                  6 CALL_FUNCTION            1
                  9 RETURN_VALUE
    
    >>> import math
    >>> def myfunc(x):
    ...     return math.sin(x)
    ...
    >>> import dis
    >>> dis.dis(myfunc)
      2           0 LOAD_GLOBAL              0 (math)
                  2 LOAD_ATTR                1 (sin)
                  4 LOAD_FAST                0 (x)
                  6 CALL_FUNCTION            1
                  8 RETURN_VALUE
    >>> from math import sin
    >>> def myfunc(x):
    ...     return sin(x)
    ...
    >>> dis.dis(myfunc)
      2           0 LOAD_GLOBAL              0 (sin)
                  2 LOAD_FAST                0 (x)
                  4 CALL_FUNCTION            1
                  6 RETURN_VALUE

    默认值不能用可变类型

    >>> def B():
    ...   def A(x=[]):
    ...     x.append(2)
    ...     return x
    ...   return A
    ...
    >>> import dis
    >>> dis.dis(B)
      2           0 BUILD_LIST               0
                  2 BUILD_TUPLE              1
                  4 LOAD_CONST               1 (<code object A at 0x7febe7e5de40, file "<stdin>", line 2>)
                  6 LOAD_CONST               2 ('B.<locals>.A')
                  8 MAKE_FUNCTION            1
                 10 STORE_FAST               0 (A)
    
      5          12 LOAD_FAST                0 (A)
                 14 RETURN_VALUE
    
    
    构建了一个函数,是B.<locals>.A,并且list作为默认值一开始就存进去了
    >>> def X(x=[]):
    ...   return x
    ...
    >>> X.__defaults__
    ([],)

    第三章 列表和元祖

    python使用魔法函数eq和lt来进行对象的比较。

    bisect模块是二分查找模块

    通用代码会比某个特定问题设计的代码慢很多。

    blist是比默认的list在存在大量修改的list场景下实现更快的数据结构。

    第四章 字典和集合

    python在va == vb的判断内部调用的是eq方法。

    可以被散列(哈希)的对象是同时实现了hash的魔法函数以及eq或者cmp两者之一的类型。

    这里一定要实现eq或者cmp为了防止两个对象的hash相同,那样就需要判断两个对象是否相等,如果相等则是同一个,不然则是不同的。

    python对dict本质就是一个hash表,底层对hash冲突的处理方式是开放寻址法

    同时在python的dict到达容量的2/3时会发生扩容,扩容的复杂度是O(n)的,需要将所有的对象都重新hash一次。

    每当python访问一个变量、函数或模块时,首先会查找locals()数组,其内保存了所有本地变量的条目,如果不在本地变量里那么搜索globals()字典,最后如果对象也不在则搜索builtin对象。这里可能为了搜一个函数或者变量要搜好几个dict。

    第五章 迭代器和生成器

    代码每次运行到yield该函数就会“发射”出一个值,然后外部代码需求另一个值时该函数才会继续运行(上下文会保存)。

    使用python的内置函数iter来创建迭代器,iter函数会返回对象的iter属性:

    # python的循环
    for i in object:
        do_work(i)
    
    # 等价于
    object_iterator = iter(object)
    while 1:
        try:
            i = object_iterator.next()
            do_work(i)
        except StopIteration:
            break

    如果只是计算满足某个条件的列表数量,这样可以节省一笔内存

    # 不要写:
    [i for i in xrange(n) if i % 3 == 0]
    # 要用:
    sum((1 for i in xrange(n) if i % 3 == 0))
    
    ----------------------
    项目里一些代码的鞭尸:
    level_aver = float(sum([member.rank_level for member in self.member_dict.values()])) / self.size
    
    total_num = sum([abs(value) for value in pop_result.itervalues()])
    
    sum([mgr.busy_count for mgr in self.combat_mgr.itervalues()])
    
    # 这里每次+可能会增加一次内存分配和复制
    # 用list(chain()) 在1000*1000的对象上操作要快396倍
    task_list = reduce(lambda x, y: x + y, task_level_list)
    
    # 而且原场景其实不需要这个list,拼接了之后只是一次性使用直接返回迭代器即可

    python里一些表达式:

    • 列表表达式: [f(xx) for xx in rr if xx else f(xx)]
    • 生成器表达式: (f(xx) for xx in rr if xx else f(xx))
    • 字典表达式: { key_expr: value_expr for value in collection if condition }
    • 集合生成器: {f(xx) for xx in rr if xx else f(xx)}

    在这里记录一下。

    标准库中的itertools库提供了内建函数map, reduce, filter和zip的生成器版本(分别是imap, ireduce, ifilter和izip),以及其他很多有用的函数,特别是:

    • islice 允许对一个无穷生成器进行切片
    • chain 讲多个生成器链接到一起
    • takewhile 给生成器添加一个终止条件
    • cycle 通过不断重复将一个有限生成器变成无穷

    顺便记录一下上面几个函数的功能:

    • map(function, iterable, …): 将参数以函数执行的生成器
    • reduce(function, iterable[, initializer]): 跟map类似,不过f的参数是两个,先对迭代器中的第 1、2 个元素进行操作,得到的结果再与第三个数据用 function 函数运算,最后得到一个结果。
    • filter(function, iterable): 对迭代器的对象执行f来进行过滤,为True才会返回
    • zip([iterable, …]): 将对象中对应的元素打包成一个个元组,然后返回由这些元组组成的列表。
    • any(iterable), 如果 iterable 的任一元素为真值则返回 True。
    • all(iterable), 如果 iterable 的所有元素都为真值则返回 True。

    第六章 矩阵和矢量计算

    原生python并不支持矢量操作,主要的核心原因是python的列结构存储的内容是指向对象的指针,其次python的字节码没有对矢量操作做优化。

    result = 0
    for i xrange(num_iterations):
       result += i * sin(num_iterations)
    return result
    
    # 下面这个快过上面那个,虽然是废话,但是很实用
    result = 0
    for i xrange(num_iterations):
       result += i
    return result * sin(num_iterations)
    
    # -------------------------------------
    # damage_system
    for ratio in reduce_ratio_list:
        damage *= ratio
    
    # 比上面要快16%
    damage = reduce(operator.mul, reduce_ratio_list, damage)
    
    # -------------------------------------

    书中用numpy去优化一段代码,带来了40倍的效率提升,但是神奇的事情是,禁用矢量指令集优化,性能依然有极大的提高,用perf分析发现矢量操作近带来了40倍中的15%,剩下的是内存问题导致的效率低下。

    perf是一个进程级别的分析工具。

    numexpr

    将python能够分析执行顺序,非常大程度的优化矩阵,可以自动地利用多CPU的优势,并且考虑到CPU缓存的问题,会特意移动数据让各级CPU缓存拥有正确的数据。

    如果numpy可以将速度快几倍,那使用numexpr可能可以将速度提升至几十上百倍。

    但是如果矩阵特别小,会有负优化的效果。

    第七章 编译成C

    Cython、Shed Skin和Pythran是纯粹的基于C的编译方式,凭借Numba的基于LLVM的编译方式,还有替代虚拟机的pypy,内置了一个即时编译器(JIT)。

    无论使用哪条路线,都要在适用性和团队效率上作出权衡,

    image

    优化是永无止尽的,但是对一个模块的优化是有限的。

    顺便一提,pyc只是py编译成的python机器码,并不包含优化。

    对python的优化

    Cython

    可以直接把python代码编译成so,可以先用Cython在服务端优化一轮,顺便提前把模块化做好。

    Shed Skin

    将python翻译成C++的编译器,会自动去猜测类型,可以直接被import,不像Cython需要显式指定类型。

    Shed Skin会将python的list拷贝成Shed Skin环境的变量,这个是会花时间的,

    numba

    llvm编译器的python脚本编译,只需要在需要编译的函数增加@jit()修饰符即可,执行速度非常快

    Pythran

    有点像Numba和Cython——我注解函数的参数,接着它接管进一步的类型注解和代码特化,它会利用OpenMP的并行化可能性。

    pypy

    底层换了虚拟机,提供了JIT,执行时编译,所以第一次会很慢,编译好之后再执行非常快!

    pypy和CPython的垃圾回收机制不同。

    任何纯python的库pypy都能直接安装运行,但是有C扩展库的就可能无法工作。

    内存消耗比cpython多。

    写C/C++程序的优化

    ctypes

    C++只写一些函数,然后通过ctypes来”import”进python,需要在python层将所有的调用对象都转化成ctypes对应的C类型,然后执行。

    这里在使用list或者dict的时候,会非常非常消耗。

    cffi

    相比ctypes方便很多,并且支持一些很便利的语法糖。

    CPython模块

    我们项目里目前是用的模块,会很繁琐,很简单的代码也要写几十行来兼容,但是好处是控制颗粒度非常高,从无视GIL到引用计数,一切都可以直接去修改,但是对程序的要求也会高一点,因为需要了解python的一些细节。

    在大部分情况下,书中的建议是不使用这种方式。

    第八章 并发

    时间循环有两种方式:回调或者future。

    回调会带来很长的调用链,future+asyncio是一个很好的,不过我们用python2是永远没机会用了。

    分别使用了gevent,tomado和asyncio

    第九章 multiprocessing模块

    可以让程序基于进程和线程的并行处理,multiprocessing.Pool的功能感觉很强!

    对于使用这个模块,需要解决的问题:

    • 把工作拆分成独立的工作单元
    • 考虑是否能随机化工作序列
    • 尽量让同时在处理的任务数量和CPU数量相同

    第十章 集群和工作队列

    一个容易调适的系统可能胜过一个更快的系统。

    • 启动组件:cron任务,Circus或supervisord
    • 测试容灾的组件:ChaosMonkey
    • 部署系统:Fabric、Salt、Chef或Puppet

    下面几个都是集群化的方案

    Parallel Python模块

    • 几乎没有依赖性,接口简单;
    • 不是很强大,缺少通信机制

    Ipython Parallel

    IPython作为shell做并行任务控制,依赖ZeroMQ。

    NSQ

    是一个可随时投入生产的队列系统,有持久性和扩展性。

    其他集群化的工具

    • Celery
    • Gearman
    • PyRes
    • 亚马逊的简单队列服务(SQS)

    第十一章 使用更少的RAM

    基础对象开销高:100000000项的list要消耗760MB的内存,可以替换成array,array是连续的内存块,而且array可以直接传递给C++层不需要额外的转换。

    python3对字符串的存储效率相比python2提高了很多。

    image

    高效地存储文本,trie树和有向无环图 (DAWG)(双trie树结构)单词图:

    通过允许概率误差来减少数据集需要的内存空间:

    • Morris计数器
    • 布隆过滤器
    • loglog计数器

    End.