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 52 · Accepted Answer

让你的编译器弄清楚！

说真的，如果你真的关心这个级别的优化（除非它出现在配置文件中，否则你不应该关心），你应该习惯于查看编译器的汇编语言输出。您会惊讶于编译器代表您所做的事情。

所有推荐数学技巧的人要么有糟糕的编译器，要么低估了他们的编译器。例如，尝试编译这个函数：

unsigned long div1000000(unsigned long n) {
  return n / 1000000UL;
}

在 x86 (-O3, -fomit-frame-pointer) 上使用 gcc 4.3.3 编译，我得到：

$ objdump -d div.o -M intel

test2.o:     file format elf32-i386


Disassembly of section .text:

00000000 <div1000000>:
   0:   b8 83 de 1b 43          mov    eax,0x431bde83
   5:   f7 64 24 04             mul    DWORD PTR [esp+0x4]
   9:   c1 ea 12                shr    edx,0x12
   c:   89 d0                   mov    eax,edx
   e:   c3                      ret

换句话说，编译器n / 1000000UL将其转换为(unsigned long long)(n * 0x431bde83) >> (0x12 + 32). 为什么这行得通？在我的头顶上，我不知道！但是编译器认为它会比发出原生除法更快。

故事的道德启示：

除非您确定这是一个瓶颈，否则不要优化它。
不要做花哨的算术（乘以倒数、移位等），除非你已经知道你的编译器在做什么并且你认为你可以打败它。
对结果进行基准测试——如果你已经证明你已经超越了你的编译器，那么只留下一个像花哨的位数学这样的疣。

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/1,000,000。它应该更快。我的谷歌搜索说要加速分裂，乘以倒数。因此，如果有一组相对已知的可能值，我会预先计算倒数或倒数列表，然后相乘。

雅各布

score 3 · Accepted Answer

但是，我经常这样做，想知道它是否会成为瓶颈。

第一件事。如果您认为这将是一个瓶颈，请分析有问题的代码并确定。

如果（且仅当）这是您的瓶颈，那么请努力改进它。

现在，关于您的改进选项：

1.您可能不需要立即转换为毫秒。如果您只是收集数据，只需存储从返回的完整 64 位数字gethrtime()并完成它。人类需要阅读的任何内容都可以在以后进行后处理，或者以不那么激进的更新频率进行。

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在您的硬件上执行的最佳方法。大多数时候，这只是一两个时钟周期。

我使用UI32andUI64来表示 32 位和 64 位无符号数。

所有这些都需要更多的分析，以确保它实际上产生了可衡量的改进。

score 2 · Accepted Answer

正如Joshua Haberman 提到的，您的编译器可能已经将除以常数 1000000 转换为乘以“幻数”，然后是移位（如果除法是整数运算）。您可以在 Henry Warren 的“Hacker's Delight”一书和配套网站上获得更多详细信息：

http://www.hackersdelight.org/

他甚至有一个页面，里面有一个用于计算幻数的 Javascript 计算器：

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

score 2 · Accepted Answer

首先，明显的免责声明：除非您每秒至少执行几百万次除法，否则它不会成为瓶颈，您应该离开它。过早的优化等等。

其次，您需要的结果有多准确？在二进制和十进制之间转换的一个方便的经验法则是 2^10 ~= 10^3。

换句话说，一百万大约等于 2^20。所以你可以右移 20。当然，编译器不会自动为你做这件事，因为它会改变结果。但是，如果您愿意忍受轻微的准确性，并且除法实际上是一个真正的性能问题，那么这就是我的建议。

score 0 · Accepted Answer

可以将整数除法转换为一系列更简单的操作。Terje Mathisen 推广的通用方法在汇编语言中的优化子例程的第 136 页上进行了概述。如果您事先知道数据类型的宽度以及要除以的内容，这将引导您了解如何将其转变为一系列更简单的操作，理论上可能比必须处理的更通用的除法操作更快任何除数。如果您担心其中一些整数大小不同，仍然会有一些平台问题需要关注。

除非您实际上是用汇编语言对此进行编程，否则我敢打赌，您实际上会在 SPARC 划分实现过程中改进任何东西。也许如果您使用的是非常古老的 SPARC V7 处理器，从在硬件中实现分区之前开始，您可能会得到一些改进，但即便如此，我还是打赌内置分区会更快。

无论如何，我怀疑您已经在这里进行了一些过早的优化。在假定此部门对其运行时有任何重大影响之前，您应该从分析您拥有的应用程序开始，并且您应该类似地分析对部门的任何更改以证明它按预期工作。很容易获得您认为会执行得更快但实际上现在却没有的代码，因为 CPU 缓存之类的事情变得如此复杂。

score 0 · Accepted Answer

如果你能解决这个问题，这是我的解决方案。

使用整数而不是浮点数（它们更快）
通过向右移动位除以 1048576（这比浮点数上的任何东西都便宜）

并说服自己毫秒应该是base2而不是base10。;-)

score 0 · Accepted Answer

1/1000000 是 0.0000000000000000000 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

请注意，这是一个“定点”计算，您应该知道精度可能会丢失。

c++ - 纳秒到毫秒 - 快速除以 1000000

10 回答 10

Related

Reference