10
\$\begingroup\$

I'm looking for the fastest way to determine if a C-style string contains only alphabetic characters.

For this question, there are a few assumptions:

  1. strlen(c) > 0
  2. Strings are null-terminated
  3. Continuous character encoding from a-z and A-Z is not guaranteed, but likely.
  4. The string is not a null pointer, nor is the pointer its "default value".
#include <stdbool.h>
#include <ctype.h>

bool stralpha(const char *c)
{
    bool alphabetic = true;

    while(*c)
        alphabetic &= !!isalpha(*c++);

    return alphabetic;
}

/* so gcc does not complain */
int main(void){}

To be clear: I know that any performance difference in such a function will be minimal at best. This is just for fun.

In my case, I was having issues with the function returning false even when c was purely alphabetic. That is why I use double negation !! on isalpha(), because it is not guaranteed to return consistently 0 or 1 per the standard.

\$\endgroup\$
  • \$\begingroup\$ I don't have time to put together a solution myself, but there may be an interesting approach using perfect hashing and the machine's native word size. If you could operate on strings in 4 or 8 character chunks, that could be significant enough to warrant the extra opcodes needed to produce the hash. \$\endgroup\$ – Cort Ammon Mar 28 '18 at 18:20
  • \$\begingroup\$ You can easily shortcut the function by returning false as soon as you find a non alpha character. \$\endgroup\$ – Turksarama Mar 29 '18 at 5:49
13
\$\begingroup\$

The main problem with your code (in terms of performance) is that it processes every character in the string regardless. It's probably better to actually exit early if you find a non-alpha character, with something like:

bool isStrAlpha (const char *chPtr) {
    // if (*chPtr == '\0') return false;
    while (*chPtr != '\0')
        if (! isalpha (*chPtr++))
            return false;
    return true;
}

And just a couple of extra notes:

  • This code works fine even for zero-length strings, assuming the intent is to ensure whatever characters are in the string are all alpha. In other words, it considers an empty string valid because it contains no non-alpha characters. If you want to ensure the string has to have at least one alpha, just reinstate the commented-out line at the start of the function.

  • Your second assumption is superfluous. A series of characters that are not terminated with \0 is not actually a string in C.

  • Whether alpha characters are likely to be consecutive is not relevant in my opinion, I usually prefer correct, portable code over speed. But, in any case, you can be reasonably certain that the people who created your implementation will have optimised the wazoo out of the character classification stuff.

\$\endgroup\$
8
\$\begingroup\$

Not much to review except a typo (it should be <ctype.h>). As noted in the other answer, !! is of a dubious value.

As for fun, a true nostalgic seventies loop would look like

    while (isalpha(*c++)) {
        ;
    }
    return !c[-1];
\$\endgroup\$
  • 2
    \$\begingroup\$ I wouldn't really recommend anyone to write obscure code like this. The only purpose it fills is to stroke the programmer's ego, making them look "smart". Why not write return !- true<:c:>; while you are at it... Instead, write code as readable as possible. \$\endgroup\$ – Lundin Mar 28 '18 at 8:16
  • 7
    \$\begingroup\$ For example something along the lines of while (isalpha(*c)) { c++; } return *c != '\0';. This is CR, not IOCCC. \$\endgroup\$ – Lundin Mar 28 '18 at 8:22
  • \$\begingroup\$ @Lundin: A sufficiently dumb compiler from 40 odd years ago might actually generate different (and possibly less efficient) assembly for your version than for vnp's. That said, I'd expect an actual optimized implementation targeting compilers from that era to look something like this: register char c, *p; do { c = *p++; } while (isalpha(c)); return !c; And I'd at least consider replacing the isalpha() call with a hand-written macro. \$\endgroup\$ – Ilmari Karonen Mar 28 '18 at 14:32
  • \$\begingroup\$ I would wonder what @Ilmari is up to that this would make a difference. To 99.9% of all C programmers optimising their code for ~40 year old compilers is pointless \$\endgroup\$ – Baldrickk Mar 28 '18 at 16:03
  • 1
    \$\begingroup\$ Actually, I,m pretty certain the !! is vital in the original code, because OP is using &= (bitwise & rather than logical &&) and the standard only requires that the character classification functions return zero or non-zero. The !! forces the output of isalpha() to become zero or one so it works correctly with &. \$\endgroup\$ – user7649 Mar 29 '18 at 1:32
8
\$\begingroup\$

First and foremost, I should point out that if you're doing performance work, you should profile the code to see where the slowdown is. That will allow you to determine objectively whether changes you make are actually helping or not.

You have 2 negations on your call to isalpha(). If you remove them both, you'll get the same result, but faster. I had originally thought that the double negation of isalpha() was pointless, but others have pointed out that it's needed because of quirks in the C language. Given that, and given that I don't recall ever running into this in the wild, I'd recommend reformulating it. There are a few options:

  1. Get rid of the &= as mentioned below.
  2. Write a function that returns an actual bool value so you don't have to worry about this particular quirk.
  3. Change the local call site to calculate a bool by doing something like alphabetic &= (isalpha(*c++) != 0);
  4. At the very least, comment on why you need the !! in the first place since it's not immediately obvious.

You could exit the loop early at the first non-alphabetic character. So something like:

while ((*c) && (alphabetic))
{
    alphabetic &= isalpha(*c++);
}

A local in-line implementation of isalpha() is likely to be faster than a system library call. Of course, that makes maintenance harder because you have to have a different version for each encoding, given the possibility of non-contiguous a-z characters. A simple way, if you can guarantee 8-bit characters, is to have a 256 element lookup-table where each element is true or false. You could automatically build it by doing something like:

bool alphaTable[256];
for (int nextChar = 0; nextChar < 256; nextChar++)
{
    alphaTable[nextChar] = isalpha(nextChar);
}

Then your loop becomes:

bool alphabetic = true;
while((*c) && (alphabetic))
{
    alphabetic = alphaTable[*c++];
}

You can get rid of the &= because whenever it becomes false, 1) we're done, and 2) all future values will be false.

This could be made even faster by using SIMD instructions. The details would vary depending on the architecture, so again, more maintenance. If you have a very large number of strings to calculate this on at one time, you could also perform multiple simultaneous calculations by running the function on multiple cores at the same time.

\$\endgroup\$
  • 11
    \$\begingroup\$ The !!isalpha(...) is likely because isalpha is not specified to return either 0 or 1, so isalpha('a') & isalpha('b') is allowed to evaluate to 0. The implicit conversion to bool should avoid problems (edit: no, it doesn't, the conversion is done the other way around: bool a = true; a &= 2; sets a to false), but I can't imagine" an implementation that doesn't optimise !! the same way, so I can't imagine an implementation where removing !! makes it faster. \$\endgroup\$ – hvd Mar 28 '18 at 7:48
  • \$\begingroup\$ Modern GCC editions will inline calls to the look-up functions declared in ctype.h for you, so I wouldn't worry about that: godbolt.org/g/iXAUqH \$\endgroup\$ – David Foerster Mar 28 '18 at 10:34
  • 2
    \$\begingroup\$ isalpha is unlikely to be a system call. There won’t be an overhead to calling it, compared to a locally defined function. \$\endgroup\$ – Konrad Rudolph Mar 28 '18 at 11:33
  • 2
    \$\begingroup\$ agreed on the speed arguments in above comments. !! will be optimised, and isalpha() won't be slow, so no need to do the lookup table. Keep the while((*c) && (alphabetic)) however to fail early if that is desired. \$\endgroup\$ – Baldrickk Mar 28 '18 at 16:01
  • 1
    \$\begingroup\$ With that said, while(!!isalpha(*c++)){;} return *c == '\0'; will do the job too. \$\endgroup\$ – Baldrickk Mar 28 '18 at 16:06
6
\$\begingroup\$

The truly fastest way is some manner of look-up table, as demonstrated in another answer. Such a table could even be generated at compile time:

const bool is_alpha [256] =
{
  ['A'] = true,
  ['B'] = true,
  ...
  ['Z'] = true,
  ['a'] = true,
  ...
};

Elements that aren't set to true are guaranteed to be default initialized to 0 = false.


That being said, here is my code review:

Bugs

  • bool alphabetic = true; means that your function will return true if the first element of the array is \0.

  • You don't stop once you find an invalid character, so the whole function is needlessly slow.

Coding style

  • The !! is fine. The other reviews fail to grasp that the C standard only guarantees: (C11 7.4.1)

    The functions in this subclause return nonzero (true) if and only if the value of the argument c conforms to that in the description of the function.

    This text has remained unchanged since C90, as in before C had a boolean type. So it does not mean that the function necessarily returns boolean true, but rather that it returns anything non-zero.

    However, the code would be more readable if you write is_alpha(...) != false. The use of !! is often criticised as obfuscation.

  • The use of ++ (pre or postfix) mixed with other operators in the same expression is widely recognized as bad practice. There are many dangers with this, both operator precedence bugs and risk of invoking poorly-defined behavior. In addition, it makes the code hard to read.

    Suppose for example that someone comes in and maintains the code, want to allow spaces, is aware that the is... functions return anything non-zero, and therefore writes something like !!(isalpha(*c++) | isspace(*c)). Boom, severe bug, undefined behavior.

    Therefore, never write things such as *c++ even though this happen to be a very commonly used C trick. There is no benefit what-so-ever of mixing ++ with other operators, only dangers.

  • The use of while(*c) is a debated coding style. As such, it is a bit subjective - some think this style is fine as it is "traditional C". Others, like the MISRA-C coding standard (and me) prefer while(*c != '\0') as this is more self-documenting, improves possibilities of static code analysis and prevents mix-ups with c != NULL, which of course means something else entirely.

  • Always use compound statements { } after all control and loop expressions, with no exceptions. To skip this when there's just one line of code trailing is bad and dangerous practice. Such coding style caused the most expensive bug ever written in the history of programming, after which there are no arguments left that justifies the style.


A fixed version:

bool stralpha(const char *c)
{
  if(*c == '\0')
  {
    return false;
  }

  while(*c != '\0' && isalpha(*c))
  {
    c++;
  }

  return *c == '\0';
}
\$\endgroup\$
  • 3
    \$\begingroup\$ isalpha() often is a macro using a look-up table, atleast for non-UTF systems. The table has 256 bytes, with an entry for each character/. The byte represents a bitfield, for whitespace, alpha, numerical, hex (a-f, A-F), lower, upper, etc. \$\endgroup\$ – CSM Mar 28 '18 at 8:05
  • \$\begingroup\$ @CSM I've seen standard library implementations that actually do implement it as a function - most notably in small embedded systems where the look-up table is too expensive. \$\endgroup\$ – Lundin Mar 28 '18 at 8:08
  • 3
    \$\begingroup\$ Agreed with you up to the last point. There’s absolutely no evidence of this being “dangerous practice”; it’s all just FUD. On the contrary, it removes code clutter, which reduces cognitive load and therefore potentially prevents bugs. Which is “the most expensive bug ever written in the history of programming” that you are referring to? I am unable to find this information. I hope you’re not referring to “goto fail”, which was caused by a faulty merge, not by missing parentheses. \$\endgroup\$ – Konrad Rudolph Mar 28 '18 at 11:40
  • \$\begingroup\$ @KonradRudolph The Apple goto fail was made possible by allowing the sloppy coding style - it would never have occurred if that style was banned. If the most expensive bug in programming history is not enough for you, then look at why MISRA-C bans this style. The core of MISRA-C is based on scientific research and population studies by prof. Les Hatton in the 90s, where he looked at root causes for bugs in C code. You can read the absolutely existing scientific evidence in his book/scientific report "Safer C". \$\endgroup\$ – Lundin Mar 28 '18 at 14:36
  • \$\begingroup\$ @Lundin Thanks for the reference (I haven’t read Safer C. I have read similar reports and the evidence presented therein is often apocryphal; evidence-based software engineering is in its infancy). But no, this has been discussed ad nauseam: goto fail or equivalent bugs could have occurred even if single statements were enclosed in braces. \$\endgroup\$ – Konrad Rudolph Mar 28 '18 at 15:11
2
\$\begingroup\$

The ++ operator, when used as an expression, is error-prone in case someone later adds or removes some lines. Just use a regular loop, the optimizer will compile most of the answers given here to the same code anyway:

bool isalpha_str(char const* s)
{
    for(; *s; ++s)
    {
        if(!isalpha(*s))
        {
            return false;
        }
    }
    return true;
}
\$\endgroup\$
-1
\$\begingroup\$

If a char is 8 bytes and a short is 16 bytes (you'd have to enforce this beforehand) you could do some loop unrolling and test up to two characters at once for some modest improvements. I tested this out with a 27 characters string (with the non-alpha at the end so as not to exploit the original code's lack of short circuiting) and tested it against the basic 256-entry lookup table version. The unrolled version was about 25% faster on my machine using gcc and -O3 for both.

bool alphaTable16[65536];

void init16 ()
{
    for (int i=0; i<256; ++i)
    {
        for (int j=0; j<256; ++j)
        {
            char k[2]={i,j};
            alphaTable16[*(unsigned short *)k]=isalpha(k[0]) && isalpha(k[1]);
        }
    }
    for (int j=0; j<256; ++j)
    {
        alphaTable16[j]=isalpha(j);
    }
}

bool stralpha2 (const char *c)
{
    while (true)
    {
        const char *d=c;
        if (*c++==0) /* test no characters */
            return true;
        if (*c++==0) /* test one character */
            return alphaTable16[*d];
        /* test two characters */
        if (!alphaTable16[*(unsigned short *)d]) return false;
    }
}
\$\endgroup\$
  • \$\begingroup\$ void init16 () Don't use obsolete style declarations. *(unsigned short *)k Don't invoke undefined behavior by violating strict aliasing. Don't use the potentially signed char type to store raw data. Don't use global variables. Use consistent coding style. And so on. This answer isn't a review, it is source code which desperately needs a review of its own. \$\endgroup\$ – Lundin Mar 29 '18 at 8:05
-1
\$\begingroup\$

Your code invokes undefined behavior. When operating on a const char *, the argument to the ctype functions must always be cast to unsigned char.

\$\endgroup\$
  • \$\begingroup\$ This is incorrect. The ctype functions all work on an int which is signed - per design, since they might encounter EOF. Casting to unsigned char is therefore complete nonsense, the argument will be promoted to int anyway. In addition, unsigned char and char may alias each other, so your argument is incorrect even in other cases where it would matter. \$\endgroup\$ – Lundin Mar 29 '18 at 8:01
  • \$\begingroup\$ @Lundin Please read a good and careful analysis of the C standard before calling my answer "nonsense". \$\endgroup\$ – Roland Illig Mar 29 '18 at 19:56
  • \$\begingroup\$ Actually quote it or be quiet? I have read the standard plenty, thank you. If you ever do it yourself, you will see that the ctype functions have int as parameter. \$\endgroup\$ – Lundin Mar 31 '18 at 16:09
  • \$\begingroup\$ @Lundin stackoverflow.com/a/39520176. By the way, I have already read the C standard and also understood it. \$\endgroup\$ – Roland Illig Mar 31 '18 at 20:45
  • \$\begingroup\$ Why are you linking some random post on SO about a different programming language? I asked you to cite the C standard. I'm still waiting. I suspect you will eventually locate C11 7.4 §1. "The header <ctype.h> declares several functions useful for classifying and mapping characters. In all cases the argument is an int, the value of which shall be representable as an unsigned char or shall equal the value of the macro EOF . If the argument has any other value, the behavior is undefined." After which you might even find out about lvalue conversion of function arguments. \$\endgroup\$ – Lundin Apr 1 '18 at 19:53
-3
\$\begingroup\$

The above answers using the is_alpha array are expensive in terms of memory.

you can use:

bool is_alpha(char c) {
     //A-Z
     if( (c>=65) && (c<=90) )
         return true;
     if( (c>=97) && (c<=122) )
         return true;
     return false;
}

all the conditions can be in one line, it is for clarity.

\$\endgroup\$
  • 2
    \$\begingroup\$ Note that this is not fully portable, since it assumes the ASCII character encoding. \$\endgroup\$ – Ilmari Karonen Mar 28 '18 at 13:59
  • \$\begingroup\$ right, you can expand it to use Unicode. If someone would like to have all the alphanumeric symbols in a table it will be huge. \$\endgroup\$ – nmnir Mar 28 '18 at 14:27
  • 3
    \$\begingroup\$ Actually, I was thinking more about EBCDIC, since the OP mentioned the contiguity of the characters from A to Z not being guaranteed. \$\endgroup\$ – Ilmari Karonen Mar 28 '18 at 14:47
  • \$\begingroup\$ @IlmariKaronen EBCDIC is trash. Programmers who write programs in the year 2018 to be compatible with EBCDIC are horribly confused. Now what you do in this case is a static assert of 'Z' - 'A' and 'z' - 'a'. If the result isn't the number of letters in the alphabet, throw a static assert which informs the user that their system is trash. \$\endgroup\$ – Lundin Mar 29 '18 at 8:08
  • \$\begingroup\$ That being said, this answer doesn't really solve anything, since it just repeats one likely implementation of standard library isalpha. How that will improve performance is beyond me. First sentence of the question is "I'm looking for the fastest way". \$\endgroup\$ – Lundin Mar 29 '18 at 8:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.