x/time/rate: float64 precision loss with edge cases

[linxiulei]

What version of Go are you using (go version)?

$ go version
go version go1.16.3 linux/amd64

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

go env Output

$ go env
GO111MODULE=""
GOARCH="amd64"
GOBIN="""
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPRIVATE=""
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOVCS=""
GOVERSION="go1.16.3"
GCCGO="gccgo"
AR="ar"
CC="clang"
CXX="clang++"
CGO_ENABLED="1"
GOMOD="/dev/null"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build2658845936=/tmp/go-build -gno-record-gcc-switches"

What did you do?

Write an unittest in rate_test.go and run go test

func TestPreciseAllow(t *testing.T) {
lim := NewLimiter(0.00027777777777777778, 1)
lim.tokens = 0.54990492004805558
if !lim.Allow() {
t.Errorf("want ok, got false")
}
}

What did you expect to see?

Pass the unittest

What did you see instead?

Fail to pass the unittest

[gopherbot]

Change https://golang.org/cl/325289 mentions this issue: rate: Avoid precision loss with edge cases

[cherrymui]

Thanks for reporting. Could you explain how this is related to the loss of precision and why it is expected to work that way? Thanks.

[linxiulei]

Would you please also have a look on the PR above? Thanks

For the explanation:

The 'lim.tokens' may be end up with any value, so 0.54990492004805558 is possible, which was just a case I ran into. Then, say the time has passed a very long period, Allow() should return true. However, in the method 'advance()', we calculate maxElapsed := lim.limit.durationFromTokens(float64(lim.burst) - lim.tokens), which has float64 multiplication and division. What makes it worse, it uses maxElaspsed to produce delta, which has float64 multiplication. Any of the float64 calculation might have precision loss that results in we having token 0.999999999728, which never exceeds 1. As a result of it, Allow() never returns true

[cherrymui]

cc @Sajmani @bradfitz

[thockin]

I have a bugreport against kubernetes that comes down to this same issue. The repro we boiled down to is below. The referenced patch above (https://golang.org/cl/325289) does fix the repro case. I am not familiar enough with how this lib operates to say if it is exactly correct or is the best fix.

So I'm here to +1 the issue and ask for someone in-the-know to consider the patch above.

Another repro (let it run 8 loops):

package main

import (
    "fmt"
    "time"

    "golang.org/x/time/rate"
)

func main() {
    minInterval := 1031425 * time.Microsecond
    qps := float32(time.Second) / float32(minInterval) // don't ask
    limiter := rate.NewLimiter(rate.Limit(qps), 2)                              
    for {
        if limiter.Allow() {
            syncFunc()
            time.Sleep(2 * time.Second)
        } else {
            fmt.Printf("limiter said no, retry in 1s\n")
            time.Sleep(time.Second)
        }
    }
}

func syncFunc() {
    fmt.Printf("------------------------------- do syncFunc %v --------------------------------\n\n\n\n", time.Now())
}

[thockin]

Hi everyone. Has anyone had a moment to look at this one?

[bradfitz]

@thockin, did @josharian's https://go-review.googlesource.com/c/time/+/336469 merged a few days ago resolve this for you?