I recently started playing with the computer science puzzles on codeforces.com (my contest history, rather short at this point). I started this for two reasons:

• keep myself sharp
• improve my coding skills
• learn the Go programming language

In my first contest, I was forced to rewrite my solution in C++11 because the Go implementation was too slow. The problem (greed) involves reading up to 200,001 integers from standard input. The first integer tells the program how many additional integers to read and will be 1 < n ≤ 200000. The rest of the algorithm is replaced by a simple summation of the rest of the integers. Here's the first iteration of the program.

package main
import “fmt”
func main() {
n := readInt()
sum := 0
for i := 0; i < n; i++ {
sum += readInt()
}
fmt.Println(sum)
}
func readInt() int {
var n int
fmt.Scan(&n)
return n
}

Given a input file with literal 200000 followed by 200000 random integers (about 3MB):

$ time ./nobuf < numbers > /dev/null
real	0m4.406s
user	0m1.450s
sys	0m2.912s

Whoa! 4.5 seconds to read 200000 integers and sum them? How about C++11? Here’s what I thought was an equivalent program in C++:

#include 

using namespace std;

int main() {
    int n, sum = 0, amt;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> amt;
        sum += amt;
    }
    cout << sum << endl;
 }

And the result…

$ time ./sum-c++ < numbers > /dev/null
real	0m0.006s
user	0m0.002s
sys	0m0.002s

6ms seems right to me… what on earth is happening here?! A bit of research (after the contest) and I ran across a thread lamenting the same problem. It turns out that by default, Go uses unbuffered I/O. Ok, fine, let’s switch to buffered I/O:

package main

import (
   "bufio"
   "fmt"
   "os"
   "strconv"
)

func solve() {
    n := readInt()
    sum := 0
    for i := 0; i < n; i++ {
        sum += readInt()
     }
     fmt.Println(sum)
}

var scanner *bufio.Scanner

func main() {
    scanner = bufio.NewScanner(os.Stdin)
    scanner.Split(bufio.ScanWords)
    solve()
}

func readString() string {
    scanner.Scan()
    return scanner.Text()
}

func readInt() int {
    val, _ := strconv.Atoi(readString())
    return val
}

And results:

$ time ./gobufs < numbers > /dev/null
real    0m0.059s
user    0m0.047s
sys     0m0.010s

That’s 2 orders of magnitude better, but still an order slower than C++11 (0.059s vs 0.006ms). What’s going on here is that we’re building a scanner object which will scan standard input and break it into words. Unlike the defaults, this scanner will buffer input from standard input.

There’s probably a way to make it faster, but at least for the next contest, I will hopefully experience fewer TIME_LENGTH_EXCEEDED errors because of unbuffered reads of the input!