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

Compaction could be faster #4509

Closed
jimblandy opened this issue Oct 6, 2023 · 0 comments · Fixed by #4662
Closed

Compaction could be faster #4509

jimblandy opened this issue Oct 6, 2023 · 0 comments · Fixed by #4662
Labels
naga Shader Translator

Comments

@jimblandy
Copy link
Member

Caution: I don't actually have any benchmarks here. So this would need to be undertaken along with adding a compaction benchmark to our criterion benchmark suite.

If compaction took advantage of the fact that expressions, constants, and types only refer to elements earlier in the arena than they are, it could trace these by making a single pass from end to start, marking (say) an expression's operands as used only if the expression itself is marked used.

To trace a function, you'd first trace the statement tree, but for each expression the statement tree refers to, you'd simply mark it used - you would not call trace_expression.

Then, after the statement tree has been traced, you'd make a single pass over the expression arena from back to front, marking an expression's operands as used only if the expression itself had been marked as used previously. This would require no work list manipulation.

A similar approach could be extended to the constants, constant expressions, and types.

Unlike the current algorithm, this would require traversing both live and dead arena elements. However, that traversal would be guided by the contents of the HandleSets, so that we wouldn't ever actually touch the elements we didn't intend to traverse.

@cwfitzgerald cwfitzgerald transferred this issue from gfx-rs/naga Oct 25, 2023
@cwfitzgerald cwfitzgerald added the naga Shader Translator label Oct 25, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
naga Shader Translator
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants