いくつかのカードのテクニック

何?無駄だと言ったのか?
君は大間違いだ.WCで試験したものが役に立たないはずがない.
O 2をつけるとFFTは開かないより何倍も速くなります
NO 2:NTTはFFTより速くO 2:FFTはNTTより速く
定数はできるだけ定数として宣言する
NTTの問題があって、模数は変数になって1166 1166 ms走ったことを宣言して、模数は定数になって300 ms未満走ったことを宣言します

//6s
const int p=10;
int main()
{
    open("orzzjt");
    int a;
    scanf("%d",&a);
    int i;
    for(i=1;i<=1000000000;i++)
        a=(a*a+10)%p;
    printf("%d
",a);
    return 0;
}

//10s
int p=10;
int main()
{
    open("orzzjt");
    int a;
    scanf("%d",&a);
    int i;
    for(i=1;i<=1000000000;i++)
        a=(a*a+10)%p;
    printf("%d
",a);
    return 0;
}

ビット演算ができるようにできるだけビット演算を使う
もちろん、コンパイラはほとんど最適化されます.
除算と型取りを少なくする
加算演算は1クロック周期、乗算は3クロック周期で、除算と型取り演算は数~数十クロック周期かかります.
　　 3×3 3 × 3のマトリックス乗算:プラスしながら型を取る:27回型を取る演算;全部計算してから型を取る:9 9回型を取る演算.
上位配列のアドレスの最適化
前回使用したアドレスをポインタで保存し、直接オフセットを付けます.
1つの値の繰返し演算に対して一時変数に格納
条件付きジャンプの削除
a:分治予測に適したデータに対して、平均1サイクルを測定するには4.0 4.0クロック周期が必要である.ランダムデータの場合、平均1サイクルを測定するには12.8 12.8クロックサイクルが必要である.分岐予測エラーのペナルティは2であることがわかります.×(12.8−4.0)=17.6 2 × (12.8−4.0)＝17.6クロックサイクル.
b:三元演算子で書き換え、コンパイラに条件伝送に基づくアセンブリコードを生成させる.データにかかわらず、平均1サイクル当たり4.1クロックサイクルしか必要としないことが測定された.

//a.cpp
void minmax1(int *a,int *b,int n)
{
    for(int i=1;i<=n;i++)
        if(a[i]>b[i])
        {
            int t=a[i];
            a[i]=b[i];
            b[i]=t;
        }
}

//b.cpp
void minmax2(int *a,int *b,int n)
{
    for(int i=1;i<=n;i++)
    {
        int mi=a[i]int ma=a[i]

ループ展開
a:各要素に対して平均3.65クロックサイクルが必要です.
b:各要素に対して平均1.36 1.36クロック周期が必要である.
これによりCPU並列を刺激することができる.
展開回数が多すぎると、レジスタが不十分なため、レジスタがオーバーフローする
注意各セクションが独立し、非展開回数の倍数を処理する部分

//a.cpp
double sum(double *a,int n)
{
    double s=0;
    for(int i=1;i<=n;i++)
    {
        s+=a[i];
    }
    return s;
}

//b.cpp
double sum(double *a,int n)
{
    double s0=0,s1=0,s2=0,s3=0;
    for(int i=1;i<=n;i+=4)
    {
        s0+=a[i];
        s1+=a[i+1];
        s2+=a[i+2];
        s3+=a[i+3];
    }
    return s0+s1+s2+s3;
}

キャッシュに優しいコードの作成
空間の局部性は良いです
できるだけステップ1のアクセスモードを使用します.つまり、アクセスメモリが連続しています.
高次元配列を巡ることが重要です
時間的局所性がよい
メモリアクセスのワークセットはできるだけ小さくします
整数バイナリ表現の1の個数を統計する場合、2段に分けて表を調べるより3段に分けたほうがいい場合がある.
ステップ長が大きい2 2 2のべき乗を使用しないアクセスモード
キャッシュの競合を回避します.
状圧DP、高位配列を使用する場合に重要
解決策:配列を少し大きくする
いくつかのデータ
を選択します.
ちえん
CPUレジスタ
0 0
TLB
0 0
L 1キャッシュ
4 4
L 2キャッシュ
10 10
L 3キャッシュ
50 50
仮想メモリ
200 200
あるIntel Core i 5 CPUでは、これらのキャッシュがあります.
キャッシュ・タイプ
アクセス期間
キャッシュ・サイズ
れんけつど
ブロックサイズ
グループ数
L1 I-Cache
4 4
32 32 KB
8 8
64 64 B
64 64
L1 D-Cache
4 4
32 32 KB
8 8
64 64 B
64 64
L2 Cache
約12 12
256 256 KB
4 4
64 64 B
512 512
L3 Cache
約50,50
6 6 MB
12 12
64 64 B
8192 8192
異なるn nとdに対して,このプログラムを繰り返し呼び出し,異なる時空局所性を有する.
n n nが小さいほど時間局所性が良く,d dが小さいほど空間局所性が良いことが容易に分かる.

int sum(int *a,int n,int d)
{
    int s=0;
    for(int i=0;is+=a[i*d];
    return s;
}

くうかんきょくぶせい
n nが十分大きい場合の結果は以下の通りである
理論にかなう
d d
1 1
2 2
3 3
4 4
8 8
16 16
32 32
64 64
サイクル数
1.50 1.50
2.34 2.34
3.46 3.46
4.73 4.73
9.70 9.70
15.00 15.00
19.76 19.76
20.26 20.26
じかんきょくぶせい
n=200 n=200の場合の結果は以下の通りである
d d
219 2 19
219+1 2 19 + 1
サイクル数
159 159
1.18 1.18
これはなぜですか.
200 200個の整数、明らかにL 1キャッシュで詰めることができますか?
d=219 d=2 19の場合、メモリアクセスのたびにアドレスの後19ビットは同じです.
CPUキャッシュの原理によって、これらのアドレスは必ず同じグループにマッピングされます.
したがって、キャッシュは1組のみであり、159サイクルはメモリアクセス速度である.
p.s.:後19ビットは同じ仮想アドレスであり、物理アドレスにマッピングされた後も、オペレーティングシステムの特性上、少なくとも後12ビットは同じである.