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

Question

作为一个学习锻炼,我的三个功能,ToggleCase,小写和大写,每想到一个指针的ASCII字符的字符串,由空字符终止; 他们按预期工作.有更高效或更快的方法来完成这项任务吗？我是否违反任何优秀C编码的潜规则？我已经使用了宏,因为我认为它使代码看起来更好,而且比函数调用更有效.这是典型的还是矫枉过正的？

请随意挑选和批评代码(但确实很好).

case_conversion.h

#define CASE_FLAG 32
#define a_z(c) (c >= 'a' && c <= 'z')
#define A_Z(c) (c >= 'A' && c <= 'Z')

void ToggleCase(char* c);
void LowerCase(char* c);
void UpperCase(char* c);

case_conversion.c

#include "case_conversion.h"

void ToggleCase(char* c)
{
 while (*c)
 {
  *c ^= a_z(*c) || A_Z(*c) ? CASE_FLAG : 0;
  c++;
 }
}
void LowerCase(char* c)
{
 while (*c)
 {
  *c ^= A_Z(*c) ? CASE_FLAG : 0;
  c++;
 }
}
void UpperCase(char* c)
{
 while (*c)
 {
  *c ^= a_z(*c) ? CASE_FLAG : 0;
  c++;
 }
}

Answer 1

我最喜爱的:

*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大小的单词(取决于plain char是有符号还是无符号).
2. 使用无符号(非溢出捕获)sub指令减去常量26 .
3. 如果未设置进位标志,则条件跳转到其余代码.
4. 否则,在值处添加32 *c.

步骤2和3可以组合在使用比较 - 跳转操作而不是标志的体系结构上.我能看到任何重大幕后成本的唯一方法就是机器不能直接寻址字符,或者它是否使用了令人讨厌的(符号/幅度或补码)符号值表示,在这种情况下转换为无符号会是不平凡的.据我所知,现代嵌入式架构没有这些问题; 它们主要与传统大型机(以及较小程度上的DSP)隔离.

如果有人担心错误的编译器实际执行算术<<5,你可能会尝试:

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.

Answer 2

您的宏至少存在两个主要问题.考虑如果我给他们中的一个打电话会发生什么

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给定平台上的所有可能值(或将其缩小为合法值并进行参数检查),但为了说明,这样做.)

Answer 3

注意:问题标题已被编辑 - 原始标题是关于优化" 请批判 -用C语言转换字符串案例的最佳函数 ",这解释了为什么我的答案仅涉及优化而不是一般地"改进"函数.

如果您真的在寻找绝对最快的方法,那么从长远来看,无分支版本将成为可行的方法,因为它可以使用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); 
}

为了清晰起见,我的功能得到了扩展,并使用了非硬编码常量.您可以使用硬编码值在一行中执行相同的操作但我喜欢可读代码; 但是,这是我算法的"压缩"版本.因为它这不是任何更快的 EXACT同样的事情"压缩"到一条线.

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

您可以在此处进行许多优化,以使其更快.您可以对ASCII的最佳数字进行硬编码,因为该示例不假设除az和AZ之外的任何编码映射都是连续的范围.例如,如果您没有桶形移位器,您实际上可以将AsrBits更改为4(9-5),因为ConvertVal将为+/- 32,具体取决于toupper或tolower操作.

一旦你有了branchfree版本,你就可以使用SIMD或bit-twiddling SWAR(A寄存器中的SIMD)技术一次转换4-16个字节(甚至可能更多地取决于你的寄存器有多宽,如果你展开隐藏延迟).这将比任何查找方法快得多,后者几乎仅限于单字节转换,除非您有非常大的表,这些表每个字节同时处理指数增长.

此外,您可以在不使用int upcast的情况下生成branchfree谓词,但是您必须执行更多操作(通过向上转换它只是每个范围减去一个).您可能需要对SWAR执行扩展操作,但大多数SIMD实现都有一个比较操作,可以免费为您生成一个掩码.

SWAR/SIMD操作也可以从对存储器的更少读取/写入中受益,并且可以对齐发生的写入.对于具有加载命中存储惩罚的处理器(例如PS3单元处理器),这要快得多.将其与展开版本中的简单预取相结合,您几乎可以完全避免内存停顿.

我知道在我的例子中似乎有很多代码,但是有ZERO分支(隐式或显式),结果没有分支错误预测.如果您处于具有显着分支误预测惩罚的平台上(对于许多流水线嵌入式处理器来说都是如此),那么即使没有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)

证据就在布丁中,上面编译的代码与分支版本相比,甚至在转到SWAR或SIMD之前都会非常快.

总之,为什么这应该是最快的方法:

1. 没有分支错误预测处罚
2. 能够一次4-16(或更多)字节的SIMD-ify算法
3. 编译器(或程序员)可以展开和交错以消除延迟并利用超标量(多发布)处理器
4. 没有内存延迟(即表查找)