Performantes mehrdimensionales Array gesucht

ingobulla

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?

Hast du die Debug-Informationen weggelassen und Optimierung eingeschaltet?

ingobulla

Janjan schrieb:

Hast du die Debug-Informationen weggelassen und Optimierung eingeschaltet?

Ja, und BOOST_DISABLE_ASSERTS ist gesetzt.

knivil

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

Tachyon

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

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).

ingobulla

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?

unskilled

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

ingobulla

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?

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.