任何体面的libc都会strlen比一次循环一个字节快得多,因此单独的矢量化strlen和toupper循环会更快.
基线:一个在运行中检查终止0的循环.
在Core2(Merom)2.4GHz上进行40M迭代的时间.gcc 5.2 -O3 -march=native.(Ubuntu 15.10). dst != src(所以我们制作副本),但它们不重叠(并且不在附近).两者都是一致的.
15字符串:基线:1.08s.autovec:1.34s
16 char string:baseline:1.16s.autovec:1.52s
127 char string:baseline:8.91s.autovec:2.98s //非向量清理有15个字符要处理
128 char string:baseline:9.00s.autovec:2.06s
129 char string:baseline:9.04s.autovec:2.07s //非向量清理有1个要处理的字符
一些结果与clang有点不同.
调用该函数的microbenchmark循环位于单独的文件中.否则它会内联并strlen()从循环中提升,并且运行得更快,尤其是.16个字符串(0.187s).
这有一个主要优点,gcc可以为任何架构自动矢量化它,但主要的缺点是它通常常见的小字符串情况较慢.
所以有很大的加速,但编译器自动矢量化并不会产生很好的代码,尤其是 用于清除最后15个字符.
使用SSE内在函数进行手动矢量化:
基于我的case-flip函数,它反转了每个字母字符的大小写.它利用了"无符号比较技巧",你可以low < a && a <= high通过范围转换进行单个无符号比较,这样任何值都可以小于low包含大于的值high.(如果low并且high距离太远,这种方法有效.)
SSE只有一个签名的比较,更大,但我们仍然可以通过量程变换到有符号范围的底部使用"无符号的比较"绝招:减去"A" + 128,所以字母字符的范围从-128到-128 +25(-128 +'z' - 'a')
请注意,对于8位整数,添加128和减去128是相同的.随身携带无处可去,所以它只是xor(无负载添加),翻转高位.
#include
__m128i upcase_si128(__m128i src) {
// The above 2 paragraphs were comments here
__m128i rangeshift = _mm_sub_epi8(src, _mm_set1_epi8('a'+128));
__m128i nomodify = _mm_cmpgt_epi8(rangeshift, _mm_set1_epi8(-128 + 25)); // 0:lower case -1:anything else (upper case or non-alphabetic). 25 = 'z' - 'a'
__m128i flip = _mm_andnot_si128(nomodify, _mm_set1_epi8(0x20)); // 0x20:lcase 0:non-lcase
// just mask the XOR-mask so elements are XORed with 0 instead of 0x20
return _mm_xor_si128(src, flip);
// it's easier to xor with 0x20 or 0 than to AND with ~0x20 or 0xFF
}
鉴于此函数适用于一个向量,我们可以在循环中调用它来处理整个字符串.由于我们已经针对SSE2,我们可以同时进行矢量化字符串结束检查.
在执行16B向量之后,我们还可以更好地"清理"剩余的最后15个字节:上层是幂等的,因此重新处理一些输入字节很好.我们对源的最后16B执行未对齐加载,并将其存储到与循环中的最后16B存储重叠的dest缓冲区中.
这不工作的唯一情况是当整个字符串16B下:即使在dst=src非原子读-修改-写是不是因为没有碰到一些字节都同样的事情,而且可以打破多线程代码.
我们有一个标量循环,也是为了src对齐.由于我们不知道终止0的位置,因此未对齐的负载src可能会进入下一页并发生段错误.如果我们需要对齐的16B块中的任何字节,则加载整个对齐的16B块总是安全的.
完整来源:在github要点.
// FIXME: doesn't always copy the terminating 0.
// microbenchmarks are for this version of the code (with _mm_store in the loop, instead of storeu, for Merom).
size_t strtoupper_sse2(char *dst, const char *src_begin) {
const char *src = src_begin;
// scalar until the src pointer is aligned
while ( (0xf & (uintptr_t)src) && *src ) {
*(dst++) = ascii_toupper(*(src++));
}
if (!*src)
return src - src_begin;
// current position (p) is now 16B-aligned, and we're not at the end
int zero_positions;
do {
__m128i sv = _mm_load_si128( (const __m128i*)src );
// TODO: SSE4.2 PCMPISTRI or PCMPISTRM version to combine the lower-case and '\0' detection?
__m128i nullcheck = _mm_cmpeq_epi8(_mm_setzero_si128(), sv);
zero_positions = _mm_movemask_epi8(nullcheck);
// TODO: unroll so the null-byte check takes less overhead
if (zero_positions)
break;
__m128i upcased = upcase_si128(sv); // doing this before the loop break lets gcc realize that the constants are still in registers for the unaligned cleanup version. But it leads to more wasted insns in the early-out case
_mm_storeu_si128((__m128i*)dst, upcased);
//_mm_store_si128((__m128i*)dst, upcased); // for testing on CPUs where storeu is slow
src += 16;
dst += 16;
} while(1);
// handle the last few bytes. Options: scalar loop, masked store, or unaligned 16B.
// rewriting some bytes beyond the end of the string would be easy,
// but doing a non-atomic read-modify-write outside of the string is not safe.
// Upcasing is idempotent, so unaligned potentially-overlapping is a good option.
unsigned int cleanup_bytes = ffs(zero_positions) - 1; // excluding the trailing null
const char* last_byte = src + cleanup_bytes; // points at the terminating '\0'
// FIXME: copy the terminating 0 when we end at an aligned vector boundary
// optionally special-case cleanup_bytes == 15: final aligned vector can be used.
if (cleanup_bytes > 0) {
if (last_byte - src_begin >= 16) {
// if src==dest, this load overlaps with the last store: store-forwarding stall. Hopefully OOO execution hides it
__m128i sv = _mm_loadu_si128( (const __m128i*)(last_byte-15) ); // includes the \0
_mm_storeu_si128((__m128i*)(dst + cleanup_bytes - 15), upcase_si128(sv));
} else {
// whole string less than 16B
// if this is common, try 64b or even 32b cleanup with movq / movd and upcase_si128
#if 1
for (unsigned int i = 0 ; i <= cleanup_bytes ; ++i) {
dst[i] = ascii_toupper(src[i]);
}
#else
// gcc stupidly auto-vectorizes this, resulting in huge code bloat, but no measurable slowdown because it never runs
for (int i = cleanup_bytes - 1 ; i >= 0 ; --i) {
dst[i] = ascii_toupper(src[i]);
}
#endif
}
}
return last_byte - src_begin;
}
在Core2(Merom)2.4GHz上进行40M迭代的时间.gcc 5.2 -O3 -march=native.(Ubuntu 15.10). dst != src(所以我们制作副本),但它们不重叠(并且不在附近).两者都是一致的.
15字符串:基线:1.08s.autovec:1.34s.手册:1.29s
16 char string:baseline:1.16s.autovec:1.52s.手册:0.335s
31字符串:手册:0.479s
127 char string:baseline:8.91s.autovec:2.98s.手册:0.925s
128 char string:baseline:9.00s.autovec:2.06s.手册:0.931s
129 char string:baseline:9.04s.autovec:2.07s.手册:1.02s
(实际上有定时_mm_store的循环,不_mm_storeu,因为storeu是Merom处理器速度较慢,即使地址是对齐的.这是对Nehalem的罚款和更高版本.我还保持原样对于现在的代码,而不是固定未能复制在某些情况下终止0,因为我不想重新计时.)
因此,对于长度超过16B的短字符串,这比自动矢量化要快得多.长度比矢量宽度小一个不存在问题.由于存储转发停顿,它们在就地操作时可能是一个问题.(但请注意,处理我们自己的输出仍然没问题,而不是原始输入,因为toupper是幂等的).
根据周围代码的需要以及目标微体系结构,针对不同的用例调整此问题有很多空间.让编译器为清理部分发出漂亮的代码是很棘手的.使用ffs(3)(在x86上编译为bsf或tzcnt)似乎很好,但显然这个位需要重新思考,因为我在写完大部分答案后注意到了一个错误(参见FIXME评论).
甚至更小的字符串的矢量加速可以通过movq或movd加载/存储获得.根据您的使用情况进行必要的自定义.
UTF-8:
我们可以检测到我们的向量何时具有高位设置的任何字节,并且在这种情况下回退到该向量的标量utf-8-aware循环.该dst点可以以不同于src指针的数量前进,但是一旦我们返回到对齐的src指针,我们仍然只是执行未对齐的向量存储dst.
对于UTF-8的文本,但主要由UTF-8的ASCII子集组成,这可能是好的:在所有情况下具有正确行为的常见情况下的高性能.当有很多非ASCII时,它可能会比一直保持在标量UTF-8感知循环中更糟糕.
如果下行很重要,那么以牺牲其他语言为代价提高英语速度并不是一个面向未来的决策.
感知语言区域:
在土耳其语语言环境(tr_TR)中,正确的结果toupper('i')是'?'(U0130),而不是'I'(纯ASCII).请参阅Martin Bonnertolower()关于Windows速度慢的问题的评论.
我们还可以检查异常列表并回退到标量,就像多字节UTF8输入字符一样.
由于这种复杂性,SSE4.2 PCMPISTRM或其他东西可以一次性完成我们的大量检查.
6> Milan Babušk..：
你在字符串中有ASCII或国际字符吗？
如果是后一种情况,"大写"并不那么简单,它取决于使用的字母表.有两院制和一院制字母.只有两个大小写的字母表具有不同的大小写字符.此外,还有复合字符,如拉丁大写字母'DZ'(\ u01F1'DZ'),它们使用所谓的标题案例.这意味着只有第一个字符(D)被更改.
我建议您研究ICU,以及简单和完整案例映射之间的区别.这可能有所帮助:
http://userguide.icu-project.org/transforms/casemappings
或德国eszet(sp？),看起来像希腊字母beta,意思是"ss".没有单一的德语字符意味着"SS",它是大写的等价物.德语中的"街道",当大写时,会使一个字符更长.
另一个特例是希腊字母sigma(Σ),它有***小写版本,取决于它是否在一个单词的末尾(ς)或不是(σ).然后有语言特定的规则,如土耳其语案例映射I↔ı和İ↔i.
7> 小智..：
string StringToUpper(string strToConvert)
{
for (std::string::iterator p = strToConvert.begin(); strToConvert.end() != p; ++p)
*p = toupper(*p);
return p;
}
要么,
string StringToUpper(string strToConvert)
{
std::transform(strToConvert.begin(), strToConvert.end(), strToConvert.begin(), ::toupper);
return strToConvert;
}
如果您无法获得提升,那么第二种解决方案可能是您可以获得的最佳解决方案.在第一个解决方案的参数之后,星星`**`是做什么的？
8> Pabitra Dash..：
以下适用于我.
#include
void toUpperCase(std::string& str)
{
std::transform(str.begin(), str.end(), str.begin(), ::toupper);
}
int main()
{
std::string str = "hello";
toUpperCase(&str);
}
9> Luca C...：
如果您只使用ASCII字符,速度更快:
for(i=0;str[i]!=0;i++)
if(str[i]<='z' && str[i]>='a')
str[i]-=32;
请注意,此代码运行速度更快,但仅适用于ASCII并且不是"抽象"解决方案.
如果您需要UNICODE解决方案或更传统和抽象的解决方案,请寻求其他答案并使用C++字符串的方法.
它不太好,但更快,更小,100%正确
我写了一个C答案和一个C++答案,因为C++编写的与C源完全兼容,所以任何C解决方案也是一个C++正确的解决方案
10> 小智..：
使用lambda.
std::string s("change my case");
auto to_upper = [] (char_t ch) { return std::use_facet>(std::locale()).toupper(ch); };
std::transform(s.begin(), s.end(), s.begin(), to_upper);
拜伦，不用担心其他评论。像您一样，用新的（现代）解决方案回答旧问题是完全可以的。
11> 小智..：
//works for ASCII -- no clear advantage over what is already posted...
std::string toupper(const std::string & s)
{
std::string ret(s.size(), char());
for(unsigned int i = 0; i < s.size(); ++i)
ret[i] = (s[i] <= 'z' && s[i] >= 'a') ? s[i]-('a'-'A') : s[i];
return ret;
}
12> k3a..：
只要你只使用ASCII并且你可以提供一个有效的RW存储器指针,C中有一个简单而非常有效的单行程:
void strtoupper(char* str)
{
while (*str) *(str++) = toupper((unsigned char)*str);
}
这对于像ASCII标识符这样的简单字符串尤其有用,您希望将其标准化为相同的字符大小写.然后,您可以使用缓冲区构造std:string实例.
13> Glen Knowles..：
#include
#include
std::string str = "Hello World!";
auto & f = std::use_facet>(std::locale());
f.toupper(str.data(), str.data() + str.size());
这将比使用全局toupper函数的所有答案都要好,并且可能是boost :: to_upper正在做什么.
这是因为:: toupper必须查找语言环境 - 因为它可能已被不同的线程更改 - 对于每次调用,而这里只有对locale()的调用才会有这种惩罚.查找区域设置通常涉及锁定.
在更换auto,使用新的非const str.data()之后,这也适用于C++ 98,并添加一个空格来打破模板关闭(">>"到">>"),如下所示:
std::use_facet > & f =
std::use_facet >(std::locale());
f.toupper(const_cast(str.data()), str.data() + str.size());
14> bayda..：
typedef std::string::value_type char_t;
char_t up_char( char_t ch )
{
return std::use_facet< std::ctype< char_t > >( std::locale() ).toupper( ch );
}
std::string toupper( const std::string &src )
{
std::string result;
std::transform( src.begin(), src.end(), std::back_inserter( result ), up_char );
return result;
}
const std::string src = "test test TEST";
std::cout << toupper( src );
京公网安备 11010802040832号