[gtk/wip/alexl/broadway7: 76/87] broadway: Reintroduce smarter diffing
- From: Alexander Larsson <alexl src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gtk/wip/alexl/broadway7: 76/87] broadway: Reintroduce smarter diffing
- Date: Fri, 29 Mar 2019 13:32:16 +0000 (UTC)
commit f30ba5632380326f0178d0602522f471492fb9e9
Author: Alexander Larsson <alexl redhat com>
Date: Thu Mar 28 19:17:01 2019 +0100
broadway: Reintroduce smarter diffing
We now send very minimal diff operations.
gdk/broadway/broadway-output.c | 158 +++++++++++++++++++++++++++++++--------
gdk/broadway/broadway-protocol.h | 3 +-
gdk/broadway/broadway-server.c | 26 ++++---
gdk/broadway/broadway-server.h | 10 ++-
gdk/broadway/broadway.js | 109 +++++++++++++++++----------
5 files changed, 219 insertions(+), 87 deletions(-)
---
diff --git a/gdk/broadway/broadway-output.c b/gdk/broadway/broadway-output.c
index 479a7a48da..853a66eb85 100644
--- a/gdk/broadway/broadway-output.c
+++ b/gdk/broadway/broadway-output.c
@@ -8,6 +8,7 @@
#include "broadway-output.h"
//#define DEBUG_NODE_SENDING
+//#define DEBUG_NODE_SENDING_REMOVE
/************************************************************************
* Basic I/O primitives *
@@ -317,9 +318,9 @@ static void
append_type (BroadwayOutput *output, guint32 type, BroadwayNode *node)
{
#ifdef DEBUG_NODE_SENDING
- g_print ("%*s%s", append_node_depth*2, "", broadway_node_type_names[type]);
+ g_print ("%*s%s(%d/%d)", append_node_depth*2, "", broadway_node_type_names[type], node->id,
node->output_id);
if (type == BROADWAY_NODE_TEXTURE)
- g_print (" %u", node->data[4]);
+ g_print (" tx=%u", node->data[4]);
g_print ("\n");
#endif
@@ -367,13 +368,14 @@ append_node (BroadwayOutput *output,
reused_node = lookup_old_node (old_node_lookup, node->id);
if (reused_node)
{
+ broadway_node_mark_deep_consumed (reused_node, TRUE);
append_type (output, BROADWAY_NODE_REUSE, node);
- append_uint32 (output, node->id);
+ append_uint32 (output, node->output_id);
}
else
{
append_type (output, node->type, node);
- append_uint32 (output, node->id);
+ append_uint32 (output, node->output_id);
for (i = 0; i < node->n_data; i++)
append_uint32 (output, node->data[i]);
for (i = 0; i < node->n_children; i++)
@@ -386,37 +388,131 @@ append_node (BroadwayOutput *output,
}
-static void
+static BroadwayNode *
append_node_ops (BroadwayOutput *output,
BroadwayNode *node,
+ BroadwayNode *parent,
+ BroadwayNode *previous_sibling,
BroadwayNode *old_node,
GHashTable *old_node_lookup)
{
- GPtrArray *to_remove = g_ptr_array_new ();
+ BroadwayNode *reused_node;
guint32 i;
- if (old_node != NULL)
- g_ptr_array_add (to_remove, old_node);
+ /* Maybe can be reused from the last tree. */
+ reused_node = lookup_old_node (old_node_lookup, node->id);
+ if (reused_node)
+ {
+ g_assert (node == reused_node);
+ g_assert (reused_node->reused);
+ g_assert (!reused_node->consumed); /* Should only be once in the tree, and not consumed otherwise */
+
+ broadway_node_mark_deep_consumed (reused_node, TRUE);
+
+ if (node == old_node)
+ {
+ /* The node in the old tree at the current position is the same, so
+ we need to do nothing, just don't delete it (which we won't since
+ its marked used) */
+ }
+ else
+ {
+ /* We can reuse it, bu it comes from a different place or
+ order, if so we need to move it in place */
+#ifdef DEBUG_NODE_SENDING
+ g_print ("Move old node %d/%d to parent %d/%d after %d/%d\n",
+ reused_node->id, reused_node->output_id,
+ parent ? parent->id : 0,
+ parent ? parent->output_id : 0,
+ previous_sibling ? previous_sibling->id : 0,
+ previous_sibling ? previous_sibling->output_id : 0);
+#endif
+ append_uint32 (output, BROADWAY_NODE_OP_MOVE_AFTER_CHILD);
+ append_uint32 (output, parent ? parent->output_id : 0);
+ append_uint32 (output, previous_sibling ? previous_sibling->output_id : 0);
+ append_uint32 (output, reused_node->output_id);
+ }
- append_uint32 (output, BROADWAY_NODE_OP_APPEND_NODE);
- append_uint32 (output, 0); /* Parent */
+ return reused_node;
+ }
+
+ /* If the next node in place is shallowly equal (but not necessarily
+ * deep equal) we reuse it and tweak its children as needed.
+ * Except we avoid this for reused node as those make more sense to reuse deeply.
+ */
+
+ if (old_node && broadway_node_equal (node, old_node) && !old_node->reused)
+ {
+ int old_i = 0;
+ BroadwayNode *last_child = NULL;
+
+ old_node->consumed = TRUE; // Don't reuse again
+
+ // We rewrite this new node as it now represents the old node in the browser
+ node->output_id = old_node->output_id;
+
+ /* However, we might need to rewrite then children of old_node */
+ for (i = 0; i < node->n_children; i++)
+ {
+ BroadwayNode *child = node->children[i];
+
+ /* Find the next (or first) non-consumed old child, if any */
+ while (old_i < old_node->n_children &&
+ old_node->children[old_i]->consumed)
+ old_i++;
+
+ last_child =
+ append_node_ops (output,
+ child,
+ node, /* parent */
+ last_child,
+ (old_i < old_node->n_children) ? old_node->children[old_i] : NULL,
+ old_node_lookup);
+ }
+
+ /* Remaining old nodes are either reused elsewhere, or end up marked not consumed so are deleted at
the end */
+ return old_node;
+ }
+
+ /* Fallback to create a new tree */
+#ifdef DEBUG_NODE_SENDING
+ g_print ("Insert nodes in parent %d/%d, after sibling %d/%d\n",
+ parent ? parent->id : 0,
+ parent ? parent->output_id : 0,
+ previous_sibling ? previous_sibling->id : 0,
+ previous_sibling ? previous_sibling->output_id : 0);
+#endif
+ append_uint32 (output, BROADWAY_NODE_OP_INSERT_NODE);
+ append_uint32 (output, parent ? parent->output_id : 0);
+ append_uint32 (output, previous_sibling ? previous_sibling->output_id : 0);
append_node(output, node, old_node_lookup);
- for (i = 0; i < to_remove->len; i++)
- {
- BroadwayNode *removed_node = g_ptr_array_index (to_remove, i);
- if (!removed_node->used)
- {
- // TODO: Use an array of nodes instead
- append_uint32 (output, BROADWAY_NODE_OP_REMOVE_NODE);
- append_uint32 (output, old_node->id);
- }
- }
- g_ptr_array_unref (to_remove);
+ return node;
+}
+
+/* Remove non-consumed nodes */
+static void
+append_node_removes (BroadwayOutput *output,
+ BroadwayNode *node)
+{
+ // TODO: Use an array of nodes instead
+ if (!node->consumed)
+ {
+#ifdef DEBUG_NODE_SENDING_REMOVE
+ g_print ("Remove old node non-consumed node %d/%d\n",
+ node->id, node->output_id);
+#endif
+ append_uint32 (output, BROADWAY_NODE_OP_REMOVE_NODE);
+ append_uint32 (output, node->output_id);
+ }
+
+ for (int i = 0; i < node->n_children; i++)
+ append_node_removes (output, node->children[i]);
}
+
void
broadway_output_surface_set_nodes (BroadwayOutput *output,
int id,
@@ -426,14 +522,14 @@ broadway_output_surface_set_nodes (BroadwayOutput *output,
{
gsize size_pos, start, end;
- /* Mark old nodes as unused, so we can use them once */
+
if (old_root)
- broadway_node_mark_deep_used (old_root, FALSE);
- /* Mark new nodes as used, causing any shared nodes to be marked as
- unused. This way we won't accidentally reuse them for something
- else. However, this means that is safe to reuse nodes marked as
- used for the specific case of where the id matches. */
- broadway_node_mark_deep_used (root, TRUE);
+ {
+ broadway_node_mark_deep_consumed (old_root, FALSE);
+ broadway_node_mark_deep_reused (old_root, FALSE);
+ /* This will modify children of old_root if any are shared */
+ broadway_node_mark_deep_reused (root, TRUE);
+ }
write_header (output, BROADWAY_OP_SET_NODES);
@@ -444,9 +540,11 @@ broadway_output_surface_set_nodes (BroadwayOutput *output,
start = output->buf->len;
#ifdef DEBUG_NODE_SENDING
- g_print ("====== node tree for %d =======\n", id);
+ g_print ("====== node ops for surface %d =======\n", id);
#endif
- append_node_ops (output, root, old_root, old_node_lookup);
+ append_node_ops (output, root, NULL, NULL, old_root, old_node_lookup);
+ if (old_root)
+ append_node_removes (output, old_root);
end = output->buf->len;
patch_uint32 (output, (end - start) / 4, size_pos);
}
diff --git a/gdk/broadway/broadway-protocol.h b/gdk/broadway/broadway-protocol.h
index 1ea5ff9766..b642e342bc 100644
--- a/gdk/broadway/broadway-protocol.h
+++ b/gdk/broadway/broadway-protocol.h
@@ -26,8 +26,9 @@ typedef enum { /* Sync changes with broadway.js */
} BroadwayNodeType;
typedef enum { /* Sync changes with broadway.js */
- BROADWAY_NODE_OP_APPEND_NODE = 0,
+ BROADWAY_NODE_OP_INSERT_NODE = 0,
BROADWAY_NODE_OP_REMOVE_NODE = 1,
+ BROADWAY_NODE_OP_MOVE_AFTER_CHILD = 2,
} BroadwayNodeOpType;
static const char *broadway_node_type_names[] G_GNUC_UNUSED = {
diff --git a/gdk/broadway/broadway-server.c b/gdk/broadway/broadway-server.c
index 0d789a660d..b8bfe8b1d0 100644
--- a/gdk/broadway/broadway-server.c
+++ b/gdk/broadway/broadway-server.c
@@ -183,10 +183,6 @@ broadway_node_equal (BroadwayNode *a,
{
int i;
- // Early fast return for reused nodes
- if (a == b)
- return TRUE;
-
if (a->type != b->type)
return FALSE;
@@ -211,10 +207,6 @@ broadway_node_deep_equal (BroadwayNode *a,
{
int i;
- // Early fast return for reused nodes
- if (a == b)
- return TRUE;
-
if (a->hash != b->hash)
return FALSE;
@@ -233,12 +225,21 @@ broadway_node_deep_equal (BroadwayNode *a,
void
-broadway_node_mark_deep_used (BroadwayNode *node,
- gboolean used)
+broadway_node_mark_deep_reused (BroadwayNode *node,
+ gboolean reused)
+{
+ node->reused = reused;
+ for (int i = 0; i < node->n_children; i++)
+ broadway_node_mark_deep_reused (node->children[i], reused);
+}
+
+void
+broadway_node_mark_deep_consumed (BroadwayNode *node,
+ gboolean consumed)
{
- node->used = used;
+ node->consumed = consumed;
for (int i = 0; i < node->n_children; i++)
- broadway_node_mark_deep_used (node->children[i], used);
+ broadway_node_mark_deep_consumed (node->children[i], consumed);
}
void
@@ -1779,6 +1780,7 @@ decode_nodes (BroadwayServer *server,
g_ref_count_init (&node->refcount);
node->type = type;
node->id = id;
+ node->output_id = id;
node->texture_id = 0;
node->n_children = n_children;
node->children = (BroadwayNode **)((char *)node + sizeof(BroadwayNode) + (size - 1) * sizeof(guint32));
diff --git a/gdk/broadway/broadway-server.h b/gdk/broadway/broadway-server.h
index a5624ff6fa..859464aa45 100644
--- a/gdk/broadway/broadway-server.h
+++ b/gdk/broadway/broadway-server.h
@@ -25,13 +25,15 @@ struct _BroadwayNode {
grefcount refcount;
guint32 type;
guint32 id;
+ guint32 output_id;
guint32 hash; /* deep hash */
guint32 n_children;
BroadwayNode **children;
guint32 texture_id;
/* Scratch stuff used during diff */
- gboolean used;
+ gboolean reused;
+ gboolean consumed;
guint32 n_data;
guint32 data[1];
@@ -41,8 +43,10 @@ gboolean broadway_node_equal (BroadwayNode *
BroadwayNode *b);
gboolean broadway_node_deep_equal (BroadwayNode *a,
BroadwayNode *b);
-void broadway_node_mark_deep_used (BroadwayNode *node,
- gboolean used);
+void broadway_node_mark_deep_reused (BroadwayNode *node,
+ gboolean reused);
+void broadway_node_mark_deep_consumed (BroadwayNode *node,
+ gboolean consumed);
void broadway_node_add_to_lookup (BroadwayNode *node,
GHashTable *node_lookup);
BroadwayServer *broadway_server_new (char *address,
diff --git a/gdk/broadway/broadway.js b/gdk/broadway/broadway.js
index f5ccd78740..2cef2c1e7d 100644
--- a/gdk/broadway/broadway.js
+++ b/gdk/broadway/broadway.js
@@ -15,8 +15,9 @@ const BROADWAY_NODE_TRANSFORM = 11;
const BROADWAY_NODE_DEBUG = 12;
const BROADWAY_NODE_REUSE = 13;
-const BROADWAY_NODE_OP_APPEND_NODE = 0;
+const BROADWAY_NODE_OP_INSERT_NODE = 0;
const BROADWAY_NODE_OP_REMOVE_NODE = 1;
+const BROADWAY_NODE_OP_MOVE_AFTER_CHILD = 2;
const BROADWAY_OP_GRAB_POINTER = 'g';
const BROADWAY_OP_UNGRAB_POINTER = 'u';
@@ -236,7 +237,7 @@ function cmdCreateSurface(id, x, y, width, height, isTemp)
surface.transientParent = 0;
surface.visible = false;
surface.imageData = null;
- surface.old_nodes = {};
+ surface.nodes = {};
var div = document.createElement('div');
div.surface = surface;
@@ -299,14 +300,13 @@ function cmdLowerSurface(id)
moveToHelper(surface, 0);
}
-function TransformNodes(node_data, div, old_nodes, display_commands) {
+function TransformNodes(node_data, div, nodes, display_commands) {
this.node_data = node_data;
this.display_commands = display_commands;
this.data_pos = 0;
this.div = div;
this.outstanding = 1;
- this.old_nodes = old_nodes;
- this.new_nodes = {};
+ this.nodes = nodes;
}
TransformNodes.prototype.decode_uint32 = function() {
@@ -479,16 +479,21 @@ function set_rrect_style (div, rrect) {
div.style["border-bottom-left-radius"] = args(px(rrect.sizes[3].width), px(rrect.sizes[3].height));
}
-function addOldIds(node, node_map) {
- node_map[node.node_id] = node;
-
- var child = node.firstChild;
- while (child) {
- addOldIds(child, node_map);
- child = child.nextSibling;
- }
+TransformNodes.prototype.createDiv = function(id)
+{
+ var div = document.createElement('div');
+ div.node_id = id;
+ this.nodes[id] = div;
+ return div;
}
+TransformNodes.prototype.createImage = function(id)
+{
+ var image = new Image();
+ image.node_id = id;
+ this.nodes[id] = image;
+ return image;
+}
TransformNodes.prototype.insertNode = function(parent, previousSibling, is_toplevel)
{
@@ -502,7 +507,7 @@ TransformNodes.prototype.insertNode = function(parent, previousSibling, is_tople
/* Reuse divs from last frame */
case BROADWAY_NODE_REUSE:
{
- oldNode = this.old_nodes[id];
+ oldNode = this.nodes[id];
}
break;
/* Leaf nodes */
@@ -511,7 +516,7 @@ TransformNodes.prototype.insertNode = function(parent, previousSibling, is_tople
{
var rect = this.decode_rect();
var texture_id = this.decode_uint32();
- var image = new Image();
+ var image = this.createImage(id);
image.width = rect.width;
image.height = rect.height;
image.style["position"] = "absolute";
@@ -528,7 +533,7 @@ TransformNodes.prototype.insertNode = function(parent, previousSibling, is_tople
{
var rect = this.decode_rect();
var c = this.decode_color ();
- var div = document.createElement('div');
+ var div = this.createDiv(id);
div.style["position"] = "absolute";
set_rect_style(div, rect);
div.style["background-color"] = c;
@@ -546,7 +551,7 @@ TransformNodes.prototype.insertNode = function(parent, previousSibling, is_tople
for (var i = 0; i < 4; i++)
border_colors[i] = this.decode_color();
- var div = document.createElement('div');
+ var div = this.createDiv(id);
div.style["position"] = "absolute";
rrect.bounds.width -= border_widths[1] + border_widths[3];
rrect.bounds.height -= border_widths[0] + border_widths[2];
@@ -573,7 +578,7 @@ TransformNodes.prototype.insertNode = function(parent, previousSibling, is_tople
var spread = this.decode_float();
var blur = this.decode_float();
- var div = document.createElement('div');
+ var div = this.createDiv(id);
div.style["position"] = "absolute";
set_rrect_style(div, rrect);
div.style["box-shadow"] = args(px(dx), px(dy), px(blur), px(spread), color);
@@ -590,7 +595,7 @@ TransformNodes.prototype.insertNode = function(parent, previousSibling, is_tople
var spread = this.decode_float();
var blur = this.decode_float();
- var div = document.createElement('div');
+ var div = this.createDiv(id);
div.style["position"] = "absolute";
set_rrect_style(div, rrect);
div.style["box-shadow"] = args("inset", px(dx), px(dy), px(blur), px(spread), color);
@@ -605,7 +610,7 @@ TransformNodes.prototype.insertNode = function(parent, previousSibling, is_tople
var start = this.decode_point ();
var end = this.decode_point ();
var stops = this.decode_color_stops ();
- var div = document.createElement('div');
+ var div = this.createDiv(id);
div.style["position"] = "absolute";
set_rect_style(div, rect);
@@ -669,7 +674,7 @@ TransformNodes.prototype.insertNode = function(parent, previousSibling, is_tople
m[12] + "," + m[13] + "," + m[14] + "," + m[15] + ")";
}
- var div = document.createElement('div');
+ var div = this.createDiv(id);
div.style["transform"] = transform_string;
div.style["transform-origin"] = "0px 0px";
@@ -681,7 +686,7 @@ TransformNodes.prototype.insertNode = function(parent, previousSibling, is_tople
case BROADWAY_NODE_CLIP:
{
var rect = this.decode_rect();
- var div = document.createElement('div');
+ var div = this.createDiv(id);
div.style["position"] = "absolute";
set_rect_style(div, rect);
div.style["overflow"] = "hidden";
@@ -693,7 +698,7 @@ TransformNodes.prototype.insertNode = function(parent, previousSibling, is_tople
case BROADWAY_NODE_ROUNDED_CLIP:
{
var rrect = this.decode_rounded_rect();
- var div = document.createElement('div');
+ var div = this.createDiv(id);
div.style["position"] = "absolute";
set_rrect_style(div, rrect);
div.style["overflow"] = "hidden";
@@ -705,7 +710,7 @@ TransformNodes.prototype.insertNode = function(parent, previousSibling, is_tople
case BROADWAY_NODE_OPACITY:
{
var opacity = this.decode_float();
- var div = document.createElement('div');
+ var div = this.createDiv(id);
div.style["position"] = "absolute";
div.style["left"] = px(0);
div.style["top"] = px(0);
@@ -727,7 +732,7 @@ TransformNodes.prototype.insertNode = function(parent, previousSibling, is_tople
var blur = this.decode_float();
filters = filters + "drop-shadow(" + args (px(dx), px(dy), px(blur), color) + ")";
}
- var div = document.createElement('div');
+ var div = this.createDiv(id);
div.style["position"] = "absolute";
div.style["left"] = px(0);
div.style["top"] = px(0);
@@ -741,7 +746,7 @@ TransformNodes.prototype.insertNode = function(parent, previousSibling, is_tople
case 14: // DEBUG
{
var str = this.decode_string();
- var div = document.createElement('div');
+ var div = this.createDiv(id);
div.setAttribute('debug', str);
this.insertNode(div, null, false);
newNode = div;
@@ -752,7 +757,7 @@ TransformNodes.prototype.insertNode = function(parent, previousSibling, is_tople
case BROADWAY_NODE_CONTAINER:
{
- var div = document.createElement('div');
+ var div = this.createDiv(id);
var len = this.decode_uint32();
var lastChild = null;
for (var i = 0; i < len; i++) {
@@ -767,15 +772,12 @@ TransformNodes.prototype.insertNode = function(parent, previousSibling, is_tople
}
if (newNode) {
- newNode.node_id = id;
- this.new_nodes[id] = newNode;
if (is_toplevel)
- this.display_commands.push([DISPLAY_OP_APPEND_CHILD, parent, newNode]);
- else // Here it is safe to display directly because we have not added the toplevel to the document
yet
+ this.display_commands.push([DISPLAY_OP_INSERT_AFTER_CHILD, parent, previousSibling, newNode]);
+ else // It is safe to display directly because we have not added the toplevel to the document yet
parent.appendChild(newNode);
return newNode;
} else if (oldNode) {
- addOldIds(oldNode, this.new_nodes);
// This must be delayed until display ops, because it will remove from the old parent
this.display_commands.push([DISPLAY_OP_INSERT_AFTER_CHILD, parent, previousSibling, oldNode]);
return oldNode;
@@ -788,22 +790,48 @@ TransformNodes.prototype.execute = function(display_commands)
while (this.data_pos < this.node_data.byteLength) {
var op = this.decode_uint32();
+ var parentId, parent;
switch (op) {
- case BROADWAY_NODE_OP_APPEND_NODE:
- var parentId = this.decode_uint32();
- var parent;
+ case BROADWAY_NODE_OP_INSERT_NODE:
+ parentId = this.decode_uint32();
if (parentId == 0)
parent = root;
- else
- parent = this.old_nodes[parentId];
- this.insertNode(parent, null, true);
+ else {
+ parent = this.nodes[parentId];
+ if (parent == null)
+ console.log("Wanted to insert into parent " + parentId + " but it is unknown");
+ }
+
+ var previousChildId = this.decode_uint32();
+ var previousChild = null;
+ if (previousChildId != 0)
+ previousChild = this.nodes[previousChildId];
+ this.insertNode(parent, previousChild, true);
break;
case BROADWAY_NODE_OP_REMOVE_NODE:
var removeId = this.decode_uint32();
- var remove = this.old_nodes[removeId];
+ var remove = this.nodes[removeId];
+ delete this.nodes[removeId];
+ if (remove == null)
+ console.log("Wanted to delete node " + removeId + " but it is unknown");
+
this.display_commands.push([DISPLAY_OP_DELETE_NODE, remove]);
break;
+ case BROADWAY_NODE_OP_MOVE_AFTER_CHILD:
+ parentId = this.decode_uint32();
+ if (parentId == 0)
+ parent = root;
+ else
+ parent = this.nodes[parentId];
+ var previousChildId = this.decode_uint32();
+ var previousChild = null;
+ if (previousChildId != 0)
+ previousChild = this.nodes[previousChildId];
+ var toMoveId = this.decode_uint32();
+ var toMove = this.nodes[toMoveId];
+ this.display_commands.push([DISPLAY_OP_INSERT_AFTER_CHILD, parent, previousChild, toMove]);
+ break;
}
}
}
@@ -1028,9 +1056,8 @@ function handleCommands(cmd, display_commands, new_textures, modified_trees)
var node_data = cmd.get_nodes ();
surface = surfaces[id];
- var transform_nodes = new TransformNodes (node_data, surface.div, surface.old_nodes,
display_commands);
+ var transform_nodes = new TransformNodes (node_data, surface.div, surface.nodes,
display_commands);
transform_nodes.execute();
- surface.old_nodes = transform_nodes.new_nodes;
}
break;
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
