XChy's Blog

Abstract

第一次专门写 blog 解析 LLVM 源码，最近在看鲸书学习编译优化，正好借这个系列结合 Theory 与 Practice。

Interval Analysis 是一种 Control Flow Analysis，常用作于其他优化如 LoopUnroll 的基础。

先看 Interval 类的代码，在编译理论里，Interval 一般指 Node 的集合， 集合里每个 \(Node \ne Head\) 都满足 \(Pred(Node) \subset Interval\) ：

Why do we need dependencies analysis?

Dependencies analysis is the foundation for instruction scheduling and data-cached optimization. It detects and analyzes the conflict relation on resources, control, data, etc, such that other transform can reorder the instruction/BasicBlock to chase better performance.

Here, we mainly focus on the instruction dependencies.

Classifications of instruction dependencies

Lab3 接续 Lab2，要完成Sender的角色。 TCP 的任务主要为：

• Keep track of the receiver's window (acknos and window size)
• Fill the window when possible, by reading from the ByteStream, creating new TCP segments (including SYN and FIN flags if needed), and sending them.
• Keep track of which segments have been sent but not yet acknowledged by the receiver — we call these “outstanding” segments
• Re-send outstanding segments if enough time passes since they were sent, and they haven’t been acknowledged yet

Why am I doing this? The basic principle is to send whatever the receiver will allow

us to send (filling the window), and keep retransmitting until the receiver acknowledges

each segment. This is called “automatic repeat request” (ARQ).

那么TCPSender是怎么时候知道一段segment丢失了呢？

Sender会记录每一个outstanding segment直到收到receiver的ackno。而如果一个segment outstand了太久的话， 我们就需要将其重新发送一遍。

当然，这里有些关于"outstanding for too long"的原则，但Lab3不会让我们解决一些tricky或者过于文字游戏的问题 （留在Lab4）。

这里有几个要点： - Sender的tick函数是唯一一个你可以用的，关于时间的函数。其他对于CPU/OS的调用都是被禁止的。 - Sender会被设置一个retransmission timeout (RTO)。这个就是我们resend segment的时长了。 - 我们需要自己实现retransmission timer，基于tick。 - 每个包含数据的segment被发送时，若timer没有运行，就启动timer。 - 当所有outstanding data被acknowledged了，停止timer。

在这里我们可以讨论一下RTO和Retransmission timer。 首先，当有带数据的segment被发送时，我们要让timer run起来。 当tick时若timer超时，则： - 把segno最低的重发一遍 - 若window大小不为0,则： - retransmission num ++ (timer stop的时候置零) - RTO *= 2, 这是根据流量调整速率的 - reset timer and start it

除此之外\(FIN\)的处理也有点dirty，实现的时候要注意一下。

Lab4和Lab5比较简单，就不记录了，一个是IP/Ethernet以及ARP的NetworkInterface实现，一个则是Router的跳转表实现， 不需要太动脑子。

题目如下：

n 位格雷码序列 是一个由 \(2^n\) 个整数组成的序列，其中：

每个整数都在范围 \([0, 2^n - 1]\) 内, 要求：

• 第一个整数是 0
• 一个整数在序列中出现 不超过一次
• 每对 相邻 整数的二进制表示 恰好一位不同 ，且
• 第一个 和 最后一个 整数的二进制表示 恰好一位不同

给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

说实话我一开始想的简单了，直接暴力搜索，最后发现不行，只能 refer 一下官方题解了

方法一

我们可以用归纳法，从 \(n-1\)推到\(n\)，设序列 \(G_n\) 为\(n\) 位的格雷码序列, 我们可以从 \(G_{n-1}\) 推到 \(G_n\)。

首先把 \(G_{n-1}\) 中所有元素的\(n-1\)位设为 1，得到\(G_{n-1}^T\), 然后拼接 \(G_{n-1}\)和\(G_{n-1}^T\)就得到了我们想要的结果。

为什么呢？其实很简单，\(G_{n-1}^T\) 中每个数字都与\(G_{n-1}\) 有且仅有一位不同, 且 \(G_{n-1}\)是\([0,2^{n-1}]\)的一个排列，\(G_{n-1}^T\)则是\([2^{n-1}, 2^{n}-1]\)上的排列。 二者组合后自然就得到了\([0,2^n-1]\)上的排列，且依次穿插后二进制位恰有一位不同。

方法二

这个方法是纯粹的找规律，如下：

CS144 Lab2的主要任务是完成一个TCP Receiver，在TCP协议中每一个端系统都会有两个角色： Sender和Receiver，这个Lab的主要研究对象就是后者了。

而Receiver要完成几个任务： - 从Sender接受数据 - Reassemble 这些数据（在Lab1已经完成） - 决定是否把Acknowledgement和Flow-Control的数据send back

注意， Acknowledgement 表示的是Receiver所需要下一个byte的index， Flow-Control 表示的则是Receiver想获取多少数据。

转换64位和32位的seqnos

众所周知，64位非常大，以至于可以认为其永远不会溢出，但32位最大只有4GB，这意味着32位的地址可能会不够用。 而TCP header中，seqno是用32位来表示，也就是说为了节省空间，每份sequence的地址都是32位寻址的。

这导致了TCP的一些机制： - 一旦32位的sequence number积累到 \(2^{32} - 1\)，下一字节的index就变成了0。 - 为了提高TCP的健壮性并避免在同一端点之间的早期连接中混淆旧的数据段，TCP试图确保序列号不易被猜测并且不太可能重复。 因此，流的TCP sequences number不从零开始。流中的第一个序列号是一个随机的32位数字，称为初始序列号(\(ISN\)）。 这是表示“零点”或\(SYN\)（流的开始）的序列号。之后的序列号行为与正常情况下相同： 数据的第一个字节将具有\(ISN + 1\mod 2^{32}\)的序列号，第二个字节将具有\(ISN + 2\mod 2^{32}\)的序列号，依此类推。 - (懒得翻译直接粘贴了)The logical beginning and ending each occupy one sequence number: In addition to ensuring the receipt of all bytes of data, TCP makes sure that the beginning and ending of the stream are received reliably. Thus, in TCP the SYN (beginning-ofstream) and FIN (end-of-stream) control flags are assigned sequence numbers. Each of these occupies one sequence number. (The sequence number occupied by the SYN flag is the ISN.) Each byte of data in the stream also occupies one sequence number. Keep in mind that SYN and FIN aren’t part of the stream itself and aren’t “bytes”—they represent the beginning and ending of the byte stream itself.

总之我们要实现一个Wrap32类来进行有关转换，基本代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Wrap32 Wrap32::wrap( uint64_t n, Wrap32 zero_point )
{
  return zero_point + n;
}

uint64_t Wrap32::unwrap( Wrap32 zero_point, uint64_t checkpoint ) const
{
  uint64_t cycle = 1ll << 32;
  uint64_t n_cycle = checkpoint / cycle;
  uint64_t diff = raw_value_ - zero_point.raw_value_;
  uint64_t upper = ( n_cycle + 1ll ) * cycle + diff;
  uint64_t middle = n_cycle * cycle + diff;
  uint64_t lower = ( n_cycle - 1ll ) * cycle + diff;
  if ( ( ( n_cycle == 0 && cycle <= diff ) || n_cycle != 0 ) && checkpoint <= ( lower + middle ) / 2 )
    return lower;
  if ( checkpoint <= ( middle + upper ) / 2 )
    return middle;
  else
    return upper;
}

说实话这里我debug了很久，主要是没有考虑 \(lower < 0\) 的情况。

然后是receiver的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

TCPReceiver::TCPReceiver() : ISN( nullopt ), FIN( false ) {}

void TCPReceiver::receive( TCPSenderMessage message, Reassembler& reassembler, Writer& inbound_stream )
{
  if ( message.SYN )
    ISN = message.seqno;

  if ( !ISN.has_value() )
    return;

  if ( message.FIN )
    FIN = true;

  reassembler.insert( message.seqno.unwrap( ISN.value(), reassembler.bytes_pending() ) + message.SYN - 1ll,
                      message.payload,
                      message.FIN,
                      inbound_stream );
}

TCPReceiverMessage TCPReceiver::send( const Writer& inbound_stream ) const
{
  (void)inbound_stream;
  TCPReceiverMessage ret;
  if ( !ISN.has_value() )
    ret.ackno = nullopt;
  else
    // +1 for the SYN flag, and finish only when FIN flag reached and stream is closed.
    ret.ackno
      = Wrap32::wrap( inbound_stream.bytes_pushed() + 1 + ( FIN && inbound_stream.is_closed() ), ISN.value() );

  ret.window_size = min( inbound_stream.available_capacity(), (uint64_t)UINT16_MAX );

  return ret;
}

逻辑很简单，就是要处理 \(SYN\) 和 \(FIN\) 的情况。

CS144 Lab1的主要任务是完成TCP的Reassembler，其主要功能为：

1

void Reassembler::insert( uint64_t first_index, string data, bool is_last_substring, Writer& output );

TCP的数据流一般由以下部分组成：

| popped data | unpopped-and-pushed data | arrived-and-unpushed data |

其中popped data已经被Reader获取，而unpopped-and-pushed data已经被Writer写进缓存， 但Reader暂时还未读取，最后的arrived-and-unpushed data是从网络接收，尚未组装传入Writer，非连续的数据， 是本Lab的核心工作对象。

计算机网络的特性决定了：不同的数据到来顺序是乱序的，他们之间可能有重叠(overlapping)，而且到来的数据可能已经被push， 而Reassembler要解决这些问题，提供可靠的流服务(Reliable Flow)。

设计思路

我的基本想法是用一个类似char数组的缓存存储arrived-and-unpushed的数据， 然后用一个map<int,int>存储已经到达的数据的index区间 \([l,r]\)，在数据到达时进行区间的合并， 这一问题和经典算法题插入区间一致。

其他的逻辑比较简单，主要是： - first_index若是arrived-and-unpushed data的首地址，要直接push - 若是空字符则省略，但若有last_string的标识，则要把writer关闭 - 一部分data在push之后，buf之后的数据要往前推（有优化空间？）

Reassembler的成员如下：

1
2
3
4
5

private:
  std::map<uint64_t, uint64_t> buffer;
  std::string buf;
  uint64_t end_index;
  uint64_t pending;

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

void Reassembler::insert( uint64_t first_index, string data, bool is_last_substring, Writer& output )
{
  // Your code here.
  (void)first_index;
  (void)data;
  (void)is_last_substring;
  (void)output;

  if ( buf.empty() )
    buf.resize( output.capacity() );

  uint64_t bias_push = output.bytes_pushed();
  uint64_t insert_l = max( output.bytes_pushed(), first_index );
  uint64_t insert_r = min( first_index + data.size() - 1, output.available_capacity() + bias_push - 1 );

  if ( is_last_substring )
    end_index = first_index + data.size() - 1;

  if ( data.empty() && is_last_substring ) {
    output.close();
    return;
  }

  if ( insert_l - first_index >= data.size() )
    return;
  if ( insert_l > insert_r )
    return;

  for ( uint64_t i = insert_l; i <= insert_r; i++ ) {
    buf[i - bias_push] = data[i - first_index];
  }

  bool changed = true;
  while ( changed && !buffer.empty() ) {
    changed = false;
    auto upper = buffer.lower_bound( insert_l );

    // upper.first >= l, compare [l,r] with [uf, us]
    if ( upper != buffer.end() && insert_r + 1 >= upper->first ) {

      insert_r = max( upper->second, insert_r );
      pending -= upper->second - upper->first + 1;

      buffer.erase( upper );
      changed = true;
      continue;
    }

    if ( upper == buffer.begin() || buffer.empty() )
      break;
    auto lower = --upper;

    // lower.first < l, compare [lf, ls] with [l, r]
    if ( lower != buffer.end() && lower->second + 1 >= insert_l ) {

      insert_l =  lower->first;
      insert_r = max( lower->second, insert_r );
      pending -= lower->second - lower->first + 1;

      buffer.erase( lower );
      changed = true;
      continue;
    }
  }

  if ( insert_l == output.bytes_pushed() ) {
    uint64_t old_bias = output.bytes_pushed();
    output.push( buf.substr( insert_l - output.bytes_pushed(), insert_r - insert_l + 1 ) );
    bias_push = output.bytes_pushed();

    if ( insert_r == end_index ) {
      output.close();
    }

    for ( auto it = buffer.begin(); it != buffer.end(); it++ )
      for ( uint64_t i = it->first; i <= it->second; ++i )
        buf[i - bias_push] = buf[i - old_bias];
  } else {
    buffer[insert_l] = insert_r;
    pending += insert_r - insert_l + 1;
  }
}

uint64_t Reassembler::bytes_pending() const
{
  return pending;
}

大部分的代码和插入区间问题一致,最后的性能指标为 1.78Gbit/s，有一定的优化空间。

我想用string先存储起来，最后进行合并的话性能会提高不少。

本文基于指导文档进行编写。

CS144 的 Lab0 主要分为三部分

• 第一部分是 VM 的安装/使用
• 第二部分则是 telnet 等网络程序的尝试
• 第三部分则是写一个基于 OS 自带 socket 库的网络程序和实现一个简单 ByteStream

第一部分可以略过。

第二部分则主要是介绍telnet和telcat，其中telnet的作用就是建立 connection, 并用不同协议进行通信。 netcat则是用于建立 client/server 一类的 end-to-end 的端。

首先用

1

telcat 9091

建立一个对于 9091 端口的监听 socket, 然后打开另一个终端用

1

telnet localhost 9091

连接到该端口，此时 telcat 的窗口就会显示连接信息。

重点是第三部分的实验。这个实验将利用 Linux 的 Socket 构建一个基于 TCP 的程序，要求该程序可以连接到 Web Server，并抓取一个界面。

这里有些需要注意的要点：

• 在 HTTP 协议中每行必须以‘’结尾
• 不能漏了‘Connection: closed’, 不然进程会一直等待

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void get_URL( const string& host, const string& path )
{
  TCPSocket sock1;
  Address addr = Address( host, "http" );
  sock1.connect( addr );
  sock1.write( "GET " + path + " " + "HTTP/1.1\r\nHost: " + host + "\r\nConnection: close\r\n\r\n" );
  while ( 1 ) {
    string recv;
    sock1.read( recv );
    cout << recv;
    if ( sock1.eof() )
      break;
  }
  sock1.close();
}

在 ByteStream 部分，要实现对于数据的读写，笔者主要是基于std::queue实现的缓存， 主要难点在于 peek 函数，参考网上代码后，发现 string_view 必须像下列代码一样初始化：

1
2
3
4

string_view Reader::peek() const
{
  return { &buffer.front(), 1 };
}

优化部分

用 string_view 和 move 实现移动语义：

两个队列存数据和引用

1
2

std::queue<std::string_view> buffer;
std::queue<std::string> buffer_actual;

Reader 的 pop 则要分类讨论：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void Reader::pop( uint64_t len )
{
  bytesPopped += len;
  for ( unsigned i = 0; i < len; ) {
    if ( buffer.front().size() > len - i ) {
      buffer.front() = buffer.front().substr( len - i );
      i = len;
    } else {
      i += buffer.front().size();
      buffer.pop();
      buffer_actual.pop();
    }
  }

  while ( !buffer.empty() && buffer.front().empty() )
    buffer.pop();
  bytesBuffered -= len;
}

最后优化的结果：

线性回归基本方法--最小二乘法(Least Squares Approximations)，这里记录具体思想。

\(Ax=b\)在实际情况中大多是无解的，一种情况是：方程式往往会比未知数更多(\(m>n\))，而 n 列只能产生 m 维线性空间的一小部分。 换句话讲，\(\boldsymbol{b}\) 总是在 \(C(A)\) 之外。这时我们便可以通过上一章投影的有关知识解决这一问题。

首先给出结果，和投影一样，我们的基本方程仍是如下方程： \[A^TA\boldsymbol{\hat{x}}=A^T\boldsymbol{b}\]

而我们的基本目标就是减小 error ( \(\boldsymbol{Ax-b}\) )，我们可以从三个不同的方向解决的这个问题：

几何方向

对于一条直线\(\boldsymbol{b}\)，要让其和一个平面/子空间 \(A\boldsymbol{x}\) 相距最小， 必然要求出其投影\(\boldsymbol{p}\)，\(\boldsymbol{e = b - p}\) 此时就是最小的， \(\boldsymbol{p}\) 此时也是比较合适的的接近解的直线。

代数方向

每一个向量 \(\boldsymbol{b}\) 都可以被分成两个部分，一个是在 \(C(A)\) 中的 \(\boldsymbol{p}\)， 另一部分则是正交于 \(C(A)\) 的 \(\boldsymbol{e}\)。

\(A\boldsymbol{x = b = p + e}\) 是不可解的

\(A\boldsymbol{\hat{x} = p}\) 则是可解的

而后者的解则留下了最小的误差$ $。最小的原因：

这里有 Squared length for any \(x\): \(||Ax - b||^2 = ||Ax-p||^2 + ||e||^2\)

而我们把 \(||Ax-p||^2\) 减到了 \(0\) ，已经把 \(||Ax - b||^2\) 减到不能再减了。

微积分方向

举例而言，对于直线\(C + Dt\)，有三个样本点：\((0,6), (1,0), (2,0)\)，则有：

\[ A=\left [ \begin{matrix} 1& 0 \\ 1& 1 \\ 1& 2 \\ \end{matrix} \right ] , \boldsymbol{x} = \left [ \begin{matrix} C \\ D \\ \end{matrix} \right ] , \boldsymbol{b} = \left [ \begin{matrix} 6 \\ 0 \\ 0 \\ \end{matrix} \right ] \]

我们要最小化 \(E = ||Ax-b||^2\) 则要有： \[\frac{\partial E}{\partial C} = 0, \quad \frac{\partial E}{\partial D} = 0\]

事实上最后化简的结果与 \(A^TA\hat{x}=A^Tb\) 是一样的。

The projection of \(\boldsymbol{b}\) onto a subspace \(C(A)\) is computed by:

\[ \boldsymbol{p} = P\boldsymbol{b} \]

where \(P\) is called Projection Matrix. The reason for multiplying a matrix is based on how the projection is computed.

Here is the reasoning steps:

Let's image that there is \(\boldsymbol{b}\) projecting onto a plane \(C(A)\), producing projection \(\boldsymbol{p}\). Then \(\boldsymbol{p}\) is in \(C(A)\), which could be expressed as \(A\boldsymbol{\hat{x}}\). Our goal is to get \(\boldsymbol{\hat{x}}\).

Let \(\boldsymbol{e = b - A\hat{x}}\) be the error vector , only when \(\boldsymbol{e}\) is perpendicular to the subspace, can we say \(\boldsymbol{p = b - e}\) is projection.

Since \(\boldsymbol{e}\) is perpendicular to \(C(A)\), we can get: \[A^T(\boldsymbol{b}-A\boldsymbol{\hat{x}}) = \boldsymbol{0}\] or \[A^TA\boldsymbol{\hat{x}} = A^T\boldsymbol{b}\]

The symmetric matrix \(A^TA\) is invertible if and only if \(\boldsymbol{a's}\) in \(A\) are independent. Then, \[\boldsymbol{p} = A\boldsymbol{\hat{x}}=A(A^TA)^{-1}A^T\boldsymbol{b}\]

Here \(A(A^TA)^{-1}A^T\) is a matrix, we name it Projection Matrix. You might try to split \((A^TA)^{-1}\) into \(A^{-1}(A^{T})^{-1}\), however when \(A\) is rectangular, it has no inverse.

Or when \(A\) is invertible, \(N(A), N(A^T)\) contains only zero vector, where \(A^T\boldsymbol{e} = 0 \rightarrow \boldsymbol{e=0, b=p}\) itself, \(P = \boldsymbol{I}\) satisfies it well.

Why the symmetric matrix \(A^TA\) is invertible if and only if \(\boldsymbol{a's}\) in \(A\) are independent?

\[A^TAx = 0 \Longleftrightarrow Ax = 0\]

Thus \(A^TA\) has the same nullspace with \(A\). \(A\) is invertible, if and only if \(A^TA\) is invertible.

题目描述：

基本想法：

对于每个方格索引 \(x\)，其容量\(c(x)\)取决于其左边最高的格子和右边最高的格子，也就是说令：

\[t(x) = \min(\max_{y<x}{\{h(y)\}} , \max_{y>x}{\{h(y)\}})\]

则

\[ c(x) = \begin{cases} t(x) - h(x), & \text{if } y > x \\ 0, & \text{otherwise} \end{cases} \]

故我们可以有代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
public:
  int trap(vector<int> &height) {
    int n = height.size();
    int *maxLessThan = new int[n];
    int *maxGreaterThan = new int[n];
    maxLessThan[0] = 0;
    maxGreaterThan[n - 1] = 0;

    int curMax = 0;
    for (int i = 1; i < n; ++i) {
      if (height[i - 1] > curMax)
        curMax = height[i - 1];
      maxLessThan[i] = curMax;
    }
    curMax = 0;
    for (int i = n - 2; i >= 0; --i) {
      if (height[i + 1] > curMax)
        curMax = height[i + 1];
      maxGreaterThan[i] = curMax;
    }

    int ret = 0;
    for (int i = 0; i < n; ++i) {
      int t = std::min(maxLessThan[i], maxGreaterThan[i]);
      int capa = t > height[i] ? t - height[i] : 0;
      ret += capa;
    }

    return ret;
  }
};

当然还有同样思想的双指针法，此处不表。