Skip to content

Speedup Computation for whether Aggregates containsProbe #4656

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.

Sign up for GitHub

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

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 5 commits into from
Feb 4, 2025
Merged

Speedup Computation for whether Aggregates containsProbe #4656

merged 5 commits into from
Feb 4, 2025

Conversation

mwachs5
Copy link
Contributor

@mwachs5 mwachs5 commented Feb 3, 2025 •
edited
Loading

Contributor Checklist

  • Did you add Scaladoc to every public function/method?
  • Did you add at least one test demonstrating the PR?
  • Did you delete any extraneous printlns/debugging code?
  • Did you specify the type of improvement?
  • [N/A] Did you add appropriate documentation in docs/src?
  • Did you request a desired merge strategy?
  • Did you add text to be included in the Release Notes for this change?

Type of Improvement

  • Performance improvement

Desired Merge Strategy

  • Squash: The PR will be squashed and merged (choose this if you have no preference).

Release Notes

Add a private containsProbe var to Aggregate and use it to speed up containsProbe checks.

Reviewer Checklist (only modified by reviewer)

  • Did you add the appropriate labels? (Select the most appropriate one based on the "Type of Improvement")
  • Did you mark the proper milestone (Bug fix: 3.6.x, 5.x, or 6.x depending on impact, API modification or big change: 7.0)?
  • Did you review?
  • Did you check whether all relevant Contributor checkboxes have been checked?
  • Did you do one of the following when ready to merge:
    • Squash: You/ the contributor Enable auto-merge (squash) and clean up the commit message.
    • Merge: Ensure that contributor has cleaned up their commit history, then merge with Create a merge commit.

@mwachs5 mwachs5 added this to the 3.6.x milestone Feb 3, 2025
@seldridge seldridge added the Performance Improves performance, will be included in release notes label Feb 3, 2025
seldridge
seldridge approved these changes Feb 3, 2025
View reviewed changes
Copy link
Member

@seldridge seldridge left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM

dtzSiFive
dtzSiFive approved these changes Feb 3, 2025
View reviewed changes
Copy link
Member

@dtzSiFive dtzSiFive left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM! Caching these recursive type properties is a good call, thanks!

Only doubt is if a Data is re-used or mutated to be probe-y, but not sure that's a thing?

jackkoenig
jackkoenig approved these changes Feb 3, 2025
View reviewed changes
Copy link
Contributor

@jackkoenig jackkoenig left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think this is reasonable as is but there are a couple of possible improvements:

  1. Specialize this on Vec to only check the sample element
  2. Consider doing it live with some normal traversal. This is tricky to figure out the right place so I'm not sure it's worth untangling at the moment, but e.g. we do that for if something contains a flipped [1]. That spot won't quite work because we do containsProbe on unbound types, but maybe we can figure out a similar approach.

@dtzSiFive
Copy link
Member

Only doubt is if a Data is re-used or mutated to be probe-y, but not sure that's a thing?

chisel/core/src/main/scala/chisel3/probe/ProbeBase.scala

Line 35 in 62ca9bd

val ret: T = if (!data.mustClone(prevId)) data else data.cloneType.asInstanceOf[T]

and uses of setProbeModifier (which seem today to clone)?

This will increase the object size of anything that's an Aggregate to accommodate the new field -- offhand I don't know the best recommendation but IIRC @jackkoenig went around with some tricks to reduce size needed for lazy vals in common objects? Or thereabouts?

@jackkoenig
Copy link
Contributor

This will increase the object size of anything that's an Aggregate to accommodate the new field -- offhand I don't know the best recommendation but IIRC @jackkoenig went around with some tricks to reduce size needed for lazy vals in common objects? Or thereabouts?

I'm not too worried about an extra Boolean (+ 1 bit in lazy val flags but there should be space there) in Aggregates. I'd care more if this were on all Data but it isn't so it's fine!

jackkoenig
jackkoenig requested changes Feb 3, 2025
View reviewed changes
Copy link
Contributor

@jackkoenig jackkoenig left a comment •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

val ret: T = if (!data.mustClone(prevId)) data else data.cloneType.asInstanceOf[T]

This is a problem though, good eye @dtzSiFive

@mwachs5 please add a test for this, I'm struggling to suggest the precise check but given an Aggregate that is taking advantage of the !mustClone, it will have its containsProbe memoized to false but then it will be mutated to itself be a Probe.

I think there are a couple of ways to fix this.

  1. Do the .containsProbe check after "maybe clone" part. But I don't think this is the best way because I think this mix of laziness and mutation could come up in a different place some day.
  2. Change the value we're memoizing to be "containsChildProbe" or something since that can never change--then the containsProbe check is "am I a probe OR do I containChildProbe".

@jackkoenig
Copy link
Contributor

jackkoenig commented Feb 3, 2025 •
edited
Loading

Change the value we're memoizing to be "containsChildProbe" or something since that can never change--then the containsProbe check is "am I a probe OR do I containChildProbe".

Actually it does seem like the intent of "containsProbe" is already asking about Aggregates containing children that are probes. But it's inconsistent, because "containsProbe" on a non-Aggregate does check if it locally is a Probe. In theory, an Element could never "contain" a probe.

containsProbe also appears to be trying to check "is or contains a probe" in MonoConnect:

chisel/core/src/main/scala/chisel3/internal/BiConnect.scala

Line 96 in 62ca9bd

case (left_e: Data, _) if containsProbe(left_e) =>

Same "is or contains a probe" use in ChiselEnum:

chisel/core/src/main/scala/chisel3/ChiselEnumImpl.scala

Line 151 in 62ca9bd

selfAnnotating && isSynthesizable && topBindingOpt.get.isInstanceOf[ConstrainedBinding] && !containsProbe(this)

@mwachs5
Copy link
Contributor Author

mwachs5 commented Feb 3, 2025

i like the "contains child probe" formulation, will do that. And will add some tests specifically for this

@mwachs5
Copy link
Contributor Author

mwachs5 commented Feb 4, 2025

I am going with containsProbe means "is or contains a probe". Added a bunch of tests for this. I renamed the aggregate variable to be elementsContainProbe and optimized it for Vecs.

mwachs5
mwachs5 commented Feb 4, 2025
View reviewed changes
@jackkoenig jackkoenig modified the milestones: 3.6.x, 6.x Feb 4, 2025
jackkoenig
jackkoenig approved these changes Feb 4, 2025
View reviewed changes
Copy link
Contributor

@jackkoenig jackkoenig left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks great, thanks!

Changed milestone to 6.x because probes didn't exist until then.

@mwachs5 mwachs5 merged commit c9cecfa into main Feb 4, 2025
15 checks passed
@mwachs5 mwachs5 deleted the speedup-probe-check branch February 4, 2025 17:06
@mergify mergify bot added the Backported This PR has been backported label Feb 4, 2025
chiselbot pushed a commit that referenced this pull request Feb 4, 2025
@mwachs5 @chiselbot
Speedup Computation for whether Aggregates containsProbe (#4656)
098025d 
* save the elementContainsProbes for an Aggregate to speed up various computations
* add unit tests for ContainsProbe

(cherry picked from commit c9cecfa)
@mergify Mergify
Copy link
Contributor

mergify bot commented Feb 4, 2025

backport

✅ Backports have been created

@chiselbot chiselbot mentioned this pull request Feb 4, 2025
Merged
13 tasks
chiselbot added a commit that referenced this pull request Feb 4, 2025
@chiselbot @mwachs5
Speedup Computation for whether Aggregates containsProbe (#4656) (#4664)
6b7429a 
* save the elementContainsProbes for an Aggregate to speed up various computations
* add unit tests for ContainsProbe

(cherry picked from commit c9cecfa)

Co-authored-by: Megan Wachs <megan@sifive.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@seldridge seldridge seldridge approved these changes

@jackkoenig jackkoenig jackkoenig approved these changes

@dtzSiFive dtzSiFive dtzSiFive approved these changes

Assignees
No one assigned
Labels
Backported This PR has been backported Performance Improves performance, will be included in release notes
Projects
None yet
Milestone
6.x
Development

Successfully merging this pull request may close these issues.
4 participants
@mwachs5 @dtzSiFive @jackkoenig @seldridge