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

Avoid O(n²) graph ordering when adding nodes 'organically' #467

Open
orottier opened this issue Feb 27, 2024 · 2 comments
Open

Avoid O(n²) graph ordering when adding nodes 'organically' #467

orottier opened this issue Feb 27, 2024 · 2 comments

Comments

@orottier
Copy link
Owner

orottier commented Feb 27, 2024

Given a sorted audio graph, the following typical operation should not trigger a full sort:

  • let src = create_oscillator/buffersource/constant (creates audioparams behind the scenes)
  • let gain = create_gain
  • src.connect(gain)
  • gain.connect(X) - X being the destination node or any other part of the graph

We should be able to prepend the sorted list without any further analysis in the following order

  1. the audioparams feeding into the source
  2. the source
  3. the gain

Currently, the full sort is triggered by self.ordered.clear(); in the Graph object when adding or removing edges.

Sidequest - do we even need to sort when edges are removed? Only if that edge was part of a cycle which after removal can be unmuted!

@orottier
Copy link
Owner Author

Hm, running the example/benchmarks.rs without any sorting at all, it does not seem to make any significant difference. Which indicates that the sorting algo is actually not a bottleneck at all, even in the granular synthesis case.

@b-ma
Copy link
Collaborator

b-ma commented Feb 27, 2024

Actually it make sens I think, because the graph is never changed in the benchmarks (as they use an OfflineAudioContext) so it is sorted only once

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants