1 /* 2 * Copyright 2017 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #ifndef SkTaskGroup2D_DEFINED 9 #define SkTaskGroup2D_DEFINED 10 11 #include "SkTaskGroup.h" 12 13 #include <mutex> 14 #include <vector> 15 16 // The interface for doing work on a 2D grid with possible initialization on columns. 17 class SkWorkKernel2D { 18 public: 19 // Return false iff the column needs initialization and such initialization is not finished yet. 20 virtual bool work2D(int row, int column, int thread) = 0; 21 22 // Return false if no initialization is done for this colum (e.g., it's already initialized; or 23 // maybe some other thread is initializing the column). 24 virtual bool initColumn(int column, int thread) = 0; 25 ~SkWorkKernel2D()26 virtual ~SkWorkKernel2D() {} 27 }; 28 29 // A 2D grid (height rows x width columns) of tasks to be executed on a given executor with 30 // threadCnt number of threads. 31 // 32 // The height (number of rows) is fixed. The width (number of columns) may be dynamically expanded. 33 // 34 // The task on row i and column j is abstracted as work2D(i, j, t). Parameter t is the thread id and 35 // it shouldn't affect the work to be done. It's only used to allow some variables that are not 36 // thread safe and should be used exclusively by one thread (e.g., thread allocators). We guarantee 37 // that the task on the same row will be executed in order (i.e., work2D(1, 1, t) is guaranteed to 38 // finish before calling work2D(1, 2, t)). Tasks in different rows can happen in any order. 39 // 40 // There are also width number of init calls, one per column. work2D(i, j, t) may return false if 41 // column j requires initialization but it's not initialized yet. In that case, a thread t needs to 42 // call initColumn(j, t) once to unblock all rows that depend on the initialization of column j. 43 // (Again, t shouldn't affect the init work to be done; it's just for some non-thread-safe 44 // variables). The init calls have no order requirement so we can call them in any order. 45 // 46 // Multiple therads may try to init the same column j at the same time. InitFn is expected to handle 47 // this gracefully (e.g., let only one thread do the init and return immediately for other threads). 48 class SkTaskGroup2D { 49 public: SkTaskGroup2D(SkWorkKernel2D * kernel,int height,SkExecutor * executor,int threadCnt)50 SkTaskGroup2D(SkWorkKernel2D* kernel, int height, SkExecutor* executor, int threadCnt) 51 : fKernel(kernel), fHeight(height), fThreadCnt(threadCnt), fIsFinishing(false) 52 , fWidth(0), fThreadsGroup(new SkTaskGroup(*executor)) {} 53 ~SkTaskGroup2D()54 virtual ~SkTaskGroup2D() {} 55 56 virtual void addColumn(); // Add a new column of tasks. 57 58 void start(); // start threads to execute tasks 59 void finish(); // wait and finish all tasks (no more tasks can be added after calling this) 60 isFinishing()61 SK_ALWAYS_INLINE bool isFinishing() const { 62 return fIsFinishing.load(std::memory_order_relaxed); 63 } 64 65 protected: 66 static constexpr int MAX_CACHE_LINE = 64; 67 68 // Finish all tasks on the threadId and then return. 69 virtual void work(int threadId) = 0; 70 71 // Initialize a column that needs to be initialized. The parameter initCol is not thread safe 72 // and should only be exclusively accessed by the working thread which will modify it to the 73 // column that may need to be initialized next. initAnUninitializedColumn(int & initCol,int threadId)74 void initAnUninitializedColumn(int& initCol, int threadId) { 75 bool didSomeInit = false; 76 while (initCol < fWidth && !didSomeInit) { 77 didSomeInit = fKernel->initColumn(initCol++, threadId); 78 } 79 } 80 81 SkWorkKernel2D* fKernel; 82 const int fHeight; 83 const int fThreadCnt; 84 85 std::atomic<bool> fIsFinishing; 86 std::atomic<int> fWidth; 87 88 std::unique_ptr<SkTaskGroup> fThreadsGroup; 89 }; 90 91 // A simple spinning task group that assumes height equals threadCnt. 92 class SkSpinningTaskGroup2D final : public SkTaskGroup2D { 93 public: SkSpinningTaskGroup2D(SkWorkKernel2D * kernel,int h,SkExecutor * x,int t)94 SkSpinningTaskGroup2D(SkWorkKernel2D* kernel, int h, SkExecutor* x, int t) 95 : SkTaskGroup2D(kernel, h, x, t) { 96 SkASSERT(h == t); // height must be equal to threadCnt 97 } 98 99 protected: 100 void work(int threadId) override; 101 }; 102 103 class SkFlexibleTaskGroup2D final : public SkTaskGroup2D { 104 public: SkFlexibleTaskGroup2D(SkWorkKernel2D * kernel,int h,SkExecutor * x,int t)105 SkFlexibleTaskGroup2D(SkWorkKernel2D* kernel, int h, SkExecutor* x, int t) 106 : SkTaskGroup2D(kernel, h, x, t), fRowData(h) {} 107 108 protected: 109 void work(int threadId) override; 110 111 private: 112 // alignas(MAX_CACHE_LINE) to avoid false sharing by cache lines 113 struct alignas(MAX_CACHE_LINE) RowData { RowDataRowData114 RowData() : fNextColumn(0) {} 115 116 int fNextColumn; // next column index to work 117 std::mutex fMutex; // the mutex for the thread to acquire 118 }; 119 120 std::vector<RowData> fRowData; 121 }; 122 123 #endif//SkTaskGroup2D_DEFINED 124