User Agent: Mozilla/5.0 (Windows NT 6.3; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/31.0.1650.34 Safari/537.36 Steps to reproduce: 1. Visit http://www.scirra.com/labs/audioeffects/ 2. Click 'Play SFX1', then SFX2, SFX3, SFX4 in turn. Then click 'Play music'. 3. When the music starts playing, click 'Add delay effect' Actual results: The audio plays back with lots of distortion (it sounds kind of fuzzy, like static playing over the top). Also, following these steps, after closing the browser I get a ghost Nightly.exe process which is not using CPU but needs to be ended from task manager before it lets you open a new instance of the browser. This is reproducible every time on my system. Expected results: The audio should not be distorted and the process should exit correctly after closing the browser. All effects should sound like they do in Chrome.

I would add in my opinion you were over-optimistic to ship this in release with Firefox 25. This bug report is using Firefox 28 Nightly; in Firefox 25, it's far more unstable. The ghost process issue is also reproducible there, and audio also completely cuts out following these steps, or (non-reproducibly) degrades in to stuttering distortion after playing with a few different effects. Additionally according to https://wiki.mozilla.org/WebAudio_API_Rollout_Status there is still no support for OscillatorNode (used to control the phaser and flanger effects, so they sound different in Firefox as they do to Chrome) or WaveTable (used for the distortion effect so it does not work in Firefox). Construct 2, a major HTML5 game engine, supports all these features in its audio engine. We were forwards-thinking enough to feature detect the unprefixed AudioContext and have kept up to date with API changes, but this in turn means all existing web content using our engine is affected by the above issues.

I think the problems stem from context.createMediaElementSource(). This is the only sensible way to play music with the Web Audio API, and all Construct 2-made games have been using it for a long time. However Firefox 25 seems unable to emit any audio at all for this type of node, or only brief clips which cut out or reduce to distortion. Real-world example: http://www.scirra.com/labs/sbwebapp2/ (the title screen music and in-game music are played with HTML5 audio going through createMediaElementSource()). The impact of this bug appears to be: Firefox can no longer play music in any game made using the Construct 2 engine. We feature-detect the presence of createMediaElementSource before using it. If it does not exist, we simply play HTML5 audio separately without connecting it in to the Web Audio API. A possible workaround would be to remove the createMediaElementSource function until it is working. I would favour a patch to the stable branch for this.

(In reply to ashley from comment #0) > Also, following these steps, after closing the browser I get a ghost > Nightly.exe process which is not using CPU but needs to be ended from task > manager before it lets you open a new instance of the browser. This is > reproducible every time on my system. This seems to be the same issue as bug 926522. The process can continue for up to a minute. I've verified that patches in that bug and its dependency fix this. We can use this bug to track fixing the delay distortion.

(In reply to ashley from comment #1) > Additionally according to > https://wiki.mozilla.org/WebAudio_API_Rollout_Status there is still no > support for OscillatorNode (used to control the phaser and flanger effects, > so they sound different in Firefox as they do to Chrome) or WaveTable (used > for the distortion effect so it does not work in Firefox). I've updated that page as OscillatorNode and PeriodicWave were implemented in Firefox 25. In Firefox 25 Beta 7, on Linux, the distortion, phaser, flanger effects sound similar to Chromium Version 30.0.1599.37. (In reply to ashley from comment #2) > I think the problems stem from context.createMediaElementSource(). This is > the only sensible way to play music with the Web Audio API, and all > Construct 2-made games have been using it for a long time. However Firefox > 25 seems unable to emit any audio at all for this type of node, or only > brief clips which cut out or reduce to distortion. Real-world example: > http://www.scirra.com/labs/sbwebapp2/ (the title screen music and in-game > music are played with HTML5 audio going through createMediaElementSource()). I'm not aware of differences in MediaElementAudioSourceNode between Nightly and Firefox 25, but on Win 7 I see these problems on http://www.scirra.com/labs/audioeffects/ even without adding effects. On Linux, I'm not really able to reproduce this issue. I'm hearing the music without problems on http://www.scirra.com/labs/sbwebapp2/ in Firefox 25 Beta 7. I can reproduce at least one situation on Linux where the effects are not good on Firefox 25 Beta 7 but OK on Nightly: 1. Visit http://www.scirra.com/labs/audioeffects/ 2. Click 'Add distortion effect' twice 3. Click 'Play music' and then 'SFX4' immediately after. I can also reproduce the delay effect problem even on Win 7 and Linux Nightly with: 1. Visit http://www.scirra.com/labs/audioeffects/ 2. Click 'Add delay effect' once. 3. Click 'Play music'. Changing OS to all, at least for the delay effect issue reported in comment 0, though perhaps there may be something specific to MediaElementAudioSourceNode (?decoders) on WINNT. A testcase in human-readable javascript may be necessary for diagnosis.

(In reply to Karl Tomlinson (:karlt) from comment #4) > I can reproduce at least one situation on Linux where the effects are not > good on Firefox 25 Beta 7 but OK on Nightly: > > 1. Visit http://www.scirra.com/labs/audioeffects/ > 2. Click 'Add distortion effect' twice > 3. Click 'Play music' and then 'SFX4' immediately after. In fact, step 2 is not necessary. This is best reproduced soon after page load. This changed from an awful buzz to something believable on Nightly in this range. http://hg.mozilla.org/mozilla-central/pushloghtml?fromchange=ab5f29823236&tochange=3697f962bb7b Even on a recent Nightly, however, with no effects applied, the music gets louder and more distorted each time "Play music" is clicked: 1. Visit http://www.scirra.com/labs/audioeffects/ 2. Click 'Play music' repeatedly.

(In reply to Karl Tomlinson (:karlt) from comment #5) > > 1. Visit http://www.scirra.com/labs/audioeffects/ > > 3. Click 'Play music' and then 'SFX4' immediately after. > This changed from an awful buzz to something believable on Nightly in this > range. > http://hg.mozilla.org/mozilla-central/ > pushloghtml?fromchange=ab5f29823236&tochange=3697f962bb7b The changeset that fixed that is http://hg.mozilla.org/mozilla-central/rev/b0f89cf3ede6, a follow-up in bug 752796, which is now in Firefox 26 beta. https://hg.mozilla.org/releases/mozilla-beta/rev/b0f89cf3ede6

Filed bug 937962 on the distortion with createMediaElementSource, because that is still happening.

Someone gave me a nicer test case on twitter, attached here for posterity. The problem seem to be about feedback loops: source.connect(delay); delay.delatTime.value = 0.5; delay.connect(gain); gain.gain.value = 0.4; delay.connect(context.destination); gain.connect(delay);

Here is a tentative diagnostic patch. Running the test case, we can see that the stream ordering is not the same each time: > Cycle detected, starting at 0x7f41826e0280 > -- 0x7f41826e00c0 > Cycle end > Stream ordering: > -- DelayNodeEngine > -- GainNodeEngine > -- DestinationNodeEngine > -- ScriptProcessorNodeEngine > -- OscillatorNodeEngine > End. > Cycle detected, starting at 0x7f41826e00c0 > -- 0x7f41826e0280 > Cycle end > Stream ordering: > -- GainNodeEngine > -- DelayNodeEngine > -- DestinationNodeEngine > -- ScriptProcessorNodeEngine > -- OscillatorNodeEngine > End. > Cycle detected, starting at 0x7f41826e0280 > -- 0x7f41826e00c0 > Cycle end > Stream ordering: > -- DelayNodeEngine > -- GainNodeEngine > -- DestinationNodeEngine > -- ScriptProcessorNodeEngine > -- OscillatorNodeEngine > End. This could be an issue, I guess.

So, I applied ehsan's patch from bug 883010 (the one that could not be checked in because of failures), that makes us cache the stream order (so it's not recomputed every time, with the order change weirness), to quickly check my theory, and the distortion goes away.

(In reply to comment #10) > So, I applied ehsan's patch from bug 883010 (the one that could not be checked > in because of failures), that makes us cache the stream order (so it's not > recomputed every time, with the order change weirness), to quickly check my > theory, and the distortion goes away. Perhaps that also explains the test failures?

(In reply to :Ehsan Akhgari (needinfo? me!) from comment #11) > (In reply to comment #10) > > So, I applied ehsan's patch from bug 883010 (the one that could not be checked > > in because of failures), that makes us cache the stream order (so it's not > > recomputed every time, with the order change weirness), to quickly check my > > theory, and the distortion goes away. > > Perhaps that also explains the test failures? Maybe. I've picked up your patch again and I'm trying to make it green, but I hit a jit crash so it slowed me down a bit. It seems promising, although the real fix for this bug would be to make the ordering of the stream the same regardless of the order in which they are before ordering.

The stream order should be cached where possible, but that is not the solution to this bug. (Consider for example, the cycle / feedback loop running while changes are made elsewhere in the graph. Those changes will disable the caching, but should not affect the output of the cycle.) Each stream order satisfying the requirements in the calculation should produce the same output. If different stream orders are producing different output then there is a problem with our model or the requirements. To make cycles work correctly we need a means to get output from the delay node before input (for this block in time) is provided.

(In reply to Karl Tomlinson (back Jan 28 :karlt) from comment #13) > The stream order should be cached where possible, but that is not the > solution to this bug. (Consider for example, the cycle / feedback loop > running while changes are made elsewhere in the graph. Those changes will > disable the caching, but should not affect the output of the cycle.) Agreed, I picked up the patch again to check my theory, and seeing it was close to being landable, I fixed a couple things. > Each stream order satisfying the requirements in the calculation should > produce the same output. If different stream orders are producing different > output then there is a problem with our model or the requirements. I think we have some weirdness in the algorithm, that makes it dependent on the input order. > To make cycles work correctly we need a means to get output from the delay > node before input (for this block in time) is provided. Yes, I think that's taken care of already [1]. http://dxr.mozilla.org/mozilla-central/source/content/media/AudioNodeStream.cpp?from=audionodestream#285

This works, but feels hacky. Basically, it justs puts the "sinks" (MediaStreamDestinationNode, AudioDestinationNode, etc.) at beginning of the array, so that the recursive ordering algorithm works in "pull" mode, and the ordering is the same each time. But this is just a sketch I think.

(In reply to Paul Adenot (:padenot) from comment #14) > > To make cycles work correctly we need a means to get output from the delay > > node before input (for this block in time) is provided. > > Yes, I think that's taken care of already [1]. > > http://dxr.mozilla.org/mozilla-central/source/content/media/AudioNodeStream. > cpp?from=audionodestream#285 That's not quite what I meant. Consider processing for block n at time t with a cycle with a DelayNode: Attempt 1: Process the DelayNode *before* other nodes in the cycle: * The output from the DelayNode is now available to all nodes connected to its output, including those in the cycle. * DelayNode input from nodes outside the cycle will already be available. * However, DelayNode input from nodes within the cycle will be from nodes that have not yet processed block n. Input from those nodes will be for block n-1. Attempt 2: Process the DelayNode *after* other nodes in the cycles: * The input to the DelayNode is now available from all nodes connected to its input, including those in the cycle. * DelayNode output will be available to downstream nodes outside the cycle. * However, DelayNode output for block n was not available for nodes in the cycle. Those nodes received data from block n-1 instead of block n. I think we need to set mLastChunks for the DelayNode *before* processing for other nodes in the cycle (or provide a different means of getting the output). We then need to feed input into the delay node *after* processing for the other nodes in the cycle.

There is actually two issues in this bug: - The topological sort we use to decide in which order we should process the streams should find a better ordering, independant on input order. Simply starting the algorithms from the sinks fixes that. - We should then make sure the nodes get the right block. Attached is a stand alone web page that can help us do that (just change the content of the "dirac" function). It seems kind of okay, from my testing (with the patch applied), but I haven't thought about it enough.

(In reply to Paul Adenot (:padenot) from comment #17) > There is actually two issues in this bug: > - The topological sort we use to decide in which order we should process the > streams should find a better ordering, independant on input order. Simply > starting the algorithms from the sinks fixes that. If the nodes receive and send the correct blocks, then is there a problem with the ordering? Ordering is observable through ScriptProcessorNode, AnalyserNode, and other nodes that send events, but ordering is not specified.

(In reply to Karl Tomlinson (back Jan 28 :karlt) from comment #19) > (In reply to Paul Adenot (:padenot) from comment #17) > > There is actually two issues in this bug: > > - The topological sort we use to decide in which order we should process the > > streams should find a better ordering, independant on input order. Simply > > starting the algorithms from the sinks fixes that. > > If the nodes receive and send the correct blocks, then is there a problem > with the ordering? > > Ordering is observable through ScriptProcessorNode, AnalyserNode, and other > nodes that send events, but ordering is not specified. Well, that's the whole problem: the stream order, currently, depends on the stream order for the previous MSG run, (comment 9). This is a bug: the nodes _don't_ receive and send the correct blocks.

I've written a test case for the Web Audio mochitest suite to test for distortion in feedback loops -- this bug seems to occur even when gain/delay are 0, so a feedback loop is set up with a gain and delay of 0 and the output is checked against a pure sine wave.

This allow the MSG to order the stream in a true "pull" fashion, as needed for proper rendering of cycles. The distortion goes away, with this.

This is similar to attachment 8366761 [details] but swaps the delay and gain nodes. The black line is the actual output while the red line is expected - actual. The patch of attachment 8379793 [details] [diff] [review] makes the loop delay consistent, but now always one block too long. I have some WIP patches to separate delay buffer write and read so that read can happen before write (when delay > 1 block), if you are happy for me to take over.

(In reply to Paul Adenot (:padenot) from comment #22) > This allow the MSG to order the stream in a true "pull" fashion, as needed > for proper rendering of cycles. The distortion goes away, with this. I don't understand the problem. UpdateStreamOrder should already ensure that a stream with no outputs is ordered after all of its input streams. Why is that not enough?

(In reply to Karl Tomlinson (:karlt) from comment #16) > I think we need to set mLastChunks for the DelayNode *before* processing for > other nodes in the cycle (or provide a different means of getting the > output). We then need to feed input into the delay node *after* processing > for the other nodes in the cycle. I agree with this.

(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #24) > (In reply to Paul Adenot (:padenot) from comment #22) > > This allow the MSG to order the stream in a true "pull" fashion, as needed > > for proper rendering of cycles. The distortion goes away, with this. > > I don't understand the problem. UpdateStreamOrder should already ensure that > a stream with no outputs is ordered after all of its input streams. Why is > that not enough? Because when you have a loop, nodes part of the loop are swapped (in the final ordering) when running the algorithm twice in a row. Since we (used to) reorder the streams each iteration, we would grab the wrong input chunk, and this provoked the distortion. We don't do that anymore, but the problem can still be triggered (if authors change the graph topology often enough to trigger enough reordering). Karl, I'm happy for you to take over this. I'd rather have a fixed ordering that does not glitch for now, and then write a proper solution (or maybe your WIP in progress patches can make it soon?). I fully agree that comment 16 is the proper way to fix this. I'm just concerned by the fact that this problem is being reported to me over and over.

I have something working at https://tbpl.mozilla.org/?tree=Try&rev=1316a1837bac https://tbpl.mozilla.org/?tree=Try&rev=76b70b699a7d but properly determining the number of output channels before knowing the number of input channels is really bug 857610. I'll have a solution for that soon.

Thank you, roc, for the suggestion to use two passes. Perhaps it might be possible to do two different analyses during one traversal, but this is simpler. If two cycles share a common path, they will now *both* be treated as cycles, either by muting or by enforcing minimum delay. Previously, marking one cycle mHasBeenOrdered first could prevent detection of other cycles.

Now that ProduceOutput doesn't necessarily produce output, ProcessInput might be a better name.

Similarly for the AudioNodeEngine methods.

Comment on attachment 8382713 [details] [diff] [review] change stream ordering to get DelayNode echo output before supplying input Review of attachment 8382713 [details] [diff] [review]: ----------------------------------------------------------------- Basically, it's difficult to tell how this works, so some more precise documentation is needed. ::: content/media/MediaStreamGraph.cpp @@ +531,5 @@ > + OrderingState(int aFirstOrderingIndex) : > + stackPosition(UINT_MAX), orderingIndex(aFirstOrderingIndex) {}; > + // Descending counter used to determine which streams on the stack are > + // included in cycles. > + unsigned stackPosition; uint32_t @@ +533,5 @@ > + // Descending counter used to determine which streams on the stack are > + // included in cycles. > + unsigned stackPosition; > + // Ascending counter used to mark the order of streams. > + int orderingIndex; int32_t. Also, use "m" prefix. Also, please give a precise description of the invariants here. @@ +537,5 @@ > + int orderingIndex; > +}; > + > +// Search depth-first upstream, marking the stream order for dependencies and > +// this stream. This comment is hard to understand. Please specify exactly what this does, I think that will really help make this code understandable. @@ +677,5 @@ > + > + // Reference count changes on streams are atomic operations, so avoid > + // unnecessary changes. > + for (uint32_t i = sourceStreamCount; i < mFirstCycleBreaker; ++i) { > + while (1) { while (true) ::: content/media/MediaStreamGraph.h @@ +992,5 @@ > > // The list of all inputs that are currently enabled or waiting to be enabled. > nsTArray<MediaInputPort*> mInputs; > bool mAutofinish; > + unsigned mCycleMarker; uint32_t

Comment on attachment 8382712 [details] [diff] [review] part 1: allow DelayNodeEngine to produce output before input Review of attachment 8382712 [details] [diff] [review]: ----------------------------------------------------------------- ::: content/media/AudioNodeEngine.h @@ +265,5 @@ > } > + /** > + * Produce the next block of audio samples, before input is provided. > + * ProduceAudioBlock() will be called later, and it then should not change > + * aOutput. This is used only for DelayNodeEngine in an echo loop. s/echo/feedback/ to be more generic.

(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #32) > Comment on attachment 8382713 [details] [diff] [review] > Basically, it's difficult to tell how this works, so some more precise > documentation is needed. Fair enough. This was helpful in ironing out a bug with intersecting cycles. It should make more sense now. > ::: content/media/MediaStreamGraph.cpp > @@ +531,5 @@ > > + OrderingState(int aFirstOrderingIndex) : > > + stackPosition(UINT_MAX), orderingIndex(aFirstOrderingIndex) {}; > > + // Descending counter used to determine which streams on the stack are > > + // included in cycles. > > + unsigned stackPosition; > > uint32_t > > + // Ascending counter used to mark the order of streams. > > + int orderingIndex; > > int32_t. Also, use "m" prefix. Also, please give a precise description of > the invariants here. I've added documentation to these members, particularly the former as there are not many invariants directly involving the ordering index. I've also changed the names a little to highlight differences from the corresponding processed stream variables. The 'm' prefix is useful in classes with methods, so as to distinguish from local (automatic) variables. If there are no methods in the class, then all uses of the members involve pointer-to-member operators and so the members never look like locals. https://groups.google.com/forum/#!searchin/mozilla.dev.platform/style$20pod$20m/mozilla.dev.platform/EYCylYteP-I/whbDMW72TC8J almost said something similar, and I don't remember any disagreement about this point. However, 'm' does at least make it clear that these are not class static variables. > ::: content/media/MediaStreamGraph.h > > + unsigned mCycleMarker; > > uint32_t You've requested some changes to integer types, but I don't know why. orderingIndex is used with nsTArray<>::index_type, so I've changed it and ProcessedMediaStream::mOrderingIndex to uint32_t to match that. stackPosition and mCycleMarker, however, are not used as nsTArray indices, and so are free from the quirks of nsTArray. I assume you are not requesting the special-length type because you are concerned about future memory usage or packing of member variables in ProcessedMediaStream. Usually I prefer the regular unsigned int for unsigned variables when nothing larger is required because then we know that integral promotion won't convert it to a signed type, possibly leading to unexpected results (cf. bug 651309). However, that shouldn't be a problem here, so I don't think there is much harm in using uint32_t.

(In reply to Karl Tomlinson (:karlt) from comment #34) > The 'm' prefix is useful in classes with methods, so as to distinguish from > local (automatic) variables. If there are no methods in the class, then all > uses of the members involve pointer-to-member operators and so the members > never look like locals. I don't think this distinction is worth making. It means that as soon as you add a single member function to the class you should rename all the members, which would be a real pain, so it just seems like trouble. > > ::: content/media/MediaStreamGraph.h > > > > + unsigned mCycleMarker; > > > > uint32_t > > You've requested some changes to integer types, but I don't know why. > > orderingIndex is used with nsTArray<>::index_type, so I've changed it and > ProcessedMediaStream::mOrderingIndex to uint32_t to match that. > > stackPosition and mCycleMarker, however, are not used as nsTArray indices, > and > so are free from the quirks of nsTArray. I assume you are not requesting the > special-length type because you are concerned about future memory usage or > packing of member variables in ProcessedMediaStream. > > Usually I prefer the regular unsigned int for unsigned variables when nothing > larger is required because then we know that integral promotion won't convert > it to a signed type, possibly leading to unexpected results (cf. bug 651309). > However, that shouldn't be a problem here, so I don't think there is much > harm > in using uint32_t. I prefer to use fixed-length types in most situations since it ensures overflow will happen under the same conditions for 32bit and 64bit platforms.

Comment on attachment 8384317 [details] [diff] [review] part 2 v2: change stream ordering to get DelayNode echo output before supplying input Review of attachment 8384317 [details] [diff] [review]: ----------------------------------------------------------------- ::: content/media/MediaStreamGraph.cpp @@ +682,5 @@ > + // not in cycles, and there may be more than one DelayNode in a cycle, so we > + // must detect all DelayNodes in cycles before breaking the cycles. We > + // don't want to analyse every cycle to see whether it contains a delay > + // node, so first find delay nodes in cycles, then break at DelayNodes, and > + // reorder again. Your comments are good, but the code is still more complex than I was hoping for. How about we implement this by explicitly using Tarjan's algorithm? http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm A node is in a cycle iff it is in a strongly-connected component of size > 1. Tarjan's algorithm topologically orders the SCCs for us so in the absence of cycles it computes a valid order. When we identify an SCC of size > 1, we can check it for DelayNodes and make them cycle-breakers. Then, we can do a DFS within the SCC to see if we've broken all cycles, giving the correct order for those nodes if we have. It's still going to be a bit complicated but I think being explicit about the algorithms we're using will make this more maintainable. ::: content/media/MediaStreamGraph.h @@ +988,5 @@ > + struct OrderingState; > + uint32_t SetOrderUpstream(OrderingState *orderingState); > + bool HasBeenOrdered() { return mOrderingIndex != uint32_t(-1); } > + // Returns true if this stream receives input, directly or indirectly, from > + // any streams on the stack. Add "See MediaStreamGraphImpl::UpdateStreamOrder".

Landed the method renames and DelayNodeEngine refactoring to minimize conflicts with other developments while investigating roc's proposal. https://hg.mozilla.org/integration/mozilla-inbound/rev/5678323e54ad https://hg.mozilla.org/integration/mozilla-inbound/rev/597c9e0f6c7e https://hg.mozilla.org/integration/mozilla-inbound/rev/aa3c47aed9e9

https://hg.mozilla.org/mozilla-central/rev/5678323e54ad https://hg.mozilla.org/mozilla-central/rev/597c9e0f6c7e https://hg.mozilla.org/mozilla-central/rev/aa3c47aed9e9

Original report still reproduces in Firefox 32.0a1 nightly. Is this still being worked on? It's holding back enabling createMediaElementSource() in Firefox in Construct 2, a major HTML5 game engine.

The issue being addressed here is the distortion from a feedback loop. That is unrelated to createMediaElementSource(). I filed bug 937962 on an issue related to createMediaElementSource(), but the main issue in the testcase there has been addressed. If there is still distortion from createMediaElementSource(), then would you be able to file a new bug with steps to reproduce, please?

Any news on this? Delay node still causes distortion.

The current ordering algorithm sometimes adds and removes thread-safe references unnecessarily. We could jump through hoops to swap array elements or use forget() and alreadyAddRefed() in order to avoid refcount manipulation, but this is more complicated than the benefits from provided by the RAII class. The RAII is already complicated by the fact that I happens after and on a different thread to RA. Eventually we should probably replace mStreams with a linked list to reduce the cost of destroying the graph from n^2 to n, so this is a step in that direction.

See http://www.timl.id.au/?p=327 for a nice description of how this cycle detection algorithm works. (In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #36) > Comment on attachment 8384317 [details] [diff] [review] > How about we implement this by explicitly using Tarjan's algorithm? > http://en.wikipedia.org/wiki/ > Tarjan%27s_strongly_connected_components_algorithm Thanks for the link. I didn't know this was called Tarjan's algorithm. The previous patch differed from Tarjan's algorithm in that it used a sub-tree DFS search to find the SCC when its root was popped from the DFS stack. This version tracks these in an explicit stack, as in Pearce's algorithm, which removes some of the complexity. The previous version followed the recursive nature of Tarjan's algorithm but an iterative implementation is better for potentially large graphs on child threads. Using linked lists makes the input iteration for iterative DFS simple, and will be useful for addressing n^2 destruction. > A node is in a cycle iff it is in a strongly-connected component of size > > 1. A node in an SCC of size 1 may either be in a cycle or not, and so Tarjan's algorithm doesn't distinguish. Both are SCCs of size 1, but a small variation, retained from the previous patch, handles that case. > When we identify an SCC of size > 1, we can check it for DelayNodes and make > them cycle-breakers. Then, we can do a DFS within the SCC to see if we've > broken all cycles, giving the correct order for those nodes if we have. This was a nice improvement, thanks.

Comment on attachment 8452108 [details] [diff] [review] part 6 (part 2 v3): change stream ordering to get DelayNode echo output before supplying input Review of attachment 8452108 [details] [diff] [review]: ----------------------------------------------------------------- Gnarly! ::: content/media/AudioNodeStream.cpp @@ +490,5 @@ > +{ > + MOZ_ASSERT(mEngine->OutputCount() == 1, > + "DelayNodeEngine output count should be 1"); > + MOZ_ASSERT(!InMutedCycle(), "DelayNodes should break cycles"); > + mLastChunks.SetLength(1); We should assert around here that this is actually for a DelayNode. ::: content/media/MediaStreamGraph.cpp @@ +577,5 @@ > + // whether streams in SCCs of size 1 are in a cycle and (b) to re-run the > + // algorithm over SCCs with breaks at DelayNodes. > + // > + // [1] https://github.com/scipy/scipy/blob/e2c502fca/scipy/sparse/csgraph/_traversal.pyx#L582 > + // [2] http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.1707 Might want to link to the blog here too. @@ +713,5 @@ > + mStreams[mFirstCycleBreaker] = ns; > + } > + } > + auto after_scc = next; > + while((next = static_cast<ProcessedMediaStream*>(sccStack.popFirst())) space after 'while'

Without this, UpdateOutputBlock() would be called from ProcessBlock(), giving the wrong minimum delay.

https://hg.mozilla.org/integration/mozilla-inbound/rev/04019eb4d1b5 https://hg.mozilla.org/integration/mozilla-inbound/rev/013907ce316a

https://hg.mozilla.org/mozilla-central/rev/04019eb4d1b5 https://hg.mozilla.org/mozilla-central/rev/013907ce316a

Verified fixed in nightly 34. Thanks for the good work.