c++ - ナノ秒からミリ秒 - 1000000 による高速除算

Question

出力を gethrtime からミリ秒に変換したいと考えています。

これを行う明白な方法は、1000000 で割ることです。しかし、私はこれをかなり頻繁に行っており、ボトルネックになるのではないかと考えています。

1000000 のような数値を扱うときに最適化された除算操作はありますか?

注: すべてのコードは移植可能でなければなりません。私は gcc を使用していますが、これは一般的に Sparc ハードウェア上にあります

以下のコードを使用したいくつかの簡単なテスト...それが正しいことを願っています。

#include <sys/time.h>
#include <iostream>

using namespace std;

const double NANOSECONDS_TO_MILLISECONDS = 1.0 / 1000000.0;

int main()
{
    hrtime_t start;
    hrtime_t tmp;
    hrtime_t fin;

    start = gethrtime();
    tmp = (hrtime_t)(start * NANOSECONDS_TO_MILLISECONDS);
    fin = gethrtime();

    cout << "Method 1"
    cout << "Original val: " << start << endl;
    cout << "Computed: " << tmp << endl;
    cout << "Time:" << fin - start << endl;

    start = gethrtime();
    tmp = (start / 1000000);
    fin = gethrtime();

    cout "Method 2"    
    cout << "Original val: " << start << endl;
    cout << "Computed: " << tmp << endl;
    cout << "Time:" << fin - start << endl;

    return 0;
}

出力例:

Original val: 3048161553965997
Computed: 3048161553
Time:82082
Original val: 3048161556359586
Computed: 3048161556
Time:31230

Original val: 3048239663018915
Computed: 3048239663
Time:79381
Original val: 3048239665393873
Computed: 3048239665
Time:31321

Original val: 3048249874282285
Computed: 3048249874
Time:81812
Original val: 3048249876664084
Computed: 3048249876
Time:34830

これが正しい場合、この場合、逆数による倍数は実際には遅くなります。おそらく、固定小数点演算ではなく浮動小数点演算を使用しているためです。私は整数除算に固執しますが、それでもほとんど時間がかかりません。

score 34 · Accepted Answer

除算は高価な操作ではありません。1000000 で割る操作が、アプリケーションの主要なボトルネックの近くにあるかどうかは非常に疑わしいです。浮動小数点プロセッサは、単一の操作を実行するよりも、思いつくあらゆる種類の「トリック」よりもはるかに高速です。

score 15 · Accepted Answer

まだ誰もこれを手に入れていないことに驚いています…</p>

除算は分数による乗算と同じです
2 の小数乗による乗算は高速です。ビットシフトのみです。
整数除算には切り捨てが含まれます
切り捨ては、わずかに小さい分数を乗算するようなものです (特定のポイントまでは、範囲に注意する必要があります)。

そう、

const uint64_t numerator = (1LL<<32)/1000000;

...

millionths = ( number * numerator ) >> 32;

すーぱーはやく！

score 3 · Accepted Answer

しかし、私はこれをかなり頻繁に行っており、それがボトルネックになるのではないかと考えています。

まず最初に。これがボトルネックになると思われる場合は、問題のコードをプロファイリングして確認してください。

これがボトルネックである場合 (およびその場合にのみ)、改善に取り組みます。

次に、改善オプションに進みます。

1.すぐにミリ秒に変換する必要はないかもしれません。単純にデータを収集する場合は、返された完全な 64 ビット数値を保存するだけgethrtime()で完了です。人間が読む必要があるものはすべて、後で後処理するか、あまり積極的な更新頻度で処理できません。

2.繰り返しイベントのタイミングを計っている場合は、2 つの呼び出しの差で除算を実行してみてください。ボトルネックが発生するほど頻繁に呼び出している場合、この差は非常に小さいはずです。gethrtime()

static hrtime_t oldtime;
hrtime_t newtime = gethrtime();
int milliseconds = fastDivByOneMillion((UI32)(newtime - oldtime));
oldtime = newtime;

3.fastDivByOneMillion()2 の累乗による乗算と除算として実装できます。

int fastDivByOneMillion(UI32 nanoseconds)
{
    return (int)((UI64)nanoseconds * 4295 >> 32);
}

ノート：

コンパイラは、ハードウェアで行う最善の方法を見つけ出すことができ>> 32ます。ほとんどの場合、これは 1 つか 2 つのクロックサイクルだけです。

UI32およびを使用しUI64て、32 ビットおよび 64 ビットの符号なし数値を表しました。

これらすべてが、実際に測定可能な改善を生み出していることを確認するために、さらにプロファイリングを行う必要があります。

score 3 · Accepted Answer

1/1,000,000 を掛けます。それはより速いはずです。私のGoogle検索は、除算をスピードアップし、逆数を掛けると言っていました。したがって、可能な値の比較的既知のセットがある場合は、逆数または逆数のリストを事前に計算してから乗算します。

ジェイコブ

score 2 · Accepted Answer

まず、明らかな免責事項：少なくとも1秒間に数百万回分割を実行しない限り、それはボトルネックにはならず、そのままにしておく必要があります。時期尚早の最適化とそのすべて。

次に、結果をどの程度正確にする必要がありますか？2進数と10進数の間で変換するための便利な経験則は、2 ^ 10〜= 10^3です。

つまり、100万は2^20にほぼ等しくなります。したがって、20を右にシフトすることができます。もちろん、結果が変わるため、コンパイラはこれを自動的に行いません。しかし、あなたがわずかな正確さで生きることをいとわず、分割が実際に実際のパフォーマンスの問題である場合、これは私の提案です。

score 2 · Accepted Answer

Joshua Haberman が述べたように、コンパイラはおそらく、定数 1000000 による除算を、「マジックナンバー」とそれに続くシフトによる乗算に変換します (除算が整数演算の場合)。Henry Warren の「Hacker's Delight」の本と関連 Web サイトで、何が起こっているかの詳細を確認できます。

http://www.hackersdelight.org/

彼は、マジックナンバー用の Javascript 電卓を含むページさえ持っています。

http://www.hackersdelight.org/magic.htm

score 0 · Accepted Answer

1/1000000 は 0.00000000000000000 0100 0011 0001 1011 1101 1110 1000 0010 1101 0111 1011 0110 0011 01 バイナリ - これは 0x431BDE82 * 2^-18 です

したがって、n/1000000 は (n*0x431BDE82)>>18 と同等です

また、n/1000000 は (n*0x8637BD04)>>19 と同等です

これは「固定小数点」計算であり、精度が失われる可能性があることに注意してください。

score 0 · Accepted Answer

整数除算を一連のより単純な演算に変換することができます。Terje Mathisen によって広められた一般的な方法は、 Optimizing subroutines in assembly languageの 136 ページに概説されています。データ型の幅と何を除算するかを事前に知っている場合は、それを、処理する必要があるより一般的な除算操作よりも理論的には高速である可能性がある、より単純な操作に変換する方法を説明します。任意の除数。それらのいくつかで異なるサイズの整数について心配している場合は、懸念すべきプラットフォームの問題がまだいくつかあります。

これを実際にアセンブリ言語でプログラミングしていない限り、SPARC 除算の実装よりもプロセスの改善を実際に行うことには反対です。割算がハードウェアに実装される前から、かなり古い SPARC V7 プロセッサを使用している場合は、多少の改善が得られるかもしれませんが、それでも組み込みの割算が高速であることに賭けます。

とにかく、ここで少し時期尚早の最適化を開始したのではないかと思います。この分割がランタイムに重大な影響を与えると推測する前に、取得したアプリのプロファイルを作成することから始めてください。同様に、分割への変更をプロファイルして、期待どおりに機能することを証明する必要があります。CPU キャッシュのようなものがいかに複雑になったかを考えると、実行速度が速いと思われるコードを取得するのは非常に簡単ですが、実際にはそうではありません。

score 0 · Accepted Answer

If you can get around with that, here's my solution.

use integers instead of floats (they are faster)
divide by 1048576 by shifting bits to the right (that is cheaper than anything on floats)

and convince yourself that milliseconds should be base2 and not base10. ;-)

c++ - ナノ秒からミリ秒 - 1000000 による高速除算

10 に答える 10

Related

Reference