Does this issue reproduce with the latest release?
Yes
What operating system and processor architecture are you using (go env)?
leetcode runtime
What did you do?
Most of time when I work on leetcode problems, go runs faster than Java .
However on the problem 26, Remove Duplicates from Sorted Array. The golang takes ~102ms compared to Java ~12ms. 10 times slower, when I am using almost the same logic.
Here attached the accepted solutions in the question.
Question :
Solution :
func removeDuplicates(nums []int) int {
lens := len(nums)
if lens==0 {return 0}
j := 0
for i := 1; i < lens; i++ {
if (nums[i]>nums[j]) {
j=j+1;
nums[j]=nums[i]
}
}
return j+1;
}
class Solution {
public int removeDuplicates(int[] nums) {
if(nums.length==0)
return 0;
int j=0;
for(int i=0;i<nums.length;i++){
if(nums[i]>nums[j])
nums[++j]=nums[i];
}
return j+1;
}
}
What did you expect to see?
I hope to understand and highlight this to see if there is a possibility to find some improvement.
What did you see instead?
There is a huge difference in the runtime in go compared to Java.
I’m not getting that problem, but it is not functioning completely as intended. Not sure why that is. Here is what I wrote on the playground: https://play.golang.org/p/vlzFCvvM4i
Looking further into this, due to the behavior of the algorithm causing a duplication, I found a better method of doing this thats still rendering a less than 0 time. Here it uses a map to record occurences: https://play.golang.org/p/0sEzAC4lRU
When I run the first solution on leetcode test cases, it still takes ~103 ms to complete all tests. For sure in Java, these 161 test cases only cost ~10ms on leetcode. I am working in solving leet code questions in 8 programming languages to get better understanding in the efficiency between languages. Apparently, go is almost always one of the top three. And so far, seldom do I find any major slow-down in go. This is one of them, I was coming here to seek for help from the language developers to see if we can have any findings.
Your 2nd solution does not compile on leetcode, as the return shall be integer, somehow I feel it’s the backend issue in the leetcode. Perhaps I shall drop this question there for their testers, as there are many hidden test case I don’t know. It must be one of them slows down the program.
Are these time measurements taken directly on leetcode? If so, what do they measure exactly? Is the binary startup time included? Is the compile time included? What flags are they using for the build?
IMHO there are just too many unkonwns here to tell where the time goes. I’d suggest running the code on a local machine, and, in case of Go, write a benchmark test to get accurate results.
From a quick look at the code, the only possible time sink I see is the parameter passing. Remember that Go has pass-by-value semantics. If the nums slice is really large, copying it may take up some of the overall execution time. Passing a pointer to the slice might (slightly) improve the speed.
Slices are already reference-like (lacking more precise terminology…).
I could potentially see bounds checking being a thing here. I’d experiment with for i, v := range nums ... compared to for i := 1, i <= ... to see what effect it has, if any. (The indexing will be different; the point is to avoid at least a couple of the nums[i] expressions.)
But, as @christophberger says, wire up a benchmark of your own for this.
Most of time, golang stands the fastest, so the compile time/ startup time /flags might not be the major cause this time.
That’s a good suggestion, I may write some test locally to see if I may find the cause. It may take a while, as I might not be lucky enough to think of a full simulation of those 161 test cases.
Does that mean Java doesn’t use pass-by-value semantics ? As in my understanding, Java is also pass-by-value.
You‘re right, this rules out the startup/compile aspect.
If the local test results reflect the results from leetcode, then I would suspect that maybe the Java compiler goes great lengths to optimize that loop. After all, it is more mature than the Go compiler.
I am not sure how Java passes arrays (my Java knowledge is quite rusty), but as @calmh pointed out, Go slices are not entirely passed by value. (I was utterly wrong on that.) Only the slice header is passed by value, and this header consists of just three values (length, capacity, and a pointer to the data). So whether or not Java passes arrays by value, Go would not have any disadvantage here.
