Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

cmd/compile: poor performance when accessing slices for numerical work (multiplying vectors) #6206

Open
gopherbot opened this issue Aug 21, 2013 · 8 comments
Milestone

Comments

@gopherbot
Copy link

by dean.w.schulze:

Running the enclosed code the best runtime is 6.45 seconds.  The same code in Java (JDK
1.7) runs in 4.8 seconds, a serious performance hit.

For simple slice (go) / array (Java) access I would expect similar runtime performance.

Go and Java code is below.


Which operating system are you using?
go version go1.1.2 linux/amd64
This is a VM running on OSX host.  Similar results on Windows 7 64-bit

============================================================

package main

import (
    "fmt"
    "time"
)


func main() {
    
    sz := 100000
    sl1 := make([]int32, sz)

    for j := range sl1 {

        sl1[j] = int32(j)
    }

    sl2 := make([]int32, sz)

    for j := range sl2 {

        sl2[j] = int32(j*2)
    }

    multiplySlices(sl1, sl2)
    multiplySlices_(sl1, sl2)
    multiplySlices__(sl1, sl2)
}



func multiplySlices(sl1 []int32, sl2 []int32) {

    start := time.Now()
    var num int64 = 0
    for _, n1 := range sl1 {

        var n int64 = 0
        for _, n2 := range sl2 {

            n +=  int64(n1 * n2)
        }

        num += n
    }

    et := time.Since(start)
    fmt.Println("")
    fmt.Println("multiplySlices")
    fmt.Println(et)
    fmt.Println(num)
}


func multiplySlices_(sl1 []int32, sl2 []int32) {

    start := time.Now()
    var num int64 = 0
    for _, n1 := range sl1 {

        for _, n2 := range sl2 {

            num +=  int64(n1 * n2)
        }
    }

    et := time.Since(start)
    fmt.Println("")
    fmt.Println("multiplySlices_")
    fmt.Println(et)
    fmt.Println(num)
}


func multiplySlices__(sl1 []int32, sl2 []int32) {

    start := time.Now()
    var num int64 = 0
    for i := range sl1 {

        n := sl1[i]
        for j := range sl2 {

            num +=  int64(n * sl2[j])
        }
    }

    et := time.Since(start)
    fmt.Println("")
    fmt.Println("multiplySlices__")
    fmt.Println(et)
    fmt.Println(num)
}


=======================================================================


package arraytest;

import java.util.Date;

public class Driver {
    public static void main(String[] args) {
        int sz = 100000;
        int[] arr1 = new int[sz];
        int[] arr2 = new int[sz];
        for (int i = 0; i < sz; i++) {
            arr1[i] = i;
            arr2[i] = i * 2;
        }
        
        mutiplyArrays(arr1, arr2);
        mutiplyArrays_(arr1, arr2);
        
    }

    private static void mutiplyArrays(int[] arr1, int[] arr2) {
        
        int sz = arr1.length;
        Date start = new Date();
        long num = 0;
        for (int i = 0; i < sz; i++) {
            int n = arr1[i];
            long acc = 0;
            for (int j = 0; j < sz; j++) {
                acc += n * arr2[j];
            }
            
            num += acc;
        }
        Date end = new Date();
        long l = end.getTime() - start.getTime();
        System.out.println(l + " ms.");
        System.out.println(num);
    }
    

    private static void mutiplyArrays_(int[] arr1, int[] arr2) {
        
        int sz = arr1.length;
        Date start = new Date();
        long num = 0;
        for (int i = 0; i < sz; i++) {
            int n = arr1[i];
            for (int j = 0; j < sz; j++) {
                num += n * arr2[j];
            }
        }
        Date end = new Date();
        long l = end.getTime() - start.getTime();
        System.out.println(l + " ms.");
        System.out.println(num);
    }

}
@jayschwa
Copy link
Contributor

Comment 1:

Out of curiosity, what kind of vector multiplication is this? It does not look like the
two kinds I am familiar with (matrix multiplication and dot product).

@gopherbot
Copy link
Author

Comment 2 by dean.w.schulze:

This isn't really vector multiplication.  It's a test case I wrote to see if slice
access is slow after noticing a performance difference between Java and Go when doing
vector multiplication.  
Part of the problem is that the var num declared outside of the outer loop isn't stored
in a register.  That's why the var n declaration inside the outer loop gives more than a
factor of 2 speed up.  Even with that optimization there is still a significant
performance hit.

@remyoudompheng
Copy link
Contributor

Comment 3:

It's almost the same thing as sum(sl1) * sum(sl2).

@remyoudompheng
Copy link
Contributor

Comment 4:

Labels changed: added performance.

@robpike
Copy link
Contributor

robpike commented Aug 24, 2013

Comment 5:

Labels changed: added priority-later, removed priority-triage.

Status changed to Accepted.

@rsc
Copy link
Contributor

rsc commented Nov 27, 2013

Comment 6:

Labels changed: added go1.3maybe.

@rsc
Copy link
Contributor

rsc commented Dec 4, 2013

Comment 7:

Labels changed: added release-none, removed go1.3maybe.

@rsc
Copy link
Contributor

rsc commented Dec 4, 2013

Comment 8:

Labels changed: added repo-main.

@rsc rsc added this to the Unplanned milestone Apr 10, 2015
@rsc rsc changed the title cmd/6g: Poor performance when accessing slices for numerical work (multiplying vectors) cmd/compile: poor performance when accessing slices for numerical work (multiplying vectors) Jun 8, 2015
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

5 participants