跳转至

Welcome

  • 需要 2 分钟阅读时间

数据库优化总结

这里总结了从数据库设计和sql结构两个方面的优化

数据库设计范式 Normal Form

范式是在数据库的设计时总结出来的一套规范，通常满足3范式就足够了。但由于3范式也存在问题，所以有了3.5范式

范式从1到3是越来越严格，所以满足1NF不一定满足2NF，但满足2NF就肯定满足1NF

满足所有范式的表没有冗余数据，但也有问题，比如效率不高。这就有了反范式做法，即允许数据冗余，用空间换时间

1NF：原子化，单元格里的值不能被分割

Employee Id Employee Name Phone Number Salary
1EDU001 Alex +91 85532065
+91 85532066		 60,131
1EDU002 Alex +91 85532066 75,331
1EDU003 Alex +91 85532068 63,231
1EDU004 Alex +91 85532069 70,231
1EDU005 Alex +91 85543065
+91 85543075		 60,531

可见，有条目的电话格里有两个号码，是可以分割的， 所以不满足1NF。应改为

Employee Id Employee Name Phone Number Salary
1EDU001 Alex +91 85532065 60,131
1EDU001 Alex +91 85532066 60,131
1EDU002 Alex +91 85532066 75,331
1EDU003 Alex +91 85532068 63,231
1EDU004 Alex +91 85532069 70,231
1EDU005 Alex +91 85543065 60,531
1EDU005 Alex +91 85543075 60,531

当所有单元格都无法分割了，就满足了第一范式

2NF：属性不允许部分依赖（复合）主键

满足2NF前提要满足1NF, 范式2要求非主属性必须依赖完整复合主键或者主键。

下表Employee Id和Department Id组成复合主键
|Employee Id|Department Id |Office Location | |---|---|---| |1EDUO01 | ED-T1 | Pune | |1EDUO02 | ED-S2 |Bengaluru | |1EDUO03 | ED-M1 | Delhi | |1EDUO04 | ED-T3 | Mumbai | |1EDUO05 | ED-T1 | Pune |

但Office Location只依赖主键的Employee Id部分。或者说只需Department Id就能保证Office Location唯一， 所以是部分依赖。这样不满足2NF了，应改成两个表

Employee Id Department Id
1EDUO01 ED-T1
1EDUO02 ED-S2
1EDUO03 ED-M1
1EDUO04 ED-T3
1EDUO05 ED-T1
Department Id Office Location
ED-T1 Pune
ED-S2 Bengaluru
ED-M1 Delhi
ED-T3 Mumbai

3NF： 依赖不能传递

满足3NF前提要满足2NF, 还有非主属性必须依赖主键/复合主键，不能依赖其他非主属性

Student Id Student name Subject Id Subject Adress
1DT1SENGO1 Alex 15CS11 SQL Goa
1DT1SENGO2 Barry 15CS13 JAVA Bengaluru
1DT15ENGO3 Clair 15CS12 C++ Delhi
1DT15ENG04 DavId 15CS13 JAVA Kochi

上表的Subject依赖非主属性Subject Id，而不是依赖Student Id， 这就不满足3NF了。应改成

Student Id Student name Subject Id
1DT1SENGO1 Alex 15CS11
1DT1SENGO2 Barry 15CS13
1DT15ENGO3 Clair 15CS12
1DT15ENG04 DavId 15CS13
Subject Id Subject Adress
15CS11 SQL Goa
15CS13 JAVA Bengaluru
15CS12 C++ Delhi
15CS13 JAVA Kochi
不满足3范式的问题

不满足3范式的数据库会存在以下问题: * 插入问题： 插入数据时，如果只有部分数据，可能导致插入失败（若某列为NOT NULL）。举例2NF里原来的表，若只有Department Id和Office Location，就无法插入 * 更新问题： 当更新某个字段时，需要更新其它列。举例2NF的表，当更新Pune时， 第1列和第4列都要更新 * 删除问题： 当删除某些属性时，其他属性也要删除， 举例3NF原来的表，当删除SQL课程时，学生Alex的信息也会丢失

3.5NF： BCNF

3.5范式用于解决3范式遗留问题
例如

Student Id Subject Professor
1DT15ENG01 SQL Prof. Mishra
1DT15ENG02 JAVA Prof. Anand
1DT15ENG02 C++ Prof. Kanthi
1DT15ENG03 JAVA Prof. Anand
1DT15ENG04 DBMS Prof. Lokesh

说明： * 一个学生可以登记多个科目 * 多个老师可以教授同一个科目 * 每个科目会有一个老师分配给一个学生

所以这个表满足3范式，因为Student Id和Subject组成了复合主键，决定了Professor。

但是不满足3.5NF，因为Student Id和Subject组成了复合主键，所以Subject是主属性， 而存在Professor依赖Subject， 虽然Subject是主属性，但Professor是非主属性，所以不满足BCNF。

此表应改成

Student Id Professor Id
1DT15ENG01 1DTPF01
1DT15ENG02 1DTPF02
1DT15ENG02 1DTPF03
Professor ID Professor Subject
1DTPF01 Prof. Mishra SQL
1DTPF02 Prof. Anand JAVA
1DTPF03 Prof. Kanthi C++

反范式

没有冗余数据的设计未必是好设计，有时为了效率，必须降低范式标准，适当允许保留冗余数据，以达到用空间换时间的目的。

例如订单表存在商品，单价，数量，总价， 这里总价是冗余的，因为可以通过单价和数量来求得，但总价经常需要，所以冗余可以提高效率。

HAVING 和查询语句优先级

SQL查询字句类似C语言的运算符优先级， 虽然标准里没有定义优先级，但大致为以下 

FROM > WHERE > SELECT > GROUP BY > HAVING > ORDER BY
这个顺序可以帮忙理解查询语句是如何执行的，比如因为SELECT优先级低于FROM, 所有只能在FROM中定义alais在SELECT中使用，而不能在SELECT中定义alias并在FROM中使用

HAVING指令通常和GROUP一起用，因为优先级比GROUP低，所以HAVING可以计算出GROUP的值并进行筛选。

SELECT Sno FROM Grade GROUP BY Sno HAVING COUNT(Cno) > 3;
这个语句筛选出相同Sno记录的个数>3的集合

VIEW和数据冗余

View是一种虚拟表，可以将多表的数据关联在一起，也可以做一些冗余数据，如计算平均值

CREATE VIEW Cl_avg_age AS SELECT Clno, AVG(Sage) AS avg_age FROM Student;

事物，存储过程和触发器

存储过程需要提前创建再使用。 因为存储过程中定义变量， 输入输出明确，所以让数据库操作更安全。 

CREATE PROCEDURE ap_returncount @Sno char(7) AS DECLARE @count int SELECT @count = Number FROM Class WHERE Clno = (SELECT Clno FROM Student WHERE Sno = @Sno) RETURN @count;

触发器是当触发条件时自动执行的命令，如当插入和更新满足条件时自动执行事物回撤。这是基于事物机制的。 事物可以保证多个操作的原子性， 当莫个操作不满足条件则全部ROLLBACK，回撤所有的操作，例如典型的转账场景，必须要扣除和增加都成功时才能成功。

但事物导致效率比较低。

CREATE TRIGGER tri_ins_upd_student ON Student AFTER INSERT, UPDATE AS IF 40 < (SELECT Number FROM Class WHERE Clno = (SELECT Clno FROM inserted )) ROLLBACK TRANSACTION;

参考

https://www.edureka.co/blog/normalization-in-sql/

  • 需要 2 分钟阅读时间

二进制小数精度

计算机使用2进制存储数据，而2进制可以表示所有的10进制整数，这样在整数范围内不存在问题，但导致小数的精度不够。

例如表示整数时，二进制不存在问题: |十进制|二进制| |--|--| |0| 0| |1|2^0| |2|2^1| |3|2^2 + 2^1|

而表示小数时，二进制只能有0.5, 0.25, 0.125...。 |二进制|十进制| |--|--| |2^-1| 0.5| |2^-2|0.25| |2^-3|0.125|

所以二进制表示10进制的小数颗粒比较大，若想表示0.6: 就要使用二进制小数 * 2^n来表示，有些数始终无法相等

浮点型和双精度

计算机显然没有无穷大的位置来存储”高阶的X“，只能折衷一下。故在c/c++中，有两种类型来表示小数，对应不同精度:
内存分布，两种类型的内存分布都为: 符号位(sign)+偏移位(exponent)+尾数位(mantissa)， 其值则为 (-1)^sign * mantissa * 2^exponent

float: 浮点类型

占用4字节（32位），精度为10^-6, 即第7位小数开始可能四舍五入或者直接忽略

内存分布： 第一位是符号位，后8位为偏移位，最后23位为尾数位，则有23+1位来表示小数，10^7 < 2^23+1 < 10^8，所以可以精确到第7位， 但最后以为可能会4四舍五入，精确到第6位

double: 双精度类型

占用8字节（64位），精度为10^-15, 即第16位小数开始可能四舍五入或者直接忽略

内存分布： 第一位是符号位，后11位为偏移位，最后52位为尾数位，则有52+1位来表示小数，10^16 < 2^52+1 < 10^17，所以可以精确到第16位， 但最后以为可能会4四舍五入，精确到第15位

计算问题

由于精度问题，精度之外的小数就会被忽略掉，导致出现下面的相等 

double i = 0.1;
double j = 0.2;
i+j == 0.3 + 4e-17;// 后面的数被忽略了
注意如果要使用float类型，需要显式使用'0.1f', 因为默认以double处理

如何比较两个浮点数

浮点数比较不可能100%正确，但下面都是错的 

float a = 0.15 + 0.15
float b = 0.1 + 0.2
if(a == b) // can be false!
if(a >= b) // can also be false!
if( Math.abs(a-b) < 0.00001) // wrong - don't do this
if( Math.abs((a-b)/b) < 0.00001 ) // still not right!

下面的才是大部分正确 

float absA = fabs(a);
float absB = fabs(b);
float diff = fabs(a - b);
if (a == b) { // shortcut, handles infinities
    return true;
} else if (a == 0 || b == 0 || (absA + absB < 1e-16)) {
            // a or b is zero or both are extremely close to it
            // relative error is less meaningful here
    return diff < (epsilon * Float.MIN_NORMAL);
} else { // use relative error
    return diff / Math.min((absA + absB), Float.MAX_VALUE) < epsilon;
}

但如果知道精度，直接将其乘以10^n变成整数来比较是最佳的方法

  • 需要 1 分钟阅读时间

CPP原子操作

无锁队列

atomic

      void
      store(__pointer_type __p,
        memory_order __m = memory_order_seq_cst) noexcept
      { return _M_b.store(__p, __m); }

      void
      store(__pointer_type __p,
        memory_order __m = memory_order_seq_cst) volatile noexcept
      { return _M_b.store(__p, __m); }

      __pointer_type
      load(memory_order __m = memory_order_seq_cst) const noexcept
      { return _M_b.load(__m); }

      __pointer_type
      load(memory_order __m = memory_order_seq_cst) const volatile noexcept
      { return _M_b.load(__m); }

      __pointer_type
      exchange(__pointer_type __p,
           memory_order __m = memory_order_seq_cst) noexcept
      { return _M_b.exchange(__p, __m); }

cpp实现

atomic::compare_exchange_weak

memory_order

  • memory_order_relaxed
  • memory_order_seq_cst
  • 需要 1 分钟阅读时间

cmake预处理头文件

预处理头文件是cmake 3.16添加的新功能，可以将头文件先

Precompiling header files can speed up compilation by creating a partially processed version of some header files, and then using that version during compilations rather than repeatedly parsing the original headers.
  • 需要 2 分钟阅读时间

前言

记一次单元测试用例时失败，且出现奇怪的报错 

tpp.c:63: __pthread_tpp_change_priority: Assertion `new_prio == -1 ||(new_prio >= __sched_fifo_min_prio && new_prio <=__sched_fifo_max_prio)' failed

原因

函数定义如下，原因是下面的第一个assert条件不成立，new_prio != -1。这个函数的注释说明了需要使用者确保调用前已初始化。

/* We only want to initialize __sched_fifo_min_prio and __sched_fifo_max_prio
   once.  The standard solution would be similar to pthread_once, but then
   readers would need to use an acquire fence.  In this specific case,
   initialization is comprised of just idempotent writes to two variables
   that have an initial value of -1.  Therefore, we can treat each variable as
   a separate, at-least-once initialized value.  This enables using just
   relaxed MO loads and stores, but requires that consumers check for
   initialization of each value that is to be used; see
   __pthread_tpp_change_priority for an example.
 */

int
__pthread_tpp_change_priority (int previous_prio, int new_prio)
{
  struct pthread *self = THREAD_SELF;
  struct priority_protection_data *tpp = THREAD_GETMEM (self, tpp);
  int fifo_min_prio = atomic_load_relaxed (&__sched_fifo_min_prio);
  int fifo_max_prio = atomic_load_relaxed (&__sched_fifo_max_prio);
  if (tpp == NULL)
    {
      /* See __init_sched_fifo_prio.  We need both the min and max prio,
         so need to check both, and run initialization if either one is
         not initialized.  The memory model's write-read coherence rule
         makes this work.  */
      if (fifo_min_prio == -1 || fifo_max_prio == -1)
        {
          __init_sched_fifo_prio ();
          fifo_min_prio = atomic_load_relaxed (&__sched_fifo_min_prio);
          fifo_max_prio = atomic_load_relaxed (&__sched_fifo_max_prio);
        }
      size_t size = sizeof *tpp;
      size += (fifo_max_prio - fifo_min_prio + 1)
              * sizeof (tpp->priomap[0]);
      tpp = calloc (size, 1);
      if (tpp == NULL)
        return ENOMEM;
      tpp->priomax = fifo_min_prio - 1;
      THREAD_SETMEM (self, tpp, tpp);
    }
  assert (new_prio == -1
          || (new_prio >= fifo_min_prio
              && new_prio <= fifo_max_prio));
  assert (previous_prio == -1
          || (previous_prio >= fifo_min_prio
              && previous_prio <= fifo_max_prio));

网上帖子的原因是给初始化mutex并设置RECURSIVE类型时，忘了对mutexattr进行初始化，导致使用了脏内存 即pthread_mutexattr_init(&mutexattr)

pthread_mutexattr_t mutexattr;

// Set the mutex as a recursive mutex
pthread_mutexattr_settype(&mutexattr, PTHREAD_MUTEX_RECURSIVE_NP);

// create the mutex with the attributes set
pthread_mutex_init(&CritSec, &mutexattr);

// After initializing the mutex, the thread attribute can be destroyed
pthread_mutexattr_destroy(&mutexattr);

总之，要在线程启动前初始化好mutex

其他问题

这个问题其实是c++代码抛出来的，多线程执行了下面的代码，导致了上面的问题。

AppCache中有个小粒度的锁，但这个锁还未初始化就被其他线程去lock了，导致出现问题。所以要mutex最好要在线程启动前初始化

AppCache{
std::mutex
}；

  auto app = m_app_cache.find(app_path);
  if (app == m_app_cache.end()) {
    // create a new monitor element
    m_app_cache.insert_or_assign(app_path, std::make_shared<AppCache>());
  }
  std::lock_guard<std::mutex> lk(app->second->cache_mutex);

引用

https://sourceware.org/legacy-ml/libc-help/2008-05/msg00072.html?utm_source=pocket_mylist

  • 需要 2 分钟阅读时间

堆排序

堆排类似选择排序，只排序未排序的部分，但堆排比较方式不同，每次只比较log(n)次
最终的堆排时间复杂度为O(nlogn)

关键下标

堆一般用数组来表示，但是关系为

  • 当以1为起点时，若父节点是n
  • 左子节点=n*2

  • 右子节点=n*2 + 1

  • 若节点为n, 则其父节点为n/2

  • 若元素为m个，则最后一个根节点（非叶节点）为m/2

  • 当以0为起点时，若父节点是n

  • 左子节点=(n+1)2-1 = n2 + 1

  • 右子节点=(n+1)2+1 -1 = n2 + 2

  • 若节点下标为n, 其父节点为(n+1)/2 - 1 = (n-1)/2

  • 若元素为m个，则最后一个根节点（非叶节点）为(m+1)/2-1 = (m-1)/2

可见，若以1为起点，要简洁很多

建立堆

  1. 从第一个非叶子节点开始，比较父子节点中找的最值，如果需要调整则交换父子节点再递归遍历下一层：
  2. 建立最小堆时，每次比较出最大值，一遍之后，堆顶为最大
  3. 建立最大堆时，每次比较出最小值，一遍之后，堆顶为最小
  4. 比较到顶部节点时，完成第一次遍历，找到了顶部的最值
  5. 将堆顶的最值与尾部交换，遍历范围-1，然后从堆顶开始比较
  6. 重复3动作，直到范围为1

3的动作类似选择排序，只遍历未排序的部分

最大堆和最小堆

最小堆可以求得topK大的数，反过来最大堆可以求得topK小的数

topK

堆排序通常用来实现topK，适用于限制内存的情况。方法是建立一个堆大小为K： 先用头部K个数据建立最小堆，后续的数字与堆顶（最小）比，如果跟小则跳过，否则替换然后执行thiftdown。其时间复杂读为O)KlogK + NlogK), 只需要一次建堆，后续都是比较。空间复杂度为K。

也可以则使用分治法，将数据分为多组，每组求其top k。最后合并起来再排序，求最终的topK。 分治法可以配合线程一起使用加快速度。

// 使用最小堆来实现topK
void thiftdown(int *heap, int root, int size) {
  int m = root;
  int l = root * 2 + 1;
  int r = root * 2 + 2;

  if (l < size && heap[l] > heap[m]) {
    m = l;
  }
  if (r < size && heap[r] > heap[m]) {
    m = r;
  }

  if (m != root) {
    int tmp = heap[root];
    heap[root] = heap[m];
    heap[m] = tmp;

    thiftdown(heap, m, size);
  }
}

void adjust(int *heap, int root, int size) {
  int m = root;
  int l = root * 2 + 1;
  int r = root * 2 + 2;

  if (l < size && heap[l] < heap[m]) {
    m = l;
  }
  if (r < size && heap[r] < heap[m]) {
    m = r;
  }

  if (m != root) {
    int tmp = heap[root];
    heap[root] = heap[m];
    heap[m] = tmp;

    adjust(heap, m, size);
  }
}

void heapify(int *heap, int size) {
  for (int i = (size - 1) / 2; i >= 0; i--) {
    thiftdown(heap, i, size);
  }

  while (size > 0) {
    int tmp = heap[0];
    heap[0] = heap[size - 1];
    heap[size - 1] = tmp;
    size--;
    thiftdown(heap, 0, size);
  }
}

void add(int *heap, int val, int size) {
  if (heap[0] >= val) {
    return;
  }
  heap[0] = val;
  adjust(heap, 0, size);
}

使用方法 

heapify(m, 5);
for (int i = 5; i < 49; i++) {
  add(m, n[i], 5);
}
return m[0];

海量数据求topK

常见问题类似： 1. 求许多重复整数中，重复第K多的正整数。 2. 求文本中重复出现的词语次数，重复第K多的”， 3. ip中访问最K多的”。

这些问题需要多一步统计，统计出现次数，然后再使用堆来查找topK。

  1. 使用数组统计，如果目标都是正整数，如问题1
  2. 使用map统计，int表示出现次数，如果目标字符串，如问题2和问题3

统计完成后，将目标和计数放入结构体，再使用堆来找topK 

{
  目标
  次数
}

总结

topK 问题除了堆排序以外，还常用快排来找。

  • 需要 1 分钟阅读时间

DP 四板斧

以跳台阶的题目为例， 题目是以每次跳1层或2层的方式跳到n台阶， 问一共有多少种跳法
开始我觉得这是求路径个数，而通常dp算最大或最小值， 不适用。
但后来换个角度想，求最大最小必须得试过所有方法才得出来的， 而将所有的试过的方法计数，就是这题的解

写出递归

dp第一步要先写出递归来， 写递归得写收敛条件
这里的收敛条件是当传参小于0,则说明解法失败（多跳了），返回0。 当恰好为0则解法有效返回1

递归体就是跳1层和跳2层

static int jump(int number) {
  if (number < 0) {
    return 0;
  } else if (number == 0) {
    return 1;
  }
  return jump(number - 1) + jump(number - 2);
}

int jumpFloor(int number) { 
  return jump(number - 1) + jump(number - 2); 
}

用缓存来优化递归

递归显然会重复计算， 可以用缓存计算结果来避免， 当有缓存时使用缓存，否则才去计算， 最后将结果缓存

并且使用缓存时应该指定尾递归的值

int jump(int number, int *cache) {
  if (number < 3) {
    return cache[number];
  }
  // 缓存没命中就计算
  int ret1 =
      cache[number - 1] != -1 ? cache[number - 1] : jump(number - 1, cache);
  int ret2 =
      cache[number - 2] != -1 ? cache[number - 2] : jump(number - 2, cache);
  cache[number] = ret1 + ret2;
  return cache[number];
}

int jumpFloor(int number) {
  int cache[number + 1];
  for (int i = 0; i < number + 1; i++) {
    cache[i] = -1;
  }

  cache[0] = 0;
  cache[1] = 1;
  cache[2] = 2;
  return jump(number, cache);
}

递归改for循环

递归的调用流程是自上而下，先计算(n)->计算(n -1)->再计算(n-2) ... 0
现在要反过来， 先计算(0)->计算(1)->计算(2) ... n 即自下而上

int jumpFloor(int number) {
  if (number < 3) {
    return number;
  }

  // 之前要初始化为了判断， 而现在显然下标大于2的值是要计算出来的，不需要读取  
  // 所以不需要初始化
  int cache[number + 1];
  cache[1] = 1;
  cache[2] = 2;

  for (int i = 3; i <= number; i++) {
    cache[i] = cache[i - 1] + cache[i - 2];
  }

  return cache[number];
}

缩小缓存大小

仔细看， 其实每次计算只涉及最大的三个数， 所以数组并不需要那么大，只用3个单元就足够，故直接写成3个变量

  int jumpFloorD(int number) {
    if (number < 3) {
      return number;
    }

    int total = 0;
    int minors2 = 1;
    int minors1 = 2;

    for (int i = 3; i <= number; i++) {
      total = minors1 + minors2;
      minors2 = minors1;
      minors1 = total;
    }

    return total;
  }

这样DP解法就出来了， 这个套路是我从力扣上学到的， 非常有效简单

总结

从上可见，你需要训练如何发现递归关系，剩下的工作就是缓存递归调用的结果，最后是将从上到下的解决思路变为从下到上。这样我们就可以用O(N)的时间复杂度去遍历

参考

https://leetcode.com/discuss/study-guide/1490172/dynamic-programming-is-simple

  • 需要 1 分钟阅读时间

引题

在stackoverflow上搜到一个有趣帖子
讨论了指针解引用和数组下标访问的区别，而根本原因就是指针有时不同于数组，这是《c专家编程》有仔细讨论的，故再看了一遍

问题

帖子的问题可以用类型不同和指针在extern声明时不同于数组来直接了当地解释。而类型不匹配如何导致程序崩溃的呢

//file file1.c

int a[2] = {800, 801};
int b[2] = {100, 101};

//file file2.c

extern int a[2];

// here b is declared as pointer,
// although the external unit defines it as an array
extern int *b; 

int main() {

  int x1, x2;

  x1 = a[1]; // ok
  x2 = b[1]; // crash at runtime, segment fault

  return 0;
}

当声明为extern 数组时，编译后符号表保存了数组的地址，那么a[1]解引用只是在数组地址上加偏移量a+1得到新地址，然后取新地址的内容，所以数组的地址提前可知
当声明为extern 指针时，编译后符号表保存的是符号b，让编译器以指针的方式处理b，所以b是一个指针，其指针地址被赋值为数组的内容（101100）。在运行时，先取出b的地址为（101100），
再加上偏移量得到新地址(101101), 最后访问这个非法地址导致崩溃

因为当声明为extern int *b时，在file1中的b应该是存放一个内存地址而实际存放的是数组内容，就导致程序把数组的内容当地址访问。

打印指针地址

如果在coredump之前，先打印b的地址，得到的是b数组的值为'0x6500000064', 正好指针长度是两个int之和。所以file2中把数组内容当成了指针地址，然后偏移一个int长度后，地址是'0x6500000068', 然后这个无效地址导致段错误。 

printf("%p\n", (void*)b);

从汇编角度看这个问题

b存放的是内容，而程序以为是地址。因为实际上编译器不会为数组额外分配空间来存储指针, 但是要为指针分配空间。 

int main() {
    int *a = 0;
    int b[4];
    *b = 0;
    // 为了显示栈大小
    foo();
}
从汇编代码可见，分配了32个字节的空间，指针8 + 4*4 = 
        sub     rsp, 32
        mov     QWORD PTR -8[rbp], 0
        mov     DWORD PTR -32[rbp], 0

弱符号

  • 需要 2 分钟阅读时间

浅谈内存管理

这里记录一下看书所得，应用程序的内存管理，即glibc的malloc和相关函数

内存管理的重要性

过去Linux通过默认的dlmalloc来申请内存，但不支持多线程，这导致的竞争和性能降低，而ptmalloc2支持多线程，也成为了Linux新的默认方式
ptmalloc2通过为每个线程单独维护一个帧，这样每个线程的申请和释放可以并行执行，但当线程过多时，线程也将共享帧。这种帧叫做per thread arena

主线程和线程的内存申请方式

主线程中使用brk来申请大块内存，其实brk不过是修改了寄存器的值。而且返回的大小通常要比malloc申请的多，如同测试中的在主线程中申请100个字节大小的内存，返回了132 KB。 

55f7b402c000-55f7b404d000 rw-p 00000000 00:00 0                          [heap]
而在线程中，malloc使用mmap来申请内存，返回大小也比申请大小多，测试中的在线程中申请100字节，返回了64M的地址空间， 但只有8MB是可用的堆内存。 
7fb738000000-7fb738021000 rw-p 00000000 00:00 0      
7fb738021000-7fb73c000000 ---p 00000000 00:00 0

主线程中申请的地址大于Data Section的地址，说明使用的brk，而后者申请时用了mmap，对比附录文档可以看出32位和64位区别比较大

arena

主线程和线程使用不同的arena，这样主线程和线程同时申请内存时不存在竞争。但不是所有的线程都独享一份arena, arena的个数限制如下

For 32 bit systems:
     Number of arena = 2 * number of cores.
For 64 bit systems:
     Number of arena = 8 * number of cores.

当线程个数太多时，会公用主线程的arena

main arena 和 per thread arena

main arena 指在主线程（main）中使用的，而后者是子线程中使用，两者有很大区别
主线程只有一块heap，所以没有heapinfo结构，而子线程有。主线程的Arena header是全局变量，所以存在于libc.so的Data Segment中

线程的arena含有多个heap, 每个heap都有heapinfo结构，多个heapinfo组成链表。线程的多个heap共享一个malloc_state 也称为Arena header

Arena header包含了bin、top chunk等信息

每个heap有多个chunk，每个chunk有个malloc_chunk结构，其管理chunk的状态和其在heap中的偏移大小，有以下几种状态

  • Allocated chunk
  • Free chunk
  • Top chunk
  • Last Remainder chunk

Top chunk 处于arena的顶部，在freelist没有合适大小的chunk时使用，如果Top chunk比申请的大，则又分为两部分（新Top chunk和用户申请的chunk）

Last Remainder chunk, 是当用户请求small chunk时，会先遍历small bin和Unsorted bin， 如果都无法满足，则遍历其他bin。
如果找到的chunk还有剩余，则这个chunk变为Last Remainder chunk，且将被加入到Unsorted bin
这样的好处是多次申请small chunk时，会先向Unsorted bin的Last Remainder chunk申请， 所以小内存块会集中分布在Last Remainder chunk，提高小块内存的局部性

bin

当malloc的内存被free后（仅仅是例子中的100字节chunk），并不会释放给内核，而是进入到glibc的bin中，也叫做freelist。
当下次申请内存时，会从bin中查找合适的chunk，而只有当没有合适的大小时，才向内核申请。

所以bin用来保存free过的chunk, 基于chunk的大小分为 - Fast bin - Unsorted bin - Small bin - Large bin

但不同的bin都使用链表来管理这些chunk

测试方法

获取程序运行时的pid, 假设为949293, 那么通过以下命令可以获取程序的内存结构 

cat /proc/949632/maps
# address                 perms offset  dev    inode             pathname
55f7b378a000-55f7b378b000 r--p 00000000 103:02 4727634                   /tmp/a.out (deleted)
55f7b378b000-55f7b378c000 r-xp 00001000 103:02 4727634                   /tmp/a.out (deleted)
55f7b378c000-55f7b378d000 r--p 00002000 103:02 4727634                   /tmp/a.out (deleted)
55f7b378d000-55f7b378e000 r--p 00002000 103:02 4727634                   /tmp/a.out (deleted)
55f7b378e000-55f7b378f000 rw-p 00003000 103:02 4727634                   /tmp/a.out (deleted)
55f7b402c000-55f7b404d000 rw-p 00000000 00:00 0                          [heap]
7f4808000000-7f4808021000 rw-p 00000000 00:00 0 
7f4808021000-7f480c000000 ---p 00000000 00:00 0 
7f480ea3d000-7f480ea3e000 ---p 00000000 00:00 0 
7f480ea3e000-7f480f241000 rw-p 00000000 00:00 0 
...
* address 是起始地址-结束地址，差值为空间大小 * perm 是指权限，分为rwx[p,s], [p,s]指最后一位可以是private或者shared, 这些能通过mprotect命令修改(c中的const实现) * offset 仅对mmap的区域有效，指映射偏移量 * pathname 如果此区域是映射的文件，则显示文件名。如果映射的是匿名映射则显示空白, 匿名映射包括线程通过mmap申请的堆内存，而[heap]是main函数的堆

所以通过计算address可以知道glibc申请的内存情况

malloc的返回值有意义吗

在我本机（gcc (Debian 10.2.1-6) 10.2.1 20210110 12GB）上测试了一段程序 1. 如果一次性申请13GB，malloc返回失败 2. 如果每次只申请2GB但不释放，第10次申请（20GB）malloc返回成功 3. 如果每次只申请2GB但不释放且访问，第三次申请（6GB）malloc返回成功，但访问时OOM

所以说，malloc的返回值是没有太大意义的

void foo(size_t large) {
  char *buffer = (char *)malloc(large);
  if (buffer == NULL) {
    printf("error!\n");
    exit(EXIT_FAILURE);
  }
  printf("Memory allocated\n");
  //  for (size_t i = 0; i < large; i += 4096) {
  //    buffer[i] = 0;
  //  }
  printf("Travalse done\n");
}
int main() {
  // size_t large = 1099511627776;
  size_t large = 13958643712;
  for (int i = 0; i < 100; i++) {
    foo(2147483648);
  }

  return EXIT_SUCCESS;
}

其他

内存管理不仅存在应用程序（或者说glibc）中，Linux内核也有内存管理。也不只有glibc的内存malloc一种实现，还有

  • dlmalloc – General purpose allocator
  • ptmalloc2 – glibc
  • jemalloc – FreeBSD 的libc实现, 相比其他第三方，这个比较流行
  • tcmalloc – Google 为多线程场景开发
  • libumem – Solaris

malloc是glibc对ptmalloc2的包装，而ptmalloc2是dlmalloc的重构，区别很大

最后总结，glibc的malloc通过两个系统调用函数brk和mmap来向内核申请内存，但内存释放后不会归还内核，而是放到freelist等待再次被利用

引用

https://man7.org/linux/man-pages/man5/proc.5.html https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/comment-page-1/ https://lemire.me/blog/2021/10/27/in-c-how-do-you-know-if-the-dynamic-allocation-succeeded/

  • 需要 1 分钟阅读时间

spdlog

spdlog 支持多spdlog::logger, 适用与多个隔离模块的日志分别保存

而且logger含有多个sink的vector。sink与文件对应，如果想把日志输出到多个文件，就创建多个sink

std::vector<sink_ptr> sinks_;

logger和sink的级别独立 

// logger级别的判断
template<typename... Args>
inline void spdlog::logger::log(source_loc source, level::level_enum lvl, const char *fmt, const Args &... args)
{
    if (!should_log(lvl))
    {
        return;
    }


// sink级别的判断
inline void spdlog::logger::sink_it_(details::log_msg &msg)
{
#if defined(SPDLOG_ENABLE_MESSAGE_COUNTER)
    incr_msg_counter_(msg);
#endif
    for (auto &sink : sinks_)
    {
        if (sink->should_log(msg.level))
        {
            sink->log(msg);
        }
    }

所以可以支持不同的级别到不同的文件，例如logger设置为trace级别， sink1 设置为info级别， sink2设置为trace级别，这样就能创建两个日志文件 

info.log  # 只保存info级别
full.log  # 保存所有级别（logger级别或者sink2的级别）