web-audio-api-rs icon indicating copy to clipboard operation
web-audio-api-rs copied to clipboard

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

Open orottier opened this issue 1 year ago • 2 comments

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 avatar Feb 27 '24 09:02 orottier

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.

orottier avatar Feb 27 '24 12:02 orottier

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

b-ma avatar Feb 27 '24 13:02 b-ma