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

proposal: time: add Instant type exposing Monotonic Time #61765

Closed
deankarn opened this issue Aug 4, 2023 · 17 comments
Closed

proposal: time: add Instant type exposing Monotonic Time #61765

deankarn opened this issue Aug 4, 2023 · 17 comments

Comments

@deankarn
Copy link

deankarn commented Aug 4, 2023

This will be short a suite as it's pretty basic.

There is appetite to have access to Monotonic Time in Go from previous issues, proposals and requests.

Proposed Additions

I propose adding a new type to the time package called Instant which will represent an opaque type that can only be compared with one another and allows measuring of duration. An existing implementation can be found here exert posted below for convenience.

package timeext

import "time"

// Instant represents a monotonic instant in time.
//
// Instants are opaque types that can only be compared with one another and allows measuring of duration.
type Instant int64

// NewInstant returns a new Instant.
func NewInstant() Instant {
	return Instant(NanoTime())
}

// Elapsed returns the duration since the instant was created.
func (i Instant) Elapsed() time.Duration {
	return time.Duration(NewInstant() - i)
}

// Since returns the duration elapsed from another Instant, or zero is that Instant is later than this one.
func (i Instant) Since(instant Instant) time.Duration {
	if instant > i {
		return 0
	}
	return time.Duration(i - instant)
}

This will allow access to Monotonic Time from Go, that already exists, but yet unexposed except through time.Time. The reason this is necessary is that time.Time is a very heavy structure and has a bunch of overhead that is not necessary if only measuring monotonically increasing time such as when used in Benchmarking and very hot code paths.

@gopherbot gopherbot added this to the Proposal milestone Aug 4, 2023
@gophun
Copy link

gophun commented Aug 4, 2023

The whole point of https://go.googlesource.com/proposal/+/master/design/12914-monotonic.md was to avoid exposing monotonic clocks.

@deankarn
Copy link
Author

deankarn commented Aug 4, 2023

OK...AND... this is a new proposal to expose them, for good reasons.

I do not agree that it should not be exposed.

@apparentlymart
Copy link

The linked earlier proposal that added monotonic time as an implementation detail describes the rationale for not exposing a separate monotonic API: that having two different APIs which behave exactly the same except during very occasional events like a leap second invites bugs where people use the wrong one.

However, I can see some subtlety in that argument: having two separate APIs where one is a strict subset of the other would seem to avoid the bug hazard and instead offer two APIs that both correctly handle monotonic time but where one of them is free of the overhead of also tracking wallclock time.

That seems like a plausible argument in theory, but I expect the best way to argue the value of such an addition would be to demonstrate:

  • That the overhead of tracking wallclock time in systems that only need monotonic time is material for several specific applications, and
  • That the overhead of tracking wallclock time cannot be reduced or eliminated as an implementation detail, without changing the API design.

I don't have a strong opinion about this myself. I offer the above just as an idea for how to add new information that might motivate revisiting the conclusions from that earlier proposal. It isn't typically sufficient only to disagree with the previous outcome without adding new information.

@deankarn
Copy link
Author

deankarn commented Aug 5, 2023

I have read the paper before and what it's describing sounds very much like the different of SystemTime and Instant.

I'll refer to Rust's types because I think their documentation explains it better than I could ever.

I understand the rational of trying to limit the API surface area and hiding some lower level concepts and complexity under time.Time, however, in doing so and not exposing the other ways of dealing with time limits the Go language and specific, even if niche, valid use cases.

Maybe My proposal should be to add both SystemTime and Instant rather than just Instant.

In either case I am only interested in Monotonic time at this moment, here are some performance reasons, using the existing linked code in the proposal, I think this new type would benefit some real world libraries involving as caches, benchmarking and metrics off the top of my head.

func BenchmarkTime(b *testing.B) {
	for i := 0; i < b.N; i++ {
		instant := time.Now()
		_ = time.Since(instant)
	}
}

func BenchmarkInstant(b *testing.B) {
	for i := 0; i < b.N; i++ {
		instant := timeext.NewInstant()
		_ = instant.Elapsed()
	}
}

--- Result

goos: darwin
goarch: arm64
pkg: test
BenchmarkTime-8         16162813                66.93 ns/op            0 B/op          0 allocs/op
BenchmarkInstant-8      34626579                34.55 ns/op            0 B/op          0 allocs/op

Just dealing with Instant and not the additional time same approximately 50% of the time, on my machine at least. But that's not the whole story either, there's also the size different of representing each in memory:

	fmt.Println(unsafe.Sizeof(time.Now()))
	fmt.Println(unsafe.Sizeof(timeext.NewInstant()))

-----

// 24
// 8

time.Time is 3x more expensive memory wise than a primitive type to monitor monotonic time alone.

@dsnet
Copy link
Member

dsnet commented Aug 5, 2023

For prior art, @tailscale has tstime.Now, which is basically what this proposal is asking for. A fast monotonic clock reading is useful in high-throughput packet processing.

@rsc
Copy link
Contributor

rsc commented Aug 9, 2023

From an API standpoint, start := time.Now(); ...; d := time.Since(start) is just about perfect. I do not want to introduce a second API to do that calculation. Among other things, the next thing that will happen is tons of CLs updating that idiom all over the place to use the new API. And what happens on systems without monotonic time? And so on and so on. Perhaps we can find a way to optimize this sequence instead. Let's look at the space and cpu costs separately.

For space, I find it very hard to believe the 24 vs 8 bytes matters at all. No one is making giant arrays of Instants. They're only subtracting them. People who really really care about the space can declare

var globalStart = time.Now()

and then store arrays of durations since globalStart.

For cpu, there is a factor of two in querying the time, since time.Now fetches wall time and monotonic time, and both have roughly the same cost (the RDTSC or equivalent, which takes O(10-30ns)). Later, when Since is used, the code already knows to fetch only monotonic time when that's all it needs. So for a Now+Since pair, we are fundamentally talking about optimizing 3 time fetches down to 2, or making the sequence 33% faster. (Benchmark at end confirming my claims.) So how can we get rid of that extra fetch?

People who really need to optimize away 50% of time.Now today already can do that:

// global
var base = time.Now()

// timing specific code
start := time.Since(base)
...
d := time.Since(base) - start

(tstime/mono.now could do the same thing – return int64(time.Since(baseWall)) – instead of linkname subterfuge.)

Given that there is a portable way to optimize away the one extra RDTSC already, I don't think it's terribly urgent to make an API change here, especially one that doubles the number of time types.


In the long term, I wonder if we can pressure the operating systems to add a function that gets a matched pair of both times. I'm not sure how much Windows or macOS matter anyway. For Linux the kernel vdso provides the accessors, and the two accessors do exactly the same thing except for which offset they add. Perhaps we could convince the Linux kernel team to accept a patch adding a "get both" call.


Benchmark
package timebench

import (
	"testing"
	"time"
	_ "unsafe"
)

var now time.Time
var d time.Duration

func BenchmarkTimeNow(b *testing.B) {
	for i := 0; i < b.N; i++ {
		now = time.Now()
	}
}

func BenchmarkTimeSince(b *testing.B) {
	for i := 0; i < b.N; i++ {
		d += time.Since(now)
	}
}

//go:linkname nanotime runtime.nanotime
func nanotime() int64

var inow int64
var id int64

func BenchmarkNanotime(b *testing.B) {
	for i := 0; i < b.N; i++ {
		inow = nanotime()
	}
}

func BenchmarkNanosince(b *testing.B) {
	for i := 0; i < b.N; i++ {
		id += nanotime() - inow
	}
}

@rsc
Copy link
Contributor

rsc commented Aug 9, 2023

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.
— rsc for the proposal review group

@rsc rsc changed the title proposal: time: Add Instant type exposing Monotonic Time proposal: time: add Instant type exposing Monotonic Time Aug 10, 2023
@rsc
Copy link
Contributor

rsc commented Aug 10, 2023

CL 518135 has an optimization of time.now on Linux that avoids the second RDTSC in exchange for a few extra seqlock checks: instead of doing two regular clock_gettime, it does one regular clock_gettime and three coarse clock_gettime.
Specifically, it does

  1. coarse realtime
  2. coarse monotime
  3. accurate realtime
  4. coarse realtime

If (1) and (4) match, then 1, 2, 3, and 4 are all based on the same vdso time parameter update, meaning we can derive accurate monotime = (3) - (1) + (2).

On a relatively old (2014) Intel chip:

goos: linux
goarch: amd64
cpu: Intel(R) Xeon(R) CPU E5-2690 v3 @ 2.60GHz
BenchmarkTimeNow-48      	34610529	        32.72 ns/op
BenchmarkTimeNow-48      	36555846	        31.50 ns/op
BenchmarkTimeNow-48      	38082440	        31.24 ns/op
BenchmarkTimeSince-48    	53753678	        23.07 ns/op
BenchmarkTimeSince-48    	54047199	        23.06 ns/op
BenchmarkTimeSince-48    	50990598	        22.60 ns/op
BenchmarkNanotime-48     	56250726	        21.05 ns/op
BenchmarkNanotime-48     	57996276	        20.93 ns/op
BenchmarkNanotime-48     	53579763	        21.33 ns/op
BenchmarkNanosince-48    	51618572	        20.85 ns/op
BenchmarkNanosince-48    	54901424	        21.35 ns/op
BenchmarkNanosince-48    	58051893	        21.03 ns/op
PASS

On a relatively new (2022) AMD chip:

goos: linux
goarch: amd64
cpu: AMD Ryzen 9 7950X 16-Core Processor            
BenchmarkTimeNow-32      	60488217	        19.15 ns/op
BenchmarkTimeNow-32      	62665620	        18.61 ns/op
BenchmarkTimeNow-32      	64010760	        19.12 ns/op
BenchmarkTimeSince-32    	69519552	        17.10 ns/op
BenchmarkTimeSince-32    	69622921	        16.71 ns/op
BenchmarkTimeSince-32    	69680964	        16.37 ns/op
BenchmarkNanotime-32     	76564293	        16.15 ns/op
BenchmarkNanotime-32     	78482005	        15.08 ns/op
BenchmarkNanotime-32     	76783846	        15.09 ns/op
BenchmarkNanosince-32    	75900324	        15.91 ns/op
BenchmarkNanosince-32    	72681342	        15.81 ns/op
BenchmarkNanosince-32    	77141396	        15.82 ns/op

That is, on the old Intel chip, with the optimization, Now+Since takes (31+22)/(21+21) = 1.25X longer than optimal,
while on the new AMD chip, with the optimization, Now+Since takes (19+17)/(15+16) = 1.16X longer than optimal.
Without the optimization, it's more like (2+1)/(1+1) = 1.5X longer than optimal.

It is still difficult for me to understand the situation where 15ns overhead (for just time.Now) is no big deal but 30ns is a problem. Or where 30ns (for Now+Since) is no big deal but 45ns is a problem.

If we can drop the comparisons to 15 vs 19 and 31 vs 36 then I assume that situation gets even less compelling as a rationale
for whole new APIs.

Anyone is welcome to check out CL 518135 and see how it speeds up their systems. It is linux/amd64-only.

@rsc
Copy link
Contributor

rsc commented Aug 10, 2023

And again anyone who really needs direct monotonic time access at the fastest possible speed already has a portable way to do that (time.Since against a reference time).

@deankarn
Copy link
Author

what happens on systems without monotonic time?

Curious, how would/does the existing Time handle that same possibility?

@deankarn
Copy link
Author

Very cool, didn't know that when time.Since is used, the code already knows to fetch only monotonic time when that's all it needs 👍

So I'm convinced that the existing API can be leveraged to get the same speedup as direct monotonic time access given all the above :)

var base = time.Now()

// timing specific code
start := time.Since(base)
...
d := time.Since(base) - start

Wondering if the conversation could be shifted then from performance to easy of use. The following 100% works but is a little verbose to write, maybe that's ok in the pursuit of this kind of performance, but wanted to float the idea of leveraging existing Time API, not creating a new one, for a new Instant type instead. Then the justification for Instant could be for code clarity/intent and ease of use.

What would you think about something like this?

var base = time.Now()

// Instant represents a monotonic instant in time.
//
// Instants are opaque types that can only be compared with one another and allows measuring of duration.
type Instant int64

// NewInstant returns a new Instant.
func NewInstant() Instant {
	return Instant(time.Since(base))
}

// Elapsed returns the duration since the instant was created.
func (i Instant) Elapsed() time.Duration {
	return time.Since(base) - time.Duration(i)
}

// Since returns the duration elapsed from another Instant, or zero is that Instant is later than this one.
func (i Instant) Since(instant Instant) time.Duration {
	if instant > i {
		return 0
	}
	return time.Duration(i - instant)
}

Then could be use like so just as before just some complexity hidden under the hood:

start := time.NewInstant()
...
d := start.Elapsed()

An example of code clarity using Instant vs Duration

var maxCacheAge time.Duration

type cacheNode struct {
    ...
    added time.Instant
}

vs

type cacheNode struct {
    ...
    added time.Duration
}

Although the added values would be the same, the intent of what the variable/code is being used for/is doing is a little more clear.

Again floating the idea and would be curious your thoughts.

@rsc
Copy link
Contributor

rsc commented Aug 10, 2023

Curious, how would/does the existing Time handle that same possibility?

time.Time uses monotonic times when available (all the major operating systems) and otherwise falls back to non-monotonic time.

So I'm convinced that the existing API can be leveraged to get the same speedup as direct monotonic time access given all the above :)

I'm convinced we can get the same speedup as direct monotonic time access by optimizing time.Now. It may take a little while to get completely down to the same speed, but new APIs last forever. I don't think we need to add new API.

but wanted to float the idea of leveraging existing Time API, not creating a new one, for a new Instant type instead.

I think that kind of Instant type is fine to define in your own package. Once we fix the speed of time.Now, the only benefit of Instant will be that it's 8 bytes instead of 24. If you have a ton of these, maybe that matters. In that case, defining your own smaller type makes sense.

That is, given the choice between time.Instant and time.Duration in the cacheNode, I would choose time.Time instead. If a time.Time was too big, then I would define my own unexported type, private to the cache, justified by whatever optimizations I wanted. Maybe it would even make sense to coarsen it to 4 bytes, depending on context. That's a good decision to make inside a specific package. I agree that direct use of Duration is not the clearest way to write that code.

If we add Instant to package time, it is absolutely a new API. I don't think "storing so many times that 24 bytes is too much" comes up often enough in practice to be worth new API in package time.

In your own API, anything you want is fine. 😄 That said, for my reading I don't think Since is the right name. In package time, Since is a top-level function: time.Since(t) is clear and means what the English phrase "time since t" means. When Since is a method on Instant, then i.Since(j) is not clear at all and has no English analogue. It seems like i.Sub(j) would be clearer (and align with Durations).

@gopherbot
Copy link

Change https://go.dev/cl/518336 mentions this issue: time: make time.Since a few nanoseconds faster

gopherbot pushed a commit that referenced this issue Aug 11, 2023
time.Since(base) is an idiom that can be used to read the system
monotonic time as efficiently as possible, when that matters.
The current code structure adds a few nanoseconds on top of
the 15-20ns the time read already takes. Remove those few.

After this CL, there is no reason at all for anyone to
//go:linkname runtime.nanotime1 instead.

Came up while investigating #61765.

Change-Id: Ic9e688af039babfc2a5a8e67dcbb02847a5eb686
Reviewed-on: https://go-review.googlesource.com/c/go/+/518336
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Damien Neil <dneil@google.com>
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Joseph Tsai <joetsai@digital-static.net>
bradfitz pushed a commit to tailscale/go that referenced this issue Aug 11, 2023
time.Since(base) is an idiom that can be used to read the system
monotonic time as efficiently as possible, when that matters.
The current code structure adds a few nanoseconds on top of
the 15-20ns the time read already takes. Remove those few.

After this CL, there is no reason at all for anyone to
//go:linkname runtime.nanotime1 instead.

Came up while investigating golang#61765.

Change-Id: Ic9e688af039babfc2a5a8e67dcbb02847a5eb686
Reviewed-on: https://go-review.googlesource.com/c/go/+/518336
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Damien Neil <dneil@google.com>
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Joseph Tsai <joetsai@digital-static.net>
(cherry picked from Go commit 4467839)

See tailscale/tailscale#8848
@rsc
Copy link
Contributor

rsc commented Aug 16, 2023

Based on the discussion above, this proposal seems like a likely decline.
— rsc for the proposal review group

@gopherbot
Copy link

Change https://go.dev/cl/520065 mentions this issue: runtime: faster time.now on linux/amd64

@gopherbot
Copy link

Change https://go.dev/cl/521237 mentions this issue: time: make time.Until a few nanoseconds faster

gopherbot pushed a commit that referenced this issue Aug 25, 2023
This is similar to CL 518336.

For #61765.

Change-Id: I7c1d92a3b3e2b6c1c0058a2094997d93082ad139
Reviewed-on: https://go-review.googlesource.com/c/go/+/521237
Run-TryBot: Ian Lance Taylor <iant@golang.org>
Auto-Submit: Ian Lance Taylor <iant@google.com>
Run-TryBot: Ian Lance Taylor <iant@google.com>
Reviewed-by: Ian Lance Taylor <iant@google.com>
Reviewed-by: Bryan Mills <bcmills@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
@rsc
Copy link
Contributor

rsc commented Aug 30, 2023

No change in consensus, so declined.
— rsc for the proposal review group

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Status: Declined
Development

No branches or pull requests

6 participants