纳秒到毫秒 - 快速除以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

如果这是正确的,那么在这种情况下,乘以倒数的倍数实际上更慢.这可能是由于使用浮点数学而不是定点数学.我会坚持整数除法然后几乎不需要任何时间.

Answer 1

让你的编译器搞清楚!

说真的,如果你真的关心这个级别的优化(除非它出现在配置文件中,否则你不应该这样做),你应该习惯于查看编译器的汇编语言输出.您会惊讶于编译器代表您做了什么.

推荐数学技巧的所有人都有糟糕的编译器,或者他们低估了他们的编译器.例如,尝试编译此函数:

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).为什么这样做？在我的头顶,我不知道!但编译器认为它比发布原生鸿沟要快.

故事的道德启示:

• 除非你确定它是一个瓶颈,否则不要对此进行优化.
• 除非你已经知道你的编译器在做什么并且你认为你可以击败它,否则不要做花式算术(乘以倒数,移位等).
• 对结果进行基准测试 - 如果你已经证明你已经超越了你的编译器,那么只留下像花哨的蠢货一样的疣.

Answer 2

分部不是一项昂贵的操作.我非常怀疑1000000除以后的操作是否会接近应用程序的主要瓶颈.浮点处理器比任何类型的"技巧"都快,而不仅仅是单一操作.

Answer 3

我很惊讶没有人得到这个......

• 除法乘以一个分数相同
• 乘以2的分数幂是快的:只是位移
• 整体分工涉及四舍五入
• 向下舍入就像乘以稍微小一部分(达到某一点,你需要知道你的范围)

所以,

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

...

millionths = ( number * numerator ) >> 32;

Supah快!