有没有一款C编译器不能编译这个代码?

22

我在分析器中挂了一段时间,试图找出如何加速常见日志解析器的瓶颈(即日期解析),并尝试了各种算法来提高速度。

对我而言,最快的尝试也是迄今为止最可读的,但可能是非标准的C代码。

这个方法在 GCCicc 和我非常老旧、挑剔的 SGI 编译器中都效果很好。因为这是一种很容易理解的优化方法,所以它有什么不符合我的要求呢?

static int parseMonth(const char *input) {
    int rv=-1;
    int inputInt=0;
    int i=0;

    for(i=0; i<4 && input[i]; i++) {
        inputInt = (inputInt << 8) | input[i];
    }

    switch(inputInt) {
        case 'Jan/': rv=0; break;
        case 'Feb/': rv=1; break;
        case 'Mar/': rv=2; break;
        case 'Apr/': rv=3; break;
        case 'May/': rv=4; break;
        case 'Jun/': rv=5; break;
        case 'Jul/': rv=6; break;
        case 'Aug/': rv=7; break;
        case 'Sep/': rv=8; break;
        case 'Oct/': rv=9; break;
        case 'Nov/': rv=10; break;
        case 'Dec/': rv=11; break;
    }
    return rv;
}

1
@JaredPar:我不认为VS是衡量可移植性的好标准。 - Robert Gamble
13个回答

23
Solaris 10 - SPARC - SUN编译器。
测试代码:
#include <stdio.h>

static int parseMonth(const char *input) {
    int rv=-1;
    int inputInt=0;
    int i=0;

    for(i=0; i<4 && input[i]; i++) {
        inputInt = (inputInt << 8) | input[i];
    }

    switch(inputInt) {
        case 'Jan/': rv=0; break;
        case 'Feb/': rv=1; break;
        case 'Mar/': rv=2; break;
        case 'Apr/': rv=3; break;
        case 'May/': rv=4; break;
        case 'Jun/': rv=5; break;
        case 'Jul/': rv=6; break;
        case 'Aug/': rv=7; break;
        case 'Sep/': rv=8; break;
        case 'Oct/': rv=9; break;
        case 'Nov/': rv=10; break;
        case 'Dec/': rv=11; break;
    }

    return rv;
}

static const struct
{
    char *data;
    int   result;
} test_case[] =
{
    { "Jan/", 0 },
    { "Feb/", 1 },
    { "Mar/", 2 },
    { "Apr/", 3 },
    { "May/", 4 },
    { "Jun/", 5 },
    { "Jul/", 6 },
    { "Aug/", 7 },
    { "Sep/", 8 },
    { "Oct/", 9 },
    { "Nov/", 10 },
    { "Dec/", 11 },
    { "aJ/n", -1 },
};

#define DIM(x) (sizeof(x)/sizeof(*(x)))

int main(void)
{
    size_t i;
    int    result;

    for (i = 0; i < DIM(test_case); i++)
    {
        result = parseMonth(test_case[i].data);
        if (result != test_case[i].result)
            printf("!! FAIL !! %s (got %d, wanted %d)\n",
                   test_case[i].data, result, test_case[i].result);
    }
    return(0);
}

结果(GCC 3.4.2 和 Sun):

$ gcc -O xx.c -o xx
xx.c:14:14: warning: multi-character character constant
xx.c:15:14: warning: multi-character character constant
xx.c:16:14: warning: multi-character character constant
xx.c:17:14: warning: multi-character character constant
xx.c:18:14: warning: multi-character character constant
xx.c:19:14: warning: multi-character character constant
xx.c:20:14: warning: multi-character character constant
xx.c:21:14: warning: multi-character character constant
xx.c:22:14: warning: multi-character character constant
xx.c:23:14: warning: multi-character character constant
xx.c:24:14: warning: multi-character character constant
xx.c:25:14: warning: multi-character character constant
$ ./xx
$ cc -o xx xx.c
$ ./xx
!! FAIL !! Jan/ (got -1, wanted 0)
!! FAIL !! Feb/ (got -1, wanted 1)
!! FAIL !! Mar/ (got -1, wanted 2)
!! FAIL !! Apr/ (got -1, wanted 3)
!! FAIL !! May/ (got -1, wanted 4)
!! FAIL !! Jun/ (got -1, wanted 5)
!! FAIL !! Jul/ (got -1, wanted 6)
!! FAIL !! Aug/ (got -1, wanted 7)
!! FAIL !! Sep/ (got -1, wanted 8)
!! FAIL !! Oct/ (got -1, wanted 9)
!! FAIL !! Nov/ (got -1, wanted 10)
!! FAIL !! Dec/ (got -1, wanted 11)
$

请注意,最后一个测试用例仍然通过了——也就是说,它生成了-1。
下面是parseMonth()的修订版,更加详细,可以在GCC和Sun C编译器下正常工作:
#include <stdio.h>

/* MONTH_CODE("Jan/") does not reduce to an integer constant */
#define MONTH_CODE(x)   ((((((x[0]<<8)|x[1])<<8)|x[2])<<8)|x[3])

#define MONTH_JAN       (((((('J'<<8)|'a')<<8)|'n')<<8)|'/')
#define MONTH_FEB       (((((('F'<<8)|'e')<<8)|'b')<<8)|'/')
#define MONTH_MAR       (((((('M'<<8)|'a')<<8)|'r')<<8)|'/')
#define MONTH_APR       (((((('A'<<8)|'p')<<8)|'r')<<8)|'/')
#define MONTH_MAY       (((((('M'<<8)|'a')<<8)|'y')<<8)|'/')
#define MONTH_JUN       (((((('J'<<8)|'u')<<8)|'n')<<8)|'/')
#define MONTH_JUL       (((((('J'<<8)|'u')<<8)|'l')<<8)|'/')
#define MONTH_AUG       (((((('A'<<8)|'u')<<8)|'g')<<8)|'/')
#define MONTH_SEP       (((((('S'<<8)|'e')<<8)|'p')<<8)|'/')
#define MONTH_OCT       (((((('O'<<8)|'c')<<8)|'t')<<8)|'/')
#define MONTH_NOV       (((((('N'<<8)|'o')<<8)|'v')<<8)|'/')
#define MONTH_DEC       (((((('D'<<8)|'e')<<8)|'c')<<8)|'/')

static int parseMonth(const char *input) {
    int rv=-1;
    int inputInt=0;
    int i=0;

    for(i=0; i<4 && input[i]; i++) {
        inputInt = (inputInt << 8) | input[i];
    }

    switch(inputInt) {
        case MONTH_JAN: rv=0; break;
        case MONTH_FEB: rv=1; break;
        case MONTH_MAR: rv=2; break;
        case MONTH_APR: rv=3; break;
        case MONTH_MAY: rv=4; break;
        case MONTH_JUN: rv=5; break;
        case MONTH_JUL: rv=6; break;
        case MONTH_AUG: rv=7; break;
        case MONTH_SEP: rv=8; break;
        case MONTH_OCT: rv=9; break;
        case MONTH_NOV: rv=10; break;
        case MONTH_DEC: rv=11; break;
    }

    return rv;
}

static const struct
{
    char *data;
    int   result;
} test_case[] =
{
    { "Jan/", 0 },
    { "Feb/", 1 },
    { "Mar/", 2 },
    { "Apr/", 3 },
    { "May/", 4 },
    { "Jun/", 5 },
    { "Jul/", 6 },
    { "Aug/", 7 },
    { "Sep/", 8 },
    { "Oct/", 9 },
    { "Nov/", 10 },
    { "Dec/", 11 },
    { "aJ/n", -1 },
    { "/naJ", -1 },
};

#define DIM(x) (sizeof(x)/sizeof(*(x)))

int main(void)
{
    size_t i;
    int    result;

    for (i = 0; i < DIM(test_case); i++)
    {
        result = parseMonth(test_case[i].data);
        if (result != test_case[i].result)
            printf("!! FAIL !! %s (got %d, wanted %d)\n",
                   test_case[i].data, result, test_case[i].result);
    }
    return(0);
}

我想使用MONTH_CODE()函数,但编译器没有配合。

3
SPARC 是大端序吗?如果是,翻转字符(或循环顺序)应该能解决问题。 - Mr Fooz
我非常好奇GCC和Sun C之间的差异。尽管这最多只是实现定义的行为,但通常情况下,GCC很好地模拟了本地编译器。我不认为这是一个错误——无论是在任何一个编译器中。这只是“实现特定”的行为,没有问题。 - Jonathan Leffler
1
我也尝试了“/naJ”,想得到-1,但是函数返回了0并且测试失败。因此,四字节单词的反向排序可以通过测试。但这几乎没有解决问题 - parseMonth()代码在不同平台上不可靠。 - Jonathan Leffler
@CesarB;是的,这应该可以——调用MONTH_CODE('J','a','n','/');硬编码'/'并将参数减少到三个可能很诱人。 - Jonathan Leffler
从技术上讲,Sun C编译器当然可以编译代码;只是它的工作方式与GCC或英特尔芯片下的工作方式不同。因此,这并不完全是对问题的准确回答。 :D - Jonathan Leffler
显示剩余5条评论

13
if ( !input[0] || !input[1] || !input[2] || input[3] != '/' )
    return -1;

switch ( input[0] )
{
    case 'F': return 1; // Feb
    case 'S': return 8; // Sep
    case 'O': return 9; // Oct
    case 'N': return 10; // Nov
    case 'D': return 11; // Dec;
    case 'A': return input[1] == 'p' ? 3 : 7; // Apr, Aug
    case 'M': return input[2] == 'r' ? 2 : 4; // Mar, May
    default: return input[1] == 'a' ? 0 : (input[2] == 'n' ? 5 : 6); // Jan, Jun, Jul
}

可读性稍低,验证程度不如前,但也许更快,对吧?


最后一行有错别字('a' ? 0 -- 而不是1),但是在我的机器上确实快了两倍多。在性能方面,你赢了。不过我想知道这里是否不够易读。 - Dustin
2
@Dustin,如果你添加注释来解释它,那么它就是可读的——不会影响运行速度,但会使下一个查看它的人能够像你一样轻松阅读。我建议将31天的月份列在前面,因为这会略微提高速度(从统计学角度来看)。 - paxdiablo
假设情况语句按照给定的顺序编译。 - paxdiablo
8
我不认为"Zax"应该被接受作为一月的代表,也不认为"Xxx"应该被接受作为七月的代表。 - Jonathan Leffler
1
就像我所说的 - 它没有验证。如果你想要验证,那么这些不是你要找的行。 - Vilx-
显示剩余2条评论

11

你只是计算这四个字符的哈希值。为什么不预定义一些整数常量以相同的方式计算哈希值并使用它们呢?同样易读,而且不会依赖于编译器特定的特性。

uint32_t MONTH_JAN = 'J' << 24 + 'a' << 16 + 'n' << 8 + '/';
uint32_t MONTH_FEB = 'F' << 24 + 'e' << 16 + 'b' << 8 + '/';

...

static uint32_t parseMonth(const char *input) {
    uint32_t rv=-1;
    uint32_t inputInt=0;
    int i=0;

    for(i=0; i<4 && input[i]; i++) {
        inputInt = (inputInt << 8) | (input[i] & 0x7f); // clear top bit
    }

    switch(inputInt) {
        case MONTH_JAN: rv=0; break;
        case MONTH_FEB: rv=1; break;

        ...
    }

    return rv;
}

我在审美上确实喜欢这个。我认为它看起来和我做的一样好看,但可以更加稳定地工作,而且不会出现偶尔的编译器警告。谢谢。 - Dustin
使用宏;#define MON_HASH(s) ((((s)[0]) & 0xff << 24) | (((s)[1]) & 0xff << 16) | (((s)[2]) & 0xff << 8) | (((s)[3]) & 0xff)) ... switch (MON_HASH(input)) { ... case MON_HASH("Jan/")注意,使用类似于gperf生成8位(或更短)哈希(Vilx-最接近gperf的操作)比上述的int“哈希”要高效得多(对int进行switch不会使用跳转表,而对char__int8进行switch可能会使用)。 - vladr

10

我只知道C标准(C99)中对此的规定:

包含多个字符(例如“ab”)或包含一个不能映射到单字节执行字符的字符或转义序列的整数字符常量的值是实现定义的。如果整数字符常量只包含一个字符或转义序列,则其值是将具有char类型且值为该单个字符或转义序列的对象转换为int类型时得到的值。

(摘自草案6.4.4.4/10)

因此,它是实现定义的。这意味着不能保证它在所有地方都能正常工作,但是实现必须记录其行为。例如,如果在特定实现中,int仅为16位宽度,则像'Jan/'这样的字符文本无法表示为您所期望的方式(char至少必须为8位,而字符文字始终为int类型)。


从理论上讲,这是错误的,我明白。我想知道是否有任何C编译器在实践中不起作用。这完全是出于好奇心,因为它在我身上起作用,即使在一个失败了一半的开源软件中也是如此。 - Dustin
1
@Dustin,请尝试为 PPC(非 Intel Mac OS X)编译。我认为那是大端序。 - strager
@strager 你知道吗...我在我的G3和SGI上都运行了这个程序(SGI是双向的,但是在big-endian下运行IRIX)。 - Dustin
@Dustin,我有一个旧的8051编译器,无法编译这个程序 - 它只支持16位整数,并且在处理“xxxx”常量时出错(也会在运行时出现移位或代码问题)。实际上,它也无法处理“xx”常量。 - paxdiablo
@Pax 很好,谢谢。我想我应该用32位编译器来限定它,但第二个失败是我正在寻找的错误类型的一半。 - Dustin
显示剩余2条评论

6
char *months = "Jan/Feb/Mar/Apr/May/Jun/Jul/Aug/Sep/Oct/Nov/Dec/";
char *p = strnstr(months, input, 4);
return p ? (p - months) / 4 : -1;

我也做了那个。它确实更小,但由于解析12月份的日期比1月份的日期要花费更长的时间,所以并不更快。我有一个可以适应输入是按时间顺序的干草堆的方法。更复杂,但并不真正更快。 - Dustin
这很令人惊讶,因为在大多数个人电脑上,strstr()应该编译成几乎单一的机器指令。 - Scott Evernden
@Dustin,我在我的五年老电脑上使用你的原始方法和Scott的方法进行了一些没有优化的基准测试。Scott在1.6秒内找到了Jan一千万次,在8.3秒内找到了Dec,而你的程序在2.6秒内找到了Jan和Dec。因此,虽然Scott的方法明显更清晰,但速度稍慢... - Robert Gamble
我的问题是:你到底在做什么,只有能够每秒调用这个函数一百万次才会成为瓶颈? - Robert Gamble
1
@Robert,"没有进行优化的基准测试" <-- 结果毫无意义。在进行基准测试时,请打开优化! - vladr
显示剩余2条评论

4

至少有3个因素使得该程序不可移植:

  1. 多字符常量是实现定义的,因此不同编译器可能处理它们的方式不同。
  2. 一个字节可以超过8位,有很多硬件的最小可寻址内存单元为16甚至32位,比如在 DSP 中经常会出现这种情况。如果一个字节超过8位,那么由于 char 的定义是一字节长,所以 char 也会超过8位;在这些系统上,您的程序将无法正常工作。
  3. 最后,有许多机器的 int 只有16位(这是 int 允许的最小尺寸),包括嵌入式设备和旧机器,您的程序在这些机器上也会失败。

我的64位处理器有32位整数,它可以正常工作。也许你的意思是少于? - strager
真的还是BYTE这个东西?据我所知,字节的定义是8位。 - JaredPar
@JaredPar:在C语言中,一个字节至少有8个位,但可能会更多。今天有很多系统(包括新系统!)的字节比8位更大。 - Robert Gamble
好的,你正在使用C定义(众所周知不明确)。我现在已经到了在我的代码中使用显式大小类型来防止其他人困惑的地步。例如:__int16、__int32等... - JaredPar
@strager:具体来说,Cray机器上的sizeof(char) == sizeof(short) == sizeof(int);我相信它们都是32位的量。 - Jonathan Leffler
显示剩余3条评论

4

National Instrument's CVI 8.5 for Windows编译器在您的原始代码上出现多个警告并失败:

  Warning: Excess characters in multibyte character literal ignored.

并且错误的形式为:

  Duplicate case label '77'.

它在Jonathan的代码上成功了。


2

我收到了警告,但没有错误(gcc)。似乎编译和操作都很正常。不过可能对大端系统无效!

虽然我不建议使用这种方法。也许你可以使用异或运算代替或移位运算,以创建一个单独的字节。然后在一个字节上使用case语句(或者更快地,在前N位上使用LUT)。


这实际上是一个完美哈希。对于这个应用程序来说并不太重要,但完美哈希的缺点是它可能会对错误输入返回错误的答案。 - Dustin
@Dustin,一旦你有了可能的答案,就可以使用strcmp进行检查。对此使用一个LUT即可。很容易。 - strager
我早期尝试的一个方法是编写一个程序,它以一组单词作为输入,并生成一个分层的 case 语句,在执行 strcmp 之前切换字母。例如:http://pastebin.com/f30e09462(可选择进一步拆分 Js)。 - Dustin
@Dustin,也许你可以将你的switch语句进一步分解成多个switch语句。这比调用memcmp函数要快。如果你不想那样做,你可以利用你已经知道第一个字符的事实,并且不需要进行比较。 - strager
@strager 我写了这个东西来为我构建它:http://github.com/dustin/snippets/tree/master/python/misc/gensearch.py - Dustin

1

一个四个字符的常量等同于一个特定的32位整数,这是一个非标准的特性,通常出现在MS Windows和Mac电脑(以及PalmOS,AFAICR)的编译器中。

在这些系统中,四个字符的字符串通常用作标识数据文件块或应用程序/数据类型标识符(例如“APPL”)的标签。

对于开发人员来说,这是一种方便,他们可以将这样的字符串存储到各种数据结构中,而不必担心零字节终止、指针等问题。


1

Comeau编译器

Comeau C/C++ 4.3.10.1 (Oct  6 2008 11:28:09) for ONLINE_EVALUATION_BETA2
Copyright 1988-2008 Comeau Computing.  All rights reserved.
MODE:strict errors C99 

"ComeauTest.c", line 11: warning: multicharacter character literal (potential
          portability problem)
          case 'Jan/': rv=0; break;
               ^

"ComeauTest.c", line 12: warning: multicharacter character literal (potential
          portability problem)
          case 'Feb/': rv=1; break;
               ^

"ComeauTest.c", line 13: warning: multicharacter character literal (potential
          portability problem)
          case 'Mar/': rv=2; break;
               ^

"ComeauTest.c", line 14: warning: multicharacter character literal (potential
          portability problem)
          case 'Apr/': rv=3; break;
               ^

"ComeauTest.c", line 15: warning: multicharacter character literal (potential
          portability problem)
          case 'May/': rv=4; break;
               ^

"ComeauTest.c", line 16: warning: multicharacter character literal (potential
          portability problem)
          case 'Jun/': rv=5; break;
               ^

"ComeauTest.c", line 17: warning: multicharacter character literal (potential
          portability problem)
          case 'Jul/': rv=6; break;
               ^

"ComeauTest.c", line 18: warning: multicharacter character literal (potential
          portability problem)
          case 'Aug/': rv=7; break;
               ^

"ComeauTest.c", line 19: warning: multicharacter character literal (potential
          portability problem)
          case 'Sep/': rv=8; break;
               ^

"ComeauTest.c", line 20: warning: multicharacter character literal (potential
          portability problem)
          case 'Oct/': rv=9; break;
               ^

"ComeauTest.c", line 21: warning: multicharacter character literal (potential
          portability problem)
          case 'Nov/': rv=10; break;
               ^

"ComeauTest.c", line 22: warning: multicharacter character literal (potential
          portability problem)
          case 'Dec/': rv=11; break;
               ^

"ComeauTest.c", line 1: warning: function "parseMonth" was declared but never
          referenced
  static int parseMonth(const char *input) {
             ^

感谢您提供编译器指针。我不担心编译器会抱怨潜在的可移植性问题,只担心编译器生成的代码行为不同。 - Dustin

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接