Generating letter combinations

Question

It's about two months since I posted this question on CodeReview. I've been working hard to improve the code posted there and came up with the following.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned long long ull;

int main(void) {

    ull start=1, stop=100,cnt;
    register int t,len;
    char *str=calloc(33,sizeof(char));
    char *Alpha="abcdefghijklmnopqrstuvwxyz", *p1, *p2;
    int a_len=(int)strlen(Alpha);

    for (;start<=stop;++start) {

        cnt=start;

        /*
            This is used to construct a string from given alphabet.
            The generated string must be reversed
        */
        for (t = 0, len = 0; cnt; cnt = (cnt-1)/a_len, ++str, ++len, ++t) 
            *str = Alpha[(cnt-1) % a_len];

        /* 
            A bit odd but working (and important!) part of this code.
            As the str pointer was incremented during string generation,
            we need to 'reverse' it. 
        */
        while ( t-- ) str--;

        /* 
            This is used to reverse a string instead of strrev
        */
        for (p1 = str, p2 = str+len-1; p2>p1; ++p1, --p2) {
            *p1 ^= *p2;
            *p2 ^= *p1;
            *p1 ^= *p2;
        }

        printf("%llu --- %s\n",start,str);
    }

    free(str);

    return 0;
}

As you could have already guessed, this code generates letter combinations. The 'reversing' of a pointer (I'm not quite sure how to call this properly) is necessary because if one doesn't do that, he'll get a SegmentationFault as he'll be trying to access unallocated memory.

Example output

1 --- a
2 --- b
3 --- c
4 --- d
5 --- e
6 --- f
7 --- g
8 --- h
9 --- i
10 --- j

< omitted >

91 --- cm
92 --- cn
93 --- co
94 --- cp
95 --- cq
96 --- cr
97 --- cs
98 --- ct
99 --- cu
100 --- cv

This works quite well but I was wondering if it is possible to do the same thing even faster, if it is possible to omit the 'pointer revering' business.

Note: this code is different from the one I linked this question to because it doesn't use a function, thus, the technique and the algorithm are very different.

Answer 1

Do you really need this:

typedef unsigned long long ull;

Will a long or an int not just work (1 .. 100) fit nicely in these types.

One variable declaration per line.
You are not helping the compiler by making less lines of code (it will work just as well with more). But humans who have to read this will work better with cleaner more readable code.

ull start=1, stop=100,cnt;

A register declaration. Wow. I have not seen one of those in a while (20 years). The optimizer is much better than you at deciding what fits in a register let it do its job. I would even bet this keyword is ignored nowadays.

register int t,len;

Do you realy need to cast the result here?

int a_len=(int)strlen(Alpha);

That could would look a lot clearer without the cast. I would only keep it if the compiler is generating a warning. (but then I may change the type of a_len to be the correct type (but I am a C++ programmer and correct types is important to me).

This seems like a complicated way

 while ( t-- ) str--;

of saying:

 // Or
 str -= t;
 t    = 0;

WTF!!!!

        *p1 ^= *p2;
        *p2 ^= *p1;
        *p1 ^= *p2;

Why O Why do you use this. Its a obfuscated way of swapping two values. Just swap the two values using a temporary. The compiler will use any tricks it has internally to do this as fast as possible (probably using a register and two memory accesses rather than 3 memory accesses (which will be slower)).

Seems to me like you are trying to manually do peephole optimizations that the compiler is already doing for you. The compiler is better than you at these optimizations so the only thing you are doing is screwing with the compilers ability to perform these optimizations probably resulting in slower code.

Humans are bad at this, compilers are very very very good. Humans are good at algorithmic optimizations compilers are bad at this. Do what humans do best and let the compiler to what it is good at.

Answer 2

1. Overall code does not convey "Generating letter combinations". Simply using a function in main() called Generating_letter_combinations(const char *Alpha) would help.

2. Prefer the, IMO, easier to code and maintain allocation style of the following. sizeof(char) is pointless as it is always 1.

   // char *str=calloc(33,sizeof(char));
   char *str = calloc(33, sizeof *str);
   

3. 33 is a naked magic number. Give it some self-documentation and explain why 33. Same for stop=100. What is the 100 about?

   // char *str=calloc(33,sizeof(char));
   #define MAX_STR_SIZE (33)
   char *str = calloc(MAX_STR_SIZE, sizeof *str);
   

4. Make pointers to constant strings const to allow certain optimizations and prevent mis-use.

   char *Alpha="abcdefghijklmnopqrstuvwxyz";
   const char *Alpha = "abcdefghijklmnopqrstuvwxyz";
   

5. Consider using type size_t for array sizes and indexes. Not a big concern to small strings, but a better programming paradigm as SIZE_MAX may exceed INT_MAX. In this case also size_t cnt, start, stop. Watch out for values "below" 0 then - it appears your code is OK for that.

   // int a_len=(int)strlen(Alpha);
   size_t a_len = strlen(Alpha);
   

6. Watch out for 0-length strings like "". Better not compute p = str+0-1 which is UB.

   // for (p1 = str, p2 = str+len-1; p2>p1; ++p1, --p2) {
   if (len > 0) 
     for (p1 = str, p2 = str+len-1; p2>p1; ++p1, --p2) {
   

7. Since start is type llu which could change, (there is no comment near typedef unsigned long long ull saying this is just shorthand) make the format adjustable too near the same place ull is defined.

   typedef unsigned long long ull
   #define PRT_ull "llu"
   ...
   // printf("%llu --- %s\n",start,str);
   printf("%" PRT_ull " --- %s\n", start, str);
   

8. register is rarely useful today, use sparingly.

   // register int t,len;
   int t, len;
   

9. Inconsistent spacing. Recommend consistency. Suggest var = foo. Better yet, use an auto formatter.

   //       vv --- no space
   int a_len=(int)strlen(Alpha);
   ...
   cnt = (cnt-1)/a_len
   // ^ ^ --- space
   

10. Variables names t, p1, p2 convey too little meaning.

All-in-all. OK code, put recommend another review after amendments.