Efficient integer input / output (with a use case)

Question

The task:

A set of functions used to read/write integers from/to stdin/stdout as efficiently as possible.

Rationale:

printf/scanf fail to offer best possible performance. For example, it is possible to write a solution for UVA problem 10055 "Hashmat the Brave Warrior" that runs in below 0.01 sec, however a straightforward solution with printf / scanf typically runs in around 0.02 sec. Digit by digit input/output of numbers using getchar_unlocked and putchar_unlocked is the only way I'm aware of to make it run as fast as possible.

Result:

• Functions rd* read integers, and functions wr* write integers.
• The next few letters in the function's name describe the type the function operates on, with similar naming conventions to printf/scanf format specifiers. So for example rdllu reads an unsigned long long int, while wrhhi writes the numerical value of a signed char. (It is possible to use a function operating on unsigned integers to read / write a signed integer, this will simply skip checking if the integer is negative).
• In addition, every rd* function has a counterpart ending with eof, meaning that it checks for EndOfFile and returns 0 in that case. Functions not checking for EOF always return 1. This is to enable convenient reading a few integers in a loop like while(rdllueof(&a) && rdllu(&b)) {do_something;}.
• You might say that these names are cryptic and unreadable. Honestly though, I think they're not much worse than standard library functions like strncmpy. And definitely much better than the alternative, that is read_unsigned_long_long_int_while_checking_for_eof. If I am to avoid such long names I'm not sure what else can I devise.

Approach:

Sorry for using macros to generate these functions, that's another point I suppose you might think is wrong. But otherwise I'd have to write 30 repetitive functions, which would violate DRY pretty hard.

The code:

#include <stdio.h>

int fisdigit(int ch)
{
        return ch >= '0' && ch <= '9';
}

#define rdi_funcname_sign_1_eof_1(abbrev) rd##abbrev##ieof
#define rdi_funcname_sign_1_eof_0(abbrev) rd##abbrev##i
#define rdi_funcname_sign_0_eof_1(abbrev) rd##abbrev##ueof
#define rdi_funcname_sign_0_eof_0(abbrev) rd##abbrev##u

#define wri_funcname_sign_1(abbrev) wr##abbrev##i
#define wri_funcname_sign_0(abbrev) wr##abbrev##u

#define rwi_argtype_sign_1(type) unsigned type
#define rwi_argtype_sign_0(type) signed type

#define read_integer(type, abbrev, check_sign, check_eof) \
        int \
        rdi_funcname_sign_##check_sign##_eof_##check_eof(abbrev) \
        (rwi_argtype_sign_##check_sign(type)* n) \
        { \
                *n = 0; \
                int ch; \
                int is_neg = 0; \
                \
                do { \
                        ch = getchar_unlocked(); \
                        if(check_eof) { \
                                if(ch == EOF) \
                                        return 0; \
                        } \
                        if(check_sign) { \
                                if(ch == '-') \
                                        is_neg = 1; \
                        }\
                } while(!fisdigit(ch)); \
                \
                do { \
                        *n *= 10; \
                        *n += ch-'0'; \
                        ch = getchar_unlocked(); \
                } while(fisdigit(ch)); \
                if(check_sign) { \
                        if(is_neg) \
                                *n *= -1; \
                } \
                return 1; \
        }

#define write_integer(type, abbrev, check_sign, max_digits) \
        void \
        wri_funcname_sign_##check_sign(abbrev) \
        (rwi_argtype_sign_##check_sign(type) n) \
        { \
                size_t const buffsiz = \
                        (check_sign ? max_digits+1 : max_digits); \
                char buff[max_digits]; \
                \
                size_t i = 0; \
                if(check_sign) {  \
                        if(n < 0) \
                                buff[i++] = '-'; \
                } \
                while(n != 0) { \
                        buff[i++] = n%10; \
                        n /= 10; \
                } \
                \
                if(i == 0) \
                        putchar_unlocked('0'); \
                else \
                        while(i-- != 0) \
                                putchar_unlocked(buff[i] + '0'); \
                \
                return; \
        }


#define rwi_variations(type, abbrev, max_digits_i, max_digits_u) \
        read_integer(type, abbrev, 1, 1) \
        read_integer(type, abbrev, 1, 0) \
        read_integer(type, abbrev, 0, 1) \
        read_integer(type, abbrev, 0, 0) \
        write_integer(type, abbrev, 1, max_digits_i) \
        write_integer(type, abbrev, 0, max_digits_u)

rwi_variations(long long int, ll, 19, 20)
rwi_variations(long int, l, 10, 10)
rwi_variations(int, , 5, 5)
rwi_variations(short int, h, 5, 5)
rwi_variations(char, hh, 3, 3)

#undef rdi_funcname_sign_1_eof_1
#undef rdi_funcname_sign_0_eof_1
#undef rdi_funcname_sign_1_eof_0
#undef rdi_funcname_sign_0_eof_0
#undef wri_funcname_sign_1
#undef wri_funcname_sign_0
#undef rwi_argtype_sign_1
#undef rwi_argtype_sign_0
#undef rwi_variations
#undef read_integer
#undef write_integer

Restriction:

Must compile with ANSI C 5.3.0 - GNU C Compiler with options: -lm -lcrypt -O2 -pipe -ansi -DONLINE_JUDGE

Use case:

The solution for the aforementioned UVA Problem 10055: "Hashmat the Brave Warrior":

void wrc(char c)
{
        putchar_unlocked(c);
}

int main()
{
        unsigned long long int a, b;
        while(rdllueof(&a) && rdllu(&b)) {
                if(a > b)
                        wrllu(a-b);
                else
                        wrllu(b-a);

                wrc('\n');
        }

        return 0;
}

I added the wrc function just for consistency with the naming convention of wrllu et al. I think it's better to print everything with wr* rather than print integers with wr* and characters with putchar_unlocked.

PS

Any way to optimize this even more?

Answer 1

You worry about violating DRY, but you've violated a C standard, macros should always be all capitals.

While I don't recommend it, the fastest code would be to avoid the use of functions totally and just have the macros. Inline code should always be faster than functions, although on modern computers this is less of an issue.

The fisdigit() function can be a macro or just inline

do {
    ...
} while(ch >= '0' && ch <= '9');

For performance reasons you don't want to call a function.

Check the ctype.h file, isdigit() may be a macro, in older versions of C (pre C89 for sure, possible pre C99 ) all functions provided by ctype.h were macros.

Type Issues
The variables a and b in main are declared as unsigned long long, however the functions are expecting pointers to long long. It's also unclear that long long is required since 2^32 is the max value for either a or b.

Answer 2

1. Bug: Below fails to print digits when n<0

   buff[i++] = n%10; ... putchar_unlocked(buff[i] + '0')
   

2. if(i == 0) not needed, just use a do {} while

         do {
            buff[i++] = n%10;
         } while (n /= 10);
   

3. Bug. Wrong array size

   size_t const buffsiz = (check_sign ? max_digits+1 : max_digits); \
   // char buff[max_digits];
   char buff[buffsiz];
   

4. Why stingy on buffer size? Could simply use +1 always

   size_t const buffsiz = max_digits+1;
   char buff[buffsiz];
   

5. Bug buff[i++] = '-' ... putchar_unlocked(buff[i] + '0'); will not print a '-'.