1 of 66

​

​

Blink Scheduler Update:

Scheduling Idle Tasks

May 13th, 2015

​

​

​

{rmcilroy, skyostil, alexclarke}@chromium.org

2 of 66

Scheduler basics

Before: one per-thread task queue

Task queue

3 of 66

Scheduler basics

Before: one per-thread task queue

Task�1

4 of 66

Scheduler basics

Before: one per-thread task queue

Task�1

Task�2

5 of 66

Scheduler basics

Before: one per-thread task queue

Task�1

Task�3

Task�2

6 of 66

Scheduler basics

Before: one per-thread task queue

Task�1

Task�3

Task�4

Task�2

7 of 66

Scheduler basics

Before: one per-thread task queue

Task�1

Task�3

Task�4

Task�2

8 of 66

Scheduler basics

Before: one per-thread task queue

Task�3

Task�4

Task�2

9 of 66

Scheduler basics

Before: one per-thread task queue

Task�3

Task�4

Task�2

Input

Task

10 of 66

Scheduler basics

Now: dedicated queues for different task types

Default task queue

Input task queue

Loading task queue

11 of 66

Scheduler basics

Now: dedicated queues for different task types

Task�2

Task�3

Task�1

Input

Task

Loading

Task

12 of 66

Scheduler basics

Now: dedicated queues for different task types

Task�2

Task�3

Task�1

Input

Task

Loading

Task

Blink

Scheduler

13 of 66

Scheduler basics

Now: dedicated queues for different task types

Task�2

Task�3

Task�1

Input

Task

Loading

Task

Blink

Scheduler

14 of 66

Scheduler basics

Now: dedicated queues for different task types

Task�2

Task�3

Task�1

Input

Task

Loading

Task

input state

render state

Blink

Scheduler

15 of 66

Scheduler basics

Now: dedicated queues for different task types

Magic

Task�2

Task�3

Task�1

Input

Task

Loading

Task

Blink

Scheduler

16 of 66

Scheduler basics

Now: dedicated queues for different task types

Task�2

Task�3

Task�1

Input

Task

Loading

Task

run

this

one

Blink

Scheduler

17 of 66

Scheduler basics

Now: dedicated queues for different task types

Task�2

Task�3

Task�1

Input

Task

Loading

Task

Blink

Scheduler

18 of 66

Scheduler basics

Now: dedicated queues for different task types

Task�2

Task�3

Task�1

Loading

Task

Blink

Scheduler

19 of 66

Scheduler basics

Tasks get posted by various clients

Task�2

Task�3

Task�1

Loading

Task

Compositor

Input router

Blink

...

Blink

Scheduler

20 of 66

Scheduling input & compositing

  • User input delivery
    • Touch, mouse event handlers
  • Compositor
    • requestAnimationFrame, scroll handlers, layout, painting

​

​

21 of 66

Scheduling input & compositing

  • User input delivery
    • Touch, mouse event handlers
  • Compositor
    • requestAnimationFrame, scroll handlers, layout, painting

​

Rule: Have I seen input in the last 100ms?

⇒ If so, prioritize input and compositor work

22 of 66

Scheduling input & compositing

Touchstart handling

touchstart

touchmove

ack

Paint

23 of 66

Scheduling input & compositing

Touchstart handling

touchstart

touchmove

ack

Paint

Loading task

24 of 66

Scheduling input & compositing

Touchstart handling

touchstart

touchmove

ack

Paint

delay

Loading task

25 of 66

Scheduling input & compositing

Touchstart handling: disallow loading tasks between touchstart and touchmove

touchstart

touchmove

ack

Paint

delay

Loading task

26 of 66

Scheduling input & compositing

first_gesture_scroll_update

Median ~41ms drops to ~25ms

-39%

​

​

​

​

mean_input_event_latency

Median ~50ms drops to ~42ms

-16%

​

​

​

​

​

​

queuing_durations

Median ~13ms drops to ~9ms

-30%

​

27 of 66

Scheduling loading tasks

HTML parser

Parse

main thread

background parser thread

Construct DOM

Parse

28 of 66

Scheduling loading tasks

HTML parser

Parse

main thread

background parser thread

Construct DOM

Input

Parse

29 of 66

Scheduling loading tasks

HTML parser

Parse

main thread

background parser thread

Parse

30 of 66

Scheduling loading tasks

HTML parser

Parse

main thread

background parser thread

Parse

Should yield?

31 of 66

Scheduling loading tasks

HTML parser

Parse

main thread

background parser thread

Input

Parse

Should yield?

32 of 66

Scheduling loading tasks

Yielding in

  • HTML parsing
  • top-level script execution
  • timers

main thread

33 of 66

Scheduling timers

  • Timers used very heavily
    • setTimeout() from JS
    • internal users

​

34 of 66

Scheduling timers

  • Timers used very heavily
    • setTimeout() from JS
    • internal users
  • Timer heap implements a mini-scheduler inside Blink

Timer

Timer

Timer

Timer

sorted by time

Message�Loop

35 of 66

Scheduling timers

  • Timers used very heavily
    • setTimeout() from JS
    • internal users
  • Timer heap implements a mini-scheduler inside Blink

Timer

Timer

Timer

Timer

sorted by time

Message�Loop

post

36 of 66

Scheduling timers

  • Timers used very heavily
    • setTimeout() from JS
    • internal users
  • Timer heap implements a mini-scheduler inside Blink

Timer

Timer

Timer

Timer

run all expired timers

Message�Loop

callback

37 of 66

Scheduling timers

  • Timers used very heavily
    • setTimeout() from JS
    • internal users
  • Timer heap implements a mini-scheduler inside Blink

Timer

Timer

Timer

Timer

Message�Loop

Should yield?

38 of 66

Scheduling timers

  • Timers used very heavily
    • setTimeout() from JS
    • internal users
  • Timer heap implements a mini-scheduler inside Blink

⇒ Turn timers into first

class tasks

  • Able to disable timers

Timer

Timer

Timer

Timer

Blink Scheduler

39 of 66

Demo video

goo.gl/YnGT5f

40 of 66

Idle Tasks

  • Push non-critical tasks off the critical path
  • Aimed at tasks which are:
    • Not latency critical
    • Potentially costly
    • Can estimate their execution time or able to yield with fine granularity
  • Current main users are V8 and Oilpan GC

41 of 66

Idle Periods

Compositor Task

Time

Input Task

Compositor Task

VSync

VSync

VSync

Other Task

Compositor Task

42 of 66

Idle Periods

Compositor Task

WillBegin

Frame

Time

Input Task

DidCommitFrame

WillBegin

Frame

Compositor Task

DidCommitFrame

Compositor Task

WillBegin

Frame

Other Task

43 of 66

Idle Periods

Compositor Task

WillBegin

Frame

Time

Input Task

DidCommitFrame

WillBegin

Frame

Compositor Task

DidCommitFrame

Compositor Task

WillBegin

Frame

Other Task

expected next frame begin

44 of 66

Idle Periods

Compositor Task

WillBegin

Frame

Time

Input Task

DidCommitFrame

idle period

WillBegin

Frame

Compositor Task

Compositor Task

WillBegin

Frame

idle period

Other Task

DidCommitFrame

45 of 66

Idle Periods

Compositor Task

WillBegin

Frame

Time

Input Task

Idle Task

DidCommitFrame

idle period

WillBegin

Frame

Compositor Task

Compositor Task

WillBegin

Frame

idle period

Other Task

DidCommitFrame

46 of 66

Idle task characteristics

  • May be starved for arbitrarily long
  • Take a deadline argument
    • Should finish by the deadline or earlier
    • Should return immediately (and repost) if they can’t do anything within deadline
  • Posted tasks won’t run until next idle period

47 of 66

Idle Periods

Compositor Task

Time

Input Task

Idle Task

idle period

Compositor Task

Compositor Task

idle period

Idle tasks return immediately due to too short deadline

Other Task

Repost Idle Task

48 of 66

V8 GC

Begin Frame

Commit Frame

16ms

49 of 66

V8 GC

Begin Frame

Commit Frame

16ms

JANK!

50 of 66

V8 GC Events

  • Scavenge [1-10ms]
    • Clean-up new space
  • Incremental Marking [<1-10ms]
    • Marking old space in small chunks
  • Mark-Compact [5-100ms]
    • Clean-up old space

51 of 66

Scheduling Idle GC

Blink Scheduler

Deadline

GCIdleHandler

V8 Heap

Heap State

Mark Speed

% full

Alloc Load

Magic

Scavenge

Incremental Marking

Compaction

Nothing

52 of 66

Scheduling Idle GC

Idle Period

CC

commit

begin frame

53 of 66

Long Idle Periods

Normal Task

Idle Task

Idle period

Time

Non-idle period

PostDelayed(20ms)

VSync

Input

54 of 66

Long Idle Periods

Normal Task

Idle Task

Idle period

Time

Non-idle period

BeginFrameNotExpectedSoon

PostDelayed(20ms)

VSync

Input

55 of 66

Long Idle Periods

Normal Task

Idle Task

Idle period

Time

Non-idle period

PostDelayed(20ms)

20ms

deadline

VSync

Input

56 of 66

Long Idle Periods

Normal Task

Idle Task

Idle period

Time

Non-idle period

PostDelayed(20ms)

20ms

deadline

50ms

deadline

VSync

50ms

deadline

50ms

deadline

Input

57 of 66

Long Idle Periods

Normal Task

Idle Task

Idle period

Time

Non-idle period

PostDelayed(20ms)

20ms

deadline

50ms

deadline

VSync

50ms

deadline

50ms

deadline

Input

58 of 66

~20%�GC during idle

Nexus 5 - Key Mobile Sites (%GC in idle)

Desktop (MacOS 10.9) - Top 25 Sites (%GC in idle)

Long Idle Periods Enabled

Tweak GC heuristics (hpayer@)

​

~60%�GC during idle

59 of 66

Reduction in GC Atomic Pause

Long Idle Periods Enabled

Tweak GC heuristics (hpayer@) + Weak closure over approximation (jochen@)

Nexus 5 - Key Mobile Sites

60 of 66

Exposing idle time to the web

Starting prototype work on requestIdleFrame

​

doWork = function(deadline) {

while (performance.now() + estimatedTime < deadline) {

// Do work

}

if (hasMoreWork()) {

requestIdleFrame(doWork);

}

}

requestIdleFrame(doWork);

61 of 66

Demo of requestIdleFrame

http://rawgit.com/rmcilroy/mandelbrot-js/master/mandelbrot.html

62 of 66

Next steps

  • Load time jank
    • Prioritize loading during first 1s
    • Is the page scrollable?
  • Schedule more things
    • Workers, GPU, browser, ...
  • Spatial scheduling
    • Which part of the page are tasks associated with?

​

63 of 66

Questions?

  • go/scheduler-dev

​

  • scheduler-dev@chromium.org

64 of 66

65 of 66

66 of 66

Demo

goo.gl/XZod0S