runtime: improve timer performance

[OmidHekayati]

Needed changes to improve performance (At least in theory):

• Change timers []*timer to timers []timerBucket
• Make new timerBucket struct as

type timerBucket struct {
	timer *timer
	// Two reason to have timer when here:
	// - hot cache to prevent dereference timer to get when field
	// - It can be difference with timer when filed in timerModifiedXX status.
	when int64
}

• Delete when int64 from timer struct in favor of timerBucket when field.
• Rename nextwhen int64 to when int64 in timer struct
• Make some few other changes to respect above changes in related functions

By this changes, we claim that we improve performance in siftupTimer and siftdownTimer when need to compare timers added when to timing heap, we don't need to get data from many different location in the memory (dereference many timers) and we have timers added when in sequential array.

Additional suggestions to improve code readability:

• make timer.go and timers.go in runtime package
• make timers struct
• move timers field from p struct in runtime2.go to timers struct and embed this struct instead
• move all timers logic from many files in runtime package to timers.go such as logics in time.go - almost everthing, proc.go - checkTimers, ...

p.s: If the idea is ok, I can help to make changes by send a PR.

[seankhliao]

do you have benchmarks to prove that these will provide real world performance improvements?

[OmidHekayati]

do you have benchmarks to prove that these will provide real world performance improvements?

No, but It's not to hard to write some codes.

Anyway, as said, It is obvious (in theory) that when we need dereference many timer struct in many location (due to each timer sturct allocate in very different and random memory location) to have a field (here when int64 field), we loose hot L1 CPU (or some huge timers slice L2) cache.

[ianlancetaylor]

I don't quite see how modtimer works if we remove the when field from timer. The modtimer function would not have access to the timerBucket, so it would not know the current value of the when field, so it would not know whether to set timerModifiedEarlier or timerModifiedLater. But that knowledge seems fairly important for performance of typical programs.

[OmidHekayati]

I don't quite see how modtimer works if we remove the when field from timer. The modtimer functio would not have access to the timerBucket, so it would not know the current value of the when field, so it would not know whether to set timerModifiedEarlier or timerModifiedLater. But that knowledge seems fairly important for performance of typical programs.

I agree with you that in one scenario, It is better to check timerBucket.when with new timer when in modtimer, but it is very rare situation that a timer changed more than once before its timerout.

Timer set to 60 sec later, after 10 sec logic change timer to 120 sec later, after another 10 sec logic change timer to 60 sec later. We change timer.status to timerModifiedEarlier but it must change to timerModifiedLater base on timer added to timing heap. But base on timer logic we change it correctly and just to prevent heap sorting on every timers changes we break the timer rules.
Anyway almost we don't lose anything in this situation, just call updateTimerModifiedEarliest wrongly and one atomic and one compare waste. In other functions, We don't make a difference between this two status as case timerModifiedEarlier, timerModifiedLater:

[mknyszek]

When it comes down to it, what matters most is if it improves the performance of real-world programs. You can feel free to implement it and send a PR and try it out, but the decision on whether to merge it is going to come down to actual performance data (though of course if you have any nice cleanups, those would be welcomed on their own). Assigning to you @OmidHekayati for now.

[ianlancetaylor]

@OmidHekayati We got to our current approach through a series of real world programs and bug reports that showed bad performance with earlier approaches. I would be quite reluctant to say things like "it is very rare situation that a timer changed more than once before its timerout" or "almost we don't lose anything in this situation." We added the current features because they mattered to real programs, not because we wanted increased complexity.

[OmidHekayati]

@ianlancetaylor You are right, I must choose better words to transfer my thoughts in better way (English is not my native language). I agree with you that no one want to increase complexity for nothing.

@mknyszek Thx. I will write some benchmark first to prove the idea and after your approvment, I will take a time to write the actual PR.

p.s: Any way I must say that we occur a real problem in one of our project to implement TCP on userspace in Go with millions of timer! So it is very obvious that a little performance improvements can change the game. So this issue is not just hobby for me.

[OmidHekayati]

As you can see our benchmark here, The below result show that when timers allocate in very different memory location with many timers in timing, it is take almost 10X more time to order the timers heap with exiting go runtime library.

Some consideration:

• I know we don't reorder timers heap very much e.g. in every timer adding or modifing, So this benchmark can fool us about real situation.
• May be you have better solution to fill memory to prevent timer allocate in order in memory to respect real software requirements, But I don't want to complicate the benchmarks at least now.

Any idea to improve benchmark to cover better real usage?

goos: windows
goarch: amd64
cpu: Intel(R) Core(TM) i7-2670QM CPU @ 2.20GHz

With fillsMemory:
Benchmark_newTiming-8   	  463105	      2778 ns/op	   27368 B/op	       2 allocs/op
Benchmark_oldTiming-8   	  248739	     24886 ns/op	   27376 B/op	       2 allocs/op

Without fillsMemory:
Benchmark_newTiming-8   	 7114608	       178.2 ns/op	      80 B/op	       1 allocs/op
Benchmark_oldTiming-8   	 5867421	       195.9 ns/op	      88 B/op	       1 allocs/op

[gopherbot]

Change https://go.dev/cl/421615 mentions this issue: runtime: cleanup timer codes

[OmidHekayati]

I think it is the time we must close this issue and related PR as It will never ever have chance to merge. I suggest main Golang developers with enough power to change, work on /runtime/ package and move time and timer functionality to dedicate packages as /time/ and /timer/. In this case we will have /time/monotonic, /time/unix, ... packages