4
\$\begingroup\$

In some (perhaps not well-designed) competitive programming problems, the runtime and score is dependent on how fast your program can process input. Therefore I've written a small C99 library with optimized functions for reading from stdin and writing to stdout:

fastio.h:

#ifndef FASTIO_H
#define FASTIO_H

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

#ifdef _WIN32
#define putchar_unlocked putchar
#else
#include <unistd.h>
#include <sys/mman.h>
#include <sys/stat.h>
#endif

// Fast IO routines accessing stdin and stdout. The purpose of them is
// to reduce IO overhead in competitive programming. Therefore, no
// error checking anywhere.

// On Linux and OS X, this is a pointer to stdin's next character. On
// Windows, standard getchar() is used and the pointer
// is NULL.
extern char *
FAST_IO_STDIN;

void
fast_io_init();

// Reading
inline char
fast_io_read_char() {
#ifdef _WIN32
    return getchar();
#else
    return *FAST_IO_STDIN++;
#endif
}

inline unsigned int
fast_io_read_unsigned_int() {
    int val = 0;
#ifdef _WIN32
    while (true) {
        char c = getchar();
        if (c < '0') {
            ungetc(c, stdin);
            break;
        }
        val = val * 10 + c - '0';
    }
#else
    do {
        val = val*10 + *FAST_IO_STDIN++ - '0';
    } while(*FAST_IO_STDIN >= '0');
#endif
    return val;
}

inline int
fast_io_read_int() {
    int val = 0;
    int sgn = 1;

#ifdef _WIN32
    char c = getchar();
    if (c == '-') {
        sgn = -1;
    } else {
        ungetc(c, stdin);
    }
    while (true) {
        char c = getchar();
        if (c < '0') {
            ungetc(c, stdin);
            break;
        }
        val = 10 * val + c - '0';
    }
#else
    if (*FAST_IO_STDIN == '-') {
        sgn = -1;
        FAST_IO_STDIN++;
    }
    do {
        val = val*10 + *FAST_IO_STDIN++ - '0';
    } while(*FAST_IO_STDIN >= '0');
#endif
    return val * sgn;
}

// Writing
inline void
fast_io_write_char(char ch) {
    putchar_unlocked(ch);
}

inline void
fast_io_write_long(long n) {
    if (n < 0) {
        putchar_unlocked('-');
        n *= -1;
    } else if (n == 0) {
        putchar_unlocked('0');
        return;
    }
    long N = n;
    long rev = N;
    int count = 0;
    rev = N;

    while ((rev % 10) == 0) {
        count++; rev /= 10;
    }
    rev = 0;
    while (N != 0) {
        rev = (rev<<3) + (rev<<1) + N % 10; N /= 10;
    }
    while (rev != 0) {
        putchar_unlocked(rev % 10 + '0');
        rev /= 10;
    }
    while (count--) {
        putchar_unlocked('0');
    }
}
#endif

fastio.c

#include "fastio.h"

char *
FAST_IO_STDIN = NULL;

void
fast_io_init() {
#ifdef _WIN32
    // Nothing to do on Windows because we use standard getchar().
#else
    int flags = MAP_SHARED;
#ifdef __linux__
    // Prefills the buffer.
    flags |= MAP_POPULATE;
#endif
    struct stat sb;
    (void)fstat(STDIN_FILENO, &sb);
    FAST_IO_STDIN = (char*)mmap(0, sb.st_size,
                                PROT_READ, flags, STDIN_FILENO, 0);
#endif
}

extern inline char fast_io_read_char();
extern inline unsigned int fast_io_read_unsigned_int();
extern inline int fast_io_read_int();
extern inline void fast_io_write_char(char ch);
extern inline void fast_io_write_long(long n);

I want the library to work on Windows, Linux and OS X, but performance only matters on Linux because bots for competitive programming only run on Linux. As the goal is to shave off milliseconds to win contests, there is absolutely no error checking.

Does anyone have any ideas how to make it even faster?

\$\endgroup\$
3
\$\begingroup\$

On Windows, you'd rather use the console API directly instead of stdio.h. This should increase performance somewhat, since these functions are what getchar etc will end up calling anyhow.

Other issues:

  • All functions should be declared to take void as parameters, rather than to accept any parameter. If they are properly inlined this should hopefully not have any impact on the program, but in some cases it might mess up the calling convention.
  • Rather than making a mess with compiler switch #ifdef all over the place, you could in the header file do something like:

    #ifdef _WIN32
      #define fast_io_read_char fast_io_read_char_windows
    #else
      #define fast_io_read_char fast_io_read_char_linux
    #endif
    

    And so on. Then separate the implementation of each function, so that you have one file fastio_windows.c and one fastio_linux.c. You can add both files to linking both no matter, the #ifdef in the header will determine which functions that actually get linked to the binary.

  • Left shifting the signed type long rev is questionable code - you have to ensure that n is never negative or too large.
  • Missing #include <stdbool.h> so the code won't compile.
  • getchar calls incorrectly use char instead of int so the code cannot handle EOF. If you don't intend to handle EOF, then you should still cast the result of getchar() to char - to silence compiler warnings and write self-documenting code that shows that you have considered this.
\$\endgroup\$
  • \$\begingroup\$ Thank you. I think inline functions in libraries need to be declared in that way. See this SO answer. But maybe there's a better way. \$\endgroup\$ – Björn Lindqvist Jan 8 at 16:21
  • \$\begingroup\$ @BjörnLindqvist Ah right, that remark isn't correct, I just found it odd to find them in the .c file. But technically they can be anywhere in the translation unit. I did however notice a few other issues just now. Post updated. \$\endgroup\$ – Lundin Jan 9 at 7:38

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.