diff options
author | Michael Drake <michael.drake@codethink.co.uk> | 2021-05-15 16:15:41 +0100 |
---|---|---|
committer | Michael Drake <michael.drake@codethink.co.uk> | 2021-05-15 19:59:24 +0100 |
commit | 6c69e82879901a3a8f5eb19914e7ffc4224d0eca (patch) | |
tree | 96f15fe2e9a47fdf378ead352e770fca4e25552e | |
parent | 26a7ff24df8cb52c08bab23cff7a8f5ceb3c4465 (diff) | |
download | libhubbub-6c69e82879901a3a8f5eb19914e7ffc4224d0eca.tar.gz libhubbub-6c69e82879901a3a8f5eb19914e7ffc4224d0eca.tar.bz2 |
Perf tester: Optimise tree node data structure with last child pointer.
For loading the html5 single page spec:
* This reduces append_child callback self time from 21% to 0.6% of
total runtime.
* Total instruction fetch cost is reduced from 7,085,287,214 to
5,652,755,136.
This makes it more useful for observing where hubbub itself is slow,
rather than the tester's simple treebuilder implementation.
-rw-r--r-- | perf/hubbub.c | 86 |
1 files changed, 49 insertions, 37 deletions
diff --git a/perf/hubbub.c b/perf/hubbub.c index c945fe6..53d17c7 100644 --- a/perf/hubbub.c +++ b/perf/hubbub.c @@ -50,7 +50,8 @@ struct node_t { node_t *next; node_t *prev; - node_t *child; + node_t *child_first; + node_t *child_last; node_t *parent; }; @@ -276,26 +277,25 @@ hubbub_error append_child(void *ctx, void *parent, void *child, void **result) tchild->next = tchild->prev = NULL; *result = child; - if (parent == (void *)1) { if (Document) { insert = Document; + while (insert->next != NULL) { + insert = insert->next; + } } else { Document = tchild; } } else { - if (tparent->child == NULL) { - tparent->child = tchild; + if (tparent->child_first == NULL) { + tparent->child_first = tchild; + tparent->child_last = tchild; } else { - insert = tparent->child; + insert = tparent->child_last; } } if (insert) { - while (insert->next != NULL) { - insert = insert->next; - } - if (tchild->type == CHARACTER && insert->type == CHARACTER) { insert->data.content = realloc(insert->data.content, strlen(insert->data.content) + @@ -305,6 +305,10 @@ hubbub_error append_child(void *ctx, void *parent, void *child, void **result) } else { insert->next = tchild; tchild->prev = insert; + if (insert->parent != NULL && + insert->parent != (void *)1) { + insert->parent->child_last = insert; + } } } @@ -341,7 +345,7 @@ hubbub_error insert_before(void *ctx, void *parent, void *child, void *ref_child if (tchild->prev) tchild->prev->next = tchild; else - tparent->child = tchild; + tparent->child_first = tchild; *result = child; } @@ -356,11 +360,16 @@ hubbub_error remove_child(void *ctx, void *parent, void *child, void **result) UNUSED(ctx); - assert(tparent->child); + assert(tparent->child_last); + assert(tparent->child_first); assert(tchild->parent == tparent); - if (tchild->parent->child == tchild) { - tchild->parent->child = tchild->next; + if (tchild->parent->child_first == tchild) { + tchild->parent->child_first = tchild->next; + } + + if (tchild->parent->child_last == tchild) { + tchild->parent->child_last = tchild->prev; } if (tchild->prev) @@ -387,10 +396,6 @@ hubbub_error clone_node(void *ctx, void *node, bool deep, void **result) *new_node = *old_node; *result = new_node; - new_node->child = new_node->parent = - new_node->next = new_node->prev = - NULL; - if (deep == false) return HUBBUB_OK; @@ -401,15 +406,22 @@ hubbub_error clone_node(void *ctx, void *node, bool deep, void **result) new_node->next = n; new_node->next->prev = new_node; + + new_node->parent = old_node->parent; + if (new_node->parent != NULL && new_node->parent != (void *)1) { + new_node->parent->child_last = new_node; + } } - if (old_node->child) { + if (old_node->child_first) { void *n; - clone_node(ctx, old_node->child, true, &n); + clone_node(ctx, old_node->child_first, true, &n); - new_node->child = n; - new_node->child->parent = new_node; + if (new_node) + new_node->child_last = n; + new_node->child_first = n; + new_node->child_first->parent = new_node; } return HUBBUB_OK; @@ -422,30 +434,30 @@ hubbub_error reparent_children(void *ctx, void *node, void *new_parent) node_t *old_parent = node; node_t *insert; - node_t *kids; + node_t *kids_first; + node_t *kids_last; UNUSED(ctx); - kids = old_parent->child; - if (!kids) return HUBBUB_OK; + kids_first = old_parent->child_first; + kids_last = old_parent->child_last; + if (!kids_first) return HUBBUB_OK; - old_parent->child = NULL; + old_parent->child_first = NULL; + old_parent->child_last = NULL; - insert = parent->child; + insert = parent->child_last; if (!insert) { - parent->child = kids; + parent->child_first = kids_first; } else { - while (insert->next != NULL) { - insert = insert->next; - } - - insert->next = kids; - kids->prev = insert; + insert->next = kids_first; + kids_first->prev = insert; } + parent->child_last = kids_last; - while (kids) { - kids->parent = parent; - kids = kids->next; + while (kids_first) { + kids_first->parent = parent; + kids_first = kids_first->next; } return HUBBUB_OK; @@ -465,7 +477,7 @@ hubbub_error has_children(void *ctx, void *node, bool *result) { UNUSED(ctx); - *result = ((node_t *)node)->child ? true : false; + *result = ((node_t *)node)->child_first ? true : false; return HUBBUB_OK; } |