unix: hierarchical time wheels implemention and benchmarks by yjhjstz · Pull Request #823 · libuv/libuv

yjhjstz · 2016-04-12T02:48:17Z

see issue #809.

time wheels worse case benchmark result:

heap:

➜  libuv git:(v1.x) ✗ out/Release/run-benchmarks million_timers_cascade
10.42 seconds total
2.47 seconds init
7.57 seconds dispatch
0.38 seconds cleanup

time-wheels:

➜  libuv git:(v1.x-time-wheel) ✗ out/Release/run-benchmarks million_timers_cascade 
6.00 seconds total
1.46 seconds init
4.15 seconds dispatch
0.39 seconds cleanup

heap:

➜  libuv git:(v1.x) ✗ out/Release/run-benchmarks million_timers_cancel
9.92 seconds total
9.38 seconds start/stop
0.00 seconds run
0.54 seconds cleanup

time-wheels:

➜  libuv git:(v1.x-time-wheel) ✗ out/Release/run-benchmarks million_timers_cancel
1.39 seconds total
0.95 seconds start/stop
0.00 seconds run
0.45 seconds cleanup

@saghul @bnoordhuis

saghul · 2016-04-12T11:59:29Z

+  This file is licensed to you under your choice of the GNU Lesser
+  General Public License, version 3 or any later version (LGPLv3 or
+  later), or the GNU General Public License, version 2 (GPLv2), in all
+  cases as published by the Free Software Foundation.


We cannot incorporate code with this license.

I will delete it.

yjhjstz · 2016-04-21T13:23:42Z

update benchmark result, big improve!

saghul · 2016-04-21T13:28:26Z

@@ -0,0 +1,241 @@
+#ifndef _LLIST_H


Is this the same file as before? If so, you can't just delete the license and be done with it, we cannot incorporate GPL code. Can't you use our queue.h?

Later, I will try use queue.h , any other suggestion?

yjhjstz · 2016-04-26T11:46:40Z

update commit message, separate implemention and benchmarks.

saghul · 2016-04-28T08:48:36Z

Sorry @yjhjstz, I won't be able to look at this in the upcoming weeks. I have not forgotten though!

yjhjstz · 2016-04-28T08:52:35Z

any other libuv member can review it for me ? thanks.

txdv · 2016-04-28T09:26:42Z

 #endif

+
+// 8+6+6+6+6=32


do not use //, use only /* */, old c style compliant comments

txdv · 2016-04-28T22:27:41Z

Just putting out the inpact on the struct sizes. With your code:

sizeof(uv_loop_t) = 9032
sizeof(uv_timer_t) = 144

with the old code:

sizeof(uv_loop_t) = 848
sizeof(uv_timer_t) = 152

txdv · 2016-04-29T06:28:00Z

-  heap_remove((struct heap*) &handle->loop->timer_heap,
-              (struct heap_node*) &handle->heap_node,
-              timer_less_than);
+  --handle->loop->timer_counter;


I think handle->loop->timer_counter-- would be cleaner (put the decrement operator at the end).

Fishrock123 · 2016-05-17T15:26:50Z

ping me if I forget to take a look :)

yjhjstz · 2016-05-27T23:58:43Z

cc @libuv/collaborators

bnoordhuis · 2016-06-28T07:50:25Z

Ping @Fishrock123? I don't have time to review it myself.

yjhjstz · 2016-07-22T09:42:18Z

@saghul can you ?

saghul · 2016-07-22T10:19:35Z

@yjhjstz sorry, I don't have much time these days. At any rate, this PR would need to be applied to master, not v1.x because it breaks the ABI. And it should be used also on Windows.

Give this is a v2 thing, it may take a while for us to find the time, please don't despair!

Fishrock123 · 2016-09-20T16:04:19Z

ugh geez, I'll try to take a look soon >_<

Fishrock123 · 2016-09-20T16:07:29Z

@saghul in http://www.slideshare.net/saghul/planning-libuv-v2/12?src=clipshare you noted that:

Timer Wheels

Linux removed them! Worst case scenario is far worse. Complex implementation.

Could you give some more insight as to points 1 and 2 there? I am relatively familiar with the complexity increase.

Fishrock123 · 2016-09-20T16:10:12Z

Also as a note from my time profiling Node timers: the existing impl here seems pretty performant.

(And AFAIK the existing algorithm is a O(log n) insert/remove heap, correct me if I'm wrong.)

saghul · 2016-09-20T16:20:33Z

@Fishrock123 I was planning on commenting here, but ran out of time yesterday :-S

@bnoordhuis can probably elaborate but the key points (if I noted them correctly) are:

Performance in the bad cases is notably worse
The Linux kernel removed its timer wheel implementation because of this (I found some text about this here: https://www.kernel.org/doc/Documentation/timers/hrtimers.txt)
Complexity: maintaining the implementation is non-trivial
Size: it adds some overhead to the loop struct (though this is not a show stopper)

For these reasons we ( @bnoordhuis, @piscisaureus, @indutny and myself ) generally agreed to not pursue this.

If anyone sees any inaccuracies please feel free to correct me here.

Fishrock123 · 2016-09-26T22:29:14Z

Thanks. I'll try to read though that wall of text within the next few days.

saghul · 2016-09-27T07:57:49Z

Thanks! At any rate, we should consider including the benchmarks.

Fishrock123 · 2018-10-11T22:19:48Z

So at least in regarding to how node does stuff, @apapirovski took a look at using timer wheels and we both concluded that it was a less optimal solution than the one we already have and is already described in this great big wall of text.

That is: make a map of timer durations to linked lists, insert timers to the end of those lists, and keep timeout information on those lists similar to a heap, processing it first similar to a heap, and then the timers in each list. (That's the tl;dr, please go read the read deal for more.)

Modern linux distro timer wheels have very slightly improved perf characteristics (always O(1) vs Lists operations are O(1), map lookup is somewhere sub O(n) for way less entries, usually less than 10), but at a pretty significant cost. The accuracy of its hierarchical timer wheel impl degrades quite significantly over time. Ours does not.

Edit: In case it wasn't clear, I personally recommend closing this.

stale · 2019-09-30T13:51:23Z

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

yjhjstz force-pushed the v1.x-time-wheel branch from 70ef369 to 455a43b Compare April 12, 2016 02:55

saghul reviewed Apr 12, 2016
View reviewed changes

yjhjstz force-pushed the v1.x-time-wheel branch from f6f07eb to 837e5cd Compare April 18, 2016 23:35

saghul reviewed Apr 21, 2016
View reviewed changes

jianghua.yjh added 2 commits April 22, 2016 11:15

hierarchical time wheels implemention

af1245b

add timers benchmarks

ed3626f

yjhjstz force-pushed the v1.x-time-wheel branch from 837e5cd to ed3626f Compare April 22, 2016 03:16

yjhjstz changed the title ~~hierarchical time wheels implemention and benchmarks~~ unix: hierarchical time wheels implemention and benchmarks Apr 22, 2016

txdv reviewed Apr 28, 2016
View reviewed changes

txdv reviewed Apr 29, 2016
View reviewed changes

rename struct with prefix uv__

cb3e46c

yjhjstz force-pushed the v1.x-time-wheel branch from 2a6ca2b to cb3e46c Compare April 29, 2016 23:44

saghul mentioned this pull request May 17, 2016

timers: improve performance proposal #809

Closed

saghul added enhancement pending-review v2 labels Jul 22, 2016

Fishrock123 mentioned this pull request Feb 13, 2017

timers: use Maps for internal duration pooling nodejs/node#11040

Closed

3 tasks

cjihrig removed the v2 label Mar 16, 2018

cjihrig force-pushed the v1.x branch from c92be35 to abe9e01 Compare September 18, 2018 15:50

stale Bot added the stale label Sep 30, 2019

stale Bot closed this Oct 7, 2019

Conversation

yjhjstz commented Apr 12, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

saghul Apr 12, 2016

Choose a reason for hiding this comment

Uh oh!

yjhjstz Apr 12, 2016

Choose a reason for hiding this comment

Uh oh!

yjhjstz commented Apr 21, 2016

Uh oh!

saghul Apr 21, 2016

Choose a reason for hiding this comment

Uh oh!

yjhjstz Apr 21, 2016

Choose a reason for hiding this comment

Uh oh!

yjhjstz commented Apr 26, 2016

Uh oh!

saghul commented Apr 28, 2016

Uh oh!

yjhjstz commented Apr 28, 2016

Uh oh!

txdv Apr 28, 2016

Choose a reason for hiding this comment

Uh oh!

txdv commented Apr 28, 2016

Uh oh!

txdv Apr 29, 2016

Choose a reason for hiding this comment

Uh oh!

yjhjstz Apr 29, 2016

Choose a reason for hiding this comment

Uh oh!

Fishrock123 commented May 17, 2016

Uh oh!

yjhjstz commented May 27, 2016

Uh oh!

bnoordhuis commented Jun 28, 2016

Uh oh!

yjhjstz commented Jul 22, 2016

Uh oh!

saghul commented Jul 22, 2016

Uh oh!

Fishrock123 commented Sep 20, 2016

Uh oh!

Fishrock123 commented Sep 20, 2016

Uh oh!

Fishrock123 commented Sep 20, 2016

Uh oh!

saghul commented Sep 20, 2016

Uh oh!

Fishrock123 commented Sep 26, 2016

Uh oh!

saghul commented Sep 27, 2016

Uh oh!

Fishrock123 commented Oct 11, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

stale Bot commented Sep 30, 2019

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

yjhjstz commented Apr 12, 2016 •

edited

Loading

Fishrock123 commented Oct 11, 2018 •

edited

Loading