From e727d6670479a0ed9dc746c96fdf0a97d36e090e Mon Sep 17 00:00:00 2001 From: Koni Marti Date: Wed, 2 Nov 2022 22:26:50 +0100 Subject: threadbuilder: better scaling for thread insertion Improve thread builder's performance scaling by inserting a new top-level thread at the beginning of the linked list which is an O(1) operation. The order of the top-level threads does not matter here since they will be sorted later anyways. Signed-off-by: Koni Marti Acked-by: Tim Culverhouse --- lib/threadbuilder.go | 14 ++++++++++---- 1 file changed, 10 insertions(+), 4 deletions(-) diff --git a/lib/threadbuilder.go b/lib/threadbuilder.go index 6a32dd29..600f6539 100644 --- a/lib/threadbuilder.go +++ b/lib/threadbuilder.go @@ -93,6 +93,7 @@ func (builder *ThreadBuilder) buildAercThreads(structure jwz.Threadable, uids []uint32, sort bool, ) []*types.Thread { threads := make([]*types.Thread, 0, len(builder.threadBlocks)) + if structure == nil { for _, uid := range uids { threads = append(threads, &types.Thread{Uid: uid}) @@ -130,7 +131,7 @@ func (builder *ThreadBuilder) buildAercThreads(structure jwz.Threadable, // build thread tree root := &types.Thread{Uid: 0} - builder.buildTree(structure, root, bigger) + builder.buildTree(structure, root, bigger, true) // copy top-level threads to thread slice for thread := root.FirstChild; thread != nil; thread = thread.NextSibling { @@ -144,7 +145,7 @@ func (builder *ThreadBuilder) buildAercThreads(structure jwz.Threadable, // buildTree recursively translates the jwz threads structure into aerc threads func (builder *ThreadBuilder) buildTree(c jwz.Threadable, parent *types.Thread, - bigger func(l, r *types.Thread) bool, + bigger func(l, r *types.Thread) bool, rootLevel bool, ) { if c == nil || parent == nil { return @@ -153,9 +154,14 @@ func (builder *ThreadBuilder) buildTree(c jwz.Threadable, parent *types.Thread, thread := parent if !node.IsDummy() { thread = builder.newThread(node, parent) - parent.InsertCmp(thread, bigger) + if rootLevel { + thread.NextSibling = parent.FirstChild + parent.FirstChild = thread + } else { + parent.InsertCmp(thread, bigger) + } } - builder.buildTree(node.GetChild(), thread, bigger) + builder.buildTree(node.GetChild(), thread, bigger, node.IsDummy()) } } -- cgit