@gregor

virtuell Realisticer

Hallo,

bei mir sind es in C++:

12172ms
OS: FreeBSD 4.7-RELEASE
gcc-version: 2.95.4

Java hab ich leider nicht installiert. Werd ich mal installieren muessen

mfg
v R

volkard

hab jetzt einen, der einigermaßen ernshaft ist. also nicht nur für genau dieses programm optimiert, sondern fast einsetzbar.
ein TEST defines ist, sieht man mit dem taskmanager fein, daß der speicher auch wirklich ans BS zurückgegeben wird.
falls einer den MSVC60 drauf hat und Java, könnte der mal messen? (ka, ob der MSVC7 den code fressen würde, hab noch gar nicht auf plattformunabhängigkeit geachtet.)

#include <iostream> 
#include <stdlib.h> 
#include <ctime> 
#include <iostream>
using namespace std;

#include <windows.h>
#include <cassert>

////////////////////////////////////////////////////////////////////////////////
//hier anschalten, ob der small object allocator verwendet werden soll
#define SMALLOBJECTALLOCATOR

////////////////////////////////////////////////////////////////////////////////
//zuerst ein wenig arithmetik.
//gegeben sei SIZE, die größe der zu allokierenden objekte.
//berechnet werden sonn eine ALLOCATORSIZE, die bei glatten zahlen 
//gleich SIZE ist und bei krummen zahlen die nächhöhere glatte zahl.
//glatt seien die zahlen 1, 2, 3, 4, 6, 8, 12, 18, 24, 32...
//also zahlen der form 2^n oder 3*2^n.
//für jede glatte zahl wird später eine eigener allocator angeboten.
//diese allocatoren werden in einem array stehen. 
//mit
//int ai(int s)
//{
//	if(s<4) return s;
//	if(s%2==0) return 2+ai(s/2);
//	return ai(s+1);
//}
//kann aus der size rekursiv der allocatrindex berechnet werden.
//mit
//int as(int i)
//{
//	if(i<4) return i;
//	return 2*as(i-2);
//}
//kann aus dem allocatorindex die allocatorsize berechnet werden.
//as(ai(s)) ergibt die zu s passende glatte zahl.

////////////////////////////////////////////////////////////////////////////////
//SizeToAllocatorIndex berechnet aus der SIZE den arrayindex des allocators.
//SIZE VALUE
//   1     1
//   2     2
//   3     3
//   4     4
//   5     5
//   6     5
//   7     6
//   8     6
//   9     7
//  10     7
//  11     7
//  12     7
//  13     8
//  14     8
//  15     8
//  16     8
//  17     9
//...
template<size_t SIZE>
struct SizeToAllocatorIndex
{
	enum{CALL=SIZE%2==0?SIZE/2:SIZE+1};
	enum{OFFSET=SIZE%2==0?2:0};
	enum{VALUE=OFFSET+SizeToAllocatorIndex<CALL>::VALUE};
};
template<>
struct SizeToAllocatorIndex<1>
{
	enum{VALUE=1};
};
template<>
struct SizeToAllocatorIndex<2>
{
	enum{VALUE=2};
};
template<>
struct SizeToAllocatorIndex<3>
{
	enum{VALUE=3};
};

////////////////////////////////////////////////////////////////////////////////
//AllocatorIndexToAllocatorSize berechnet aus dem arrayindex des allocators dessen objektsize.
//SIZE VALUE
//   1     1
//   2     2
//   3     3
//   4     4
//   5     6
//   6     8
//   7    12
//   8    16
//   9    24
//...
template<int INDEX>
struct AllocatorIndexToAllocatorSize
{
	enum{VALUE=2*AllocatorIndexToAllocatorSize<INDEX-2>::VALUE};
};
template<>
struct AllocatorIndexToAllocatorSize<1>
{
	enum{VALUE=1};
};
template<>
struct AllocatorIndexToAllocatorSize<2>
{
	enum{VALUE=2};
};
template<>
struct AllocatorIndexToAllocatorSize<3>
{
	enum{VALUE=3};
};

////////////////////////////////////////////////////////////////////////////////
template<class T>
class IntrusiveRing
{//ich fürchte, ich werde immer wieder eigene container schreiben müssen.
	//oder hab ich den in der stl oder bost nur übersehen?
public:
	struct Entry
	{
	private:
		Entry* left;
		Entry* right;
	protected:
		friend class IntrusiveRing<T>;
	};
private:
	Entry anchor;
public:
	IntrusiveRing()
	{
		anchor.left=&anchor;
		anchor.right=&anchor;
	}
	void push(T* x)
	{
		Entry* left=anchor.left;
		Entry* right=&anchor;
		x->Entry::left=left;
		x->Entry::right=right;
		left->right=x;
		right->left=x;
	}
	T* pop()
	{
		Entry* x=anchor.left;
		if(x==&anchor) return 0;
		x->left->right=x->right;
		x->right->left=x->left;
		return static_cast<T*>(x);
	}
	void remove(T* x)
	{
		Entry* left=x->Entry::left;
		Entry* right=x->Entry::right;
		left->right=right;
		right->left=left;
	}
};

////////////////////////////////////////////////////////////////////////////////
//maschinenabhänig.
typedef unsigned __int32 u32;
u32 const PAGESIZE=4096;

////////////////////////////////////////////////////////////////////////////////
//und hier endlich der small object allocator
struct Page:public IntrusiveRing<Page>::Entry
{
	void* firstFree;
	u32 usedCount;
};

//mal erlauben, daß der user 4<=SIZE<=255 wählen darf.
int const ALLOCATORS_COUNT=SizeToAllocatorIndex<255>::VALUE+1;
IntrusiveRing<Page> notFullPages[ALLOCATORS_COUNT];
Page* workingPage[ALLOCATORS_COUNT]={0};

//hab ich konstruktor oder was? nee, ich baue c!
Page* createPage(u32 size)
{
	Page* p=(Page*)VirtualAlloc(0,PAGESIZE,MEM_COMMIT,PAGE_READWRITE);//op new geht nicht, denn seiten müsen auf PAGESIZE aligned sein.
	assert(p);

	char* pos=(char*)p+sizeof(Page);					//pos zeigt auf ersten objekt
	p->firstFree=pos;										//firstFree auch (ist topOfStack)

	char* end=(char*)p+PAGESIZE;						//evtl falsch! erste verbotene startadresse

	char* next=pos+size;									//und mit ner schleife
	while(next<end)										//bis zum ende laufen
	{															//und bei jedem objekt den zeiger
		*(void**)pos=next;								//auf das folgende eintragen
		pos=next;
		next+=size;
	}
	*(void**)pos=0;										//und das letzte objet zeigt auf 0

	p->usedCount=0;										//count auf 0 setzen

	return p;
}

//und alloc und free sind erschreckend öde. 
void* smallalloc(int allocatorIndex,u32 size)
{
	Page* p=workingPage[allocatorIndex];
	if(!p){											//wenn keine working page da
		p=notFullPages->pop();					//dann hol die nächste vom page-stack
		if(!p)										//wenn dort keine war
			p=createPage(size);						//dann baue eine neue
		workingPage[allocatorIndex]=p;		//und merk dir die working page
	}

	void* result=p->firstFree;				//ergebnis ist nächstes objekt der page
	p->firstFree=*(void**)result;			//object-stack poppen
	++p->usedCount;									//

	if(!p->firstFree)							//wenn page leergemacht
		workingPage[allocatorIndex]=0;	//dann working page vergessen

	return result;
}

void smallfree(int allocatorIndex,void* x)
{
	u32 const MASK=~(PAGESIZE-1);			//page durch adressrechnung ermitteln
	Page* p=reinterpret_cast<Page*>(reinterpret_cast<u32>(x)&MASK);

	if(!p->firstFree){						//wenn page vergessen war
		if(workingPage)							//wenn working page da
			notFullPages[allocatorIndex].push(workingPage[allocatorIndex]);//working page pushen
		workingPage[allocatorIndex]=p;		//working page sei aktuelle page
	}
	*static_cast<void**>(x)=p->firstFree;//object in page pushen
	p->firstFree=x;

	--p->usedCount;							//usedCount dekrementieren
	if(p->usedCount==0)						//wenn 0
	{
		Page* np=notFullPages[allocatorIndex].pop();	//nächste page holen
		if(np){													//falls noch eine da war
			VirtualFree(p,0,MEM_RELEASE);						//die aktuelle löschen
			workingPage[allocatorIndex]=np;					//udn die nächste zur aktuellen machen
		}
	}
}

//die hier sollen mal im header stehen, der komplette andere schmonz kann weg in ne *.cpp.
template<size_t SIZE>
inline void* smallalloc()
{
	int const ALLOCATORINDEX=SizeToAllocatorIndex<SIZE>::VALUE;
	int const ALLOCATORSIZE=AllocatorIndexToAllocatorSize<ALLOCATORINDEX>::VALUE;
	return smallalloc(ALLOCATORINDEX,ALLOCATORSIZE);
}
template<size_t SIZE>
inline void smallfree(void* x)
{
	int const ALLOCATORINDEX=SizeToAllocatorIndex<SIZE>::VALUE;
	smallfree(ALLOCATORINDEX,x);
}

//#define TEST

#ifdef TEST

int main()
{
	int MAX=1024*1024*16;
	for(int o=0;o<3;++o)
	{
		int** a=new int*[MAX];
		for(int i=0;i<MAX;++i)
//			a[i]=new int;
			a[i]=(int*)smallalloc<4>();
		for(int j=0;j<MAX;++j)
//			delete a[j];
			smallfree<4>(a[j]);
		delete[] a;
		Sleep(5000);
	}
	return 0;
}
#else

class TestClass 
{ 
private : 
	int number; 

public : 
#ifdef SMALLOBJECTALLOCATOR
	void* operator new(size_t size)
	{
		return smallalloc<sizeof(TestClass)>();
	}
	void operator delete(void* p)
	{
		smallfree<sizeof(TestClass)>(p);
	}
#endif
	TestClass () 
	{ 
	} 

	TestClass (int i) 
		: number (i) 
	{ 
	} 

	~TestClass () 
	{ 
	} 

	int getNumber () 
	{ 
		return number; 
	} 

	void setNumber (int i) 
	{ 
		number = i; 
	} 
};

int main(int argc, char *argv[]) 
{ 
	int size = 500; 
	int sum = 0; 
	clock_t time; 

	TestClass ** array = new TestClass* [size]; 
	int i,j; 

	time = clock(); 
	for (j = 0 ; j < 200000 ; ++j) 
	{ 
		for (i = 0 ; i < size ; ++i) 
		{ 
			array[i] = new TestClass(i); 
		} 
		for (int i = 0 ; i < size ; ++i) 
		{ 
			sum += array[i]->getNumber (); 
			delete array[i]; 
		} 
	} 
	delete [] array; 
	std::cout << clock() - time; 

	system("PAUSE");   
	return 0; 
}
#endif

virtuell Realisticer

Hallo,

dein Code volkard brauch bei mir (BCB 6; Konsolenanwendung) 9534ms.

mfg
v R

VC++ 7.1, compiliert mit 2 Warnungen, Laufzeit 1270ms

virtuell Realisticer

Hallo,

wenn ich auf Release kompiliere, brauch er unterm BCB 6 immernoch 3465ms

mfg
v R

PS: gcc kennt keine windows.h, daher faellt er wohl weg.

class TestClass 
{ 
    private int number; 

    public TestClass () 
    { 
    } 

    public TestClass (int i) 
    { 
    	number = i;
    } 

    public int getNumber () 
    { 
        return number; 
    } 

    public void setNumber (int i) 
    { 
        number = i; 
    } 
}

class Test
{
	public static void main(String[] args)
	{ 
		long time = System.currentTimeMillis();

 	   	int size = 500; 
  	  	int sum = 0; 

 	   	TestClass[] array = new TestClass[size]; 
 	   	int i,j; 

  	   	for (j = 0 ; j < 200000 ; ++j) 
 	   	{ 
 	       	for (i = 0 ; i < size ; ++i) 
    	    { 
        	    array[i] = new TestClass(i); 
        	} 

        	for (i = 0 ; i < size ; ++i) 
        	{ 
          	  	sum += array[i].getNumber (); 
         	} 
    	} 

    	System.gc();
		System.out.println(System.currentTimeMillis() - time);
	}

Ich bin mir nicht sicher, ob das ne gleichwertige Übersetzung ist, braucht bei mir 4900ms.
Und jetzt bau bitte noch ne Array-Indexprüfung ein.

EDIT: Der Unterschied zwischen Debug- (71s) und Release-Version (1,3s) ist gigantisch, dem trau ich nicht so ganz.

volkard

virtuell Realisticer schrieb:

PS: gcc kennt keine windows.h, daher faellt er wohl weg.

wird nur für VirtualAlloc/VirualFree gebraucht. hab leider keine ahnung, wie man sich unter linux ne speicherseite vom BS besorgen tut. muß leider direkt vom BS besorgen, damit die seite auf 4k aligned ist.

volkard

hat auch einer zugleich java und c++ drauf und kann beide zeiten ermitteln?

c++:
2062

java:
7892
24950000000

mathik

MSVC6 release: 1872
java 1.4.2.1: 4977

virtuell Realisticer

volkard schrieb:

virtuell Realisticer schrieb:

PS: gcc kennt keine windows.h, daher faellt er wohl weg.

wird nur für VirtualAlloc/VirualFree gebraucht. hab leider keine ahnung, wie man sich unter linux ne speicherseite vom BS besorgen tut. muß leider direkt vom BS besorgen, damit die seite auf 4k aligned ist.

Hmmm...ich schau mal in meinen schlauen Buechern nach, is schon ne Zeit lang her,
dass ich _so_ nah am BS programmiert hab :).

mfg
v R

virtuell Realisticer

So, ich hab das ganze jetzt ein ganz klein wenig fuer den gcc angepasst.

Ich kann auf meinem System getrost malloc einsetzten, da die Standard-Pagesize
auf meinem System 4096 ist. Zudem hab ich das Ganze so abgeaendert, dass man
auf einem BSD-System die Konstante BSD definieren muss, damit 2 weitere
Dateien includiert werden, der typedef des u32-Typs geaendert, sowie die
VirtualAlloc/VirtualFree durch malloc/free geaendert werden. Bei malloc wird
vom System garantiert, dass der Speicher zur Pagesize hin passend 'aligned'
ist. Da die von dir festgelegte Pagesize genau der auf meinem System
entspricht, gibt es da auch keine Probleme.

Wenn dem nicht so ist, weiss ich auch nicht weiter. Auf BSD-Systemen gibt es,
anscheinend, keine aequivalente Funktion zu VirtualAlloc. Auf Linux-Systemen
kann man sich mittels kmalloc() und kfree() helfen, da man bei diesen
Funktionen die Pagesizegroesse angeben kann.

Naja, jedenfalls braucht das Programm jetzt noch 1313ms.

mfg
v R

SirLant

Volkard's Code VC++ 7.1 1515ms
Optimizer's Code Java 1.4.2 5344ms
Gregor's Code Java 1.4.2 5813ms

Ich hab in den C++ Code noch ne Indexprüfung für den Array-Zugriff eingebaut, das macht aber keinen nennenswerten Unterschied (1270 -> 1500).
Aber ohne den Test in Frage stellen zu wollen: Theoretisch kann die Zahlensumme berechnet werden, ohne die ganzen Objekte wirklich zu erzeugen und zu deleten. Wäre es möglich, dass der C++ Compiler das Ganze einfach rauskickt?

Der Grund: Ich lass mir ja gerne erzählen, dass der Debug-Build 10- oder 20mal langsamer ist. Aber bei einem so trivialem Programm 50mal (!!) langsamer zu sein, kommt mir echt happig vor (etwa 70s Laufzeit).

Gregor

@Optimizer: Initialisier die Summe doch einfach mal mit einem Zufallswert oder mit der aktuellen Zeit oder so und gib sie am Schluss aus. Das sollte doch eigentlich das Problem beheben, wenn es denn wirklich existiert.

@virtuellRealisticer: Was willst du aussagen, wenn du die C++-Werte ohne die Java-Vergleichswerte angibst?

Insgesamt sind die Ergebnisse der neuen C++-Version IMHO glaubhaft und recht gut. Trotzdem bin ich entsetzt, welchen Aufwand man treiben muss, um da entsprechende Performance herauszuholen. IMHO zeigt dieses Beispiel sehr eindrucksvoll, wie nützlich und mächtig ein automatisiertes Speichermanagement ist.

SirLant

Das gleiche habe ich auch gedacht Gregor, wenn man will kann man mit C++ schneller
sein, jedoch muss man dafür einigen Aufwand betreiben, man vergleiche einmal beide
Programme.
Aber D wird ja beides unterstützen, nen GC und wenn man will jederzeit das Management
von Hand

Gregor schrieb:

IMHO zeigt dieses Beispiel sehr eindrucksvoll, wie nützlich und mächtig ein automatisiertes Speichermanagement ist.

Nein, zeigt es IMHO nicht. Denn dazu müsste Volkard jetzt noch einen GC coden, um auf den selben Stand zu kommen (den wir bei dem Java-Programm haben), damit man von automatisiertem Speichermanagement sprechen kann.
Das würde den Code sicher um einiges nochmal größer (und langsamer?) machen. Das war jetzt natürlich nicht das Thema dieses Tests, schon klar.

btw. ne Zufallszahl würde das Problem IMO auch nicht beheben. Ich will jetzt aber nichts unterstellen, vielleicht ist das Programm wirklich so schnell. Mich verwundert es halt zumindest, dass der Unterschied zwischen Debug und Release so gigantisch groß ist.

Gregor

Optimizer schrieb:

Nein, zeigt es IMHO nicht. Denn dazu müsste Volkard jetzt noch einen GC coden, um auf den selben Stand zu kommen (den wir bei dem Java-Programm haben), damit man von automatisiertem Speichermanagement sprechen kann.
Das würde den Code sicher um einiges nochmal größer (und langsamer?) machen. Das war jetzt natürlich nicht das Thema dieses Tests, schon klar.

Die Idee von einem automatisierten Speichermanagement ist ja unter anderem, dass man da nichts selbst "coden" muss.

volkard

..

volkard

Gregor schrieb:

Trotzdem bin ich entsetzt, welchen Aufwand man treiben muss, um da entsprechende Performance herauszuholen.

wieso? waren doch nur 1,5 jährchen.

IMHO zeigt dieses Beispiel sehr eindrucksvoll, wie nützlich und mächtig ein automatisiertes Speichermanagement ist.

nee. es ist erschreckend, daß das normale new/delete vom msvc für kleine objekte so lahm ist. beim oop werden nunmal richtig viele kleine objekte mit new angelegt. dem sollte die implementierung von new stärkstens rechnung tragen, hat sie aber nicht.