Eine Woche Programmierwettbewerb: Rechtecke

[Ponto]

Zur Erinnerung. Heute um 18 Uhr ist Einsendeschluss.

Sobald ich zurück bin, werde ich mich an die Auswertung machen.

[TomasRiker]

Ich habe dir meine Lösung jetzt zugeschickt.
Bitte sag mir bescheid, dass sie angekommen ist

[Ponto]

Hallo,

ich habe 4 Einsendungen erhalten:

otze
Jens
TomasRiker
camper

Ich werde mich morgen an die Auswertung setzen.

[Badestrand]

Ach verflucht, ich hab irgendeinen doofen Fehler nicht rausgekriegt

[rapso]

Badestrand schrieb:

Ach verflucht, ich hab irgendeinen doofen Fehler nicht rausgekriegt

und mir klang das ein wenig spanish von den anforderungen her, als ob jemand gratis die optimierungsarbeit von anderen sehen moechte *hehe*

[Ponto]

rapso schrieb:

Badestrand schrieb:

Ach verflucht, ich hab irgendeinen doofen Fehler nicht rausgekriegt

und mir klang das ein wenig spanish von den anforderungen her, als ob jemand gratis die optimierungsarbeit von anderen sehen moechte *hehe*

Wenn du nicht völlig realitätsfremde Probleme sehen möchtest, hast du diese Gefahr immer. Dass du mir nicht vertraust, dass es hier nur um den Wettbewerb geht, kann ich verstehen. Warum sollte man das auch tun.

[Ponto]

Ich suche übrigends Ideen für einen folgenden Programmierwettbewerb. Wenn jemand eine interessante Problemstellung hat, kann er sich an die obige Adresse melden.

[jenz]

@rapso:

ich hatte ja mal wegen der threads nachgefragt.
warum meinst du, dass das "random" ist?
ich finde, dass sich das problem recht gut parallelisieren ließe.
einfach die plane aufteilen und wenn ein thread dann schneller fertig ist, als andere, dann bekommt er einen teil von dessen plane.

würde in mein verfahren recht gut reinpassen.

ich verstehe nicht, was daran dann nicht von vorteil sein sollte, natürlich nur bei mehreren kernen/prozessoren, aber das kann man im rahmen der optimierung ja anpassen.

@ponto:
optimieren auf mehrere threads/prozessoren vielleicht?

jenz

[Ponto]

jenz schrieb:

@ponto:
optimieren auf mehrere threads/prozessoren vielleicht?

jenz

Dazu bräuchte man aber auch eine andere Aufgabe.

[rapso]

Ponto schrieb:

rapso schrieb:

Badestrand schrieb:

Ach verflucht, ich hab irgendeinen doofen Fehler nicht rausgekriegt

und mir klang das ein wenig spanish von den anforderungen her, als ob jemand gratis die optimierungsarbeit von anderen sehen moechte *hehe*

Wenn du nicht völlig realitätsfremde Probleme sehen möchtest, hast du diese Gefahr immer. Dass du mir nicht vertraust, dass es hier nur um den Wettbewerb geht, kann ich verstehen. Warum sollte man das auch tun.

tja, am ende hast du selbst zugegeben dass du das nutzen moechtest (nutzen!=copy&paste), andere zahlen mir mein gehalt damit ich sowas fluessig auf dem schirm zaubere, da kann ich das ja nicht gratis hier machen (zumal das mein arbeitsvertrag auch verbietet, wie vielleicht von einigen anderen auch).

[rapso]

jenz schrieb:

@rapso:

ich hatte ja mal wegen der threads nachgefragt.
warum meinst du, dass das "random" ist?
ich finde, dass sich das problem recht gut parallelisieren ließe.
einfach die plane aufteilen und wenn ein thread dann schneller fertig ist, als andere, dann bekommt er einen teil von dessen plane.

würde in mein verfahren recht gut reinpassen.

ich verstehe nicht, was daran dann nicht von vorteil sein sollte, natürlich nur bei mehreren kernen/prozessoren, aber das kann man im rahmen der optimierung ja anpassen.

multithreading haengt oft stark von der architektur ab auf der es laeuft, manchmal kannst du cachetrasching produzieren die deine 4threads langsammer als einen machen, manchmal kann genau der selbe code fast 4mal schneller laufen, wenn man da nicht sehr genau weiss was man macht und auf welcher maschine koennen die resultate random sein.
natuerlich hat man im schnitt wenn alle hier teilnehmen ne bessere geschwindigkeit, aber es kann gut sein dass auf einer anderen maschine der letzte der erste wird.

[Ponto]

tja, am ende hast du selbst zugegeben dass du das nutzen moechtest (nutzen!=copy&paste), andere zahlen mir mein gehalt damit ich sowas fluessig auf dem schirm zaubere, da kann ich das ja nicht gratis hier machen (zumal das mein arbeitsvertrag auch verbietet, wie vielleicht von einigen anderen auch).

Wie gesagt habe ich Verständnis dafür, dass du deine Ideen für dich behalten möchtest oder gar musst. Andererseits wäre es dumm, nicht mit den anderen Ideen den eigenen Horizont zu erweitern. Das gilt für diesen und für alle folgenden Wettbewerbe. Es tut mir auch leid, dass du Zeit in diese Sache gesteckt hast, ohne etwas einsenden zu dürfen.

Ich denke jedoch, dass es nichts zuzugeben gab. Ich habe auf jede Frage zu der Aufgabe bereitwillig geantwortet. Wofür man eine Lösung der Aufgabe nutzen kann, ist auch nicht schwer zu erraten. Dann muss man sich von Anfang an fragen, ob man eine Lösung beisteuern kann oder nicht. Hättest du die Aufgabe anders bewertet, wenn ich gesagt hätte, dass mir kein praktischer Nutzen einfällt? Oder wenn keiner nach dem Ursprung gefragt hätte? Ich denke also, dass sich durch meine späteren Aussagen grundsätzlich nichts geändert hat.

[jenz]

okay, wenn die caches gemeinsam genutzt werden, dann kann ich mich darauf einlassen, dass es schief gehen kann. auch wenn die threads ja so ziemlich auf den gleichen daten arbeiten.
lesend auf den rechtecken, schreibend auf der plane. lesen muss man nicht kontrollieren, das schreiben in die plane bei meinem verfahren auch nicht.

jeder thread hätte dann noch eine eigene "verwaltugsstruktur", die könnte natürlich den cache durcheianderbringen...

bei getrennten caches sollte die geschwinigkeitssteigerung aber ziemlich deutlich sein. eben fast verdoppelt, wenn man 2 nimmt.

jenz

[rapso]

Ponto schrieb:

tja, am ende hast du selbst zugegeben dass du das nutzen moechtest (nutzen!=copy&paste), andere zahlen mir mein gehalt damit ich sowas fluessig auf dem schirm zaubere, da kann ich das ja nicht gratis hier machen (zumal das mein arbeitsvertrag auch verbietet, wie vielleicht von einigen anderen auch).

Wie gesagt habe ich Verständnis dafür, dass du deine Ideen für dich behalten möchtest oder gar musst. Andererseits wäre es dumm, nicht mit den anderen Ideen den eigenen Horizont zu erweitern. Das gilt für diesen und für alle folgenden Wettbewerbe. Es tut mir auch leid, dass du Zeit in diese Sache gesteckt hast, ohne etwas einsenden zu dürfen.

keine sorge, ich kann das ja nach dem release der resultate usw. mit meiner version vergleichen. Bisher hab ich nicht viel zeit reingesteckt, leidglich das framework gesetzt und jesters version umgestellt mit trivialoptimierungen. (da sind nichtmal deine generatoren integriert).
wobei es mich auch mehr reizt dann das ganze fluessig darzustellen (was du ja als eigentliche anwendung genannt hast) als punkte in nem vector<vector<>> zu setzen *hehe*.

Ich denke jedoch, dass es nichts zuzugeben gab. Ich habe auf jede Frage zu der Aufgabe bereitwillig geantwortet. Wofür man eine Lösung der Aufgabe nutzen kann, ist auch nicht schwer zu erraten. Dann muss man sich von Anfang an fragen, ob man eine Lösung beisteuern kann oder nicht. Hättest du die Aufgabe anders bewertet, wenn ich gesagt hätte, dass mir kein praktischer Nutzen einfällt?

wenn ich gesehen haette dass es keinen nutzen gibt, haette ich eventuell code eingesand, aber da ich die benches auch alleine fuer mich machen kann wenn die sources und resultate freigegeben sind...

Oder wenn keiner nach dem Ursprung gefragt hätte? Ich denke also, dass sich durch meine späteren Aussagen grundsätzlich nichts geändert hat.

es wirkte von anfang an sehr auf einen speziellen context bezogen, deine aufgabenstellung implizirte das (vielleicht deine wortwahl )

Ich finde es ja gut dass du nen contest hier machst, raetsel loesen macht ja auch spass selbst wenn man sich nicht oeffentlich mit anderen misst oder es grossartige preise gibt.

[Ponto]

jenz schrieb:

okay, wenn die caches gemeinsam genutzt werden, dann kann ich mich darauf einlassen, dass es schief gehen kann. auch wenn die threads ja so ziemlich auf den gleichen daten arbeiten.
lesend auf den rechtecken, schreibend auf der plane. lesen muss man nicht kontrollieren, das schreiben in die plane bei meinem verfahren auch nicht.

jeder thread hätte dann noch eine eigene "verwaltugsstruktur", die könnte natürlich den cache durcheianderbringen...

bei getrennten caches sollte die geschwinigkeitssteigerung aber ziemlich deutlich sein. eben fast verdoppelt, wenn man 2 nimmt.

Nehmen wir mal an, dass du folgendermaßen parallelisierst:

Jeder Thread bekommt einen Teil der plane. Dann geht er durch die Rechteckliste und aktualisiert seinen Planeanteil, wenn das Rechteck darin liegt.

Wir können leicht dafür sorgen, dass die Planeteile, in die die Threads schreiben sich Cachemässig nicht in die Quere kommen. Dennoch wird man keinen Faktor 2 bei 2 Threads erhalten, denn wir machen jetzt manche Arbeit doppelt.

Nehmen wir an die Gesamtarbeit ist GA und der Anteil für das Schreiben in die Plane ist x*GA. Dann haben wir noch (1-x)*GA an Arbeit, die für das Durchlaufen der Rechteckliste und für die Bestimmung, ob die Rechecke in die Plane passen, draufgehen. Den ersten Teil kann man parallelisieren, den zweiten macht man jedoch doppelt.

Damit steigt die Arbeit im Falle zweier Threads auf x*GA + 2*(1-x)*GA und mit perfekter parallelisierung macht dann jeder Thread: 0.5*x* GA + (1-x)*GA

Der Speedupfaktor gegenüber der seriellen Lösung ist dann GA/(0.5*x* GA + (1-x)*GA) = 1 /(0.5*x + (1-x)) = 1/(1 - 0.5x).

Je näher also das x an 1 ist, desto näher ist der Speedup bei 2. Aber wenn x klein ist, können wir nur ganz geringe Speedups erwarten.

[rapso]

jenz schrieb:

okay, wenn die caches gemeinsam genutzt werden, dann kann ich mich darauf einlassen, dass es schief gehen kann. auch wenn die threads ja so ziemlich auf den gleichen daten arbeiten.

du kannst pech haben und jeder thread hat seine daten so, dass sie sich im cache ueberlagern, sodass sich die threads gegenseitig die daten "wegschmeissen" aus dem cache.

lesend auf den rechtecken, schreibend auf der plane. lesen muss man nicht kontrollieren, das schreiben in die plane bei meinem verfahren auch nicht.

das ist dem cache relativ egal beim mappen von cache-adress-space auf den echten addressspace.

jeder thread hätte dann noch eine eigene "verwaltugsstruktur", die könnte natürlich den cache durcheianderbringen...

koennte, koennte auch ein gewinn sein, je nach architektur.

bei getrennten caches sollte die geschwinigkeitssteigerung aber ziemlich deutlich sein. eben fast verdoppelt, wenn man 2 nimmt.

koennte aber auch doppelte belastung des rams sein, was wenn das ram das limitierende in dem fall ist? dann zerschiessen sich die threads die sequential reads?

was ist bei nem intel quadcore, 2cores teilen sich jeweils den cache, greifen die cores in der falschen combination auf die daten zu, muessen die daten aus dem einen cache ueber den FSB ins ram geschrieben werden und dann in den anderen cache....

klar, am ende hat man irgend ne beschleunigung, einer hat eventuell ne arschkarte und die ergebnisse sehen auf jeder maschine aus wie anders ausgewuerfelt

mag sein dass ich hier zu sehr schwarzmale, aber ich hab schon erlebt, dass je besser eine optimierung fuer threads ist, desto anfaelliger ist sie auf anderen architekturen.

[jenz]

nun gut, ich nehme das mal so hin...

@ponto:
eins aber noch
vielleicht kannst du ja in deinen vergleich die fläche der plane einfach mal ein paar mal verdoppeln, dann kann man den speedup vielleicht ein bisschen abschätzen.

ich habe das gerade auch ein bisschen gemacht und das ergebnis sieht wirklich nicht so erfolgversprechend aus...schade

jenz

[rapso]

jenz schrieb:

nun gut, ich nehme das mal so hin...

http://www.xbitlabs.com/articles/cpu/display/3dmax5-p4-ht.html

da sieht man ein wenig wie random die resultate sein koennen, einige benches bei denen singlethreaded 10% schneller ist, auf der zweiten seite ist dann der p4 mit HTT 5mal schneller...

[jenz]

schon interessant, aber da haben wir ja nicht wirklich getrennte rechner, sondern eben hyperthreading...

aber ich erkenne den punkt, dass es auch da schwankt.

gut, dann machen wir mal weiter unsere eigenen erfahrungen

@ponto:
wie sieht es denn mit den ergebnissen aus?

[Badestrand]

Und wäre auch interessant, wenn der Gewinner seine Herangehensweise schildern könnte; könnte man ja noch was von lernen
Muss ja nicht der Code sein, aber evtl das Prinzip, wie es gelöst wurde. Falls der Gewinner damit einverstanden ist, natürlich.