Bug 239672 - gcov: Optimize list traverse by two passes
Summary: gcov: Optimize list traverse by two passes
Status: Closed Works As Intended
Alias: None
Product: Base System
Classification: Unclassified
Component: gnu (show other bugs)
Version: CURRENT
Hardware: Any Any
: --- Affects Some People
Assignee: freebsd-bugs mailing list
URL:
Keywords: needs-qa, performance
Depends on:
Blocks:
 
Reported: 2019-08-06 11:30 UTC by Chuhong Yuan
Modified: 2019-08-08 02:33 UTC (History)
2 users (show)

See Also:


Attachments
gcov_fs patch (535 bytes, patch)
2019-08-06 11:30 UTC, Chuhong Yuan
no flags Details | Diff
gcov_fs patch v2 (1.30 KB, patch)
2019-08-07 06:16 UTC, Chuhong Yuan
no flags Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Chuhong Yuan 2019-08-06 11:30:57 UTC
Created attachment 206304 [details]
gcov_fs patch

The original implementation of gcov_stats_reset() uses LIST_FOREACH to traverse the list.
However, because of the remove inside, it has to traverse from the beginning every time after removing node.
We can utilize LIST_FOREACH_SAFE to eliminate such redundant operations.
Comment 1 Conrad Meyer freebsd_committer 2019-08-07 01:59:52 UTC
This change is not correct.  Nodes are actually in a tree topology and remove_node() will release parent nodes as it goes, potentially invalidating the traverse (even with FOREACH_SAFE).

The code could be refactored to mark removed nodes as a first pass, and then remove them in a second pass (with plain TAILQ_FOREACH_SAFE).  This alternative would avoid wasted work for nodes that are never removed (which is probably the goal of the proposed change), but not break the algorithm.
Comment 2 Chuhong Yuan 2019-08-07 06:16:52 UTC
Created attachment 206319 [details]
gcov_fs patch v2

Use two passes to optimize the traverse.
In the first pass, add all nodes which need to be removed to a queue.
In the second pass, traverse the queue and remove the nodes.
Comment 3 Conrad Meyer freebsd_committer 2019-08-07 16:09:06 UTC
This change isn't quite right either.  The remove_node() traversal needs to happen on the first pass.  It can mark the nodes for removal during that pass, but cannot remove them from the "all_head" list (nor free them, of course).

The question that comes to mind is, why does this function's performance matter at all?  It can only be invoked manually from a sysctl.  Does it take material time?
Comment 4 Chuhong Yuan 2019-08-08 02:28:03 UTC
(In reply to Conrad Meyer from comment #3)
I just find this algorithm is a little strange and has redundant operations.

I am not very clear about how to revise it...
remove_node() will remove the node from "all_head" list and free the node, so how to call it in the first pass but just mark the nodes for removal and do not remove or free the nodes?
Comment 5 Conrad Meyer freebsd_committer 2019-08-08 02:33:38 UTC
(In reply to Chuhong Yuan from comment #4)
> (In reply to Conrad Meyer from comment #3)
> I am not very clear about how to revise it...
> remove_node() will remove the node from "all_head" list and free the node,
> so how to call it in the first pass but just mark the nodes for removal and
> do not remove or free the nodes?

You would modify remove_node().

However, if you don't have clear motivation to improve this algorithm (performance does not matter), don't have a good grasp of what the algorithm does, why are you trying to change it?