Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

WIP BFS for Tagger#4987

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Draft
gzm0 wants to merge1 commit intoscala-js:main
base:main
Choose a base branch
Loading
fromgzm0:bfs
Draft

WIP BFS for Tagger#4987

gzm0 wants to merge1 commit intoscala-js:mainfromgzm0:bfs

Conversation

gzm0
Copy link
Contributor

No description provided.

@gzm0
Copy link
ContributorAuthor

Alternative to#4986.

TODO:

  • Validate this actually improves matters.
  • See if we can add unit tests.
  • Comment
  • See if we can reduce the overall number of traversals by propagating the entire previous path.

/cc@steinybot

@steinybot
Copy link

I tested this and it still OOMEs. BFS alone is not enough, once a path to a dependency has been found then no longer paths should be processed otherwise we get an explosion ofpathSteps. This is in contention with the excluded hop count which does have to traverse the longest paths. I think the only way is to calculate the excluded hop count separately.

@steinybot
Copy link

Ah correction it did eventually complete it just thrashed the GC for a few minutes. That's suprising. Maybe there was just enough memory.

@steinybot
Copy link

BFS alone is not enough, once a path to a dependency has been found then no longer paths should be processed otherwise we get an explosion of pathSteps.

Oh what am I on about... it does have the same updated check. Hmm so what is the difference 🤔

@steinybot
Copy link

A couple observations:

  • The statics should be traversed entirely before the dynamics. That ensures that we find the shortest paths first which can greatly reduce the combined lenghts of all the paths in memory. So the BFS needs to be in terms of thepathSteps not the dependencies. Since statics don't contribute to the path we have to traverse all of those before the dynamics.
  • The queue grows too big with duplicates.

@steinybot
Copy link

Some rough benchmarks with 6G of memory runningclient/clean;client/fullLinkJS with-Dsbt.task.timings=true:

bfs:

[info] Full optimizing /Users/jason/src/goodcover/core/client/target/scala-2.13/client-opt[warn] In the last 10 seconds, 5.207 (53.8%) were spent in GC. [Heap: 0.19GB free of 5.95GB, max 5.95GB] Consider increasing the JVM heap using `-Xmx` or try a different collector, e.g. `-XX:+UseG1GC`, for better performance.[warn] In the last 10 seconds, 8.379 (90.5%) were spent in GC. [Heap: 0.06GB free of 5.95GB, max 5.95GB] Consider increasing the JVM heap using `-Xmx` or try a different collector, e.g. `-XX:+UseG1GC`, for better performance.[warn] In the last 9 seconds, 8.776 (97.8%) were spent in GC. [Heap: 0.06GB free of 5.95GB, max 5.95GB] Consider increasing the JVM heap using `-Xmx` or try a different collector, e.g. `-XX:+UseG1GC`, for better performance.[warn] In the last 10 seconds, 9.002 (97.5%) were spent in GC. [Heap: 0.06GB free of 5.95GB, max 5.95GB] Consider increasing the JVM heap using `-Xmx` or try a different collector, e.g. `-XX:+UseG1GC`, for better performance.[warn] In the last 10 seconds, 9.022 (97.6%) were spent in GC. [Heap: 0.06GB free of 5.95GB, max 5.95GB] Consider increasing the JVM heap using `-Xmx` or try a different collector, e.g. `-XX:+UseG1GC`, for better performance.[warn] In the last 10 seconds, 8.859 (88.7%) were spent in GC. [Heap: 0.06GB free of 5.95GB, max 5.95GB] Consider increasing the JVM heap using `-Xmx` or try a different collector, e.g. `-XX:+UseG1GC`, for better performance.[warn] In the last 10 seconds, 9.243 (97.8%) were spent in GC. [Heap: 0.06GB free of 5.95GB, max 5.95GB] Consider increasing the JVM heap using `-Xmx` or try a different collector, e.g. `-XX:+UseG1GC`, for better performance.[warn] In the last 10 seconds, 8.979 (97.7%) were spent in GC. [Heap: 0.06GB free of 5.95GB, max 5.95GB] Consider increasing the JVM heap using `-Xmx` or try a different collector, e.g. `-XX:+UseG1GC`, for better performance.[warn] In the last 10 seconds, 9.294 (97.8%) were spent in GC. [Heap: 0.06GB free of 5.95GB, max 5.95GB] Consider increasing the JVM heap using `-Xmx` or try a different collector, e.g. `-XX:+UseG1GC`, for better performance.[warn] In the last 10 seconds, 8.967 (97.7%) were spent in GC. [Heap: 0.06GB free of 5.95GB, max 5.95GB] Consider increasing the JVM heap using `-Xmx` or try a different collector, e.g. `-XX:+UseG1GC`, for better performance.[warn] In the last 10 seconds, 9.491 (97.8%) were spent in GC. [Heap: 0.06GB free of 5.95GB, max 5.95GB] Consider increasing the JVM heap using `-Xmx` or try a different collector, e.g. `-XX:+UseG1GC`, for better performance.[info] Total time: 220455 ms[info]   client / Compile / fullLinkJS                                        : 173015 ms
  • It is hit and miss. Sometimes it OOMes sometimes not. It's hard to get it warmed up properly.

For comparison, my PR:

[info]   client / Compile / fullLinkJS                                        :  4625 ms
  • This is after 5 runs. It starts at ~13s and gets faster every run.

Sign up for freeto join this conversation on GitHub. Already have an account?Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

2 participants
@gzm0@steinybot
[8]ページ先頭
©2009-2025 Movatter.jp