LUT für float

m.mickey

Hallo Forum,

ich habe sehr viele float Multiplikationen durchzuführen, sodass sich rechnerisch LUT lohnt. Das Problem, ich arbeite mit float Daten.

Die Daten haben alle Werte zwischen 0.0 und 1.0, deshalb war die Idee ein LUT für die 23Bit der Mantisse zu erzeugen (auch wenn das nicht meine Idee war ).

Jedoch habe ich keine Ahnung, wie ich effizient die Mantisse als 32Bit Integer auslesen kann. (Das Erzeugen eines LUT an sich, also für Integer Daten ist mir klar.)

Über Hinweise oder Links dazu wäre ich dankbar. (C oder C++ ist egal, effizienter ist besser )

Viele Grüße mickey

pumuckl

m.mickey schrieb:

deshalb war die Idee ein LUT für die 23Bit der Mantisse zu erzeugen

Dir ist hoffentlich klar, dass das nicht portabel ist, weil nirgendwo garantiert ist, dass ein float genau 23 Bit in der Mantisse hat. Du solltest also, falls nicht sowieso festgelegt ist, dass das Ganze nur auf einem speziellen Syste läuft, die Sache so implementieren, dass die LUT nur dann benutzt wird, wenn du tatsächlich auf einem 23-Bit-Mantissen-System bist. Die Zahl findest du in std::numeric_limits<float>::digits im header <limits>. Dort findest du auch die anderen Ziffern die wichtig sind, und zwar zur Compilezeit. Damit kannst du dann schon zur Compilezeit das nötige Werkzeug für folgende Schritte zusammenbauen:

Herausfinden, auf welche 23 Bits die Mantisse steht
Mittels reinterpret_cast den wichtigen Teil des Float in einen unsingned int oder unsigned long kopieren
Das Ergebnis so bitshiften, dass die niedirgsten 23 Bits mit der float-Mantisse belegt sind
Mit bitand den Rest auf 0 setzen.

Wie gesagt das Ganze ist nicht portabel, man kann es aber mit ein wenig Templatemagie soweit hinbekommen, dass es auf den meisten gängigen Systemen richtig läuft und andernfalls einfach nicht kompiliert.

camper

ldexp/frexp dürften hier die richtigen Funktionen sein.

m.mickey schrieb:

ich habe sehr viele float Multiplikationen durchzuführen, sodass sich rechnerisch LUT lohnt.

Wie kommst Du darauf?

m.mickey schrieb:

Jedoch habe ich keine Ahnung, wie ich effizient die Mantisse als 32Bit Integer auslesen kann. (Das Erzeugen eines LUT an sich, also für Integer Daten ist mir klar.)

Mir nicht. Ich weiß nicht, was Du genau machen willst.

pumuckl schrieb:

Mittels reinterpret_cast den wichtigen Teil des Float in einen unsingned int oder unsigned long kopieren

Was meinst Du? Das Verhalten von

uint_typ blah = reinterpret_cast<uint_typ const&>(mein_float);

ist meines Wissens undefiniert. Siehe §3.10/15 im C++ Standard. ("If a program attempts to access the stored value of an object through an lvalue of other than one of the following types the behaviour is undefined...")

Besser:

uint_typ blah;
memcpy(&blah, &mein_float, sizeof(blah));

Bashar

1.) Was soll eine LUT hier bringen? Wie genau soll hier irgendwas beschleunigt werden? Wieviele Einträge soll die überhaupt haben?

2.) Warum nur die Mantisse? Den Exponenten gibt es nicht zum Spaß, der gehört zur Eindeutigkeit der Zahl dazu.

m.mickey

Erstmal danke für eure Antworten.

@pumukel: Nein, dass es vom System abhängt war mir nicht klar. Danke auch für ie Hinweise wo ich mehr dazu finde...

Ich habe mehrere Millionen gleichartiger Rechnungen (Bildbearbeitung, 32bit float nach 16bit Integer und umgekehrt) und da ein look up deutlich weniger kostet als immer wieder neu rechnen... (zumindest wenn die Mantisse "billig" bestimmt werden kann.)

Viele Grüße mickey

m.mickey schrieb:

Ich habe mehrere Millionen gleichartiger Rechnungen (Bildbearbeitung, 32bit float nach 16bit Integer und umgekehrt) und da ein look up deutlich weniger kostet als immer wieder neu rechnen...

Wie kommst Du darauf?

m.mickey

krümelkacker schrieb:

m.mickey schrieb:

Ich habe mehrere Millionen gleichartiger Rechnungen (Bildbearbeitung, 32bit float nach 16bit Integer und umgekehrt) und da ein look up deutlich weniger kostet als immer wieder neu rechnen...

Wie kommst Du darauf?

Du kannst es mir auch gerne erklären (Kommt besser als nur schnippische Kommentare )

Viele Grüße mickey

m.mickey schrieb:

Du kannst es mir auch gerne erklären

Du kannst gerne mal erklären, was Du eigentlich machen willst. Wenn Du Bilder zwischen 16 und 32 bit/pixel konvertieren willst, wobei die Werte einfach nur skaliert werden, dann sehe ich nicht, wie Dir ein LUT hilft. Das riecht eher nach "premature optimization".

hustbaer

@m.mickey:
Was für CPU, was für System, welche Berechnung, wie viele Daten, ...?

Wenn du z.B. nur multiplizieren willst... SSE2 ist da unglaublich flott. Vor allem weil du je 4 Werte zugleich verwursten kannst.

m.mickey

hustbaer schrieb:

@m.mickey:
Was für CPU, was für System, welche Berechnung, wie viele Daten, ...?

Wenn du z.B. nur multiplizieren willst... SSE2 ist da unglaublich flott. Vor allem weil du je 4 Werte zugleich verwursten kannst.

Systeme sind normale Desktoprechner oder für die hartgesottenen Laptops... Parallelisierung läuft mit OpenMP, momentan für Windows und Linux (da es QT verwendet ist eine Portierung auf Mac denkbar...)
Ist im Wesentlichen ein Programm das Teile der Funktionalität von Lightroom zur
Verfügung stellt. Um Speicher und Rechenzeit zu sparen laufen viele Teile auf unsigned 16 Bit Integer, allerdings sind einige Filter auf Float im Bereich 0.0 und 1.0 angewiesen, es wird also häufig hin und her konvertiert... Im wesentlichen Integer/0xffff und Float*0xffff...

Viele Grüße mickey

hustbaer

Dann würd ich mir wirklich mal SSE angucken. z.B. da:

http://msdn.microsoft.com/en-us/library/tb8tkdha.aspx
und da:
http://msdn.microsoft.com/en-us/library/yk5x06zy.aspx

Hab mich im Übrigen vertan: du brauchst natürlich SSE und nicht SSE2...
Aber egal.

m.mickey schrieb:

Um Speicher und Rechenzeit zu sparen laufen viele Teile auf unsigned 16 Bit Integer, allerdings sind einige Filter auf Float im Bereich 0.0 und 1.0 angewiesen, es wird also häufig hin und her konvertiert... Im wesentlichen Integer/0xffff und Float*0xffff...

Wieso hast du viele Teile auf unsigned 16 Bit Integer, um Rechenzeit zu sparen, wenn dich das Konvertieren dann wieder soviel Zeit kostet? Wieviel Prozent der Zeit macht das konvertieren denn aus?

Ein Speicherzugriff auf einem aktuellen Computer ist sehr sehr viel langsamer, als eine Gleitkomma-Rechnung. Sobald die Tabelle größer als der L1-Cache ist, kannst du es total vergessen. Wahrscheinlich hast du eh sehr viele Daten zu verarbeiten, was nahe legt, dass nicht der Prozessor, sondern der Speicher zu langsam ist.

hustbaer

ProgChild schrieb:

Ein Speicherzugriff auf einem aktuellen Computer ist sehr sehr viel langsamer, als eine Gleitkomma-Rechnung. Sobald die Tabelle größer als der L1-Cache ist, kannst du es total vergessen. Wahrscheinlich hast du eh sehr viele Daten zu verarbeiten, was nahe legt, dass nicht der Prozessor, sondern der Speicher zu langsam ist.

Nö.
Der Speicher ist heutzutage eigentlich sehr sehr flott bei sequenziellen Zugriffen. Man tut sich schon schwer mit reinen Kopierschleifen (mit nur einem Core) die Geschwindigkeit des Hauptspeichers auszunutzen. Von irgendwelchen Algorithmen die dann noch Berechnungen machen müssen ganz zu schweigen.
Und auch der L2 Cache ist nicht SO lahm wie du uns hier weismachen willst (AFAIK 10 cycles Latenz beim i7).

Was wirklich immer noch langsam ist, sind Zugriffe die für die Predictor-Logik der CPU unvorhersagbar sind, und die auch wirklich in den Hauptspeicher durchgehen.

Shade Of Mine

hustbaer schrieb:

Der Speicher ist heutzutage eigentlich sehr sehr flott bei sequenziellen Zugriffen.

Bei so einer LUT hast du aber Random Access ueber Page-Grenzen hinweg.

Aber klar, sequentielle Zugriffe sind enorm schnell, was teuer ist sind aber die page faults...

hustbaer schrieb:

Und auch der L2 Cache ist nicht SO lahm wie du uns hier weismachen willst (AFAIK 10 cycles Latenz beim i7).

Ja. Er versucht eine einzelne Gleitkomma-Multiplikation wegzuoptimieren... Wie lange braucht die nochmal?

hustbaer

ProgChild schrieb:

hustbaer schrieb:

Und auch der L2 Cache ist nicht SO lahm wie du uns hier weismachen willst (AFAIK 10 cycles Latenz beim i7).

Ja. Er versucht eine einzelne Gleitkomma-Multiplikation wegzuoptimieren... Wie lange braucht die nochmal?

Ja. Und?

Wahrscheinlich hast du eh sehr viele Daten zu verarbeiten, was nahe legt, dass nicht der Prozessor, sondern der Speicher zu langsam ist.

Das legt nahe dass du das "Speicherzugriff ist sehr sehr viel langsamer" auf das Lesen und Schreiben der zu konvertierenden Daten beziehst.
Und das ist genau kein Problem. Um dabei vom Speicher ausgebremst zu werden muss man sich schon ordentlich ins Zeug legen.

Nichts anderes hab ich geschrieben.

Und selbst auf die LUT bezogen: Faktor 10 oder um was es sich da reissen wird ist für mich nicht "sehr sehr viel langsamer". Eher "viel langsamer". Aber das ist natürlich Ansichtssache.

hustbaer

Shade Of Mine schrieb:

hustbaer schrieb:

Der Speicher ist heutzutage eigentlich sehr sehr flott bei sequenziellen Zugriffen.

Bei so einer LUT hast du aber Random Access ueber Page-Grenzen hinweg.

Aber klar, sequentielle Zugriffe sind enorm schnell, was teuer ist sind aber die page faults...

Page-Grenzen sind vollkommen egal.
Page-Faults hast du auch nur beim 1. Durchlauf des Algorithmus', danach wird das OS die Seiten wohl hoffentlich nicht sofort auslagern.

Aber mal davon abgesehen dass es darum geht was gerade im Cache ist und was nicht: dass Random-Access böse ist (weil langsam) ist mir schon klar. Nur dass ich die Darstellung von ProgChild einfach für übertrieben bzw. falsch halte.

Vielleicht hab' ich ihn auch nur falsch verstanden, aber sein Beitrag liest sich für mich so, als wolle er behaupten, dass der Algorithmus so-oder-so vom Speicherzugriff limitiert sein wird, ganz egal ob mit oder ohne LUT, weil der OP so viel Daten umwandeln will.
Und das ist nunmal Unfug^3.

hustbaer schrieb:

Das legt nahe dass du das "Speicherzugriff ist sehr sehr viel langsamer" auf das Lesen und Schreiben der zu konvertierenden Daten beziehst.
Und das ist genau kein Problem. Um dabei vom Speicher ausgebremst zu werden muss man sich schon ordentlich ins Zeug legen.

Nö. Brauchst nur bei einem 2D-Array die falsche Reihenfolge der Indizes verwenden.

hustbaer schrieb:

Nur dass ich die Darstellung von ProgChild einfach für übertrieben bzw. falsch halte.

Vielleicht hab' ich ihn auch nur falsch verstanden, aber sein Beitrag liest sich für mich so, als wolle er behaupten, dass der Algorithmus so-oder-so vom Speicherzugriff limitiert sein wird, ganz egal ob mit oder ohne LUT, weil der OP so viel Daten umwandeln will.

Nein. Meine Aussage war, dass er mit eine Tabelle eine einzelne Gleitkomma-Operation nicht schneller bekommt.

hustbaer

Das wolltest du vielleicht sagen, aber für mich war es nicht verständlich.
Für mich kam nur rüber "Speicher is langsam".