Opened 12 days ago

Closed 12 days ago

Last modified 12 days ago

#2249 closed enhancement (fixed)

Use sorted linked list for timer

Reported by: riza Owned by: riza
Priority: normal Milestone: release-2.10
Component: pjlib Version: trunk
Keywords: timer-refactoring Cc:
Backport to 1.x milestone: Backported: no

Description

Currently, the library use binary heap tree for timer implementation.
However it is difficult to debug when a crash happen.
This ticket will use a sorted linked list as an alternative.
Note that this implementation is intended for debugging purposes and based on our test, it will hamper performance significantly if used with large number of entries.

sorted linked list:
05:31:25.191 ....random scheduling/cancelling test..
05:31:25.191     test 1 of 1..
05:31:25.191     Entries 0-100: schedule 1,594,896 ent/sec
05:31:25.193     Entries 101-1,000: schedule 624,652 ent/sec
05:31:25.416     Entries 1,001-10,000: schedule 40,300 ent/sec
05:33:24.605     Entries 10,001-100,000: schedule 755 ent/sec
07:48:19.304     Entries 100,001-500,000: schedule 49 ent/sec
07:48:19.305     Entries 500,000-499,900: cancel 3,401,360 ent/sec
07:48:19.319     Entries 499,899-499,000: cancel 5,322,676 ent/sec
07:48:19.326     Entries 498,999-490,000: cancel 8,436,298 ent/sec
07:48:19.337     Entries 489,999-400,000: cancel 8,541,803 ent/sec
07:48:19.374     Entries 399,999-0: cancel 10,727,227 ent/sec
07:48:19.374 ....increment scheduling/cancelling test..
07:48:19.375     test 1 of 1..
07:48:19.377     Entries 0-100: schedule 2,673,796 ent/sec
07:48:19.380     Entries 101-1,000: schedule 2,785,869 ent/sec
07:48:19.385     Entries 1,001-10,000: schedule 2,887,626 ent/sec
07:48:19.408     Entries 10,001-100,000: schedule 3,932,474 ent/sec
07:48:19.521     Entries 100,001-500,000: schedule 3,569,618 ent/sec
07:48:19.521     Entries 500,000-499,900: cancel 7,874,015 ent/sec
07:48:19.522     Entries 499,899-499,000: cancel 13,498,498 ent/sec
07:48:19.526     Entries 498,999-490,000: cancel 8,376,617 ent/sec
07:48:19.535     Entries 489,999-400,000: cancel 10,622,735 ent/sec
07:48:19.565     Entries 399,999-0: cancel 13,477,373 ent/sec

binary heap tree:
13:10:40.284 ....random scheduling/cancelling test..
13:10:40.284     test 1 of 1..
13:10:40.285     Entries 0-100: schedule 967,117 ent/sec
13:10:40.286     Entries 101-1,000: schedule 1,344,399 ent/sec
13:10:40.294     Entries 1,001-10,000: schedule 1,700,716 ent/sec
13:10:40.359     Entries 10,001-100,000: schedule 1,367,398 ent/sec
13:10:40.594     Entries 100,001-500,000: schedule 1,713,635 ent/sec
13:10:40.594     Entries 500,000-499,900: cancel 998,003 ent/sec
13:10:40.596     Entries 499,899-499,000: cancel 1,417,533 ent/sec
13:10:40.602     Entries 498,999-490,000: cancel 2,005,661 ent/sec
13:10:40.643     Entries 489,999-400,000: cancel 2,230,563 ent/sec
13:10:40.783     Entries 399,999-0: cancel 2,858,820 ent/sec
13:10:40.783 ....increment scheduling/cancelling test..
13:10:40.786     test 1 of 1..
13:10:40.787     Entries 0-100: schedule 3,125,000 ent/sec
13:10:40.788     Entries 101-1,000: schedule 2,535,966 ent/sec
13:10:40.791     Entries 1,001-10,000: schedule 2,508,851 ent/sec
13:10:40.820     Entries 10,001-100,000: schedule 3,170,262 ent/sec
13:10:40.940     Entries 100,001-500,000: schedule 3,344,568 ent/sec
13:10:40.940     Entries 500,000-499,900: cancel 358,680 ent/sec
13:10:40.944     Entries 499,899-499,000: cancel 465,296 ent/sec
13:10:40.960     Entries 498,999-490,000: cancel 571,470 ent/sec
13:10:41.069     Entries 489,999-400,000: cancel 820,636 ent/sec
13:10:41.377     Entries 399,999-0: cancel 1,303,636 ent/sec

Change History (2)

comment:1 Changed 12 days ago by riza

  • Owner set to riza
  • Resolution set to fixed
  • Status changed from new to closed

In 6099:

Close #2249: Use sorted linked list for timer implementation.

comment:2 Changed 12 days ago by riza

In 6100:

Re #2249: Fixed warning on pjlib-test.

Note: See TracTickets for help on using tickets.