Cython (mit Numpy) wird nicht schnell

[felue]

Hallo,

mein erstes Cython Programm ist nicht nennenswert schneller als das, was ich von Python (numnpy) kenne. Folgendes habe ich entsprechend der Tutorials gemacht:

- Typen definiert
- bei Funktionsaufruf typen übergeben für effizientes Indexing
- bounds checking ausgeschaltet

Ich habe einige Schleifen drin wie:

Code: Alles auswählen

...
cdef unsigned int indexMinimumZerosColumn
cdef unsigned int rowIndex = 0
cdef unsigned int columnIndex = 0
cdef numpy.ndarray coverRows = numpy.zeros([matrixSize], dtype=numpy.int32)
cdef numpy.ndarray numberOfRowZeros = numpy.zeros([matrixSize], dtype=numpy.int32)
cdef numpy.ndarray matrixSizeVector = numpy.arange(matrixSize, dtype = numpy.int32)
...

for rowIndex in matrixSizeVector:
	if searchMatrix[rowIndex,indexMinimumZerosColumn] == 0:	
		coverRows[rowIndex] = 1		
		numberOfRowZeros[rowIndex] =0	
			for columnIndex in matrixSizeVector:		
				if searchMatrix[rowIndex,columnIndex] == 0:
					searchMatrix[rowIndex,columnIndex] = 1	

da frage ich mich, ob z.B. die for-Schleife über ein numpyArray(matrix Size Vector) langsam ist? Mit dem Profiler hbe ich für ganz normalen Code ca 1.9 Sec ermittelt. Mit allen o.g. Einstellungen sinds ca 1.2 sec.

Vielen Dank für eure Hilfe. Optimal wäre es, wenn mal jemand über die angehängte Datei drüberschauen könnte (kann man das hier nicht? - dann hänge ich den Code der Funktion halt direkt hier an). Besonders die Funktion "getMinimalCover" ist kritisch, weil sie einige male aufgerufen wird und ca 90% der Gesamtbearbeitungszeit frisst.

VG

Code: Alles auswählen

@cython.boundscheck(False) # turn of bounds-checking for entire function
def getMinimalCover(numpy.ndarray[DTYPE_t, ndim=2] inputMatrix not None, numpy.ndarray[numpy.int32_t, ndim=2] assignmentMatrix not None):
	
	cdef numpy.ndarray searchMatrix = numpy.copy(inputMatrix)
	cdef unsigned int matrixSize = searchMatrix.shape[0]
	cdef numpy.ndarray matrixSizeVector = numpy.arange(matrixSize, dtype = numpy.int32)
	cdef numpy.ndarray numberOfRowZeros = numpy.zeros([matrixSize], dtype=numpy.int32)
	cdef numpy.ndarray numberOfColumnZeros = numpy.zeros([matrixSize], dtype=numpy.int32)
	cdef numpy.ndarray coverRows = numpy.zeros([matrixSize], dtype=numpy.int32)
	cdef numpy.ndarray coverColumns = numpy.zeros([matrixSize], dtype=numpy.int32)
	cdef unsigned int rowIndex = 0
	cdef unsigned int columnIndex = 0
	cdef unsigned int noZeros = 0
	cdef unsigned int index
	cdef unsigned int element
	cdef unsigned int currentMinimum
	cdef unsigned int indexMinimumZerosRow
	cdef unsigned int indexMinimumZerosColumn
	cdef unsigned int minimumZerosRow
	cdef unsigned int minimumZerosColumn
	
	for rowIndex in matrixSizeVector:
		noZeros = 0
		for columnIndex in matrixSizeVector:
			if searchMatrix[rowIndex, columnIndex] == 0:
				noZeros +=1
		numberOfRowZeros[rowIndex] = noZeros
		
	for columnIndex in matrixSizeVector:
		noZeros = 0
		for rowIndex in matrixSizeVector:
			if searchMatrix[rowIndex, columnIndex] == 0:
				noZeros +=1
		numberOfColumnZeros[columnIndex] = noZeros			
	
	
	while 1:
		index = 0
		currentMinimum = 1000	
		for element in numberOfRowZeros:
			if element > 0 and element < currentMinimum:
				currentMinimum = element
				indexMinimumZerosRow = index
			index +=1
		minimumZerosRow = currentMinimum
		
		if currentMinimum  == 1000:
			break
		
		index = 0
		currentMinimum = 1000
		for element in numberOfColumnZeros:
			if element > 0 and element < currentMinimum:
				currentMinimum = element
				indexMinimumZerosColumn = index
			index +=1
		minimumZerosColumn = currentMinimum
		
		if minimumZerosRow <= minimumZerosColumn:
			for columnIndex in matrixSizeVector:
				if searchMatrix[indexMinimumZerosRow,columnIndex] == 0:	
					coverColumns[columnIndex] = 1		
					numberOfColumnZeros[columnIndex] =0
					for rowIndex in matrixSizeVector:		
						if searchMatrix[rowIndex,columnIndex] == 0:
							searchMatrix[rowIndex,columnIndex] = 1	
							numberOfRowZeros[rowIndex] -=1
		else:	
			
			for rowIndex in matrixSizeVector:
				if searchMatrix[rowIndex,indexMinimumZerosColumn] == 0:	
					coverRows[rowIndex] = 1		
					numberOfRowZeros[rowIndex] =0	
					for columnIndex in matrixSizeVector:		
						if searchMatrix[rowIndex,columnIndex] == 0:
							searchMatrix[rowIndex,columnIndex] = 1	
							numberOfColumnZeros[columnIndex] -=1
						
	return coverRows, coverColumns

[Dauerbaustelle]

Edit: Alles Müll was ich hier erzähle. Aus Transparenzgründen lass' ich das aber trotzdem mal stehen...

Ich vermute mal, dass bei sowas Cython-Code nicht bedeutend schneller wird als Python-Code -- das Problem hier ist, dass trotz der ganzen Typannotationen die ganze Zeit Python-Typen im Spiel sind: numpy ist nicht in Python geschrieben, wodurch es auch nicht von Cython optimiert werden kann und man deswegen immer Python-Typen hat.

Die meiste Zeit befindet sich o.g. Schleife ja in irgendwelchen Methoden von Numpy-Typen, die als "Eingabe" Python-Typen erwarten (z.B. Tupels für die Argumente etc) und Python-Typen zurückgeben. Hier spart man sich also kaum Overhead. Wenn mich nicht alles täuscht, könnte ein solches Cythonprogramm sogar ein klein Wenig langsamer werden, weil z.B. Python-Integer umgewandelt werden müssen in "C-Integer" (auf dem Stack) und wenn du sie dann z.B. an numpy-Methoden weitergibst wieder in Python-Integer zurückumgewandelt werden.

Bitte alles was oben steht mit Vorsicht genießen, ist eher Ratehalbwissen. Aus meiner Sicht macht es aber Sinn ;-)

Sicher ist aber, dass du den Code kaum optimieren kannst (etwa durch Cython), weil die meiste Zeit vermutlich eh in Numpy draufgeht... was in C geschrieben ist.

[BlackJack]

@Dauerbaustelle: Schau Dir nochmal die Typdeklarationen an. Zum Beispiel: ``cdef numpy.ndarray coverRows ...``. Cython kennt die Interna von `numpy`-Arrays und kann Code erzeugen der direkter an den Inhalt heran kommt als über die Python-Methdoden. Siehe auch das Working with NumPy-Tutorial aus der Cython-Dokumentation.

Edit: Das sollte der OP vielleicht auch mal lesen, zum Beispiel den Abschnitt Efficient Indexing.

[Dauerbaustelle]

@BlackJack: Hätte man das mal gewusst. Okay, war dann offensichtlich totaler Bullshit, den ich da gemutmaßt habe :-)

[felue]

Danke schonmal euch beiden für die prompte Rückmeldung. Die "Lektüreempfehlung" kannte ich schon und habe die Funktion dementsprechend geschrieben (oder nicht? Ich sehe da jetzt keinen Unterschied).

DTYPE_t habe ich in meinem Modul fogendermaßen definiert:
DTYPE = numpy.float64
ctypedef numpy.float64_t DTYPE_t

Was mir noch auffällt und etwas seltsam erscheint: Wenn die inputMatrix (die als Argument der Funktion übergeben wird) höherwertige Elemente besitzt (habe die ganzen Matrix mal mit 1000000 multipliziert), dann wird das alles extrem langsam. Dabei sollte das doch eigentlich keinen Einfluss haben, da die Matrix einen festen Datentyp zugewiesen bekommen hat. Oder?

VG

[BlackJack]

@felue: Lies Dir den Abschnitt nochmal durch. Du hast die lokalen Arrays nur allgemein als Arrays deklariert, aber bei der Deklaration weder angegeben welchen Typ die haben, noch welche Anzahl von Dimensionen bei Indexzugriffen besonders schnell sein sollen.

[felue]

Super,
habe mir das nochmal angeschaut. Wirkt auf mich zwar seltsam, in einer Zeile 2 mal den Datentyp fetzulegen, aber es ist jetzt deutlich schneller.

aus

Code: Alles auswählen

cdef numpy.ndarray searchMatrix = numpy.copy(inputMatrix)
cdef numpy.ndarray matrixSizeVector = numpy.arange(matrixSize, dtype=numpy.int32)

wurde jetzt

Code: Alles auswählen

cdef numpy.ndarray [DTYPE_t, ndim=2] searchMatrix = numpy.copy(inputMatrix)
cdef numpy.ndarray [numpy.int32_t, ndim=1] matrixSizeVector = numpy.arange(matrixSize, dtype=numpy.int32)

Besten Dank nochmal

[BlackJack]

Wenn Du das nicht machst, könnte Cython nicht in allen Fällen den Typ statisch ermitteln. Nur der Typ `ndarray` kann ja an beliebiger Stelle an ein neues Array-Objekt mit anderem Typ und Dimensionen gebunden werden.