HashedWheelTimer vs ScheduledThreadPoolExecutor for higher performance

Question

I'm figuring what a timer implementation to use if you need to schedule tons of (non blocking) tasks as fast as possible inside jvm on one machine.

I've studied ScheduledThreadPoolExecutor and HashedWheelTimer sources (+wheel timer general docs) and here are basic differences (N - number of all outstanding scheduled tasks so far, C - wheel size):

ScheduledThreadPoolExecutor

• O(log N) for adding new task
• O(1) per each timer tick (but tick per each task, so N overall)
• O(log N) cancelling the task
• lock per each tick/task

HashedWheelTimer

• O(1) adding new task
• O(m) per each timer tick (m ~ N/C where C > 512 approx), so ~C ticks overall
• O(m) for cancelling a task
• lock per bucket of tasks (on each tick)

Thus I tend using HW Timer for such use-case, because you must schedule tasks quickly with minimum overhead, i.e. O(1) for new task. Also you will minimize a bookkeeping activity, because you'll get less number of ticks (N < C) and less lock contention. Canceling is not very important feature in this case

Did anybody try these timers for similar activities and what results see in practice? Thanks!

Enteric

The fundamental difference between them is that HWT is optimized for scheduling with tolerance for timing imprecision. If you can live with its imprecision, then it is almost certainly the better choice. – Boong

Thanks, yes, a throughput (say per second) is more important for me than individual task accurate scheduling. On the other hand I doubt STPE would be very accurate on the heavy load and with huge work-queue. And you may get HWT more accurate after tuned tick-size in this case. – Enteric

Answer 1

HWT. Unless you require to-the-ns-precision, use the HWT. For most client-server applications, a HWT is sufficient. In many internet-scale applications, especially for in-memory caches that were the timeout was constantly changing, it was the only option. We're talking about billions of jobs here.

Actually, if you require that level of precision, you need a system with guaranteed interrupt times and not GC pauses; i.e. not Java, not Intel... :)

Myel

Please elaborate “ need a system with guaranted interrupt times not intel” – Karmakarmadharaya