推理性能优化

发表于 2022-11-23 更新于 2026-03-23 分类于 AI
本文字数： 726 阅读时长 ≈ 3 分钟

推理性能优化

推理优化工作可以归成四类

算子优化
图优化
模型压缩
部署优化

算子优化

算子优化就是优化单算子的性能，方法无非是算法优化和微架构优化。

对同一个算子可能有不同的算法去实现它。举个例子，对卷积算法我们常见的就有：矩阵乘法，直接卷积法，Winograd 变换法，FFT 变换法。需要我们针对目标问题，分析并实现合适的算法，来达到最佳性能。
微架构优化。微架构优化主要焦点是如何充分利用好微架构的内置加速器的能力去最大化算子的性能。

图优化

图优化主要通过子图变换和算子融合的方式来达到减少计算量或者其他系统开销（如访存开销），从而达到性能优化的目的。图优化主要是希望在不影响模型的数值特性的基础上，通过图变换达到简化计算、资源开销，提升性能，所以是性能优化时的首选方法之一。

子图变换

子图变换主要是通过数学变换的手段对图进行精简，从而减少计算和调度开销。常见的有常数折叠，公共子表达式折叠以及算术变换。

常数折叠 (Constant Folding)

算数变换

算子融合

在深度学习中，一般来说，计算密集型和访存密集型算子是相伴出现的。这时候我们可以通过 fusion 来实现寄存器计算，从而减少访存密集型算子的访存，减少内存访问延时和带宽压力，提高推理效率。

通过这种方式，减少两次 tensor 的内存读写操作。

模型压缩

上面的方案都是精度无损的，当这三点都做完了后，如果还需要额外的性能增益，这时候需要考虑模型压缩方案。

模型量化

模型量化主要是通过降低模型中 tensor 和 weights 精度的手段，从而减少计算需求和数据存储与传输需求，来达到加速的目的。例如把权重从 FP32 降低为 FP16。虽然可以加速，但是有一定的精度损失。

模型蒸馏

模型蒸馏采用的是迁移学习的方法，通过采用预先训练好的复杂模型（Teacher Model）的输出作为监督数据，去训练另外一个简单的网络（Student Model），最后把 Student Model 用于推理。有精度损失。

部署优化

部署优化主要通过调整模型在部署时的资源分配和调度的参数来进一步优化性能。如，调整了 NUMA 的参数。

cpp不同种类构造函数

发表于 2022-11-18 更新于 2026-03-23 分类于 cpp
本文字数： 646 阅读时长 ≈ 2 分钟

cpp 的构造函数种类

构造函数：生成一个新的对象。
拷贝构造函数：参数是 const T& x，用于拷贝。
赋值构造函数：这个严格意义来说不是构造函数，是赋值运算符 = 的重载。初始化的时候不会调用这个函数！
移动构造函数：参数是 T &&x，用于移动构造，提升效率。

代码示例

#include <iostream>
#include <string>

using namespace std;

class Integer {
private:
    int* m_ptr;
public:
    //  普通构造函数
    Integer(int value) : m_ptr(new int(value)) {
        cout << "constructor" << endl;
    }
    //  拷贝构造函数
    Integer(const Integer& source) : m_ptr(new int(*source.m_ptr)) {
        cout << "copy constructor" << endl;
    }
    //  移动构造函数
    Integer(Integer&& source) : m_ptr(source.m_ptr) {
        source.m_ptr = nullptr;
        cout << "move constructor" << endl;
    }
    //  赋值运算符重载
    Integer& operator=(const Integer& source) {
        m_ptr = new int(*source.m_ptr);
        cout << "copy assignment constructor" << endl;
        return *this;
    }
    ~Integer() {
        cout << "destructor:" << GetValue() << endl;
        delete m_ptr;
    }
    int GetValue(void) {
        if (m_ptr) {
            return *m_ptr;
        } else {
            return -1;
        }
    }
};

Integer getNum() {
    Integer a(100);
    return a;
}
int main(int argc, char const* argv[]) {
    Integer a(getNum()); 
    cout << "a=" << a.GetValue() << endl;
    cout << "-----------------" << endl;
    Integer temp(10000);
    Integer b(temp);
    cout << "b=" << b.GetValue() << endl;
    cout << "-----------------" << endl;
    Integer c = b;
    c = a;
    cout << "c=" << c.GetValue() << endl;
    cout << "-----------------" << endl;
    return 0;
}

在编译的时候一定要指定编译选项 --no-elide-constructors，否则会被编译器优化！

@└────> # ./a.out 
constructor
move constructor
destructor:-1
move constructor
destructor:-1
a=100
-----------------
constructor
copy constructor
b=10000
-----------------
copy constructor
copy assignment constructor
c=100
-----------------
destructor:100
destructor:10000
destructor:10000
destructor:100

分析

a

第一个 constructor，是在 getNum() 中首句 Integer a(100) 所打印的，调用默认的构造函数。
第二个 move constructor 是因为 return a 的时候，这个 a 是个右值，作为 main 函数 getNum() 的返回值，而调用的移动构造函数，将 getNum() 函数内的返回值移动构造给 main 函数接收 getNum() 的对象。
第三个 destructor 是析构 getNum() 中的对象 a。
第四个 move constructor 是因为 Integer a(右值)，所以调用移动构造函数。
第五个 destructor 是析构 Integer a(右值) 中的右值而显示的。

b

第一个 constructor 是 Integer temp(10000); 调用的默认构造函数。
第二个 copy constructor 是 Integer b(temp); 调用的拷贝构造函数，将 temp 拷贝给 b；

c

第一个 copy constructor 是 Integer c = b; 调用的拷贝构造函数，可以看到此处并没有调用拷贝赋值运算符，因为这是在初始化！
第二个 copy assignment constructor 是 c = a 调用的才是拷贝赋值运算符。

可以看到，初始化的时候不会调用拷贝赋值运算符！！！

析构

最后的四个 destructor 是析构。根据规则，先构造的后析构，后调用的先析构。析构顺序：c = 100，b = 10000，temp = 10000，a = 100。

cpp左值和右值

发表于 2022-11-17 更新于 2026-03-23 分类于 cpp
本文字数： 1.4k 阅读时长 ≈ 5 分钟

何为右值

任何值不是左值，就是右值。左值和右值是针对表达式定义的。

右值的生存周期只到表达式结束，即语句分号后右值的生存周期就结束了。
左值可以取地址，右值不行。
左值可以放在 = 的左右，但是右值只能放在右边。

为什么要引入这么复杂的概念呢？为了性能。在赋值的时候，难免会产生一些临时变量的构造和销毁，这些构造和销毁可能会引起内存的申请与释放。频繁的系统调用会有很大的性能开销。这种时候没必要重复申请内存，只要把那个将要销毁对象内部的指针指向的空间被新的对象所利用就可以了！

int t = 10;  // t为左值
++t;         // t为左值，没有拷贝，这就是为什么 ++t 比 t++ 高效
t++;         // t为右值，因为加之前的值是个将亡值，是个 t_copy，是个临时变量
int &&r = t; // 错误，右值不能绑定左值。

std::move()

实现代码

/**
 *  @brief  Convert a value to an rvalue.
 *  @param  __t  A thing of arbitrary type.
 *  @return The parameter cast to an rvalue-reference to allow moving it.
*/
template<typename _Tp>
  constexpr typename std::remove_reference<_Tp>::type&&
  move(_Tp&& __t) noexcept
  { return static_cast<typename std::remove_reference<_Tp>::type&&>(__t); }

这个函数就一个作用：将左值明确的转换为右值。由于引用折叠的存在，导致返回值一定是右值。引用折叠概念见下一小节。

示例

#include <iostream>
using namespace std;
void func(string &&str) {
    cout << "右值函数" << endl;
}
void func(string &str) {
    cout << "左值函数" << endl;
}

int main() {
    string s;
    func(s + s);
    func(s);
    func(std::move(s));
}

结果：

@└────> # ./a.out 
右值函数
左值函数
右值函数

可以看到，s + s 是一个右值，编译器会自动匹配调用右值对应的函数。s 是一个左值，会调用左值对应的函数。使用 std::move() 强行把左值转换为右值，就匹配右值对应的函数。此处注意，因为 s 已经变为右值了，所以在调用之后，s 会失效。

std::forward()

在介绍 std::forward() 之前，先介绍下引用折叠。

引用折叠

引用折叠是指，在左值类型和右值类型叠加时，确认叠加规则。如下代码：

#include <iostream>
using namespace std;

template<typename T>
void WithoutPerfectForward(T &&t) {
    cout << "lvalue:" << std::is_lvalue_reference<decltype(t)>::value << endl;
    cout << "rvalue:" << std::is_rvalue_reference<decltype(t)>::value << endl;
    cout << endl;
}

int main() {
    int a = 1;
    int b = 2;
    const int c = 1;
    const int d = 0;
    int &e = a;
    int &f = b;
    const int &g = c;
    const int &h = d;
    WithoutPerfectForward(a);        // l + r = l
    WithoutPerfectForward(move(b));  // r + r = r
    WithoutPerfectForward(c);        // const l + r = l
    WithoutPerfectForward(move(d));  // const r + r = r
    WithoutPerfectForward(e);        // l ref + r = l
    WithoutPerfectForward(move(f));  // r ref + r = r
    WithoutPerfectForward(g);        // const l ref + r = l
    WithoutPerfectForward(move(h));  // const r ref + r = r
}

@└────> # ./a.out 
lvalue:1
rvalue:0

lvalue:0
rvalue:1

lvalue:1
rvalue:0

lvalue:0
rvalue:1

lvalue:1
rvalue:0

lvalue:0
rvalue:1

lvalue:1
rvalue:0

lvalue:0
rvalue:1

可以看到，因为 T 的不同会产生不同的模版函数特化版本，如参数会变为 T& && 和 T&& && 这两种形式，c++11 支持的编译器会对这种情况用 4 条规则做折叠处理，生成只有 & 和 && 的引用方式：

& + & = &
& + && = &
&& + & = &
&& + && = &&

即引用折叠时只要有左值引用，就折叠为左值引用，全部是右值引用，才折叠为右值引用。

那么考虑如下场景：

#include <iostream>
using namespace std;

void RunCode(int && m) {
    cout << "int && called!" << endl;
}
void RunCode(int &m) {
    cout << "int & called!" << endl;
}
void RunCode(const int && m) {
    cout << "const int && called!" << endl;
}
void RunCode(const int & m) {
    cout << "const int & called!" << endl;
}

template<typename T>
void WithoutPerfectForward(T &&t) {
    RunCode(t);
}

int main() {
    int a = 1;
    int b = 2;
    const int c = 1;
    const int d = 0;
    int &e = a;
    int &f = b;
    const int &g = c;
    const int &h = d;
    WithoutPerfectForward(a);        // l + r
    WithoutPerfectForward(move(b));  // r + r
    WithoutPerfectForward(c);        // const l + r
    WithoutPerfectForward(move(d));  // const r + r
    WithoutPerfectForward(e);        // l ref + r
    WithoutPerfectForward(move(f));  // r ref + r
    WithoutPerfectForward(g);        // const l ref + r
    WithoutPerfectForward(move(h));  // const r ref + r
}

结果：

@└────> # ./a.out 
int & called!
int & called!
const int & called!
const int & called!
int & called!
int & called!
const int & called!
const int & called!

可以看到虽然在函数 WithoutPerfectForward 中是右值，但是传给下一个函数的时候又默认都是左值了。虽然参数 t 是右值类型的，但此时 t 在内存中已经有了位置，所以 t 其实是个左值。

完美转发

为了实现不丢失传进来值的左右性，使用 std::forward() 就可以实现完美的转发了！

#include <iostream>
using namespace std;

void RunCode(int && m) {
    cout << "int && called!" << endl;
}
void RunCode(int &m) {
    cout << "int & called!" << endl;
}
void RunCode(const int && m) {
    cout << "const int && called!" << endl;
}
void RunCode(const int & m) {
    cout << "const int & called!" << endl;
}

template<typename T>
void WithoutPerfectForward(T &&t) {
    RunCode(std::forward<T>(t));
}

int main() {
    int a = 1;
    int b = 2;
    const int c = 1;
    const int d = 0;
    int &e = a;
    int &f = b;
    const int &g = c;
    const int &h = d;
    WithoutPerfectForward(a);        // l + r
    WithoutPerfectForward(move(b));  // r + r
    WithoutPerfectForward(c);        // const l + r
    WithoutPerfectForward(move(d));  // const r + r
    WithoutPerfectForward(e);        // l ref + r
    WithoutPerfectForward(move(f));  // r ref + r
    WithoutPerfectForward(g);        // const l ref + r
    WithoutPerfectForward(move(h));  // const r ref + r
}

结果：

@└────> # ./a.out 
int & called!
int && called!
const int & called!
const int && called!
int & called!
int && called!
const int & called!
const int && called!

实现代码

/**
 *  @brief  Forward an lvalue.
 *  @return The parameter cast to the specified type.
 *
 *  This function is used to implement "perfect forwarding".
 */
template<typename _Tp>
  constexpr _Tp&&
  forward(typename std::remove_reference<_Tp>::type& __t) noexcept
  { return static_cast<_Tp&&>(__t); }

/**
 *  @brief  Forward an rvalue.
 *  @return The parameter cast to the specified type.
 *
 *  This function is used to implement "perfect forwarding".
 */
template<typename _Tp>
  constexpr _Tp&&
  forward(typename std::remove_reference<_Tp>::type&& __t) noexcept
  {
    static_assert(!std::is_lvalue_reference<_Tp>::value, "template argument"
          " substituting _Tp is an lvalue reference type");
    return static_cast<_Tp&&>(__t);
  }

可以看到，std::forward() 有两个函数，会根据是左值还是右值调用不同的函数，返回不同种类出参。

KMP算法

发表于 2022-11-09 更新于 2026-03-23 分类于 algorithm
本文字数： 935 阅读时长 ≈ 3 分钟

KMP算法是什么

是用来解决字符串匹配的问题。在一个 $str$ 字符串中找到一个子字符串 $sub$ ，返回索引的位置。
常规能想到的最简单的方式就是一个一个比对，匹配失败的话就向下挪一个位置继续匹配。这样做时间复杂度是 $O(n^2)$ 。
KMP算法可以在 $O(n)$ 的时间复杂度内解决这个问题。

next数组是什么

$next$ 数组的本质是寻找子串中“相同前后缀的长度，并且最长”。并且不能是字符串本身。举个例子而言，如下所示：

A	B	A	B	C
0	0	1	2	0

第 $1$ 位 $A$ 只有一个字符，不能是字符串本身，为 $0$ ；
第 $2$ 位 $B$ 和 $A$ 比较，不相等，为 $0$ ；
第 $3$ 位 $A$ 和 $A$ 比较，相等，所以相同前缀为 $1$ ；
第 $4$ 位 $B$ 和前缀为 $1$ 后的 $B$ 比较，相等，和前缀组成了 $AB$ 的相同模式的串，所以相同前缀为 $2$ ；
第 $5$ 位 $C$ 和前缀为 $2$ 后的 $A$ 比较，不相等，和前缀长度为 $0$ 的比，相同前缀为 $0$ ；
关于最长前缀的理解是，如下图所示。

最后一位的 $A$ 很显然可以和 $ABA$ 组成长度为 $3$ 的相同前缀，也可以自己 $A$ 组成长度为 $1$ 的相同前缀。这种情况下选择较大的那个值。

求解next数组

$next$ 数组求解的本质是动态规划。假设我们已经知道当前数字的共同前后缀了，如下图所示。

接下来求第 $i$ 位的 $next$ 数组，分为两种情况。

下一位也和前缀相等
那就很明显等于 $next[i - 1]$ 加上 $1$ 。
下一位和前缀不相等
这里不是直接等于 $0$ 哦。如下图所示

虽然 $ABAB$ 和 $ABAC$ 并不相等，但是也不能直接设为 $0$ 。因为这个新来的 $B$ 可以和前面的 $A$ 组成 $AB$ ，达到 $2$ 的长度。那么这个数难道要暴力求解吗？其实不然。此时第 $i - 1$ 位的 $next$ 的可利用的值在前缀的 $next$ 数组中可以得到答案，在本图中为 $next[2]$ ，即是 $1$ 。此时修改前缀长度为 $next[2]$ ，则又回到了最开始的状况，匹配长度为 $1$ 并且匹配下一位，下一位 $B$ 相等，所以 $next[i]$ 为 $1 + 1 = 2$ 。
代码如下：

vector<int> buildNext(string sub) {
    vector<int> next;
    next.push_back(0);
    int prefix_len = 0;
    int i = 1; // 处理的索引，不会后退，以保证时间复杂度为O(n)
    while (i < sub.size()) {
        if (sub[i] == sub[prefix_len]) { // 下一位相等，next数组数值+1
            prefix_len++;
            next.push_back(prefix_len);
            i++;
        } else { // 下一位不相等
            if (prefix_len == 0) {
                next.push_back(prefix_len); // 目前没有相等的，就是0了
                i++;
            } else {
                prefix_len = next[prefix_len - 1]; // 有不为0的前缀选择，继续回到开始状况
            }
        }
    }
    return next;
}

next数组在KMP中的应用

KMP算法在匹配失败的时候，回去看最后失败的字符前一个字符所对应的 $next$ 值。 $next$ 数组中的值是什么作用呢？它代表我们可以“跳过匹配”的字符数量。

这样就可以保证匹配的 $i$ 不向后退，达到时间复杂度 $O(n)$ 的目的。
代码如下：

int kmp(string s, string sub) {
    vector<int> next = buildNext(sub);
    int i = 0; // 主串指针
    int j = 0; // 子串指针
    while (i < s.size()) {
        if (s[i] == sub[j]) { // 匹配，指针后移
            i++;
            j++;
        } else if (j > 0) { // 匹配失败，但是next跳过了一些字符继续匹配
            j = next[j - 1];
        } else { // 子串第一个字符就匹配失败
            i++;
        }
        if (j == sub.size()) {
            return i - j; // 成功，返回初始下标
        }
    }
    return -1; // 失败
}

nslookup程序(getaddrinfo和getnameinfo示例)

发表于 2022-09-26 更新于 2026-03-23 分类于 socket-programming
本文字数： 146 阅读时长 ≈ 1 分钟

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/socket.h>
#include <netdb.h>

#define MAXLINE 64
int main(int argc, char **argv)
{
    struct addrinfo *p, *listp, hints;
    char buf[MAXLINE];
    int rc, flags;

    if (argc != 2) {
        fprintf(stderr, "usage: %s <domain name>\n", argv[0]);
        exit(0);
    }
    memset(&hints, 0, sizeof(struct addrinfo));
    hints.ai_family = AF_INET;  // 只用IPV4
    hints.ai_socktype = SOCK_STREAM;  // 只用TCP
    if ((rc = getaddrinfo(argv[1], NULL, &hints, &listp)) != 0) {
        fprintf(stderr, "getaddrinfo error: %s\n", gai_strerror(rc));
        exit(1);
    }

    flags = NI_NUMERICHOST;  // 展示数字而不是域名
    for (p = listp; p; p = p->ai_next) {  // 遍历结果链表
        getnameinfo(p->ai_addr, p->ai_addrlen, buf, MAXLINE, NULL, 0, flags);
        printf("%s\n", buf);
    }

    freeaddrinfo(listp);

    exit(0);
}

编译：

gcc nslookup.c -o nslook

运行：

Reference:

CSAPP: $P_{659}$

回文串

发表于 2022-09-10 更新于 2026-03-23 分类于 algorithm
本文字数： 1.9k 阅读时长 ≈ 7 分钟

什么是回文串？

回文串是如abcdedcba，abccba这样的字符串，从前往后和从后往前读是一样的结果。
算法逻辑也很简单，从前和从后同时校验一个字符串，如果不相等直接返回失败。时间复杂度为 $O(n)$ 。

bool check(string s) {
    int len = s.size();
    for (int i = 0; i < len / 2; i++) {
        if (s[i] != s[len - 1 - i]) {
            return false;
        }
    }
    return true;
}

最长回文串问题

给你一个字符串 s，找到 s 中最长的回文子串。
示例：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

暴力搜索

暴力搜索就是依次判断每个子串，如果是回文串就记录下他的长度。

string longestPalindrome(string s) {
    int len = s.size();
    if (len <= 1) {
        return s;
    }
    int maxlen = 1;
    string res = s.substr(0, maxlen);
    for (int i = 0; i < len; i++) {
        for (int j = 2; i + j <= len; j++) { // j是子串的长度，一种优化手段就是从 maxlen + 1 开始取
            string sub = s.substr(i, j);
            if (check(sub) && j > maxlen) { // 更新最长的回文串信息
                res = sub;
                maxlen = j;
            }
        }
    }
    return res;
}

遍历每个子串的时间复杂度是 $O(n^2)$ ，检验回文串时间复杂度为 $O(n)$ ，所以暴力求解的时间复杂度为 $O(n^3)$ 。

中心扩散法

从每一个位置出发，向两边扩散即可，遇到不是回文串就结束。

举例，s=acdbbdaa时，从s[2]=b开始扩散，是什么步骤呢？

向左扩散，直到不和原字符相等。
left = 2, right = 2, cur = 2, len = 1
acdbbdaa

向右扩散，直到不和原字符相等。
left = 2, right = 3, cur = 2, len = 2
acdbbdaa

同时向左右扩散，直到左右不相等。
left = 1, right = 4, cur = 2, len = 4
acdbbdaa

string longestPalindrome(string s) {
    int len = s.size();
    if (len <= 1) {
        return s;
    }
    int left = 0, right = 0, cur = 0;
    string res = "";
    while (cur < len) {
        left = cur, right = cur;
        while (left > 0 && s[left - 1] == s[cur]) { // 向左扩散
            left--;
        }
        while (right < len - 1 && s[right + 1] == s[cur]) { // 向右扩散
            right++;
        }
        while (left > 0 && right < len - 1 && s[left - 1] == s[right + 1]) { // 两边扩散
            left--;
            right++;
        }
        if (right - left + 1 > res.size()) { // 更新结果
            res = s.substr(left, right - left + 1);
        }
        cur++;
    }
    return res;
}

该方法遍历中心点时间复杂度 $O(n)$ ，扩散的时间复杂度 $O(n)$ ，总时间复杂度 $O(n^2)$ 。

动态规划

要判断 $dp[l][r]$ 是否是回文串，只需要知道 $dp[l+1][r-1]$ 是否是回文串就可以了。如果是的话，那么如果 $s[l] == s[r]$ ，那么就是回文串，否则不是。其中有一种特殊情况，在 $s[l] == s[r]$ 相等时，如果这俩相隔是 $2$ ，也可以认为是回文串。
初始化边界条件为所有都是 $false$ ，当 $l==r$ 时为 $true$ （单个字符是回文串）。
递推关系式为

dp[l][r] = ((dp[l+1][r-1]\ \ || \ \ j - i <= 2)\ \ \&\& \ \ s[l]==s[r])\ ?\ true : false

string longestPalindrome(string s) {
    int n = s.size();
    vector<vector<bool>> dp(n, vector<bool>(n, false)); // 初始化为都不是
    for (int i = 0; i < n; i++) { // 初始化边界
        dp[i][i] = true;
    }
    string res = s.substr(0, 1);
    for (int i = n - 1; i >= 0; i--) { // 注意遍历顺序，倒着遍历是为了保证依赖的数据是经过计算的
        for (int j = i + 1; j < n; j++) {
            if (dp[i + 1][j - 1] || j - i <= 2) {
                if (s[i] == s[j]) {
                    dp[i][j] = true;
                }
                if (dp[i][j] && j - i + 1 > res.size()) {
                    res = s.substr(i, j - i + 1);
                }
            }
        }
    }
    return res;
}

这种方式时间复杂度为 $O(n^2)$ ，空间复杂度也为 $O(n^2)$ 。

Manacher算法

这种算法又被称为“马拉车”，可以用 $O(n)$ 的时间复杂度解决最长回文字符串问题。这个算法的总框架是，遍历所有的中心点，寻找每个中心点对应的最长回文子串，然后找到所有中心点对应的最长回文子串。但是在时间复杂度上做了优化，使其变成线性。

臂长

为了表述方便，我们定义一个新概念臂长，表示中心扩展算法向外扩展的长度。如果一个位置的最大回文字符串长度为 $2 * length + 1$ ，其臂长为 $length$ 。
下面的讨论只涉及长度为奇数的回文字符串。长度为偶数的回文字符串可以在每个字符串之间添加用不到的字符从而达到长度变为 $2n + 1$ 为奇数的目的。

从中心扩展的长度即为臂长， $臂长 - 1$ 就是原子串的回文字符串长度。所以问题就变成了求臂长数组。

求原字符串下标

用 $(i - P[i]) / 2$ ，就是原字符串开头的下标了。例如 $P[6] = 5$ ，那么原字符串开头下标为 $(6 - 5) / 2 = 0$ ，所以返回的结果为原字符串的 $[0, 5 - 1]$ 即可。

求每个 P[i]

用 $C$ 表示回文串中心 $Centre$ ，用 $R$ 表示臂长右半部分下标边界，即 $R = C + P[i]$ 。 $C$ 和 $R$ 对应当前循环中 $R$ 最靠右的回文串（手最长的，能管这个数组到最远的，之所以可以保证复杂度是因为保证 $R$ 不退缩）。

如图，在求 $P[i]$ 时，用 $i\_mirror$ 表示要求的第 $i$ 个字符关于 $C$ 对应的下标。我们要求 $P[i]$ ，用中心扩展法就是向两边伸长。但是可以利用已经求出来的回文串中心 $C$ 的对称性，因为 $P[i\_mirror] = 3$ ，那干脆让 $P[i] = 3$ 。有以下 $3$ 中情况会导致这个直接赋值不正确：

1. 超出了 R

当求 $P[i]$ 时， $P[i\_mirror] = 7$ ，但是却不应该等于 $7$ ，因为从 $i$ 往后面数 $7$ 个已经等于 $22$ 了，然而 $R$ 才到 $20$ ，很显然还没有探索到那里。但是可以保证我们一定可以扩展到 $R$ （因为对称），所以 $P[i]$ 至少可以为 $5$ 。剩下的只能中心扩展了。

2. P[i_mirror] 遇到了原字符串左边界

此时 $P[i\_mirror] = 1$ ，但是 $P[i]$ 赋值成 $1$ 是不正确的，原因是 $P[i\_mirror]$ 在扩展时首先是 $\#=\#$ ，之后遇到了边界才终止循环的，但是 $P[i]$ 并没有遇到边界，所以和上面一样继续中心扩展。

3. i == R

这个和情况一很像，将 $P[i] = 0$ ，之后中心扩展即可。

C 和 R 的更新

一步一步求 $P[i]$ ，当求出的 $P[i]$ 的右边界大于当前 $R$ 时，就要更新 $C$ 和 $R$ 了。

此时 $P[i] = 3$ ，导致 $R_(new) = 10 + 3 = 13 > 11$ ，那么 $C = 10, R = 13$ 。

string longestPalindrome(string s) {
    int len = s.length();
    if (len < 1) {
        return "";
    }
    // 预处理
    string s1;
    for (int i = 0; i < len; i++) {
        s1 += "#";
        s1 += s[i];
    }
    s1 += "#";
    len = s1.length();
    int R = 0;               // 当前访问到的所有回文子串，所能触及的最右一个字符的位置
    int C = 0;               // R对应的回文串的对称轴所在的位置
    int MaxP = 0;            // 最大回文串的回文半径
    int MaxC = 0;            // MaxP对应的回文串的对称轴所在的位置
    vector<int> P(len, 0);   // P[i] 表示以第 i 个字符为对称轴的回文串的回文半径
    for (int i = 0; i < len; i++) {
        if (i < R) {  // 1) 当i在R的左边
            P[i] = min(P[2 * C - i], R - i);
        } else {  // 2) 当i在R的右边
            P[i] = 1;
        }
        // 尝试扩展 P[i]，注意处理边界
        while (i - P[i] >= 0 && // 可以把 P[i] 理解为左半径,即回文串的起始位不能小于 0
               i + P[i] < len && // 同上,即回文串的结束位不能大于总长
               s1[i - P[i]] == s1[i + P[i]]) {  // 回文串特性，左右扩展，判断字符串是否相同
            P[i] += 1;
        }
        // 更新 R, C
        if (P[i] + i - 1 > R) {
            R = P[i] + i - 1;
            C = i;
        }
        // 更新 MaxP, MaxC
        if (MaxP <= P[i]) {
            MaxP = P[i];
            MaxC = i;
        }
    }
    return s.substr((MaxC - MaxP + 1) / 2, MaxP - 1);
}

为何基类析构函数必须为虚函数

发表于 2022-08-17 更新于 2026-03-23 分类于 cpp
本文字数： 706 阅读时长 ≈ 3 分钟

基类析构函数为虚函数的必要性

由于 C++ 中类的多态性，使用基类指针指向派生类时，若函数是虚的，则调用派生类中的函数。析构函数也是如此。如果有个基类指针指向了派生类对象，删除这个指针，调用的则是派生类的析构函数。派生类的析构函数又会自动调用基类的析构函数，达到所有空间都释放的目的。

如果不声明为虚函数，那么编译器实行静态绑定，在删除基类指针时，只调用基类的虚构函数而不调用派生类的析构函数，造成派生类中有空间没有释放完全而导致内存泄漏。

所以声明为虚函数是必要的，为了防止只析构基类而不析构派生类。

非虚析构函数会发生什么

#include <iostream>
using namespace std;
class Parent {
    public:
        Parent() {
            cout << "父类构造函数" << endl;
        }
        ~Parent() {
            cout << "父类析构函数" << endl;
        }
};

class Son : public Parent {
    public:
        Son() {
            cout << "子类构造函数" << endl;
        }
        ~Son() {
            cout << "子类析构函数" << endl;
        }
};

int main() {
    Parent *p = new Son();
    delete p;
    p = nullptr;
    return 0;
}

结果：

@└────> # ./a.out 
父类构造函数
子类构造函数
父类析构函数

可以看到，子类析构函数并没有被调用到。

基类析构函数定义为虚函数

#include <iostream>
using namespace std;
class Parent {
    public:
        Parent() {
            cout << "父类构造函数" << endl;
        }
        virtual ~Parent() {
            cout << "父类析构函数" << endl;
        }
};

class Son : public Parent {
    public:
        Son() {
            cout << "子类构造函数" << endl;
        }
        ~Son() {
            cout << "子类析构函数" << endl;
        }
};

int main() {
    Parent *p = new Son();
    delete p;
    p = nullptr;
    return 0;
}

结果：

@└────> # ./a.out 
父类构造函数
子类构造函数
子类析构函数
父类析构函数

小技巧

如果父类的设计者忘记了在析构函数处加 virtual，子类的设计者有义务提醒父类设计者，避免内存泄漏。

C++11 的关键字 override 可以起作用。override 表示函数应当重写基类中的虚函数（用于派生类的虚函数中）。编译器会检查基类中的虚函数和派生类中带有 override 的虚函数有没有相同的函数签名，一旦不匹配便会报错。

因此子类设计者可以在其析构函数后增加关键字 override，一旦父类缺少关键字 virtual，就会被编译器发现并报错。

#include <iostream>
using namespace std;
class Parent {
    public:
        Parent() {
            cout << "父类构造函数" << endl;
        }
        ~Parent() {  // 此处没加 virtual，会有编译错误
            cout << "父类析构函数" << endl;
        }
};

class Son : public Parent {
    public:
        Son() {
            cout << "子类构造函数" << endl;
        }
        ~Son() override {
            cout << "子类析构函数" << endl;
        }
};

int main() {
    Parent *p = new Son();
    delete p;
    p = nullptr;
    return 0;
}

编译结果：

@└────> # g++ test.cc 
test.cc:18:9: error: ‘Son::~Son()’ marked ‘override’, but does not override
         ~Son() override {
         ^

并查集

发表于 2022-08-09 更新于 2026-03-23 分类于 data-structure
本文字数： 683 阅读时长 ≈ 2 分钟

并查集是为了解决什么问题

有10个人，他们之间有错综复杂的关系。如果认定1和2为朋友，2和3也为朋友，那么就认定1和3也是朋友。现在给定两个编号，能否快速知道这两个人是否是朋友？这就是并查集的领域了。

基本思想：

并查集的本质是一个单向且出度为1的图。可以用一个数组来表示，这个数组记录的内容为这个节点所指向的另一个节点的编号。由于这个图出度为1，所以每个元素只唯一的指向另一个元素。而指向的这个节点，我们称为该节点的父节点。
并查集英文叫 unionFind，顾名思义这个数据结构有两个方法，union 和 find。union 用于连接两个集合，find 用于找到这个集合所属的编号。

初始化

只需要把每个节点的父节点设置为自己即可。

void init() {
    for (int i = 0; i < N; i++) {
        parent[i] = i;
    }
}

所属集合的判断

所属的集合只要一直向上遍历，直到找到祖先为止。祖先的编号就是这整个集合的标志编号。

int find(int i) {
    while (parent[i] != i) {
        i = parent[i];
    }
    return i;
}

关系的建立

如果要把两个节点建立并查集关系，只需要指定一个节点的祖先为另一个节点的父节点就可以了。

void merge(int a, int b) {
    int x = find(a);
    int y = find(b);
    if (x == y) {
        return;
    }
    parent[x] = y;
}

路径压缩

在某些极端情况下，这棵树型结构的集合可能会退化为线性结构，这样的情况下find函数会十分耗时。所以我们可以试着在某些方面优化这个效率。

查找时优化

在查找的过程中就直接将沿途的所有元素都指向根节点，大大的缩短下次查找时的时间。

int find(int i) {
    if (i == parent[i]) {
        return i;
    }
    return parent[i] = find(parent[i]); //在第一次查找的时候 将结点直接连到祖先
}

合并时优化

目前的合并是无论如何都让第二个节点的祖先当第一个节点祖先的新祖先，无视了每个集合内树的高度。如果我们记录下树的高度，让较高的树作为新的祖先，较低的树作为它的子节点，可以一定程度的平衡下树的高度。

void merge(int a, int b) {
    int x = find(a);
    int y = find(b);
    if (x == y) {
        return;
    }
    // 比高度
    if (rank[x] < rank[y]) {
        parent[x] = y;
    } else {
        parent[y] = x;
        if (rank[x] == rank[y]) {
            rank[x]++;
        }
    }
}

零拷贝

发表于 2022-07-26 更新于 2026-03-23 分类于 linux
本文字数： 1.4k 阅读时长 ≈ 5 分钟

为什么要零拷贝

传统的 IO 拷贝在计算机中拷贝次数太多，速度太慢，零拷贝可以减少拷贝次数，增加系统性能。另外，零拷贝并不是指没有进行文件的拷贝，只是减少了拷贝的次数。

DMA

直接内存访问（Direct Memory Access）是一种执行 I/O 的工作方式。在这种方式中，DMA 控制器从 CPU 完全接管对总线的控制。这意味着数据交换不经过 CPU，而直接在内存和 I/O 设备之间进行。DMA 方式一般用于高速传送成组数据。DMA 控制器将向内存发出地址和控制信号，修改地址，对传送的字的个数计数，并且以中断方式向 CPU 报告传送操作的结束。

DMA 方式的主要优点是速度快。由于 CPU 根本不参加传送操作，因此就省去了 CPU 取指令、取数、送数等操作。在数据传送过程中，没有保存现场、恢复现场之类的工作。内存地址修改、传送字个数的计数等等，也不是由软件实现，而是用硬件线路直接实现的。所以 DMA 方式能满足高速 I/O 设备的要求，也有利于 CPU 效率的发挥。

用户态和内核态

在 Linux 系统中，有的程序权限很高，可以访问计算机的任何资源，但是有的程序权限就低，只能访问部分资源。这两个类型的程序，就可以映射为用户态和内核态。内核态是计算机的核心，可以访问计算机的任何资源，如网卡、硬盘。为了安全，CPU 不能让用户程序肆无忌惮的访问计算机的任何资源，这样如果用户程序不稳定可能会造成系统崩溃，因此才有的用户态。

内核态：可以访问内存的所有数据，包括外围设备，例如硬盘，网卡，cpu 也可以将自己从一个程序切换到另一个程序。
用户态：只能受限的访问内存，且不允许访问外围设备，占用 cpu 的能力被剥夺，cpu 资源可以被其他程序获取。

综上所述，在 CPU 想要读取硬盘文件的时候，需要从用户态切换为内核态，才有权限。读取完成之后，为了程序安全，需要从内核态切换为用户态。

普通拷贝

在普通的拷贝时，流程如下：

切换到内核态，先到内核态查询内核缓冲区，如果内核缓冲区有数据，则可以直接拷贝到用户空间中。如果内核缓冲区没有，则 CPU 会让 DMA 加载到内核空间中。这里就会有一次 DMA 拷贝。
拷贝到内核缓冲区之后，CPU 将会从内核缓冲区拷贝走。这是一次 CPU 拷贝。拷贝完成切换到用户态。
写数据的时候，再次切换到内核态。切换完成之后，写到 socket 缓冲区。写完之后，切换到用户态。
DMA 通过异步的方式将 socket 缓冲区的数据通过网卡发送到对端。

这种普通的IO。总共有 4 次 CPU 切换（上图蓝色）。分别是：读 2 次、写 2 次。

4 次文件拷贝，分别是：

文件从硬盘到内核空间
内核空间到 CPU
CPU 到 socket 缓冲区
socket 缓冲区到网卡。

零拷贝

mmap

mmap 是零拷贝的一种方式通过虚拟内存的方式实现。也就是说用户空间和内核空间使用同一个物理地址。这样，文件就不在需要经过用户空间。可以从内核缓冲区直接复制到 socket 缓冲区。减少了一次文件拷贝。流程如下：

调用 mmap，将一块用户空间映射到内核空间。此时进入内核态。DMA 把数据加载到内核空间，这是一次 DMA 拷贝。
切换回用户态。
调用 write，向用户空间写数据。数据直接从内核缓冲区写入到 socket 缓冲区。这是一次 CPU 拷贝。
返回用户态。DMA 异步的将 socket 缓冲区内容通过网卡发送到对端。

共计 3 次内存拷贝，4 次用户内核态切换。

sendfile

sendfile 函数可以在两个文件描述符之间传递数据（完全在内核中操作），从而避免了内核缓冲区和用户缓冲区之间的数据拷贝。流程如下：

系统调用 sendfile() 通过 DMA 把硬盘数据拷贝到内核缓冲区，这是一次 DMA 拷贝。
然后数据被内核拷贝到另外一个与 socket 相关的 socket 缓冲区。这里没有用户态和核心态之间的切换，在内核中直接完成了从一个缓冲区到另一个缓冲区的拷贝。这里虽说是写了 cpu 复制，但是如果网卡支持 scatter-gather ，并没有直接复制内容，而是复制了一些 offset 和 length 之类的数据到 socket 缓冲区。如下图：
DMA 异步将 socket 缓冲区内容发送给对端，是一次 DMA 拷贝。如果网卡支持 scatter-gather，那么就直接从内核缓冲区直接 DMA 拷贝到网卡驱动。

共计 3 次或 2 次内存拷贝，2 次用户内核态切换。

linux进程内存布局

发表于 2022-07-26 更新于 2026-03-23 分类于 linux
本文字数： 1.1k 阅读时长 ≈ 4 分钟

进程内存布局

在 x86_64 架构的 32 位操作系统中，linux 的进程内存布局如图所示。这个是进程的虚拟地址空间，这些虚拟地址通过页表映射到物理内存。页表由操作系统维护，由处理器引用。每一个进程都有一个自己的页表。内核也是一个特殊的进程，因为虚拟地址被使能会应用于所有软件，所以内核需要在每个进程的地址空间中都保留一部分虚拟地址专门给内核使用。

内核空间

从 0xC0000000 到 0xFFFFFFFF 这 1G 的空间是内核空间，而 0x00000000 到 0xBFFFFFFF 是用户空间。用户空间无法直接访问内核的虚拟内存空间，仅能通过系统调用来进入内核态，从而来访问内核空间的内存地址。只要用户态的程序试图访问这些页，就会导致一个页错误（page fault）。在 linux 中，内核空间持续存在，并且所有进程中都映射到同样的物理内存。内核的代码和数据总是可以被寻址的，因为随时为系统调用和中断做准备。另外，用户进程也是无法访问 0x00000000 ~ 0x08048000 这一段虚拟内存地址的，在这段地址上有诸多例如 C 库，动态加载器如 ld.so 等的映射地址。如果用户进程访问到该区间会返回段错误。

用户空间

栈

在用户空间的最顶部的部分被叫做栈空间，它一般用于存放函数参数或局部变量。例如：调用一个函数会将函数参数压入到栈空间中，在函数返回时，参数会被栈弹出清理。进程中的每一个线程都有属于自己的栈。

mmap

在栈的低一段便是 mmap，mmap 是一种高效便捷的文件 I/O 方式。内核将文件内容映射在此段内存中，例如加载动态链接库。另外，在 linux 中，如果你通过 malloc 申请一块大于 MMAP_THRESHOLD（默认大小是 128KB）大小的堆空间时，glibc 会返回一块匿名的 mmap 内存块而非一块堆内存。

堆

堆同栈一样，都是为进程运行提供动态的内存分配，但其和栈的的一个很大区别在于堆上内存的生命周期和执行分配的函数的生命周期不同，堆上分配的内存只有在对应进程通过系统调用主动释放或进程结束后才会释放。堆的内存分配效率比栈要低得多。因为栈是由操作系统提供管理的，会在底层堆栈提供支持，分配专门的寄存器（$esp）存放栈的地址，包括压栈出栈也都有专门的指令执行，所以执行效率很高。而堆则是由 C 函数库提供支持，它的机制相对复杂，例如分配一块内存，库函数会按照一定的算法在堆内存空间中搜索可用的足够大的内存空间，如果没有足够大的连续空间，则需要操作系统来重新整理堆内存，这样才有机会分到足够大小的空间，然后才返回。对于堆来说，频繁的 malloc/free（new/delete）势必会造成内存空间的不连续，从而造成大量的内存碎片，程序的运行效率降低。而对于栈来说，分配的一定是连续的内存空间。

BSS段

堆段再往下便是 BSS 段这个静态内存区域，它是用来存储静态局部或静态全局变量的，其在编译期间便决定了虚拟内存的消耗，BSS 段存放的是未初始化的变量。另外根据 C 语言标准规定，未初始化的静态成员变量的初始值必须为 0，所以内核在加载二进制文件后执行程序前会将 BSS 段清 0。

DATA段

DATA 段也是个静态内存区域，也是用来存储静态局部或静态全局变量。但是放的是已经初始化的变量。

代码段

DATA 段再往下便是代码段，这段中存有程序的指令代码。TEXT 段是通过只读的方式加载到内存中的，它可以在多个进程中被安全共享。