软件性能工程 project1 write up

软件性能工程 project1 write up -吕茂宁

| ——————– | ——————————– |
| 本实验属于哪门课程？ | 中国海洋大学25春《软件性能工程》 |
| 实验名称？ | 实验1 |

许多程序都在严格的约束条件下运行，在这种情况下如何满足性能要求？

约束条件：

  • 不要执行多线程并行化
  • 以标准C代码为例，不能使用内联汇编指令；
  • 也不要试图使用编译器内部函数或使用汇编或内部函数的库达到相同的效果

问题总结：

  • bit_right_amount 转成 bit_left_amount 后，没有考虑旋转长度超出子区间位长度 (bit_length) 的情况。
  • 旋转算法假设按字节（byte）单位进行操作，但忽略了位数组偏移 (bit_offset) 时，首字节和尾字节并非完整的 8 位，存在跨字节的问题。
  • 采用直接 shift 操作进行旋转时，忽略了位偏移带来的不对齐问题。

解决方案

方法3：方案位运算

首先尝试了第三种方式来实现

方法 3 的优化思路是通过反转操作来实现旋转。具体来说，旋转操作可以分解为以下步骤：

  1. 将子数组分为两部分：a 和 b。
  2. 分别反转 a 和 b，得到 a^R 和 b^R。
  3. 将整个子数组 a^R b^R 反转，得到 ba。

这种方法的优点在于反转操作只需要常量存储空间，且时间复杂度为 O(n)，其中 n 是子数组的长度。

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
// Reverses a subarray of bits.
static void bitarray_reverse(bitarray_t *const bitarray,
                             const size_t bit_offset,
                             const size_t bit_length) {
  size_t left = bit_offset;
  size_t right = bit_offset + bit_length - 1;

  while (left < right) {
    // Swap the bits at positions left and right.
    bool left_bit = bitarray_get(bitarray, left);
    bool right_bit = bitarray_get(bitarray, right);

    bitarray_set(bitarray, left, right_bit);
    bitarray_set(bitarray, right, left_bit);

    left++;
    right--;
  }
}

void bitarray_rotate(bitarray_t *const bitarray,
                     const size_t bit_offset,
                     const size_t bit_length,
                     const ssize_t bit_right_amount) {
  assert(bit_offset + bit_length <= bitarray->bit_sz);

  if (bit_length == 0) {
    return;
  }

  // Convert a rotate left or right to a left rotate only, and eliminate
  // multiple full rotations.
  const size_t bit_left_amount = modulo(-bit_right_amount, bit_length);

  // If the rotation amount is zero, no need to rotate.
  if (bit_left_amount == 0) {
    return;
  }

  // Perform the rotation using the reverse method: (a^R b^R)^R = ba
  const size_t split_point = bit_offset + bit_left_amount;

  // Reverse the first part (a^R).
  bitarray_reverse(bitarray, bit_offset, bit_left_amount);

  // Reverse the second part (b^R).
  bitarray_reverse(bitarray, split_point, bit_length - bit_left_amount);

  // Reverse the entire subarray (a^R b^R)^R.
  bitarray_reverse(bitarray, bit_offset, bit_length);
}

此种方式虽然也实现了目标，但有约20%的样例不能通过，调试很久没有找到解决方案，于是尝试下一种方式

方法1：中间数组

该方法可以预测到当目标字符串较大的时候，性能会较低，所以先尝试另一种方案

方法2：位数组区间旋转（采用的方式）

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
void bitarray_rotate(bitarray_t *const bitarray,
                     const size_t bit_offset,
                     const size_t bit_length,
                     const ssize_t bit_right_amount) {
  assert(bit_offset + bit_length <= bitarray->bit_sz);
  if (bit_length == 0) return;

  const size_t bit_left_amount = modulo(-bit_right_amount, bit_length);
  if (bit_left_amount == 0) return;

  const size_t byte_offset = bit_offset / 8;
  const size_t bit_offset_in_byte = bit_offset % 8;
  const size_t total_bits = bit_length;
  const size_t total_bytes = (total_bits + bit_offset_in_byte + 7) / 8;

  uint8_t *temp_buffer = malloc(total_bytes);
  assert(temp_buffer != NULL);

  for (size_t i = 0; i < total_bytes; i++) {
    temp_buffer[i] = bitarray->buf[byte_offset + i];
  }

  const size_t rotate_bytes = bit_left_amount / 8;
  const size_t rotate_bits_in_byte = bit_left_amount % 8;

  for (size_t i = 0; i < total_bytes; i++) {
    size_t next_index = (i + rotate_bytes + 1) % total_bytes;
    size_t new_index = (i + rotate_bytes) % total_bytes;
    temp_buffer[i] =
        (temp_buffer[new_index] << rotate_bits_in_byte) |
        (temp_buffer[next_index] >> (8 - rotate_bits_in_byte));
  }

  for (size_t i = 0; i < total_bytes; i++) {
    bitarray->buf[byte_offset + i] = temp_buffer[i];
  }

  free(temp_buffer);
}

提升旋转效率，相比按位单步旋转方式，减少位移操作次数，降低时间复杂度。

该代码的实现思路是：

首先通过 assert 确保旋转操作的起始位和长度不超过位数组的总位数，并检查是否需要旋转（如果长度为 0 或旋转量为 0 则直接返回）；

接着计算实际需要左移的位数 bit_left_amount，然后根据起始位和长度计算需要操作的字节偏移和位偏移，并分配一个临时缓冲区 temp_buffer 来存储需要旋转的数据；

之后将位数组中指定范围的数据复制到 temp_buffer 中，并根据旋转量分解为字节旋转数 rotate_bytes 和位旋转数 rotate_bits_in_byte，通过遍历 temp_buffer 对数据进行重新排列，实现旋转操作；

最后将旋转后的数据写回位数组的相应位置，并释放临时缓冲区。整个过程通过临时缓冲区和位操作高效地完成了位数组的旋转功能。

以下部分是优化前后的对比，可以发现性能有了较为明显的提升

以-l情况为例

耗时表

设计 编码 调试 测试 会议
2H 6H 1H 2H 3H

实验心得

通过本次实验，对课上讲解的内容有了更加深刻的理解，通过实际代码将课上不懂的地方补充完整了，并更加理解了操作中按位操作的重要性。

后续改进方向

  1. 性能优化：
    • 针对 对齐情况（如 bit_offset % 8 == 0 且 bit_length % 8 == 0） 时，考虑按字节旋转优化。
    • 针对较长区间位旋转，尝试批量位操作或硬件指令加速。
  2. 接口扩展：
    • 增加 批量旋转、带掩码旋转等高级功能。
    • 封装成库形式，支持更复杂的位图操作。
  3. 测试全面性：
    • 增加边界条件自动生成器，系统性覆盖所有旋转组合。