CODEWITHSUNDEEP
cinputscanfnumeric-input
Jo So
Jo So

Reputation: 26531

Faster than scanf?

I was doing massive parsing of positive integers using scanf("%d", &someint). As I wanted to see if scanf was a bottleneck, I implemented a naive integer parsing function using fread, just like:

int result;
char c;

while (fread(&c, sizeof c, 1, stdin), c == ' ' || c == '\n')
    ;

result = c - '0';
while (fread(&c, sizeof c, 1, stdin), c >= '0' || c <= '9') {
     result *= 10;
     result += c - '0';
}

return result;

But to my astonishment, the performance of this function is (even with inlining) about 50% worse. Shouldn't there be a possibility to improve on scanf for specialized cases? Isn't fread supposed to be fast (additional hint: Integers are (edit: mostly) 1 or 2 digits)?

Upvotes: 8

Views: 8878

Answers (4)

Jo So
Jo So

Reputation: 26531

The overhead I was encountering was not the parsing itself but the many calls to fread (same with fgetc, and friends). For each call, the libc has to lock the input stream to make sure two threads aren't stepping on each other's feet. Locking is a very costly operation.

What we're looking for is a function that gives us buffered input (reimplementing buffering is just too much effort) but avoids the huge locking overhead of fgetc.

If we can guarantee that there is only a single thread using the input stream, we can use the functions from unlocked_stdio(3), such as getchar_unlocked(3). Here is an example:

static int parseint(void)
{
    int c, n;

    n = getchar_unlocked() - '0';
    while (isdigit((c = getchar_unlocked())))
        n = 10*n + c-'0';

    return n;
}

The above version doesn't check for errors. But it's guaranteed to terminate. If error handling is needed it might be enough to check feof(stdin) and ferror(stdin) at the end, or let the caller do it.

My original purpose was submitting solutions to programming problems at SPOJ, where the input is only whitespace and digits. So there is still room for improvement, namely the isdigit check.

static int parseint(void)
{
    int c, n;

    n = getchar_unlocked() - '0';
    while ((c = getchar_unlocked()) >= '0')
        n = 10*n + c-'0';

    return n;
}

It's very, very hard to beat this parsing routine, both performance-wise and in terms of convenience and maintainability.

Upvotes: 9

Boris
Boris

Reputation: 805

Here's something I use.

 #define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
 char _;

However, this only works with Integers.

Upvotes: 1

Philip
Philip

Reputation: 5917

From what you say, I derive the following facts:

  • numbers are in the range of 0-99, which accounts for 10+100 different strings (including leading zeros)
  • you trust that your input stream adheres to some sort of specification and won't contain any unexpected character sequences

In that case, I'd use a lookup table to convert strings to numbers. Given a string s[2], the index to your lookup table can be computed by s[1]*10 + s[0], swapping the digits and making use of the fact that '\0' equals 0 in ASCII.

Then, you can read your input in the following way:

// given our lookup method, this table may need padding entries
int lookup_table[] = { /*...*/ };

// no need to call superfluous functions
#define str2int(x) (lookup_table[(x)[1]*10 + (x)[0]])

while(read_token_from_stream(stdin, buf))
        next_int = str2int(buf);

On today's machines, it will be hard to come up with a faster technique. My guess is that this method will likely run 2 to 10 times faster than any scanf()-based approach.

Upvotes: -2

Timothy Jones
Timothy Jones

Reputation: 22145

You'll be able to improve significantly on your example by buffering - read a large number of characters into memory, and then parse them from the in-memory version.

If you're reading from disk you might get a performance increase by your buffer being a multiple of the block size.

Edit: You can let the kernel handle this for you by using mmap to map the file into memory.

Upvotes: 4

Related Questions