• Linux 内存管理 概述与深入理解

    为什么要学习内存管理 （WHY）

    关注越界访问，避免有类型错误或者算术溢出带来的内存问题

    比如 char类型，在127+1后编程-128，导致越界访问或者擦写内存的问题。

    避免内存泄漏

    了解内存分配与释放机制，避免进行某些会导致内存泄漏的操作。

    段错误

    了解段错误发生的机制，淡定填坑。

    Double Free

    关注双重释放带来的后果，对free操作有敬畏之心。

    内存碎片与性能

    了解分配机制，避免内存碎片以及分配和释放带来的性能影响

    性能瓶颈问题分析

    应用可能一条语句，内核就要执行上千条。正所谓“领导一句话，下属跑断腿” io read write发生了两次，用mmap只需要一次拷贝 

    • 如何处理CPU指令重排问题？
    • 如何高效利用Cpu Cache？
    • 如何利用CPU 分支预测（乱序执行）？
    • 如何利用内存指令重排代替锁，实现无锁队列或同步问题？

    内存映射几种类型

    私有匿名映射

    各进程不共享，fork之后，会进行写时复制

        mmap(NULL, 1024, PORT_WRITE|PORT_READ, MAP_ANON|MAP_PRIVATE, -1, 0)

    共享匿名映射

    各进程共享，会写时复制，常用进程间通信

        mmap(NULL, 1024, PORT_WRITE|PORT_READ, MAP_ANON|MAP_SHARED, -1, 0)

    私有文件映射

    各进程不共享，常见是私有的动态库加载

        mmap(NULL, 1024, PORT_WRITE|PORT_READ, MAP_RPIVATE, fd, 0)

    共享文件映射

    各进程共享，文件映射，传输

        mmap(NULL, 1024, PORT_WRITE|PORT_READ, MAP_SHARED, fd, 0)

    查看命令：

        cat /proc/<pid>/maps

    进程地址空间

    简介

    在Linux中，3G~4G的内存空间，划分给了内核，所有进程中该部分都是一样的。 地址由低到高，分别是代码段区域，数据段区域（Data, Bss）、堆区、栈区。其中栈区和堆区之间，存放着mmap开辟的内存映射区域。一般栈的生长方向是由高地址向低地址。而堆则是由低至高地址生长。堆区的顶部指针，称为brk地址。在内核空间中，将一部分虚拟地址空间线性映射至物理地址空间中，32位中一般为896M，这部分称为低端内存。剩下一部分常规可分配内存称为高端内存（还有一部分是DMA内存区）。

    内存分配

    从进程地址空间可以看出，用户分配小内存，则是在堆区线性扩展。向上增大或者向下减小区域，对于通过brk系统调用来完成。 另外，对于分配大内存，超过128K时，使用mmap系统调用来在堆区和栈区之间分配内存。 

    malloc工作原理

    参考：linux - How does glibc malloc work? - Reverse Engineering Stack Exchange

    malloc内存块组织方式

    1. 内存块头部
    2. {
    3.     块状态： 空闲，在使用；
    4.     前一块指针；
    5.     下一块指针；
    6.     内存块大小：
    7. }

    glic malloc源码位置:malloc.c source code [glibc/malloc/malloc.c] - Woboq Code Browser

    分配的特点是通过bins管理大小相近的内存。对于ptmalloc一般有fast bins, smaller bins, unsorted bins ， larger bins, 四种类型。基本上每种bins的相邻间隔为8个字节，每个bin可能是单向链表或双向链表。对于fast bins一般是不大于64B, smaller bins <= 512B， larger bins > 512B 且128K。 unsorted bins没有规定具体大小，是一个临时管理链表可以存放临时合并的chunk。 对于大于128K之类的内存，会统一放在mmaped chunk 中，释放时直接归还给系统。

    malloc分配的是虚拟地址，管理的是虚拟内存的分配。那么对于物理内存如何管理呢？物理内存的分配使用相关的有slab/slub/slob分配器，还有著名的buddy system伙伴系统。

    Buddy System 伙伴系统

     伙伴系统最小分配单位是页，并且以页的阶数分配。两个页快是否为伙伴的规则如下：

    1. 大小相同，物理连续的两个页块。
    2. n阶的页块，第一个页框编号为2^n的整数倍
    3. 两个相邻n阶页块合并成n+1阶之后，第一个页框编号也为2^(n+1)的整数倍

    linux默认最大分配是10阶页块。在include/linux/mmzone.h 中设置。

    伙伴系统的引入主要是用来解决内存外部碎片的问题。既然有内存外部碎片问题，那就有内存内部碎片的问题。外部碎片是指，没有分配的内存无法利用起来。内部碎片是指已经分配的内存只利用了部分，剩下的内存没有利用起来。而slab分配器的引入，解决了内存内部碎片的问题。

    Slab 分配器

     slab是按照对象的概念来缓冲的。比如上述如果一个对象是512个字节，那么一页就可以换成8个对象。slab的工作就是管理这个8个对象的分配和释放。这里slab管理的内存区为线性映射器区，即虚拟地址和物理地址是线性关系，对于linux一般这个区域大小为896M。常见的内核驱动的对象分配比如kmalloc,kmem_cache_alloc这些接口内部即使使用slab来管理。

    虚拟地址与物理地址的映射关系

    1. 为什么不直接一一映射？内存不足

    2. 为什么采用了多级的映射？节约内存

    3. 为什么有TLB块表？cache

    4. 相同虚拟地址TLB如何区分？flush， ASID。

    5. 不同进程访问共享的内核地址空间如何提高效率？nG , G标志

    6. 为什么有写时复制？避免在fork时就拷贝大量的物理内存数据

    7. mmu和cache哪个先访问？都可以，取决于TLB放在Cache之前还是之后。各有利弊

    8. cache这么小如何缓存这么大的地址空间？ (set) = (memory address) / (line size) % (number of sets)

    (critical stride) = (number of sets) * (line size) = (total cache size) / (number of ways).

    在linux上，查看虚拟地址与物理地址的关系：https://github.com/jethrogb/ptdump

    1. git clone https://github.com/jethrogb/ptdump
    2. cd ptdump/dump/linux/
    3. make
    4. sudo insmod ptdump.ko
    5. ls /proc/page*

     运行测试app. test_virtual_address例程：

    • 运行：test_virtual_address， 读取father.log并跟cat /proc//maps比较，发现申请的内存并没有物理地址。
    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. #include 
    9. #include 
    10. #include 
    11. #include 
    12. #include 
    13. #include 
    14. #include 
    15. #include 
    16.  
    17. struct Page {
    18.     uint64_t address;
    19.     uint64_t entry[512];
    20. };
    21.  
    22. uint64_t get_phy_address(uint64_t entry)
    23. {
    24.     static const uint64_t mask = (1LL<<63) | ((1<<12)-1);
    25.     return entry & ~mask;
    26. }
    27.  
    28. bool writable(uint64_t entry)
    29. {
    30.     return (entry & (1 << 1)) != 0;
    31. }
    32.  
    33. bool executable(uint64_t entry)
    34. {
    35.     return (entry & (1LL << 63)) == 0;
    36. }
    37.  
    38. bool user_mode(uint64_t entry)
    39. {
    40.     return (entry & (1LL << 2)) != 0;
    41. }
    42.  
    43. void print_entry(FILE *fp, int level, uint64_t entry, uint64_t virtual_address)
    44. {
    45.    fprintf(fp, "%d\t0x%-16llx\t0x%-16llx\t%d\t%d\t%d\n", level, get_phy_address(entry), virtual_address, 
    46. 		   writable(entry),executable(entry),user_mode(entry));
    47. }
    48.  
    49. void dump(FILE *fp, const Page*& page, int level, uint64_t virtual_address)
    50. {
    51.     const Page *curr_page=page++;
    52.     for (int i = 0; i < 512; i++) {
    53.         const uint64_t entry = curr_page->entry[i];
    54. 	const uint64_t child_virtual_address = (virtual_address << 9) | i;
    55. 	if (level > 0) {
    56.              if (entry & 1) {
    57. 	         if (!(entry &(1 << 7))) {
    58. 		     dump(fp, page, level-1, child_virtual_address);		 
    59. 		 }else {
    60. 		     print_entry(fp, level, entry, child_virtual_address << (level*9+12));
    61. 		 }
    62. 	     }	
    63. 	} else {
    64. 	   if (entry) {
    65. 	      print_entry(fp, level, entry, child_virtual_address << 12);
    66. 	   }
    67. 	}
    68.     }
    69. }
    70.  
    71. void dump_table(FILE *fp)
    72. {
    73.     std::ifstream ifs("/proc/page_table_3", std::ios::binary);
    74.     if (!ifs) {
    75.     	return ;
    76.     }
    77.     std::string content((std::istreambuf_iterator<char>(ifs)), std::istreambuf_iterator<char>());
    78.     const Page *page = (const Page *)&content[0];
    79.     const Page *end_page = (const Page *)(&content[0]+content.length());
    80.     dump(fp, page, 3,  0);
    81.     std::cout<< (const void *)end_page << "\t" << (const void *)page << std::endl;
    82.     std::flush(std::cout);
    83. }
    84.  
    85. int main(int argc, char **argv)
    86. {
    87.     int cpu_index =0;
    88.     if(argc >= 3) cpu_index=atoi(argv[2]); 
    89.  
    90.     cpu_set_t set; 
    91.     CPU_ZERO(&set); 
    92.     CPU_SET(cpu_index, &set); 
    93.     sched_setaffinity(0, sizeof(set), &set); 
    94.  
    95.     const size_t asize = 1024*1024*8;
    96.  
    97.     bool hugetable = false;
    98.     bool do_fork = false;
    99.     bool do_write = false;
    100.     if (argc >= 2) {
    101.         switch (argv[1][0])
    102.         {
    103.             case 'h':  hugetable=true;do_write=true; break;
    104.             case 'f':  do_fork=true;do_write=true; break;
    105.             case 'w':  do_write=true; break;
    106.             default:break;
    107.         }
    108.     }
    109.     char *virtual_ptr = (char *)mmap(NULL, asize, PROT_READ|PROT_WRITE, 
    110. 		    MAP_ANONYMOUS|MAP_PRIVATE|(hugetable?MAP_HUGETLB:0), -1, 0);
    111.     if (do_write) *virtual_ptr = '\0';
    112.     FILE *fp = NULL;
    113.     std::cout<< "father pid: " << getpid() << std::endl; 
    114.     if (do_fork) {
    115.     	pid_t pid = fork();
    116. 	if (pid == 0) {
    117. 	    fp = fopen("child.log", "w");
    118.             std::cout<< "child pid: " << getpid() << std::endl; 
    119. 	}else {
    120. 	    fp = fopen("father.log", "w");
    121. 	}
    122.     } else {
    123.         fp = fopen("father.log", "w");
    124.     }
    125.     fprintf(fp, "pid=%d map address: %p\n", getpid(), virtual_ptr);
    126.     dump_table(fp);
    127.     fclose(fp);
    128.     while(true) {
    129.        usleep(10000); 
    130.     }
    131.     return 0;
    132. }
    133.

    • 运行：test_virtual_address w， 读取father.log并跟cat /proc//maps比较，发现申请的内存有了物理地址。

      

    •   运行：test_virtual_address f， 读取father.log和child.log并跟cat /proc//maps比较，可以看到写时复制时的工作原理。注意看权限的不同。

      

    普通文件read和文件映射mmap读取速度比较

    1.  
    2. static void test_file_read()
    3. {
    4.    FILE *fp = NULL;
    5.    fp = fopen(FILE_NAME, "rb+");
    6.    char *buff = (char *)malloc(1024);
    7.    int len = 0;
    8.    size_t sum = 0;
    9.    size_t fsize;
    10.    fseek(fp,0,SEEK_END);
    11.    fsize=ftell(fp);
    12.    auto start = std::chrono::high_resolution_clock::now();
    13.    for (int n = 0; n < 100; n++) {
    14.        fseek(fp,0,SEEK_SET);
    15.        while((len=fread(buff, 1,1024, fp)) >0 ) {
    16.            sum +=len;
    17.        }
    18.    }
    19.    auto end = std::chrono::high_resolution_clock::now();
    20. 	size_t use_time = std::chrono::duration_cast(end-start).count();
    21. 	std::cout << "test_file_read elapsed milliseconds: " << use_time << std::endl;
    22. 	std::flush(std::cout);
    23.    
    24.    printf("size=%ld\n", sum);
    25.    fclose(fp);
    26.    free(buff);
    27. }
    28.  
    29. static void test_mmap_read()
    30. {
    31.    FILE *fp = NULL;
    32.    fp = fopen(FILE_NAME, "rb+");
    33.    char *buff = (char *)malloc(1024);
    34.    int len;
    35.    size_t sum = 0;
    36.    int readsize;
    37.    size_t fsize;
    38.    size_t size;
    39.    fseek(fp,0,SEEK_END);
    40.    fsize=ftell(fp);
    41.    fseek(fp,0,SEEK_SET);
    42.    size = fsize;
    43.    fclose(fp);
    44.    int ffd = open(FILE_NAME, O_RDWR|O_CREAT,0666);
    45.    char *ptr=(char *)mmap(NULL, size, PROT_READ, MAP_SHARED, ffd, 0);
    46.    close(ffd);
    47.    char *readPtr = NULL; 
    48.    
    49.    auto start = std::chrono::high_resolution_clock::now();
    50.    for (int n = 0; n < 100; n++) { 
    51.        readPtr = ptr; 
    52.        size = fsize;
    53.        while(size){
    54.            readsize = size > 1024 ? 1024 : size;
    55.            memcpy(buff, readPtr, readsize); 
    56.            size -= readsize;
    57.            readPtr += readsize; 
    58.            sum += 1024;
    59.        }
    60.    }
    61. 	auto end = std::chrono::high_resolution_clock::now();
    62. 	size_t use_time = std::chrono::duration_cast(end-start).count();
    63. 	std::cout << "test_mmap_read elapsed milliseconds: " << use_time << std::endl;
    64. 	std::flush(std::cout);
    65.    free(buff);
    66.    munmap(buff, fsize);
    67.    printf("size=%ld\n", sum);
    68. }

    运行test_mmap f  和test_mmap m

    1. ~/test_perf$ ./show_perf.sh ./test_mmap f
    2. run ./test_mmap f 
    3. test_file_read elapsed milliseconds: 2245
    4. size=10485760000
    5.  
    6.  Performance counter stats for './test_mmap f':
    7.  
    8.         74,743,510      cache-references          #   36.454 M/sec                  
    9.         35,690,848      cache-misses              #   47.751 % of all cache refs    
    10.      8,925,687,804      instructions                                                
    11.      1,367,859,141      branches                  #  667.137 M/sec                  
    12.          3,955,388      branch-misses             #    0.29% of all branches        
    13.                117      faults                    #    0.057 K/sec                  
    14.                219      context-switches          #    0.107 K/sec                  
    15.        2050.342526      task-clock (msec)         #    0.909 CPUs utilized          
    16.                  0      migrations                #    0.000 K/sec                  
    17.  
    18.        2.256351930 seconds time elapsed
    19.  
    20. ~/test_perf$ ./show_perf.sh ./test_mmap m
    21. run ./test_mmap m 
    22. test_mmap_read elapsed milliseconds: 489
    23. size=10485760000
    24.  
    25.  Performance counter stats for './test_mmap m':
    26.  
    27.         62,951,973      cache-references          #  127.169 M/sec                  
    28.         18,601,851      cache-misses              #   29.549 % of all cache refs    
    29.      1,502,833,265      instructions                                                
    30.        147,082,645      branches                  #  297.121 M/sec                  
    31.             24,354      branch-misses             #    0.02% of all branches        
    32.              1,718      faults                    #    0.003 M/sec                  
    33.                  8      context-switches          #    0.016 K/sec                  
    34.         495.025615      task-clock (msec)         #    0.995 CPUs utilized          
    35.                  0      migrations                #    0.000 K/sec                  
    36.  
    37.        0.497508855 seconds time elapsed

     

     

     利用缓存命中提高性能

    cache-misses

    • 小结构体遍历： test_cache_miss s
    • 大结构体遍历： test_cache_miss b
    • 数组遍历:  test_cache_miss a
    • vector遍历： test_cache_miss v
    • 按行顺序遍历: test_cache_miss a
    • 按列顺序遍历:test_cache_miss i
    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. //#pragma pack(64)
    7. typedef struct {
    8.     int cnt;
    9.     std::string str;
    10.     char resv[24];
    11. }algin_data_t __attribute__((aligned(64)));
    12. //#pragma pack()
    13.  
    14. typedef struct {
    15.     int cnt;
    16.     std::string str;
    17. }small_data_t;
    18.  
    19. typedef struct {
    20.     int cnt;
    21.     char str[128];
    22. }big_data_t;
    23.  
    24.  
    25. static void test_small_struct()
    26. {
    27.     std::vector<small_data_t> dat(10000);
    28.     int num=0;
    29.     for (int i = 0; i < 10000; i++) {
    30.         for (auto &e:dat) {
    31.            e.cnt = num++;
    32.         }
    33.     }
    34. }
    35. static void test_algin_struct()
    36. {
    37.     std::vector<algin_data_t> dat(10000);
    38.     int num=0;
    39.     for (int i = 0; i < 10000; i++) {
    40.         for (auto &e:dat) {
    41.            e.cnt = num++;
    42.         }
    43.     }
    44. }
    45.  
    46. static void test_big_struct()
    47. {
    48.     std::vector<big_data_t> dat(10000);
    49.     int num=0;
    50.     for (int i = 0; i < 10000; i++) {
    51.         for (auto &e:dat) {
    52.            e.cnt = num++;
    53.         }
    54.     }
    55. }
    56.  
    57. static void test_vector_foreach()
    58. {
    59.     std::vectorint>> dat(10000, std::vector<int>(64, 0));
    60.     int num=0;
    61. 	for (int cnt = 0; cnt < 100; cnt++) {
    62. 		for (int i = 0; i < 10000; i++) {
    63. 			for (int j = 0; j < 64; j++) {
    64. 			   dat[i][j] = num++;
    65. 			}
    66. 		}
    67. 	}
    68. }
    69. static int dat_array[10000][64];
    70. static void test_array_foreach()
    71. {
    72.     int num=0;
    73. 	for (int cnt = 0; cnt < 100; cnt++) {
    74. 		for (int i = 0; i < 10000; i++) {
    75. 			for (int j = 0; j < 64; j++) {
    76. 			   dat_array[i][j] = num++;
    77. 			}
    78. 		}
    79. 	}
    80. }
    81. static void test_array_inv_foreach()
    82. {
    83.     int num=0;
    84. 	for (int cnt = 0; cnt < 100; cnt++) {
    85. 		for (int i = 0; i < 64; i++) {
    86. 			for (int j = 0; j < 10000; j++) {
    87. 			   dat_array[j][i] = num++;
    88. 			}
    89. 		}
    90. 	}
    91. }
    92. int main(int argc, char **argv)
    93. {
    94.     if(argc <= 1) {
    95.        printf("exe b or exe s\n");
    96.        return 0;
    97.     }
    98.     printf("small=%d algin:%d\n", sizeof(small_data_t), sizeof(algin_data_t)); 
    99.     switch (argv[1][0])
    100.     {
    101.         case 's':  test_small_struct(); break;
    102.         case 'b':  test_big_struct(); break;
    103. 		
    104.         case 'a':  test_array_foreach(); break;
    105.         case 'v':  test_vector_foreach(); break;
    106.         case 'i':  test_array_inv_foreach(); break;
    107.         
    108.         case 'l':  test_algin_struct(); break;
    109.         default:break;
    110.     }    
    111.     return 0;
    112. }
    113.  
    1. ~/test_perf$ ./show_perf.sh ./test_branch_miss s
    2. run ./test_branch_miss s 
    3.  
    4.  Performance counter stats for './test_branch_miss s':
    5.  
    6.             35,237      cache-references          #    1.035 M/sec                  
    7.             15,563      cache-misses              #   44.167 % of all cache refs    
    8.        127,110,597      instructions                                                
    9.         31,639,756      branches                  #  929.747 M/sec                  
    10.             67,240      branch-misses             #    0.21% of all branches        
    11.                111      faults                    #    0.003 M/sec                  
    12.                  0      context-switches          #    0.000 K/sec                  
    13.          34.030495      task-clock (msec)         #    0.969 CPUs utilized          
    14.                  0      migrations                #    0.000 K/sec                  
    15.  
    16.        0.035105508 seconds time elapsed
    17.  
    18. ~/test_perf$ ./show_perf.sh ./test_branch_miss b
    19. run ./test_branch_miss b 
    20.  
    21.  Performance counter stats for './test_branch_miss b':
    22.  
    23.             38,823      cache-references          #   20.861 M/sec                  
    24.             12,309      cache-misses              #   31.705 % of all cache refs    
    25.          2,843,103      instructions                                                
    26.            485,745      branches                  #  261.009 M/sec                  
    27.             15,449      branch-misses             #    3.18% of all branches        
    28.                102      faults                    #    0.055 M/sec                  
    29.                  0      context-switches          #    0.000 K/sec                  
    30.           1.861031      task-clock (msec)         #    0.679 CPUs utilized          
    31.                  0      migrations                #    0.000 K/sec                  
    32.  
    33.        0.002742285 seconds time elapsed
    34.  
    35. ~/test_perf$ ./show_perf.sh ./test_branch_miss a
    36. run ./test_branch_miss a 
    37.  
    38.  Performance counter stats for './test_branch_miss a':
    39.  
    40.             45,370      cache-references          #    0.627 M/sec                  
    41.             15,784      cache-misses              #   34.790 % of all cache refs    
    42.        121,528,996      instructions                                                
    43.         30,681,381      branches                  #  423.988 M/sec                  
    44.          4,005,835      branch-misses             #   13.06% of all branches        
    45.                111      faults                    #    0.002 M/sec                  
    46.                  2      context-switches          #    0.028 K/sec                  
    47.          72.363755      task-clock (msec)         #    0.975 CPUs utilized          
    48.                  0      migrations                #    0.000 K/sec                  
    49.  
    50.        0.074219125 seconds time elapsed
    51.  
    52. ~/test_perf$ ./show_perf.sh ./test_branch_miss v
    53. run ./test_branch_miss v 
    54.  
    55.  Performance counter stats for './test_branch_miss v':
    56.  
    57.             31,512      cache-references          #    9.504 M/sec                  
    58.             12,034      cache-misses              #   38.189 % of all cache refs    
    59.          2,857,202      instructions                                                
    60.            488,248      branches                  #  147.256 M/sec                  
    61.             14,946      branch-misses             #    3.06% of all branches        
    62.                103      faults                    #    0.031 M/sec                  
    63.                  0      context-switches          #    0.000 K/sec                  
    64.           3.315638      task-clock (msec)         #    0.678 CPUs utilized          
    65.                  0      migrations                #    0.000 K/sec                  
    66.  
    67.        0.004890918 seconds time elapsed
    68.  
    69. ~/test_perf$ ./show_perf.sh ./test_branch_miss i
    70. run ./test_branch_miss i 
    71.  
    72.  Performance counter stats for './test_branch_miss i':
    73.  
    74.             31,792      cache-references          #   13.768 M/sec                  
    75.             13,951      cache-misses              #   43.882 % of all cache refs    
    76.          2,864,321      instructions                                                
    77.            489,395      branches                  #  211.938 M/sec                  
    78.             14,898      branch-misses             #    3.04% of all branches        
    79.                103      faults                    #    0.045 M/sec                  
    80.                  0      context-switches          #    0.000 K/sec                  
    81.           2.309145      task-clock (msec)         #    0.704 CPUs utilized          
    82.                  0      migrations                #    0.000 K/sec                  
    83.  
    84.        0.003280504 seconds time elapsed
    1. #!/bin/sh
    2. echo "run $* "
    3. perf stat -B -e cache-references,cache-misses,instructions,branches,branch-misses,faults,context-switches,task-clock,migrations $*
    • 热点数据紧凑合并 :  ./test_together
    • 热点数据分散合并 : ./test_together
    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. #include 
    9. #include 
    10. #include 
    11. #include 
    12. #include 
    13. #include 
    14. #include 
    15. #include 
    16.  
    17. static const int array_size = 1024;
    18.  
    19. struct Dat_One{
    20. 	int buff_one[array_size];
    21. 	int buffer_two[array_size];
    22. };
    23. static Dat_One dat_one;
    24.  
    25. struct Dat_Two{
    26. 	int buff_one;
    27. 	int buffer_two;
    28. };
    29. static Dat_Two dat_two[array_size];
    30.  
    31. static int do_func(int dat)
    32. {
    33. 	static int sum = 0;
    34. 	sum++;
    35. 	return dat;
    36. }
    37. static void test1()
    38. {
    39.    auto start = std::chrono::high_resolution_clock::now();
    40.     for (int n = 0; n < 10000; n++)
    41.          for (int j = 0; j < array_size; j++) {
    42.              dat_one.buffer_two[j] = do_func(dat_one.buff_one[j]);
    43.          }
    44.     auto end = std::chrono::high_resolution_clock::now();
    45.     size_t use_time = std::chrono::duration_cast(end-start).count();
    46.     std::cout << "big struct : elapsed milliseconds: " << use_time << std::endl;
    47.     std::flush(std::cout);
    48. }
    49. static void test2()
    50. {
    51.    auto start = std::chrono::high_resolution_clock::now();
    52.     for (int n = 0; n < 10000; n++)
    53.          for (int j = 0; j < array_size; j++) {
    54.              dat_two[j].buffer_two= do_func(dat_two[j].buff_one);
    55.          }
    56.     auto end = std::chrono::high_resolution_clock::now();
    57.     size_t use_time = std::chrono::duration_cast(end-start).count();
    58.     std::cout << "small struct : elapsed milliseconds: " << use_time << std::endl;
    59.     std::flush(std::cout);
    60. }
    61.  
    62.  
    63. int main(int argc, char **argv)
    64. {
    65.     int cpu_index =0;
    66.     if(argc >= 3) cpu_index=atoi(argv[2]); 
    67.  
    68.     cpu_set_t set; 
    69.     CPU_ZERO(&set); 
    70.     CPU_SET(cpu_index, &set); 
    71.     sched_setaffinity(0, sizeof(set), &set); 
    72.  
    73.     test1();
    74.     test2();
    75.  
    76.     return 0;
    77. }
    78.

    • 增加无用数据减少cache冲突: test_Tmat 2 && test_Tmat 3
    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. #include 
    9. #include 
    10. #include 
    11. #include 
    12. #include 
    13. #include 
    14. #include 
    15. #include 
    16.  
    17. //(critical stride) = (number of sets)*(line size) = (total cache size) / (number of ways).
    18. //: (set) = (memory address) / (line size) % (number of sets)
    19. //cat /sys/devices/system/cpu/cpu0/cache/index0/ways_of_associativity 
    20. //cat /sys/devices/system/cpu/cpu0/cache/index0/number_of_sets
    21.  
    22. //answer : https://stackoverflow.com/questions/11413855/why-is-transposing-a-matrix-of-512x512-much-slower-than-transposing-a-matrix-of
    23. //sudo perf stat -e cache-misses ./test_Tmat 2
    24.  
    25.  
    26. #define MATSIZE_512 (4096UL) //L1 cache miss
    27. #define MATSIZE_513 (4096UL+16)
    28.  
    29.  
    30. static void transpose_mat512()
    31. {
    32.    const size_t alloc_size = MATSIZE_512*MATSIZE_512;
    33.    std::cout << alloc_size << std::endl;
    34.    char *total_mem = (char *)malloc(alloc_size);
    35.    assert(total_mem != nullptr);
    36.    char (*mat_512)[MATSIZE_512] = (char (*)[MATSIZE_512])total_mem;
    37.    auto start = std::chrono::high_resolution_clock::now();
    38.     for (int n = 0; n < 10; n++)
    39.      for (int i = 1; i < MATSIZE_512; i++)
    40.          for (int j = 0; j < i; j++) {
    41.               int temp = mat_512[i][j];
    42.               mat_512[i][j] = mat_512[j][i];
    43.               mat_512[j][i] = temp;
    44.          }
    45.     auto end = std::chrono::high_resolution_clock::now();
    46.     size_t use_time = std::chrono::duration_cast(end-start).count();
    47.     std::cout << "mat512x512 elapsed milliseconds: " << use_time << std::endl;
    48.     std::flush(std::cout);
    49. 	free(total_mem);
    50. }
    51. static void transpose_mat513()
    52. {
    53. 	const size_t alloc_size = MATSIZE_513*MATSIZE_513;
    54.    char *total_mem = (char *)malloc(alloc_size);
    55.    assert(total_mem != nullptr);
    56.    char (*mat_513)[MATSIZE_513] = (char (*)[MATSIZE_513])total_mem;
    57.    auto start = std::chrono::high_resolution_clock::now();
    58.     for (int n = 0; n < 10; n++)
    59.      for (int i = 1; i < MATSIZE_513; i++)
    60.          for (int j = 0; j < i; j++) {
    61.               int temp = mat_513[i][j];
    62.               mat_513[i][j] = mat_513[j][i];
    63.               mat_513[j][i] = temp;
    64.          }
    65.     auto end = std::chrono::high_resolution_clock::now();
    66.     size_t use_time = std::chrono::duration_cast(end-start).count();
    67.     std::cout << "mat513x513 elapsed milliseconds: " << use_time << std::endl;
    68.     std::flush(std::cout);
    69. 	free( total_mem);
    70. }
    71.  
    72.  
    73.  
    74. int main(int argc, char **argv)
    75. {
    76.     int cpu_index =0;
    77.     if(argc >= 3) cpu_index=atoi(argv[2]); 
    78.  
    79.     cpu_set_t set; 
    80.     CPU_ZERO(&set); 
    81.     CPU_SET(cpu_index, &set); 
    82.     sched_setaffinity(0, sizeof(set), &set); 
    83. 	switch(argv[1][0]) {
    84. 		case '2' :   transpose_mat512();break;
    85. 		case '3' :   transpose_mat513();break;
    86. 	}
    87.  
    88.     return 0;
    89. }
    90.  
    1. ~/test_perf$ ./show_perf.sh ./test_Tmat 2
    2. run ./test_Tmat 2 
    3. 16777216
    4. mat512x512 elapsed milliseconds: 2721
    5.  
    6.  Performance counter stats for './test_Tmat 2':
    7.  
    8.         99,403,455      cache-references          #   36.646 M/sec                  
    9.         55,481,043      cache-misses              #   55.814 % of all cache refs    
    10.      4,075,121,270      instructions                                                
    11.        252,150,019      branches                  #   92.958 M/sec                  
    12.            728,994      branch-misses             #    0.29% of all branches        
    13.              8,297      faults                    #    0.003 M/sec                  
    14.                 20      context-switches          #    0.007 K/sec                  
    15.        2712.515229      task-clock (msec)         #    0.995 CPUs utilized          
    16.                  1      migrations                #    0.000 K/sec                  
    17.  
    18.        2.725778361 seconds time elapsed
    19.  
    20. ~/test_perf$ ./show_perf.sh ./test_Tmat 3
    21. run ./test_Tmat 3 
    22. mat513x513 elapsed milliseconds: 816
    23.  
    24.  Performance counter stats for './test_Tmat 3':
    25.  
    26.          4,054,160      cache-references          #    4.947 M/sec                  
    27.          2,411,165      cache-misses              #   59.474 % of all cache refs    
    28.      4,499,294,985      instructions                                                
    29.        172,637,350      branches                  #  210.638 M/sec                  
    30.             73,871      branch-misses             #    0.04% of all branches        
    31.              8,360      faults                    #    0.010 M/sec                  
    32.                  5      context-switches          #    0.006 K/sec                  
    33.         819.594449      task-clock (msec)         #    0.996 CPUs utilized          
    34.                  1      migrations                #    0.001 K/sec                  
    35.  
    36.        0.822494459 seconds time elapsed

    branch-misses

    • 随机数组遍历条件执行： test_branch_miss a
    • 随机数组排序后遍历条件执行： test_branch_miss s
    • likely和unlikely干预分支预测： test_branch_miss n  ;  test_branch_miss l
    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #define likely(x) __builtin_expect(!!(x), 1)
    7. #define unlikely(x) __builtin_expect(!!(x), 0)
    8. static int dat_array[10000];
    9. static void test_array_foreach()
    10. {
    11.     int num=0;
    12.     
    13. 	for (int i = 0; i < 10000; i++) {          
    14.               dat_array[i]=rand()%512;		
    15.         }
    16. 	for (int cnt = 0; cnt < 1000; cnt++) {
    17. 		for (int i = 0; i < 10000; i++) {
    18. 			  if( dat_array[i] > 256) {
    19.                             dat_array[i]=num++;
    20.                           }
    21. 		}
    22. 	}
    23. }
    24.  
    25. volatile int test_a;
    26. static inline void test_no_use()
    27. {
    28.      test_a = 1000;
    29.      test_a += 1;
    30.      test_a *= 10;
    31.      test_a /= 3;
    32.      test_a <<= 1;
    33. }
    34. static void test_array_sort_foreach()
    35. {
    36.     int num=0;
    37.          
    38. 	for (int i = 0; i < 10000; i++) {          
    39.               dat_array[i]=rand()%512;		
    40.         }
    41.  
    42.         std::sort(dat_array, dat_array+10000);
    43.  
    44. 	for (int cnt = 0; cnt < 1000; cnt++) {
    45. 		for (int i = 0; i < 10000; i++) {
    46. 			  if( dat_array[i] > 256) {
    47.                             dat_array[i]=num++;
    48.                            }
    49.                  }
    50.         }
    51. }
    52.  
    53. static void test_nolikely_foreach()
    54. {
    55.     int num=0;
    56.         
    57. 	for (int i = 0; i < 10000; i++) {          
    58.         dat_array[i]=rand()%512;		
    59.     }
    60. 	for (int cnt = 0; cnt < 10000; cnt++) {
    61. 		for (int i = 0; i < 10000; i++) {
    62. 			  if( dat_array[i] > 50) {
    63.                             dat_array[i]=num;
    64. 			                num+=2;
    65.                             test_no_use();
    66.                           }else {
    67.                             dat_array[i]=num;
    68.                             num++;
    69.                           }
    70. 		       }
    71.         }
    72. }
    73.  
    74. static void test_likely_foreach()
    75. {
    76.     int num=0;
    77.         
    78. 	for (int i = 0; i < 100000; i++) {          
    79.               dat_array[i]=rand()%512;		
    80.         }
    81. 	for (int cnt = 0; cnt < 1000; cnt++) {
    82. 		for (int i = 0; i < 10000; i++) {
    83. 			  if(likely( dat_array[i] > 50)) {
    84.                             dat_array[i]=num;
    85. 			                num+=2;
    86.                             test_no_use();
    87.                           }else {
    88.                             dat_array[i]=num;
    89.                             num++;
    90.                          }
    91.                 }
    92.         }
    93. }
    94.  
    95. int main(int argc, char **argv)
    96. {
    97.     if(argc <= 1) {
    98.        printf("exe b or exe s\n");
    99.        return 0;
    100.     }
    101.  
    102.     switch (argv[1][0])
    103.     {
    104.         case 's':  test_array_sort_foreach(); break;
    105.         case 'a':  test_array_foreach(); break;
    106.         case 'n':  test_nolikely_foreach(); break;
    107.         case 'l':  test_likely_foreach(); break;
    108. 		
    109.         default:break;
    110.     }    
    111.     return 0;
    112. }
    113.  
    1. ~/test_perf$ ./show_perf.sh ./test_branch_miss a
    2. run ./test_branch_miss a 
    3.  
    4.  Performance counter stats for './test_branch_miss a':
    5.  
    6.             37,087      cache-references          #    0.527 M/sec                  
    7.             13,650      cache-misses              #   36.805 % of all cache refs    
    8.        121,502,626      instructions                                                
    9.         30,676,994      branches                  #  435.643 M/sec                  
    10.          4,005,535      branch-misses             #   13.06% of all branches        
    11.                110      faults                    #    0.002 M/sec                  
    12.                  0      context-switches          #    0.000 K/sec                  
    13.          70.417747      task-clock (msec)         #    0.979 CPUs utilized          
    14.                  0      migrations                #    0.000 K/sec                  
    15.  
    16.        0.071961280 seconds time elapsed
    17.  
    18. ~/test_perf$ ./show_perf.sh ./test_branch_miss s
    19. run ./test_branch_miss s 
    20.  
    21.  Performance counter stats for './test_branch_miss s':
    22.  
    23.             34,839      cache-references          #    0.856 M/sec                  
    24.             15,265      cache-misses              #   43.816 % of all cache refs    
    25.        127,107,931      instructions                                                
    26.         31,638,325      branches                  #  777.609 M/sec                  
    27.             67,152      branch-misses             #    0.21% of all branches        
    28.                112      faults                    #    0.003 M/sec                  
    29.                  0      context-switches          #    0.000 K/sec                  
    30.          40.686661      task-clock (msec)         #    0.966 CPUs utilized          
    31.                  0      migrations                #    0.000 K/sec                  
    32.  
    33.        0.042110582 seconds time elapsed
    34.  
    35. ~/test_perf$ ./show_perf.sh ./test_branch_miss n
    36. run ./test_branch_miss n 
    37.  
    38.  Performance counter stats for './test_branch_miss n':
    39.  
    40.             46,054      cache-references          #    0.111 M/sec                  
    41.             20,105      cache-misses              #   43.655 % of all cache refs    
    42.      4,304,097,649      instructions                                                
    43.        600,785,471      branches                  # 1452.078 M/sec                  
    44.             34,768      branch-misses             #    0.01% of all branches        
    45.                110      faults                    #    0.266 K/sec                  
    46.                  7      context-switches          #    0.017 K/sec                  
    47.         413.741881      task-clock (msec)         #    0.994 CPUs utilized          
    48.                  0      migrations                #    0.000 K/sec                  
    49.  
    50.        0.416110095 seconds time elapsed
    51.  
    52. ~/test_perf$ ./show_perf.sh ./test_branch_miss l
    53. run ./test_branch_miss l 
    54. ./test_branch_miss: Segmentation fault
    55.  
    56.  Performance counter stats for './test_branch_miss l':
    57.  
    58.             41,754      cache-references          #    9.202 M/sec                  
    59.             15,556      cache-misses              #   37.256 % of all cache refs    
    60.          3,663,840      instructions                                                
    61.            688,072      branches                  #  151.649 M/sec                  
    62.             16,502      branch-misses             #    2.40% of all branches        
    63.                109      faults                    #    0.024 M/sec                  
    64.                  2      context-switches          #    0.441 K/sec                  
    65.           4.537274      task-clock (msec)         #    0.035 CPUs utilized          
    66.                  0      migrations                #    0.000 K/sec                  
    67.  
    68.        0.129464292 seconds time elapsed

    利用cpu乱序执行与内存、指令重排提高性能

    • cpu乱序执行 （无数据依赖遍历与有数据依赖遍历）: test_reorder 4 ; test_reorder 5
    • volatile原理: mfence
    • 原子操作原理： 
    • cpu指令重排带来的多线程问题:  test_reorder 1 ;  test_reorder 2
    • 内存重排带来的无锁编程问题
    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. #include 
    9. #include 
    10. #include 
    11. #include 
    12. #include 
    13. #include 
    14. #include 
    15. #include 
    16. #include 
    17. #include 
    18. #include 
    19.  
    20. #define barrier() __asm__ __volatile__("": : :"memory")
    21. #define mfence() __asm__ __volatile__("mfence": : :"memory")
    22. //https://en.cppreference.com/w/cpp/atomic/memory_order#Release-Consume_ordering
    23.  
    24. static sem_t sem[2];
    25. static int X, Y;
    26. static int r1, r2;
    27. static void t1_run(void)
    28. {
    29. 	sem_wait(&sem[0]);
    30. 	X=1;
    31. 	//mfence();
    32. 	r1=Y;
    33. }
    34. static void t2_run(void)
    35. {
    36. 	sem_wait(&sem[1]);
    37. 	Y=1;
    38. 	//mfence();
    39. 	r2=X;
    40. }
    41.  
    42. static void test_order_once()
    43. {
    44. 	static int num = 0;
    45. 	static int round = 0;
    46. 	round++;
    47. 	X = 0;
    48. 	Y = 0;
    49. 	std::thread t1(t1_run);
    50. 	std::thread t2(t2_run);
    51. 	sem_post(&sem[0]);
    52. 	sem_post(&sem[1]);
    53. 	t1.join();
    54. 	t2.join();
    55. 	if ((r1 == 0) && (r2 == 0)) {
    56. 		num++;
    57. 		printf("reorder: %d, iterator: %d\n", num, round);
    58. 	}
    59. }
    60.  
    61. /
    62. static std::atomic<int> aX;
    63. static std::atomic<int> aY;
    64. static int err_num = 0;
    65. static void load_aY_to_aX()
    66. {
    67. 	sem_wait(&sem[0]);
    68. 	r1 = aY.load(std::memory_order_relaxed);
    69. 	aX.store(r1, std::memory_order_relaxed);
    70. }
    71.  
    72. static void load_aX_then_store_aY()
    73. {
    74. 	sem_wait(&sem[1]);
    75. 	r2 = aX.load(std::memory_order_relaxed);
    76. 	aY.store(42, std::memory_order_relaxed);
    77. }
    78.  
    79. static void test_order_relaxed_once()
    80. {
    81. 	static int num = 0;
    82. 	static int round = 0;
    83. 	round++;
    84. 	aX = 0;
    85. 	aY = 0;
    86. 	std::thread t1(load_aY_to_aX);
    87. 	std::thread t2(load_aX_then_store_aY);
    88. 	sem_post(&sem[0]);
    89. 	sem_post(&sem[1]);
    90. 	t1.join();
    91. 	t2.join();
    92. 	if ((r1 == 42) && (r2 ==42)) {
    93. 		printf("reorder: %d, iterator: %d\n", ++num, round);
    94. 	}
    95. }
    96.  
    97. /
    98. static std::atomic ptr;
    99. static int data;
    100.  
    101. static void producer()
    102. {
    103.     std::string* p  = new std::string("Hello");
    104.     data = 42;
    105.     ptr.store(p, std::memory_order_release);
    106. }
    107.  
    108. static void consumer()
    109. {
    110.     std::string* p2;
    111.     while (!(p2 = ptr.load(std::memory_order_acquire)));
    112.     assert(*p2 == "Hello"); // never fires
    113.     assert(data == 42); // never fires
    114. }
    115.  
    116. static void relese_acquire_test()
    117. {
    118. 	
    119.     std::thread t1(producer);
    120.     std::thread t2(consumer);
    121.     t1.join(); 
    122. 	t2.join();
    123. }
    124.  
    125. static void test_auto_add()
    126. {
    127. 	const int size = 1000;
    128. 	float list[size], sum = 0; int i;
    129. 	auto start = std::chrono::high_resolution_clock::now();
    130.     for (int n = 0; n < 100000; n++)
    131. 		for (i = 0; i < size; i++) sum += list[i];
    132.     auto end = std::chrono::high_resolution_clock::now();
    133.     size_t use_time = std::chrono::duration_cast(end-start).count();
    134.     std::cout << "test_auto_add elapsed milliseconds: " << use_time << std::endl;
    135.     std::flush(std::cout);
    136. }
    137.  
    138. static void test_dependency_add()
    139. {
    140. 	const int size = 1000;
    141. 	float list[size], sum1 = 0, sum2 = 0; 
    142. 	int i;
    143. 	auto start = std::chrono::high_resolution_clock::now();
    144.     for (int n = 0; n < 100000; n++) {
    145. 		for (i = 0; i < size; i+=2) {
    146. 			sum1 += list[i];
    147. 			sum2 += list[i+1];
    148. 		}
    149. 		sum1 += sum2;
    150. 	}
    151.     auto end = std::chrono::high_resolution_clock::now();
    152.     size_t use_time = std::chrono::duration_cast(end-start).count();
    153.     std::cout << "test_auto_add elapsed milliseconds: " << use_time << std::endl;
    154.     std::flush(std::cout);
    155. }
    156.  
    157. int main(int argc, char **argv)
    158. {
    159.    sem_init(&sem[0], 0, 0);
    160.    sem_init(&sem[1], 0, 0);
    161. 	switch(argv[1][0]) {
    162. 		case '1' :  while(true) test_order_once(); break;
    163. 		case '2' :  while(true) test_order_relaxed_once();;break;
    164. 		case '3' :  while(true) relese_acquire_test();;break;
    165. 		case '4' :  test_auto_add();;break;
    166. 		case '5' :  test_dependency_add();;break;
    167. 	}
    168.  
    169.     return 0;
    170. }
    171.  
    1. ~/test_perf$ ./show_perf.sh ./test_reorder 4
    2. run ./test_reorder 4 
    3. test_auto_add elapsed milliseconds: 310
    4.  
    5.  Performance counter stats for './test_reorder 4':
    6.  
    7.             41,274      cache-references          #    0.132 M/sec                  
    8.             21,390      cache-misses              #   51.824 % of all cache refs    
    9.      1,004,169,232      instructions                                                
    10.        200,905,980      branches                  #  640.344 M/sec                  
    11.            118,085      branch-misses             #    0.06% of all branches        
    12.                113      faults                    #    0.360 K/sec                  
    13.                  0      context-switches          #    0.000 K/sec                  
    14.         313.746779      task-clock (msec)         #    0.995 CPUs utilized          
    15.                  0      migrations                #    0.000 K/sec                  
    16.  
    17.        0.315352555 seconds time elapsed
    18.  
    19. ~/test_perf$ ./show_perf.sh ./test_reorder 5
    20. run ./test_reorder 5 
    21. test_auto_add elapsed milliseconds: 159
    22.  
    23.  Performance counter stats for './test_reorder 5':
    24.  
    25.             38,816      cache-references          #    0.238 M/sec                  
    26.             18,949      cache-misses              #   48.817 % of all cache refs    
    27.        854,311,607      instructions                                                
    28.        100,877,665      branches                  #  617.780 M/sec                  
    29.            117,673      branch-misses             #    0.12% of all branches        
    30.                113      faults                    #    0.692 K/sec                  
    31.                  0      context-switches          #    0.000 K/sec                  
    32.         163.290585      task-clock (msec)         #    0.992 CPUs utilized          
    33.                  0      migrations                #    0.000 K/sec                  
    34.  
    35.        0.164629185 seconds time elapsed

    至于以上实验为什么会有这些测试结果。后续补上 ，先上班~~~~~~ 

  • 相关阅读:
    工作中使用Redis的10种场景
    团队建设游戏分享
    在Linux系统上实现区域更改
    mybatis开启缓存cache
    数据结构 —— 堆（超详细图解 & 接口函数实现）
    从零开始学YC-Framework之鉴权
    linux驱动32：延迟执行
    OpenFeign简介，负载策略
    HDRP Water & 云影
    快递保卫战：找出北极星指标、锁定优质供应商
  • 原文地址：https://blog.csdn.net/sdewenking/article/details/126655606