Wie programmiere ich performant? Literaturtipps?

[DSP-freak]

hustbaer schrieb:

Einen FIR Filter kann man z.B. stur mit Kreuzkorrelation berechnen, oder mit Hilfe einer FFT/IFFT, was viel schneller geht.

normalerweise wird, aus geschwindigkeitsgründen, bei FIR filtern mit konstanten gearbeitet, so dass man zur laufzeit keine aufwendigen berechnungen wie FFT mehr machen muss.

[hustbaer]

@DSP-freak:
Ich weiss nicht genau was du meinst. Ich spreche von langen FIR Filtern wo nahezu alle Koeffizienten ungleich 0 sind - was willst du da mit "Konstanten" optimieren?

[digitalfiter-freak]

mit konstanten meinte ich die koeffizienten. sampling-wert kommt in einen ringuffer, dann werden alle elemente des buffers mit dem dazugehörigen koeffizienten multipliziert, der output berechnet (z.b. mittelwert von allem). danach wird der buffer eins weitergeschoben, wobei das älteste element rausfliegt. usw.usw..

[soerenP]

Mein lieber DSP-Freak,
dann hast du wohl noch nie FIR-Filter mit längeren koeffizientensätzen probiert... (ohne DSP) Da geht nämlich ohne FFT-Faltung gar nichts. Und die muss man wohl zur laufzeit durchführen, die koeffizienten kann man zwar vorher transformieren, aber der Audio-Input ist (zumindest bei mir ) immer noch zur Laufzeit erstellt...
Falls dir das Prinzip ungeläufig ist:
Input und Koeffizienten werden über FFT in den Frequenzbereich transformiert, dort wird eine komplexe Multiplikation durchgeführt, was viel schneller geht als eine Faltung (n berechnungen anstatt n*n) da die FFT ab einer bestimmten Puffergröße viel schneller ist als eine normale Transormation (die so lange dauern würde wie die brute force faltung) kann man so immens Zeit sparen.
@alle anderen:
Ja, klar kann ich über die richtigen Algorithmen Zeit sparen, wie man sieht, aber wenn man mal keinen Standard braucht, wer sagt mir, wie ich vorgehen soll?
Ich bin mir sicher, dass in meinem Programm so unglaubliche Schnitzer drin sind, für deren verbesserung mir bestimmt kein Algorithmen-Buch hilft.
Algorithmen sind ja auch eher Mathematischer Natur. Ich meine, ein Algorithmus kann bestimmt ganz toll sein (z.B. FFT), ein ahnungsloser Mathematiker könnte ihn aber unter Umständen sehr schlecht in Code übersetzen, z.B. weil er nicht weiss, dass Speicherzugriff auch Zeit kostet, oder wie auch immer. Versteht ihr, was ich meine?
Viele Grüße
Sören

[soerenP]

Nochmal, um meine Misere etwas zu erläutern:
Ich bin dabei, einen Synthesizer für die VST-Schnittstelle zu basteln. Läuft auch, alles kein Thema. Er basiert auf dem Karplus-Strong algorithmus, im Prinzip nur eine Verzögerung, die der Periodendauer entspricht, eine Anregungsfunktion und ein Filter, der die Höhen rausnimmt im Verlauf der Schwingung. (den ich aber auch deaktiviert habe, um zu schauen, wieviel Leistung er frisst). Alles mit Sicherheit kein Hexenwerk. Wenn ich davon aber 5 Stimmen Spiele (ohne Filter) ist mein Turion Dual Core schon zu 50% ausgelastet. Da ist bestimmt was ziemlich im Argen und meine Algorithmen sind meiner Meinung nach so simpel, dass sie nicht wirklich zu vereinfachen sind. Ich bin fast der Meinung, dass man die eigentlich nicht so schlecht hinbekommen kann, dass ich ein solches Ergebnis bekomme...
Naja...
Grüße
Sören

[und]

hast du jetzt schon mal nen profiler verwendet?

[soerenP]

Just in diesem Moment habe ich den CodeAnalyst von AMD mal angeschmissen.Und wollte auch gleich eine Frage dazu stellen.
Also: Der Analyst zeigt an, dass die meiste Zeit "an der ersten Klammer meiner Funktionen" verbraucht wird. Was sagt mir das? Würde da inline was helfen, weil ich da nicht für jeden Aufruf jede Menge quatsch auf den Stack schreibe (vorsicht, Halbwissen)? Wie kann ich den Plot, bzw. die Timesamples, überhaupt interpretieren?
Heißt das konkret, wieviel Zeit der Prozessor mit einem bestimmten Befehl beschäftigt ist?
Hab mal die ASM-übersetzuung angeschaut. Die meiste Zeit (über 50%) verbringt er mit:

rep stosd es:[edi]

und zwar bei jeder funktion. Weiss jemand, was das heißt?
Grüße
Sören

[Redhead]

Wenn du unter Windows programmierst könnte ich aus eigener Erfahrung:
http://www.glowcode.com/
empfehlen. Der ist einfach zu verwenden und der Output ist, meines
Erachtens, nahezu selbsterklärend.

[hmmm......]

Kenn den CodeAnalyst nicht. Aber kann es sein, dass du ne große Struktur/Klasse oder was anderes großes als Kopie und nicht als Pointer/Referenz übergiebst?

[soerenP]

hmmm...... schrieb:

Kenn den CodeAnalyst nicht. Aber kann es sein, dass du ne große Struktur/Klasse oder was anderes großes als Kopie und nicht als Pointer/Referenz übergiebst?

Eigentlich nicht, weder in dieser funktion (die ist void (void)) noch in irgendwelchen anderen Funktionen übergebe ich Objekte oder Strukturen, wenn dann als Pointer. Meine betroffenen funktionen sind alle void (void) oder seltener float (void) und zuletzt float (float).
Vielleicht hat der Compiler ne falsche Einstellung?
Ist der VC++ 2005 Express Edition-Compiler.
Grüße
Sören

[soerenP]

Wie ich das jetzt rausgefunden habe, hat der rep stosd den zweck, Daten zu kopieren, in meinem Falle die unnützen Daten aus eax (cccccccch) 33h-mal an [edi]etc...pp... zu kopieren. Warum schreibt mein dummer Compiler das an den Anfang meiner Funktion?
Grüße
Sören

Achja, Worauf edi zeigt? Keine Ahnung, es gab ein

mov ebp,esp
lea edi,[ebp-000000cch]

vorher, mehr weiß ich nicht.

[rapso]

ich wuerde vermuten dass du riesige datenmengen per value uebergibst oder zumindestens riesige datenmengen zuweist (kann auch ein ctor einer localen variable sein der das macht).

[yogle]

Mit Exception Handling wie try catch oder __try __except kann es nichts zu tun haben?

[soerenP]

rapso schrieb:

ich wuerde vermuten dass du riesige datenmengen per value uebergibst oder zumindestens riesige datenmengen zuweist (kann auch ein ctor einer localen variable sein der das macht).

Nö, tut mir leid. Als lokale Variablen gibts nur einfache floats und ints. Funktionen sind, wie gesagt ohne oder nur mit float-parameter.
Es gibt auch sonst keinen sinnvollen Grund in einen 33h - mal 4 ByteGroßen Speicher cccccccch reinzuschreiben, oder?
Aber im Laufe meiner Nachforschungen habe ich rausgefunden, dass genau der Code auch bei anderen Funktionen (nicht von mir, siehe hier:
http://forums.devshed.com/c-programming-42/convert-c-to-assembly-language-183227.html vorne dran gehängt wird. Kann doch nicht Sinn der Sache sein, oder? Vielleicht sollte ich mal im Assembler-Forum nachfragen.
Grüße
Sören

[soerenP]

yogle schrieb:

Mit Exception Handling wie try catch oder __try __except kann es nichts zu tun haben?

Hmmm, auch nicht. Hab in meinem kompletten Code kein __try drin

[rapso]

soerenP schrieb:

rapso schrieb:

ich wuerde vermuten dass du riesige datenmengen per value uebergibst oder zumindestens riesige datenmengen zuweist (kann auch ein ctor einer localen variable sein der das macht).

Nö, tut mir leid. Als lokale Variablen gibts nur einfache floats und ints. Funktionen sind, wie gesagt ohne oder nur mit float-parameter.
Es gibt auch sonst keinen sinnvollen Grund in einen 33h - mal 4 ByteGroßen Speicher cccccccch reinzuschreiben, oder?

doch, debuggen.

[dapadu]

Du kompilierst aber nicht im debug modus bei der performance messung?

Kannst die die Codestellen mal zeigen (funktion+aufruf)?

[soerenP]

Ok, stimmt, wenn ich nicht debugge, schmeißt er anderen Code raus, der auch nicht wesentlichs schneller ist, aber die o.g. Aufrufe nicht hat. Vielleicht versteh ich den Profiler auch nicht so ganz. Jetzt zeigt er mir an, dass ein fstp ca.40% der Rechenzeit einer Funktion verbaucht. Kann ja auch nicht wirklich sein, oder?
Ich probier mal den Glowcode aus..[edit: NOOOOOOOT, wer gibt mir die 499$]

[soerenP]

dapadu schrieb:

Du kompilierst aber nicht im debug modus bei der performance messung?

Kannst die die Codestellen mal zeigen (funktion+aufruf)?

Ja, sorry, ich wusste nicht, dass der Debug die performance so einschränkt. Ausserdem bekomm ich es nicht hin, nicht zu debuggen und im Profiler noch c++ code zu bekommen
Code folgt:

//Um nicht ständig return werte zu bekommen und in die nächste Funktion zu
//stecken habe ich die Module durch Pointer verbunden, wo sie ihren Eingang her
//beziehen und ihren Ausgang reinschreiben
float CSVoice::computeNextSample()
{

	if(!m_active)return 0;

	m_initWave[0].computeNextSample();//displayed on the lefthand side
	m_initWave[1].computeNextSample();
	(*m_mixOut)+=m_inGainModulated*(m_mixModulated*m_mixIn1+m_oneMinusMix*m_mixIn2)+m_sympathyInput;
	m_mixIn1=0;
	m_mixIn2=0;
	m_filter.computeNextSample();
	m_antiFixpointHP.computeNextSample();
	m_delay.computeNextSample();
	m_nonlinearity.computeNextSample();
	if(m_loopInput<0.0000000001&&m_loopInput>-0.0000000001&&m_loopInput!=0)m_denormalCounter++;
	else m_denormalCounter=0;
	if(m_denormalCounter>500)
	{
		m_delay.clear();
		m_active=false;
	}
	return m_loopInput;
}
//Ein variables nicht-integer delay
void CSVFDelay::computeNextSample()
{
	//linearInterpolation
	(*m_output)=m_delayLine[m_readPointer2]*m_integerRemainder+m_delayLine[m_readPointer]*(1-m_integerRemainder);
	//if(m_loopOutput)(*m_loopOutput)=(*m_output);
	m_delayLine[m_writePointer]=m_input;
	m_input=0;
	m_writePointer++;
	m_readPointer++;
	m_readPointer2++;
	if(m_writePointer==kMaxDelay)m_writePointer=0;
	if(m_readPointer==kMaxDelay)m_readPointer=0;
	if(m_readPointer2==kMaxDelay)m_readPointer2=0;
}
//Ein brute-force fir-filter mit 5 bzw. 13 koeffizienten
//Wollte noch ausprobieren, ob es mit Ringpuffer schneller geht, siehe
//diskussion im Forum
void CSParamFilter::computeNextSample()
{
	memmove(&m_inBuffer[m_activeInBuffer][1],&m_inBuffer[m_activeInBuffer][0],m_lengthMinusOne[m_activeInBuffer]*sizeof(float));
	float sum=0;
	m_inBuffer[m_activeInBuffer][0]=m_input;
	for(int i=0;i<m_filterLength[m_activeCoeff];i++)
		sum+=m_inBuffer[m_activeInBuffer][i]*m_theCoeffs[m_activeCoeff][i];
	(*m_output)+=sum;
	if(m_loopOutput)(*m_loopOutput)=sum;
	m_input=0;
}
//wendet eine nichtlineare funktion auf den Input an. Diese ist definiert durch
//eine Tabelle (functionLut), die im x-Bereich von -1 bis 1 geht. 
void CSNonlinearity::computeNextSample()
{
	m_input*=m_preGain;
	if(m_input>1)
	{
		m_input=1;
	}
	if(m_input<-1)
	{
		m_input=-1;
	}

	int in=(int)(m_input*m_hLutSize);
	float rest=m_input*m_hLutSize-in;
	in+=m_hLutSize;
	//linearInterpolation:1. between two LookUpTable values, 2. linear/nonlinear
	float temp=(m_functionLut[in]*(1-rest)+m_functionLut[in+1]*rest)*m_nonlinearity+(1-m_nonlinearity)*m_input;
	(*m_output)=temp*m_postGain;
	m_input=0;
}

Mit Sicherheit lässt sich da einiges tun, aber sooo schlecht wie mein Ergebnis hätte ich es nicht erwartet...
Grüße
Sören

[rapso]

soerenP schrieb:

Ok, stimmt, wenn ich nicht debugge, schmeißt er anderen Code raus, der auch nicht wesentlichs schneller ist, aber die o.g. Aufrufe nicht hat.

die stelle die 50% der zeit zieht ist weg und es laeuft immer noch gleich schnell? ja...

Vielleicht versteh ich den Profiler auch nicht so ganz. Jetzt zeigt er mir an, dass ein fstp ca.40% der Rechenzeit einer Funktion verbaucht. Kann ja auch nicht wirklich sein, oder?

doch, die allermeisten programme sind speicherlimitiert, da die compiler wenn alle optimierungen eingeschaltet sind akzeptablen code generieren und fuer den misst der dann noch uebrig bleibt, dafuer sind die x86 cpus angepasst worden.
was unoptimiert bleibt ist meist der speicher-teil, durch allignment und padding kann der compiler nur maginal aushelfen, da auch dafuer die x86-cpus ausgelegt sind.