performance: why golang I/O are slow on this example?

[Yann Salaün]

Hi,

I programmed this toy exercise: https://www.hackerrank.com/challenges/the-grid-search. The goal is to find a pattern inside a 2D array of integers .

I have put my golang solution on this gist, with a C and a python equivalent and one input file (~5MB). https://gist.github.com/yansal/fe153577744508e4064c

The difference in performance are very surprising to me: python is 2 to 5 times slower than C, but go is two order of magnitude slower!

    ./c < z.txt  0.02s user 0.00s system 98% cpu 0.023 total
    python main.py < z.txt  0.06s user 0.00s system 96% cpu 0.066 total
    ./go < z.txt  0.78s user 0.78s system 100% cpu 1.559 total

I have the intuition that the difference is related to the input scanning and string allocation, but I can't find a way to make it go faster.

Anybody has a comment on this or on the code?

Yann

[Tad Glines]

Unlike the C stdlib, in Go fmt.Scan doesn't use buffered IO.

If you create a read buffer:

in := bufio.NewReader(os.Stdin)

And use that:

fmt.Fscan(in, ...)

then the go version will be about as fast as the C version.

On my system the run time goes from 0.125s to 0.011s; an order of magnitude increase.

-Tad

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Yann Salaün]

I updated the gist with your suggestion. The golang program now runs one order of magnitude faster. However, it still runs one order of magnitude slower than the C version.

On my system: C runs in ~50ms, python in ~125ms and go in ~450ms.

Is there any other hidden trick that I am not aware of?

Thanks for your answers,

Yann

[Robert Melton]

Try profiling your code, it is incredibly easy:
https://github.com/davecheney/profile (and
http://dave.cheney.net/2013/07/07/introducing-profile-super-simple-profiling-for-go-programs)
-- and find and crush those hotspots.

> --
> You received this message because you are subscribed to the Google Groups
> "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-nuts...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

--
Robert Melton | http://robertmelton.com

[ns...@google.com]

Profile it. If it turns out that you're losing time on Fscan, try Fscanf (avoids reflection), or better: strconv instead.

n

[Tad Glines]

It's the Fscan. And Fscanf doesn't make any better.

But, using in.ReadString makes it just as fast as the C version.

See here: https://gist.github.com/tadglines/76a9c967738a50d6bd5f

Interestingly, switching to []byte from string didn't produce any noticeable difference in speed, like I expected. This may be due to the bulk of the time being spent in something other than allocation/GC.

-Tad

--

[Dave Cheney]

Thanks for the plug Robert.

I've recently spruced up this package, hopefully making it even easier to use. You'll find it here.

github.com/pkg/profile

Dave

[branimir....@gmail.com]

Try this one:

http://pastebin.com/39g8czcL

On Tuesday, November 4, 2014 4:44:06 PM UTC+1, Yann Salaün wrote:

[Phea Duch]

Use the bufio package.

Something like

scanner := bufio.NewScanner(os.Stdin)

scanner.Split(bufio.ScanLines)

Then you can loop over each line with scanner.Scan().

I had to do this with one the challenges on HackerRank myself. Using fmt.Scan() I was timing out with 6 seconds, using the bufio package test cases were completed in ~.12 seconds. 

[egon]

Use a better algorithm :).

For small patterns it works quite well, but you can derive more interesting/faster algorithms from different search algorithms. (http://en.wikipedia.org/wiki/String_searching_algorithm)

During an algorithmics course we had to do it. My approach was something like:

1. assume you have a pattern with size RxC

2. at each R-th row in the haystack find candidates for positioning the pattern

3. test the candidates

For finding the candidates, 

setup: create a set of numbers W with a rolling hash over the rows of the pattern

1. using the rolling hash walk over the R-th row

2. at each number check whether the number is in W, then add that position with the pattern row index to the candidates

I didn't test the algorithm, but it should give quite a speed-up, if you don't have much repetition and you don't just have a single column.

Of course you can also adjust KMP or BM to work on 2D patterns.

+ egon

[Andrew Bursavich]

Reading 1,000,000 ints from raw os.Stdin with fmt.Fscan took ~24s.

Wrapping os.Stdin in a bufio.Reader got it to ~2.2s.

Wrapping os.Stdin in a bufio.Scanner and using strconv.Atoi to parse token strings got it to ~450ms.

Parsing the tokens from bufio.Scanner manually as bytes without string allocations got it to ~280ms.

http://play.golang.org/p/1qndGdxdtb

Cheers,

Andy

P.S.  +1 to what egon said.