实现查找表的最简单方法是使用带有 256 个字符(256 字节)的数组的查找表来检查字符是否为 alpha?我知道我可以使用 isalpha 函数,但是查找表应该更有效,需要一个比较而不是多个比较。我正在考虑将索引与 char 十进制转换相对应,并直接检查 char 是否等效。
6 回答
我一直使用这种单一的比较方法(我认为它的流水线更好),因为它比最多进行四次比较要快。
unsigned((ch&(~(1<<5))) - 'A') <= 'Z' - 'A'
我对几种不同的方法进行了基准测试,并考虑了查找表方法的 TLB 缓存未命中。我在 Windows 上运行了基准测试。以下是字符集为 '0'..'z' 的时间:
lookup tbl no tlb miss: 4.8265 ms
lookup table with tlb miss: 7.0217 ms
unsigned((ch&(~(1<<5))) - 'A') <= 'Z' - 'A': 10.5075 ms
(ch>='A' && ch<='Z') || (ch>='a' && ch<='z'): 17.2290 ms
isalpha: 28.0504 ms
您可以清楚地看到语言环境代码是有代价的。
以下是字符集为 0..255 的时间:
tbl no tlb miss: 12.6833 ms
unsigned((ch&(~(1<<5))) - 'A') <= 'Z' - 'A': 29.2403 ms
(ch>='A' && ch<='Z') || (ch>='a' && ch<='z'): 34.8818 ms
isalpha: 78.0317 ms
tbl with tlb miss: 143.7135 ms
时间更长,因为测试了更多的字符。在第二次测试中,我用于 tlb“flush”的段数更大。可能是表查找方法比第一次运行所表明的 tlb 未命中受到的影响更大。您还可以看到,当字符为 alpha 时,单个 cmp 方法效果更好。
如果比较一行中的多个字符,查找表方法是最好的,但它并不比单个 cmp 方法好多少。如果您在这里和那里比较字符,那么 tlb 缓存未命中可能会使 tbl 方法比单个 cmp 方法更差。当字符更可能是字母时,单个 cmp 方法效果最好。
这是代码:
__forceinline bool isalpha2(BYTE ch) {
return (ch>='A' && ch<='Z') || (ch>='a' && ch<='z');
}
__forceinline bool isalpha1(BYTE ch) {
return unsigned((ch&(~(1<<5))) - 'A') <= 'Z' - 'A';
}
bool* aTbl[256];
int main(int argc, char* argv[])
{
__int64 n = 0, cTries = 100000;
int b=63;
int ch0=' ', ch1 ='z'+1;
ch0=0, ch1 = 256;
// having 255 tables instead of one lets us "flush" the tlb.
// Intel tlb should have about ~32 entries (depending on model!) in it,
// so using more than 32 tables should have a noticable effect.
for (int i1=0 ; i1<256 ; ++i1) {
aTbl[i1] = (bool*)malloc(16384);
for (int i=0 ; i<256 ; ++i)
aTbl[i1][i] = isalpha(i);
}
{ CBench Bench("tbl with tlb miss");
for (int i=1 ; i<cTries ; ++i) {
for (int ch = ch0 ; ch < ch1 ; ++ ch)
n += aTbl[ch][ch]; // tlb buster
}
}
{ CBench Bench("tbl no tlb miss");
for (int i=1 ; i<cTries ; ++i) {
for (int ch = ch0 ; ch < ch1 ; ++ ch)
n += aTbl[0][ch];
}
}
{ CBench Bench("isalpha");
for (int i=1 ; i<cTries ; ++i) {
for (int ch = ch0 ; ch < ch1 ; ++ ch)
n += isalpha(ch);
}
}
{ CBench Bench("unsigned((ch&(~(1<<5))) - 'A') <= 'Z' - 'A'");
for (int i=1 ; i<cTries ; ++i) {
for (int ch = ch0 ; ch < ch1 ; ++ ch)
n += isalpha1(ch);
}
}
{ CBench Bench("(ch>='A' && ch<='Z') || (ch>='a' && ch<='z')");
for (int i=1 ; i<cTries ; ++i) {
for (int ch = ch0 ; ch < ch1 ; ++ ch)
n += isalpha2(ch);
}
}
return n;
}
class CBench {
public:
__declspec(noinline) CBench(CBench* p) : m_fAccumulate(false), m_nTicks(0),
m_cCalls(0), m_pBench(p), m_desc(NULL), m_nStart(GetBenchMark()) { }
__declspec(noinline) CBench(const char *desc_in, bool fAccumulate=false) :
m_fAccumulate(fAccumulate), m_nTicks(0), m_cCalls(0), m_pBench(NULL),
m_desc(desc_in), m_nStart(GetBenchMark()) { }
__declspec(noinline) ~CBench() {
__int64 n = (m_fAccumulate) ? m_nTicks : GetBenchMark() - m_nStart;
if (m_pBench) {
m_pBench->m_nTicks += n;
m_pBench->m_cCalls++;
return;
} else if (!m_fAccumulate) {
m_cCalls++;
}
__int64 nFreq;
QueryPerformanceFrequency((LARGE_INTEGER*)&nFreq);
double ms = ((double)n * 1000)/nFreq;
printf("%s took: %.4f ms, calls: %d, avg:%f\n", m_desc, ms, m_cCalls,
ms/m_cCalls);
}
__declspec(noinline) __int64 GetBenchMark(void) {
__int64 nBenchMark;
QueryPerformanceCounter((LARGE_INTEGER*)&nBenchMark);
return nBenchMark;
}
LPCSTR m_desc;
__int64 m_nStart, m_nTicks;
DWORD m_cCalls;
bool m_fAccumulate;
CBench* m_pBench;
};
实际上,根据 Plauger 在“标准 C 库”[91]isalpha
中的说法,通常使用查找表来实现。那本书确实过时了,但今天可能仍然如此。这是他对 isalpha 提出的定义
功能
int isalpha(int c)
{
return (_Ctype[c] & (_LO|_UP|_XA));
}
宏
#define isalpha(c) (_Ctype[(int)(c)] & (_LO|_UP|_XA))
记住优化的第一条规则:不要这样做。
然后记住第二条优化规则,很少应用:不要这样做。
然后,如果您确实遇到瓶颈并且您已确定isalpha
原因,那么这样的事情可能会更快,具体取决于您的库如何实现该功能。您需要衡量环境中的性能,并且仅在确实有可衡量的改进时才使用它。这假设您不需要测试范围之外的值unsigned char
(通常为 0...255);为此,您需要做一些额外的工作。
#include <cctype>
#include <climits>
class IsAlpha
{
public:
IsAlpha()
{
for (int i = 0; i <= UCHAR_MAX; ++i)
table[i] = std::isalpha(i);
}
bool operator()(unsigned char i) const {return table[i];}
private:
bool table[UCHAR_MAX+1];
};
用法:
IsAlpha isalpha;
for (int i = 0; i <= UCHAR_MAX; ++i)
assert(isalpha(i) == bool(std::isalpha(i)));
您的编译器库的实现可能非常有效,并且可能已经在大多数情况下使用查找表,但也处理一些可能有点棘手的情况,如果您要自己做的话isalpha()
:
- 正确处理带符号的字符(在查找表上使用负索引)
- 处理非 ASCII 语言环境
您可能不需要处理非 ASCII 语言环境,在这种情况下,您可能(也许)能够稍微改进库。
事实上,如果一个宏或函数只返回以下结果,我不会感到惊讶:
((('a' <= (c)) && ((c) <= 'z')) || (('A' <= (c)) && ((c) <= 'Z')))
可能比表查找更快,因为它不必占用内存。但我怀疑它会以任何有意义的方式更快,并且很难衡量差异,除非在一个只做isalpha()
调用的基准测试中(这也可能会改善表查找结果,因为该表可能会在缓存中为许多的测试)。
而且isalpha()
真的是瓶颈吗?对任何人?
只需使用编译器库中的那个。
如果您正在寻找字母字符 aZ,那么这比您的 255 数组要少得多。您可以从相关的 ASCII 字符(最低的字母字符)中减去“A”,这将是数组的索引。例如,'B' - 'A' 为 1。如果测试为负,则不是 alpha。如果大于您的最大 alpha ('z'),则它不是 alpha。
如果您完全使用 unicode,则此方法将不起作用。
我认为您可以比使用查找表更简单地实现 isalpha。使用字符 'a'-'z' 和 'A'-'Z' 在ASCII中连续的事实,这样的简单测试就足够了:
char c ;
// c gets some value
if(('A'<=c && 'Z'>=c) || ('a'<=c && 'z'>=c)) // c is alpha
请注意,这没有考虑不同的语言环境。