Objektorintiert vs Harvard

Mag sein. Da kann ich mich irren.

C++-lib: Naja, man kann in C++ auch einen vernünftigen[tm] compiler schreiben. Was die Sprache nicht direkt unterstützt hat sie nicht.

Ich hab lang genug C++ programmiert um es nicht zu mögen. Der Featureism verleitet zur Vernebelung. Mit KISS hat C++ nichts zu tun und das "un-KISS" bringt keinen Vorteil. Kleine, mächtige und lesbare Sprachen sind besser.

Ich will nicht ins Detail gehen, wie die Suche aussieht: Das mit dem "rauskramen" ist eine freundliche Umschreibung. :-) Aber das könnte dir auch gefallen: "Inside the C++ Object Model", Stanley B. Lippman; Addison Wesley; ISBN

0-201-83454-5. Ich suche weiter ...

Gruß, Nick

--
Motor Modelle // Engine Models
http://www.motor-manufaktur.de
DIY-DRO -> YADRO

Wer an Bubble sort denkt, wird in der Welt der effizienten Algorithmen nicht weit kommen. Ich nehme an, dieses Unding ist ein typisches Produkt der "strukturierten" Schule. Wenn man schon ein if then goto einbaut, kann man das goto gleich auf die richtige Zeile zeigen lassen, dann heisst der Algorithmus straight insertion und ist durchschnittlich 2.5 mal schneller als Bubblesort, ohne eine Zeile mehr code, IIRC.

--
mfg Rolf Bombach

Bubble ist hier ein Synonym für einen beliebigen O(N^2) Algorithmus: Effizient für kleine Datenmengen - dann sogar mangels Overheads effizienter als ein "großer" Algorithmus - aber ineffizient für große Datenmengen.

Wenn es noch schneller gehen soll: Shell's Verfahren, dann kann man eigentlich auch gleich einen "großen" Sortieralgorithmus hernehmen.

Nö, das ist ein Schmarrn, Straight Insertion geht selbstredend so wie jede andere Programmieraufgabe.

Dein Einwand ist im Detail sicher gerechtfertigt, leidet aber etwas an dem im deutsprachigen Raum verbreiteten "kleinklein" oder "wir sehen vor lauter Bäumen den Wald nicht mehr":

Aufgabenstellung ist es, einen für die jeweilige Aufgabe _unter_Berücksichtigung_der_Randbedingungen_ optimalen Algorithmus mit Hardwareunterstützung auszuwählen. Dabei ist es für das _Beispiel_ völlig irrelevant, ob der "kleine kompakte" Algorithmus ein Bubble, Straight Selection/Insertion oder wasauchimmer ist, ebensowenig wie der Expertenstreit, ob denn nun Heapsort oder Quicksort (schluckt Stack!) in einer seiner vielen Varianten oder was auch immer der tollste und schönste "große" Algorithmus ist.

Diese Diskussion überlasse ich gerne dem Nutzer der Erfindung ;-)

Goto ist deshalb heutzutage sehr schlecht, weil es dem Compiler viele Optimierungsmöglichkeiten nimmt. Bei strukturierter Programmierung innerhalb einer Schleife ist sofort klar, wie der Einstieg aussieht (eben nur über die Schleife) und der Ausstieg (Schleifenende oder break wenn genutzt).

Bei Goto kann man lustig raus und wieder reinspringen, womöglich noch Conditional, für Compiler ist das recht eklig zu verfolgen, deshalb will man das eigentlich selbst in Fortran nicht mehr sehen. Wenige Ausnahmesituation bei sparsamster Verwendung bestätigen die Regel.

Ansonsten macht wildes "goto" so ziemlich alle "großen" Optimierungen sehr schwierig, die an Schleifen ansetzen.

Nochmals Vorsicht: Bei heutigen Rechnern ist immer auch zu beachten, inwieweit eine Schreiboperation auf dem Speicher lokal ist, da schneidet Straight Insertion mit seiner Array-Schieberei gegenüber z.B. dem erweiterten Bubble namens Straight Selection (also Swapen des kleinsten Elements aus dem Restarray nach vorne) bei den kleinen Lösungen _garnicht_ gut ab. Letzeres kommt nämlich mit maximal (n-1) Swaps aus.

Siehe:

Grund ist, dass das _Lesen_ beim Cache (wir reden über kleine Arrays!) immer unproblematisch ist, hingegen _Schreibvorgänge_ ihren Weg ins DRAM und ggf. bei Multicore-Szenarien zu anderen CPU-Caches finden müssen.

Gruß Oliver

--
Oliver Bartels + Erding, Germany + obartels@bartels.de
http://www.bartels.de + Phone: +49-8122-9729-0 Fax: -10

In der '"strukturierten" Schule' wird aber goto tunlichst vermieden. Da aber if - then - else nicht immer reicht...

... gibt es comeform als neues Konstrukt.

SCNR, Norbert

In article , Norbert Hahn writes: |> In der '"strukturierten" Schule' wird aber goto tunlichst |> vermieden. Da aber if - then - else nicht immer reicht... |> |> ... gibt es comeform als neues Konstrukt.

INTERCAL kennt in der Tat "come from" anstatt "go to" :)

Rainer

Hehe, Du meinen :

;-))

Ansonsten zur Info für die Freunde des historischen "goto":

Der BAE ist in seinen pi-mal-Daumen 1 Mio. Lines of Code komplett goto-frei strukturiert programmiert.

Lediglich beim Einstieg in extrem speicherdynamische Modulen wird als Ersatz für Exceptions (NULL malloc) an wenigen Stellen im Fehlerfall setjmp/longjmp genutzt.

Exceptions gibt es in C nicht, C++ gab es damals noch nicht und ist für besagte Modulen auch heute kein Thema, da sie von der Performance extrem optimiert sind, das kann C noch einen Tick besser, bestimmte C++ Konstrukte sind einfach zu verführerisch ;-) Außerdem können aktivierte Exceptions in C++ richtig böse Performance schlucken (Zusatzaufwand beim Stack Handling zum Anlegen bestimmter Infos, wenn das ganze Objekt-Gerümpel ;-) irregulär abgebaut werden soll), deshalb kann man sie bei vielen Compilern deaktivieren.

Dabei geht es im BAE aber nur um den nicht regulären Ablauf, z.B. bei Speicherplatzmangel, und um wenige zentrale Routinen (Listenhandling etc.) bzw. Einstiegspunkte in besagte Modulen.

Es geht also strukturiert ;-)

Gruß Oliver

P.s.: Hint noch an Rolf: Den BAE hab' ich schon initial selber entwickelt, auch 1985 waren da schon bessere Sortierroutinen drin, sonst hätte ich kaum die etablierte Konkurrenz derart ärgern können ;-)

P.s.2.: Das heißt übrigens nicht, dass z.B. Fortran 90 schlecht ist, es gibt klar definierte technisch-wissenschaftliche Aufgabenstellungen, bei denen Fortran 90 auch C++ von der Performance her in Schutt und Asche legt. Man schaue sich nur die integrierte Unterstützung für Vektormaschinen oder den integrierten Datentyp "complex" an, in C++ sind komplexe Zahlen Objekte mit dem ganzen Overhead, in Fortran 90 schlicht integriert. Es gibt nur leider sehr viel unstrukturierten Fortran-Code in der Form einer bekannten italienischen Pasta ...

--
Oliver Bartels + Erding, Germany + obartels@bartels.de
http://www.bartels.de + Phone: +49-8122-9729-0 Fax: -10

Oliver Bartels schrieb:

Ach, wo stand denn sowas? Wo du so in Fahrt bist, warum beschimpfst du mich nicht gleich als Terrorist, Nazikommunist oder sonstwas?

Zudem geht es hier nicht wirklich um existierende Werke, sondern um mangelnde Erfindungshöhe.

Was immer das für eine Wortschöpfung sein soll, die Zweige eines Summentyps sind ziemlich dynamisch. Deine Unterstriche ändern nicht viel daran, dass deine "Erfindung" von praktisch jedem modernen Compiler bereits benutzt wird, natürlich ohne spezielle Hardware.

Und nur um das nochmal unmißverständlich klarzustellen: es ist scheißegal, ob die Lispmachine bereits in Hardware tat, was GHC heute in Software macht, die bloße Übertragung von Software in Hardware besitzt eben keine Erfindungshöhe.

Ganz recht. Exakt das macht (nicht nur) GHC. Pausenlos.

"Ich bin zu dumm, sowas zu kennen, deswegen steht mir ein Patent zu!"

Also das tut mir leid, aber wenn das Patentsystem so funktioniert, bin ich wirklich grundsätzlich dagegen.

Typisch Usenet:

Ich habe nach Prior Art gefragt und erhalte Blablubb und aktionistische ("Terrorist, Nazikommunist") Sprüche. Halt das, was immer kommt, wenn die Argumente ausgehen.

Aber keine Sorge, dann werd' ich auch etwas ironisch:

Soso, dann zeig doch mal bitte, wie Dein praktisch moderner Compiler das bei typischen Programmcode mal eben macht und selber zwei Funktionen für eine Aufgabe erzeugt.

Hint: Normale CPU's haben keinen Ternärspeicher und das hat Implikationen. So würde spätestens beim zweiten Parameter die Auswahl mit Sprungketten etc. länger dauern als gleich die "falsche" Funktion zu nehmen. So wird das nix.

**** Und dann zeig auch mal bitte, wie der dynamisch nachcompiliert, zu dem Abschnitt in meinem letzten Posting schweigst Du sehr verdächtig ;-) Und dazu, dass aus _einer_ Funktion in einer imperativen Programmiersprache n Varianten effizient ausgewählt werden, _ohne_ dass der Benutzer etwas tun _muss_ (er _kann_), dazu schweigst Du auch. ****

Du argumentierst wie die Patentabteilung einer großen Bank mit angeschlossener Elektroabteilung, ich habe das _tatsächlich_ schonmal live erlebt:

- Wir haben drei dicke Bücher

- Wenn wir das hieraus nehmen, das daraus und das dortraus, alles kombinieren und etwas Intution reinpacken, die jeder Ingenieur von Fa. S selbstredend in Unmengen hat, dann wären wir auch drauf gekommen.

Haben sie _so_ in einem Einspruch gebracht => abgewiesen =>

sind dann zum Bundespatentgericht gerannt => dort aber wegen Aussichtslosigkeit _nicht_erschienen_ (sie wollten nur verzögern und blockieren) => vier Richter durften nutzlos rumsitzen, waren recht sauer über besagte Bank und haben dann einige deutliche Worte ins Urteil geschrieben.

Neu bei Dir:

- Man kann es grundsätzlich in Software simulieren, dann hat es keine Erfindungshöhe

Mit dem "Argument" bekommt man _jede_ Erfindung tot.

Du solltest Dich sofort bei der Bank mit angeschlossener Elektroabteilung bewerben. Sag' aber bitte bei der Bewerbung, dass Du das nur für fremde Patente so siehst, bei den eigenen tun sie nämlich wirklich jeden noch so nichtigen Mist anmelden.

Zu Deinem komischen Argument noch ein

Hint: Natürlich hat die Übertragung von Software in Hardware Erfindungshöhe, wenn ich irgendein Ding hab', dass z.B. eine Software mit 1000 Zyklen geschickt durch einen Hardware- Zyklus ersetzt, dann ist das ja wohl nützlich. Und wenn es eben vorher keiner wußte wie geht, dann ist es auch erfinderisch, mit Höhe.

Codebeispiel und Hardwarebeispiel ;-)

Behauptung "ich kann's auch" ist nicht Prior Art.

Und nochmal: Overloading ist etwas anderes. Lambda auch. Und ein Prolog-alike mit Unifizierung hab' ich selber schon in den BAE eingebaut. Ist aber auch was anderes ;-)

Ich bin für offene Worte und lese aus Deinem Posting den in Deutschland nicht unüblichen, ähm, Nei^H^H^H Habitus bzgl. Leistungen Dritter. "Ich bin nicht draufgekommen, also kann es nichts taugen." Fehlt nur noch die Forderung nach einem besonderen Solidaritätszuschlag auf in Deutschland angemeldete Erfindungen und einer allgemeinen Freigabe für soziale Zwecke, dazu zählen grundsätzlich Nutzungen durch Konzerne der Deutschland AG und ansonsten von jedem Uni-Heini, der "sozial" ruft ;-)

Es ist auch nicht unüblich, dann ein bisserl verquer zu argumentieren, in der Hoffnung, dass es keiner merkt, wie gesagt, ich bin das bereits von der Bank mit angeschlossener Elektroabteilung gewohnt, die haben wieviel Mitarbeiter ? 200000 ?

Die sind zwar gewiß nicht alle so drauf, aber ein Gutteil schon. BTDTNT.

Gruß Oliver

P.s.: Und wieder was dazugelernt: Ich werde Neuigkeiten hier nicht mehr diskutieren, bringt eh' nix mangels Leserlevel. Irgendwas Konstruktives oder wenigstens argumentativ Brauchbares ist nicht gekommen. Deutschland 2006 halt.

--
Oliver Bartels + Erding, Germany + obartels@bartels.de
http://www.bartels.de + Phone: +49-8122-9729-0 Fax: -10

also interessierte Leser hast du bestimmt viele ...

doch ich muss zugeben, dass ich selbst nach fast abgeschlossenem Studium häufig ratlos vor deinen Beiträgen sitze und nicht folgen kann ...

Die Grundidee hier ist wohl rübergekommen - aber für die Details müsste man dann wohl doch Informatiker mit Compilerbau-Vorlesungen sein :-( Als Elektrotechniker bin ich froh nach dem Studium (immernoch) programmieren zu können - für einen Einspruch oder eine Diskussion reicht das aber nicht ...

besonders schön sind dann Absätze wie:

frohe Ostern noch

bye, Michael

Nein, Oliver, genau das hast du nicht. In meine Erklärung, dass dein Patent keine Erfindungshöhe besitzt, hast du stattdessen hineininterpretiert(!), dass ich Patente grundsätzlich ablehne. Was erwartest du denn für eine Antwort nach so einem Strohmannargument?

Also eigentlich typisch Usenet-Kook: "Wer meine Großartigkeit nicht erkennt, ist dumm / gegen die Grundlagen der westlichen Zivilisation / Teil der Weltverschwörung gegen mich / ein Netcop."

Geh nach

lad das Ding herunter und sieh dir die Implementierung von Integer und String an. Das ist exakt das, was du beschrieben hast (in Software natürlich). Nein, er kommt nicht von selbst auf die Idee, den Code oder gar die Repräsentation zu spezialisieren, aber sowas hast du auch eigentlich nicht beschrieben. Ich bezweifle auch ganz stark, dass du das überhaupt realisiert hast, von uninteressanten Spezialfällen (degenerierte Vektoren, habe ich ununterbrochen in meinem Code) abgesehen.

Nun, genau so wird es aber gemacht, und in den genannten Fällen lohnt es sich sehr wohl. Du machst dich ein wenig lächerlich, wenn du theoretisch beweist, dass etwas praktisch existierendes nicht existieren kann. Das gab es schon einmal, ich glaube, die Jupitermonde waren es, die theoretisch die Kristallsphäre durchschlagen müssten oder sowas.

Weil mir der Teil am Arsch vorbei geht. Wenn man nämlich den Java-Anhängern glauben darf, macht deren JIT-Compiler sowas schon längst, also Laufzeitprofilierung und Spezialisierung soweit es sich lohnt. Ob das stimmt, will ich gar nicht wissen, weil ich die Sprache einfach widerlich finde.

Jungejunge... ES WIRD BEREITS IN SOFTWARE GETAN, es ist nicht bloß grundsätzlich simulierbar. Du kannst nichts erfinden, was bereits existiert. Ja, neuerdings ist es üblich, eine alte Erfindung zu nehmen und sich nochmal patentieren zu lassen, einmal mit einem ASIC und dann noch einmal mit einem Cluster und dann mit einem Cluster von ASICs. Jedenfalls in den USA.

Das. Hat. Aber. Keine. Erfindungshöhe.

Gute Idee. "Ich bin voll der Held, weil ich ein Trivialpatent habe" will nämlich auch keiner lesen. (Hier übrigens schon gar nicht, ist nämlich nichts elektrisches. Nein, Software in ASICs umgesetzt ist immer noch Software, auch wenn es die Patentamtsaffen nicht merken.)

Keine Erfindungshöhe ist immer das, was kommt, wenn sonst nix mehr kommt. Begründet hast Du es aber nicht, weder mit Beispielen (auch nicht mit dem unten) noch sonstwie.

Wenn es keine Erfindungshöhe hätte, wäre es längst bei Intel und AMD in den CPU's implementiert.

Ist es aber nicht. Punkt.

Aus dem Gesamteindruck Deiner Äußerungen (" Patentamtsaffen") entnehme ich sehr wohl, dass Dir Patente grundsätzlich gegen den Strich gehen.

Jedenfalls solange, wie Du nicht selber drauf gekommen bist ;-/

Aha: "eigentlich". Bitte. Danke.

Dann ist es auch nicht das, was ich beschrieben habe, und jede weitere Diskussion mit Deinem Haskel ist sinnlos. Es mag eine nette funktionale Sprache sein, geht aber _völlig_ an dem Gegenstand der Erfindung vorbei.

Ich muss für ein Patent erstmal überhaupt nix realisieren, und das, was wir da exakt realisieren, werde ich sicher hier nicht veröffentlichen.

Nur soviel: Es gibt schon mehr als nur das Patent.

Erfindungsgemäß geht es aber schneller als per Sprungkette.

Kurzum: Die Sprungkette ist das Problem, nicht die Lösung.

Macht er nicht, aber ich finde die Informatiker-Diadochenkämpfe um nix immer wieder lustig.

=> Es will Dir doch niemand Dein Haskel Spielzeug nehmen ;-)

Das ist kein Kriterium, dass jemand ein Problem in Software hat, und keine schnelle Lösung in Hardware.

Nicht nur in den USA.

Nochmal zum Mitmeißeln:

Wenn es eine besonders ellegante Lösung gibt, eine Software- Krücke durch eine schnelle Hardware zu ersetzen, die es vorher nicht gab, dann ist das ganz klar vom Status her eine Erfindung.

Es steht Dir frei, weiterhin in Deinem Haskel-Spielzeug den lahmen Gaulsweg der Sprungkette zu gehen.

Wenn Dein Argument zutreffen würde, gäbe es seit der Touring-Maschine überhaupt keine Patente mehr auf CPU-Hardware-Architekturen, weil man ja theoretische jede Aufgabe mit der Touring-Maschine lösen könnte und das vielleicht auch schon sehr umständlich per Gaulsweg in Software gemacht wird.

Aber nochmal: Das Stenzelsche Kriterium spielt für Patente auf Hardware nach dem Patentgesetz keine Rolle. Punkt.

Hat es, wirst Du sehen. Du kannst ja dann Einspruch einlegen, es wird Dich nur Geld kosten und nix bringen.

Du definierst Erfindung völlig flasch:

Wenn ich heute, sagen wir mal, ein konkrete Lösung habe, einen Automotor zu bauen, der den Karren mit 1L Sprit auf 100km antreibt, indem irgendwas im Motor verändert wird, dann fehlt dem nicht deshalb die Erfindungshöhe, weil Du herkommst und sagst, dass das 1L Auto schon seit 20 Jahren gewünscht wird.

Konkret: Deine Sprungleiste vom ghc ist keine Lösung.

Sie ist _das_Problem_, und zwar performancemäßig in jeder Hinsicht.

Das liest sich wie: "Bäh, ich bin selber nicht auf die Idee gekommen, wie man das in Hardware umsetzt, und deshalb ist es keine Erfindung und sowieso Sch(zensiert) usw." Halt das übliche N-Problem.

Geh' bitte weiter spielen. Danke.

Nochmal: Wenn das alles so ohne Erfindungshöhe und so einfach wäre, wie ein Herr Stenzel sich das vorstellt, dann gäbe es das längst in gängigen CPU's.

Totschlagargument: Gibt es aber nicht ;-)

Ciao Oliver

--
Oliver Bartels + Erding, Germany + obartels@bartels.de
http://www.bartels.de + Phone: +49-8122-9729-0 Fax: -10

Das ist ein Nulargument. "Das" gibt es deswegen nicht in aktuellen CPUs, weil bis auf "Exotensprachen" wie eben Haskell es keiner braucht. Weil kein Compiler automatisch Spezialcode für degenerierte Vektoren / komplexe Zahlen usw. generiert. Weil das Feature damit brachliegen würde. Und die Haskellaner simulieren sich sowas mit Sprungleisten und verfluchen die Prozessorbauer, die berechnete Sprünge so langsam machen. Weils in C ja keiner braucht.

Mein erster Gedanke beim Lesen des Postings vor 3 Monaten war auch "klingt verdammt nach STG-(=Haskell)-Patternmatching". Wenn's das irgendwie als Hardware geben soll, warum nicht. Und wenn als Patent, warum nicht (um das klarzustellen: mein Hauptkritikpunkt am Patentsystem ist nicht dessen pure Existenz, sondern die für insbesondere Software absurd langen Laufzeiten). Ich hab allerdings durchaus Zweifel, dass zumindest die mir bekannte Compilertechnologie da ohne manuelle Nachhilfe wirklich viel rausholen kann. Ich lass mich natürlich auch gerne überraschen.

Stefan

Es ist schon ein Argument, weil man das "gewußt wie" für imperative Programmiersprachen bisher nicht hatte.

Die Leute bei den Halbleiterherstellern sind normalerweise für jedes Features dankbar, das Geschwindigkeit bringt, gerade bei den Sprüngen plagt man sich ohne Ende mit der Branch Prediction rum.

Da gibt es übrigen auch Ansätze wie Verzweigungszähler im Branch Prediction Cache (Pentium M) oder Caches, die sagen, welcher Prediction Algorithmus an der Adresse bisher das beste Ergebnis geliefert hat.

Vieles von dem ist auch patentiert, obwohl der Sprungbefehl und die Schleife uralt sind ...

Nur: Die Firma Intel unterhält eine große Abteiliung, die nix weiter ausßer Compilerbau macht und im übrigen zwei sauschnelle solche (C/C++ und Fortran) herausgibt, um die Vorzüge der eigenen CPU's herauszustreichen.

Wenn die eine entsprechende Idee gehabt hätten, wäre es längst in den CPU's, natürlich vermarktet als "Extension", die es für neue Software irgendwann braucht ;-)

Interessant wird nur, ob wir, da Erfindung aus .de, wieder auf ein "not invented here" Problem auflaufen, das umgekehrte "invented here" Problem hat Udo ja schon "eindrucksvoll" demonstriert :-(

Ich hab' mir das Haskel Zeug mittlerweile mal angeschaut, für die Jungs würde das natürlich ziemlich helfen, wenn man die "Sonderdönches" in der Hardware mit berücksichtigt, wenngleich Pattern-Matching in eine etwas andere Richtung geht. Von Hardware schreiben die aber ganz klar nix, sie plagen sich bisher auch mit Sprungleisten.

Der Ansatz für den breiten Markt sind aber ganz klar imperative Programmiersprachen.

Insofern weiß ich auch nicht, was der Ärger soll, das ist meiner Meinung nach mal wieder typisch deutsches "ich gönn dir das nicht", weil man nicht selber draufgekommen ist, obwohl man die ganze Zeit mit Pattern Matching schafft und da Sprungleisten wirklich eklig sind.

Im Grunde sollten die Haskell Leute doch heilfroh sein, wenn über den Weg über imperative Programmiersprachen derlei Einzug in die Hardware findet. Und es muß ja nicht immer nur ein großer wie Intel oder AMD sein, der die Lizenzrechte hat, auch wenn der Teutsche seinen Großkonzern über alles liebt, jedenfalls solange, bis der ihn auf die Strasse stellt.

Eben, das ist doch ein Wort.

Die Laufzeiten sollten für bestimmte Bereiche der Technik angepasst werden, da stimme ich Dir zu.

Ein Medikament ist doch etwas anderes wie ein Tintenstrahldrucker oder ein Stück Software.

Allerdings gibt es bereits jetzt einen Hebel, der aber leider nur die kleinen trifft und kaum die Konzerne: Die Jahresgebühr steigt mit den Jahren ...

Es wird dann gehen, wenn man das wirklich inklusive Statistik in Hardware mitlaufen läßt und bei Bedarf im Hintergrund per Online-Compiler zuschlägt.

Der Ansatz dazu spielt sich bei konventionellen Programmiersprachen auf zwei Ebenen ab:

- Der Compiler kann anhand der Kostenfaktoren auch bereits auf Zwischencode-Ebene eine "was wäre wenn" Information mitgeben, also ein "wenn das const. ist, oder jene Bedingung gilt, spart man die und jene Kosten bzw. Rechenzeit".

Nicht nur zufälligerweise haben wir in unserem Autorouter einen "welche Leiterbahn muss ich rauswerfen, damit ich hier durchkomme" Algorithmus drin, die Lösung für den Compiler (auch nur eine Suche nach der besten Codesequenz) ist da garnicht soooo weit weg davon), hier heißt die Aufgabe: Welchen Code muss ich rauswerfen, damit es schnell wird, und welche Anforderung stellt das an die Funktionsparameter.

- Auf der Ebene der Hardware wird dann geprüft, ob eine der Spar-Annahmen des Compilers in eine speziellen Variante (z.B. const = 3) zutreffend ist. Dazu wird ein Testeintrag im CAM angelegt und dann schaut man, was dessen Statistik sagt. Spricht sie für die Lösung, dann verweist der Testeintrag irgendwann auf eine Spezialimplementation der allgemeinen Prozedur oder Funktion.

Vom Prinzip her ist das ein Feld, auf dem man softwareseitig bzw. beim Compilerbau sich extrem mit Algorithmen und Forschung austoben kann, eben mal was ganz neues.

Schaunmermal, was draus wird (*).

Gruß Oliver

P.s. (*) ich schätze langsame Privatentwicklung von uns, obwohl wir lizenzvergabewillig sind. Irgendwann wundert sich dann wer, wieso in irgendeinem Produkt "Schritt 3: Es geschieht ein Wunder" abläuft und klagt dann z.B. gegen jede Werbeaussage, weil er gegen die Wand läuft. Haben wir gerade bei einem Kunden - halt typisch Deutschland -, deren Wettbewerber ist technisch zu allem zu blöd, macht aber Theater wegen Wettbewerbsrecht und sonstigen Stunk ohne Ende, weil er jetzt mit seinem Kram im Markt ein Problem hat. Es ist das, was ich an Deutschland im Jahr 2006 so liebe: Wettbewerb heißt nicht mehr: "Ätsch, ich hab' aber die noch bessere Lösung", sonder "Bäh, ich werf dir Knüppel zwischen die Beine" :-(( => "Wer aufhört, besser zu werden, hat aufgehört gut zu sein". ( Philip Rosenthal )

--
Oliver Bartels + Erding, Germany + obartels@bartels.de
http://www.bartels.de + Phone: +49-8122-9729-0 Fax: -10

Stefan Reuther schrieb:

Na, "Mainstreamsprachen" brauchen "das" genauso (oder auch nicht), nur an anderer Stelle.

Hier konkret: GHC stellt den Integer wahlweise als Maschinenwort oder als Zeiger auf eine entsprechende Struktur der gmp-Bibliothek dar. Der Datentyp Integer ist die algebraische Summe aus beidem. Das lohnt sich deshalb, weil beim Rechnen mit kleinen Zahlen der Aufruf an die gmp-Bibliothek entfällt. Genau das beschrieb Olli für komplexe Zahlen. Natürlich wird hier das sowieso vorhandene Patternmatching zur Implementierung benutzt.

Wie sieht dasselbe in C++ aus? Vermutlich würde man "kleine Integer" und "große Integer" von der abstrakten Klasse "Integer" ableiten, und sich häßliche Probleme mit fehlender Unterstützung für multiple Dispatch einhandeln. Und in C? Nimmt man eine "tagged Union". Ist auch Pattern-Matching, nur unkomfortabel.

"Das" ist deshalb nicht in aktuellen CPUs, weil die Verzweigung gar kein Flaschenhals ist. Im Gegenteil, die Kette von wenigen Verzweigungen verträgt sich besser mit Sprungvorhersage als eine Sprungtabelle.

Richtig, das wird ein Mensch machen müssen. Sehen, dass eine abgewandelte Repräsentation für degenerierte Vektoren lohnt und den Compiler anweisen, dafür spezialisierten Code zu erzeugen. Wenn Olli das automagisch hinkriegt, ist er ein Held. Vaporware reicht aber nicht.

Warum nicht? Weil in der Patentschrift irgendwelcher Unfug von "einem System, bestehend aus Software und Hardware, welches alternative Repräsentationen für Daten und alternative Codepfade oder anderes verwendet, um Rechnungen zu optimieren oder andere Dinge zu tun, wozu es Tagbits oder was anderes speichert oder berechnet" stehen wird und dann braucht es nur noch einen findigen Anwalt, damit jeder Programmierer, der tagged Unions verwendet oder welche durch Ableitung simuliert, eine Lizenz kaufen muss, obwohl sein Algorithmus schon in TAOCP beschrieben ist.

Praktisch existierende C++ Libraries in diesem Bereich überladen die entsprechenden Operatoren mehrfach. Damit klappt das dann natürlich nur noch statisch. Für die Mehrheit der Fälle sollte das aber ausreichen. (BIGNUM vs. Maschinen-INT ist ein unglücklicher Fall, aber entartete COMPLEX oder Polynome sind meistens schon zur Compile- zeit erkennbar).

Nicht nur das. Ich sehe da jede Menge unrealistische Annahmen:

- Quelltext ist zur Laufzeit verfügbar; das kann man bis auf wenige Spezialfälle (gut weggesperrte embedded Computer) abhaken. Am realistischsten dürfte Bytecode a'la Java sein. Dann degradiert das zu einem JIT Compiler mit Hardware-Unterstützung.

- es kann/darf überhaupt Code zur Laufzeit ausgetauscht werden. Schon Java-JITs als vergleichsweise abgehangene Implementation machen in der Praxis häßliche Probleme. Debugging wird z.B. praktisch unmöglich. Eigentlich will man JIT nur als zweithäß- lichste Lösung gleich nach "Code ist prohibitiv langsam".

- einerseits soll zwar die Laufzeit verkürzt werden, andererseits hat man aber Zeit für Profiling, Statistiken, Neucompilieren etc. Oliver redet zwar laufend von "im Hintergund", aber wenn man die Resourcen ohnehin vorhält, kann man sie auch gleich auf das eigentliche Problem werfen.

- last not least: Olivers Lösung erfordert *engste* Kooperation zwischen Compiler- und Prozessor-Bauer. Das hat zumindest in der Vergangenheit nicht funktioniert. Die wenigsten Applikationen stehen überhaupt als Kompilat für die tatsächliche Laufzeit- Umgebung bereit. Praktisch macht das niemand - außer für Benchmarks.

Meine Schlußfolgerung: das Ganze ist nicht massenmarkttauglich und

*deswegen* steckt es nicht in z.B. Intel-CPUs drin.

IMHO ist die Hardware inzwischen viel weiter vor den Compilern her, als jemals gut gewesen sein kann. Von den ganzen RISC-Versprechen ist nichts geblieben außer "die meisten Instruktionen laufen in einem Taktschritt".

Z.B. ist das ganze Branch-Prediction-Gerümpel nur ein Zeichen der Kapitulation vor der miesen Qualität des erzeugten Maschinencodes. In erster Linie sollte der Programmierer wissen, welcher Zweig in einem if() oder while() der wahrscheinlichere ist. Die entsprechenden builtins gibt es nicht erst seit gestern. Für Härtefälle profiled man halt ein paar Testläufe und optimiert danach. Das wird manchmal ein bisschen daneben liegen, aber schlimmer als die branch prediction in der Hardware sicherlich nicht. Die Anwendung, bei der statische Optimierung gar nicht funktioniert, halte ich für einen Mythos.

XL

Das tut man natürlich außerdem. Auch GHC überlädt die numerischen Operationen mehrfach und spezialisiert einige davon statisch.

In der Tat, ist ja auch so ziemlich das einzige Beispiel, das mir auf Anhieb einfiel. Lohnt sich hier wohl hauptsächlich deshalb, weil der Aufruf einer ganzen Bibliotheksfunktion durch ein paar Maschinenbefehle ersetzt wird.

Jup, denkt man sich eigentlich so. Komischerweise zeigt aber die Erfahrung, dass ein JIT wirklich ein Gewinn sein kann: HPPA-Code mit einem JIT-Compiler auf der HPPA auszuführen ist schneller als ihn direkt auszuführen. Ich vermute aber, das liegt daran, dass die Prozessoren eine 30-jährige Evolution hinter sich haben, die Programmiersprache aber immernoch dieselbe ist, C nämlich.

Letztenendes baut man aber eben doch lieber Compiler, die versuchen, Sprünge rauszuoptimieren bzw. baut Hardwareunterstützung für bestimmte Schleifen ein ('rep movsd' auf x86, 'do' auf 56000, etc.).

Aus dem Gebiet der funktionalen Programmierung bin ich seit geraumer Zeit "raus", aber in den Veröffentlichungen über STG, die GHC-Runtime usw. kam schon immer mal der Wunsch nach Hardware-Unterstützung auf. Weil man im Gegensatz zu z.B. einer Faltung in C, die man aufrollen kann, in Haskell/STG kaum Sprünge wegoptimieren kann, und dann sind das auch noch alles berechnete Sprünge.

Hardwareunterstützung wäre eben z.B. ein Befehl 'addcu reg, mem, label' (add memory to register if memory is evaluated, call label if memory is unevaluated), so dass eben in einem arithmetischen Ausdruck die ALU schon mal spekulativ losrechnen kann. So wie ich deine Beschreibung verstanden habe, soll das ja was ähnliches werden, nur eben über eine "daneben" stehende Verarbeitungseinheit mit CAM, die die Operanden beobachtet und ggf. eingreift.

Meiner bescheidenen Meinung nach sind degenerierte Vektoren zu selten (Gamerz wollen 3D!), degenerierte komplexe Zahlen sparen zu wenig (es kostet einfach mehr, die Entscheidung "real oder komplex" zu fällen, als es kostet, die Multiplikation gleich komplex auszuführen), und funktionale Programmierung ist eine belächelte Nischenecke.

Wenn's natürlich beim Leiterplatten-Routing was bringt :)

Weil es nichts anderes gibt. Das geniale an der STG ist ja, dass sie die lazy-Auswertung halbwegs performant auf eine von-Neumann-Maschine bringt.

Yep. Wenn's ein Erfolg wird, werde ich hoffentlich in der Heise-Presse davon lesen :)

Stefan

Das Hardware-Repeat ist eine klassische Operation für DSP's und bei praktisch allen besseren DSP's implementiert. Wenn eh' schon ein Adressgenerator da ist, dann spielt der zusätzliche Zähler oder Zähler-Stapel auch nicht mehr die große Rolle.

_Manche_ PC-Prozessoren erkennen nach dem ersten Schleifendurchgang auch, was Sache ist, in Shen Lipasti ist ganz gut die Branch Prediction speziell für Schleifen beschrieben.

Das ist der Punkt, und das Üble an der Standardumsetzung ist genau das "erst fragen wir den Parameter ab, oh es ist immer noch nicht entschieden, dann müssen wir noch jenen abfragen, noch ein berechneter Sprung" usw.

An dem Punkt haben die Rufer nach Hardware dann wohl aufgegeben ;-/

Mein Ansatz ist der, zumindest die gängigen Fälle in einem Bitstring zu codieren und dann _parallel_ die gesamte Evaluierung durchzuführen.

Genau das macht den Unterschied.

Sie wird aktiv gefragt und entscheidet in einem Zyklus.

Bei Deinem 'addcu' ist immer noch die Sequenz drin, genau die will ich rausbringen.

Mir geht es um eine schnelle Entscheidung beim Aufruf eines Unterprogramms, welche Variante denn zu nehmen ist, anhand einem Blick auf _alle_ (wesentlichen) Parameter.

D.h. es gibt eine Hardware, welche sich die Parameter z.B. auf dem Stack oder in Registern ansieht und daraus ein Bitmuster erzeugt, welches den Eigenschaften der Werte der Parameter entspricht.

Danach gibt es noch genau einen Zugriff in den TCAM Speicher, der sagt dann, welche Variante der Funktion angesprochen werden soll.

Im Grunde ist das ganz klassische Programmierung und hat mit dem funktionalen Ansatz nicht viel gemein.

Für den Compiler ist es auch nicht so schwer: Der kann relativ leicht untersuchen, was wäre, wenn das zu übersetzende Unterprogramm einen oder mehrere Parameter mit genau diesen Eigenschaften bekommt, genauer: Um wieviel einfacher dann das Programm wird.

Ergibt sich eine erhebliche Einsparmöglichkeit, dann kann das z.B. im P-Code vermerkt werden, auf das, wenn Profiling aktiviert, zur Runtime auf genau den Fall untersucht wird. Lohnt es sich, dann wird der P- nach Maschinencode- Compiler angeworfen, mit dem oder den Parametern z.B. auf den besagten konstanten Wert gesetzt (z.B. Null), der Optimizer wirft dann unnötigen Code raus (irgendwas mal Null braucht man nicht berechnen).

Ist das Profiling beendet, dann kann man im Prinzip auch den gesamten Maschinencode einfrieren.

Interessant ist die Frage, wie das "lohnt sich" bei _mehreren_ gleichzeitigen Eigenschaften der Parameter ermittelt wird, aber auch da gibt es Lösungsmöglichkeiten ;-)

Die degenerierten Vektoren sind nur ein Beispiel, bei komplexen Zahlen könnte so ein Mini-CAM im Bereich der Pipeline deren Auslastung schon verbessern, immerhin fallen _Fließpunkt_ Multiplikationen _und_ Additionen weg. Wichtig ist nur, dass die Abfrage nicht länger braucht als der Rechenvorgang.

Ja. Sie ist nett, aber letztlich für reale Anwendungen doch nicht unbedingt durchsichtig (es braucht teure Experten), genau genug kontrollierbar und schnell genug. Der "Kunde" wünscht zumeist eine "ah, jetzt macht er erst dies und dann das" Programmiersprache.

Dagegen ist funktionale Programmierung eher wie höhere Mathematik und damit nicht jedermanns Sache.

Es kommt aus der Ecke, weil wir teilweise wegen wenigen Sonderfällen ziemlich aufgeblasene Funktionen haben, ohne die Sonderfälle deutlich schneller wären.

Kommerziell interessant ist es dafür aber nicht, der Ansatz muss dann eher schon Richtung IC oder allgemeine Nutzbarkeit gehen.

Wobei: Auch da ist der Aufwand im Vergleich zu anderen Patenten - wie zumeist in der EDV - eher hoch und der erzielbare Preis - wie zumeist in der EDV ;-/ - nicht so hoch. Deshalb schätze ich, dass das bei uns eher nebenbei laufen wird.

Hier besteht ganz klar Bedarf an einer erfinderischen Lösung ;-)

Gruß Oliver

--
Oliver Bartels + Erding, Germany + obartels@bartels.de
http://www.bartels.de + Phone: +49-8122-9729-0 Fax: -10

Zumindest für die Entscheidung ausgewertet / unausgewertet bringt das nichts. Es bringt was bei Pattern Matching a la data Complex = R Int | C Int Int add (R a) (R b) = R (a+b) add (R a) (C br bi) = C (a+br) bi add (C ar ai) (R b) = C (ar+b) ai add (C ar ai) (C br bi) = C (ar+br) (ai+bi) Aber bei unausgewerteten Parametern ist die Reaktion immer die gleiche: auswerten. Zumal es da auch unendlich viele Fälle geben kann, da ja der Parameter ein beliebig komplizierter Parameter sein kann. Damit bringt es IMHO kaum was, hier auf den Fall 'add ' zu spezialisieren o.ä.

Mit einem Befehl a la 'addcu' wollte ich primär erreichen, dass ein Ausdruck 'foo = a*b + c - d' ganz klassisch compiliert werden kann mov r0, a mulcu r0, b, label1 addcu r0, c, label2 subcu r0, d, label3 und im Normalfall in 4 Takten durchläuft. Nicht wie heute mit dutzenden Sprüngen.

Als Hobby-Compilerbauer würde ich das "nicht so schwer" bezweifeln. Ich kann mir momentan jedenfalls nichts vorstellen, was nicht Compilezeit und/oder Codegröße explodieren lässt.

(Ich habe ein paar Theorie-Resultate unserer Uni implementiert, wo neue Funktionen 'fg(x)' synthetisiert werden, die einen Aufruf 'f(g(x))' direkt ohne Zwischenergebnis berechnen. Insbesondere in Anwesenheit von separater Compilierung stellt sich hier sofort die Frage: welche f kombiniere ich mit welchen g, ohne den Operator fragen zu müssen? Die letztenendes gewählte Lösung kombiniert alles, was irgendwie zueinander passt, und hofft darauf, dass der Linker schon aufräumen wird.)

Ja, und da ist IMHO das Problem, dass auch Fließpunkt heutzutage

*verdammt* schnell ist. Jedenfalls auf PC-Hardware. (Mit Floating-Point- DSPs hatte ich noch nicht das Vergnügen, aber die werden wohl auch nicht gerade langsam sein.)

Ich hab eine Zeitlang einfache digitale Filter mit Emacs-Lisp synthetisiert. Hätte ich nen Hugs gehabt, hätte ich den genommen.

Stefan