11

C 标准对类型族非常不清楚uint_fast*_t。在 gcc-4.4.4 linux x86_64 系统上,类型uint_fast16_tuint_fast32_t都是 8 字节大小。但是,8 字节数字的乘法似乎比 4 字节数字的乘法要慢得多。下面的一段代码证明了这一点:

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

int
main ()
{
  uint_least16_t p, x;
  int count;

  p = 1;
  for (count = 100000; count != 0; --count)
    for (x = 1; x != 50000; ++x)
      p*= x;

  printf("%"PRIuLEAST16, p);
  return 0;
}

在程序上运行时间命令,我得到

real 0m7.606s
user 0m7.557s
sys  0m0.019s

如果我将类型更改为uint_fast16_t(和 printf 修饰符),则时间变为

real 0m12.609s
user 0m12.593s
sys  0m0.009s

uint_fast16_t那么,如果将 stdint.h 标头(以及 uint_fast32_t)定义为 4 字节类型,不是更好吗?

4

5 回答 5

5

(u)int_(fast/least)XX_t如果系统尚未定义这些类型,AFAIK 编译器只会定义它们自己的类型版本。这是因为在单个系统上的所有库/二进制文件中同样定义这些类型非常重要。否则,如果不同的编译器对这些类型的定义不同,则使用 CompilerA 构建的库可能与使用 CompilerBuint_fast32_t构建的二进制文件具有不同的类型,但该二进制文件仍可能链接到该库;没有正式的标准要求系统的所有可执行代码必须由相同的编译器构建(实际上在某些系统上,例如 Windows,代码由各种不同的编译器编译是相当普遍的)。如果现在这个二进制文件调用库的函数,事情就会崩溃!

所以问题是:真的是 GCC 在这里定义了 uint_fast16_t,还是实际上是 Linux(我指的是这里的内核)或者甚至是定义这些类型的标准 C Lib(在大多数情况下是 glibc)?因为如果 Linux 或 glibc 定义了这些,构建在该系统上的 GCC 除了采用这些已经建立的任何约定外别无选择。所有其他可变宽度类型也是如此:char, short, int, long, long long; 所有这些类型在C 标准中只有一个最小保证位宽(因为int它实际上是 16 位,所以在int32 位的平台上,它已经比标准要求的要大得多)。


除此之外,我实际上想知道您的 CPU/编译器/系统出了什么问题。在我的系统上,64 位乘法与 32 位乘法一样快。我修改了您的代码以测试 16、32 和 64 位:

#include <time.h>
#include <stdio.h>
#include <inttypes.h>

#define RUNS 100000

#define TEST(type)                                  \
    static type test ## type ()                     \
    {                                               \
        int count;                                  \
        type p, x;                                  \
                                                    \
        p = 1;                                      \
        for (count = RUNS; count != 0; count--) {   \
            for (x = 1; x != 50000; x++) {          \
                p *= x;                             \
            }                                       \
        }                                           \
        return p;                                   \
    }

TEST(uint16_t)
TEST(uint32_t)
TEST(uint64_t)

#define CLOCK_TO_SEC(clock) ((double)clockTime / CLOCKS_PER_SEC)

#define RUN_TEST(type)                             \
    {                                              \
        clock_t clockTime;                         \
        unsigned long long result;                 \
                                                   \
        clockTime = clock();                       \
        result = test ## type ();                  \
        clockTime = clock() - clockTime;           \
        printf("Test %s took %2.4f s. (%llu)\n",   \
            #type, CLOCK_TO_SEC(clockTime), result \
        );                                         \
    }

int main ()
{
    RUN_TEST(uint16_t)
    RUN_TEST(uint32_t)
    RUN_TEST(uint64_t)
    return 0;
}

使用未优化的代码(-O0),我得到:

Test uint16_t took 13.6286 s. (0)
Test uint32_t took 12.5881 s. (0)
Test uint64_t took 12.6006 s. (0)

使用优化代码(-O3),我得到:

Test uint16_t took 13.6385 s. (0)
Test uint32_t took 4.5455 s. (0)
Test uint64_t took 4.5382 s. (0)

第二个输出非常有趣。@R.. 在上面的评论中写道:

在 x86_64 上,32 位算术永远不应该比 64 位算术慢。

第二个输出表明对于 32/16 位算术不能说同样的事情。16 位算术在 32/64 位 CPU 上可能会明显变慢,即使我的 x86 CPU 本身可以执行 16 位算术;与其他一些 CPU 不同,例如 PPC,它只能执行 32 位运算。但是,这似乎只适用于我的 CPU 上的乘法,当更改代码以进行加法/减法/除法时,16 位和 32 位之间不再存在显着差异。

上面的结果来自 Intel Core i7 (2.66 GHz),但如果有人感兴趣,我也可以在 Intel Core 2 Duo(上一代 CPU)和 Motorola PowerPC G4 上运行这个基准测试。

于 2012-08-28T11:39:24.247 回答
3

运行时的实际性能是一个非常非常复杂的话题。有许多因素,包括 RAM 内存、硬盘、操作系统;以及许多特定于处理器的怪癖。但这会给你一个粗略的失败:

N_fastX_t

  • 为处理器有效计算大多数(加法和减法)操作的最佳大小。这是特定于硬件的,其中 32 位变量是本机的,并且比 16 位变量更快(因此使用)。(例如)
  • 由于它在缓存行命中方面不如 N_leastX 受益,因此应该主要在只需要尽可能快的单个变量时使用它。虽然不在大型阵列中(遗憾的是,在两者之间切换的最佳大小取决于平台)
  • 请注意,快速与最少有几个怪癖情况,主要是乘法和除法。那是特定于平台的。但是,如果大多数操作是加法/减法/或/和。通常可以安全地假设快就是快。(再次注意 CPU 缓存和其他怪癖)

N_leastX_t

  • 硬件允许的最小变量,即至少为 X 大小。(例如,某些平台无法分配低于 4 个字节的变量。事实上,您的大多数 BOOL 变量至少占用一个字节,而不是一个位)
  • 如果不存在硬件支持,可以通过 CPU 昂贵的软件仿真计算。
  • 由于单个操作的部分硬件支持(与快速相比),可能会导致性能下降。
  • 但是:由于它占用的变量空间更少,它可能会更频繁地访问缓存行。这在数组中更为突出。因此会更快(内存成本 > CPU 成本)有关更多详细信息,请参阅http://en.wikipedia.org/wiki/CPU_cache

乘法问题?

还要回答为什么较大的 fastX 变量在乘法中会变慢。是由于乘法的本质造成的。(与您在学校的想法相似)

http://en.wikipedia.org/wiki/Binary_multiplier

//Assuming 4bit int
   0011 (3 in decimal)
 x 0101 (5 in decimal)
 ======
   0011 ("0011 x 0001")
  0000- ("0011 x 0000")
 0011-- ("0011 x 0001")
0000--- ("0011 x 0000")
=======
   1111 (15 in decimal)

但是,重要的是要知道计算机是“逻辑白痴”。虽然对我们人类来说很明显跳过尾随零步骤。计算机仍然会解决它(它更便宜,然后有条件地检查然后无论如何都会解决它)。因此,这为相同值的较大大小变量创建了一个怪癖

   //Assuming 8bit int
      0000 0011 (3 in decimal)
    x 0000 0101 (5 in decimal)
    ===========
      0000 0011 ("0011 x 0001")
    0 0000 000- ("0011 x 0000")
   00 0000 11-- ("0011 x 0001")
  000 0000 0--- ("0011 x 0000")
 0000 0000 ---- (And the remainders of zeros)
 -------------- (Will all be worked out)
 ==============
      0000 1111 (15 in decimal)

虽然我没有在乘法过程中发送剩余的 0x0 加法。重要的是要注意计算机将“完成它们”。因此,较大的变量乘法自然会比较小的变量乘法花费更长的时间。(因此,尽可能避免乘法和除法总是好的)。

然而,第二个怪癖来了。它可能不适用于所有处理器。需要注意的是,所有 CPU 操作都以 CPU 周期计算。如上所示,在每个循环中执行数十个(或更多)这样的小加法操作。因此,由于各种优化和 CPU 特定的怪癖,8 位加法可能需要与 8 位乘法等相同的时间。

如果它与您有那么大的关系。去参考英特尔: http: //www.intel.com/content/www/us/en/processors/architectures-software-developer-manuals.html


额外提及 CPU 与 RAM

由于 CPU 已经达到摩尔定律,比您的 DDR3 RAM 快几倍。

这可能会导致花费更多时间从 ram 中查找变量然后 CPU“计算”它的情况。这在长指针链中最为突出。

因此,虽然大多数处理器上都存在 CPU 缓存以减少“RAM 查找”时间。它的用途仅限于特定情况(缓存行受益最大)。对于不适合的情况。请注意,RAM 查找时间 > CPU 处理时间(不包括乘法/除法/一些怪癖)

于 2013-05-15T06:37:40.287 回答
3

我认为这样的设计决策并不容易做出。这取决于许多因素。目前我不认为你的实验是结论性的,见下文。

首先,没有一个单一的概念来说明快速应该意味着什么。在这里你强调了乘法,这只是一个特殊的观点。

那么 x86_64 是一个架构而不是一个处理器。因此,对于该系列中的不同处理器,结果可能会大不相同。我不认为 gcc 的类型决定取决于针对给定处理器进行优化的特定命令行开关是明智的。

现在回到你的例子。我猜你也看过汇编代码?它是否使用 SSE 指令来实现您的代码?您是否打开了处理器特定选项,例如-march=native

编辑:我对您的测试程序进行了一些实验,如果我完全保持原样,我基本上可以重现您的测量结果。但是修改和玩弄它,我更不相信它是决定性的。

例如,如果我将内部循环也更改为向下,则汇编程序看起来与以前几乎相同(但使用递减和针对 0 的测试),但执行需要大约 50% 的时间。所以我猜这个时间很大程度上取决于你想要进行基准测试的指令的环境、管道停顿等等。您必须对性质非常不同的代码进行基准测试,其中指令在不同的上下文中发出,对齐问题和矢量化开始发挥作用,以决定fast typedefs 的适当类型是什么。

于 2010-11-07T07:44:43.083 回答
2

是的,我认为这只是一个错误。不幸的是,你不能在不破坏 ABI 的情况下修复这样的错误,但这可能并不重要,因为几乎没有人(当然也没有我知道的库函数)实际使用这些*int_fast*_t类型。

于 2010-11-07T03:03:00.197 回答
1

仅仅因为我对快速整数类型感到好奇,我对现实生活中的解析器进行了基准测试,该解析器在语义部分使用整数类型来索引数组和 C++ 容器。它执行混合操作而不是简单的循环,并且大多数程序不依赖于所选的整数类型。实际上,对于我的特定数据,任何整数类型都可以。所以所有版本都产生了相同的输出。

在装配级别有 8 个案例:4 个用于大小,2 个用于签名。24 个 ISO C 类型名称必须映射到 8 个基本类型。正如 Jens 已经说过的,“好的”映射必须考虑特定的处理器和特定的代码。因此,在实践中,即使编译器编写者应该知道生成的代码,我们也不应该期望完美的结果。

该示例的多次运行被平均化,因此运行时间的波动范围仅为最小给定数字的 2 左右。对于这个特定的设置,结果是:

  • int16_t/uint16_tint64_t/之间没有运行时差异uint64_t
  • int8_t对于/uint8_tint32_t/来说,未签名的版本要快得多uint32_t
  • 未签名版本总是比签名版本小(文本和数据段)。

编译器:g++ 4.9.1,选项:-O3 mtune=generic -march=x86-64

CPU:Intel™ Core™ 2 Duo E8400 @ 3.00GHz

映射

| |整数| |
|标志|尺寸| 类型 |
| |[位] | |
|:--:|------:|:------------------------------------------------ --------------------------------:|
| 你| 8 | uint8_t uint_fast8_t uint_least8_t |
| 小号 | 8 | int8_t int_fast8_t int_least8_t |
| 你| 16 | uint16_t uint_least16_t |
| 小号 | 16 | int16_t int_least16_t |
| 你| 32 | uint32_t uint_least32_t |
| 小号 | 32 | int32_t int_least32_t |
| 你| 64 | uint64_t uint_fast16_t uint_fast32_t uint_fast64_t uint_least64_t |
| 小号 | 64 | int64_t int_fast16_t int_fast32_t int_fast64_t int_least64_t |

尺寸和时间

| | 整数 | | | | |
| 登录 | 尺寸 | 正文 | 数据 | bss | 时间 |
| | [位] | [字节] |[字节]|[字节]| [毫秒] |
|:----:|--------:|--------:| -----:|--------:|--------:|
| 你| 8 | 1285801 | 3024 | 5704 | 407.61 |
| 小号 | 8 | 1285929 | 3032 | 5704 | 412.39 |
| 你| 16 | 1285833 | 3024 | 5704 | 408.81 |
| 小号 | 16 | 1286105 | 3040 | 5704 | 408.80 |
| 你| 32 | 1285609 | 3024 | 5704 | 406.78 |
| 小号 | 32 | 1285921 | 3032 | 5704 | 413.30 |
| 你| 64 | 1285557 | 3032 | 5704 | 410.12 |
| 小号 | 64 | 1285824 | 3048 | 5704 | 410.13 |
于 2015-02-05T21:03:31.727 回答