如何改进这些案例转换功能?

宏至少有两个主要问题。想想如果我叫他们中的一个

a_z('a' + 1);

由于运算符优先,调用将不会给出正确的结果。这很容易用括号固定:

#define a_z(c) ((c) >= 'a' && (c) <= 'z')

但也可以这样称呼:

a_z(i++);

i

据我所知,在大小写之间转换的最快方法是使用查找表。当然,这是用内存换取速度-选择你的偏好知道你的特定平台:-)

char toUpper[128]; // we care only about standard ASCII
for (int i = 0; i < 128; i++)
  toUpper[i] = i;
toUpper['a'] = 'A';
...
toUpper['z'] = 'Z';

而且转换很简单:

char toUpperCase(char c)
{
  return toUpper[c];
}

char 给定平台上的值(或将其收缩为仅合法值并进行参数检查),但为了便于说明,将这样做。)

*c += (*c-'A'<26U)<<5; /* lowercase */
*c -= (*c-'a'<26U)<<5; /* uppercase */
*c ^= ((*c|32U)-'a'<26)<<5; /* toggle case */

因为您的目标是嵌入式系统,所以您应该学习如何消除不必要的代码膨胀、分支等。确定ascii字符是否按字母顺序排列的条件是4个比较/分支操作;我的条件是1。我建议查找一些关于算术和位操作技巧的好资源。

注:我更改了 *32 操作到 <<5 *32个 可能会更好地说明你的意图。

关于我的代码有太多隐式编译器生成操作的指控,我认为这是完全错误的。下面是任何半正派编译器都应该为第一行生成的伪asm:

1. *c 零或符号扩展它来填充 int char 已签名或未签名)。
2. sub 指示。
4. 否则,在 .

步骤2和3可以在使用比较跳转操作而不是标志的体系结构上组合。我能看到的唯一一个明显的幕后代价是如果机器不能直接寻址字符,或者如果它使用了讨厌的(符号/大小或一个补码)符号值表示,在这种情况下,转换为无符号将是非常重要的。据我所知,没有现代的嵌入式架构有这些问题;它们大多与传统的大型机(以及较小程度上的dsp)隔离。

如果有人担心糟糕的编译器实际上为 << ,您可以尝试:

if (*c-'A'<26U) *c+=32;

而不是我的代码。无论如何,这可能更干净,但我通常喜欢避免语句,这样我就可以将代码推入循环条件或类似宏的函数中。

编辑2: 根据请求,第一行的无分支版本:

*c += (64U-*c & *c-91U)>>(CHAR_BIT*sizeof(unsigned)-5);

*c += (64U-*c & *c-91U) >> CHAR_BIT*sizeof(unsigned)-1 << 5;

为了让它可靠地工作, c 应该有类型 unsigned char * 和 unsigned int 应该比 unsigned char .

注意:问题标题已编辑-原始标题是关于优化的” 请批判——一个最优函数

如果你真的在寻找最快的方法,那么从长远来看,无分支版本将是最好的方法,因为它可以使用SIMD。此外,它还避免了使用表(如果内存实在太小,嵌入式系统中的表可能太大)。

这是一个简单的非SIMD分支自由的例子,ToLower是一个很小的改变。

char BranchFree_AsciiToUpper(char inchar) 
{ 
        // Branch-Free / No-Lookup 
        // toupper() for ASCII-only 
        const int ConvertVal = 'A' - 'a'; 
        // Bits to Shift Arithmetic to Right : 9 == (char-bits + 1) 
        const int AsrBits = 9; 

        int c=(int)inchar; 
        //if( (('a'-1)<c) && (c<('z'+1)) ) { c += 'A'-'a'; } 
        int LowerBound = ('a'-1) - c; 
        int UpperBound = c - ('z' + 1); 
        int BranchFreeMask = (LowerBound & UpperBound)>>AsrBits;
        c = c + (BranchFreeMask & ConvertVal); 
        return((char)c); 
}

为了清晰起见,我的函数进行了扩展,并使用了非硬编码常量。您可以用硬编码值在一行中执行相同的操作,但我喜欢可读的代码;不过,这里是我的算法的“压缩”版本。再快不过了 这个 同样的东西“压缩”成一行 .

c+=(((96-(int)c)&((int)c-123))>>9)&(-32);

一旦你有了可操作的分支树版本, 你可以用SIMD 或位旋转SWAR(寄存器内的SIMD)技术 一次转换4-16字节

SWAR/SIMD操作还可以从较少的内存读/写操作中获益,并且确实发生的写操作可以对齐。这在具有加载命中存储惩罚的处理器(如PS3单元处理器)上要快得多。结合这一点,在展开的版本中进行简单的预取,可以避免几乎完全的内存暂停。

我知道我的示例中似乎有很多代码,但是 分支 (隐式或显式)并且没有因此而导致分支预测失误。如果您所处的平台具有严重的分支预测失误惩罚(这对于许多流水线嵌入式处理器都是如此),那么即使没有SIMD,您优化的 上面的代码应该比看起来简单得多但却创建隐式分支的代码运行得更快 .

即使没有SIMD/SWAR,智能编译器也有可能展开和交错上述实现,以隐藏延迟并产生非常快的版本,特别是在现代超标量处理器上,它可以在每个周期发出多个非依赖指令。对于任何分支版本,这通常都是不可能的。

// Unrolled inner loop where 'char *c' is the string we're converting
char c0=c[0],c1=c[1],c2=c[2],c3=c[3];  // Grouped-Loads
c[0]=BranchFree_AsciiToUpper(c0);
c[1]=BranchFree_AsciiToUpper(c1);
c[2]=BranchFree_AsciiToUpper(c2);
c[3]=BranchFree_AsciiToUpper(c3);
c+=4;

一个好的编译器应该能够内联ToUpper并完全交错上述代码,因为它们之间没有分支,没有内存别名,也没有依赖于代码的指令。为了好玩,我决定编译这个 一种针对PowerPC的编译器,它为双问题超标量核心生成了完美的交织,这种交织很容易胜过任何有分支的代码 .

mr               r31,r3
mr               r13,r13
lbz              r11,0(r31)
lbz              r10,1(r31)
extsb            r11,r11
lbz              r9,2(r31)
extsb            r10,r10
lbz              r8,3(r31)
subfic           r7,r11,96
addi             r6,r11,-123
srawi            r5,r7,9
srawi            r4,r6,9
subfic           r3,r10,96
addi             r7,r10,-123
extsb            r9,r9
srawi            r6,r3,9
srawi            r3,r7,9
subfic           r7,r9,96
addi             r30,r9,-123
extsb            r8,r8
srawi            r7,r7,9
srawi            r30,r30,9
subfic           r29,r8,96
addi             r28,r8,-123
srawi            r29,r29,9
srawi            r28,r28,9
and              r5,r5,r4
and              r3,r6,r3
and              r7,r7,r30
and              r30,r29,r28
clrrwi           r4,r5,5
clrrwi           r6,r7,5
clrrwi           r5,r3,5
clrrwi           r7,r30,5
add              r4,r4,r11
add              r3,r5,r10
add              r11,r6,r9
stb              r4,0(r31)
add              r10,r7,r8
stb              r3,1(r31)
stb              r11,2(r31)
stb              r10,3(r31)

总之,这应该是最快的方法的原因是:

1. 无分支预测失误惩罚
2. 一次为4-16(或更多)字节简化算法的能力
3. 编译器(或程序员)可以展开和交错以消除延迟并利用超标量(多问题)处理器
4. 无内存延迟(即表查找)

标题

1. #define a_z(c) (c >= 'a' && c <= 'z')

   • IS_LOWERCASE )提醒用户这是一个宏
   • c 在展开部分应该在括号内,以防止出现奇怪的副作用
   • 个人选择 :我喜欢重新排列条件,使其读起来更像英文的“a”<=c<=“z” (('a' <= (c)) && ((c) <= 'z'))

2. 我来做功能 void ToggleCase(char* c) 返回a char* (与发送的相同)以便能够按顺序使用它们: printf("%s\n", UpperCase(LowerCase("FooBar")));

1. 三元运算符不会使代码更快或更易于阅读。我会写一个简单的 if

就这样。

哦!还有一件事:您的代码采用ASCII(您自己也这么说),但不记录它。我会在头文件中加上一个注释。

我犹豫着回答这个问题,因为我已经20多年没有使用过小型设备了。然而,我认为规则几乎是一样的(有一个可能的补充):

1. 最小化内存访问
3. 最小化代码大小

当我在开发低级代码时,规则1使所有其他规则黯然失色。没有任何板上高速缓存,而且相对于处理器来说,内存速度慢得难以置信;这就是C中存在“register”存储类的原因。今天情况有所改变,但它仍然是最重要的两个问题之一。正如我在一篇文章中所评论的,查找表是一个好主意,但是要认识到它意味着每个测试都有一个额外的内存访问。一旦它进入缓存,这可能不是问题,但每次进入函数时,您都要付出多次缓存命中的代价(除非您经常调用它,以便查找表可以保留在缓存中)。

规则2看起来像是“你当然想这么做,为什么不是规则1?”但事实上,推理更深入。实际上,在某些方面,它是对规则1的重述,因为每个指令在执行之前都必须从内存中获取。有一个微妙的折衷方案:在纯整数处理器上,使用查找表来计算三角函数是一个明显的胜利;在嵌入浮点的芯片上,也许不是。

我不确定规则3是否仍然适用。以我的经验,人们总是争先恐后地削减代码,把俗话说的20磅装进10磅的袋子里。但今天看来最小的袋子是50磅。然而,即使有一个50磅的袋子(或许多兆字节的ROM)来保存代码/数据,您仍然需要将其拉入缓存(如果您有)。

新规则1:保持管道充满

现代处理器有很深的指令管道(如果您不熟悉这个术语,请参阅本文: http://arstechnica.com/old/content/2004/09/pipelining-1.ars/1 ). 深管道的一般经验法则是,分支(一个“if”测试)代价高昂,因为这意味着可能必须刷新管道才能加载到新代码中。因此,您编写代码以分支处理不太可能的情况(请参见 阿迪萨克

有比我更近经验的人可能会评论说,“现代处理器用两个分支加载管道,所以没有成本损失。”这一切都很好,但它提出了一个总体规则:

规则0:优化取决于您的体系结构和工作负载

我洗碗机里的微处理器可能没有流水线,也可能没有缓存。当然,它可能也不会做很多文本处理。或者两者都有;似乎市场上只有少数几款主要的嵌入式处理器,所以也许那块电路板上有奔腾,而不是8051系列。即使如此,即使是在基于奔腾的嵌入式处理器中,也有广泛的应用范围(http://en.wikipedia.org/wiki/List\u英特尔奔腾微处理器嵌入式处理器). 对一个人最好的东西未必对另一个人最好。

然后是你在处理什么样的数据。如果您正在处理文本,那么很可能(但不能保证)您的大多数数据是字母,而不是数字或标点符号;因此您可以对此进行优化。

然而,还有更多:我评论说“仅限于ASCII,嗯?”在OP上,另一个注释更为明确:如果您在2010年处理文本,则可能不会处理ASCII。至少,您将处理ISO-8859-1或类似的8位字符集。在这种情况下,也许无分支或智能分支(注意管道)解决方案仍然比查找表快(是的,这是我的假设)。但是如果你处理的是Unicode BMP(16位),你几乎必须使用这个表,不管它在内存方面的成本是多少,因为没有简单的规则来确定什么是小写还是大写。如果你处理的是Unicode的高级平面。。。好吧,也许“旧斜体”的大写并不那么重要(特别是因为它没有大写和小写)。

最后,确定的唯一方法是分析给定的实际工作负载。

最后:清除代码FTW

这篇文章是从我给OP写了一条评论开始的,评论说他/她使用宏是个坏主意(因为进入维护模式所以无法进入)。Peter Torok(抱歉,我不支持Unicode,甚至不支持ISO-8859-1)给出了一个原因,但还有另一个原因:它们是黑匣子。

这个操作看起来又漂亮又干净:代码很短,大量使用了位运算符和三元运算符,如果你懂这门语言就很容易理解。但如果你看到 A_Z ToggleCase

也许我是一个讨厌派对的人,因为据说这是一个学习练习,但是学习的一个关键部分应该是学会有效地使用你的工具。

ANSI C在标准库中包含了必要的函数,而且它们可能已经由编译器供应商为您的体系结构进行了大量优化。

首先我要说的是重新命名 a_z A_Z is_ASCII_Lowercase 和 is_ASCII_Uppercase

另外,使用 ^= 和 ?: if -陈述。

也许我花费了太多时间在C++上,而C的花费还不够,但我不是宏有参数的宏迷。正如Peter Torok指出的那样,它们会导致一些问题。CASE_标志的定义是可以的(不需要任何参数),但是我将用函数替换宏a_z和a_z。

怎么样(差不多可以):

char slot[] = { 0, 31, 63, 63 };
*c = slot[*c/32] + *c%32;

有几件事你可以改变:

*c += a_z(*c)*CASE_FLAG; // adds either zero or three two
// you could also replace multiplication with the shift (1<<5) trick

字符串实际上是数组:

char upper[] = "ABC..ABC..."; // 
...
*c = upper[*c+offset];

或

char upper[] = "ABC.."; // 
...
*c = upper[*c%32];

或

*c = 'A' + *c%32;

或者别的什么。。。

根据你的系统和你的cpu架构,很多事情可以做得不同。

关于你的代码,我有几个设计要点。首先,宏。宏有一些残酷的陷阱,应该小心使用。第二,使用全局切换情况。我会重写成这样-

 enum CASE {UPPER, LOWER};

void ToggleCase(char* c, CASE newcase)
{
    if(newcase == UPPER)
       UpperCase(c);
    else if(newcase == LOWER)
       LowerCase(c);
    else 
       { ; } //null
}

void LowerCase(char* c)
{
  while (*c++)  //standard idiom for moving through a string.
  {
    *c = *c < 'Z' ? *c + 32 : *c;
  }
}


void UpperCase(char* c)
{
  while (*c++)
  {
    *c = *c > 'a' ? *c - 32 : *c;
  }
}

现在,有人批评我的代码。

首先,是布兰奇。其次,假设输入是[a-zA-Z]+。第三,它只是ASCII(EBDIC呢?)。第四,它假设以空结尾(我认为有些字符串在字符串的开头有一些字符-Pascal)。第五,代码大小写并不是100%天真地显而易见。还要注意,枚举是一个隐藏得很严重的整数。你可以通过 ToggleCase("some string", 1024)

这些并不是说我的代码非常糟糕。在某些情况下,它服务于并且将服务于。

我之所以使用宏是因为,我认为,它使代码看起来更好,而且比函数调用更有效率。

效率更高吗?你对代码大小有什么要求?(对于生成的可执行代码,而不是C源代码)在现代桌面系统中,这很少是一个问题,而且速度更重要;但是除了“嵌入式系统应用程序”之外,您没有给我们提供更多的细节,因此我们无法为您解答这个问题。不过,这不是问题,因为宏中的代码实在是太小了,但你不能认为避免函数调用总是更有效!

如果允许,可以使用内联函数。自1999年以来,它们就正式成为C的一部分,但在一些编译器中支持的时间要长得多。内联函数是 比宏更干净,但是,根据您的确切目标要求,很难从源代码预测生成的代码。然而,更常见的情况是,人们总是被过时的东西(现在已经超过十年了!)不支持它们的C编译器。

简而言之,你总是需要知道你的确切要求,以确定什么是最优的。然后你必须 test to verify your performance predictions .

如果一个人试图同时处理多个字节,我认为最好的方法是强制所有值为0..127,添加5或37(这会使'z'到'z'变成127),注意该值,然后添加26,注意该值,然后进行一些咀嚼。类似于:

unsigned long long orig,t1,t2,result;

t1 = (orig & 0x7F7F7F7F7F7F7F7F) + 0x0505050505050505;
t2 = t1 + 0x1A1A1A1A1A1A1A1A;
result = orig ^ ((~(orig | t1) & t2 & 0x8080808080808080) >> 2);

隐马尔可夫模型。。。我想这很管用,即使是32位的机器。如果四个寄存器预装了适当的常量,一个ARM可以用最优的代码执行七个指令占用七个周期的操作;我怀疑编译器是否能找到优化(或者弄清楚将常量保存在寄存器中会有帮助——如果常量不保存在寄存器中,则单独处理字节会更快)。