Du bist nicht angemeldet.

Werbeanzeige

21

16.09.2008, 14:16

Ich habe es auch hingekriegt!
NO RISK NO FUN

Helmut

5x Contest-Sieger

Beiträge: 691

Wohnort: Bielefeld

  • Private Nachricht senden

22

16.09.2008, 16:36

Hi,
also ich muss schon sagen, dass ich erstaunt bin, wie viele Algos einem zu sowas einfallen. Allerdings habe ich ein kleines Problem. Und zwar würde ich gerne meine memset Funktion etwas optimieren:

C-/C++-Quelltext

1
2
3
4
5
void my_memset(uint* dest, uint value, uint size)
{
    for(uint i = 0; i != size; i++)
        *dest++ = value;
}


Zwar optimiert das mein VS Compiler ganz gut in prakisch nur eine Instruction (rep stosd), allerdings soll das aus Gründen, die ich nicht verstehe, langsamer sein, als wenn man SSE oder Ähnliches benutzt.
Kennt jemand zufällig so eine Funktion? Die benutzt übrigens 32Bit Werte, statt 8Bit im originalem memset. Ich kann leider nicht wirklich Assembler..

Ciao
Sei stets geduldig gegenüber Leuten, die nicht mit dir übereinstimmen. Sie haben ein Recht auf ihren Standpunkt - trotz ihrer lächerlichen Meinung. (F. Hollaender)

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 184

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

23

16.09.2008, 16:55

@Helmut:
memset ist normalerweise schon sehr gut optimiert. Auch wenn du da nur einen 8-Bit-Wert angibst, heißt das ja nicht, dass er intern nicht 32-Bit-Werte schreibt. Das tut er mit ziemlicher Sicherheit. Wahrscheinlich benutzt er auch SSE.
Ich habe übrigens versucht, mit SSE was zu machen, aber das war auch langsamer als memset. Also hier würde ich erstmal nicht versuchen zu optimieren.

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 184

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

24

17.09.2008, 11:48

Hier mal ein Zwischenergebnis.
Anzumerken ist, dass dies mein Ansatz für große Anzahlen von Rechtecken ist. Für wenige muss ich mir noch was Anderes einfallen lassen, was dann schneller ist.

Quellcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
image_size  num_rectangles  OK?   Zeit (ms)     Referenzzeit (ms)  Speed-up
-----------------------------------------------------------------------------
128         1000            Ja    0.236463      0.422654           1.7874
128         10000           Ja    0.257632      2.62254            10.1794
128         100000          Ja    0.398327      25.075             62.9508
128         1000000         Ja    0.313725      199.455            635.761
256         1000            Ja    0.767165      4.10656            5.3529
256         10000           Ja    0.821018      24.1446            29.4081
256         100000          Ja    0.855066      274.875            321.466
256         1000000         Ja    0.79713       2402               3013.31
512         1000            Ja    4.03831       29.8382            7.3888
512         10000           Ja    3.96436       179.667            45.3205
512         100000          Ja    3.76648       1578               418.959
512         1000000         Ja    4.07332       29882              7336.03
1024        1000            Ja    17            775                45.5882
1024        10000           Ja    19.4854       3390               173.976
1024        100000          Ja    17.1624       42371              2468.83
1024        1000000         Ja    18.0901       727705             40226.7


Hat noch jemand was zu zeigen? :)

Asmodiel

Treue Seele

Beiträge: 150

Wohnort: Schweiz

Beruf: Applikationsentwickler

  • Private Nachricht senden

25

17.09.2008, 14:31

Wtf... Freak! xD
Gibt's eigentlich ne Seite mit guten Performance Tips?

Helmut

5x Contest-Sieger

Beiträge: 691

Wohnort: Bielefeld

  • Private Nachricht senden

26

17.09.2008, 16:48

Zitat von »"David Scherfgen"«

@Helmut:
memset ist normalerweise schon sehr gut optimiert. Auch wenn du da nur einen 8-Bit-Wert angibst, heißt das ja nicht, dass er intern nicht 32-Bit-Werte schreibt. Das tut er mit ziemlicher Sicherheit. Wahrscheinlich benutzt er auch SSE.
Ich habe übrigens versucht, mit SSE was zu machen, aber das war auch langsamer als memset. Also hier würde ich erstmal nicht versuchen zu optimieren.

Ja, in die memset und memcpy Implementierungen von MS hab ich schon reingeschaut. memset benutzt SSE leider nur, wenn der Puffer genullt wird und abgesehen davon wäre ich auch zu doof, das irgendwie an den gcc zu verfüttern..
Aber bei deinen Geschwindigkeiten kann ich eh gleich einpacken... Hier meine (3 verschiedene Algos):

Quellcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
image_size  num_rectangles  OK?   Zeit (ms)     Referenzzeit (ms)  Speed-up
-----------------------------------------------------------------------------
128         1000            Ja    0.211477      0.731529           3.45913
128         10000           Ja    1.44863       4.62356            3.19169
128         100000          Ja    14.4604       40.86              2.82564
128         1000000         Ja    17.4          325.571            18.711
256         1000            Ja    0.491525      2.45521            4.99509
256         10000           Ja    3.20833       16.048             5.00197
256         100000          Ja    36.7091       185.545            5.05448
256         1000000         Ja    19.9604       1604               80.3591
512         1000            Ja    1.25455       7.56604            6.0309
512         10000           Ja    10.738        63.4375            5.90778
512         100000          Ja    93            522.25             5.61559
512         1000000         Ja    125.313       8267               65.9711
1024        1000            Ja    17.6228       260                14.7536
1024        10000           Ja    64.1875       781.333            12.1727
1024        100000          Ja    789.333       7960               10.0845
1024        1000000         Ja    1497          151860             101.443


Was mich wundert ist, dass sich die Zeiten der Referenz so stark unterscheiden. Du hast doch die unveränderte Referenzimplementierung mit gcc im Releasemodus kompiliert?

Ciao
Sei stets geduldig gegenüber Leuten, die nicht mit dir übereinstimmen. Sie haben ein Recht auf ihren Standpunkt - trotz ihrer lächerlichen Meinung. (F. Hollaender)

Crush

Alter Hase

Beiträge: 384

Wohnort: Stuttgart

Beruf: Softwareentwickler

  • Private Nachricht senden

27

17.09.2008, 21:10

@David Scherfgen

Hier mein Ansatz für kleine Rechecke...
In den ersten 8 Tests schlag ich Dich wenigstens schon mal - und ich hab sicher noch etwas Luft zu weiteren Optimierungen (was ja auch Deine Ergebnisse zeigen). Jetzt kann ich mich auch an den Ansatz für große Rechtecke machen :lol:

Bis jetzt sieht´s so aus, als ob ein Mix aus unseren beiden Varianten optimal wäre :D

Wollen wir beim Wettbewerb als Team zusammen arbeiten? (hehe)
Hast Du Assembler verwendet? Ich bis jetzt noch nicht.
Der Einbruch bei 1024x10000 ist mir unerklärlich...

Quellcode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
image_size  num_rectangles  OK?   Zeit (ms)     Referenzzeit (ms)  Speed-up  

128         1000            Ja    0.0683761     0.577534           8.44643   
128         10000           Ja    0.0921871     3.39559            36.8336   
128         100000          Ja    0.122888      30.5606            248.687   
128         1000000         Ja    0.106781      249.222            2333.97   
256         1000            Ja    0.305857      1.99501            6.5227    
256         10000           Ja    0.172846      13.039             75.4369   
256         100000          Ja    0.280466      137.067            488.711   
256         1000000         Ja    0.374042      1235.5             3303.11   
512         1000            Ja    0.838926      5.6338             6.71549   
512         10000           Ja    2.67156       44.3696            16.6081   
512         100000          Ja    1.17716       364.333            309.501   
512         1000000         Ja    1.49254       6296               4218.32   
1024        1000            Ja    4.01807       47.3256            11.7782   
1024        10000           Ja    37.1296       198.182            5.33757   
1024        100000          Ja    5.52762       2441               441.6     
1024        1000000         Ja    3.56684       40779              11432.8

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 184

Wohnort: Bonn

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

28

17.09.2008, 22:11

@Crush:

Wow, super.
Aber etwas verwundert mich.
Warum braucht bei dir die Referenzfunktion für den letzten Fall nur so wenig Zeit?
Bei dir braucht sie 40 Sekunden, bei mir über 10 Minuten!

Crush

Alter Hase

Beiträge: 384

Wohnort: Stuttgart

Beruf: Softwareentwickler

  • Private Nachricht senden

29

17.09.2008, 22:36

Das mit der Referenzzeit ist schon mysteriös. Allerdings scheint das Problem bei Dir zu liegen. Beim Helmut & Asmodiel sieht´s ja auch eher aus wie bei mir.

Zitat Helmut:

Zitat

Was mich wundert ist, dass sich die Zeiten der Referenz so stark unterscheiden. Du hast doch die unveränderte Referenzimplementierung mit gcc im Releasemodus kompiliert?

-> mal nachgeschaut?

Vermutlich ist bei Dir etwas verbogen. Probier mal Deinen Code ins aktuelle Projekt einzufügen. Evtl. sind meine Compiler-Settings auch besser als Deine?

Vielleicht hab ich auch nur ein geniales Laptop und hab´s noch gar nicht mitbekommen ;)

Powerpaule

Treue Seele

Beiträge: 162

Wohnort: Berlin

Beruf: Softwareentwickler

  • Private Nachricht senden

30

17.09.2008, 22:43

hmm, na ja, bei mir ist die Referenzlösung im 1. Fall schneller als bei dir (Crush), und dann nachher bedeutend langsamer... ich brauch endlich 'nen neuen Rechner! xD

Werbeanzeige