Change Details

## What is the update cache? In short: The update cache stores what elements have changed since the last time the eval object was updated. Additionally, the update cache can now store multiple updates to the data and minimizes the number of elements that need to be copied. ## Motivation In our previous proposal (T93934) the elements that changed were tagged in the original data-block and had to be searched for when the update of the eval object took place. This means that in the worst case, the entire data-block had to be iterated through (into all the layers, into all frames and over all the strokes). Our profiling showed that close to 100% of the time was simply spent iterating over the linked-lists checking if something had been tagged. The update cache is our attempt at solving this problem. ## Tagging To make use of the update cache, we need to tag elements that need to be updated. This is done using dedicated BKE functions. **Full update tag (`BKE_gpencil_tag_full_update`)** The full update tag will update the element itself, but also all of its content. E.g. a full update tag on a layer will not only copy the layer, but also the entire frames and strokes in that layer. **Struct update tag (`BKE_gpencil_tag_struct_update`)** The struct update is a lighter type of update: it will only update the properties of an element, leaving its underlying content unchanged. E.g a struct copy can be used to indicate that a layer's name has been modified or that a keyframe selection status has changed. ## Explanation of the Update Cache Here is a diagram of what an update cache might look like after some operation on the grease pencil data happend: {F12839570, width=100%} As we can see, the cache resembles a tree. This is because the grease pencil data can be divided up into four distinct “levels”. The upper-most level is the whole data-block, then below are layers and then frames and finally strokes. Each one of those levels fully contains the others below, hence the tree structure. An update cache node is composed of 4 things: # The **index** of the cached element in the linked-list. E.g. when a node caches an update of a frame, the index is where that frame is in the linked-list of all the frames in its layer. In the diagram, this is the number inside the node. # A **flag** indicating the type of update: full, struct, or no update. # A **data pointer** to the element that is cached. The pointer might be null if the node does not cache an update for this element, but it will still store its index. These nodes are indicated using dashed lines in the diagram. Nodes that do have a valid data pointer are indicated with a bold circle for struct updates and a square for full updates. These are the nodes that were tagged for an update. # The **children** nodes. This is an ordered map with the key being the index and the value being an update cache node. This also means that an update cache node can have 0 or more children (except if it is on the lowest level, e.g. a stroke). To minimize the number of updates needed, the update cache does the following optimization: If a node in the update cache tree indicates a full update it mustn't have any children. This can be done, because the element that a node represents must contain all the data that is represented by the children nodes. So for example, during the `update_on_write`, if a layer was tagged and needs to be copied, all of the data contained in that layer will of course be copied as well. So there is no need to e.g. tag a frame in that layer, because it would be copied twice. So to summarize our update cache tree has these properties: - Nodes can have 0 or more children. - Only the leaf nodes cache elements that need a full update. - Any node may cache elements that require a struct update. We use an ordered map for the children of the nodes to be able to do a single iteration over the eval data-block. Since the indices are sorted, we can always find the next element by iterating forwards. ## Updating the eval object With the update cache, the original object is no longer copied to replace the current eval object (copy-on-write). Instead, the eval object is updated, meaning that only parts will be copied over from the original (we call this **update-on-write**). The assumption here is that these parts were correctly tagged and nothing else changed. This then guarantees that the indices in our cache are the same on the eval object so we can use them to find the elements that need to be replaced. Updating then becomes almost trivial. We just iterate over the levels in the update cache tree, iterate over the children nodes, check if they need to be replaced and then do so. All the information needed to perform the replacement is stored in the node. ## Implementation - TODO: link to patch

## What is the update cache? In short: The update cache stores what elements have changed since the last time the eval object was updated. Additionally, the update cache can now store multiple updates to the data and minimizes the number of elements that need to be copied. ## Motivation In our previous proposal (T93934) the elements that changed were tagged in the original data-block and had to be searched for when the update of the eval object took place. This means that in the worst case, the entire data-block had to be iterated through (into all the layers, into all frames and over all the strokes). Our profiling showed that close to 100% of the time was simply spent iterating over the linked-lists checking if something had been tagged. The update cache is our attempt at solving this problem. ## Tagging To make use of the update cache, we need to tag elements that need to be updated. This is done using dedicated BKE functions. **Full update tag (`BKE_gpencil_tag_full_update`)** The full update tag will update the element itself, but also all of its content. E.g. a full update tag on a layer will not only copy the layer, but also the entire frames and strokes in that layer. **Struct update tag (`BKE_gpencil_tag_struct_update`)** The struct update is a lighter type of update: it will only update the properties of an element, leaving its underlying content unchanged. E.g a struct copy can be used to indicate that a layer's name has been modified or that a keyframe selection status has changed. ## Explanation of the Update Cache Here is a diagram of what an update cache might look like after some operation on the grease pencil data happend: {F12839570, width=100%} As we can see, the cache resembles a tree. This is because the grease pencil data can be divided up into four distinct “levels”. The upper-most level is the whole data-block, then below are layers and then frames and finally strokes. Each one of those levels fully contains the others below, hence the tree structure. An update cache node is composed of 4 things: # The **index** of the cached element in the linked-list. E.g. when a node caches an update of a frame, the index is where that frame is in the linked-list of all the frames in its layer. In the diagram, this is the number inside the node. # A **flag** indicating the type of update: full, struct, or no update. # A **data pointer** to the element that is cached. The pointer might be null if the node does not cache an update for this element, but it will still store its index. These nodes are indicated using dashed lines in the diagram. Nodes that do have a valid data pointer are indicated with a bold circle for struct updates and a square for full updates. These are the nodes that were tagged for an update. # The **children** nodes. This is an ordered map with the key being the index and the value being an update cache node. This also means that an update cache node can have 0 or more children (except if it is on the lowest level, e.g. a stroke). To minimize the number of updates needed, the update cache does the following optimization: If a node in the update cache tree indicates a full update it mustn't have any children. This can be done, because the element that a node represents must contain all the data that is represented by the children nodes. So for example, during the `update_on_write`, if a layer was tagged and needs to be copied, all of the data contained in that layer will of course be copied as well. So there is no need to e.g. tag a frame in that layer, because it would be copied twice. So to summarize our update cache tree has these properties: - Nodes can have 0 or more children. - Only the leaf nodes cache elements that need a full update. - Any node may cache elements that require a struct update. We use an ordered map for the children of the nodes to be able to do a single iteration over the eval data-block. Since the indices are sorted, we can always find the next element by iterating forwards. ## Updating the eval object With the update cache, the original object is no longer copied to replace the current eval object (copy-on-write). Instead, the eval object is updated, meaning that only parts will be copied over from the original (we call this **update-on-write**). The assumption here is that these parts were correctly tagged and nothing else changed. This then guarantees that the indices in our cache are the same on the eval object so we can use them to find the elements that need to be replaced. Updating then becomes almost trivial. We just iterate over the levels in the update cache tree, iterate over the children nodes, check if they need to be replaced and then do so. All the information needed to perform the replacement is stored in the node. ## Implementation TODO: link to patch

## What is the update cache? In short: The update cache stores what elements have changed since the last time the eval object was updated. Additionally, the update cache can now store multiple updates to the data and minimizes the number of elements that need to be copied. ## Motivation In our previous proposal (T93934) the elements that changed were tagged in the original data-block and had to be searched for when the update of the eval object took place. This means that in the worst case, the entire data-block had to be iterated through (into all the layers, into all frames and over all the strokes). Our profiling showed that close to 100% of the time was simply spent iterating over the linked-lists checking if something had been tagged. The update cache is our attempt at solving this problem. ## Tagging To make use of the update cache, we need to tag elements that need to be updated. This is done using dedicated BKE functions. **Full update tag (`BKE_gpencil_tag_full_update`)** The full update tag will update the element itself, but also all of its content. E.g. a full update tag on a layer will not only copy the layer, but also the entire frames and strokes in that layer. **Struct update tag (`BKE_gpencil_tag_struct_update`)** The struct update is a lighter type of update: it will only update the properties of an element, leaving its underlying content unchanged. E.g a struct copy can be used to indicate that a layer's name has been modified or that a keyframe selection status has changed. ## Explanation of the Update Cache Here is a diagram of what an update cache might look like after some operation on the grease pencil data happend: {F12839570, width=100%} As we can see, the cache resembles a tree. This is because the grease pencil data can be divided up into four distinct “levels”. The upper-most level is the whole data-block, then below are layers and then frames and finally strokes. Each one of those levels fully contains the others below, hence the tree structure. An update cache node is composed of 4 things: # The **index** of the cached element in the linked-list. E.g. when a node caches an update of a frame, the index is where that frame is in the linked-list of all the frames in its layer. In the diagram, this is the number inside the node. # A **flag** indicating the type of update: full, struct, or no update. # A **data pointer** to the element that is cached. The pointer might be null if the node does not cache an update for this element, but it will still store its index. These nodes are indicated using dashed lines in the diagram. Nodes that do have a valid data pointer are indicated with a bold circle for struct updates and a square for full updates. These are the nodes that were tagged for an update. # The **children** nodes. This is an ordered map with the key being the index and the value being an update cache node. This also means that an update cache node can have 0 or more children (except if it is on the lowest level, e.g. a stroke). To minimize the number of updates needed, the update cache does the following optimization: If a node in the update cache tree indicates a full update it mustn't have any children. This can be done, because the element that a node represents must contain all the data that is represented by the children nodes. So for example, during the `update_on_write`, if a layer was tagged and needs to be copied, all of the data contained in that layer will of course be copied as well. So there is no need to e.g. tag a frame in that layer, because it would be copied twice. So to summarize our update cache tree has these properties: - Nodes can have 0 or more children. - Only the leaf nodes cache elements that need a full update. - Any node may cache elements that require a struct update. We use an ordered map for the children of the nodes to be able to do a single iteration over the eval data-block. Since the indices are sorted, we can always find the next element by iterating forwards. ## Updating the eval object With the update cache, the original object is no longer copied to replace the current eval object (copy-on-write). Instead, the eval object is updated, meaning that only parts will be copied over from the original (we call this **update-on-write**). The assumption here is that these parts were correctly tagged and nothing else changed. This then guarantees that the indices in our cache are the same on the eval object so we can use them to find the elements that need to be replaced. Updating then becomes almost trivial. We just iterate over the levels in the update cache tree, iterate over the children nodes, check if they need to be replaced and then do so. All the information needed to perform the replacement is stored in the node. ## Implementation - TODO: link to patch