[JBoss JIRA] Created: (JGRP-1051) TimeScheduler: replace use of ScheduledThreadPoolExecutor with ConcurrentSkipListMap
6:26 a.m.
TimeScheduler: replace use of ScheduledThreadPoolExecutor with ConcurrentSkipListMap
------------------------------------------------------------------------------------
Key: JGRP-1051
URL: https://jira.jboss.org/jira/browse/JGRP-1051
Project: JGroups
Issue Type: Feature Request
Reporter: Bela Ban
Assignee: Bela Ban
Fix For: 2.9
Attachments: TimeScheduler.java
TimeScheduler currently extends ScheduledThreadPoolExecutor, which uses a DelayQueue for
keeping an ordered list of tasks (ordered by their execution times).
DelayQueue doesn't provide good speed, e.g. (IIRC) remove() requires a linear list
scan.
ConcurrentSkipListMap however provides O(log(n)) cost for get(), put(), remove() and
containsKey(). Attached is a cursory impl of TimeScheduler based on ConcurrentSkipListMap.
It is faster than the old version.
Since ConcurrentSkipListMap requires JDK 1.6, we cannot use this in 2.6.x. It can be used
in 3.0 only, or perhaps - after a discussion on the mailing list - in 2.9...
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
https://jira.jboss.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
6:26 a.m.
New subject: [JBoss JIRA] Updated: (JGRP-1051) TimeScheduler: replace use of ScheduledThreadPoolExecutor with ConcurrentSkipListMap
[
https://jira.jboss.org/jira/browse/JGRP-1051?page=com.atlassian.jira.plug...
]
Bela Ban updated JGRP-1051:
---------------------------
Attachment: TimeScheduler.java
TimeScheduler: replace use of ScheduledThreadPoolExecutor with
ConcurrentSkipListMap
------------------------------------------------------------------------------------
Key: JGRP-1051
URL: https://jira.jboss.org/jira/browse/JGRP-1051
Project: JGroups
Issue Type: Feature Request
Reporter: Bela Ban
Assignee: Bela Ban
Fix For: 2.9
Attachments: TimeScheduler.java
TimeScheduler currently extends ScheduledThreadPoolExecutor, which uses a DelayQueue for
keeping an ordered list of tasks (ordered by their execution times).
DelayQueue doesn't provide good speed, e.g. (IIRC) remove() requires a linear list
scan.
ConcurrentSkipListMap however provides O(log(n)) cost for get(), put(), remove() and
containsKey(). Attached is a cursory impl of TimeScheduler based on ConcurrentSkipListMap.
It is faster than the old version.
Since ConcurrentSkipListMap requires JDK 1.6, we cannot use this in 2.6.x. It can be used
in 3.0 only, or perhaps - after a discussion on the mailing list - in 2.9...
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
https://jira.jboss.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
9:27 a.m.
New subject: [JBoss JIRA] Commented: (JGRP-1051) TimeScheduler: replace use of ScheduledThreadPoolExecutor with ConcurrentSkipListMap
[
https://jira.jboss.org/jira/browse/JGRP-1051?page=com.atlassian.jira.plug...
]
Brian Stansberry commented on JGRP-1051:
----------------------------------------
A couple comments:
1) If the thread taking tasks from the map sleeps the delay until the next task, rather
than INTERVAL, it's more precise for low timeout tasks like bundled message
transmission.
2) If you do 1) then in the schedule methods you need to test if a newly added task is
scheduled before the earliest task. Otherwise you could have:
a) Schedule a MERGE task for 100 secs from now.
b) processing thread goes to sleep for 100 secs.
c) Schedule a message bundle for 30 ms from now.
d) processing thread wakes up 100 secs later.
3) The processing thread can call Task.isCancelled() and not pass the task to the pool if
so. Passing the task to the pool requires taking a lock, blocking until a pool thread is
available etc.
TimeScheduler: replace use of ScheduledThreadPoolExecutor with
ConcurrentSkipListMap
------------------------------------------------------------------------------------
Key: JGRP-1051
URL: https://jira.jboss.org/jira/browse/JGRP-1051
Project: JGroups
Issue Type: Feature Request
Reporter: Bela Ban
Assignee: Bela Ban
Fix For: 2.9
Attachments: TimeScheduler.java
TimeScheduler currently extends ScheduledThreadPoolExecutor, which uses a DelayQueue for
keeping an ordered list of tasks (ordered by their execution times).
DelayQueue doesn't provide good speed, e.g. (IIRC) remove() requires a linear list
scan.
ConcurrentSkipListMap however provides O(log(n)) cost for get(), put(), remove() and
containsKey(). Attached is a cursory impl of TimeScheduler based on ConcurrentSkipListMap.
It is faster than the old version.
Since ConcurrentSkipListMap requires JDK 1.6, we cannot use this in 2.6.x. It can be used
in 3.0 only, or perhaps - after a discussion on the mailing list - in 2.9...
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
https://jira.jboss.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
9:46 a.m.
New subject: [JBoss JIRA] Commented: (JGRP-1051) TimeScheduler: replace use of ScheduledThreadPoolExecutor with ConcurrentSkipListMap
[
https://jira.jboss.org/jira/browse/JGRP-1051?page=com.atlassian.jira.plug...
]
Bela Ban commented on JGRP-1051:
--------------------------------
Yes, this is something I wanted to do as an optimization:
- Var sleep-time which is the time ofthe first element (next to be executed)
- When a new task is schedule, do a sleep_time=min(sleep_time, next_task.delay)
- If the new sleep_time is lower than the current, interrupt and reschedule the runner
TimeScheduler: replace use of ScheduledThreadPoolExecutor with
ConcurrentSkipListMap
------------------------------------------------------------------------------------
Key: JGRP-1051
URL: https://jira.jboss.org/jira/browse/JGRP-1051
Project: JGroups
Issue Type: Feature Request
Reporter: Bela Ban
Assignee: Bela Ban
Fix For: 2.9
Attachments: TimeScheduler.java
TimeScheduler currently extends ScheduledThreadPoolExecutor, which uses a DelayQueue for
keeping an ordered list of tasks (ordered by their execution times).
DelayQueue doesn't provide good speed, e.g. (IIRC) remove() requires a linear list
scan.
ConcurrentSkipListMap however provides O(log(n)) cost for get(), put(), remove() and
containsKey(). Attached is a cursory impl of TimeScheduler based on ConcurrentSkipListMap.
It is faster than the old version.
Since ConcurrentSkipListMap requires JDK 1.6, we cannot use this in 2.6.x. It can be used
in 3.0 only, or perhaps - after a discussion on the mailing list - in 2.9...
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
https://jira.jboss.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
3:33 p.m.
New subject: [JBoss JIRA] Updated: (JGRP-1051) TimeScheduler: replace use of ScheduledThreadPoolExecutor with ConcurrentSkipListMap
[
https://jira.jboss.org/jira/browse/JGRP-1051?page=com.atlassian.jira.plug...
]
Brian Stansberry updated JGRP-1051:
-----------------------------------
Attachment: timer.zip
Attaching ScheduledThreadPoolExecutor variant I mentioned. The interesting class is
DelayQueue; the others are just the same as the JDK classes; only needed because the JDK
classes don't provide a hook to set the queue. The fact that all the other classes
besides DelayQueue are required makes this nothing more than an interesting experiment,
IMO.
The TimerTest class is a work-in-progress attempt at testing the perf of the other classes
compared to the standard JDK classes.
TimeScheduler: replace use of ScheduledThreadPoolExecutor with
ConcurrentSkipListMap
------------------------------------------------------------------------------------
Key: JGRP-1051
URL: https://jira.jboss.org/jira/browse/JGRP-1051
Project: JGroups
Issue Type: Feature Request
Reporter: Bela Ban
Assignee: Bela Ban
Fix For: 2.9
Attachments: timer.zip, TimeScheduler.java
TimeScheduler currently extends ScheduledThreadPoolExecutor, which uses a DelayQueue for
keeping an ordered list of tasks (ordered by their execution times).
DelayQueue doesn't provide good speed, e.g. (IIRC) remove() requires a linear list
scan.
ConcurrentSkipListMap however provides O(log(n)) cost for get(), put(), remove() and
containsKey(). Attached is a cursory impl of TimeScheduler based on ConcurrentSkipListMap.
It is faster than the old version.
Since ConcurrentSkipListMap requires JDK 1.6, we cannot use this in 2.6.x. It can be used
in 3.0 only, or perhaps - after a discussion on the mailing list - in 2.9...
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
https://jira.jboss.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
2:03 a.m.
New subject: [JBoss JIRA] Commented: (JGRP-1051) TimeScheduler: replace use of ScheduledThreadPoolExecutor with ConcurrentSkipListMap
[
https://jira.jboss.org/jira/browse/JGRP-1051?page=com.atlassian.jira.plug...
]
Bela Ban commented on JGRP-1051:
--------------------------------
[Brian]
I realized that my java.util.Timer suggestion can be just as easily implemented with a
ScheduledThreadPoolExecutor with a single pool thread. The threading behavior is the same,
which my gut tells me is a key thing -- no multiple pool threads waking up every time
DelayQueue.take() is invoked and competing with app threads for the queue lock.
So, I implemented it, which was quite simple. Patch to rev 1.23.4.6 of TimeScheduler is
attached. This is basically about 1/2 way to your ConcurrentSkipListMap approach, so if
CSLM is a faster data structure moving to it when you move to JDK 6 should be
straightforward.
I then took the result and integrated it with the source from the latest jar you sent me
-- the one w/ the do/while loop. I also moved the do/while loop contents back inside the
entry lock, a la what you said you'd done in your workspace. Trying to get to about
what you've got on your system.
Attachment is TimeScheduler.patch
TimeScheduler: replace use of ScheduledThreadPoolExecutor with
ConcurrentSkipListMap
------------------------------------------------------------------------------------
Key: JGRP-1051
URL: https://jira.jboss.org/jira/browse/JGRP-1051
Project: JGroups
Issue Type: Feature Request
Reporter: Bela Ban
Assignee: Bela Ban
Fix For: 2.9
Attachments: timer.zip, TimeScheduler.java, TimeScheduler.patch
TimeScheduler currently extends ScheduledThreadPoolExecutor, which uses a DelayQueue for
keeping an ordered list of tasks (ordered by their execution times).
DelayQueue doesn't provide good speed, e.g. (IIRC) remove() requires a linear list
scan.
ConcurrentSkipListMap however provides O(log(n)) cost for get(), put(), remove() and
containsKey(). Attached is a cursory impl of TimeScheduler based on ConcurrentSkipListMap.
It is faster than the old version.
Since ConcurrentSkipListMap requires JDK 1.6, we cannot use this in 2.6.x. It can be used
in 3.0 only, or perhaps - after a discussion on the mailing list - in 2.9...
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
https://jira.jboss.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
2:03 a.m.
New subject: [JBoss JIRA] Updated: (JGRP-1051) TimeScheduler: replace use of ScheduledThreadPoolExecutor with ConcurrentSkipListMap
[
https://jira.jboss.org/jira/browse/JGRP-1051?page=com.atlassian.jira.plug...
]
Bela Ban updated JGRP-1051:
---------------------------
Attachment: TimeScheduler.patch
TimeScheduler: replace use of ScheduledThreadPoolExecutor with
ConcurrentSkipListMap
------------------------------------------------------------------------------------
Key: JGRP-1051
URL: https://jira.jboss.org/jira/browse/JGRP-1051
Project: JGroups
Issue Type: Feature Request
Reporter: Bela Ban
Assignee: Bela Ban
Fix For: 2.9
Attachments: timer.zip, TimeScheduler.java, TimeScheduler.patch
TimeScheduler currently extends ScheduledThreadPoolExecutor, which uses a DelayQueue for
keeping an ordered list of tasks (ordered by their execution times).
DelayQueue doesn't provide good speed, e.g. (IIRC) remove() requires a linear list
scan.
ConcurrentSkipListMap however provides O(log(n)) cost for get(), put(), remove() and
containsKey(). Attached is a cursory impl of TimeScheduler based on ConcurrentSkipListMap.
It is faster than the old version.
Since ConcurrentSkipListMap requires JDK 1.6, we cannot use this in 2.6.x. It can be used
in 3.0 only, or perhaps - after a discussion on the mailing list - in 2.9...
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
https://jira.jboss.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
11:25 a.m.
New subject: [JBoss JIRA] Commented: (JGRP-1051) TimeScheduler: replace use of ScheduledThreadPoolExecutor with ConcurrentSkipListMap
[
https://jira.jboss.org/jira/browse/JGRP-1051?page=com.atlassian.jira.plug...
]
Bela Ban commented on JGRP-1051:
--------------------------------
Possible impl: http://www.cse.wustl.edu/~cdgill/courses/cs6874/TimingWheels.ppt
TimeScheduler: replace use of ScheduledThreadPoolExecutor with
ConcurrentSkipListMap
------------------------------------------------------------------------------------
Key: JGRP-1051
URL: https://jira.jboss.org/jira/browse/JGRP-1051
Project: JGroups
Issue Type: Feature Request
Reporter: Bela Ban
Assignee: Bela Ban
Fix For: 2.9
Attachments: timer.zip, TimeScheduler.java, TimeScheduler.patch
TimeScheduler currently extends ScheduledThreadPoolExecutor, which uses a DelayQueue for
keeping an ordered list of tasks (ordered by their execution times).
DelayQueue doesn't provide good speed, e.g. (IIRC) remove() requires a linear list
scan.
ConcurrentSkipListMap however provides O(log(n)) cost for get(), put(), remove() and
containsKey(). Attached is a cursory impl of TimeScheduler based on ConcurrentSkipListMap.
It is faster than the old version.
Since ConcurrentSkipListMap requires JDK 1.6, we cannot use this in 2.6.x. It can be used
in 3.0 only, or perhaps - after a discussion on the mailing list - in 2.9...
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
https://jira.jboss.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
8:05 p.m.
New subject: [JBoss JIRA] Commented: (JGRP-1051) TimeScheduler: replace use of ScheduledThreadPoolExecutor with ConcurrentSkipListMap
[
https://jira.jboss.org/jira/browse/JGRP-1051?page=com.atlassian.jira.plug...
]
Brian Stansberry commented on JGRP-1051:
----------------------------------------
FYI, Trustin Lee has an implementation of a Hashed Timer Wheel in Netty.
TimeScheduler: replace use of ScheduledThreadPoolExecutor with
ConcurrentSkipListMap
------------------------------------------------------------------------------------
Key: JGRP-1051
URL: https://jira.jboss.org/jira/browse/JGRP-1051
Project: JGroups
Issue Type: Feature Request
Reporter: Bela Ban
Assignee: Bela Ban
Fix For: 2.9
Attachments: timer.zip, TimeScheduler.java, TimeScheduler.patch
TimeScheduler currently extends ScheduledThreadPoolExecutor, which uses a DelayQueue for
keeping an ordered list of tasks (ordered by their execution times).
DelayQueue doesn't provide good speed, e.g. (IIRC) remove() requires a linear list
scan.
ConcurrentSkipListMap however provides O(log(n)) cost for get(), put(), remove() and
containsKey(). Attached is a cursory impl of TimeScheduler based on ConcurrentSkipListMap.
It is faster than the old version.
Since ConcurrentSkipListMap requires JDK 1.6, we cannot use this in 2.6.x. It can be used
in 3.0 only, or perhaps - after a discussion on the mailing list - in 2.9...
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
https://jira.jboss.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
5:44 a.m.
New subject: [JBoss JIRA] Updated: (JGRP-1051) TimeScheduler: replace use of ScheduledThreadPoolExecutor with ConcurrentSkipListMap
[
https://jira.jboss.org/jira/browse/JGRP-1051?page=com.atlassian.jira.plug...
]
Bela Ban updated JGRP-1051:
---------------------------
Fix Version/s: 2.10
(was: 2.9)
TimeScheduler: replace use of ScheduledThreadPoolExecutor with
ConcurrentSkipListMap
------------------------------------------------------------------------------------
Key: JGRP-1051
URL: https://jira.jboss.org/jira/browse/JGRP-1051
Project: JGroups
Issue Type: Feature Request
Reporter: Bela Ban
Assignee: Bela Ban
Fix For: 2.10
Attachments: timer.zip, TimeScheduler.java, TimeScheduler.patch
TimeScheduler currently extends ScheduledThreadPoolExecutor, which uses a DelayQueue for
keeping an ordered list of tasks (ordered by their execution times).
DelayQueue doesn't provide good speed, e.g. (IIRC) remove() requires a linear list
scan.
ConcurrentSkipListMap however provides O(log(n)) cost for get(), put(), remove() and
containsKey(). Attached is a cursory impl of TimeScheduler based on ConcurrentSkipListMap.
It is faster than the old version.
Since ConcurrentSkipListMap requires JDK 1.6, we cannot use this in 2.6.x. It can be used
in 3.0 only, or perhaps - after a discussion on the mailing list - in 2.9...
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
https://jira.jboss.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
9:44 a.m.
New subject: [JBoss JIRA] Updated: (JGRP-1051) TimeScheduler: replace use of ScheduledThreadPoolExecutor with ConcurrentSkipListMap
[
https://jira.jboss.org/jira/browse/JGRP-1051?page=com.atlassian.jira.plug...
]
Bela Ban updated JGRP-1051:
---------------------------
Fix Version/s: 2.11
(was: 2.10)
TimeScheduler: replace use of ScheduledThreadPoolExecutor with
ConcurrentSkipListMap
------------------------------------------------------------------------------------
Key: JGRP-1051
URL: https://jira.jboss.org/jira/browse/JGRP-1051
Project: JGroups
Issue Type: Feature Request
Reporter: Bela Ban
Assignee: Bela Ban
Fix For: 2.11
Attachments: timer.zip, TimeScheduler.java, TimeScheduler.patch
TimeScheduler currently extends ScheduledThreadPoolExecutor, which uses a DelayQueue for
keeping an ordered list of tasks (ordered by their execution times).
DelayQueue doesn't provide good speed, e.g. (IIRC) remove() requires a linear list
scan.
ConcurrentSkipListMap however provides O(log(n)) cost for get(), put(), remove() and
containsKey(). Attached is a cursory impl of TimeScheduler based on ConcurrentSkipListMap.
It is faster than the old version.
Since ConcurrentSkipListMap requires JDK 1.6, we cannot use this in 2.6.x. It can be used
in 3.0 only, or perhaps - after a discussion on the mailing list - in 2.9...
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
https://jira.jboss.org/jira/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
6:02 a.m.
New subject: [JBoss JIRA] Resolved: (JGRP-1051) TimeScheduler: replace use of ScheduledThreadPoolExecutor with ConcurrentSkipListMap
[
https://jira.jboss.org/browse/JGRP-1051?page=com.atlassian.jira.plugin.sy...
]
Bela Ban resolved JGRP-1051.
----------------------------
Resolution: Done
TimeScheduler: replace use of ScheduledThreadPoolExecutor with
ConcurrentSkipListMap
------------------------------------------------------------------------------------
Key: JGRP-1051
URL: https://jira.jboss.org/browse/JGRP-1051
Project: JGroups
Issue Type: Feature Request
Reporter: Bela Ban
Assignee: Bela Ban
Fix For: 2.11
Attachments: timer.zip, TimeScheduler.java, TimeScheduler.patch
TimeScheduler currently extends ScheduledThreadPoolExecutor, which uses a DelayQueue for
keeping an ordered list of tasks (ordered by their execution times).
DelayQueue doesn't provide good speed, e.g. (IIRC) remove() requires a linear list
scan.
ConcurrentSkipListMap however provides O(log(n)) cost for get(), put(), remove() and
containsKey(). Attached is a cursory impl of TimeScheduler based on ConcurrentSkipListMap.
It is faster than the old version.
Since ConcurrentSkipListMap requires JDK 1.6, we cannot use this in 2.6.x. It can be used
in 3.0 only, or perhaps - after a discussion on the mailing list - in 2.9...
--
This message is automatically generated by JIRA.
-
If you think it was sent incorrectly contact one of the administrators:
https://jira.jboss.org/secure/Administrators.jspa
-
For more information on JIRA, see: http://www.atlassian.com/software/jira
5832
days inactive
6153
days old
11 comments
2 participants
participants (2)
-
Bela Ban (JIRA) -
Brian Stansberry (JIRA)