Better Code: Concurrency

1.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Better Code: Concurrency Sean Parent | Principal Scientist

2.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Better Code ! Regular Type ! Goal: Implement Complete and Eﬃcient Types ! Algorithms ! Goal: No Raw Loops ! Data Structures ! Goal: No Incidental Data Structures ! Runtime Polymorphism ! Goal: No Raw Pointers ! Concurrency ! Goal: No Raw Synchronization Primitives ! … 2

3.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Common Themes ! Manage Relationships ! Understand the Fundamentals ! Code Simply 3

4.
© 2013 AdobeSystems Incorporated. All Rights Reserved. Demo 4

5.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Concurrency ! Concurrency: when tasks start, run, and complete in overlapping time periods ! Parallelism: when two or more tasks execute simultaneously ! Why? ! Enable performance through parallelism ! Improve interactivity by handling user actions concurrent with processing and IO 5 http://docs.oracle.com/cd/E19455-01/806-5257/6je9h032b/index.html

6.
© 2013 AdobeSystems Incorporated. All Rights Reserved. No Raw Synchronization Primitives 6

7.
© 2013 AdobeSystems Incorporated. All Rights Reserved. What are raw synchronization primitives? ! Synchronization primitives are basic constructs such as: ! Mutex ! Atomic ! Semaphore ! Memory Fence ! Condition Variable 7

8.
© 2014 AdobeSystems Incorporated. All Rights Reserved. 8 Desktop Compute Power (8-core 3.5GHz Sandy Bridge + AMD Radeon 6950) 8

9.
© 2014 AdobeSystems Incorporated. All Rights Reserved. 8 Desktop Compute Power (8-core 3.5GHz Sandy Bridge + AMD Radeon 6950) 8 0 750 1500 2250 3000 GPU Vectorization Multi-thread Scalar (GFlops)

10.
© 2014 AdobeSystems Incorporated. All Rights Reserved. 8 Desktop Compute Power (8-core 3.5GHz Sandy Bridge + AMD Radeon 6950) 8 OpenGL OpenCL CUDA Direct Compute C++ AMP DirectX 0 750 1500 2250 3000 GPU Vectorization Multi-thread Scalar (GFlops)

11.
© 2014 AdobeSystems Incorporated. All Rights Reserved. 8 Desktop Compute Power (8-core 3.5GHz Sandy Bridge + AMD Radeon 6950) Intrinsics Auto-vectorization OpenCL 8 OpenGL OpenCL CUDA Direct Compute C++ AMP DirectX 0 750 1500 2250 3000 GPU Vectorization Multi-thread Scalar (GFlops)

12.
© 2014 AdobeSystems Incorporated. All Rights Reserved. 8 Desktop Compute Power (8-core 3.5GHz Sandy Bridge + AMD Radeon 6950) Intrinsics Auto-vectorization OpenCL 8 TBB GCD OpenMP C++11 OpenGL OpenCL CUDA Direct Compute C++ AMP DirectX 0 750 1500 2250 3000 GPU Vectorization Multi-thread Scalar (GFlops)

13.
© 2014 AdobeSystems Incorporated. All Rights Reserved. 8 Desktop Compute Power (8-core 3.5GHz Sandy Bridge + AMD Radeon 6950) Intrinsics Auto-vectorization OpenCL 8 Straight C++ TBB GCD OpenMP C++11 OpenGL OpenCL CUDA Direct Compute C++ AMP DirectX 0 750 1500 2250 3000 GPU Vectorization Multi-thread Scalar (GFlops)

14.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Threads and Tasks ! Thread: Execution environment consisting of a stack and processor state running in parallel to other threads ! Task: A unit of work, often a function, to be executed on a thread ! Tasks are scheduled on a thread pool to optimize machine utilization 9

15.
© 2014 AdobeSystems Incorporated. All Rights Reserved. C++14 and Tasks ! C++14 does not have a task system ! Threads ! Futures (more on this) 10

16.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Amdahl’s Law 11 http://en.wikipedia.org/wiki/Amdahl%27s_law

17.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Amdahl’s Law 12 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Processors Performance

18.
© 2014 AdobeSystems Incorporated. All Rights Reserved. What Makes It Slow ! Starvation ! Latency ! Overhead ! Wait 13 Hartmut Kaiser - HPX

19.
© 2013 AdobeSystems Incorporated. All Rights Reserved. Why No Raw Synchronization Primitives? 14 Object thread thread thread

20.
© 2013 AdobeSystems Incorporated. All Rights Reserved. Why No Raw Synchronization Primitives? 14 Object thread thread thread STOP STOP GO

21.

22.

23.
© 2013 AdobeSystems Incorporated. All Rights Reserved. Minimize Locks 15 STOP

24.
© 2013 AdobeSystems Incorporated. All Rights Reserved. Minimize Locks 15 STOP

25.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Building a Task System ! Portable Reference Implementation in C++14 ! Windows - Window Thread Pool and PPL ! Apple - Grand Central Dispatch (libdispatch) ! open source, runs on Linux and Android ! Intel TBB - many platforms ! open source ! HPX - many platforms ! open source 16

26.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Building a Task System 17 http://docs.oracle.com/cd/E19253-01/816-5137/ggedn/index.html Core Core Core… Thread Thread Thread . . . Task Task Task Task

27.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Building a Task System 18

28.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Building a Task System using lock_t = unique_lock<mutex>; 18

29.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Building a Task System using lock_t = unique_lock<mutex>; class notification_queue { deque<function<void()>> _q; mutex _mutex; condition_variable _ready; 18

30.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Building a Task System using lock_t = unique_lock<mutex>; class notification_queue { deque<function<void()>> _q; mutex _mutex; condition_variable _ready; public: void pop(function<void()>& x) { lock_t lock{_mutex}; while (_q.empty()) _ready.wait(lock); x = move(_q.front()); _q.pop_front(); } 18

31.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Building a Task System using lock_t = unique_lock<mutex>; class notification_queue { deque<function<void()>> _q; mutex _mutex; condition_variable _ready; public: void pop(function<void()>& x) { lock_t lock{_mutex}; while (_q.empty()) _ready.wait(lock); x = move(_q.front()); _q.pop_front(); } template<typename F> void push(F&& f) { { lock_t lock{_mutex}; _q.emplace_back(forward<F>(f)); } _ready.notify_one(); } }; 18

32.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Building a Task System 19

33.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Building a Task System class task_system { const unsigned _count{thread::hardware_concurrency()}; vector<thread> _threads; notification_queue _q; 19

34.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Building a Task System class task_system { const unsigned _count{thread::hardware_concurrency()}; vector<thread> _threads; notification_queue _q; void run(unsigned i) { while (true) { function<void()> f; _q.pop(f); f(); } } 19

35.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Building a Task System class task_system { const unsigned _count{thread::hardware_concurrency()}; vector<thread> _threads; notification_queue _q; void run(unsigned i) { while (true) { function<void()> f; _q.pop(f); f(); } } public: task_system() { for (unsigned n = 0; n != _count; ++n) { _threads.emplace_back([&, n]{ run(n); }); } } 19

36.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Building a Task System class task_system { const unsigned _count{thread::hardware_concurrency()}; vector<thread> _threads; notification_queue _q; void run(unsigned i) { while (true) { function<void()> f; _q.pop(f); f(); } } public: task_system() { for (unsigned n = 0; n != _count; ++n) { _threads.emplace_back([&, n]{ run(n); }); } } ~task_system() { for (auto& e : _threads) e.join(); } 19

37.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Building a Task System class task_system { const unsigned _count{thread::hardware_concurrency()}; vector<thread> _threads; notification_queue _q; void run(unsigned i) { while (true) { function<void()> f; _q.pop(f); f(); } } public: task_system() { for (unsigned n = 0; n != _count; ++n) { _threads.emplace_back([&, n]{ run(n); }); } } ~task_system() { for (auto& e : _threads) e.join(); } template <typename F> void async_(F&& f) { _q.push(forward<F>(f)); } }; 19

38.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Building a Task System class notification_queue { deque<function<void()>> _q; bool _done{false}; mutex _mutex; condition_variable _ready; public: void done() { { unique_lock<mutex> lock{_mutex}; _done = true; } _ready.notify_all(); } bool pop(function<void()>& x) { lock_t lock{_mutex}; while (_q.empty() && !_done) _ready.wait(lock); if (_q.empty()) return false; x = move(_q.front()); _q.pop_front(); return true; } template<typename F> void push(F&& f) { { lock_t lock{_mutex}; _q.emplace_back(forward<F>(f)); 20

39.

40.

41.

42.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Building a Task System 21 Core Core Core… Thread Thread Thread . . . Task Task Task Task

43.

44.
© 2013 AdobeSystems Incorporated. All Rights Reserved. Why No Raw Synchronization Primitives? 22 Object thread thread thread

45.

46.

47.

48.

49.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Building a Task System 24 Core Core Core… Thread Thread Thread . . . Task Task Task . . . Task Task Task . . . Task Task Task Task Scheduler

50.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Building a Task System class task_system { const unsigned _count{thread::hardware_concurrency()}; vector<thread> _threads; vector<notification_queue> _q{_count}; atomic<unsigned> _index{0}; void run(unsigned i) { while (true) { function<void()> f; if (!_q[i].pop(f)) break; f(); } } public: task_system() { } ~task_system() { for (auto& e : _q) e.done(); for (auto& e : _threads) e.join(); } template <typename F> void async_(F&& f) { auto i = _index++; _q[i % _count].push(forward<F>(f)); } }; 25

51.

52.

53.

54.

55.

56.

57.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Building a Task System 27 Core Core Core… Thread Thread Thread . . . Task Task Task . . . Task Task Task . . . Task Task Task Task Scheduler Task Stealing

58.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Building a Task System class notification_queue { deque<function<void()>> _q; bool _done{false}; mutex _mutex; condition_variable _ready; public: bool try_pop(function<void()>& x) { lock_t lock{_mutex, try_to_lock}; if (!lock || _q.empty()) return false; x = move(_q.front()); _q.pop_front(); return true; } template<typename F> bool try_push(F&& f) { { lock_t lock{_mutex, try_to_lock}; if (!lock) return false; _q.emplace_back(forward<F>(f)); } _ready.notify_one(); return true; } void done() { { unique_lock<mutex> lock{_mutex}; 28

59.

60.

61.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Building a Task System void run(unsigned i) { while (true) { function<void()> f; for (unsigned n = 0; n != _count; ++n) { if (_q[(i + n) % _count].try_pop(f)) break; } if (!f && !_q[i].pop(f)) break; f(); } } public: task_system() { } ~task_system() { } template <typename F> void async_(F&& f) { auto i = _index++; for (unsigned n = 0; n != _count; ++n) { if (_q[(i + n) % _count].try_push(forward<F>(f))) return; } _q[i % _count].push(forward<F>(f)); } }; 29

62.

63.

64.

65.

66.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Task System ! Within a few percentage points of Apple’s GCD (libdispatch) under load ! Can be improved by spinning more on try_pop in run 31

67.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Futures 32 future<cpp_int> x = async([]{ return fibonacci<cpp_int>(1'000'000); }); // Do Something cout << x.get() << endl;

68.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Futures ! Fibonacci is often used as an example for parallel algorithms ! Please stop… 32 future<cpp_int> x = async([]{ return fibonacci<cpp_int>(1'000'000); }); // Do Something cout << x.get() << endl;

69.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Public Service Announcement - How to Write Fibonacci template <typename T, typename N, typename O> T power(T x, N n, O op) { if (n == 0) return identity_element(op); while ((n & 1) == 0) { n >>= 1; x = op(x, x); } T result = x; n >>= 1; while (n != 0) { x = op(x, x); if ((n & 1) != 0) result = op(result, x); n >>= 1; } return result; } 33

70.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Public Service Announcement - How to Write Fibonacci template <typename T, typename N, typename O> T power(T x, N n, O op) { if (n == 0) return identity_element(op); while ((n & 1) == 0) { n >>= 1; x = op(x, x); } T result = x; n >>= 1; while (n != 0) { x = op(x, x); if ((n & 1) != 0) result = op(result, x); n >>= 1; } return result; } 33 Egyptian Multiplication (Russian Peasant Algorithm) See “From Mathematics to Generic Programming” - Alex Stepanov and Dan Rose

71.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Public Service Announcement - How to Write Fibonacci template <typename N> struct multiply_2x2 { array<N, 4> operator()(const array<N, 4>& x, const array<N, 4>& y) { return { x[0] * y[0] + x[1] * y[2], x[0] * y[1] + x[1] * y[3], x[2] * y[0] + x[3] * y[2], x[2] * y[1] + x[3] * y[3] }; } }; template <typename N> array<N, 4> identity_element(const multiply_2x2<N>&) { return { N(1), N(0), N(0), N(1) }; } template <typename R, typename N> R fibonacci(N n) { if (n == 0) return R(0); return power(array<R, 4>{ 1, 1, 1, 0 }, N(n - 1), multiply_2x2<R>())[0]; } 34

72.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Futures 19532821287077577316320149475962563324435429965918733969534051945716252578870156947666419876341501461288795 24335220236084625510912019560233744015438115196636156919962125642894303370113827800638002767411527927466669 86557837931882283206127149758323033485489348957259923072291290192820926433162752173086146001791258204269965 99360209593392020051848620284024473431398113674187202038684801753185386211128781082406177413832935545616876 06454065125954718029126547942894036981659206361019359291352135410376799082940320155702716115395031975973247 78216295763162965335669477766328506234524559346064757502593581344345781676764625878859011372729907372947851 14480895724561915035070255895291168685500088020132334587472177947814475467920160901706425856293597475465327 57575740077432034913428785189795354304734560307765078938767286539166799232817449361991523768149557632085371 04785970618843873153058239562756087906310781900497516959470973671389174570455520213512335079440336071203050 41446852210415650373210679322756258647511914611417360349681217380234224786080292021093192496490409832397066 83247054441763512526732455275419501683845206023007394959854279298297831204382115757645787692495583351402522 15272066244180900325938075362849179668095297118507191379833678873770459913639333955814212036990261617972113 25091840023055327607104316478190974300434647793363287601469996128023925829471557316688943339455429292871877 48774789204296166356536610796023919702109728472966709427334586344798048633944635211654971507261342768205479 32093175079888010130416027982506354182344034558742236701282666356934611294613123128389060036547327660245693 15151850018328483150645480029978935985161237074046158229354440701748339514575869547491750264542126364262224 72060048855462589961190475892101224280542898621594646662478564373572217775549876087685912030118551635668902 01034463998397732663888903650784161807091545252992759735213957415477729146008794314339156060445825107823511 66271892637923313014643880597879468444879060576786297460989627426663569682474293386740207436559426057944790 71193052258931590719386545525880429139747140181849169733838138446154843063123649290835584278078456131936457 55911722136946338180311600307896211668652895953778436464402382516362449718197385444149563131714002850338928 22274134603018094224837216321854717270452813824078425638747365249141118080783866506339945376239206700513391 87333107136069698189628284763245423299306272870457991293245741167533902274499963096566680922262516468582544 55785134982414412726124015815753818098466667145006988839178551800894370189025721992485208742915560261917752 28124660628996787166529678487268484905041328497297712688011639978376434280202452251550102240354169885185375 01584673881194047619720619603126534496759917893244478170702904446589571950228809157793897642423751814020998 99958161231477902295781100168670186738619861797138139854666281969548553740707356228616165539428076418408092 12047932816683005984504787929406356318097479755152035094682765918741610907637506902765294367561539803261388 35

73.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Futures 15790155892833100345673846243104676900000936756893803676769777642059716492347060997973282994459039755683869 10568541105888505197986232161807165960864316652383369579251545877324797429523572491518310013505994095431367 23454418539676396422570487868443336735568511535850565172490141772333018072390350689838662532338266203548476 87722321662223383305226882245421258277211223435986491973881404168406609216954760818955479619408040043497601 35646408461148077885537891122888139618703907906033147416881433658136276942006644505679690480702792206520855 12245086839375655196861305232092138041808273198852928058246964575561801618520046644949262341864859342928965 21378574554544426221453176445385228867960454072522804961741905198550911362542849130027243353553345377968558 49780195976636516290598457219043489821358221206856924121139313137132134865741440892670003665555632446499775 56853514681289887391700907057970839124191923062570547772748610990924519168225326823578140721238189631411471 29610287340041050015549547086272721534936510345705849389706515725684266079756708385889612130516276472992631 59674474594901199950849178952149715987731953191759591623424021718579696778102054496598766846143959650647332 21985323521378108187030642875506951890343587181633604126397675020909133548480151135951824112432636080497447 37395896608759569909256138919905403404664655310556021101996525724843421071082933739200159651403373870955680 75656822683537933983982488022723770319785461480932302347255796621173892988541730741484707211664044157057536 04582256143224299859780683239696543855523783781413866750792868372058020433472254190336846843017198934115689 96526838242546875 35 0.72s to calculate 208,988 digits

74.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Futures 36 future<cpp_int> x = async([]{ return fibonacci<cpp_int>(1'000'000); }); // Do Something cout << x.get() << endl;

75.
f(…)->r © 2014 AdobeSystems Incorporated. All Rights Reserved. Futures 37

76.
f(…) r © 2014Adobe Systems Incorporated. All Rights Reserved. Futures 37

77.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Futures ! Futures allow minimal code transformations to express dependencies 38

78.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Futures: What year is this? ! C++14 futures have: ! Exception Marshaling ! Sever Notification (broken promise) 39

79.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Futures: What year is this? ! C++14 futures lack: ! Continuations - .then() ! Joins - when_all() ! Cancelation ! Progress Monitoring (Except Ready) ! … ! And C++14 futures don’t compose (easily) to add these features 40

80.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Futures: Continuations 41

81.
© 2013 AdobeSystems Incorporated. All Rights Reserved. Futures: Continuations ! Blocking on std::future.get() has two problems ! One thread resource is consumed, increasing contention ! Any subsequent non-dependent calculations on the task are also blocked ! C++14 doesn’t have continuations ! GCD has serialized queues and groups ! PPL has chained tasks ! TBB has flow graphs ! TS Concurrency will have them ! Boost futures have them now 42

82.
© 2013 AdobeSystems Incorporated. All Rights Reserved. Futures: Continuations future<cpp_int> x = async([]{ return fibonacci<cpp_int>(1'000'000); }); future<void> y = x.then([](future<cpp_int> x){ cout << x.get() << endl; }); // Do something y.wait(); 43

83.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Futures 44

84.
© 2013 AdobeSystems Incorporated. All Rights Reserved. Futures: Continuations auto x = async([]{ return fibonacci<cpp_int>(1'000'000); }); auto y = async([]{ return fibonacci<cpp_int>(2'000'000); }); auto z = when_all(std::move(x), std::move(y)).then([](auto f){ auto t = f.get(); return cpp_int(get<0>(t).get() * get<1>(t).get()); }); cout << z.get() << endl; 45

85.
© 2013 AdobeSystems Incorporated. All Rights Reserved. Futures: Continuations auto x = async([]{ return fibonacci<cpp_int>(1'000'000); }); auto y = async([]{ return fibonacci<cpp_int>(2'000'000); }); auto z = when_all(std::move(x), std::move(y)).then([](auto f){ auto t = f.get(); return cpp_int(get<0>(t).get() * get<1>(t).get()); }); cout << z.get() << endl; 45 f is a future tuple of futures

86.
© 2013 AdobeSystems Incorporated. All Rights Reserved. Futures: Continuations auto x = async([]{ return fibonacci<cpp_int>(1'000'000); }); auto y = async([]{ return fibonacci<cpp_int>(2'000'000); }); auto z = when_all(std::move(x), std::move(y)).then([](auto f){ auto t = f.get(); return cpp_int(get<0>(t).get() * get<1>(t).get()); }); cout << z.get() << endl; 45 f is a future tuple of futures result is 626,964 digits

87.

88.
© 2013 AdobeSystems Incorporated. All Rights Reserved. Futures: Continuations future<cpp_int> x = async([]{ return fibonacci<cpp_int>(100); }); future<cpp_int> y = x.then([](future<cpp_int> x){ return cpp_int(x.get() * 2); }); future<cpp_int> z = x.then([](future<cpp_int> x){ return cpp_int(x.get() / 15); }); 47

89.
© 2013 AdobeSystems Incorporated. All Rights Reserved. Futures: Continuations future<cpp_int> x = async([]{ return fibonacci<cpp_int>(100); }); future<cpp_int> y = x.then([](future<cpp_int> x){ return cpp_int(x.get() * 2); }); future<cpp_int> z = x.then([](future<cpp_int> x){ return cpp_int(x.get() / 15); }); 47 Assertion failed: (px != 0), function operator->, file shared_ptr.hpp, line 648.

90.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Continuations ! Desired behavior ! A future should behave as a regular type - a token for the actual value ! shared_futures let me pass them around and do multiple get() operations, but don’t fix continuations ! [at least with boost] ! Releasing the last instance of a future should cancel (no-op) any unexecuted, contributing, operations 48

91.

92.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Futures 49 shared

93.

94.
© 2014 AdobeSystems Incorporated. All Rights Reserved. Futures 50 shared shared shared

95.
© 2013 AdobeSystems Incorporated. All Rights Reserved. Futures: Building, The template <typename> struct result_of_; //not defined template <typename R, typename... Args> struct result_of_<R(Args...)> { using type = R; }; template <typename F> using result_of_t_ = typename result_of_<F>::type; 51

96.
© 2013 AdobeSystems Incorporated. All Rights Reserved. Futures: Building, The template <typename> struct result_of_; //not defined template <typename R, typename... Args> struct result_of_<R(Args...)> { using type = R; }; template <typename F> using result_of_t_ = typename result_of_<F>::type; 51 result_of_t_<int(double)> -> int

97.
© 2013 AdobeSystems Incorporated. All Rights Reserved. Futures: Building, The template <typename> class packaged_task; //not defined template <typename R> class future { shared_ptr</* ... */> _p; public: future() = default; template <typename F> auto then(F&& f) { } const R& get() const { } }; template<typename R, typename ...Args > class packaged_task<R (Args...)> { weak_ptr</* ... */> _p; public: packaged_task() = default; template <typename... A> void operator()(A&&... args) const { } }; 52

98.

99.

100.

101.

102.
© 2013 AdobeSystems Incorporated. All Rights Reserved. template <typename> class packaged_task; //not defined template <typename> class future; template <typename S, typename F> auto package(F&& f) -> pair<packaged_task<S>, future<result_of_t_<S>>>; template <typename R> class future { shared_ptr</* ... */> _p; template <typename S, typename F> friend auto package(F&& f) -> pair<packaged_task<S>, future<result_of_t_<S>>>; explicit future(shared_ptr</* ... */> p) : _p(move(p)) { } /* ... */ }; template<typename R, typename ...Args > class packaged_task<R (Args...)> { weak_ptr</* ... */> _p; template <typename S, typename F> friend auto package(F&& f) -> pair<packaged_task<S>, future<result_of_t_<S>>>; explicit packaged_task(weak_ptr</* ... */> p) : _p(move(p)) { } /* ... */ }; Futures: Building, The 53

103.

104.

105.

106.
© 2013 AdobeSystems Incorporated. All Rights Reserved. template <typename S, typename F> auto package(F&& f) -> pair<packaged_task<S>, future<result_of_t_<S>>> { auto p = make_shared<shared<S>>(forward<F>(f)); return make_pair(packaged_task<S>(p), future<result_of_t_<S>>(p)); } Futures: Building, The 54

107.
© 2013 AdobeSystems Incorporated. All Rights Reserved. template <typename S, typename F> auto package(F&& f) -> pair<packaged_task<S>, future<result_of_t_<S>>> { auto p = make_shared<shared<S>>(forward<F>(f)); return make_pair(packaged_task<S>(p), future<result_of_t_<S>>(p)); } Futures: Building, The 54 package<int(double)>(f) -> { void(double), future<int> }

108.
© 2013 AdobeSystems Incorporated. All Rights Reserved. template <typename R> struct shared_base { vector<R> _r; // optional mutex _mutex; condition_variable _ready; vector<function<void()>> _then; virtual ~shared_base() { } /* ... */ }; template <typename> struct shared; // not defined template <typename R, typename... Args> struct shared<R(Args...)> : shared_base<R> { function<R(Args...)> _f; template<typename F> shared(F&& f) : _f(forward<F>(f)) { } /* ... */ }; Futures: Building, The 55

109.

110.

111.
© 2013 AdobeSystems Incorporated. All Rights Reserved. template<typename R, typename ...Args > class packaged_task<R (Args...)> { weak_ptr<shared<R(Args...)>> _p; template <typename S, typename F> friend auto package(F&& f) -> pair<packaged_task<S>, future<result_of_t_<S>>>; explicit packaged_task(weak_ptr<shared<R(Args...)>> p) : _p(move(p)) { } public: packaged_task() = default; template <typename... A> void operator()(A&&... args) const { auto p = _p.lock(); if (p) (*p)(forward<A>(args)...); } }; Futures: Building, The 56

112.

113.

114.
© 2013 AdobeSystems Incorporated. All Rights Reserved. template <typename R, typename... Args> struct shared<R(Args...)> : shared_base<R> { function<R(Args...)> _f; template<typename F> shared(F&& f) : _f(forward<F>(f)) { } template <typename... A> void operator()(A&&... args) { this->set(_f(forward<A>(args)...)); _f = nullptr; } }; Futures: Building, The 57

115.
© 2013 AdobeSystems Incorporated. All Rights Reserved. template <typename R, typename... Args> struct shared<R(Args...)> : shared_base<R> { function<R(Args...)> _f; template<typename F> shared(F&& f) : _f(forward<F>(f)) { } template <typename... A> void operator()(A&&... args) { this->set(_f(forward<A>(args)...)); _f = nullptr; } }; Futures: Building, The 57

116.
© 2013 AdobeSystems Incorporated. All Rights Reserved. template <typename R> struct shared_base { vector<R> _r; // optional mutex _mutex; condition_variable _ready; vector<function<void()>> _then; virtual ~shared_base() { } void set(R&& r) { vector<function<void()>> then; { lock_t lock{_mutex}; _r.push_back(move(r)); swap(_then, then); } _ready.notify_all(); for (const auto& f : then) _system.async_(move(f)); } }; Futures: Building, The 58

117.
© 2013 AdobeSystems Incorporated. All Rights Reserved. template <typename R> struct shared_base { vector<R> _r; // optional mutex _mutex; condition_variable _ready; vector<function<void()>> _then; virtual ~shared_base() { } void set(R&& r) { vector<function<void()>> then; { lock_t lock{_mutex}; _r.push_back(move(r)); swap(_then, then); } _ready.notify_all(); for (const auto& f : then) _system.async_(move(f)); } }; Futures: Building, The 58

118.
© 2013 AdobeSystems Incorporated. All Rights Reserved. template <typename R> class future { shared_ptr<shared_base<R>> _p; template <typename S, typename F> friend auto package(F&& f) -> pair<packaged_task<S>, future<result_of_t_<S>>>; explicit future(shared_ptr<shared_base<R>> p) : _p(move(p)) { } public: future() = default; template <typename F> auto then(F&& f) { auto pack = package<result_of_t<F(R)>()>([p = _p, f = forward<F>(f)](){ return f(p->_r.back()); }); _p->then(move(pack.first)); return pack.second; } const R& get() const { return _p->get(); } }; Futures: Building, The 59

119.

120.

121.

122.
© 2013 AdobeSystems Incorporated. All Rights Reserved. template <typename R> struct shared_base { vector<R> _r; // optional mutex _mutex; condition_variable _ready; vector<function<void()>> _then; virtual ~shared_base() { } void set(R&& r) { } template <typename F> void then(F&& f) { bool resolved{false}; { lock_t lock{_mutex}; if (_r.empty()) _then.push_back(forward<F>(f)); else resolved = true; } if (resolved) _system.async_(move(f)); } const R& get() { lock_t lock{_mutex}; while (_r.empty()) _ready.wait(lock); return _r.back(); } }; Futures: Building, The 60

123.

124.

125.

127.
© 2013 AdobeSystems Incorporated. All Rights Reserved. template <typename F, typename ...Args> auto async(F&& f, Args&&... args) { using result_type = result_of_t<F (Args...)>; using packaged_type = packaged_task<result_type()>; auto pack = package<result_type()>(bind(forward<F>(f), forward<Args>(args)...)); _system.async_(move(get<0>(pack))); return get<1>(pack); } Futures: Building, The 62

128.
© 2013 AdobeSystems Incorporated. All Rights Reserved. Futures: Continuations future<cpp_int> x = async([]{ return fibonacci<cpp_int>(100); }); future<cpp_int> y = x.then([](const cpp_int& x){ return cpp_int(x * 2); }); future<cpp_int> z = x.then([](const cpp_int& x){ return cpp_int(x / 15); }); cout << y.get() << endl; cout << z.get() << endl; 63

129.
© 2013 AdobeSystems Incorporated. All Rights Reserved. Futures: Continuations future<cpp_int> x = async([]{ return fibonacci<cpp_int>(100); }); future<cpp_int> y = x.then([](const cpp_int& x){ return cpp_int(x * 2); }); future<cpp_int> z = x.then([](const cpp_int& x){ return cpp_int(x / 15); }); cout << y.get() << endl; cout << z.get() << endl; 63 708449696358523830150 23614989878617461005

132.
© 2013 AdobeSystems Incorporated. All Rights Reserved. What if we persist the graph? ! Allow multiple invocations of the tasks by setting the source values ! Each change triggers a notification to the sink values ! This is a reactive programming model and futures are known as behaviors 66

135.
© 2013 AdobeSystems Incorporated. All Rights Reserved. A function is a directed relationship ! We can remove the arrows by providing a package of functions to represent the relationship ! a = b * c  b = a / c  c = a / b ! This forms a type of constraint system called a property model ! Flow is determined by value, or cell, priority ! Cells can only have one in-edge for a given flow or the system is over constrained 69

137.
© 2013 AdobeSystems Incorporated. All Rights Reserved. Property Models ! Reflowing a property model doesn’t require all relationships to be resolved ! The task representing them can still be executing concurrently ! This creates a single dependency graph that is appended to for each new flow and is pruned and unravels as tasks are complete 71

139.
© 2013 AdobeSystems Incorporated. All Rights Reserved. Final Thoughts ! Perhaps representing such systems as if it where imperative code is not the correct approach ! Instead the a graph description can be compiled and statically validated 73

Better Code: Concurrency

More Related Content

What's hot

Similar to Better Code: Concurrency

More from Platonov Sergey

Recently uploaded

Better Code: Concurrency