Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

C++ Library Extension

Werbeanzeige

LukasBanana

Alter Hase

  • »LukasBanana« ist der Autor dieses Themas

Beiträge: 1 097

Beruf: Shader Tools Programmer

  • Private Nachricht senden

21

04.07.2014, 16:22

Ok, ich hab jetzt mit Release with Debug Info kompiliert.

Hier der C++ Code:

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#ifdef _MSC_VER
#   define NOINLINE __declspec(noinline) 
#else
#   define NOINLINE
#endif

typedef int ClassicArray[10][10][10];
typedef multi_array<int, 10, 10, 10> LukasArray;

NOINLINE int Get(const ClassicArray& a, size_t x, size_t y, size_t z)
{
    return a[x][y][z];
}

NOINLINE int Get(const LukasArray& a, size_t x, size_t y, size_t z)
{
    return a[x][y][z];
}


Hier die "Get" Funktion für "ClassicArray":

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

NOINLINE int Get(const ClassicArray& a, size_t x, size_t y, size_t z)
{
009F3DC0  push        ebp  
009F3DC1  mov         ebp,esp  
    return a[x][y][z];
009F3DC3  mov         eax,dword ptr [x]  
009F3DC6  lea         ecx,[eax+eax*4]  
009F3DC9  mov         eax,dword ptr [y]  
009F3DCC  lea         eax,[eax+ecx*2]  
009F3DCF  lea         ecx,[eax+eax*4]  
009F3DD2  mov         eax,dword ptr [z]  
009F3DD5  lea         ecx,[eax+ecx*2]  
009F3DD8  mov         eax,dword ptr [a]  
009F3DDB  mov         eax,dword ptr [eax+ecx*4]  
}
009F3DDE  pop         ebp  
009F3DDF  ret


Und hier für "LukasArray":

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

NOINLINE int Get(const LukasArray& a, size_t x, size_t y, size_t z)
{
009F3DF0  push        ebp  
009F3DF1  mov         ebp,esp  
    return a[x][y][z];
009F3DF3  mov         eax,dword ptr [x]  
009F3DF6  lea         ecx,[eax+eax*4]  
009F3DF9  mov         eax,dword ptr [y]  
009F3DFC  lea         eax,[eax+ecx*2]  
009F3DFF  lea         ecx,[eax+eax*4]  
009F3E02  mov         eax,dword ptr [z]  
009F3E05  lea         ecx,[eax+ecx*2]  
009F3E08  mov         eax,dword ptr [a]  
009F3E0B  mov         eax,dword ptr [eax+ecx*4]  
}
009F3E0E  pop         ebp  
009F3E0F  ret


Scheint ein gutes Ergebnis zu sein :D

In der Debug Version sieht das schon ganz anders aus:

Quellcode

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

NOINLINE int Get(const ClassicArray& a, size_t x, size_t y, size_t z)
{
00322610  push        ebp  
00322611  mov         ebp,esp  
    return a[x][y][z];
00322613  imul        eax,dword ptr [x],190h  
0032261A  add         eax,dword ptr [a]  
0032261D  imul        ecx,dword ptr [y],28h  
00322621  add         eax,ecx  
00322623  mov         edx,dword ptr [z]  
00322626  mov         eax,dword ptr [eax+edx*4]  
}
00322629  pop         ebp  
0032262A  ret  

; ...

NOINLINE int Get(const LukasArray& a, size_t x, size_t y, size_t z)
{
00322630  push        ebp  
00322631  mov         ebp,esp  
00322633  sub         esp,8  
00322636  mov         dword ptr [ebp-8],0CCCCCCCCh  
0032263D  mov         dword ptr [ebp-4],0CCCCCCCCh  
    return a[x][y][z];
00322644  lea         eax,[z]  
00322647  push        eax  
00322648  lea         ecx,[y]  
0032264B  push        ecx  
0032264C  lea         edx,[ebp-8]  
0032264F  push        edx  
00322650  lea         eax,[x]  
00322653  push        eax  
00322654  lea         ecx,[ebp-4]  
00322657  push        ecx  
00322658  mov         ecx,dword ptr [a]  
0032265B  call        multi_array<int,10,10,10>::operator[] (0321406h)  
00322660  mov         ecx,eax  
00322662  call        multi_array<int,10,10,10>::const_slice<10,10,10>::operator[] (032140Bh)  
00322667  mov         ecx,eax  
00322669  call        multi_array<int,10,10,10>::const_slice<10,10>::operator[] (032141Ah)  
0032266E  mov         eax,dword ptr [eax]  
}
00322670  add         esp,8  
00322673  cmp         ebp,esp  
00322675  call        _RTC_CheckEsp (0328F90h)  
0032267A  mov         esp,ebp  
0032267C  pop         ebp  
0032267D  ret
Mein YouTube Channel
Mein Twitter Profil
Meine Projekte auf github.com
Meine Projekte auf bitbucket.org

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

22

04.07.2014, 16:32

Super! :)
Wie gut, dass die Compiler heute so schlau sind.
David Scherfgens Website | Konzentrationstest Polizei

LukasBanana

Alter Hase

  • »LukasBanana« ist der Autor dieses Themas

Beiträge: 1 097

Beruf: Shader Tools Programmer

  • Private Nachricht senden

23

24.09.2014, 00:59

Ich habe eben mal mit einer neuen Klasse für meine kleine C++ Erweiterung angefangen:

range_iterator

Damit man nicht immer den Iterator, begin() und end() an Funktionen übergeben muss, wenn man alle drei braucht.
Mir ist das heute beim Parsen der "main" Argumente zu Gute gekommen ( d.h. zum Parsen von 'int main(int argc, char* argv[])' ).

Die Klasse hat ähnliche Funktionen wie die "Iterator" Klasse in Java (z.B. "has_next").
Mein YouTube Channel
Mein Twitter Profil
Meine Projekte auf github.com
Meine Projekte auf bitbucket.org

LukasBanana

Alter Hase

  • »LukasBanana« ist der Autor dieses Themas

Beiträge: 1 097

Beruf: Shader Tools Programmer

  • Private Nachricht senden

24

19.10.2014, 15:42

Ich habe eben mal schnell mit einer neuen Klasse angefangen:

packed_vector

Problemstellung:
Dank des templatisierten "std::vector" kann man Listen eines einzelnen Typs kompakt im Speicher verwalten, was der Cache-Lokalität sehr gut zuträglich ist.

In diesem Bsp. hat man einen großen, zusammenhängenden Speicherblock:

C-/C++-Quelltext

 
1
2
3
4
5

struct widget
{
    /* big data here ... */
};
std::vector<widget> container(1000);


Hier hat man einen großen, verteilten Speicherblock:

C-/C++-Quelltext

 
1
2

struct widget { /* like above */ };
std::vector<std::unique_ptr<widget>> container(1000);


Wenn aber nun "widget" eine Basisklasse ist, und wir abgeleitete Klassen in unserem "container" speichern wollen, kommen wir wohl um den pointer nicht umhin.

Lösungsvorschlag:
Meine Klasse "packed_vector<Base>" verwaltet einen "std::vector<char>", also einen byte-aligned raw-buffer.
Alle Elemente in diesem Container sind entweder vom Typ 'Base' oder einer abgeleiteten Klasse 'Target'.
Das sieht dann z.B. so aus:

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

struct A
{
    virtual ~A()
    {
    }
    int x = 1;
};
struct B : public A
{
    int y = 2;
};
struct C
{
    int z = 3;
};

packed_vector<A> container;

// Add elements
container.push_back(A());
container.push_back(B());

// Access these elements
auto a = container.get<A>(0);
auto b = container.get<B>(1);
auto b_as_a = container.get<A>(1);
auto c = container.get<C>(1); // ERROR (static_assert) -> 'C' is not a base of 'A' (std::is_base_of), ERROR -> 2nd element is of type 'B' and 'C'

In der Funktion "get" wird mit "dynamic_cast" der jeweilige Typ geliefert.
Bei der Speicherverwaltung des raw buffers wird in "push_back" das gesamte Element, inklusive RTTI Daten, kopiert.

Fazit:
Das ist natürlich eine Art 'bit-level-hacking' und dazu müsste man sich noch mal die C++ Spec. genauer anschauen, ob das auch sicher ist.
Funktioniert auf jeden Fall schon mal sehr gut und ist denke ich eine gute Lösung, wenn man viele kleine Klassen in einem Container hat, die von der selben Basis Klasse erben.

Gruß,
Lukas
Mein YouTube Channel
Mein Twitter Profil
Meine Projekte auf github.com
Meine Projekte auf bitbucket.org

Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von »LukasBanana« (19.10.2014, 15:54)

Steef

Alter Hase

Beiträge: 492

  • Private Nachricht senden

25

19.10.2014, 16:48

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#include <iostream>
#include "packed.hpp"

struct BaseA
{
    virtual ~BaseA() {};
    
    int ba_x;
};

struct BaseB
{
    virtual ~BaseB() {};
    
    int bb_x;
};

struct DerivedB : public BaseB, public BaseA
{
    int db_x;
};

int main()
{
    ext::packed_vector<BaseA> list;
    list.push_back(DerivedB());
    
    DerivedB derived;
    BaseA* ptr = &derived;


    DerivedB* ptr2 = dynamic_cast<DerivedB*>(ptr);
    if (!ptr2)
    {
        std::cerr << "Error: ptr2 == nulltpr\n";
    }
    else if (ptr2 != &derived)
    {
        std::cerr << "Error: ptr wrong value\n";
    }
    
    DerivedB* ptr3 = list.get_ptr<DerivedB>(0);
    if (!ptr3)
    {
        std::cerr << "Error: ptr3 == nulltpr\n";
    }
}

Quellcode

 
1
2

~ % clang++ -std=c++11 -g test_multi2.cpp && ./a.out
Error: ptr3 == nulltpr
"Theory is when you know something, but it doesn’t work. Practice is when something works, but you don’t know why. Programmers combine theory and practice: Nothing works and they don’t know why." - Anon

LukasBanana

Alter Hase

  • »LukasBanana« ist der Autor dieses Themas

Beiträge: 1 097

Beruf: Shader Tools Programmer

  • Private Nachricht senden

26

19.10.2014, 17:28

Danke für dein Code Beispiel.

Es funktioniert allerdings, wenn du als Basis Klasse die angibst, von der du bei deiner abgeleiteten Klasse als erstes erbst.
Probier das hier mal:

C-/C++-Quelltext

 
1
2
3
4
5
6
7

packed_vector<BaseA> list;

// Vorher:
struct DerivedB : public BaseB, public BaseA

// Nachher:
struct DerivedB : public BaseA, public BaseB

Andernfalls funktioniert der dynamic_cast von "BaseA" zu "DerivedB" nicht.
Mein YouTube Channel
Mein Twitter Profil
Meine Projekte auf github.com
Meine Projekte auf bitbucket.org

Steef

Alter Hase

Beiträge: 492

  • Private Nachricht senden

27

19.10.2014, 18:07

Wenn man die Klassen umdreht funktioniert es, allerdings ist das nicht der Sinn der Sache.
Das Beispiel zeigt nämlich die Voraussetzung für deinen Code, die du implizit annimmst:

C-/C++-Quelltext

 
1
2

Derived d; // Basisklasse: Base
(void*)&d == (void*)((Base*)&d);

Dies geht bei mehreren Basisklassen selbstverständlich in die Hose. Das Problem ist allerdings, dass diese Bedingung nicht einmal bei nur einer Basisklasse stimmen muss:

Zitat von »"C++ Standard: §10 Abs 5"«

The order in which the base class subobjects are allocated in the most derived object is unspecified.

Es können also sehr gut erst die abgeleiteten Member im Speicher kommen und dann die der Basisklasse.
"Theory is when you know something, but it doesn’t work. Practice is when something works, but you don’t know why. Programmers combine theory and practice: Nothing works and they don’t know why." - Anon

Spiele Programmierer

Alter Hase

Beiträge: 1 223

Wohnort: Deutschland Bayern

Beruf: Schüler

  • Private Nachricht senden

28

19.10.2014, 18:16

Hast du mal realistische Benchmarks dazu gemacht?
Klingt für mich nicht unbedingt deutlich effizienter als die alte Variante. Außerdem sehe ich gerade nicht, warum "dynamic_cast" notwendig ist und das ist eigentlich eine relativ berüchtigte Performancebremse. Nicht ohne Grund ist RTTI auch gelegentlich komplett deaktiviert. Außerdem behebt die Klasse nicht das grundlegende Problem mit OO bei der Performance: Zusätzliche Indirektion und schlechtere Cache-Lokalität. Im vermute, dass es es wahrscheinlich im wesentlichen höchstens die Allokation optimiert. Die Idee ist aber interessant.

LukasBanana

Alter Hase

  • »LukasBanana« ist der Autor dieses Themas

Beiträge: 1 097

Beruf: Shader Tools Programmer

  • Private Nachricht senden

29

19.10.2014, 18:32

Zitat von »Spiele Programmierer«

Hast du mal realistische Benchmarks dazu gemacht?
Klingt für mich nicht unbedingt deutlich effizienter als die alte Variante.

Versuche ich noch zu machen, aber ich habe heute erst mit der Klasse angefangen.
Tatsache ist, dass die Cache Lokalität sehr stark durch die Wahl der Container beeinflusst werden kann.
Herb Sutter hat dazu in einigen Vorträgen genaueres erzählt. Dieser Dev Talk (so ab min. 26) ist zu diesem Thema auch recht interessant ;-)
Daher denke ich, dass das eine ganze Menge ausmachen kann.

Zitat von »Steef«


Zitat von »"C++ Standard: §10 Abs 5"«

The order in which the base class subobjects are allocated in the most derived object is unspecified.

Es können also sehr gut erst die abgeleiteten Member im Speicher kommen und dann die der Basisklasse.

Das ist in der Tat ein Problem. Vielleicht lässt sich das aber auch irgendwie lösen.
Möglicher Weise mit Compiler spezifischen queries; ich denke da an so was in der Art:

C-/C++-Quelltext

 
1
2
3
4
5

#if defined(_MSC_VER)
__msvc_compiler_specific_keyword_about_polymorphic_storage_management(...)
#elif defined(GNUC)
...
#endif

Wie gesagt, es ist momentan noch bit-level hacking, aber letzten Endes müssen ja irgendwo die RTTI Daten gespeichert werden.
Und warum sollte es nicht möglich sein, den Compiler abzufragen, wie er diese Daten verwaltet.
Mein YouTube Channel
Mein Twitter Profil
Meine Projekte auf github.com
Meine Projekte auf bitbucket.org

Steef

Alter Hase

Beiträge: 492

  • Private Nachricht senden

30

19.10.2014, 19:30

Du könntest dir einen Offset merken und daraus den richtigen Base-Pointer rekonstruieren (siehe Anhang).

Allerdings hat deine Datenstruktur noch deutlich größere Probleme bei bestimmten Inhalten.
Beispiel:

C-/C++-Quelltext

 
1
2
3
4

struct S
{
     std::unique_ptr<int> i;
}

i wird freigegeben, wenn das Objekt, das du an push_back übergibst, zerstört wird. Dein Vector enthält dann aber immer noch den (jetzt ungültigen) Zeiger. Desweiteren wird für Elemente in deiner Struktur niemals ein Destruktor aufgerufen.
»Steef« hat folgende Datei angehängt:
  • packed.hpp (5,12 kB - 53 mal heruntergeladen - zuletzt: 01.04.2024, 04:47)
"Theory is when you know something, but it doesn’t work. Practice is when something works, but you don’t know why. Programmers combine theory and practice: Nothing works and they don’t know why." - Anon

Werbeanzeige

Ähnliche Themen