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 /perf | |
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.
Diffstat (limited to 'perf')
-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; } |