C++14

比利♂海灵顿 · 2021-09-02 11:17:43 · 个人记录

关于 C++ 14

这里会做一些我较为疑惑的测试.

register

在 cppreference.com 中明确指出: C++11 及以后, register 仍可以定义, 但是定义的 register 变量和其它变量没有区别. 而在 C++17 及以后, register 变量不可以被定义, 但 register 仍是保留字.

Since C++11, auto is no longer a storage class specifier; it is used to indicate type deduction.

In C, the address of a register variable cannot be taken, but in C++, a variable declared register is semantically indistinguishable from a variable declared without any storage class specifiers. (until C++17)

In C++, unlike C, variables cannot be declared register. (since C++17)

测试代码: 用固定种子生成一个 2 * 10^6 的字符串, 并且倍增法计算后缀数组, 然后求出 Height 数组, 对其建立 ST 表.

Register

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
#define Wild_Donkey 0
using namespace std;
unsigned ST[22][2000005], Bin[22], Log[2000005], ScdRk[2000005];
unsigned Bucket[2000005], SA[2000005], RK[2000005], RkTmp[4000005], m;
char S[2000005];
inline unsigned Min(unsigned L, unsigned R) {
  register unsigned LenLog(Log[R - L + 1]);
  return min(ST[LenLog][L], ST[LenLog][R - Bin[LenLog] + 1]);
}
signed main() {
  srand(573346); m = 2000000;
  for (register unsigned i(1); i <= m; ++i) S[i] = (rand() % 26) + 'a';
  for (register unsigned i(1); i <= m; ++i) ++Bucket[RK[i] = (S[i] -= '_')];
  for (register unsigned i(1); i <= 27; ++i) Bucket[i] += Bucket[i - 1];
  for (register unsigned i(1); i <= m; ++i) SA[Bucket[RK[i]]--] = i;
  for (register unsigned i(1), BucketSize(27); i <= m; ++i) {
    memset(Bucket, 0, (BucketSize + 1) << 2);
    for (register unsigned j(1); j <= m; ++j) ++Bucket[RK[j]];
    for (register unsigned j(1); j <= BucketSize; ++j) Bucket[j] += Bucket[j - 1];
    for (register unsigned j(m - i + 1); j <= m; ++j) ScdRk[j] = j;
    for (register unsigned j(1), TopSR(m - i + 1); j <= m; ++j) if (SA[j] > i) ScdRk[--TopSR] = SA[j] - i;
    for (register unsigned j(1); j <= m; ++j) SA[Bucket[RK[ScdRk[j]]]--] = ScdRk[j];
    memcpy(RkTmp, RK, (m + 1) << 2), BucketSize = 0;
    for (register unsigned j(1); j <= m; ++j) RK[SA[j]] = ((RkTmp[SA[j]] ^ RkTmp[SA[j - 1]]) || (RkTmp[SA[j] + i] ^ RkTmp[SA[j - 1] + i])) ? (++BucketSize) : (BucketSize);
    if (BucketSize == m) break;
  }
  for (register unsigned i(1), j(0); i <= m; ++i) {
    if (j) --j;
    if (RK[i] == 1) { ST[0][RK[i]] = 0; continue; }
    while ((SA[RK[i] - 1] + j <= m) && (i + j <= m) && (S[i + j] == S[SA[RK[i] - 1] + j])) ++j;
    ST[0][RK[i]] = j;
  }
  for (register unsigned i(1), j(0); i <= m; i <<= 1, ++j)
    for (register unsigned k(1); k + (i << 1) - 1 <= m; ++k)
      ST[j + 1][k] = min(ST[j][k], ST[j][k + i]);
  for (register unsigned i(1), j(0); i <= m; i <<= 1, ++j) Bin[j] = i, Log[i] = j;
  for (register unsigned i(1); i <= m; ++i) Log[i] = max(Log[i], Log[i - 1]);
  return Wild_Donkey;
}

No register

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
#define Wild_Donkey 0
using namespace std;
unsigned ST[22][2000005], Bin[22], Log[2000005], ScdRk[2000005];
unsigned Bucket[2000005], SA[2000005], RK[2000005], RkTmp[4000005], m;
char S[2000005];
inline unsigned Min(unsigned L, unsigned R) {
    unsigned LenLog(Log[R - L + 1]);
    return min(ST[LenLog][L], ST[LenLog][R - Bin[LenLog] + 1]);
}
signed main() {
    srand(573346); m = 2000000;
    for (unsigned i(1); i <= m; ++i) S[i] = (rand() % 26) + 'a';
    for (unsigned i(1); i <= m; ++i) ++Bucket[RK[i] = (S[i] -= '_')];
    for (unsigned i(1); i <= 27; ++i) Bucket[i] += Bucket[i - 1];
    for (unsigned i(1); i <= m; ++i) SA[Bucket[RK[i]]--] = i;
    for (unsigned i(1), BucketSize(27); i <= m; ++i) {
        memset(Bucket, 0, (BucketSize + 1) << 2);
        for (unsigned j(1); j <= m; ++j) ++Bucket[RK[j]];
        for (unsigned j(1); j <= BucketSize; ++j) Bucket[j] += Bucket[j - 1];
        for (unsigned j(m - i + 1); j <= m; ++j) ScdRk[j] = j;
        for (unsigned j(1), TopSR(m - i + 1); j <= m; ++j) if (SA[j] > i) ScdRk[--TopSR] = SA[j] - i;
        for (unsigned j(1); j <= m; ++j) SA[Bucket[RK[ScdRk[j]]]--] = ScdRk[j];
        memcpy(RkTmp, RK, (m + 1) << 2), BucketSize = 0;
        for (unsigned j(1); j <= m; ++j) RK[SA[j]] = ((RkTmp[SA[j]] ^ RkTmp[SA[j - 1]]) || (RkTmp[SA[j] + i] ^ RkTmp[SA[j - 1] + i])) ? (++BucketSize) : (BucketSize);
        if (BucketSize == m) break;
    }
    for (unsigned i(1), j(0); i <= m; ++i) {
        if (j) --j;
        if (RK[i] == 1) { ST[0][RK[i]] = 0; continue; }
        while ((SA[RK[i] - 1] + j <= m) && (i + j <= m) && (S[i + j] == S[SA[RK[i] - 1] + j])) ++j;
        ST[0][RK[i]] = j;
    }
    for (unsigned i(1), j(0); i <= m; i <<= 1, ++j)
        for (unsigned k(1); k + (i << 1) - 1 <= m; ++k)
            ST[j + 1][k] = min(ST[j][k], ST[j][k + i]);
    for (unsigned i(1), j(0); i <= m; i <<= 1, ++j) Bin[j] = i, Log[i] = j;
    for (unsigned i(1); i <= m; ++i) Log[i] = max(Log[i], Log[i - 1]);
    return Wild_Donkey;
}

两份代码除了 register 以外完全相同.

测试平台: 洛谷在线 IDE + 本地 (5800H)

测试 5 次取平均值.

register 优化率:

结论:

• 本地 (Windows) C++11 开 -O2 比 C++14 快, 无论开不开 register.

• 本地 C++14 对 register 敏感, 无论开不开 -O2, 开了 register 较快

• 不存在去掉 register 反而加速的情况

• 洛谷 (Linux) C++14 比 C++11 快 (其它变量相同的情况下), 无论开不开 register 或 -O2.

• register 的优化在不开 -O2 时较为敏感, 对 C++11 和 C++14 的效果区别不大.

不关于 C++14

一点基准都没有的基准测试...(以后要改成正常的代码而不是 n^2 循环百万)

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
#define Wild_Donkey 0
using namespace std;
unsigned a[10005], m, n, Cnt(0), A, B, C, D, t, Ans(0), Tmp(0);
bool b[10005];
int main() {
  for (register unsigned i(1); i <= 1000; ++i) {
    for (register unsigned j(1); j <= 1000000000; ++j) {}
    printf("%llu\n", i * (unsigned long long)1000000000);
  }
  return Wild_Donkey;
}