goto语句在这个C代码中是不可避免的吗？
Are goto statements inevitable in this C code?
如果不使用 goto 语句，我就无法编写代码。它们是不可避免的吗？
我写了这样一段代码：
sequence 是一个函数，它打印由 m 数字组成的所有序列，从 0 到 (n - 1) 和 returns 他们的数量。
它按我的预期工作，但我在其中使用了三个标签和三个 goto 语句。
我也写了 sequence_substitute 没有使用 goto 语句，但是当 n > 9 时它比 sequence 慢。
//this prints all sequences that consist of m numbers from 0 to (n - 1), and return the number of them.
//for example, if m = 2 and n = 3 then it prints "0 0 / 0 1 / 0 2 / 1 0 / 1 1 / 1 2 / 2 0 / 2 1 / 2 2 / " and return 9.
int sequence(int m, int n){
int i[100], j = 0, count = 0;
A:
if(!(j < m)){
for(int k = 0; k < m; ++k) printf("%d ", i[k]);
printf("/ ");
++count;
goto C;
}
i[j] = 0;
B:
if(i[j] < n){
++j;
goto A;
}
C:
--j;
if(j >= 0){
++i[j];
goto B;
}
putchar('\n');
return count;
}
int sequence_substitute(int m, int n){
int i[100], count = 0;
for(int j = 0; j < m; ++j) i[j] = 0;
for(;;){
int j = m - 1;
for(int k = 0; k < m; ++k) printf("%d ", i[k]);
printf("/ ");
++count;
for(;;){
if(i[j] < n - 1){
++i[j];
break;
}else{
if(j == 0){
putchar('\n');
return count;
}else{
i[j] = 0;
--j;
}
}
}
}
}
有什么方法可以不使用 goto 语句来编写与 sequence 一样快的函数吗？
我在下面的代码中对这两个函数进行了基准测试。
在此基准测试中，(m, n) = (6,15);
#include <stdio.h>
#include <stdlib.h>
double get_current_time();
int sequence(int m, int n);
int sequence_substitute(int m, int n);
double benchmark(int (*method)(int, int), int m, int n) {
double time1 = get_current_time();
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
double time2 = get_current_time();
return (time2 - time1) / 10;
}
int main(void) {
const int m = 6;
const int n = 15;
fprintf(stderr, "sequence: %f\n", benchmark(sequence, m, n));
fprintf(stderr, "sequence_substitute: %f\n",
benchmark(sequence_substitute, m, n));
return 0;
}
#if defined(WIN32) || defined(__WIN32) || defined(_WIN32) || \
defined(__WIN32__) || defined(_WIN32_)
#include <windows.h>
double get_current_time() {
LARGE_INTENGER t, f;
QueryPerformanceCounter(&t);
QueryPerformanceFrequency(&f);
return (double)t.QuadPart / (double)f.QuadPart;
}
#else
#include <sys/resource.h>
#include <sys/time.h>
double get_current_time() {
struct timeval t;
gettimeofday(&t, 0);
return t.tv_sec + t.tv_usec * 1e-6;
}
#endif
/**************************************************************************/
// this prints all sequences that consist of m numbers from 0 to (n - 1), and
// return the number of them. for example, if m = 2 and n = 3 then it prints "0
// 0 / 0 1 / 0 2 / 1 0 / 1 1 / 1 2 / 2 0 / 2 1 / 2 2 / " and return 9.
int sequence(int m, int n) {
int i[100], j = 0, count = 0;
A:
if (!(j < m)) {
for (int k = 0; k < m; ++k) printf("%d ", i[k]);
printf("/ ");
++count;
goto C;
}
i[j] = 0;
B:
if (i[j] < n) {
++j;
goto A;
}
C:
--j;
if (j >= 0) {
++i[j];
goto B;
}
putchar('\n');
return count;
}
int sequence_substitute(int m, int n) {
int i[100], count = 0;
for (int j = 0; j < m; ++j) i[j] = 0;
for (;;) {
int j = m - 1;
for (int k = 0; k < m; ++k) printf("%d ", i[k]);
printf("/ ");
++count;
for (;;) {
if (i[j] < n - 1) {
++i[j];
break;
} else {
if (j == 0) {
putchar('\n');
return count;
} else {
i[j] = 0;
--j;
}
}
}
}
}
https://gist.github.com/yuchiki/26fd96a2791f7f6d2d9929b404a16da6
结果如下：
当使用 -O3 编译时，
- 序列：5.390164[秒]
- sequence_substitute: 5.381983[秒]
并且在使用 -O0 编译时，
- 序列：5.178518[秒]
- sequence_substitute：5.256273[秒]
结果表明，即使没有任何优化，这两个函数计算结果的速度几乎相同。
也许，您在此处显示的代码过于模糊，无法重新生成您报告的速度差异。
为了更准确地讨论该现象，向我们展示以下信息可能会有用：
- 完整且准确的代码，包括 main、任何 pragma 或指令以及基准代码
- 基准测试结果
我在这两个函数的无IO版本上尝试了另一个基准测试，测试代码如下：
#include <stdio.h>
#include <stdlib.h>
double get_current_time();
int sequence(int m, int n);
int sequence_substitute(int m, int n);
double benchmark(int (*method)(int, int), int m, int n) {
double time1 = get_current_time();
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
double time2 = get_current_time();
return (time2 - time1) / 10;
}
int main(void) {
const int m = 7;
const int n = 15;
fprintf(stderr, "sequence: %f\n", benchmark(sequence, m, n));
fprintf(stderr, "sequence_substitute: %f\n",
benchmark(sequence_substitute, m, n));
return 0;
}
#if defined(WIN32) || defined(__WIN32) || defined(_WIN32) || \
defined(__WIN32__) || defined(_WIN32_)
#include <windows.h>
double get_current_time() {
LARGE_INTENGER t, f;
QueryPerformanceCounter(&t);
QueryPerformanceFrequency(&f);
return (double)t.QuadPart / (double)f.QuadPart;
}
#else
#include <sys/resource.h>
#include <sys/time.h>
double get_current_time() {
struct timeval t;
gettimeofday(&t, 0);
return t.tv_sec + t.tv_usec * 1e-6;
}
#endif
/**************************************************************************/
// this prints all sequences that consist of m numbers from 0 to (n - 1), and
// return the number of them. for example, if m = 2 and n = 3 then it prints "0
// 0 / 0 1 / 0 2 / 1 0 / 1 1 / 1 2 / 2 0 / 2 1 / 2 2 / " and return 9.
int sequence(int m, int n) {
int i[100], j = 0, count = 0;
A:
if (!(j < m)) {
for (int k = 0; k < m; ++k) {
} // printf("%d ", i[k]);
// printf("/ ");
++count;
goto C;
}
i[j] = 0;
B:
if (i[j] < n) {
++j;
goto A;
}
C:
--j;
if (j >= 0) {
++i[j];
goto B;
}
// putchar('\n');
return count;
}
int sequence_substitute(int m, int n) {
int i[100], count = 0;
for (int j = 0; j < m; ++j) i[j] = 0;
for (;;) {
int j = m - 1;
for (int k = 0; k < m; ++k) {
} // printf("%d ", i[k]);
// printf("/ ");
++count;
for (;;) {
if (i[j] < n - 1) {
++i[j];
break;
} else {
if (j == 0) {
// putchar('\n');
return count;
} else {
i[j] = 0;
--j;
}
}
}
}
}
结果如下：
当使用 -O3 编译时，
- 序列：0.019198[秒]
- sequence_substitute: 0.016234[秒]
当使用 -O0 编译时，
序列：0.136406[秒]
sequence_substitute: 0.112287[秒]
我不认为-O3版本的结果没有那么大的意义，因为可以猜测在这种情况下大部分代码被优化器删除了。但 -O0 版本表明以下事实：
- 这段代码最重的部分是IO。
- sequence_substitute 的逻辑部分也和 sequence.
的逻辑部分一样快
您关注的内容与现实世界无关。不，我不是在责备你；我只是指出你在担心一些无关紧要的事情。
最有效的实施是无效的实施。
在实践中，代码的可维护性比绝对最大性能更重要。我们每天都在学习更多关于计算机科学的知识，我们使用的硬件也在变化，所以今天绝对最优的不会是明天的。
足够好，轻松 modified/updated，更有价值。
当一个序列生成时，速度并不那么重要，因为你只运行它一次，并保存结果。
当你处理一个序列时，你经常无法存储和检索它们（因为要么宇宙中没有足够的物质，要么 I/O 太慢而不实用）。相反，您生成 序列 中的显式值。我的 This answer 针对一个相关问题——其中序列中的值具有唯一数字——展示了如何做到这一点。本质上，您使用从 0 开始的无符号整数 "index" 作为生成序列中值的种子。
然而，有时您只是在玩代码，或者可能正在制作它的游戏（例如堆栈溢出处的代码高尔夫）。或者，也许您有多个不同的实现来做完全相同的事情，并且您希望公平地比较它们。
那么，问题是microbenchmarking和benchmarking的区别。
我们当前的计算机非常复杂，因此在考虑 速度 或 效率 等概念时，完全不同的操作会严重影响彼此。最常见的机制是通过缓存。简单地说，如果你的超快函数使用了大量的缓存，它会减慢其他操作的速度（因为它们需要的数据不再被缓存，而必须从系统 RAM 中加载），这样函数的任务就是一部分的，是因为功能而整体变慢！
这意味着要进行适当的基准测试，对程序的性能进行适当的分析，我们需要使用真实世界的有效载荷。事实上，有几个不同的。并尝试形成每个实现如何执行的完整图片；当它们高效时，当它们缓慢且耗费资源时，等等。
一个常见问题是可扩展性。当有大量数据时，某些函数比其他函数更快，但当数据集较小时，反之亦然。这在排序函数中尤其常见。如果数据不多，有些排序函数会很慢；但当你有足够的数据时，它比任何其他功能都快。 （数字数据的基数排序是一个很好的例子：它确实在基本上线性的时间内进行排序，但是线性因子太大，以至于在基数排序比其他排序算法花费更少的时间之前，您需要具有数百万个条目的数组；基数排序也倾向于比其他算法更需要大量缓存。因此，尽管在某些方面它是 "superior"，但并不经常使用。）
我们在比较时使用术语 microbenchmark具有综合测试用例的功能，旨在提醒我们人类，由于上述原因，此类测试是 指示性的 ，并不完全可靠。
微基准测试本身就是一门正确的艺术。
特别是，仅对大量 运行 所花费的时间进行平均，并不能给出完整的图片。系统其他地方的不相关事件有时会减慢个体 运行s（微基准函数）；在最坏的情况下，您将这些视为带有视频播放、鼠标移动或动画的 "jitters"。由于此类事件以及其他测量误差源具有相似的特征，测得的时序具有不对称的误差条：测得的持续时间 "never" 太短，但通常又太高，因为时序涉及那些无关的事件。
缓存效应意味着如果您对存储在同一缓冲区中的数据调用相同的函数，第一次调用将比后续调用慢，因为它的时间将包括获取缓存所花费的时间 "hot" ;从 RAM 加载内容。
由于这些原因，我建议使用中位数或其他百分位数，而不是均值。
如果您考虑一下，您很少会对连续调用 1000 次可能需要多长时间感兴趣，因为在实际程序中您不会连续进行这些调用。但是，如果您知道每个函数调用花费的中位时间是 T，您就会知道在至少 50% 的微基准测试案例中，函数调用花费 T 或更短的时间。
还有在计算机上使用哪个时钟的问题。我们可以测量挂钟时间（POSIXy 系统中的 clock_gettime(CLOCK_MONOTONIC, ×pec)），或者仅测量该特定线程所用的 CPU 时间（clock_gettime(CLOCK_THREAD_CPUTIME_ID, ×pec)）。挂钟时间受同一台机器上其他所有因素 运行ning 的影响，但更符合人类对性能的期望； CPU 时间更适合不涉及大量数据的数学计算。 （我会说 CPU 时间对于 OP 想知道的功能来说更好。）
这个问题的最后一个问题是编译器优化。现在的编译器可以在机器代码级别进行令人惊讶的优化，具体取决于调用函数的上下文。对于真正的基准测试，这不是问题，但对于微基准测试，我们确实需要将功能隔离到单独的单元中，以便我们可以比较它们。
（当然，所有结果都是特定于每台机器的，并且根据编译器、编译器选项和使用的库而有所不同。仅仅因为微基准测试 X 在机器 A 上比在机器 B 上更快，并不意味着微基准测试Y 在 A 上也比在 B 上快。记住：指示性的，而不是证据或真正可靠的。）
既然我已经让你厌倦了这堵文字墙，我们可以看看实现一个真实世界的微基准测试来公平地比较这些序列生成器。
首先，I/O 部分将是瓶颈。我们把它扔掉。相反，我们使用本地缓冲区来保存字符串，每当完成新值时，我们都会调用回调函数。这样编译器就不能做任何真正糟糕的恶作剧，比如完全避免计算该值，因为它必须假设该值已被使用。
void sequence(int m, int n, void (*callback)(int index, char seq[]))
{
int index[m + 1];
char buffer[m + 1];
int count = 0;
int j = 0;
buffer[m] = '[=10=]';
A:
if (j >= m) {
callback(count, buffer);
++count;
goto C;
}
index[j] = 0;
B:
if (index[j] < n) {
++j;
goto A;
}
C:
--j;
if (j >= 0) {
++index[j];
goto B;
}
return;
}
我还将 i 数组重命名为 index。描述性名称效果更好。
假设我们将其放入 fiveseven.c。让我们也写一个小的 Makefile 来帮助我们编译这些东西：
CC := gcc
CFLAGS := -Wall -O2
LDFLAGS :=
LIBS := fiveseven.so
.PHONY: all clean
all: clean benchmark $(LIBS)
clean:
rm -f benchmark $(LIBS)
%.so: %.c
$(CC) $(CFLAGS) -fPIC -shared $^ -Wl,-soname,$@ $(LDFLAGS) -o $@
benchmark: benchmark.c
$(CC) $(CFLAGS) $^ $(LDFLAGS) -ldl -o $@
注意缩进使用Tabs，不是空格；但是这个论坛不允许那些粘贴代码的人。所以，如果你复制粘贴上面的内容，运行 sed -e 's|^ *|\t|' -i Makefile 来修复缩进。
这会编译实际的微基准程序，从 benchmark.c 到 ./benchmark，分别；以及要比较的一个或多个函数，放入动态加载的库中。这避免了编译器对代码进行任何令人惊讶的优化。
如果添加其他实现，只需将它们的库名称（在 Linux 上以 .so 结尾）添加到 LIBS 行。请注意，您还可以 运行 make CC=clang 或 make LIBS=foo.so clean all 等等，在构建时覆盖变量。
当然，我们需要基准程序本身。这是一种实现，benchmark.c:
#define _POSIX_C_SOURCE 200809L
// SPDX-License-Identifier: CC0-1.0
#include <stdlib.h>
#include <inttypes.h>
#include <dlfcn.h>
#include <stdio.h>
#include <time.h>
typedef void (sequence_fn)(int, int, void (*)(int, char []));
static int compare_int64(const void *ptr1, const void *ptr2)
{
const int64_t val1 = *(const uint64_t *)ptr1;
const int64_t val2 = *(const uint64_t *)ptr2;
return (val1 < val2) ? -1 :
(val1 > val2) ? +1 : 0;
}
static void nothing(int index, char value[])
{
return;
}
static double median_cpu_time(const size_t iterations,
const int length,
const int radix,
sequence_fn *sequence_function)
{
struct timespec started, stopped;
int64_t *nanosecs;
double result;
size_t i;
if (iterations < 1 || length < 1 || radix < 1 || !sequence_function)
return -1.0; /* Invalid parameters. */
nanosecs = malloc(iterations * sizeof nanosecs[0]);
if (!nanosecs)
return -1.0; /* Out of memory. */
for (i = 0; i < iterations; i++) {
clock_gettime(CLOCK_THREAD_CPUTIME_ID, &started);
sequence_function(length, radix, nothing);
clock_gettime(CLOCK_THREAD_CPUTIME_ID, &stopped);
nanosecs[i] = (int64_t)(stopped.tv_sec - started.tv_sec) * INT64_C(1000000000)
+ (int64_t)(stopped.tv_nsec - started.tv_nsec);
}
qsort(nanosecs, iterations, sizeof (int64_t), compare_int64);
result = (double)nanosecs[iterations / 2] / 1000000000.0;
free(nanosecs);
return result;
}
int main(int argc, char *argv[])
{
size_t iterations;
int arg, length, radix;
void *handle;
sequence_fn *func;
double seconds;
char dummy;
if (argc < 5) {
fprintf(stderr, "\n");
fprintf(stderr, "Usage: %s [ -h | --help | help ]\n", argv[0]);
fprintf(stderr, " %s LENGTH RADIX ITERATIONS ./library.so ...\n", argv[0]);
fprintf(stderr, "\n");
fprintf(stderr, "This program measures the median CPU time taken by\n");
fprintf(stderr, "each sequence(LENGTH, RADIX, callback) call\n");
fprintf(stderr, "over ITERATIONS iterations, as implemented in each\n");
fprintf(stderr, "listed dynamic library.\n");
fprintf(stderr, "\n");
return EXIT_FAILURE;
}
if (sscanf(argv[1], " %d %c", &length, &dummy) != 1 || length < 1) {
fprintf(stderr, "%s: Invalid length.\n", argv[1]);
return EXIT_FAILURE;
}
if (sscanf(argv[2], " %d %c", &radix, &dummy) != 1 || radix < 1) {
fprintf(stderr, "%s: Invalid radix.\n", argv[2]);
return EXIT_FAILURE;
}
if (sscanf(argv[3], " %zu %c", &iterations, &dummy) != 1 || iterations < 1) {
fprintf(stderr, "%s: Invalid number of iterations.\n", argv[3]);
return EXIT_FAILURE;
}
printf("Reporting median CPU time used over %zu iterations.\n", iterations);
printf("Length = %d, radix = %d.\n", length, radix);
fflush(stdout);
for (arg = 4; arg < argc; arg++) {
handle = dlopen(argv[arg], RTLD_NOW);
if (!handle) {
fprintf(stderr, "%s: %s.\n", argv[arg], dlerror());
continue;
}
func = dlsym(handle, "sequence");
if (!func) {
fprintf(stderr, "%s: Library does not implement sequence().\n", argv[arg]);
dlclose(handle);
continue;
}
printf(" %s: ", argv[arg]);
fflush(stdout);
seconds = median_cpu_time(iterations, length, radix, func);
printf("%.9f seconds median per call\n", seconds);
fflush(stdout);
dlclose(handle);
}
return EXIT_SUCCESS;
}
请注意，它提供了一个什么都不做的回调函数，而且大部分程序实际上只是提供命令行使用信息。这在实践中非常有用。我倾向于把每个 "project" 放到一个单独的 directory/folder 中。当我在寻找特定的东西时，我会执行 find + grep 或 grep -e pattern -R base-of-directories，然后检查可能的候选人。如果有可执行文件，我可以 运行 查看用法（我的总是有！）让我看到该特定目录的 用途 ；阅读数千行代码以尝试回想这是否是我要找的东西会更快、更轻松。
保存以上内容后，运行例如
make clean all
./benchmark 5 4 100000 ./fiveseven.so
查看每次调用 OP 的 sequence() 函数需要多少 CPU 时间，以秒为中位数，包括通过函数指针为每个值调用无操作函数的开销生成。
请注意，此微基准测试不会验证结果的正确性。这也是应该考虑的事情。
很像 yuchiki in their answer，我对代码进行了基准测试。我也想出了自己的解决方案。
我 运行 我在配备 2.9 GHz Intel Core i7、运行 macOS 10.14.2 Mojave 并使用 home-built GCC 的 MacBook Pro（15 英寸，2017 年）上进行的测试8.2.0，加上我的SOQ (Stack Overflow Questions) repository on GitHub as files timer.c and timer.h in the src/libsoqsub-directory中可用的时序码。我将 sequence 函数从问题重命名为 sequence_withgoto 以使其名称的长度与其他函数相似。我删除了（通过注释掉）序列生成器函数中的打印代码。我将计数器类型从 int 更改为 unsigned（尽管可以争辩说 could/should 是 unsigned long long 以提供更大的 运行ge）。下面显示的最大测试正好溢出了 32 位 unsigned 类型，给出了答案 0.
Comment-free测试代码（源文件seq23.c）：
#include <assert.h>
#include <stdio.h>
#include "timer.h"
static unsigned sequence_withgoto(int m, int n)
{
int i[100], j = 0;
unsigned count = 0;
A:
if (!(j < m))
{
++count;
goto C;
}
i[j] = 0;
B:
if (i[j] < n)
{
++j;
goto A;
}
C:
--j;
if (j >= 0)
{
++i[j];
goto B;
}
return count;
}
static unsigned sequence_substitute(int m, int n)
{
int i[100];
unsigned count = 0;
for (int j = 0; j < m; ++j)
i[j] = 0;
for ( ; ; )
{
int j = m - 1;
++count;
for ( ; ; )
{
if (i[j] < n - 1)
{
++i[j];
break;
}
else
{
if (j == 0)
{
return count;
}
else
{
i[j] = 0;
--j;
}
}
}
}
}
static unsigned generate_sequence(int m, int n)
{
assert(m <= n);
assert(m > 0);
assert(n < 20);
int data[m];
for (int i = 0; i < m; i++)
data[i] = 0;
unsigned counter = 0;
while (data[0] < n)
{
counter++;
for (int i = m - 1; i >= 0; i--)
{
if (++data[i] < n)
break;
if (i == 0)
break;
data[i] = 0;
}
}
return counter;
}
static void time_sequence_generator(const char *tag, int m, int n, unsigned (*function)(int m, int n))
{
Clock clk;
clk_init(&clk);
clk_start(&clk);
unsigned count = (*function)(m, n);
clk_stop(&clk);
char buffer[32];
printf("Number of sequences (m = %d, n = %d): %u elapsed = %s (%s)\n",
m, n, count, clk_elapsed_us(&clk, buffer, sizeof(buffer)), tag);
}
static void test_sequence_generators(int m, int n)
{
time_sequence_generator("generate_sequence", m, n, generate_sequence);
time_sequence_generator("sequence_withgoto", m, n, sequence_withgoto);
time_sequence_generator("sequence_substitute", m, n, sequence_substitute);
}
int main(void)
{
test_sequence_generators(2, 3);
test_sequence_generators(5, 9);
test_sequence_generators(4, 10);
test_sequence_generators(6, 15);
test_sequence_generators(7, 19);
test_sequence_generators(8, 16);
return 0;
}
编译命令行：
gcc -O3 -g -I./inc -std=c11 -Wall -Wextra -Werror seq23.c -o seq23 -L./lib -lsoq
headers安装在./inc，包含定时器代码的库在./lib（静态库libsoq.a）。
我得到的结果在多次运行中是惊人的和一致的：
Number of sequences (m = 2, n = 3): 9 elapsed = 0.000005 (generate_sequence)
Number of sequences (m = 2, n = 3): 9 elapsed = 0.000000 (sequence_withgoto)
Number of sequences (m = 2, n = 3): 9 elapsed = 0.000000 (sequence_substitute)
Number of sequences (m = 5, n = 9): 59049 elapsed = 0.000098 (generate_sequence)
Number of sequences (m = 5, n = 9): 59049 elapsed = 0.000119 (sequence_withgoto)
Number of sequences (m = 5, n = 9): 59049 elapsed = 0.000068 (sequence_substitute)
Number of sequences (m = 4, n = 10): 10000 elapsed = 0.000012 (generate_sequence)
Number of sequences (m = 4, n = 10): 10000 elapsed = 0.000015 (sequence_withgoto)
Number of sequences (m = 4, n = 10): 10000 elapsed = 0.000010 (sequence_substitute)
Number of sequences (m = 6, n = 15): 11390625 elapsed = 0.013260 (generate_sequence)
Number of sequences (m = 6, n = 15): 11390625 elapsed = 0.015959 (sequence_withgoto)
Number of sequences (m = 6, n = 15): 11390625 elapsed = 0.010123 (sequence_substitute)
Number of sequences (m = 7, n = 19): 893871739 elapsed = 1.064473 (generate_sequence)
Number of sequences (m = 7, n = 19): 893871739 elapsed = 1.206680 (sequence_withgoto)
Number of sequences (m = 7, n = 19): 893871739 elapsed = 0.758287 (sequence_substitute)
Number of sequences (m = 8, n = 16): 0 elapsed = 4.819932 (generate_sequence)
Number of sequences (m = 8, n = 16): 0 elapsed = 5.712081 (sequence_withgoto)
Number of sequences (m = 8, n = 16): 0 elapsed = 3.705033 (sequence_substitute)
(m = 8, n = 16)序列生成168 = 232个序列，也就是说unsigned计数器溢出到 0.
令我吃惊的是 sequence_withgoto() 是最慢的函数；我的 generate_sequence() 排在中间，但问题规模最小；问题中的 sequence_substitute() 最快，差距明显（大约是最后一个序列中使用 goto 的变体时间的 2/3）。
我实现的算法在注释文件中有描述：
/*
** Algorithm:
** Array data contains m values.
** The farthest right entry varies continuously; when it exceeds n-1, it
** is reset to 0. If the increment wraps back to 0, then the previous
** index is incremented (and if it wraps to zero, ...). The loop
** finishes when the zeroth index reaches n (wrapping is suppressed).
*/
总结
回答标题中的标题问题：
- 否；
goto 声明不是强制性的。
回答body中的速度问题：
- 使用
goto 的代码通常在 large-size 问题上并不快（如果在小问题上有任何性能优势，它不太可能足够重要）。
首先，计算结果数。这将是 numbers_of_results = pow(n, m)。例如。如果 m = 2 和 n = 3 那么将有 pow(3, 2) == 9 个结果。
一旦您知道有多少结果，您就可以使用它来为解决方案编制索引 space。例如：
numbers_of_results = pow(n, m);
for(index = 0; index < numbers_of_results; index++) {
}
索引只是一个 "base m" 数字，索引中的每个数字都确定一个数字。要从索引中提取单个数字，您可以使用 digit = (index / pow(m, digit_number) ) % m，但是当您一次提取所有数字时，可以避免使用 pow()。
例如：
unsigned int sequence(unsigned int m, unsigned int n) {
unsigned int numbers_of_results, index, temp, digit_number;
numbers_of_results = pow(n, m);
for(index = 0; index < numbers_of_results; index++) {
temp = index;
for(digit_number = 0; digit_number < n; digit_number++) {
digit = temp % m;
temp /= m;
printf("%d ", digit);
}
printf("/ ");
}
putchar('\n');
return numbers_of_results;
现在；考虑 "readability/maintainability vs. performance" 折衷方案和（如果您关心性能的话）您关心的 CPU/s。
对于某些 CPU（而非其他），最好将 pow() 替换为您自己的实现（专为整数设计）。对于某些 CPU（而不是其他），添加特殊情况版本可能是有益的（例如，对于 m 是 2 的幂的所有情况，除法和模数可以替换为 "shift by constant m" 和 "AND with constant m-1").对于某些 CPU（而不是其他 CPU），除法和模运算可能比分支预测错误的成本高很多，因此将 m 舍入到最接近的 2 的幂可能会提高性能（因此您可以使用其中一个"shift and AND" 特殊版本）但是 suppress/discarded 索引包含太大数字的情况。
如果不使用 goto 语句，我就无法编写代码。它们是不可避免的吗？
我写了这样一段代码：
sequence 是一个函数，它打印由 m 数字组成的所有序列，从 0 到 (n - 1) 和 returns 他们的数量。
它按我的预期工作，但我在其中使用了三个标签和三个 goto 语句。
我也写了 sequence_substitute 没有使用 goto 语句，但是当 n > 9 时它比 sequence 慢。
//this prints all sequences that consist of m numbers from 0 to (n - 1), and return the number of them.
//for example, if m = 2 and n = 3 then it prints "0 0 / 0 1 / 0 2 / 1 0 / 1 1 / 1 2 / 2 0 / 2 1 / 2 2 / " and return 9.
int sequence(int m, int n){
int i[100], j = 0, count = 0;
A:
if(!(j < m)){
for(int k = 0; k < m; ++k) printf("%d ", i[k]);
printf("/ ");
++count;
goto C;
}
i[j] = 0;
B:
if(i[j] < n){
++j;
goto A;
}
C:
--j;
if(j >= 0){
++i[j];
goto B;
}
putchar('\n');
return count;
}
int sequence_substitute(int m, int n){
int i[100], count = 0;
for(int j = 0; j < m; ++j) i[j] = 0;
for(;;){
int j = m - 1;
for(int k = 0; k < m; ++k) printf("%d ", i[k]);
printf("/ ");
++count;
for(;;){
if(i[j] < n - 1){
++i[j];
break;
}else{
if(j == 0){
putchar('\n');
return count;
}else{
i[j] = 0;
--j;
}
}
}
}
}
有什么方法可以不使用 goto 语句来编写与 sequence 一样快的函数吗？
我在下面的代码中对这两个函数进行了基准测试。
在此基准测试中，(m, n) = (6,15);
#include <stdio.h>
#include <stdlib.h>
double get_current_time();
int sequence(int m, int n);
int sequence_substitute(int m, int n);
double benchmark(int (*method)(int, int), int m, int n) {
double time1 = get_current_time();
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
double time2 = get_current_time();
return (time2 - time1) / 10;
}
int main(void) {
const int m = 6;
const int n = 15;
fprintf(stderr, "sequence: %f\n", benchmark(sequence, m, n));
fprintf(stderr, "sequence_substitute: %f\n",
benchmark(sequence_substitute, m, n));
return 0;
}
#if defined(WIN32) || defined(__WIN32) || defined(_WIN32) || \
defined(__WIN32__) || defined(_WIN32_)
#include <windows.h>
double get_current_time() {
LARGE_INTENGER t, f;
QueryPerformanceCounter(&t);
QueryPerformanceFrequency(&f);
return (double)t.QuadPart / (double)f.QuadPart;
}
#else
#include <sys/resource.h>
#include <sys/time.h>
double get_current_time() {
struct timeval t;
gettimeofday(&t, 0);
return t.tv_sec + t.tv_usec * 1e-6;
}
#endif
/**************************************************************************/
// this prints all sequences that consist of m numbers from 0 to (n - 1), and
// return the number of them. for example, if m = 2 and n = 3 then it prints "0
// 0 / 0 1 / 0 2 / 1 0 / 1 1 / 1 2 / 2 0 / 2 1 / 2 2 / " and return 9.
int sequence(int m, int n) {
int i[100], j = 0, count = 0;
A:
if (!(j < m)) {
for (int k = 0; k < m; ++k) printf("%d ", i[k]);
printf("/ ");
++count;
goto C;
}
i[j] = 0;
B:
if (i[j] < n) {
++j;
goto A;
}
C:
--j;
if (j >= 0) {
++i[j];
goto B;
}
putchar('\n');
return count;
}
int sequence_substitute(int m, int n) {
int i[100], count = 0;
for (int j = 0; j < m; ++j) i[j] = 0;
for (;;) {
int j = m - 1;
for (int k = 0; k < m; ++k) printf("%d ", i[k]);
printf("/ ");
++count;
for (;;) {
if (i[j] < n - 1) {
++i[j];
break;
} else {
if (j == 0) {
putchar('\n');
return count;
} else {
i[j] = 0;
--j;
}
}
}
}
}
https://gist.github.com/yuchiki/26fd96a2791f7f6d2d9929b404a16da6
结果如下：
当使用 -O3 编译时，
- 序列：5.390164[秒]
- sequence_substitute: 5.381983[秒]
并且在使用 -O0 编译时，
- 序列：5.178518[秒]
- sequence_substitute：5.256273[秒]
结果表明，即使没有任何优化，这两个函数计算结果的速度几乎相同。
也许，您在此处显示的代码过于模糊，无法重新生成您报告的速度差异。
为了更准确地讨论该现象，向我们展示以下信息可能会有用：
- 完整且准确的代码，包括 main、任何 pragma 或指令以及基准代码
- 基准测试结果
我在这两个函数的无IO版本上尝试了另一个基准测试，测试代码如下：
#include <stdio.h>
#include <stdlib.h>
double get_current_time();
int sequence(int m, int n);
int sequence_substitute(int m, int n);
double benchmark(int (*method)(int, int), int m, int n) {
double time1 = get_current_time();
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
method(m, n);
double time2 = get_current_time();
return (time2 - time1) / 10;
}
int main(void) {
const int m = 7;
const int n = 15;
fprintf(stderr, "sequence: %f\n", benchmark(sequence, m, n));
fprintf(stderr, "sequence_substitute: %f\n",
benchmark(sequence_substitute, m, n));
return 0;
}
#if defined(WIN32) || defined(__WIN32) || defined(_WIN32) || \
defined(__WIN32__) || defined(_WIN32_)
#include <windows.h>
double get_current_time() {
LARGE_INTENGER t, f;
QueryPerformanceCounter(&t);
QueryPerformanceFrequency(&f);
return (double)t.QuadPart / (double)f.QuadPart;
}
#else
#include <sys/resource.h>
#include <sys/time.h>
double get_current_time() {
struct timeval t;
gettimeofday(&t, 0);
return t.tv_sec + t.tv_usec * 1e-6;
}
#endif
/**************************************************************************/
// this prints all sequences that consist of m numbers from 0 to (n - 1), and
// return the number of them. for example, if m = 2 and n = 3 then it prints "0
// 0 / 0 1 / 0 2 / 1 0 / 1 1 / 1 2 / 2 0 / 2 1 / 2 2 / " and return 9.
int sequence(int m, int n) {
int i[100], j = 0, count = 0;
A:
if (!(j < m)) {
for (int k = 0; k < m; ++k) {
} // printf("%d ", i[k]);
// printf("/ ");
++count;
goto C;
}
i[j] = 0;
B:
if (i[j] < n) {
++j;
goto A;
}
C:
--j;
if (j >= 0) {
++i[j];
goto B;
}
// putchar('\n');
return count;
}
int sequence_substitute(int m, int n) {
int i[100], count = 0;
for (int j = 0; j < m; ++j) i[j] = 0;
for (;;) {
int j = m - 1;
for (int k = 0; k < m; ++k) {
} // printf("%d ", i[k]);
// printf("/ ");
++count;
for (;;) {
if (i[j] < n - 1) {
++i[j];
break;
} else {
if (j == 0) {
// putchar('\n');
return count;
} else {
i[j] = 0;
--j;
}
}
}
}
}
结果如下：
当使用 -O3 编译时，
- 序列：0.019198[秒]
- sequence_substitute: 0.016234[秒]
当使用 -O0 编译时，
序列：0.136406[秒] sequence_substitute: 0.112287[秒]
我不认为-O3版本的结果没有那么大的意义，因为可以猜测在这种情况下大部分代码被优化器删除了。但 -O0 版本表明以下事实：
- 这段代码最重的部分是IO。
- sequence_substitute 的逻辑部分也和 sequence. 的逻辑部分一样快
您关注的内容与现实世界无关。不，我不是在责备你；我只是指出你在担心一些无关紧要的事情。
最有效的实施是无效的实施。
在实践中，代码的可维护性比绝对最大性能更重要。我们每天都在学习更多关于计算机科学的知识，我们使用的硬件也在变化，所以今天绝对最优的不会是明天的。
足够好，轻松 modified/updated，更有价值。
当一个序列生成时，速度并不那么重要，因为你只运行它一次，并保存结果。
当你处理一个序列时，你经常无法存储和检索它们（因为要么宇宙中没有足够的物质，要么 I/O 太慢而不实用）。相反，您生成 序列 中的显式值。我的 This answer 针对一个相关问题——其中序列中的值具有唯一数字——展示了如何做到这一点。本质上，您使用从 0 开始的无符号整数 "index" 作为生成序列中值的种子。
然而，有时您只是在玩代码，或者可能正在制作它的游戏（例如堆栈溢出处的代码高尔夫）。或者，也许您有多个不同的实现来做完全相同的事情，并且您希望公平地比较它们。
那么，问题是microbenchmarking和benchmarking的区别。
我们当前的计算机非常复杂，因此在考虑 速度 或 效率 等概念时，完全不同的操作会严重影响彼此。最常见的机制是通过缓存。简单地说，如果你的超快函数使用了大量的缓存，它会减慢其他操作的速度（因为它们需要的数据不再被缓存，而必须从系统 RAM 中加载），这样函数的任务就是一部分的，是因为功能而整体变慢！
这意味着要进行适当的基准测试，对程序的性能进行适当的分析，我们需要使用真实世界的有效载荷。事实上，有几个不同的。并尝试形成每个实现如何执行的完整图片；当它们高效时，当它们缓慢且耗费资源时，等等。
一个常见问题是可扩展性。当有大量数据时，某些函数比其他函数更快，但当数据集较小时，反之亦然。这在排序函数中尤其常见。如果数据不多，有些排序函数会很慢；但当你有足够的数据时，它比任何其他功能都快。 （数字数据的基数排序是一个很好的例子：它确实在基本上线性的时间内进行排序，但是线性因子太大，以至于在基数排序比其他排序算法花费更少的时间之前，您需要具有数百万个条目的数组；基数排序也倾向于比其他算法更需要大量缓存。因此，尽管在某些方面它是 "superior"，但并不经常使用。）
我们在比较时使用术语 microbenchmark具有综合测试用例的功能，旨在提醒我们人类，由于上述原因，此类测试是 指示性的 ，并不完全可靠。
微基准测试本身就是一门正确的艺术。
特别是，仅对大量 运行 所花费的时间进行平均，并不能给出完整的图片。系统其他地方的不相关事件有时会减慢个体 运行s（微基准函数）；在最坏的情况下，您将这些视为带有视频播放、鼠标移动或动画的 "jitters"。由于此类事件以及其他测量误差源具有相似的特征，测得的时序具有不对称的误差条：测得的持续时间 "never" 太短，但通常又太高，因为时序涉及那些无关的事件。
缓存效应意味着如果您对存储在同一缓冲区中的数据调用相同的函数，第一次调用将比后续调用慢，因为它的时间将包括获取缓存所花费的时间 "hot" ;从 RAM 加载内容。
由于这些原因，我建议使用中位数或其他百分位数，而不是均值。
如果您考虑一下，您很少会对连续调用 1000 次可能需要多长时间感兴趣，因为在实际程序中您不会连续进行这些调用。但是，如果您知道每个函数调用花费的中位时间是 T，您就会知道在至少 50% 的微基准测试案例中，函数调用花费 T 或更短的时间。
还有在计算机上使用哪个时钟的问题。我们可以测量挂钟时间（POSIXy 系统中的 clock_gettime(CLOCK_MONOTONIC, ×pec)），或者仅测量该特定线程所用的 CPU 时间（clock_gettime(CLOCK_THREAD_CPUTIME_ID, ×pec)）。挂钟时间受同一台机器上其他所有因素 运行ning 的影响，但更符合人类对性能的期望； CPU 时间更适合不涉及大量数据的数学计算。 （我会说 CPU 时间对于 OP 想知道的功能来说更好。）
这个问题的最后一个问题是编译器优化。现在的编译器可以在机器代码级别进行令人惊讶的优化，具体取决于调用函数的上下文。对于真正的基准测试，这不是问题，但对于微基准测试，我们确实需要将功能隔离到单独的单元中，以便我们可以比较它们。
（当然，所有结果都是特定于每台机器的，并且根据编译器、编译器选项和使用的库而有所不同。仅仅因为微基准测试 X 在机器 A 上比在机器 B 上更快，并不意味着微基准测试Y 在 A 上也比在 B 上快。记住：指示性的，而不是证据或真正可靠的。）
既然我已经让你厌倦了这堵文字墙，我们可以看看实现一个真实世界的微基准测试来公平地比较这些序列生成器。
首先，I/O 部分将是瓶颈。我们把它扔掉。相反，我们使用本地缓冲区来保存字符串，每当完成新值时，我们都会调用回调函数。这样编译器就不能做任何真正糟糕的恶作剧，比如完全避免计算该值，因为它必须假设该值已被使用。
void sequence(int m, int n, void (*callback)(int index, char seq[]))
{
int index[m + 1];
char buffer[m + 1];
int count = 0;
int j = 0;
buffer[m] = '[=10=]';
A:
if (j >= m) {
callback(count, buffer);
++count;
goto C;
}
index[j] = 0;
B:
if (index[j] < n) {
++j;
goto A;
}
C:
--j;
if (j >= 0) {
++index[j];
goto B;
}
return;
}
我还将 i 数组重命名为 index。描述性名称效果更好。
假设我们将其放入 fiveseven.c。让我们也写一个小的 Makefile 来帮助我们编译这些东西：
CC := gcc
CFLAGS := -Wall -O2
LDFLAGS :=
LIBS := fiveseven.so
.PHONY: all clean
all: clean benchmark $(LIBS)
clean:
rm -f benchmark $(LIBS)
%.so: %.c
$(CC) $(CFLAGS) -fPIC -shared $^ -Wl,-soname,$@ $(LDFLAGS) -o $@
benchmark: benchmark.c
$(CC) $(CFLAGS) $^ $(LDFLAGS) -ldl -o $@
注意缩进使用Tabs，不是空格；但是这个论坛不允许那些粘贴代码的人。所以，如果你复制粘贴上面的内容，运行 sed -e 's|^ *|\t|' -i Makefile 来修复缩进。
这会编译实际的微基准程序，从 benchmark.c 到 ./benchmark，分别；以及要比较的一个或多个函数，放入动态加载的库中。这避免了编译器对代码进行任何令人惊讶的优化。
如果添加其他实现，只需将它们的库名称（在 Linux 上以 .so 结尾）添加到 LIBS 行。请注意，您还可以 运行 make CC=clang 或 make LIBS=foo.so clean all 等等，在构建时覆盖变量。
当然，我们需要基准程序本身。这是一种实现，benchmark.c:
#define _POSIX_C_SOURCE 200809L
// SPDX-License-Identifier: CC0-1.0
#include <stdlib.h>
#include <inttypes.h>
#include <dlfcn.h>
#include <stdio.h>
#include <time.h>
typedef void (sequence_fn)(int, int, void (*)(int, char []));
static int compare_int64(const void *ptr1, const void *ptr2)
{
const int64_t val1 = *(const uint64_t *)ptr1;
const int64_t val2 = *(const uint64_t *)ptr2;
return (val1 < val2) ? -1 :
(val1 > val2) ? +1 : 0;
}
static void nothing(int index, char value[])
{
return;
}
static double median_cpu_time(const size_t iterations,
const int length,
const int radix,
sequence_fn *sequence_function)
{
struct timespec started, stopped;
int64_t *nanosecs;
double result;
size_t i;
if (iterations < 1 || length < 1 || radix < 1 || !sequence_function)
return -1.0; /* Invalid parameters. */
nanosecs = malloc(iterations * sizeof nanosecs[0]);
if (!nanosecs)
return -1.0; /* Out of memory. */
for (i = 0; i < iterations; i++) {
clock_gettime(CLOCK_THREAD_CPUTIME_ID, &started);
sequence_function(length, radix, nothing);
clock_gettime(CLOCK_THREAD_CPUTIME_ID, &stopped);
nanosecs[i] = (int64_t)(stopped.tv_sec - started.tv_sec) * INT64_C(1000000000)
+ (int64_t)(stopped.tv_nsec - started.tv_nsec);
}
qsort(nanosecs, iterations, sizeof (int64_t), compare_int64);
result = (double)nanosecs[iterations / 2] / 1000000000.0;
free(nanosecs);
return result;
}
int main(int argc, char *argv[])
{
size_t iterations;
int arg, length, radix;
void *handle;
sequence_fn *func;
double seconds;
char dummy;
if (argc < 5) {
fprintf(stderr, "\n");
fprintf(stderr, "Usage: %s [ -h | --help | help ]\n", argv[0]);
fprintf(stderr, " %s LENGTH RADIX ITERATIONS ./library.so ...\n", argv[0]);
fprintf(stderr, "\n");
fprintf(stderr, "This program measures the median CPU time taken by\n");
fprintf(stderr, "each sequence(LENGTH, RADIX, callback) call\n");
fprintf(stderr, "over ITERATIONS iterations, as implemented in each\n");
fprintf(stderr, "listed dynamic library.\n");
fprintf(stderr, "\n");
return EXIT_FAILURE;
}
if (sscanf(argv[1], " %d %c", &length, &dummy) != 1 || length < 1) {
fprintf(stderr, "%s: Invalid length.\n", argv[1]);
return EXIT_FAILURE;
}
if (sscanf(argv[2], " %d %c", &radix, &dummy) != 1 || radix < 1) {
fprintf(stderr, "%s: Invalid radix.\n", argv[2]);
return EXIT_FAILURE;
}
if (sscanf(argv[3], " %zu %c", &iterations, &dummy) != 1 || iterations < 1) {
fprintf(stderr, "%s: Invalid number of iterations.\n", argv[3]);
return EXIT_FAILURE;
}
printf("Reporting median CPU time used over %zu iterations.\n", iterations);
printf("Length = %d, radix = %d.\n", length, radix);
fflush(stdout);
for (arg = 4; arg < argc; arg++) {
handle = dlopen(argv[arg], RTLD_NOW);
if (!handle) {
fprintf(stderr, "%s: %s.\n", argv[arg], dlerror());
continue;
}
func = dlsym(handle, "sequence");
if (!func) {
fprintf(stderr, "%s: Library does not implement sequence().\n", argv[arg]);
dlclose(handle);
continue;
}
printf(" %s: ", argv[arg]);
fflush(stdout);
seconds = median_cpu_time(iterations, length, radix, func);
printf("%.9f seconds median per call\n", seconds);
fflush(stdout);
dlclose(handle);
}
return EXIT_SUCCESS;
}
请注意，它提供了一个什么都不做的回调函数，而且大部分程序实际上只是提供命令行使用信息。这在实践中非常有用。我倾向于把每个 "project" 放到一个单独的 directory/folder 中。当我在寻找特定的东西时，我会执行 find + grep 或 grep -e pattern -R base-of-directories，然后检查可能的候选人。如果有可执行文件，我可以 运行 查看用法（我的总是有！）让我看到该特定目录的 用途 ；阅读数千行代码以尝试回想这是否是我要找的东西会更快、更轻松。
保存以上内容后，运行例如
make clean all
./benchmark 5 4 100000 ./fiveseven.so
查看每次调用 OP 的 sequence() 函数需要多少 CPU 时间，以秒为中位数，包括通过函数指针为每个值调用无操作函数的开销生成。
请注意，此微基准测试不会验证结果的正确性。这也是应该考虑的事情。
很像 yuchiki in their answer，我对代码进行了基准测试。我也想出了自己的解决方案。
我 运行 我在配备 2.9 GHz Intel Core i7、运行 macOS 10.14.2 Mojave 并使用 home-built GCC 的 MacBook Pro（15 英寸，2017 年）上进行的测试8.2.0，加上我的SOQ (Stack Overflow Questions) repository on GitHub as files timer.c and timer.h in the src/libsoqsub-directory中可用的时序码。我将 sequence 函数从问题重命名为 sequence_withgoto 以使其名称的长度与其他函数相似。我删除了（通过注释掉）序列生成器函数中的打印代码。我将计数器类型从 int 更改为 unsigned（尽管可以争辩说 could/should 是 unsigned long long 以提供更大的 运行ge）。下面显示的最大测试正好溢出了 32 位 unsigned 类型，给出了答案 0.
Comment-free测试代码（源文件seq23.c）：
#include <assert.h>
#include <stdio.h>
#include "timer.h"
static unsigned sequence_withgoto(int m, int n)
{
int i[100], j = 0;
unsigned count = 0;
A:
if (!(j < m))
{
++count;
goto C;
}
i[j] = 0;
B:
if (i[j] < n)
{
++j;
goto A;
}
C:
--j;
if (j >= 0)
{
++i[j];
goto B;
}
return count;
}
static unsigned sequence_substitute(int m, int n)
{
int i[100];
unsigned count = 0;
for (int j = 0; j < m; ++j)
i[j] = 0;
for ( ; ; )
{
int j = m - 1;
++count;
for ( ; ; )
{
if (i[j] < n - 1)
{
++i[j];
break;
}
else
{
if (j == 0)
{
return count;
}
else
{
i[j] = 0;
--j;
}
}
}
}
}
static unsigned generate_sequence(int m, int n)
{
assert(m <= n);
assert(m > 0);
assert(n < 20);
int data[m];
for (int i = 0; i < m; i++)
data[i] = 0;
unsigned counter = 0;
while (data[0] < n)
{
counter++;
for (int i = m - 1; i >= 0; i--)
{
if (++data[i] < n)
break;
if (i == 0)
break;
data[i] = 0;
}
}
return counter;
}
static void time_sequence_generator(const char *tag, int m, int n, unsigned (*function)(int m, int n))
{
Clock clk;
clk_init(&clk);
clk_start(&clk);
unsigned count = (*function)(m, n);
clk_stop(&clk);
char buffer[32];
printf("Number of sequences (m = %d, n = %d): %u elapsed = %s (%s)\n",
m, n, count, clk_elapsed_us(&clk, buffer, sizeof(buffer)), tag);
}
static void test_sequence_generators(int m, int n)
{
time_sequence_generator("generate_sequence", m, n, generate_sequence);
time_sequence_generator("sequence_withgoto", m, n, sequence_withgoto);
time_sequence_generator("sequence_substitute", m, n, sequence_substitute);
}
int main(void)
{
test_sequence_generators(2, 3);
test_sequence_generators(5, 9);
test_sequence_generators(4, 10);
test_sequence_generators(6, 15);
test_sequence_generators(7, 19);
test_sequence_generators(8, 16);
return 0;
}
编译命令行：
gcc -O3 -g -I./inc -std=c11 -Wall -Wextra -Werror seq23.c -o seq23 -L./lib -lsoq
headers安装在./inc，包含定时器代码的库在./lib（静态库libsoq.a）。
我得到的结果在多次运行中是惊人的和一致的：
Number of sequences (m = 2, n = 3): 9 elapsed = 0.000005 (generate_sequence)
Number of sequences (m = 2, n = 3): 9 elapsed = 0.000000 (sequence_withgoto)
Number of sequences (m = 2, n = 3): 9 elapsed = 0.000000 (sequence_substitute)
Number of sequences (m = 5, n = 9): 59049 elapsed = 0.000098 (generate_sequence)
Number of sequences (m = 5, n = 9): 59049 elapsed = 0.000119 (sequence_withgoto)
Number of sequences (m = 5, n = 9): 59049 elapsed = 0.000068 (sequence_substitute)
Number of sequences (m = 4, n = 10): 10000 elapsed = 0.000012 (generate_sequence)
Number of sequences (m = 4, n = 10): 10000 elapsed = 0.000015 (sequence_withgoto)
Number of sequences (m = 4, n = 10): 10000 elapsed = 0.000010 (sequence_substitute)
Number of sequences (m = 6, n = 15): 11390625 elapsed = 0.013260 (generate_sequence)
Number of sequences (m = 6, n = 15): 11390625 elapsed = 0.015959 (sequence_withgoto)
Number of sequences (m = 6, n = 15): 11390625 elapsed = 0.010123 (sequence_substitute)
Number of sequences (m = 7, n = 19): 893871739 elapsed = 1.064473 (generate_sequence)
Number of sequences (m = 7, n = 19): 893871739 elapsed = 1.206680 (sequence_withgoto)
Number of sequences (m = 7, n = 19): 893871739 elapsed = 0.758287 (sequence_substitute)
Number of sequences (m = 8, n = 16): 0 elapsed = 4.819932 (generate_sequence)
Number of sequences (m = 8, n = 16): 0 elapsed = 5.712081 (sequence_withgoto)
Number of sequences (m = 8, n = 16): 0 elapsed = 3.705033 (sequence_substitute)
(m = 8, n = 16)序列生成168 = 232个序列，也就是说unsigned计数器溢出到 0.
令我吃惊的是 sequence_withgoto() 是最慢的函数；我的 generate_sequence() 排在中间，但问题规模最小；问题中的 sequence_substitute() 最快，差距明显（大约是最后一个序列中使用 goto 的变体时间的 2/3）。
我实现的算法在注释文件中有描述：
/*
** Algorithm:
** Array data contains m values.
** The farthest right entry varies continuously; when it exceeds n-1, it
** is reset to 0. If the increment wraps back to 0, then the previous
** index is incremented (and if it wraps to zero, ...). The loop
** finishes when the zeroth index reaches n (wrapping is suppressed).
*/
总结
回答标题中的标题问题：
- 否；
goto声明不是强制性的。
回答body中的速度问题：
- 使用
goto的代码通常在 large-size 问题上并不快（如果在小问题上有任何性能优势，它不太可能足够重要）。
首先，计算结果数。这将是 numbers_of_results = pow(n, m)。例如。如果 m = 2 和 n = 3 那么将有 pow(3, 2) == 9 个结果。
一旦您知道有多少结果，您就可以使用它来为解决方案编制索引 space。例如：
numbers_of_results = pow(n, m);
for(index = 0; index < numbers_of_results; index++) {
}
索引只是一个 "base m" 数字，索引中的每个数字都确定一个数字。要从索引中提取单个数字，您可以使用 digit = (index / pow(m, digit_number) ) % m，但是当您一次提取所有数字时，可以避免使用 pow()。
例如：
unsigned int sequence(unsigned int m, unsigned int n) {
unsigned int numbers_of_results, index, temp, digit_number;
numbers_of_results = pow(n, m);
for(index = 0; index < numbers_of_results; index++) {
temp = index;
for(digit_number = 0; digit_number < n; digit_number++) {
digit = temp % m;
temp /= m;
printf("%d ", digit);
}
printf("/ ");
}
putchar('\n');
return numbers_of_results;
现在；考虑 "readability/maintainability vs. performance" 折衷方案和（如果您关心性能的话）您关心的 CPU/s。
对于某些 CPU（而非其他），最好将 pow() 替换为您自己的实现（专为整数设计）。对于某些 CPU（而不是其他），添加特殊情况版本可能是有益的（例如，对于 m 是 2 的幂的所有情况，除法和模数可以替换为 "shift by constant m" 和 "AND with constant m-1").对于某些 CPU（而不是其他 CPU），除法和模运算可能比分支预测错误的成本高很多，因此将 m 舍入到最接近的 2 的幂可能会提高性能（因此您可以使用其中一个"shift and AND" 特殊版本）但是 suppress/discarded 索引包含太大数字的情况。