c++ - C++ で関数を呼び出す際のオーバーヘッドはどれくらいですか?

Question

多くの文献では、インライン関数を使用して「関数呼び出しのオーバーヘッドを回避する」ことが述べられています。しかし、私は定量化可能なデータを見たことがありません。関数呼び出しの実際のオーバーヘッド、つまり、関数をインライン化することによってどのようなパフォーマンスの向上が達成されるでしょうか?

score 48 · Accepted Answer

ほとんどのアーキテクチャでは、コストはレジスタのすべて (または一部、またはまったく) をスタックに保存すること、関数の引数をスタックにプッシュすること (またはそれらをレジスタに入れること)、スタックポインタをインクリメントすること、および変数の先頭にジャンプすることで構成されます。新しいコード。次に、関数が完了したら、スタックからレジスタを復元する必要があります。この Web ページには、さまざまな呼び出し規約に関係する内容が説明されています。

現在、ほとんどの C++ コンパイラは、関数をインライン化するのに十分なほどスマートです。inline キーワードは、コンパイラへの単なるヒントです。役立つと判断した翻訳単位全体にインライン展開を行う人もいます。

score 24 · Accepted Answer

単純なインクリメント関数に対して単純なベンチマークを作成しました。

株式会社：

typedef unsigned long ulong;
ulong inc(ulong x){
    return x+1;
}

main.c

#include <stdio.h>
#include <stdlib.h>

typedef unsigned long ulong;

#ifdef EXTERN 
ulong inc(ulong);
#else
static inline ulong inc(ulong x){
    return x+1;
}
#endif

int main(int argc, char** argv){
    if (argc < 1+1)
        return 1;
    ulong i, sum = 0, cnt;
    cnt = atoi(argv[1]);
    for(i=0;i<cnt;i++){
        sum+=inc(i);
    }
    printf("%lu\n", sum);
    return 0;
}

Intel(R) Core(TM) i5 CPU M 430 @ 2.27GHzで 10 億回繰り返して実行すると、次の結果が得られました。

インラインバージョンの場合は1.4 秒
定期リンク版は4.4秒

(最大 0.2 まで変動するように見えますが、適切な標準偏差を計算するのが面倒で、気にすることもありません)

これは、このコンピューターでの関数呼び出しのオーバーヘッドが約3 ナノ秒であることを示唆しています。

私が測定した最速は約 0.3ns だったので、非常に単純化すると、関数呼び出しのコストは約9 プリミティブ opsであることが示唆されます。

このオーバーヘッドは、PLT を介して呼び出される関数 (共有ライブラリ内の関数) の場合、呼び出しごとに約2ns増加します (合計呼び出し時間は約6nsです)。

score 12 · Accepted Answer

技術的な答えと実用的な答えがあります。実際の答えは、それが問題になることは決してないということです。非常にまれなケースでは、実際にプロファイルされたテストを通して知る唯一の方法です。

あなたの文献が参照している技術的な答えは、コンパイラの最適化のため、一般的には関係ありません。それでも興味がある場合は、Joshが詳しく説明しています。

「パーセンテージ」に関しては、関数自体のコストを知る必要があります。ゼロコスト操作と比較しているため、呼び出された関数のコスト以外にパーセンテージはありません。インライン化されたコードの場合、コストはかかりません。プロセッサは次の命令に移動するだけです。inling の欠点は、コードサイズが大きくなり、スタックの構築や破棄のコストとは異なる方法でコストが発生することです。

score 9 · Accepted Answer

あなたの質問は、「絶対的な真実」と呼べる答えのない質問の 1 つです。通常の関数呼び出しのオーバーヘッドは、次の 3 つの要因によって異なります。

CPU。x86、PPC、および ARM CPU のオーバーヘッドは大きく異なります。1 つのアーキテクチャにとどまる場合でも、Intel Pentium 4、Intel Core 2 Duo、および Intel Core i7 の間でオーバーヘッドもかなり異なります。キャッシュサイズ、キャッシュアルゴリズム、メモリアクセスパターン、コールオペコード自体の実際のハードウェア実装などの要因により、両方が同じクロック速度で実行されたとしても、Intel と AMD の CPU の間でオーバーヘッドが著しく異なる可能性があります。オーバーヘッドへの影響。
ABI (アプリケーションバイナリインターフェイス)。同じ CPU でも、関数呼び出しがパラメーターを渡す方法 (レジスタ経由、スタック経由、または両方の組み合わせ経由) と、スタックフレームの初期化とクリーンアップがどこでどのように行われるかを指定するさまざまな ABI が存在することがよくあります。これらすべてがオーバーヘッドに影響を与えます。異なるオペレーティングシステムは、同じ CPU に対して異なる ABI を使用する場合があります。たとえば、Linux、Windows、Solaris の 3 つすべてが、同じ CPU に対して異なる ABI を使用する場合があります。
コンパイラ。ABI に厳密に従うことは、アプリケーションがシステムライブラリの関数を呼び出したり、ユーザーライブラリが別のユーザーライブラリの関数を呼び出したりする場合など、独立したコードユニット間で関数が呼び出される場合にのみ重要です。関数が「プライベート」であり、特定のライブラリまたはバイナリの外部では表示されない限り、コンパイラは「チート」する可能性があります。ABI に厳密に従うのではなく、より高速な関数呼び出しにつながるショートカットを使用する場合があります。たとえば、スタックを使用する代わりにパラメーターをレジスターに渡したり、スタックフレームのセットアップとクリーンアップを本当に必要でなければ完全にスキップしたりする場合があります。

上記の 3 つの要因の特定の組み合わせ (GCC を使用する Linux 上の Intel Core i5 など) のオーバーヘッドを知りたい場合、この情報を取得する唯一の方法は、関数呼び出しを使用する実装と、関数呼び出しを使用する実装の違いをベンチマークすることです。コードを呼び出し元に直接コピーします。インラインステートメントは単なるヒントであり、常にインライン展開につながるとは限らないため、このようにして確実にインライン展開を強制します。

ただし、ここでの本当の問題は、正確なオーバーヘッドが本当に重要なのかということです。1 つ確かなことは、関数呼び出しには常にオーバーヘッドがあるということです。小さいかもしれないし、大きいかもしれないが、確かに存在する。また、パフォーマンスが重要なセクションで関数が十分に頻繁に呼び出される場合、それがどれほど小さくても、オーバーヘッドはある程度重要になります。極端にやり過ぎない限り、インライン化によってコードが遅くなることはめったにありません。ただし、コードが大きくなります。今日のコンパイラは、いつインライン化するか、いつインライン化しないかを自分で決めるのが得意なので、頭を悩ませる必要はほとんどありません。

個人的には、プロファイリングできる多かれ少なかれ使用可能な製品ができるまで、開発中のインライン化を完全に無視します。プロファイリングによって、特定の関数が非常に頻繁に呼び出され、アプリケーションのパフォーマンスが重要なセクション内でも呼び出されることがわかった場合にのみ、インライン展開を行います。この関数の「強制インライン化」を検討してください。

これまでのところ、私の答えは非常に一般的です。C++ と Objective-C に適用されるのと同じくらい C にも適用されます。結びの言葉として、特に C++ について一言言わせてください。仮想メソッドは二重間接関数呼び出しです。つまり、通常の関数呼び出しよりも関数呼び出しのオーバーヘッドが高く、インライン化することもできません。非仮想メソッドはコンパイラによってインライン化される場合とされない場合がありますが、インライン化されていない場合でも、仮想メソッドよりもはるかに高速であるため、メソッドをオーバーライドするかオーバーライドする予定がない限り、メソッドを仮想化しないでください。

score 8 · Accepted Answer

オーバーヘッドの量は、コンパイラ、CPUなどによって異なります。オーバーヘッドの割合は、インライン化するコードによって異なります。知る唯一の方法は、コードを取得して両方の方法でプロファイリングすることです。そのため、明確な答えはありません。

score 5 · Accepted Answer

関数呼び出しの (小さな) コストは、関数本体の (非常に小さな) コストに比べて重要であるため、非常に小さな関数のインライン化は理にかなっています。数行にわたるほとんどの関数では、これは大きなメリットではありません。

score 4 · Accepted Answer

インライン化された関数は呼び出し元の関数のサイズを大きくし、関数のサイズを大きくするとキャッシュに悪影響を与える可能性があることに注意してください。境界線にいる場合、インライン化されたコードの「あと 1 枚の薄いミント」がパフォーマンスに劇的な悪影響を与える可能性があります。

「関数呼び出しのコスト」について警告している文献を読んでいる場合は、最新のプロセッサを反映していない古い資料である可能性があることをお勧めします。組み込みの世界にいるのでない限り、C が「移植可能なアセンブリ言語」である時代は本質的に過ぎ去りました。過去 10 年間 (たとえば) のチップ設計者の創意工夫の多くは、あらゆる種類の低レベルの複雑さに費やされており、「当時」の仕組みとは根本的に異なる可能性があります。

score 2 · Accepted Answer

最新のCPUは非常に高速です（明らかに！）。呼び出しと引数の受け渡しに関連するほとんどすべての操作は、フルスピードの命令です（間接呼び出しは、ほとんどの場合、ループを介した最初の場合、わずかにコストがかかる可能性があります）。

関数呼び出しのオーバーヘッドは非常に小さいため、呼び出し関数が呼び出しオーバーヘッドを適切にすることができるのはループだけです。

したがって、今日、関数呼び出しのオーバーヘッドについて話す（そして測定する）とき、私たちは通常、一般的な部分式をループから引き上げることができないというオーバーヘッドについて話します。関数が呼び出されるたびに一連の（同一の）作業を実行する必要がある場合、コンパイラーはそれをループから「引き上げ」、インライン化されている場合は1回実行できます。インライン化されていない場合、コードはおそらく先に進んで作業を繰り返すだけです、とあなたはそれを言いました！

インライン化された関数は、呼び出しと引数のオーバーヘッドのためではなく、関数から引き上げることができる一般的な部分式のために、信じられないほど高速に見えます。

例：

Foo::result_type MakeMeFaster()
{
  Foo t = 0;
  for (auto i = 0; i < 1000; ++i)
    t += CheckOverhead(SomethingUnpredictible());
  return t.result();
}

Foo CheckOverhead(int i)
{
  auto n = CalculatePi_1000_digits();
  return i * n;
}

オプティマイザーは、この愚かさを見抜いて次のことを行うことができます。

Foo::result_type MakeMeFaster()
{
  Foo t;
  auto _hidden_optimizer_tmp = CalculatePi_1000_digits();
  for (auto i = 0; i < 1000; ++i)
    t += SomethingUnpredictible() * _hidden_optimizer_tmp;
  return t.result();
}

関数の大部分をループから実際に引き上げたため、呼び出しのオーバーヘッドが不可能に減少したようです（CalculatePi_1000_digits呼び出し）。コンパイラーは、CalculatePi_1000_digitsが常に同じ結果を返すことを証明できる必要がありますが、優れたオプティマイザーはそれを行うことができます。

score 2 · Accepted Answer

「レジスタシャドウイング」と呼ばれる優れた概念があり、スタック (メモリ) の代わりに (CPU 上の) レジスタを介して (最大 6 つまで) 値を渡すことができます。また、内部で使用される関数と変数によっては、コンパイラはフレーム管理コードが不要であると判断する場合があります!!

また、C++ コンパイラでさえ「末尾再帰の最適化」を行う場合があります。つまり、A() が B() を呼び出し、B() を呼び出した後、A が返されるだけで、コンパイラはスタックフレームを再利用します。

もちろん、これはすべて、プログラムが標準のセマンティクスに固執する場合にのみ実行できます (ポインターのエイリアシングと最適化への影響を参照してください)。

score 1 · Accepted Answer

ここにはいくつかの問題があります。

十分にスマートなコンパイラを使用している場合、インラインを指定していなくても、自動的にインライン展開が行われます。一方で、インライン化できないものもたくさんあります。
関数が仮想の場合、ターゲットが実行時に決定されるため、インライン化できないという代償を払うことになります。逆に、Java では、メソッドが final であることを示さない限り、この価格を支払うことになります。
コードがメモリ内でどのように構成されているかによっては、コードが別の場所にあるため、キャッシュミスやページミスでコストがかかる場合があります。これは、一部のアプリケーションに大きな影響を与える可能性があります。

score 1 · Accepted Answer

特に小さな (インライン化可能な) 関数やクラスでさえ、オーバーヘッドはほとんどありません。

次の例には、3 つの異なるテストがあり、それぞれ何度も実行され、時間を指定されています。結果は常に、単位時間の 1000 分の 2 のオーダーに等しくなります。

#include <boost/timer/timer.hpp>
#include <iostream>
#include <cmath>

double sum;
double a = 42, b = 53;

//#define ITERATIONS 1000000 // 1 million - for testing
//#define ITERATIONS 10000000000 // 10 billion ~ 10s per run
//#define WORK_UNIT sum += a + b
/* output
8.609619s wall, 8.611255s user + 0.000000s system = 8.611255s CPU(100.0%)
8.604478s wall, 8.611255s user + 0.000000s system = 8.611255s CPU(100.1%)
8.610679s wall, 8.595655s user + 0.000000s system = 8.595655s CPU(99.8%)
9.5e+011 9.5e+011 9.5e+011
*/

#define ITERATIONS 100000000 // 100 million ~ 10s per run
#define WORK_UNIT sum += std::sqrt(a*a + b*b + sum) + std::sin(sum) + std::cos(sum)
/* output
8.485689s wall, 8.486454s user + 0.000000s system = 8.486454s CPU (100.0%)
8.494153s wall, 8.486454s user + 0.000000s system = 8.486454s CPU (99.9%)
8.467291s wall, 8.470854s user + 0.000000s system = 8.470854s CPU (100.0%)
2.50001e+015 2.50001e+015 2.50001e+015
*/


// ------------------------------
double simple()
{
   sum = 0;
   boost::timer::auto_cpu_timer t;
   for (unsigned long long i = 0; i < ITERATIONS; i++)
   {
      WORK_UNIT;
   }
   return sum;
}

// ------------------------------
void call6()
{
   WORK_UNIT;
}
void call5(){ call6(); }
void call4(){ call5(); }
void call3(){ call4(); }
void call2(){ call3(); }
void call1(){ call2(); }

double calls()
{
   sum = 0;
   boost::timer::auto_cpu_timer t;

   for (unsigned long long i = 0; i < ITERATIONS; i++)
   {
      call1();
   }
   return sum;
}

// ------------------------------
class Obj3{
public:
   void runIt(){
      WORK_UNIT;
   }
};

class Obj2{
public:
   Obj2(){it = new Obj3();}
   ~Obj2(){delete it;}
   void runIt(){it->runIt();}
   Obj3* it;
};

class Obj1{
public:
   void runIt(){it.runIt();}
   Obj2 it;
};

double objects()
{
   sum = 0;
   Obj1 obj;

   boost::timer::auto_cpu_timer t;
   for (unsigned long long i = 0; i < ITERATIONS; i++)
   {
      obj.runIt();
   }
   return sum;
}
// ------------------------------


int main(int argc, char** argv)
{
   double ssum = 0;
   double csum = 0;
   double osum = 0;

   ssum = simple();
   csum = calls();
   osum = objects();

   std::cout << ssum << " " << csum << " " << osum << std::endl;
}

10,000,000 回の反復 (各タイプ: シンプル、6 つの関数呼び出し、3 つのオブジェクト呼び出し) を実行した場合の出力は、次の半複雑な作業ペイロードでした。

sum += std::sqrt(a*a + b*b + sum) + std::sin(sum) + std::cos(sum)

次のように：

8.485689s wall, 8.486454s user + 0.000000s system = 8.486454s CPU (100.0%)
8.494153s wall, 8.486454s user + 0.000000s system = 8.486454s CPU (99.9%)
8.467291s wall, 8.470854s user + 0.000000s system = 8.470854s CPU (100.0%)
2.50001e+015 2.50001e+015 2.50001e+015

の単純な作業ペイロードを使用する

sum += a + b

各ケースで数桁高速であることを除いて、同じ結果が得られます。

score 0 · Accepted Answer

コードをどのように構成するかによって、モジュールやライブラリなどの単位に分割することが重要になる場合があります。

外部リンケージでダイナミックライブラリ関数を使用すると、ほとんどの場合、フルスタックフレーム処理が必要になります。
そのため、比較操作が整数比較と同じくらい単純な場合、stdc ライブラリの qsort を使用すると、stl コードを使用するよりも 1 桁 (10 倍) 遅くなります。
モジュール間での関数ポインタの受け渡しも影響を受けます。
同じペナルティは、コードが別のモジュールで定義されている C++ の仮想関数やその他の関数の使用に影響を与える可能性が最も高いでしょう。
良いニュースは、プログラム全体の最適化により、静的ライブラリとモジュール間の依存関係の問題が解決される可能性があることです。

score 0 · Accepted Answer

番号もありませんが、よろしくお願いします。漠然としたオーバーヘッドのアイデアから始めてコードを最適化しようとする人をよく見かけますが、実際にはよくわかりません。

score 0 · Accepted Answer

新しい関数ごとに、新しいローカルスタックを作成する必要があります。ただし、これのオーバーヘッドは、非常に多数の反復にわたるループの反復ごとに関数を呼び出す場合にのみ顕著になります。

score 0 · Accepted Answer

ほとんどの関数では、C++ と C でそれらを呼び出すための追加のオーバーヘッドはありません (「this」ポインターをすべての関数への不要な引数としてカウントしない限り..何らかの形で関数に状態を渡す必要があります)...

仮想関数の場合、それらは間接的な追加レベルです (C でポインタを介して関数を呼び出すのと同等です)... しかし、実際には、今日のハードウェアではこれは些細なことです。

c++ - C++ で関数を呼び出す際のオーバーヘッドはどれくらいですか?

16 に答える 16

Related

Reference