Fast strlen function vs aliasing rules

Question

I found this "fast strlen function" implementation:

// for x86 only
size_t my_strlen(const char *s) {
    size_t len = 0;
    for(;;) {
        unsigned x = *(unsigned*)s;
        if((x & 0xFF) == 0) return len;
        if((x & 0xFF00) == 0) return len + 1;
        if((x & 0xFF0000) == 0) return len + 2;
        if((x & 0xFF000000) == 0) return len + 3;
        s += 4, len += 4;
    }
}

An optimization techique used here is obviously simple: read memory by natural CPU words (the code is old and assumes x32 CPU), rather then by simple bytes.

But this code is violating aliasing rules, and so cause undefined behaviour, which can be freely optimized out by the compiler (those making code even faster, but inccorect).

I also see now that it is not portable, as it tied to the little-endian endianness.

Or may be i am completly wrong here and the code above is correct? Is it correct for C? For C++?

Answer 1

This is just very bad code. Even the code's author warns:

• This function will crash if an non-readable memory page is located right after the end of the string. The simplest way to prevent this is to allocate 3 additional bytes at the end of string.

• The dwords may be unaligned, but x86 architecture allows access to unaligned data. For small strings, the alignment will take more time than the penalty of unaligned reads.

• The code is not portable: you will have to add another 4 conditions if you use a 64-bit processor. For big-endian architectures, the order of conditions should be reversed.

Even if this did not break the aliasing rule the burden placed on the coder to make my_strlen work is completely unjustifiable. It has been stated several times that strlen will already be tuned beyond anything the average coder could accomplish.

But an additional statement should be made for C++: Bjarne Stroustrup, the creator of C++, in the last page of chapter 4 in his book: "The C++ Programming Language" says:

Prefer strings over C-style strings

You'll find taking the size of a string far more performant than finding the size of a C-String.

EDIT:

In your comment you say you are working with StaticallyBufferedString which purports to solve string's "pooling memory model" which causes:

• Unnecessary heap locks in a multithreaded context
• Fragmentation from real-time size control

I'd like to suggest C++17's string_view which like all of C++17 was constructed with multi-threading in mind. It provides the functionality of a string backed by heap and constexpr friendly C-Strings. You can even get a jump start on learning about it with namespace experimental: http://en.cppreference.com/w/cpp/experimental/basic_string_view Unlike your time put in on StaticallyBufferedStrings the knowledge you gain will be perfectly portable and applicable to any future C++ work you do!

Answer 2

This is a bad idea, and will make your performance worse. The standard strlen function provided by modern compilers is already highly optimized, and will do a much better job than above. For example, on SSE-enabled CPUs (i.e. pretty much all of them) it will already use SSE/AVX instructions to do a vectorized search for the null terminator, and will consider more than 4 bytes at a time as above with fewer comparison-related instructions, and fewer branches that can be mis-predicted.

Answer 3

The function as written is neither optimal nor portable. That having been said, the authors of C89 included some badly-written rules which if interpreted strictly make C89 a much less powerful language than the earlier C dialects that existed on many platforms. The stated purpose of the rule is to avoid requiring a C compilers which given code like:

float *fp;
int i;

int foo(void)
{
  i++;
  *fp=1.0f;
  return i;
}

from having to pessimistically assume that the write to *fp might affect i despite the complete absence of anything that would suggest that something of type int might be affected. Code which used type punning for a variety of purposes including chunking optimizations was widespread when C89 was written, but most such code would have included clear indications to the compiler that aliasing was going to occur. Generally, if an object was going to be modified by a foreign-type pointer between two "normal" accesses, one or both of the following would occur between the two normal accesses:

1. The object's address would be taken.

2. A pointer would be converted from the object's type to another type.

Aside from the obvious case where a pointer is used to access an object of its precise type, the Standard mostly identifies cases where it would not be obvious that a compiler should assume aliasing was possible (e.g. between an "int" and a pointer of type "unsigned*", or between anything and a pointer of type "char*"). Given the rationale, I think the authors intended to focus on making sure that compiler writers handled the cases where there would be no reason to expect aliasing, but didn't think they needed to be told how to identify cases where it was obviously likely.

Chunking optimizations will be safe on compilers which recognize that the address-of and casting operators imply that cross-type aliasing is likely, provided that all use of the pointer resulting from a cast is performed before the next access using the non-cast pointer--a requirement that most chunking code would generally meet. Unfortunately, there is no standard for "sane-compiler C", and gcc uses the fact that the authors of the Standard didn't require that compilers handle the obvious-aliasing cases as justification to ignore them.

Still, the performance advantages from chunking optimizations may outweigh the performance costs of -fno-strict-aliasing, especially if code uses restrict qualifiers when appropriate. There are some situations, mainly involving global variables, where restrict isn't sufficient to enable useful optimizations; those could be handled by an aliasing mode which limits analysis to objects of static or automatic duration (like the objects in the rationale's example) but gcc offers no such mode.

BTW, I'm not sure what instruction timings are like on modern x86 processors, but on some ARM variants compilers would have a chance at producing optimal long-string code from something like:

uint32_t x01000000 = 0x01000000;
uint64_t *search(uint64_t *p)
{
  uint64_t n;
  uint32_t a,b;
  uint32_t v = x01000000; // See note
  do
  {
    n=*p++;
    a=(uint32_t)n;
    b=n>>32;
    if (a >= v  || (a << 8) >= v || (a << 16) >= v || (a << 24) >= v ||
        b >= v  || (b << 8) >= v || (b << 16) >= v || (b << 24) >= v) return p;
  } while(1);      
}

Figuring out which comparison was responsible for breaking out of the loop would take extra time, but keeping such considerations out of the loop may allow the loop itself to be more efficient.

Many ARM processors have an instruction which can compare a shifted value with a register; compilers sometimes need a little help to realize that 0x01000000 should be kept in a register (a compare-with-constant instruction exists, but doesn't include a "free" shift of the register being compared), but with help they can find the compare-with-shift. I haven't yet found a way to convince a compiler to generate optimal code for the ARM7-TDMI, which would be equivalent to:

search:
    mov    r1,#0x010000000
lp:
    ldrmia r0,{r2,r3}
    cmp    r1,r2
    cmplt  r1,r2,asl #8
    cmplt  r1,r2,asl #16
    cmplt  r1,r2,asl #24
    cmplt  r1,r3
    cmplt  r1,r3,asl #8
    cmplt  r1,r3,asl #16
    cmplt  r1,r3,asl #24
    blt    lp
    bx     lr

That would take 15 cycles per eight bytes; it could be adapted to take 25 cycles per sixteen bytes. A loop that processes eight bytes individually would take 42 cycles; unrolled to sixteen bytes would be 82 cycles. The best loop I've seen compilers generate for the uint64_t based code would be 22 cycles for eight bytes--almost half again as long as the optimal code, but still about twice as fast as a version using bytes.