コラッツの推測をテストするためのC ++コードが、手書きのアセンブリよりも高速に実行されるのはなぜですか?

851
rosghub 2016-11-01 20:12.

Project Euler Q14のこれら2つのソリューションを、アセンブリとC ++で作成しました。彼らは、コラッツの予想をテストするために同一のブルートフォースアプローチを実装しています。アセンブリソリューションは、次のもので組み立てられました。

nasm -felf64 p14.asm && gcc p14.o -o p14

C ++は次のようにコンパイルされました。

g++ p14.cpp -o p14

アセンブリ、p14.asm

section .data
    fmt db "%d", 10, 0

global main
extern printf

section .text

main:
    mov rcx, 1000000
    xor rdi, rdi        ; max i
    xor rsi, rsi        ; i

l1:
    dec rcx
    xor r10, r10        ; count
    mov rax, rcx

l2:
    test rax, 1
    jpe even

    mov rbx, 3
    mul rbx
    inc rax
    jmp c1

even:
    mov rbx, 2
    xor rdx, rdx
    div rbx

c1:
    inc r10
    cmp rax, 1
    jne l2

    cmp rdi, r10
    cmovl rdi, r10
    cmovl rsi, rcx

    cmp rcx, 2
    jne l1

    mov rdi, fmt
    xor rax, rax
    call printf
    ret

C ++、 p14.cpp

#include <iostream>

int sequence(long n) {
    int count = 1;
    while (n != 1) {
        if (n % 2 == 0)
            n /= 2;
        else
            n = 3*n + 1;
        ++count;
    }
    return count;
}

int main() {
    int max = 0, maxi;
    for (int i = 999999; i > 0; --i) {
        int s = sequence(i);
        if (s > max) {
            max = s;
            maxi = i;
        }
    }
    std::cout << maxi << std::endl;
}

速度とすべてを改善するためのコンパイラの最適化については知っていますが、アセンブリソリューションをさらに最適化する方法は多くありません(数学ではなくプログラムで話す)。

C ++コードは、項ごとにモジュラスを使用し、1つおきに除算を使用しますが、アセンブリコードは、1つおきに1つの除算のみを使用します。

ただし、アセンブリには、C ++ソリューションよりも平均1秒長くかかります。どうしてこれなの?私は主に好奇心から質問しています。

実行時間

私のシステム:1.4GHzのIntelCeleron 2955U(Haswellマイクロアーキテクチャ)上の64ビットLinux。

10 answers

1931
Peter Cordes 2016-11-01 21:04.

64ビットのDIV命令が2で除算するのに適した方法だと思う場合は、コンパイラのasm出力が-O0(高速コンパイル、追加の最適化なし、メモリへの保存/再読み込み後/すべてのCステートメントの前にあるため、デバッガーは変数を変更できます)。

効率的なasmの記述方法については、AgnerFogのOptimizingAssemblyガイドを参照してください。彼はまた、特定のCPUの特定の詳細について、命令テーブルとマイクロアーチガイドを持っています。その他のパフォーマンスリンクについては、x86タグwikiも参照してください。

手書きのasmでコンパイラを打ち負かすことについてのこのより一般的な質問も参照してください:インラインアセンブリ言語はネイティブC ++コードよりも遅いですか?。TL:DR :(この質問のように)間違った場合はそうです。

通常、特に効率的にコンパイルできるC ++を作成しようとする場合は、コンパイラにその処理を任せても問題ありません。また、アセンブリ言語とコンパイル言語。答えの1つは、さまざまなCコンパイラがクールなトリックでいくつかの非常に単純な関数を最適化する方法を示すこれらのきちんとしたスライドへのリンクです。 Matt GodboltのCppCon2017トーク「最近、私のコンパイラは私のために何をしましたか?コンパイラのふたのボルトを外す」も同様です。


even:
    mov rbx, 2
    xor rdx, rdx
    div rbx

Intel Haswellでは、div r6436 uopsで、レイテンシは32〜96サイクル、スループットは21〜74サイクルに1つです。(さらに、RBXとゼロRDXをセットアップするための2つのuopsがありますが、アウトオブオーダー実行はそれらを早期に実行できます)。 IntelSnBファミリCPUでのマイクロコード化された命令を含むループのブランチアラインメントこの場合、遅延はループで運ばれる依存関係チェーンの一部であるため、最も関連性の高い要素です。

shr rax, 1同じ符号なし除算を実行します。これは1uopで、レイテンシ1cで、クロックサイクルごとに2つ実行できます。

比較のために、32ビット除算は高速ですが、それでもシフトに対して恐ろしいです。idiv r32Haswellでは9uops、22〜29cのレイテンシ、8〜11cのスループットごとに1つです。


gccの-O0asm出力(Godboltコンパイラエクスプローラー)を見るとわかるように、shifts命令のみを使用します。clang-O0は、64ビットIDIVを2回使用しても、思ったように単純にコンパイルされます。(最適化するとき、コンパイラーは、ソースが同じオペランドで除算とモジュラスを実行するときにIDIVの両方の出力を使用します(IDIVを使用する場合))。

GCCには完全にナイーブなモードはありません。常にGIMPLEを介して変換されますつまり、一部の「最適化」を無効にすることはできません。これには、定数による除算の認識と、シフト(2の累乗)またはGCCが整数除算を実装する際に奇妙な数による乗算を使用するのはなぜですか?(2の累乗ではない)を使用してIDIVを回避することが含まれます(div_by_13上記のゴッドボルトリンクを参照)。

gcc -Os(サイズを最適化)、2の累乗以外の除算にIDIVを使用ますが、残念ながら、乗法逆数コードがわずかに大きいがはるかに高速な場合でも使用されます。


コンパイラを支援する

(この場合の要約:使用uint64_t n

まず第一に、最適化されたコンパイラ出力を見るのは興味深いことです。(-O3)。 -O0速度は基本的に無意味です。

asm出力を確認します(Godboltで、またはGCC / clangアセンブリ出力から「ノイズ」を取り除く方法は?参照してください)。コンパイラーがそもそも最適なコードを作成しない場合:コンパイラーがより良いコードを作成するようにガイドする方法でC / C ++ソースを作成することが、通常は最良のアプローチです。asmを知り、何が効率的かを知る必要がありますが、この知識を間接的に適用します。コンパイラーも良いアイデアの源です:時々clangは何かクールなことをするでしょう、そしてあなたは同じことをするためにgccを手に持つことができます:この答えと私が以下の@Veedracのコードの展開されていないループでしたことを見てください。)

このアプローチは移植可能であり、20年以内に、将来のコンパイラーは、新しいISA拡張機能または自動ベクトル化を使用して、将来のハードウェア(x86かどうか)で効率的なものにコンパイルできます。15年前の手書きのx86-64asmは、通常、Skylake用に最適に調整されていません。たとえば、compare&branchマクロフュージョンは当時存在していませんでした。 1つのマイクロアーキテクチャ用の手作りのasmに現在最適なものは、他の現在および将来のCPUには最適ではない可能性があります。 コラッツの推測をテストするためのC ++コードが、手書きのアセンブリよりも高速に実行されるのはなぜですか?主な違いについて説明しています。これらは、このコードに大きな影響を及ぼします。しかし理論的には、g++ -O3 -march=bdver3そしてg++ -O3 -march=skylake正しいことをするでしょう。(または-march=native。)または-mtune=...、他のCPUがサポートしていない可能性のある命令を使用せずに、単に調整する。

私の考えでは、コンパイラを現在のCPUに適したasmにガイドすることは、将来のコンパイラにとって問題になることはないはずです。コードを変換する方法を見つける点で、現在のコンパイラよりも優れているといいのですが、将来のCPUで機能する方法を見つけることができます。とにかく、将来のx86は、現在のx86で良いことはおそらくひどいことではなく、将来のコンパイラーは、Cソースからのデータ移動のようなものを実装する際に、より良いものが見当たらない場合、asm固有の落とし穴を回避します。

手書きのasmはオプティマイザのブラックボックスであるため、インライン化によって入力がコンパイル時定数になる場合、定数伝播は機能しません。他の最適化も影響を受けます。asmを使用する前に、https: //gcc.gnu.org/wiki/DontUseInlineAsmをお読みください。(そして、MSVCスタイルのインラインasmを避けてください:入力/出力はメモリ通過する必要があり、オーバーヘッドが追加されます。)

この場合:あなたnは署名されたタイプを持っており、gccは正しい丸めを与えるSAR / SHR / ADDシーケンスを使用します。(IDIVと算術シフトは、負の入力では「丸め」が異なります。SARinsnset refの手動入力を参照してください)。(gccがそれを否定できないことを証明しようとして失敗した場合、IDK n。署名されたオーバーフローは未定義の動作であるため、できるはずでした。)

を使用する必要がuint64_t nあったので、SHRだけで済みます。そのため、long32ビットしかないシステム(x86-64 Windowsなど)に移植できます。


ところで、gccの最適化されたasm出力は(を使用してunsigned long n)かなり良く見えます:インライン化された内部ループmain()はこれを行います:

 # from gcc5.4 -O3  plus my comments

 # edx= count=1
 # rax= uint64_t n

.L9:                   # do{
    lea    rcx, [rax+1+rax*2]   # rcx = 3*n + 1
    mov    rdi, rax
    shr    rdi         # rdi = n>>1;
    test   al, 1       # set flags based on n%2 (aka n&1)
    mov    rax, rcx
    cmove  rax, rdi    # n= (n%2) ? 3*n+1 : n/2;
    add    edx, 1      # ++count;
    cmp    rax, 1
    jne   .L9          #}while(n!=1)

  cmp/branch to update max and maxi, and then do the next n

内側のループはブランチレスであり、ループで運ばれる依存関係チェーンのクリティカルパスは次のとおりです。

  • 3成分LEA(3サイクル)
  • cmov(Haswellでは2サイクル、Broadwell以降では1c)。

合計:反復ごとに5サイクル、遅延のボトルネック。アウトオブオーダー実行は、これと並行して他のすべてを処理します(理論的には、パフォーマンスカウンターを使用して、実際に5c / iterで実行されるかどうかをテストしていません)。

cmov(TESTによって生成された)のFLAGS入力は(LEA-> MOVからの)RAX入力よりも生成が速いため、クリティカルパス上にはありません。

同様に、CMOVのRDI入力を生成するMOV-> SHRは、LEAよりも高速であるため、クリティカルパスから外れています。IvyBridge以降のMOVのレイテンシはゼロです(レジスタリネーミング時に処理されます)。(それでもuopとパイプラインのスロットが必要なので、無料ではなく、待ち時間がゼロです)。LEA depチェーンの余分なMOVは、他のCPUのボトルネックの一部です。

cmp / jneもクリティカルパスの一部ではありません。クリティカルパス上のデータ依存関係とは異なり、制御の依存関係は分岐予測+投機的実行で処理されるため、ループキャリーされません。


コンパイラを打ち負かす

GCCはここでかなり良い仕事をしました。のinc edx代わりにadd edx, 1を使用することで、1コードバイトを節約できます。これ、P4と、部分的なフラグ変更命令に対するその誤った依存関係について誰も気にしないためです。

また、すべてのMOV命令を保存することもでき、TEST:SHRはCF =ビットをシフトアウトするように設定するためcmovctest/の代わりに使用できますcmovz

 ### Hand-optimized version of what gcc does
.L9:                       #do{
    lea     rcx, [rax+1+rax*2] # rcx = 3*n + 1
    shr     rax, 1         # n>>=1;    CF = n&1 = n%2
    cmovc   rax, rcx       # n= (n&1) ? 3*n+1 : n/2;
    inc     edx            # ++count;
    cmp     rax, 1
    jne     .L9            #}while(n!=1)

別の巧妙なトリックについては、@ johnfoundの回答を参照してください。SHRのフラグ結果で分岐してCMPを削除し、CMOVに使用します。nが1(または0)の場合にのみゼロです。(おもしろい事実:Nehalem以前でカウント!= 1のSHRは、フラグの結果を読み取るとストールを引き起こします。そのため、シングルuopになりました。ただし、1シフトの特別なエンコードで問題ありません。)

MOVを回避しても、Haswellのレイテンシーはまったく役に立ちません(x86のMOVは本当に「無料」でしょうか?なぜこれをまったく再現できないのですか?)。Intelpre-IvBやAMDBullozerファミリなど、MOVがゼロレイテンシではないCPUで非常に役立ちます。コンパイラの無駄なMOV命令は、クリティカルパスに影響を与えます。BDの複雑なLEAとCMOVはどちらもレイテンシーが低いため(それぞれ2cと1c)、レイテンシーの大部分を占めています。また、整数ALUパイプが2つしかないため、スループットのボトルネックが問題になります。 コラッツの推測をテストするためのC ++コードが、手書きのアセンブリよりも高速に実行されるのはなぜですか?からのタイミング結果があります。

Haswellでも、このバージョンは、クリティカルでないuopがクリティカルパス上のポートから実行ポートを盗み、実行を1サイクル遅らせるという、時折の遅延を回避することで少し役立つ場合があります。(これはリソースの競合と呼ばれます)。また、レジスタを保存します。これはn、インターリーブループで複数の値を並列に実行する場合に役立ちます(以下を参照)。

LEAのレイテンシは、 IntelSnBファミリCPUのアドレッシングモードによって異なります。3つのコンポーネントの場合は3c([base+idx+const]、2つの別々の追加が必要)が、2つ以下のコンポーネント(1つの追加)の場合は1cのみ。一部のCPU(Core2など)は、1サイクルで3コンポーネントLEAを実行しますが、SnBファミリは実行しません。さらに悪いことに、Intel SnBファミリはレイテンシを標準化するため、2c uopsはありません。そうでない場合、3コンポーネントLEAはBulldozerのように2cになります。(3コンポーネントLEAはAMDでも遅くなりますが、それほど遅くはありません)。

つまり、HaswellのようなIntel SnBファミリCPUでは、lea rcx, [rax + rax*2]/inc rcxはわずか2cのレイテンシであり、より高速ですlea rcx, [rax + rax*2 + 1]。BDでは損益分岐点、Core2ではさらに悪化します。追加のuopが必要であり、通常は1cのレイテンシーを節約する価値はありませんが、レイテンシーがここでの主要なボトルネックであり、Haswellには追加のuopスループットを処理するのに十分な幅があります。

gcc、icc、clang(godbolt上)のいずれもSHRのCF出力を使用せず、常にANDまたはTESTを使用していました。愚かなコンパイラ。:Pそれらは複雑な機械の素晴らしい部分ですが、賢い人間はしばしば小規模な問題でそれらを打ち負かすことができます。(もちろん、それについて考えるのに数千倍から数百万倍長くなります!コンパイラは、多くのインラインコードを最適化するときに時間がかかりすぎるため、すべての可能な方法を検索するために網羅的なアルゴリズムを使用しません。また、ターゲットのマイクロアーキテクチャでパイプラインをモデル化せず、少なくともIACAとは何ですか?どのように使用しますか?やその他の静的分析ツールと同じ詳細ではなく、ヒューリスティックを使用するだけです。)


単純なループ展開は役に立ちません; このループのボトルネックは、ループのオーバーヘッド/スループットではなく、ループで実行される依存関係チェーンの遅延です。これは、CPUが2つのスレッドからの命令をインターリーブするために多くの時間を持っているため、ハイパースレッディング(または他の種類のSMT)でうまくいくことを意味します。これは、のループを並列化することを意味しますがmain、各スレッドはn値の範囲をチェックし、結果として整数のペアを生成できるため、これで問題ありません。

1つのスレッド内で手作業でインターリーブすることも実行可能かもしれません。たぶん、それぞれが2つのレジスタしかとらず、それらはすべて同じmax/を更新できるので、並列の数値のペアのシーケンスを計算しますmaxi。これにより、より多くの命令レベルの並列性が作成されます。

秘訣は、すべてのn値に達するまで待ってから1別の開始n値のペアを取得するか、または他のシーケンスのレジスタに触れずに、終了条件に達した1つだけの新しい開始点を取得するかどうかを決定することです。おそらく、各チェーンが有用なデータで機能し続けることが最善です。そうでない場合は、条件付きでカウンターをインクリメントする必要があります。


SSEパックを使用してこれを行うこともできます。比較して、まだn到達し1ていないベクトル要素のカウンターを条件付きでインクリメントします。そして、SIMD条件付きインクリメント実装のさらに長いレイテンシーを隠すには、より多くのn値のベクトルを空中に維持する必要があります。たぶん256bベクトル(4x uint64_t)でのみ価値があります。

1「スティッキー」を検出するための最善の戦略は、カウンターをインクリメントするために追加するすべてのベクトルをマスクすることだと思います。したがって1、要素にaが表示された後、インクリメントベクトルはゼロになり、+ = 0は何もしません。

手動ベクトル化のテストされていないアイデア

# starting with YMM0 = [ n_d, n_c, n_b, n_a ]  (64-bit elements)
# ymm4 = _mm256_set1_epi64x(1):  increment vector
# ymm5 = all-zeros:  count vector

.inner_loop:
    vpaddq    ymm1, ymm0, xmm0
    vpaddq    ymm1, ymm1, xmm0
    vpaddq    ymm1, ymm1, set1_epi64(1)     # ymm1= 3*n + 1.  Maybe could do this more efficiently?

    vprllq    ymm3, ymm0, 63                # shift bit 1 to the sign bit

    vpsrlq    ymm0, ymm0, 1                 # n /= 2

    # FP blend between integer insns may cost extra bypass latency, but integer blends don't have 1 bit controlling a whole qword.
    vpblendvpd ymm0, ymm0, ymm1, ymm3       # variable blend controlled by the sign bit of each 64-bit element.  I might have the source operands backwards, I always have to look this up.

    # ymm0 = updated n  in each element.

    vpcmpeqq ymm1, ymm0, set1_epi64(1)
    vpandn   ymm4, ymm1, ymm4         # zero out elements of ymm4 where the compare was true

    vpaddq   ymm5, ymm5, ymm4         # count++ in elements where n has never been == 1

    vptest   ymm4, ymm4
    jnz  .inner_loop
    # Fall through when all the n values have reached 1 at some point, and our increment vector is all-zero

    vextracti128 ymm0, ymm5, 1
    vpmaxq .... crap this doesn't exist
    # Actually just delay doing a horizontal max until the very very end.  But you need some way to record max and maxi.

これは、手書きのasmではなく組み込み関数を使用して実装できます。


アルゴリズム/実装の改善:

同じロジックをより効率的なasmで実装するだけでなく、ロジックを単純化する方法や、冗長な作業を回避する方法を探してください。たとえば、シーケンスの一般的な終了を検出するためにメモ化します。またはさらに良いことに、一度に8つの末尾ビットを見てください(gnasherの答え)

@EOFは、tzcnt(またはbsf)を使用してn/=21つのステップで複数の反復を実行できることを指摘しています。それはおそらくSIMDベクトル化よりも優れています。SSEまたはAVX命令はそれを行うことができません。nただし、異なる整数レジスタで複数のスカラーを並列に実行することと互換性があります。

したがって、ループは次のようになります。

goto loop_entry;  // C++ structured like the asm, for illustration only
do {
   n = n*3 + 1;
  loop_entry:
   shift = _tzcnt_u64(n);
   n >>= shift;
   count += shift;
} while(n != 1);

これにより、反復回数が大幅に少なくなる可能性がありますが、BMI2のないIntel SnBファミリCPUでは、変数カウントのシフトが遅くなります。3 uops、2cレイテンシー。(count = 0はフラグが変更されていないことを意味するため、FLAGSへの入力依存関係があります。これをデータ依存関係として処理し、uopは2つの入力しか持てないため(とにかくHSW / BDW以前)複数のuopを取ります)。これは、x86のクレイジーなCISC設計について不満を言う人々が言及している種類です。x86 CPUは、ほぼ同様の方法でさえ、今日ISAがゼロから設計された場合よりも遅くなります。(つまり、これは速度/電力を消費する「x86税」の一部です。)SHRX / SHLX / SARX(BMI2)は大きな勝利です(1 uop / 1cレイテンシー)。

また、クリティカルパスにtzcnt(Haswell以降では3c)を配置するため、ループで運ばれる依存関係チェーンの合計遅延が大幅に長くなります。n>>1ただし、CMOVの必要性、またはレジスター保持の準備の必要性はなくなります。@Veedracの答えは、tzcnt / shiftを複数の反復で延期することでこれらすべてを克服します。これは非常に効果的です(以下を参照)。

その時点でゼロになることは決してないため、BSFまたはTZCNTを同じ意味で安全に使用できnます。TZCNTのマシンコードは、BMI1をサポートしないCPUでBSFとしてデコードします。(意味のないプレフィックスは無視されるため、REP BSFはBSFとして実行されます)。

TZCNTは、それをサポートするAMD CPUでBSFよりもはるかに優れたパフォーマンスを発揮するためREP BSF、出力ではなく入力がゼロの場合にZFを設定する必要がない場合でも、を使用することをお勧めします。一部のコンパイラは、を使用し__builtin_ctzllてもこれを実行します-mno-bmi

Intel CPUでも同じように動作するので、それだけが重要な場合はバイトを保存してください。Intel(Skylake以前)のTZCNTは、BSFと同様に、書き込み専用と思われる出力オペランドに誤った依存関係があり、入力= 0のBSFが宛先を変更しないという文書化されていない動作をサポートします。したがって、Skylakeのみを最適化しない限り、これを回避する必要があります。したがって、余分なREPバイトから得られるものは何もありません。(Intelは、x86 ISAマニュアルで要求されている以上のことを行って、広く使用されているコードを壊さないようにします。これは、すべきでないものに依存したり、遡及的に禁止されたりします。たとえば、Windows 9xは、TLBエントリの投機的なプリフェッチを想定していません。これは安全でした。コードが記述されたとき、自己変更コードを使用したx86での古い命令フェッチの監視。)

とにかく、HaswellのLZCNT / TZCNTはPOPCNTと同じ偽の深さを持っています:32ビットのループカウンターを64ビットに置き換えると、IntelCPUで_mm_popcnt_u64のパフォーマンスが大幅に低下します。参照してください。これが、@ Veedracのコードに対するgccのasm出力で、dst = srcを使用しないときにTZCNTの宛先として使用しようとしているレジスタのxor-zeroingdepチェーンを切断しているのがわかる理由です。TZCNT / LZCNT / POPCNTは、宛先を未定義または未変更のままにすることは決してないため、Intel CPUの出力に対するこの誤った依存関係は、パフォーマンスのバグ/制限です。おそらく、同じ実行ユニットに行く他のuopsのように動作させることは、いくつかのトランジスタ/パワーの価値があります。唯一の利点は、別のuarch制限との相互作用です。Haswellマイクロフュージョンとアドレッシングモードが、IntelがLZCNT / TZCNTの誤ったdepを削除したSkylakeではマイクロフュージョンとアドレッシングモードを「非ラミネート」します。 POPCNTは、引き続き任意のアドレスモードをマイクロヒューズできます。


他の回答からのアイデア/コードの改善:

@hidefromkgbの答えは、3n +1の後に1つの右シフトを実行できることが保証されているという素晴らしい観察結果を持っています。ステップ間のチェックを省略するよりも、これをさらに効率的に計算できます。ただし、その回答のasm実装は壊れており(OFに依存し、カウントが1より大きいSHRDの後で定義されていません)、slow:ROR rdi,2は、よりも高速SHRD rdi,rdi,2であり、クリティカルパスで2つのCMOV命令を使用すると、追加のTESTよりも低速になります。並行して実行できます。

私は整理された/改善されたC(コンパイラがより良いasmを生成するようにガイドします)を置き、Godboltでテスト+より高速なasm(Cの下のコメント)を動作させます:コラッツの推測をテストするためのC ++コードが、手書きのアセンブリよりも高速に実行されるのはなぜですか?リンクを参照してください。(この回答は、大きなGodbolt URLから30k文字の制限に達しましたが、Javaでフォーマットされたdiff出力を生成するリンクJavaでフォーマットされたdiff出力を生成するあり、とにかくgoo.glには長すぎました。)

またwrite()、一度に1文字ずつ書き込む代わりに、文字列に変換して1つ作成するように出力印刷を改善しました。これにより、perf stat ./collatz(パフォーマンスカウンターを記録するために)プログラム全体のタイミングへの影響が最小限に抑えられ、重要ではないasmの一部の難読化が解除されました。


@Veedracのコード

私たちのように私は限り右シフトからマイナーのスピードアップを持って知っているニーズをやって、ループを継続するためのチェック。制限= 1e8の7.5秒からCore2Duo(Merom)の7.275秒まで、展開係数は16です。

Godboltに関するコード+コメント。このバージョンをclangで使用しないでください。それはdefer-loopで何かばかげたことをします。tmpカウンターを使用kしてcount後で追加すると、clangの動作が変わりますが、gccが少し痛くなります。

コメントの説明を参照してください:VeedracのコードはBMI1を搭載したCPUで優れています(つまり、Celeron / Pentiumではありません)

106
johnfound 2016-11-01 22:29.

C ++コンパイラが有能なアセンブリ言語プログラマよりも最適なコードを生成できると主張することは、非常に悪い間違いです。そして特にこの場合。人間は常にコンパイラよりもコードを改善することができ、この特定の状況はこの主張の良い例です。

表示されているタイミングの違いは、問題のアセンブリコードが内部ループで最適とはほど遠いためです。

(以下のコードは32ビットですが、64ビットに簡単に変換できます)

たとえば、シーケンス関数は5つの命令のみに最適化できます。

    .seq:
        inc     esi                 ; counter
        lea     edx, [3*eax+1]      ; edx = 3*n+1
        shr     eax, 1              ; eax = n/2
        cmovc   eax, edx            ; if CF eax = edx
        jnz     .seq                ; jmp if n<>1

コード全体は次のようになります。

include "%lib%/freshlib.inc"
@BinaryType console, compact
options.DebugMode = 1
include "%lib%/freshlib.asm"

start:
        InitializeAll
        mov ecx, 999999
        xor edi, edi        ; max
        xor ebx, ebx        ; max i

    .main_loop:

        xor     esi, esi
        mov     eax, ecx

    .seq:
        inc     esi                 ; counter
        lea     edx, [3*eax+1]      ; edx = 3*n+1
        shr     eax, 1              ; eax = n/2
        cmovc   eax, edx            ; if CF eax = edx
        jnz     .seq                ; jmp if n<>1

        cmp     edi, esi
        cmovb   edi, esi
        cmovb   ebx, ecx

        dec     ecx
        jnz     .main_loop

        OutputValue "Max sequence: ", edi, 10, -1
        OutputValue "Max index: ", ebx, 10, -1

        FinalizeAll
        stdcall TerminateAll, 0

このコードをコンパイルするには、FreshLibが必要です。

私のテスト(1 GHz AMD A4-1200プロセッサ)では、上記のコードは質問のC ++コードよりも約4倍高速であり(-O0430ミリ秒対1900ミリ秒でコンパイルした場合)、2倍以上高速です(430ミリ秒対830ミリ秒)C ++コードがでコンパイルされている場合-O3

両方のプログラムの出力は同じです。最大シーケンス= 525 on i = 837799。

26
gnasher729 2016-11-03 00:04.

パフォーマンスを向上させるために:単純な変更は、n = 3n + 1の後、nが偶数になることを観察しているため、すぐに2で割ることができます。また、nは1にならないため、テストする必要はありません。したがって、いくつかのifステートメントを保存して、次のように書くことができます。

while (n % 2 == 0) n /= 2;
if (n > 1) for (;;) {
    n = (3*n + 1) / 2;
    if (n % 2 == 0) {
        do n /= 2; while (n % 2 == 0);
        if (n == 1) break;
    }
}

ここだ大きな勝利は:あなたは、nの最下位8ビットを見れば、あなたまでのすべてのステップが完全にそれらの8ビットによって決定されている2 8倍で割りました。たとえば、最後の8ビットが0x01の場合、つまり2進数の場合、数値は???? 0000 0001の場合、次の手順は次のとおりです。

3n+1 -> ???? 0000 0100
/ 2  -> ???? ?000 0010
/ 2  -> ???? ??00 0001
3n+1 -> ???? ??00 0100
/ 2  -> ???? ???0 0010
/ 2  -> ???? ???? 0001
3n+1 -> ???? ???? 0100
/ 2  -> ???? ???? ?010
/ 2  -> ???? ???? ??01
3n+1 -> ???? ???? ??00
/ 2  -> ???? ???? ???0
/ 2  -> ???? ???? ????

したがって、これらすべてのステップを予測でき、256k +1が81k + 1に置き換えられます。すべての組み合わせで同様のことが起こります。したがって、大きなswitchステートメントでループを作成できます。

k = n / 256;
m = n % 256;

switch (m) {
    case 0: n = 1 * k + 0; break;
    case 1: n = 81 * k + 1; break; 
    case 2: n = 81 * k + 1; break; 
    ...
    case 155: n = 729 * k + 425; break;
    ...
}

n≤128になるまでループを実行します。その時点で、nは2で8分割未満で1になる可能性があり、一度に8ステップ以上を実行すると、初めて1に到達するポイントを見逃してしまいます。次に、「通常の」ループを続行します。または、1に到達するためにさらにいくつのステップが必要かを示すテーブルを用意します。

PS。PeterCordesの提案がそれをさらに速くするだろうと強く思う。1つを除いて条件分岐はまったくなく、ループが実際に終了する場合を除いて、その分岐は正しく予測されます。したがって、コードは次のようになります

static const unsigned int multipliers [256] = { ... }
static const unsigned int adders [256] = { ... }

while (n > 128) {
    size_t lastBits = n % 256;
    n = (n >> 8) * multipliers [lastBits] + adders [lastBits];
}

実際には、nの最後の9、10、11、12ビットを一度に処理する方が速いかどうかを測定します。各ビットについて、テーブル内のエントリの数は2倍になり、テーブルがL1キャッシュに収まらなくなると速度が低下すると予想されます。

PPS。演算の数が必要な場合:各反復で、正確に8分割を2で行い、(3n + 1)演算の数を可変にするため、演算をカウントするための明白な方法は別の配列になります。ただし、実際には(ループの反復回数に基づいて)ステップ数を計算できます。

問題を少し再定義することができます。奇数の場合はnを(3n + 1)/ 2に置き換え、偶数の場合はnをn / 2に置き換えます。その場合、すべての反復は正確に8ステップを実行しますが、不正行為と見なすことができます:-)したがって、r個の操作n <-3n +1とs個の操作n <-n / 2があったと仮定します。n <-3n +1はn <-3n *(1 + 1 / 3n)を意味するため、結果は正確にn '= n * 3 ^ r / 2 ^ sになります。対数を取ると、r =(s + log2(n '/ n))/ log2(3)が見つかります。

n≤1,000,000までループを実行し、任意の開始点n≤1,000,000から何回の反復が必要かを事前に計算したテーブルがある場合、上記のようにrを計算し、最も近い整数に丸めると、sが本当に大きくない限り、正しい結果が得られます。

20
hidefromkgb 2016-11-02 09:35.

あまり関係のないメモ:より多くのパフォーマンスハック!

  • [最初の«予想»はついに@ShreevatsaRによって暴かれた; 削除]

  • シーケンスをトラバースする場合、現在の要素の2つの近傍N(最初に表示)で3つの可能なケースしか取得できません。

    1. [偶数] [奇数]
    2. [奇数] [偶数]
    3. [偶数] [偶数]

    これらの2つの要素を過ぎて計算するための手段飛躍するために(N >> 1) + N + 1((N << 1) + N + 1) >> 1そしてN >> 2それぞれを、。

    (1)と(2)の両方の場合で、最初の式を使用できることを証明しましょう(N >> 1) + N + 1

    ケース(1)は明らかです。ケース(2)はを意味する(N & 1) == 1ので、(一般性を失うことなく)Nが2ビット長であり、そのビットが最ba上位から最下位までa = 1であると仮定すると、、、および次のようになります。

    (N << 1) + N + 1:     (N >> 1) + N + 1:
    
            b10                    b1
             b1                     b
           +  1                   + 1
           ----                   ---
           bBb0                   bBb
    

    ここでB = !b。最初の結果を右シフトすると、まさに私たちが望むものが得られます。

    QED :(N & 1) == 1 ⇒ (N >> 1) + N + 1 == ((N << 1) + N + 1) >> 1

    証明されているように、単一の3項演算を使用して、シーケンス2要素を一度にトラバースできます。さらに2倍の時間短縮。

結果のアルゴリズムは次のようになります。

uint64_t sequence(uint64_t size, uint64_t *path) {
    uint64_t n, i, c, maxi = 0, maxc = 0;

    for (n = i = (size - 1) | 1; i > 2; n = i -= 2) {
        c = 2;
        while ((n = ((n & 3)? (n >> 1) + n + 1 : (n >> 2))) > 2)
            c += 2;
        if (n == 2)
            c++;
        if (c > maxc) {
            maxi = i;
            maxc = c;
        }
    }
    *path = maxc;
    return maxi;
}

int main() {
    uint64_t maxi, maxc;

    maxi = sequence(1000000, &maxc);
    printf("%llu, %llu\n", maxi, maxc);
    return 0;
}

n > 2シーケンスの全長が奇数の場合、プロセスが1ではなく2で停止する可能性があるため、ここで比較します。

[編集:]

これをアセンブリに変換しましょう!

MOV RCX, 1000000;



DEC RCX;
AND RCX, -2;
XOR RAX, RAX;
MOV RBX, RAX;

@main:
  XOR RSI, RSI;
  LEA RDI, [RCX + 1];

  @loop:
    ADD RSI, 2;
    LEA RDX, [RDI + RDI*2 + 2];
    SHR RDX, 1;
    SHRD RDI, RDI, 2;    ror rdi,2   would do the same thing
    CMOVL RDI, RDX;      Note that SHRD leaves OF = undefined with count>1, and this doesn't work on all CPUs.
    CMOVS RDI, RDX;
    CMP RDI, 2;
  JA @loop;

  LEA RDX, [RSI + 1];
  CMOVE RSI, RDX;

  CMP RAX, RSI;
  CMOVB RAX, RSI;
  CMOVB RBX, RCX;

  SUB RCX, 2;
JA @main;



MOV RDI, RCX;
ADD RCX, 10;
PUSH RDI;
PUSH RCX;

@itoa:
  XOR RDX, RDX;
  DIV RCX;
  ADD RDX, '0';
  PUSH RDX;
  TEST RAX, RAX;
JNE @itoa;

  PUSH RCX;
  LEA RAX, [RBX + 1];
  TEST RBX, RBX;
  MOV RBX, RDI;
JNE @itoa;

POP RCX;
INC RDI;
MOV RDX, RDI;

@outp:
  MOV RSI, RSP;
  MOV RAX, RDI;
  SYSCALL;
  POP RAX;
  TEST RAX, RAX;
JNE @outp;

LEA RAX, [RDI + 59];
DEC RDI;
SYSCALL;

次のコマンドを使用してコンパイルします。

nasm -f elf64 file.asm
ld -o file file.o

GodboltのPeterCordesによるCおよびasmの改良/バグ修正バージョンを参照してください。(編集者注:私のものをあなたの答えに入れて申し訳ありませんが、私の答えはゴッドボルトのリンクとテキストから30k文字の制限に達しました!)

6
Mangu Singh Rajpurohit 2016-11-01 20:26.

C ++プログラムは、ソースコードからマシンコードを生成するときにアセンブリプログラムに変換されます。アセンブリがC ++よりも遅いと言うのは事実上間違っています。さらに、生成されるバイナリコードはコンパイラごとに異なります。したがって、スマートC ++コンパイラ、ダムアセンブラのコードよりも最適で効率的なバイナリコードを生成する可能性があります。

ただし、プロファイリング方法には特定の欠陥があると思います。以下は、プロファイリングの一般的なガイドラインです。

  1. システムが通常/アイドル状態にあることを確認してください。開始した、またはCPUを集中的に使用する(またはネットワーク経由でポーリングする)実行中のすべてのプロセス(アプリケーション)を停止します。
  2. データサイズはサイズを大きくする必要があります。
  3. テストは5〜10秒以上実行する必要があります。
  4. 1つのサンプルだけに依存しないでください。テストをN回実行します。結果を収集し、結果の平均または中央値を計算します。
6
Emanuel Landeholm 2016-11-06 08:49.

コラッツの問題の場合、「テール」をキャッシュすることでパフォーマンスを大幅に向上させることができます。これは時間とメモリのトレードオフです。参照:メモ化(https://en.wikipedia.org/wiki/Memoization)。また、他の時間とメモリのトレードオフについて、動的計画法ソリューションを調べることもできます。

Pythonの実装例:

import sys

inner_loop = 0

def collatz_sequence(N, cache):
    global inner_loop

    l = [ ]
    stop = False
    n = N

    tails = [ ]

    while not stop:
        inner_loop += 1
        tmp = n
        l.append(n)
        if n <= 1:
            stop = True  
        elif n in cache:
            stop = True
        elif n % 2:
            n = 3*n + 1
        else:
            n = n // 2
        tails.append((tmp, len(l)))

    for key, offset in tails:
        if not key in cache:
            cache[key] = l[offset:]

    return l

def gen_sequence(l, cache):
    for elem in l:
        yield elem
        if elem in cache:
            yield from gen_sequence(cache[elem], cache)
            raise StopIteration

if __name__ == "__main__":
    le_cache = {}

    for n in range(1, 4711, 5):
        l = collatz_sequence(n, le_cache)
        print("{}: {}".format(n, len(list(gen_sequence(l, le_cache)))))

    print("inner_loop = {}".format(inner_loop))
5
Ped7g 2016-11-02 07:18.

コメントから:

しかし、このコードは(整数オーバーフローのために)停止することはありません!?!イヴ・ドースト

多くの場合、オーバーフローすることはありません

それオーバーフローする場合-それらの不運な初期シードの1つについて、オーバーフローした数は、別のオーバーフローなしで1に向かって収束する可能性が非常に高くなります。

それでもこれは興味深い質問を提起します、オーバーフローサイクルシード数はありますか?

単純な最終収束級数は、2つの値の累乗で始まります(十分に明らかですか?)。

2 ^ 64はゼロにオーバーフローします。これは、アルゴリズムによると未定義の無限ループです(1でのみ終了します)が、shr raxZF = 1を生成するため、回答の最適なソリューションは終了します。

2 ^ 64を生成できますか?開始番号が0x5555555555555555、奇数の場合、次の番号は3n + 1、つまり0xFFFFFFFFFFFFFFFF + 1=0です。理論的にはアルゴリズムの未定義の状態ですが、johnfoundの最適化された回答は、ZF = 1で終了することで回復します。cmp rax,1ピーターコルドのは、無限ループに終了する(QEDバリアント1、不定介して「安っぽい」0番号)。

なしでサイクルを作成する、より複雑な数はどう0ですか?率直に言って、私にはわかりません。私の数学理論は、真剣な考え、真剣な方法でそれを処理する方法を得るにはあまりにも曖昧です。しかし、直感的には、3n + 1式は、遅かれ早かれ、元の数(または中間)のすべての非2素因数を2の累乗にゆっくりと変換するため、級数はすべての数に対して1に収束すると思います:0 <数。したがって、元のシリーズの無限ループについて心配する必要はありません。オーバーフローだけが妨げになります。

だから私はシートにいくつかの数字を入れて、8ビットの切り捨てられた数字を調べました。

にオーバーフローする3つの値があります0227170および8585に直接行き0、他の2つはに向かって進みます85)。

しかし、循環オーバーフローシードを作成する価値はありません。

おかしなことに、私はチェックを行いました。これは、8ビットの切り捨てに苦しむ最初の番号であり、すでに27影響を受けています。9232適切な切り捨てられていない級数で値に到達し(最初の切り捨てられた値は32212番目のステップにあります)、切り捨てられていない方法で2〜255の入力数値のいずれかで到達した最大値は、13120255それ自体の場合)最大ステップ数です。収束するの1は約です128(+ -2、「1」がカウントされるかどうかはわかりません...)。

興味深いことに(私にとって)その数9232は他の多くのソース番号で最大ですが、何が特別なのですか?:-O 9232= 0x2410...うーん..わからない。

残念ながら、私はなぜそれが収束し、それらを切り捨てる意味合い何ん、このシリーズのいずれかの深い理解を得ることができないk個のビットは、しかし、でcmp number,1終了条件、それは特定の入力値として終わると、無限ループにアルゴリズムを置くことは確かに可能だ0後切り捨て。

しかし、278ビットの場合の値のオーバーフローは一種の警告です。これは、値に到達するまでのステップ数を数えると、1整数のkビットセットの合計から大部分の数値に対して誤った結果が得られるように見えます。8ビット整数の場合、256個のうち146個の数値が切り捨てによって系列に影響を与えています(それらのいくつかは、誤って正しいステップ数に達する可能性があります。私は怠惰すぎて確認できません)。

5
Damon 2016-11-02 09:50.

コンパイラーによって生成されたコードを投稿しなかったので、ここに推測がありますが、それを見ていなくても、次のように言うことができます。

test rax, 1
jpe even

...ブランチを誤って予測する可能性が50%あり、それは高くつくでしょう。

コンパイラーはほぼ確実に両方の計算を実行し(div / modは非常に長いレイテンシーであるため、無視できるほどコストがかかるため、乗算加算は「無料」です)、CMOVでフォローアップします。もちろん、これは誤予測される可能性がゼロパーセントです。

5
Dmitry Rubanovich 2016-11-02 11:16.

アセンブリを見なくても、最も明白な理由は、多くのプロセッサが非常に迅速なシフト操作を行うため、/= 2おそらく最適化され>>=1ていることです。ただし、プロセッサにシフト演算がない場合でも、整数除算は浮動小数点除算よりも高速です。

編集: 上記の「整数除算は浮動小数点除算よりも高速です」というステートメントによって、マイレージが異なる場合があります。以下のコメントは、最新のプロセッサが整数除算よりもfp除算の最適化を優先していることを示しています。だから、誰かが、このスレッドの質問がについて尋ねる高速化のための最も可能性の高い理由は、コンパイラ最適化を探していた場合/=2など>>=1見た目に最高1位だろう。


無関係なノートならば、n奇数である、式はn*3+1常に偶数となります。したがって、確認する必要はありません。そのブランチをに変更できます

{
   n = (n*3+1) >> 1;
   count += 2;
}

したがって、ステートメント全体は次のようになります。

if (n & 1)
{
    n = (n*3 + 1) >> 1;
    count += 2;
}
else
{
    n >>= 1;
    ++count;
}
4
gnasher729 2016-11-05 07:15.

一般的な答えとして、このタスクに特に向けられていません。多くの場合、高レベルで改善を行うことにより、プログラムを大幅に高速化できます。データを複数回ではなく1回計算する、不要な作業を完全に回避する、キャッシュを最適な方法で使用するなどのように。これらのことは、高級言語で行うのがはるかに簡単です。

アセンブラコードを書くことで、最適化コンパイラの機能を改善することは可能ですが、それは大変な作業です。そして、それが完了すると、コードを変更するのがはるかに難しくなるため、アルゴリズムの改善を追加するのがはるかに困難になります。プロセッサには、高級言語では使用できない機能がある場合があります。インラインアセンブリは、このような場合に役立つことが多く、それでも高級言語を使用できます。

オイラーの問題では、ほとんどの場合、何かを構築する、遅い理由を見つける、より良いものを構築する、遅い理由を見つけるなどで成功します。アセンブラを使用するのは非常に困難です。可能な速度の半分でより良いアルゴリズムは通常、フルスピードでより悪いアルゴリズムを打ち負かし、アセンブラーでフルスピードを取得することは簡単ではありません。

Related questions

MORE COOL STUFF

「水曜日」シーズン1の中心には大きなミステリーがあります

「水曜日」シーズン1の中心には大きなミステリーがあります

Netflixの「水曜日」は、典型的な10代のドラマ以上のものであり、実際、シーズン1にはその中心に大きなミステリーがあります.

ボディーランゲージの専門家は、州訪問中にカミラ・パーカー・ボウルズが輝くことを可能にした微妙なケイト・ミドルトンの動きを指摘しています

ボディーランゲージの専門家は、州訪問中にカミラ・パーカー・ボウルズが輝くことを可能にした微妙なケイト・ミドルトンの動きを指摘しています

ケイト・ミドルトンは、州の夕食会と州の訪問中にカミラ・パーカー・ボウルズからスポットライトを奪いたくなかった、と専門家は言う.

一部のファンがハリー・スタイルズとオリビア・ワイルドの「非常に友好的な」休憩が永続的であることを望んでいる理由

一部のファンがハリー・スタイルズとオリビア・ワイルドの「非常に友好的な」休憩が永続的であることを望んでいる理由

一部のファンが、オリビア・ワイルドが彼女とハリー・スタイルズとの間の「難しい」が「非常に友好的」な分割を恒久的にすることを望んでいる理由を見つけてください.

エリザベス女王の死後、ケイト・ミドルトンはまだ「非常に困難な時期」を過ごしている、と王室の専門家が明らかにする 

エリザベス女王の死後、ケイト・ミドルトンはまだ「非常に困難な時期」を過ごしている、と王室の専門家が明らかにする&nbsp;

エリザベス女王の死後、ケイト・ミドルトンが舞台裏で「非常に困難な時期」を過ごしていたと伝えられている理由を調べてください.

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

引退した一郎:「私はただ死ぬと思う」

引退した一郎:「私はただ死ぬと思う」

写真:リッチシュルツ/ APマーリンズ外野手/野球のトゥルーヒットキング鈴木一郎は43歳ですが、近い将来、プロ野球をやめるつもりはありません。昨年、彼は143試合に出場し、ヒットしました。

12年後、有名なクラブペンギン氷山がついにヒント

12年後、有名なクラブペンギン氷山がついにヒント

約12年間の運用後、ディズニーの子供向けのMMOクラブペンギンは閉店しますが、プレーヤーがゲームで最も長く実行されているミームの1つを実現する機会を得る前ではありません。氷山がひっくり返った。

安い航空券はあなたが思っているほどお得ではありません

安い航空券はあなたが思っているほどお得ではありません

お気に入りのレストランが割引価格で食事を提供し始めたが、ナプキン、フォーク、または座席が必要な場合は追加料金を支払う必要があるとします。私たちのほとんどはおそらく彼らに私たちのビジネスを与えることを躊躇するでしょうが、その躊躇は航空運賃に変換されません。

注意してください、あなたが話す次の男はUFCファイターかもしれません

注意してください、あなたが話す次の男はUFCファイターかもしれません

マークハントはUFCで最もヘビーな打者かもしれません。彼はほぼ間違いなく、現在オーストラリアに住んでいる最もタフなファイターです。

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、子供向けのパズルの本の序文を書き、ジョージ王子、シャーロット王女、ルイ王子と一緒にテキストを読むと述べた.

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

Yak's Produce は、数十個のつぶれたメロンを野生動物のリハビリ専門家であるレスリー グリーンと彼女のルイジアナ州の救助施設で暮らす 42 匹の動物に寄付しました。

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

8 枚目のスタジオ アルバムのリリースに向けて準備を進めているデミ ロヴァートは、「スーパー グレート ガイ」と付き合っている、と情報筋は PEOPLE に確認しています。

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

イーサン プラスの誕生日のお祝いは、TLC のウェルカム トゥ プラスビルのシーズン 4 のフィナーレで、戦争中の母親のキム プラスと妻のオリビア プラスを結びつけました。

安全な公衆パニックルーム

安全な公衆パニックルーム

不気味な音に慣れて、コンクリートの周りをうろつきます。痛みや苦い口を吐き出し、「過ち」の不思議な病気を通してもう一度味わうことを切望します。

長い間行方不明だった 2 つのサンフランシスコ クリークが間もなく日の目を見る可能性がある

都市の水路を回復する理由はたくさんありますが、気候が変化するにつれて、それらはすべてより持続可能な未来につながります.

長い間行方不明だった 2 つのサンフランシスコ クリークが間もなく日の目を見る可能性がある

サンフランシスコの長い間失われた小川を復元する動きが高まっており、コミュニティを地域の生態系と結びつけ、また、都市が気候変動や季節的な洪水に適応するのに役立つ新しいタイプの「グリーン インフラストラクチャ」を作成しています。最新の取り組みは町の 2 つの非常に異なる場所で行われており、それらは明確ではあるが補完的な方法で展開されています。

サンフランシスコのベイエリアで家族写真が撮れる場所トップ 5

サンフランシスコのベイエリアで家族写真が撮れる場所トップ 5

ベイエリアには写真を撮るための美しい屋外スポットがたくさんあります。この記事のすべての写真は、ベイエリアにいるさまざまな PictureHum フォトグラファーとの PictureHum セッションからのものです。

退屈に耐えられないから生きていけない

退屈に耐えられないから生きていけない

それが現代の衝動です — より少ないもので世界を覆し、私たちのほんのわずかな瞬間を自分たちから盗もうとする. 私はかつてダイニングルームのソファで一日を過ごし、祖父母の農家に斜めに差し込む光を眺め、私には関係のない世界について話している大人のつぶやきを半分聞いたり、壁を通してくぐもったテレビを聞いたり、遊んだりしました。床と犬と私の小さな靴を暖めた太陽の黒点と。

Language