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

time: optimize time.Time.Sub and time.Since #17858

Open
dsnet opened this Issue Nov 8, 2016 · 10 comments

Comments

Projects
None yet
5 participants
@dsnet
Copy link
Member

dsnet commented Nov 8, 2016

According to a profiling data from a large number of servers at Google, time.Time.Sub is within the top 150 functions by CPU time. The current implementation of Sub is not inlineable. The logic for Sub is not particularly complicated and I believe it can be made to be inlined with some love.

@dsnet dsnet added the Performance label Nov 8, 2016

@dsnet dsnet added this to the Go1.9 milestone Nov 8, 2016

@dsnet dsnet changed the title time: optimize time.Time.Sub time: optimize time.Time.Sub and time.Time.Since Nov 8, 2016

@dsnet

This comment has been minimized.

Copy link
Member

dsnet commented Nov 8, 2016

time.Since is also a hot function. It uses Sub internally. Unfortunately, it can't be inlined since it makes a call to runtime.now.

@dsnet dsnet changed the title time: optimize time.Time.Sub and time.Time.Since time: optimize time.Time.Sub and time.Since Nov 8, 2016

@josharian

This comment has been minimized.

Copy link
Contributor

josharian commented Nov 9, 2016

Oddly, looking at the output of -gcflags="-m -m", I don't see Time.Sub listed at all, either as inlineable or non-inlineable.

@gopherbot

This comment has been minimized.

Copy link

gopherbot commented Nov 9, 2016

CL https://golang.org/cl/32971 mentions this issue.

@josharian

This comment has been minimized.

Copy link
Contributor

josharian commented Nov 9, 2016

Time.Sub currently has an inlining cost of 116, well above the current inlining threshold of 80. Some minor fiddling around (below) brings it down to 111. I don't see this happening without some compiler fixes; that is #17566. (Note that Time.Sub currently compiles into 227 bytes of code, about the same as two appends.)

// Add returns the time t+d.
func (t Time) Add(d Duration) Time {
    t.sec += int64(d / 1e9)
    t.nsec += int32(d % 1e9)
    if t.nsec >= 1e9 {
        t.sec++
        t.nsec -= 1e9
    } else if t.nsec < 0 {
        t.sec--
        t.nsec += 1e9
    }
    return t
}

// Sub returns the duration t-u. If the result exceeds the maximum (or minimum)
// value that can be stored in a Duration, the maximum (or minimum) duration
// will be returned.
// To compute t-d for a duration d, use t.Add(-d).
func (t Time) Sub(u Time) Duration {
    d := Duration(t.sec-u.sec)*Second + Duration(t.nsec-u.nsec)
    // Check for overflow or underflow.
    switch {
    case u.Add(d).Equal(t):
        return d // d is correct
    case t.Before(u):
        return minDuration // t - u is negative out of range
    }
    return maxDuration // t - u is positive out of range
}
@dsnet

This comment has been minimized.

Copy link
Member

dsnet commented Nov 9, 2016

I looked at this earlier today, and I am suspicious of the current overflow checking logic. Sub does overflow checking by checking that u.Add(d).Equal(t), which initially seems legit, but it's kinda strange since the Add method itself does not do overflow checking. Thus, I find it strange that overflow checking is depending on a function that is not overflow safe.

This is a version of Sub I came up with that is inlineable:

func (t Time) SubC(u Time) Duration {
    sec := t.sec - u.sec
    nsec := t.nsec - u.nsec // Cannot overflow; in range of [-999999999, 999999999]
    d1 := Duration(sec) * Second
    d2 := d1 + Duration(nsec) // Overflows only when nsec < 0

    overflow := (sec < u.sec) != (t.sec > 0) || // Subtraction overflow?
        (d1/Second) != Duration(sec) || // Multiplication overflow?
        (d2 < d1) != (nsec < 0) // Addition overflow?
    if !overflow {
        return d2
    }

    // Overflow can only occur if number of seconds apart is large enough.
    // Thus, we do not need to compare the nanoseconds.
    if t.sec < u.sec {
        return minDuration
    } else {
        return maxDuration
    }
}

On my machine, this version runs 3.2x faster.

@dsnet dsnet self-assigned this Dec 9, 2016

gopherbot pushed a commit that referenced this issue Feb 1, 2017

cmd/compile: report more non-inlineable functions
Many non-inlineable functions were not being
reported in '-m -m' mode.

Updates #17858.

Change-Id: I7d96361b39dd317f5550e57334a8a6dd1a836598
Reviewed-on: https://go-review.googlesource.com/32971
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>

@bradfitz bradfitz modified the milestones: Go1.10, Go1.9 May 23, 2017

@bradfitz

This comment has been minimized.

Copy link
Member

bradfitz commented May 23, 2017

Sadly bumping this to Go 1.10.

@dsnet

This comment has been minimized.

Copy link
Member

dsnet commented May 23, 2017

The inclusion of monotonic timestamps doubled the complexity of the Sub method such that my inlined version no longer works. I'm not sure how to optimize this anymore.

@dsnet dsnet removed their assignment May 23, 2017

@mvdan

This comment has been minimized.

Copy link
Member

mvdan commented Sep 14, 2017

If this is ever made inlineable, be sure to add it to TestIntendedInlining to ensure that it's kept that way - see #21851.

@bradfitz bradfitz modified the milestones: Go1.10, Unplanned Nov 15, 2017

@gopherbot

This comment has been minimized.

Copy link

gopherbot commented Apr 14, 2018

Change https://golang.org/cl/107056 mentions this issue: time: increase test coverage for Time.Sub

gopherbot pushed a commit that referenced this issue Apr 16, 2018

time: increase test coverage for Time.Sub
Existing tests don't check overflow and underflow case for subtraction
monotonic time.

Updates #17858

Change-Id: I95311440134c92eadd7d5e409a0fc7c689e9bf41
Reviewed-on: https://go-review.googlesource.com/107056
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
@gopherbot

This comment has been minimized.

Copy link

gopherbot commented Aug 24, 2018

Change https://golang.org/cl/131196 mentions this issue: time: optimize Sub

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment