Du bist nicht angemeldet.

Werbeanzeige

Powerpaule

Treue Seele

Beiträge: 162

Wohnort: Berlin

Beruf: Softwareentwickler

  • Private Nachricht senden

41

18.09.2008, 22:55

Hm so gefällts mir schon etwas besser :)

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.159921      0.305316           1.90917
128         10000           Ja    0.176835      1.92919            10.9096
128         100000          Ja    0.614251      19.6078            31.9216
128         1000000         Ja    0.439754      163.462            371.712
256         1000            Ja    0.947867      5.46448            5.76503
256         10000           Ja    0.343289      31.9841            93.1698
256         100000          Ja    1.1236        359.333            319.807
256         1000000         Ja    1.07991       3141               2908.57
512         1000            Ja    8.29876       130.875            15.7704
512         10000           Ja    27.08         974                35.9675
512         100000          Ja    34.1695       7672               224.528
512         1000000         Ja    17.2414       134593             7806.39
1024        1000            Ja    16.5289       1304.5             78.9222
1024        10000           Ja    198.909       5594               28.1234
1024        100000          Ja    108.526       72953              672.215
1024        1000000         Ja    21.6667

42

19.09.2008, 11:05

Man ist übrigens schon 2-4 mal schneller als die Referenz, wenn man die Referenz kopiert und nur die Reihenfolge der For-Schleifen-Verschachtelungen am Ende austauscht. ;)

David Scherfgen

Administrator

  • »David Scherfgen« ist der Autor dieses Themas

Beiträge: 10 334

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

43

19.09.2008, 13:03

Richtig, das war Absicht :)

Asmodiel

Treue Seele

Beiträge: 150

Wohnort: Schweiz

Beruf: Applikationsentwickler

  • Private Nachricht senden

44

20.09.2008, 00:29

Wieso denn das? Ich erkenne da keinen grossen Unterschied ^^"

Crush

Alter Hase

Beiträge: 384

Wohnort: Stuttgart

Beruf: Softwareentwickler

  • Private Nachricht senden

45

20.09.2008, 17:58

@Gaspode: Heißt Deine Vermutung mit dem Cache, daß ich gute Chancen habe, bessere Werte auf anderen Testrechnern zu erreichen? Wenn der Referenzalgo dann 10x langsamer wäre, wäre mein Speed-up-Ergebnis vermutlich deutlich schneller. Das macht mir wieder Hoffnung!

Kleiner Zwischenstand mit verbessertem Algo1 (für wenig Rechtecke ;))

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.0455032     0.549122           12.0678   
128         10000           Ja    0.0868659     3.30909            38.0943   
128         100000          Ja    0.11334       29.6029            261.187   
128         1000000         Ja    0.0881213     238.111            2702.08   
256         1000            Ja    0.141153      1.94175            13.7563   
256         10000           Ja    0.118273      12.0482            101.867   
256         100000          Ja    0.135575      133.4              983.958   
256         1000000         Ja    0.134436      1165               8665.85   
512         1000            Ja    0.413309      5.44837            13.1823   
512         10000           Ja    0.621311      43.8043            70.5031   
512         100000          Ja    0.491884      353.667            719.004   
512         1000000         Ja    0.517331      6081               11754.6   
1024        1000            Ja    2.09748       42.766             20.3892   
1024        10000           Ja    3.80952       176.917            46.4406   
1024        100000          Ja    2.14133       2234               1043.28   
1024        1000000         Ja    1.82315       39045              21416.2

Mordrak

1x Contest-Sieger

Beiträge: 121

Wohnort: München

Beruf: Junior IT Consultant

  • Private Nachricht senden

46

20.09.2008, 21:44

Was mich an der ganzen Sache so schockt ist der Overhead, der durch zusaetzliche Speicherreservierung zustande kommt. Ich habe testweise mal in meiner Funktion lediglich ein new und delete (bzw. die util.cpp Funktionen) verwendet und danach sofort return... Unglaublich wie das bremst....

Gruebelnd,
Mordrak
What's yellow and equivalent to the axiom of choice? The Lemmon of Zorn!

Crush

Alter Hase

Beiträge: 384

Wohnort: Stuttgart

Beruf: Softwareentwickler

  • Private Nachricht senden

47

20.09.2008, 23:09

Also ich reserviere hier Speicher wie der Hirsch und fülle den mit allem möglichen Zeugs. Die Performance-Verluste kommen aber bei mir lustigerweise aus ganz anderen Ecken her.

Crush

Alter Hase

Beiträge: 384

Wohnort: Stuttgart

Beruf: Softwareentwickler

  • Private Nachricht senden

48

21.09.2008, 00:37

Aha, wie ich´s mir gedacht habe.
Je besser der Rechner ist, desto schlechter scheinen die Ergebnisse zu sein. Ich habe gerade mal meine vorher gepostete Version auf meinem zweiten Laptop mit Pentium4 3.2 Ghz laufen lassen und plötzlich sehen meine Werte doch schon viel besser aus - so passen auch die Referenzzeiten besser:

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.0649098     0.893655           13.7676   
128         10000           Ja    0.118008      5.03778            42.6902   
128         100000          Ja    0.152195      50.4               331.153   
128         1000000         Ja    0.122526      390.667            3188.43   
256         1000            Ja    0.204269      2.52845            12.378    
256         10000           Ja    0.173913      15.625             89.8438   
256         100000          Ja    0.195829      173.167            884.276   
256         1000000         Ja    0.184145      1516               8232.64   
512         1000            Ja    2.36686       105.263            44.4737   
512         10000           Ja    2.32829       613.25             263.391   
512         100000          Ja    1.83655       5703               3105.28   
512         1000000         Ja    2.36686       99266              41939.9   
1024        1000            Ja    8.65801       755.333            87.241    
1024        10000           Ja    11.8343       3266               275.977   
1024        100000          Ja    8.96861       41953              4677.76   
1024        1000000         Ja    8.54701       714812             83633

Gaspode

1x Contest-Sieger

  • Private Nachricht senden

49

21.09.2008, 02:40

Crush: Natürlich wird das Speed-Up grösser, wenn du das auf nem langsameren Rechner ausführst. Bei der Bewertung gehts aber um die Rechenzeit der Algorithmen auf den Testrechnern. Wenn die Referenz da langsamer läuft, wird das natürlich ziemlich sicher auch für deinen Algorithmus gelten.
Anhand der Referenzzeiten kannst du natürlich ungefähr schliessen, wie schnell dein Algorithmus auf dem anderen Rechner ist, und so schätzen, wo du momentan liegst.
Den Speed-Up benutze ich nur, um verschiedene Algorithmen direkt auf meinem Rechner miteinander zu vergleichen.

Hier mal zum Vergleich der Algorithmus, zu dem ich schonmal die Werte gepostet habe, auf meinem Laptop, Pentium M 1.4 GHz.

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.449741      2.33918            5.20117
128         10000           Ja    0.748503      14.014             18.7227
128         100000          Ja    1.85106       123.706            66.8296
128         1000000         Ja    0.793103      1016               1281.04
256         1000            Ja    0.490677      8.76419            17.8614
256         10000           Ja    0.432339      52.7632            122.041
256         100000          Ja    1.01678       619.5              609.278
256         1000000         Ja    0.421974      5348               12673.8
512         1000            Ja    2.98806       64.5161            21.5913
512         10000           Ja    2.55032       415.2              162.803
512         100000          Ja    2.82228       3734               1323.04
512         1000000         Ja    2.90843       64937              22327.2
1024        1000            Ja    11.7824       1120               95.0574
1024        10000           Ja    14.5797       4243               291.021
1024        100000          Ja    14.9552       53255              3560.96
1024        1000000         Ja    13.7329       930050             67724.3

Hab den nochmal erheblich verbessern können, hab nur keinen aktuellen Vergleich mit der Referenz.
Da die Referenz bei mir noch ein bisschen langsamer ist als bei dir, dürften wir etwa gleichauf liegen.

Bei den Geschwindigkeitsoptimierungen sind mir übrigens ein paar verrückte Sachen aufgefallen, die ich nach der Deadline mal hier posten werde.

Crush

Alter Hase

Beiträge: 384

Wohnort: Stuttgart

Beruf: Softwareentwickler

  • Private Nachricht senden

50

21.09.2008, 11:51

... also wird nachher der Benchmark trotz allem was so gepostet wird sicherlich immer noch sehr spannend bleiben :!:

Werbeanzeige