Re: [go-nuts] Weird benchmark results for seemingly identical functions

Bakul Shah Mon, 22 Jun 2020 10:04:03 -0700

They are not equivalent. You want if !(pos < suffixLen && pos < previousSuffixLen) { break } in the second case.

On Jun 22, 2020, at 5:15 AM, Yonatan Ben-Nes <yona...@epoch.co.il> wrote:

Hi,

I'm encountering a weird issue which I fail to explain. It boils down to 2 almost identical functions which give wildly different benchmark results.

The difference between the functions is that at the slow func there is a for loop like this:
for pos := 0; pos < suffixLen && pos < previousSuffixLen; pos++ {
}

While at the fast func the loop is like this:
for pos := 0; true; pos++ {
   if pos < suffixLen && pos < previousSuffixLen {
     break
   }
}
* do note that the check at both versions is the same.

Other than that the functions are identical but when I benchmark them I get:
$ go test -bench=Weird .
goos: linux
goarch: amd64
BenchmarkWeirdFast-4 280394 3602 ns/op
BenchmarkWeirdSlow-4 1866 618953 ns/op

It's extra weird since getting the condition check into the loop should be the slower form, or at least that what I intuitively thought.

Also, the extra time cost is divided between the loop section and an append function call which run immediately at the start of the function and is not connected in any way to the for loop.
And it's extra weird as the append cost also get smaller if instead of reading the test text from a file I just declare a string variable with the same text for the benchmark (mind you that I b.ResetTimer() after doing either of those options).

I attached the files to this message as they will make everything more clear and I also added comments describing what happen at the right points.

I'm using Ubuntu 18.04 and go is version 1.14.2, and I also checked it on a GCP compute engine and got the same results.

Any thoughts will be much appreciated as I'm totally confused here! :)

--
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/3cf40b00-96ec-42a6-8093-7f1c27bfd93fn%40googlegroups.com.

--
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/E696BA2E-7AF0-4C55-9374-0C11EF585087%40iitbombay.org.

package main

// Cost around 300k ns/op (with the append at the start of the function its above 600k ns/op)
func slow(suffixArray []string) (lcp []int) {
	// This append command cost about 50% of the time cost of the entire function.
	// This extra cost happen only when the condition expression of the inline for loop below is set as it is.
	// If the aforementioned condition expression is replaced with true (like at fast()) than its fast as expected
	lcp = append(lcp, 0)


	previousSuffixLen := len(suffixArray[0])

	for i := 1; i < len(suffixArray); i++ {
		suffixLen := len((suffixArray)[i])

		// Here the condition expression is set and it makes the function way slower
		for pos := 0; pos < suffixLen && pos < previousSuffixLen; pos++ {
		}

		previousSuffixLen = suffixLen
	}
	return lcp
}

func fast(suffixArray []string) (lcp []int) {
	// Here the append line is always fast no matter if BenchmarkNeverCalled() is commented out or not
	lcp = append(lcp, 0)

	previousSuffixLen := len((suffixArray)[0])

	for i := 1; i < len(suffixArray); i++ {
		suffixLen := len((suffixArray)[i])

		// Here I set the condition expression to true and move the condition to be inside the for loop
		// It makes the function be way faster (both the loop speed and not making the append cost way more as well)
		for pos := 0; true; pos++ {
			if pos < suffixLen && pos < previousSuffixLen {
				break
			}
		}

		previousSuffixLen = suffixLen
	}

	return lcp
}

package main

import (
	"io/ioutil"
	"sort"
	"testing"
)

/*
Running the following tests without changing anything give the following results at my system:

$ go test -bench=Weird .
goos: linux
goarch: amd64
BenchmarkWeirdFast-4   	  280394	      3602 ns/op
BenchmarkWeirdSlow-4   	    1866	    618953 ns/op
PASS
ok  	_/home/nimrod/projects/sandbox/kattis/dvaput	2.284s
*/

func BenchmarkWeirdFast(b *testing.B) {
	suffixList := createSuffixList(b)
	b.ResetTimer()

	for i := 0; i < b.N; i++ {
		fast(suffixList)
	}
}

func BenchmarkWeirdSlow(b *testing.B) {
	suffixList := createSuffixList(b)
	b.ResetTimer()

	for i := 0; i < b.N; i++ {
		slow(suffixList)
	}
}

func createSuffixList(b *testing.B) []string {
	// testdata/text contain a string of 2000 random character
	// If instead of reading the file I just declare text := <sameStringAsFile> than the append line at slow is running fast no matter if BenchmarkNeverCalled() is commented or not
	text, err := ioutil.ReadFile("testdata/text")
	if err != nil {
		b.Fatal(`failed to read the text file`)
	}

	var suffixList []string
	for len(text) > 0 {
		suffixList = append(suffixList, string(text))
		text = text[1:]
	}
	sort.Strings(suffixList)

	return suffixList
}

skduhfnckzjsuhgbfkjvhdrkjnguhdkjrumhgdsjuhvflskuhefjghxdcnjkrufhxjhkxumdhekfjxduhnrkjcfguhxdrkjuvghdxkjruhmcgkjxdruhgvnjkxduhrkjfguvxdhrgklmbuhxdjrguhdkxjurhgkjxdhrgjkhxdfkjghjkdxuhrgvkdxhrjkugchdrkujhskdjhfcnklasdhfcmuhwerkfujhcseklhrfvbnlskzhfevbiwsaheflkjvhsekuy4rchgkjsdrygfkjcszhdflkjzhsklufevhszxkjehcfkjsehrgfkjshdkjfhsdrkuhfgslkdmucrhgkjsehdgrkfgjhdzxkrghnvliseduhxrgbluhsxedlmkrfghmclxdzshrgnkluvdhzxrblgkvjhdzslkrmnhgclmesrhgkvdjfhvsdhfmlahwefhklsdhflkvhsdlkumfhclsadhrefnlgknhzxdkljfhvliasuehflkhcszdlkhfmxzcjhfmzhsndkufhnsiuehflkczsmhefujvhsajehgbfjsagbkfxuaghSWuidfgbsakudrgfvkjsagefkyjncgsajekfgncjsaegnfkcjgsdkjnfgvsekuahfkjmsadhgfbkjvygawekujfghmsajeghfbkjvuyasghuikeyhrkvashefjkugjhnse4kujrthgbkjedrhtgkjudshnfkjghnsdkjhgkjmdcshmfkjghmdsjhfkjsaehvfnjshdkjfghecmkjrgfmkjdhxjmdmfjghdrfjhdnflkgjbyhsedrilukhgmclksdjhrmgkjchxdnlkjfgbnlksxdhrtglnvbdsrhgklvdhmxrlkghcsdmliruhgvlmksdrhngvjsdhrlkgjhvsldkmfhgvmlisdhrtmgilhdrgklumhdrlkumghvlrukdhmgukdhmgvlhdrmlkguhmrdkughvmkudrhmgvkhdfkjghsdlnkhgklsdhrngukhskduhfnckzjsuhgbfkjvhdrkjnguhdkjrumhgdsjuhvflskuhefjghxdcnjkrufhxjhkxumdhekfjxduhnrkjcfguhxdrkjuvghdxkjruhmcgkjxdruhgvnjkxduhrkjfguvxdhrgklmbuhxdjrguhdkxjurhgkjxdhrgjkhxdfkjghjkdxuhrgvkdxhrjkugchdrkujhskdjhfcnklasdhfcmuhwerkfujhcseklhrfvbnlskzhfevbiwsaheflkjvhsekuy4rchgkjsdrygfkjcszhdflkjzhsklufevhszxkjehcfkjsehrgfkjshdkjfhsdrkuhfgslkdmucrhgkjsehdgrkfgjhdzxkrghnvliseduhxrgbluhsxedlmkrfghmclxdzshrgnkluvdhzxrblgkvjhdzslkrmnhgclmesrhgkvdjfhvsdhfmlahwefhklsdhflkvhsdlkumfhclsadhrefnlgknhzxdkljfhvliasuehflkhcszdlkhfmxzcjhfmzhsndkufhnsiuehflkczsmhefujvhsajehgbfjsagbkfxuaghSWuidfgbsakudrgfvkjsagefkyjncgsajekfgncjsaegnfkcjgsdkjnfgvsekuahfkjmsadhgfbkjvygawekujfghmsajeghfbkjvuyasghuikeyhrkvashefjkugjhnse4kujrthgbkjedrhtgkjudshnfkjghnsdkjhgkjmdcshmfkjghmdsjhfkjsaehvfnjshdkjfghecmkjrgfmkjdhxjmdmfjghdrfjhdnflkgjbyhsedrilukhgmclksdjhrmgkjchxdnlkjfgbnlksxdhrtglnvbdsrhgklvdhmxrlkghcsdmliruhgvlmksdrhngvjsdhrlkgjhvsldkmfhgvmlisdhrtmgilhdrgklumhdrlkumghvlrukdhmgukdhmgvlhdrmlkguhmrdkughvmkudrhmgvkhdfkjghsdlnkhgklsdhrngukh

Re: [go-nuts] Weird benchmark results for seemingly identical functions

Reply via email to