3. Performantes mehrdimensionales Array gesucht

Performantes mehrdimensionales Array gesucht

  • I

    Hallo,

    ich bin auf der Suche nach einem performanten mehrdimensionalen Array, dessen Größe nicht zur Compilezeit feststeht. Ich habe die mir bekannten Implementationen im Stil

    start_time = clock();
  for (int i=0; i<iter; ++i) 
    for (int x=0; x<s1; ++x) 
      for (int y=0; y<s2; ++y) 
	    for (int z=0; z<s3; ++z) 
	      test[x][y][z] = 2.341;
  end_time = clock();

    getestet und es kam raus

    Blitz++: 116.37 s
    Boost-Multiarray: 8.83 s / 3.68 s (abhängig von der Zugriffsart)
    STL-Vector: 0.69 s
    C++-eigene Arrays (Mehrfachzeiger): 0.28 s

    Daher die Frage: Kennt jemand eine Alternative, die schneller als ein STL-Vector ist, aber mehr Komfort bietet als die C++-eigenen Arrays?

    0
  • ?

    Hast du die Debug-Informationen weggelassen und Optimierung eingeschaltet?

    0
  • I

    Janjan schrieb:

    Hast du die Debug-Informationen weggelassen und Optimierung eingeschaltet?

    Ja, und BOOST_DISABLE_ASSERTS ist gesetzt.

    0
  • K

    Kannst du bitte den kompletten Test zum download anbieten, damit man sich von dem Ergebnis selbst ueberzeugen kann?

    0
  • T

    Und falls Du MSVC benutzt, hast Du dann auch _SECURE_SCL auf 0 gesetzt?

    0
  • ?

    das taugt als Benchmark nicht! Da Du eine Konstante Zuweisung machst, kann es sein, dass der Compiler für ein C-Array einen Memset macht (zumindest für die letzte Dimension).

    0
  • I

    knivil schrieb:

    Kannst du bitte den kompletten Test zum download anbieten, damit man sich von dem Ergebnis selbst ueberzeugen kann?

    Hierbei ist ein seltsames Phänomen aufgetaucht, aber erstmal der Code (es sind 4 Dateien):

    test_running_time.cpp

    /* running time comparison: 
   - native matrix
   - boost multi_array
   - vector 
*/

#include <iostream>
#include <vector>
#include <ctime>
#include <sys/time.h>
#include "test_class.h"

#define BOOST_DISABLE_ASSERTS
#include "boost/multi_array.hpp"

using namespace boost;
using namespace std;

int main() {
  clock_t start_time;
  clock_t end_time;
  const int ITERATIONS = 10000;
  int X = 10;
  int Y = 3000;
  int Z = 3;

  cout << "Main: " << endl;

  // boost multi_array:
  multi_array<double, 3> test_running_time1;
  multi_array<double, 3>::extent_gen ext;
  test_running_time1.resize(ext[X][Y][Z]);

  start_time = clock();
  for (int i=0; i<ITERATIONS; ++i) {
    for (int x=0; x<X; ++x) {
      for (int y=0; y<Y; ++y) {
        for (int z=0; z<Z; ++z) {
          test_running_time1[x][y][z] = 2.341;
        }
      }
    }
  }
  end_time = clock();
  cout << "Boost: " << double(end_time-start_time) /CLOCKS_PER_SEC*1000 << " ms" << endl;

  // Boost multi_array, different access to elements:
  start_time = clock();
  for (int i=0; i<ITERATIONS; ++i) {
    for (int x=0; x<X; ++x) {
      for (int y=0; y<Y; ++y) {
        for (int z=0; z<Z; ++z) {
          boost::array<multi_array<double,3>::index,3> idx = {{x,y,z}};
          test_running_time1(idx) = 2.341;
        }
      }
    }
  }
  end_time = clock();
  cout << "Boost diff array access: " << double(end_time-start_time) /CLOCKS_PER_SEC*1000 << " ms" << endl;

  // Native:
  double*** test_running_time2 = new double**[X];
  for (int x=0; x<X; ++x) {
    test_running_time2[x] = new double*[Y];
    for (int y=0; y<Y; ++y) {
      test_running_time2[x][y] = new double[Z];
    }
  }

  start_time = clock();
  for (int i=0; i<ITERATIONS; ++i) {
    for (int x=0; x<X; ++x) {
      for (int y=0; y<Y; ++y) {
        for (int z=0; z<Z; ++z) {
          test_running_time2[x][y][z] = 2.341;
        }
      }
    }
  }
  end_time = clock();
  cout << "Native: " << double(end_time-start_time) /CLOCKS_PER_SEC*1000 << " ms" << endl;

  // Vectors:
  vector<vector<vector<double> > > test_running_time3(X, vector<vector<double> >(Y, vector<double>(Z)));
  start_time = clock();
  for (int i=0; i<ITERATIONS; ++i) {
    for (int x=0; x<X; ++x) {
      for (int y=0; y<Y; ++y) {
        for (int z=0; z<Z; ++z) {
          test_running_time3[x][y][z] = 2.341;
        }
      }
    }
  }
  end_time = clock();
  cout << "Vector: " << double(end_time-start_time) /CLOCKS_PER_SEC*1000 << " ms" << endl << endl;

  TestClass t = TestClass();

  return 0;
}

    test_class.h

    #ifndef _TESTCLASS_H
#define _TESTCLASS_H

using namespace std;

class TestClass {
public:
  TestClass();
  ~TestClass(){};
};

#endif

    test_class.cpp

    #include <iostream>
#include <vector>
#include <ctime>
#include <sys/time.h>
#include "test_class.h"

#define BOOST_DISABLE_ASSERTS
#include "../../libs/boost/boost/multi_array.hpp"

using namespace boost;
using namespace std;

TestClass::TestClass(){
  clock_t start_time;
  clock_t end_time;
  const int ITERATIONS = 10000;
  int X = 10;
  int Y = 3000;
  int Z = 3;

  cout << "Test class: " << endl;

  // boost multi_array:
  multi_array<double, 3> test_running_time1;
  multi_array<double, 3>::extent_gen ext;
  test_running_time1.resize(ext[X][Y][Z]);

  start_time = clock();
  for (int i=0; i<ITERATIONS; ++i) {
    for (int x=0; x<X; ++x) {
      for (int y=0; y<Y; ++y) {
        for (int z=0; z<Z; ++z) {
          test_running_time1[x][y][z] = 2.341;
        }
      }
    }
  }
  end_time = clock();
  cout << "Boost: " << double(end_time-start_time) /CLOCKS_PER_SEC*1000 << " ms" << endl;

  // Boost multi_array, different access to elements:
  start_time = clock();
  for (int i=0; i<ITERATIONS; ++i) {
    for (int x=0; x<X; ++x) {
      for (int y=0; y<Y; ++y) {
        for (int z=0; z<Z; ++z) {
          boost::array<multi_array<double,3>::index,3> idx = {{x,y,z}};
          test_running_time1(idx) = 2.341;
        }
      }
    }
  }
  end_time = clock();
  cout << "Boost diff array access: " << double(end_time-start_time) /CLOCKS_PER_SEC*1000 << " ms" << endl;

  // Native:
  double*** test_running_time2 = new double**[X];
  for (int x=0; x<X; ++x) {
    test_running_time2[x] = new double*[Y];
    for (int y=0; y<Y; ++y) {
      test_running_time2[x][y] = new double[Z];
    }
  }

  start_time = clock();
  for (int i=0; i<ITERATIONS; ++i) {
    for (int x=0; x<X; ++x) {
      for (int y=0; y<Y; ++y) {
        for (int z=0; z<Z; ++z) {
          test_running_time2[x][y][z] = 2.341;
        }
      }
    }
  }
  end_time = clock();
  cout << "Native: " << double(end_time-start_time) /CLOCKS_PER_SEC*1000 << " ms" << endl;

  // Vectors:
  vector<vector<vector<double> > > test_running_time3(X, vector<vector<double> >(Y, vector<double>(Z)));
  start_time = clock();
  for (int i=0; i<ITERATIONS; ++i) {
    for (int x=0; x<X; ++x) {
      for (int y=0; y<Y; ++y) {
        for (int z=0; z<Z; ++z) {
          test_running_time3[x][y][z] = 2.341;
        }
      }
    }
  }
  end_time = clock();
  cout << "Vector: " << double(end_time-start_time) /CLOCKS_PER_SEC*1000 << " ms" << endl;
}

    makefile

    #
# Makefile for jpHMM.cpp
#

CC	        = g++
OBJ_DIR     = .
CFLAGS	    = -Wall -ansi -pedantic -g0 -ggdb -O3 -DDEBUG
TARGET 	    = test_running_time

INCLS   = -I/home/ingo/libs/boost/ 

SOURCES      = $(wildcard *.cpp)
SOURCES     := $(filter-out test_running_time.cpp, $(SOURCES))
OBJS	     = $(patsubst %.cpp, $(OBJ_DIR)/%.o, $(SOURCES))

$(TARGET): test_running_time.cpp $(OBJS)
	@echo "$(OBJS)\n"
	$(CC) $(CFLAGS) -o $@ $< $(OBJS) $(INCLS)

$(OBJ_DIR)/%.o : %.cpp
	$(CC) -c $< -o $@  $(INCLS)

clean:
	rm -f $(TARGET) $(TEST_TARGET) $(OBJS)

    Das Programm führt in test_running_time.cpp den Geschwindigkeitsvergleich durch und ruft dann den Konstruktor von TestClass auf, wodurch derselbe Geschwindigkeitsvergleich nochmal ausgeführt wird.

    Das Seltsame sind nun die Ergebnisse. Bei mir erhalte ich:

    Main:
    Boost: 490 ms
    Boost diff array access: 540 ms
    Native: 640 ms
    Vector: 740 ms

    Test class:
    Boost: 137560 ms
    Boost diff array access: 53830 ms
    Native: 4440 ms
    Vector: 9770 ms

    Kann jemand das erklären?

    0
  • U

    wie wärs denn, erst mal den quellcode leserlicher zu gestalten?
    Evtl auch die Messung etwas von der eigentlichen Aufgabe abzukoppeln?

    und dann so was:

    for (int i=0; i<ITERATIONS; ++i)
{
  for (int x=0; x<X; ++x)
  {
    for (int y=0; y<Y; ++y)
    {
      for (int z=0; z<Z; ++z)
      {
        boost::array<multi_array<double,3>::index,3> idx = {{x,y,z}};
        test_running_time1(idx) = 2.341;
      }
    }
  }
}

    (ich habs mal ordnetlich eingerückt)
    wird kein guter compiler mit eingeschalteter optimierung berücksichtigen - die äußere schleife wird einfach wegoptimiert...

    bb

    0
  • I

    Ich habe die Einrückung korrigiert (da kommt die Eingabe wohl nicht mit der gemischten Verwendung von Leerzeichen und Tabs klar).

    Unabhängig davon, ob Schleifen wegoptimiert werden: Warum sind die Zeiten zwischen Ausführung in main und Ausführung im Konstruktor einer Klasse so verschieden?

    0
  • ?

    Die Ursache ist klar: Im makefile fehlen die CFLAGS beim OBJ_DIR-Ziel.
    Korrekt ist:

    $(OBJ_DIR)/%.o : %.cpp
	$(CC) $(CFLAGS) -c $< -o $@  $(INCLS)

    In dem Zusammenhang ist vielleicht auch Array2d aus
    (http://www.cppbuch.de/code.html, unten bei 24.10) interessant.
    Vorteil: hat im Ggs. zu Boost und Blitz überladene Operatoren,
    Nachteil: A) nur 2-dimensional 😎 nur ab G++ 4.4 (muss mit
    -std=c++0x statt -ansi übersetzt werden.

    0
Anmelden zum Antworten