3. betrag-maximum suchen ...

betrag-maximum suchen ...

  • R

    tach zusammen,

    bin auf der suche nach tips, anregungen, code-schnippsel oder was auch immer um aus einem float-array der grösse 4096 dem betrage nach höchsten wert zu finden.

    gefragt ist nicht schönheit sondern speed ...

    any comment welcome ... rocknix ///

    0
  • B
     

    float max(float array[4096]) {
  float result = fabs(array[0]);
  int result_index = 0;
  for (int i = 1; i < 4096; ++i) {
    float temp = fabs(array[i]);
    if (temp > result) {
      result = temp;
      result_index = i;
    }
  }
  return array[result_index];
}

    Oder brauchst du was genialeres? C99 hat fabsf für echte floats (fabs ist für double). C++ müßte ein überladenes abs für float haben.

    0
  • R

    hm, ja ich habe es so ähnlich gemacht, allerdings ohne fabs(), sondern mit einer if-abfrage ob grösser oder kleiner 0. vermutlich wird in der fabs() funktion auch nichts anderes gemacht.

    naja, die sache ist die - es handelt sich hier um eine rt-audio-algo und dieses dämliche suchen des maxwertes verschlingt von dem gesamten processing fast 80%

    ich suche jetzt irgendwie eine methode das zu beschleunigen ... gibts nicht irgendeine bitverknüpfung, die mir das vorzeichen eines float/double ausblenden kann ... da würden dann schon mal etliche "cmp" und "condintional jmp" rausfallen ...

    rocknix ///

    0
  • B

    Joa http://www.psc.edu/general/software/packages/ieee/ieee.html sagt, das MSB ist das Vorzeichenbit.

    0
  • R

    not bad ... vielen dank - werde mal sehen, was sich damit rausholen lässt.

    rocknix ///

    0
  • R

    FYI:

    nach IEEE müsste man das vorzeichen bit so ausblenden können oder irre ich ?

    float f = -1.0;
f &= 0x7fffffff;

    das klappt so schon mal nicht, da vc++ meckert, das man bit-ops nicht mit einem float machen kann ...

    von float nach int und wieder zurück casten funktioniert irgendwie nicht, keine ahnung warum.

    ein byte-pointer auf ein float, um 3 verschoben und dann ein AND mit 0x7f, funktioniert einwandfrei, bringt ca. 10% gewinn - immerhin 🙂

    aber jetzt kommst:

    mein erster versuch (s.o.) war eine if-abfrage - tausche ich diese einfach gegen die von bashar genannte fabs() funktion aus - ich vermutete bis dato die macht dasselbe und ich spare die calls - bringt das satte 70% gewinn !!!

    na wenn das nichts ist 🙂

    jemand eine ahnung, was genau die da machen ?

    rocknix ///

    0
  • R

    ach so - noch zur info:

    die performance analyse wurde mit TRUE TIMING von NuMega DevPartnerStudio durchgeführt. also sicherlich ein aussagefähiges resultat 😉

    rocknix ///

    0
  • T

    Original erstellt von RockNix:
    **aber jetzt kommst:

    mein erster versuch (s.o.) war eine if-abfrage - tausche ich diese einfach gegen die von bashar genannte fabs() funktion aus - ich vermutete bis dato die macht dasselbe und ich spare die calls - bringt das satte 70% gewinn !!!

    na wenn das nichts ist 🙂

    jemand eine ahnung, was genau die da machen ?
    **

    Also sofern wir von einem x86-Rechner reden. Vermutlich haben die ganz einfach den fabs-Befehl da genommen. Das ist nämlich einfach schneller als einen zweiten Wert einladen und Vergleichen gehen (schon weil das fabs nur ein bit umdreht, während ein Vergleich durchaus komplex sein kann).

    0
  • B

    vielleicht gibts einen Maschinenbefehl, der den Absolutbetrag bildet. fabs wird dann idealerweise noch intrinsisch in diesen Befehl umgesetzt.

    0
  • T

    Original erstellt von Bashar:
    vielleicht gibts einen Maschinenbefehl, der den Absolutbetrag bildet. fabs wird dann idealerweise noch intrinsisch in diesen Befehl umgesetzt.

    Genau den gleichnamigen Asm-Befehl 🙂

    0
  • V

    ich nehm nicht an, daß du ein kleines messprogramm hast?

    0
  • R

    ich nehm nicht an, daß du ein kleines messprogramm hast?

    ähm, wie meinst du ?

    rocknix ///

    0
  • V

    ich würde mich morgen an der suche nach der schnellsten funktion beteiligen. und hab eigentlich nur lust auf die schnelle funktion und nicht drauf, vorher ein langes prog zu bauen, was mißt.

    0
  • R

    ach so, doch klar - hier ist meine kleine testroutine, die schnellere von beiden wird dann wieder in das "grosse" project zurückwandern.

    #include <windows.h>
#include <stdio.h>
#include <math.h>

#define AVG_SIZE 1
float m_rightAvg[AVG_SIZE];
float m_leftAvg[AVG_SIZE];
UINT m_uAvgIndex = 0;

/////////////////////////////////////////////////////////////////////////////////////
int peak_abs( const float* dest, DWORD size)
{
    DWORD iSearchLength = size/2-2;
    float f = 0.0;

    m_leftAvg[ m_uAvgIndex] = fabs( dest[0]);

    // find left max
    for( x=2;  x<iSearchLength; x=x+2)
    {
        if( m_leftAvg[ m_uAvgIndex] < fabs(dest[x]))
            m_leftAvg[ m_uAvgIndex] = fabs(dest[x]);
    }

    m_rightAvg[ m_uAvgIndex] = fabs( dest[1]);

    // find right max
    for( x=3;  x<iSearchLength; x=x+2)
    {
        if( m_rightAvg[ m_uAvgIndex] < fabs(dest[x]))
            m_rightAvg[ m_uAvgIndex] = fabs(dest[x]);
    }

    m_uAvgIndex++;

    if(m_uAvgIndex==AVG_SIZE)
            m_uAvgIndex = 0;

    return 0;
}

/////////////////////////////////////////////////////////////////////////////////////

int peak_if( const float* dest, DWORD size)
{
    DWORD iSearchLength = size/2-2;

    float* pTemp = new float[size];

    // make unsigned
    for( DWORD x=0; x<size; x++)
    {
        if( dest[x]<0.0)
            pTemp[x] = -dest[x];
        else
            pTemp[x] = dest[x];
    }

    m_leftAvg[ m_uAvgIndex] = pTemp[0];
    // find left max
    for( x=2;  x<iSearchLength; x=x+2)
    {
        if( m_leftAvg[ m_uAvgIndex]<pTemp[x])
            m_leftAvg[ m_uAvgIndex] = pTemp[x];
    }

    m_rightAvg[ m_uAvgIndex] = pTemp[1];
    // find right max
    for( x=3;  x<iSearchLength; x=x+2)
    {
        if( m_rightAvg[ m_uAvgIndex]<pTemp[x])
            m_rightAvg[ m_uAvgIndex]=pTemp[x];
    }

    m_uAvgIndex++;

    if(m_uAvgIndex==AVG_SIZE)
            m_uAvgIndex = 0;

    delete pTemp;

    return 0;
}

/////////////////////////////////////////////////////////////////////////////////////

int main()
{
    int x=0;
    float data[4096];

    ZeroMemory( data, 4096*sizeof(float));

    data[2] = 1.0;
    data[3] = -1.0;

    for( x=0; x<100; x++)
        peak_if( data, 4096);

    for( x=0; x<100; x++)
        peak_abs( data, 4096);

    return 0;
}

    so far ... rocknix ///

    ps: vielleicht ist es sogar möglich, den rechten und linken kanal in einer schleife durchzuarbeiten, who knows ...

    [ Dieser Beitrag wurde am 30.04.2003 um 16:50 Uhr von RockNix editiert. ]

    0
  • V

    ok, ich fang jetzt an.
    aber dein test-prog geht nicht. ich bau doch ein eigenes. ich nehm bashars prototyp dazu und zufallszahlen drin. umbauen auf dein prob wirste dann selber müssen.

    0
  • V

    frage: wurde das array kurz vorher gebaut oder gelesen, daß es noch im cache liegt?

    0
  • V

    ich teste hiermit (MSVC60):

    #include <iostream>
#include <cmath>
using namespace std;

float max(float array[4096]) {
  float result = fabs(array[0]);
  int result_index = 0;
  for (int i = 1; i < 4096; ++i) {
    float temp = fabs(array[i]);
    if (temp > result) {
      result = temp;
      result_index = i;
    }
  }
  return array[result_index];
}

float test(float array[4096]) {
  float result = fabs(array[0]);
  int result_index = 0;
  for (int i = 1; i < 4096; ++i) {
    float temp = fabs(array[i]);
    if (temp > result) {
      result = temp;
      result_index = i;
    }
  }
  return array[result_index];
}

void fill(float array[4096])
{
    srand(0);
    for(int i=0;i<4096;++i)
    {
        array[i]=rand()/10.0;
    }
}

typedef unsigned __int64 u64;

#pragma warning(push)
#pragma warning(disable:4035)//warning C4035: 'rdtsc' : Kein Rueckgabewert
inline u64 rdtsc()
{
    __asm rdtsc;
}
#pragma warning(pop)

int main()
{
    float array[4096];
    {
        fill(array);
        float m1=max(array);
        fill(array);
        float m2=test(array);
        if(m1!=m2)
        {
            cout<<"fehler!"<<endl;
            return 1;
        }
    }

    int left=1000;
    u64 mintime=-1;
    float sum=0;
    while(left)
    {
        --left;
        fill(array);
        u64 start=rdtsc();
        sum+=test(array);
        u64 stop=rdtsc();
        u64 time=stop-start;
        if(time<mintime)
        {
            mintime=time;
            left=1000;
            cout<<int(mintime)<<" takte"<<endl;
        }
    }
    cout<<sum<<endl;
    return 0;
}

    zur zeit bei mir 123151 takte.

    0
  • M

    hier die portierte version:

    #include <iostream>
#include <cmath>
using namespace std;

float max(float array[4096]) {
  float result = fabs(array[0]);
  int result_index = 0;
  for (int i = 1; i < 4096; ++i) {
    float temp = fabs(array[i]);
    if (temp > result) {
      result = temp;
      result_index = i;
    }
  }
  return array[result_index];
}

float test(float array[4096]) {
  float result = fabs(array[0]);
  int result_index = 0;
  for (int i = 1; i < 4096; ++i) {
    float temp = fabs(array[i]);
    if (temp > result) {
      result = temp;
      result_index = i;
    }
  }
  return array[result_index];
}

void fill(float array[4096])
{
    srand(0);
    for(int i=0;i<4096;++i)
    {
        array[i]=rand()/10.0;
    }
}

#ifdef _MSC_VER
typedef unsigned __int64 u64;

#pragma warning(push)
#pragma warning(disable:4035)//warning C4035: 'rdtsc' : Kein Rueckgabewert
inline u64 rdtsc()
{
    __asm rdtsc;
}
#pragma warning(pop)
#else // gcc
typedef unsigned long long u64;
#define _rdtsc(low) __asm__ __volatile__ ("rdtsc" : "=a" (low) : : "edx")
inline u64 rdtsc() {
    int a;
    _rdtsc(a);
    return a;
}
#endif

int main()
{
    float array[4096];
    {
        fill(array);
        float m1=max(array);
        fill(array);
        float m2=test(array);
        if(m1!=m2)
        {
            cout<<"fehler!"<<endl;
            return 1;
        }
    }

    int left=1000;
    u64 mintime=-1;
    float sum=0;
    while(left)
    {
        --left;
        fill(array);
        u64 start=rdtsc();
        sum+=test(array);
        u64 stop=rdtsc();
        u64 time=stop-start;
        if(time<mintime)
        {
            mintime=time;
            left=1000;
            cout<<int(mintime)<<" takte"<<endl;
        }
    }
    cout<<sum<<endl;
    return 0;
}
    0
  • V

    nix neues. nur bashars version kleiner.

    float test(float array[4096]) 
{
    float result = fabs(array[0]);
    for (int i = 1; i < 4096; ++i) 
    {
        if (array[i] > result) 
        {
            result = array[i];
        }
    }
    return result;
}

    hat bei mir 25% gespart.

    0
  • V

    meine meinung:
    bashars lösung ist an sich optimal. ein paar prozemzt kannste mit den üblichen tricks rauskitzenl. nicht viel. mach variablen lokal! dene globalen variablen stören den optimierer.

    und danach:
    brauchte wirklich en maximalwerte aller samples? oder reicht einer, der echt hoch ist? kannst leicht bei 4096 samples nur jeden achten nehmen und keine sau hört den unterschied. es ist hochwahrscheinlich, daß du den maximalwert oder einen, der minstestens 98% davon hat, erwischt hast. noch sauberer und genausi billig (also auchg glatt faktor 😎 ist es, in 8-er-schriten voranzum*****ieren, und bei jeder neulernung des maxwertes (ist ja selten) mal schnell die 8 oder 15 nbachbarwerte anzugucken und evtl die als neuwert zu nehmen).

    [ Dieser Beitrag wurde am 01.05.2003 um 03:37 Uhr von volkard editiert. ]

    0
Anmelden zum Antworten