1.. _Lazy_Initialization:
2
3Lazy Initialization
4====================
5
6
7.. container:: section
8
9
10   .. rubric:: Problem
11      :class: sectiontitle
12
13   Delay the creation of an object, potentially expensive, until it is accessed.
14   In parallel programming, initialization must also be guarded against race conditions.
15
16
17.. container:: section
18
19
20   .. rubric:: Context
21      :class: sectiontitle
22
23   The cost of operations that take place during the initialization
24   of the object may be considerably high. In that case, the object
25   should be initialized only when needed. Lazy initialization is
26   the common tactic that allows implementing such an approach.
27
28
29.. container:: section
30
31
32   .. rubric:: Solution
33      :class: sectiontitle
34
35   Using ``oneapi::tbb::collaborative_call_once`` with ``oneapi::tbb::collaborative_once_flag``
36   helps to implement thread-safe lazy initialization for a user object.
37
38
39   In addition, ``collaborative_call_once`` allows other thread blocked on
40   the same ``collaborative_once_flag`` to join other |short_name|
41   parallel constructions called within the initializing function.
42
43
44.. container:: section
45
46
47   .. rubric:: Example
48      :class: sectiontitle
49
50   This example illustrates the implementation of lazy initialization
51   for the calculation of the Fibonacci numbers. Here is a graphical
52   representation of the Fibonacci recursion tree for N=4.
53
54
55   |image0|
56
57
58   As seen in the diagram, some elements are recalculated more than once. These operations are redundant,
59   so the "lazy initialized" Fibonacci numbers are relevant here.
60
61
62   An implementation without the use of lazy initialization would have *O(2^N)* time complexity due to
63   the full recursion tree traversal and recalculation of values. Since all the nodes are traversed once,
64   the tree becomes a list, making the time complexity *O(N)*.
65
66
67   |image1|
68
69
70   Here you can see the code for the implementation. Already calculated values are stored in a buffer
71   paired with ``collaborative_once_flag`` and will not be recalculated when ``collaborative_call_once``
72   is invoked when initialization has already been done.
73
74
75   ::
76
77
78      using FibBuffer = std::vector<std::pair<oneapi::tbb::collaborative_once_flag, std::uint64_t>>;
79
80      std::uint64_t LazyFibHelper(int n, FibBuffer& buffer) {
81         // Base case
82         if (n <= 1) {
83            return n;
84         }
85         // Calculate nth value only once and store it in the buffer.
86         // Other threads won't be blocked on already taken collaborative_once_flag
87         // but join parallelism inside functor
88         oneapi::tbb::collaborative_call_once(buffer[n].first, [&]() {
89            std::uint64_t a, b;
90            oneapi::tbb::parallel_invoke([&] { a = LazyFibHelper(n - 2, buffer); },
91                                         [&] { b = LazyFibHelper(n - 1, buffer); });
92            buffer[n].second = a + b;
93         });
94
95         return buffer[n].second;
96      }
97
98      std::uint64_t Fib(int n) {
99         FibBuffer buffer(n+1);
100         return LazyFibHelper(n, buffer);
101      }
102
103
104.. |image0| image:: Images/image008a.jpg
105   :width: 744px
106   :height: 367px
107.. |image1| image:: Images/image009a.jpg
108   :width: 744px
109   :height: 367px
110