Faust C compiler generates O(n^2) additions for a simple O(n) implementation of prefix sums

[eleses]

import("stdfaust.lib");

ker = _,_ <: _,!, +;
presum(N) = seq(i, N - 1, si.bus(i), ker, si.bus(N - i - 2));

// test:
M = 4;
durs = par(i, M, hslider("Dur%2i", M - i, 0, M, .001));
plot = hgroup("[1]Times ", 
    par(i, M, vbargraph("Time%2i[style:numerical]", 0.0, M*M)) :> _);

hmm = durs : presum(M);

process = _ <: attach(_, hmm : plot);

Relevant graph has just 3 additions:

But the generated C code has many more...

	float fSlow0 = (float)(dsp->fHslider0);
	float fSlow1 = (float)(dsp->fHslider2);
	float fSlow2 = (float)(dsp->fHslider3);
	dsp->fVbargraph0 = (FAUSTFLOAT)(fSlow2 + fSlow1 + (float)(dsp->fHslider1) + fSlow0);
	dsp->fVbargraph1 = (FAUSTFLOAT)(fSlow2 + fSlow0 + fSlow1);
	dsp->fVbargraph2 = (FAUSTFLOAT)(fSlow1 + fSlow2);
	dsp->fVbargraph3 = (FAUSTFLOAT)(fSlow2);
	float fSlow3 = dsp->fVbargraph3 + dsp->fVbargraph2 + dsp->fVbargraph1 + dsp->fVbargraph0;

Interestingly, if I replace the ker with the one for a single pass of bubble sort (out its N), i.e. ker = _,_ <: min, max; it doesn't do this bad: just 3 fmin and 3 fmax as one may hope. So, it looks like there's something about additions that really triggers this odd behavior. But that's not the whole story, because merely replacing addition with multiplication i.e. ker = _,_ <: _,!, *; also does O(n^2) operations in the C code. However, it's not merely the asymmetric nature of that ker that triggers it. Because this (not very useful) ker = _,_ <: _,!, min; only calls three fmins in the C code. And it's not merely that the operation is non-commutative, because ker = _,_ <: _,!, -; does something pretty weird too:

	float fSlow0 = (float)(dsp->fHslider0);
	float fSlow1 = (float)(dsp->fHslider2);
	float fSlow2 = (float)(dsp->fHslider3);
	dsp->fVbargraph0 = (FAUSTFLOAT)(fSlow2 - (fSlow1 + (float)(dsp->fHslider1) + fSlow0));
	dsp->fVbargraph1 = (FAUSTFLOAT)(fSlow2 - (fSlow0 + fSlow1));
	dsp->fVbargraph2 = (FAUSTFLOAT)(fSlow2);
	dsp->fVbargraph3 = (FAUSTFLOAT)(fSlow2 - fSlow1);

So I'm guessing it's trying to propagate arithmetic expressions (but not others like fmin) back to the beginning of the graph, even when this isn't particularly useful, like in systolic arrangements such as this.

[sletz]

Most surely missing Common Subexpression Elimination (CSE) pass.

[sletz]

This code:

import("stdfaust.lib");

ker = _,_ <: _,!, +;
presum(N) = seq(i, N - 1, si.bus(i), ker, si.bus(N - i - 2));

// test:
M = 4;
durs = par(i, M, hslider("Dur%2i", M - i, 0, M, .001));
plot = hgroup("[1]Times ", 
    par(i, M, vbargraph("Time%2i[style:numerical]", 0.0, M*M)) :> _);

hmm = durs : presum(M);
process = hmm;

Generates this code which is correct:

virtual void compute(int count, FAUSTFLOAT** RESTRICT inputs, FAUSTFLOAT** RESTRICT outputs) {
		FAUSTFLOAT* output0 = outputs[0];
		FAUSTFLOAT* output1 = outputs[1];
		FAUSTFLOAT* output2 = outputs[2];
		FAUSTFLOAT* output3 = outputs[3];
		float fSlow0 = float(fHslider0);
		float fSlow1 = fSlow0 + float(fHslider1);
		float fSlow2 = float(fHslider2) + fSlow1;
		float fSlow3 = float(fHslider3) + fSlow2;
		for (int i0 = 0; i0 < count; i0 = i0 + 1) {
			output0[i0] = FAUSTFLOAT(fSlow0);
			output1[i0] = FAUSTFLOAT(fSlow1);
			output2[i0] = FAUSTFLOAT(fSlow2);
			output3[i0] = FAUSTFLOAT(fSlow3);
		}
	}

So can you paste again the exact failing code ?

[eleses]

@sletz : that seems to be using the C++ backend/architecture? I used the C one with the on-line IDE compiler (platform "source", architecture "C") for my initial report. I guess the C++ backend is more maintained. But I'm not able to get the code you mentioned using "cplusplus" instead of C as target using the on-line compiler. Instead I get this:

	virtual void compute(int count, FAUSTFLOAT** RESTRICT inputs, FAUSTFLOAT** RESTRICT outputs) {
		FAUSTFLOAT* input0 = inputs[0];
		FAUSTFLOAT* output0 = outputs[0];
		float fSlow0 = float(fHslider0);
		float fSlow1 = float(fHslider2);
		float fSlow2 = float(fHslider3);
		fVbargraph0 = FAUSTFLOAT(fSlow2 + fSlow1 + float(fHslider1) + fSlow0);
		fVbargraph1 = FAUSTFLOAT(fSlow2 + fSlow0 + fSlow1);
		fVbargraph2 = FAUSTFLOAT(fSlow1 + fSlow2);
		fVbargraph3 = FAUSTFLOAT(fSlow2);
		float fSlow3 = fVbargraph3 + fVbargraph2 + fVbargraph1 + fVbargraph0;
		for (int i0 = 0; i0 < count; i0 = i0 + 1) {
			output0[i0] = FAUSTFLOAT(float(input0[i0]));
		}
	}

I'll try the offline compiler in a sec.

With the default options in 2.81.2 I get the same result.

        virtual void compute(int count, FAUSTFLOAT** RESTRICT inputs, FAUSTFLOAT** RESTRICT outputs) {
                FAUSTFLOAT* input0 = inputs[0];
                FAUSTFLOAT* output0 = outputs[0];
                float fSlow0 = float(fHslider0);
                float fSlow1 = float(fHslider2);
                float fSlow2 = float(fHslider3);
                fVbargraph0 = FAUSTFLOAT(fSlow2 + fSlow1 + float(fHslider1) + fSlow0);
                fVbargraph1 = FAUSTFLOAT(fSlow2 + fSlow0 + fSlow1);
                fVbargraph2 = FAUSTFLOAT(fSlow1 + fSlow2);
                fVbargraph3 = FAUSTFLOAT(fSlow2);
                float fSlow3 = fVbargraph3 + fVbargraph2 + fVbargraph1 + fVbargraph0;
                for (int i0 = 0; i0 < count; i0 = i0 + 1) {
                        output0[i0] = FAUSTFLOAT(float(input0[i0]));
                }
        }

Code generated with Faust 2.81.2 (https://faust.grame.fr)
Compilation options: -lang cpp -ct 1 -es 1 -mcd 16 -mdd 1024 -mdy 33 -single -ftz 0

So I think a difference is that the code you posted doesn't attach the result to the vbargraphs like my initial report, but sends them directly on the outputs.

process = _ <: attach(_, hmm : plot); // in mine

vs

process = hmm; // yours

But even with the latter change, I dont' get your output with default compile options in the offline compiler. Instead I get

        virtual void compute(int count, FAUSTFLOAT** RESTRICT inputs, FAUSTFLOAT** RESTRICT outputs) {
                FAUSTFLOAT* output0 = outputs[0];
                FAUSTFLOAT* output1 = outputs[1];
                FAUSTFLOAT* output2 = outputs[2];
                FAUSTFLOAT* output3 = outputs[3];
                float fSlow0 = float(fHslider0);
                float fSlow1 = float(fHslider1);
                float fSlow2 = fSlow1 + fSlow0;
                float fSlow3 = float(fHslider2);
                float fSlow4 = fSlow0 + fSlow3 + fSlow1;
                float fSlow5 = fSlow0 + fSlow1 + float(fHslider3) + fSlow3;
                for (int i0 = 0; i0 < count; i0 = i0 + 1) {
                        output0[i0] = FAUSTFLOAT(fSlow0);
                        output1[i0] = FAUSTFLOAT(fSlow2);
                        output2[i0] = FAUSTFLOAT(fSlow4);
                        output3[i0] = FAUSTFLOAT(fSlow5);
                }
        }

which is still adding them multiple times. I don't see any other changes that you've made.

So, what compiler version did you use, and with what options to get that nice result?

[sletz]

This is indeed very strange !

• first this is not related to C versus C++ backend, both use the same internal machinery
• I'm not using any special option and 2.81.2 here on macOS generates the correct code
• I moved back on 2.80.4 (the online version number) and still have the correct code on macOS
• and yes the online compiler 2.80.4 generates the wrong code (so compiled and running on Linux..)
• so I guess you are compiling on Linux ? What compiler are you using to compile Faust ?

[sletz]

(we indeed have a kind of CSE pass, I was wrong this morning...)

[sletz]

I activated traces on CI on Linux, see https://github.com/grame-cncm/faust/actions/runs/16230355819/job/45831728967 and there is indeed a problem. We don't have the same behaviour on Linux compared to macOS, already at box then signal stages, where we can generate intermediate textual traces and compare to a set of reference files.

Can you possibly compile Faust with clang on Linux and check if this change something ?

[sletz]

Tested successfully with gcc14 here: intermediate textual traces are correct and the generated C++ code is also correct. So waiting for some feedback on your side : gcc version, architecture (ARM, Intel) ..etc...

[sletz]

Tested with success on a Linux VM running on a macOS ARM64, Ubuntu 22.04 and gcc 11.4.0.