Skip to content
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 our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Checkpoint faster bbox computation #259

Draft
wants to merge 1 commit into
base: main
Choose a base branch
from
Draft

Checkpoint faster bbox computation #259

wants to merge 1 commit into from

Conversation

raphlinus
Copy link
Contributor

This is a prototype of a faster approach to bounding box computation using monoids rather than atomics. The idea is sound but the current version of this PR has some flaws:

  • The fixup stage needs to gate on the partition actually containing a path end bit in the tags. It's not 100% obvious what's the best method for determining that. One appealing option is to look at the tag monoid for the next partition and see that the path count has increased, but that requires edge handling for the last partition.
  • There needs to be another reduction (and wiring into the scan) for the case where there are more than 64k path tags. This is similar to the logic for pathtag scan.
  • There will be merge conflicts with recent changes including labels on stages and buffers.
  • The type of the bbox should change from integer to float. The only reason integers were used was to support atomic operations.

I'm going to upload this in its current state because I'm not actively planning to land it right now. The idea is good and there is an impressive performance improvement. I'm also considering writing a blog post. I'll likely pick this up as part of the rectangle work, as that will benefit the bounding boxes having float type (to support antialiased rendering when the rectangle bounds aren't pixel-quantized).

This works but is currently limited to 64k path segments.
@raphlinus raphlinus mentioned this pull request Apr 6, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

1 participant