Hi Leute
ich suche eine Möglichkeit das Durchsuchen eines Arrays von
Funktionspointer zu beschleunigen. (nutze jetzt lineare Methode)
Wenn der Compiler (bzw der spätere optimier Algo) eine Jumptable erzeugt
kann er die Einträge doch tauschen (sortieren), oder?
Beispiel:
1
switch(d){
2
case5:
3
break;
4
case9:
5
break;
6
case3:
7
break;
8
case7:
9
break;
10
}
dann macht er doch draus (intern) 3, 5, 7, 9 oder so.
Könnte ich dann diese Optimierung auch bei meinem Array irgendwie
nutzen?
Oder geht das nur wenn ich so eine Switch Abfrage mache?
Mein Array liegt zur Zeit nur im Flash, da es zu groß ist um es noch ins
RAM zu kopieren!
Für Tips wäre ich sehr dankbar.
1)Als alternative hatte ich mir überlegt das ich mir zb. eine Anzahl x
der letzten Suchergebnisse merke und diese erst prüfe, aber das wurde
hier nicht beführwortet.
2) oder ich speichere das Array später in einem EEProm und sortiere es
dort
aber das kostet auch wieder Zeit. (ein Teil lesen + vergleichen, wieder
lesen und vergleichen usw.)
Stephan
>> dann macht er doch draus (intern) 3, 5, 7, 9 oder so.> Könnte ich dann diese Optimierung auch bei meinem Array irgendwie> nutzen?> Oder geht das nur wenn ich so eine Switch Abfrage mache?
Die eigentliche Frage lautet doch:
Was weißt du alles über dein d?
Sind das fortlaufende Werte? In welchem Wertebereich bewegen sich die?
> Für Tips wäre ich sehr dankbar.> 1)Als alternative hatte ich mir überlegt das ich mir zb. eine Anzahl x> der letzten Suchergebnisse merke und diese erst prüfe, aber das wurde> hier nicht beführwortet.
Kommt immer drauf an.
Wenn dieser Fall oft eintritt, kann man mit Cachen schon was rausholen.
Aber erst mal die naheliegende Variante. Was weißt du über dein d?
Ist es möglich das Array so
func[d]();
zu benutzen oder nicht? Gegebenenfalls auch mit einer einfachen
Umrechnung von d in einen anderen Wertebereich und auch unter dem
Zugeständnis dass vielleicht ein paar Arrayelemente für immer NULL
bleiben, weil sich deren Index nie aus dem d ergeben wird.
Wird das Array der Funktionspointer etwa dynamisch zur Laufzeit befüllt?
(Allerdings sehe ich da nicht, wie da ein switch-case jetzt in irgend
einer Form reinspielen würde).
Also: zeig doch mal ein wenig mehr von deiner realen Situation und
weniger irgendwie zurecht gemachtes, von dem du denkst das es
weiterhelfen könnte.
Hi,
ok hier mal ein kleines Array mit Pointern:
Das ist nur für die Spannungen. Die Funktionen liegen ja im meinem
C-Code irgendwo in text-Section.
In meinem Prog. weiß ich, das ich als nächstes zur Funktion z.B.:
'outputConfigOffsetSenseVoltage' springen muss, das hat ein Parser
erkannt, jetzt werden aber vorher noch Checks durchgeführt die bestimmte
Parameter benötigen z.B. min, max, auflösung usw. und anhand der
Funktion 'outputConfigOffsetSenseVoltage' werden diese ermittelt. Dazu
muss ich den Funktionspointer ersmal in meinem Array finden.
Früher hatte die lineare Suche ausgereicht, nun aber ist eine Tab für
Strom, Temperatur, Fans usw. dazu gekommen was die Suche etwas dauern
läßt.
Mein Beispiel hatte ich aus einem Vergleich von Bitabfragen von einem
Drehschalter (min, max von d war bekannt), mein Compiler hat dies als
Jumptable übersetzt.
Mein Array ist const und im Flash.
Stephan
Wenn ich Dich richtig verstehe, bekommst Du irgendwoher die Information,
welche Funktion Dein Programm ausführen soll, d.h. Du mußt doch irgendwo
eine Zuweisung haben wie
Hi Bronco,
ja so ähnlich mache ich das ja auch, aber da der Parser ein closed
SW-Part ist kann ich da nichts ändern.
Wir haben uns sozusagen zwischen den Parser und der aufzurufenden
Funktion gesetzt um weitere Parameter zu übergeben.
ich will eigendlich nur die Funktionspointer sortiert im Flash stehen
haben, so das ich dann mit einem geeigneten Suchalgo. die Funktion
suchen und die Param. weitergeben kann.
Wäre denn die switch- case Variante schneller? als das lineare Suchen im
unsortierten Array?
Ein B-Baum ist vielleicht etwas überdimensioniert für einen armen
kleinen Controller, aber binäre Suche ist sicher angemessener.
Wobei sich selbst das gegenüber linearer Suche erst bei mehr als wenigen
Dutzend Einträgen lohnt...
Wenn du richtig kodierst, brauchst du keine Auswahl (z.b. per switch),
sondern kennst direkt den Index im "Funktionstable". Das ist mit
Sicherheit schneller, als B-Bäume auf einem uC zu bauen. Pfff....
Ich akzeptiere, dass man den Parser nicht angreifen will. Allerdings ist
mir nicht klar, warum man dem Parser nicht einfach andere
Funktionspointer unterjubeln kann. Dann kommt der eben nicht mit einem
FUnktionspointer für outputConfigOffsetSenseVoltage daher, sondern mit
einem Funktionspointer zu einer Funktion, die eben vorher die Parameter
besorgt oder überprüft und dann ihrerseits
outputConfigOffsetSenseVoltage aufruft.
Auf die Art muss überhaupt nichts gesucht werden.
Und wenn man an die Funktionspointer im Parser überhaupt nicht rann
kommt, dann kann man immer noch den Funktionsrumpf von
outputConfigOffsetSenseVoltage gegen einen austauschen, der diese
Zusatzleistung macht und dann den originalen Funktionsrumpf aufruft.
Oder ist da noch eine Zutat, wie zb RPC, im Spiel?
Oder ist der Funktionspointer gar kein richtiger Funktionspointer, über
den man eine Funktion aufrufen kann?
Irgendwie merkwürdig das Ganze.
Genau deswegen nimmt man ja Funktionspointer, damit man eben nicht
anhand einer ID erst mühsam die Funktion eruieren muss, die aufzurufen
ist, sondern den Call direkt über den Pointer machen kann. Irgendwie
führt diese Zusatzfunktionalität jetzt das ganze Prinzip ad absurdum.
Stephan schrieb:> Wäre denn die switch- case Variante schneller? als das lineare Suchen im> unsortierten Array?
ja, weil der Compiler i.d.R. aus dem switch eine Sprungtabelle macht,
und den switch-Wert als Index für den Sprung.
Insofern kannst du das mit einer eigenen Sprungtabelle auch nicht
schneller machen.
Deshalb verstehe ich immer noch nicht, was dir am switch missfällt.
Hi Leute,
danke für die Antworten.
Wie gesagt momentan läuft es über das Array und die Geschwindigkeit
lässt leider langsam nach. Ich bekam die Aufgabe nun dies zu
überarbeiten.
Ich hab mich in den Code nun eingearbeitet und im Team die Vorschläge
s.o. gemacht. Jedoch wurden beide nicht mit vollster Zustimmung
angenommen.
Daher die Suche nach weiteren Varianten. An den Parser kommen wir nicht
dran, ist von extern! daher der Umweg über eine andere Funktion. Ist von
Anfang an so gemacht worden (vor meiner Zeit).
Der Parser kann nur 'Void'-Funktionen aufrufen (leider), hat aber eine
Pre-Call-Funktion (Event) die hier aktiviert wurde, In der dann die
Parameter aktiviert bzw lokalisiert werden.
Bevor ich jetzt die ganzen Arrays zu Testzwecken mal auf eine
Switch-Case Abfrage umbaue, wollte ich noch mal hier nachfragen ob es
überhaupt Sinn macht.
Ich werds morgen mal testen und schauen was geht.
Mir ist noch eine andere Möglichkeit eingefallen:
Ich ändere einfach das Sprung-Ziel, ich lass den Parser erst zu einer
Funktion springen der die Parameter setzt und dann weiter zur
Endgültigen Funktion springen. Ich muss noch schauen ob ich dann noch
alle Daten zur Verfügung habe, aber vielleicht geht es ja.
nochmal Danke.
Stephan
Stephan schrieb:> Wie gesagt momentan läuft es über das Array und die Geschwindigkeit> lässt leider langsam nach.
Wie das?
Ein Arrayzugriff ist unabhängig von der Größe.
Der Compiler addiert den Index zur Array-Startadresse und liest von
dieser Adresse die Daten, fertig.
Aber schreib es besser als switch/case. Dann kann der Compiler selber
den optimalen Weg aussuchen (Compare-Baum oder Sprungtabelle).
Peter
Wie geht das mit switch case?
Es wird doch nach Funktionszeigern gesucht. Funktionen haben zwar fixe
Adressen, diese sind zur Compilerzeit aber nicht bekannt und können
daher nicht in als switch/case Labels verwendet werden.
Peter Dannegger schrieb:> Stephan schrieb:>> Wie gesagt momentan läuft es über das Array und die Geschwindigkeit>> lässt leider langsam nach.>> Wie das?> Ein Arrayzugriff ist unabhängig von der Größe.
Ein einzelner Zugriff schon, aber eine Suche nicht.
Morgen,
sorry, Johann L. hat ja recht. Der Compiler nimmt es nicht an.
Ich war mir sicher das ich das schonmal vorher gesehen habe.
Hab mich scheinbar geirrt.
>Ein einzelner Zugriff schon, aber eine Suche nicht.
genau.
Stephan
Karl Heinz Buchegger schrieb:> Und wenn man an die Funktionspointer im Parser überhaupt nicht rann> kommt, dann kann man immer noch den Funktionsrumpf von> outputConfigOffsetSenseVoltage gegen einen austauschen, der diese> Zusatzleistung macht und dann den originalen Funktionsrumpf aufruft.
Warum holen sich nicht outputConfigOffsetSenseVoltage und die anderen
Listenfunktionen die benötigten Parameter selber? Dann muß gar nichts
mehr gesucht werden, jede Funktion kennt ihren Index ins Parameterarray.
Oliver
Stephan schrieb:> Ich werds morgen mal testen und schauen was geht.
Was ich noch sagen wollte:
Wie groß ist denn euer Array von Funktionspointern?
Hast du mit dem Profiler verifiziert, dass tatsächlich diese Suche ein
Bottleneck darstellt? Oder schätzt ihr nur, das dem so ist?
Wenn ich mir so durch den Kopf gehen lasse, was ein Parser so alles zu
tun hat, kann ich mir nicht wirklich vorstellen, dass eine lineare Suche
in einem Array mit 30 oder 40 Einträgen da signifikant zur Laufzeit
beträgt. Möglich ist aber alles, daher sollten erst mal aussagekräftige
Zahlen in Form einer Untersuchung mit dem Profiler her.
> Mir ist noch eine andere Möglichkeit eingefallen:> Ich ändere einfach das Sprung-Ziel, ich lass den Parser erst zu einer> Funktion springen der die Parameter setzt und dann weiter zur> Endgültigen Funktion springen.
Das wäre sowieso die einfachste Lösung. Mag zwar im Moment etwas mehr
Änderungsaufwand bedeuten, aber dann ist das 'Problem' (sofern es
überhaupt eines war) auf jeden Fall vom Tisch. Zusätzlich wird auch die
Gesamtstruktur überschaubarer.
Ansonsten: Wenn es ein Dogma ist, dass die jetzige Struktur
grundsätzlich nicht groß geändert wird: Das Array mit den
Funktionspointern einmalig sortieren und dann binär suchen anstatt
linear. Ab, ich würde mal aus dem Bauch sagen, 20 oder 30 Einträgen
gewinnt dann die logarithmische Suchzeit gegenüber dem Mehraufwand.
Programmieraufwandsmässig hält sich as ganze auch in Grenzen, weil du ja
in der Runtime-Library fertige Funktionen qsort und bsearch zur
Verfügung hast.
Stephan schrieb:>>Ein einzelner Zugriff schon, aber eine Suche nicht.> genau.
Dann erzähl dochmal, wonach gesucht werden soll.
Ich werde aus dem bisherigen überhaupt nicht schlau.
Allgemein kann man ein Suche beschleunigen, indem man die Anzahl der
Suchschritte reduziert. Dazu muß man aber wissen, nach welcher Regel die
Suche erfolgt.
Oder man beschleunigt den Suchschritt selber.
Eine Array ist ja keine Suche, sondern nur die Umsetzung einer Zahl in
eine andere, z.B. ein Index in einen Funktionspointer.
Peter
Besteht die Möglichkeit von überwachten Testläufen?
Vorsortieren und Umstrukturieren bringt nur was, wenn es Häufigkeiten
bzw. Schwerpunkte gibt.
Manchmal reichen sehr einfache Umstrukturierungen aus um die Laufzeit zu
reduzieren.
Super-Simpel-Beispiel:
case 0:
case 1:
case 2:
case 3:
case 4:
Im Versteckten bedeutet dies If 0 ... If 1 ... If 2...
Wenn deine Untersuchungen aber ergeben, dass der Fall "3" am häufigsten
vorkommt, so kannst Du die Anzahl an Abfragen reduzieren indem Du
einfach die Abfragereihenfolge änderst.
Die geänderte Abfrage lautet jetzt:
case 3:
case 0:
case 1:
case 2:
case 4:
Das bringt natürlich nur was, wenn Du auch reale Daten hast.
Sollten die oben verwendeten Werte tatsächlich Zahlen sein, so kann eine
Sprungtabelle oder die Binärsuche das Ganze stark beschleunigen.
Peter Dannegger schrieb:> Stephan schrieb:>>>Ein einzelner Zugriff schon, aber eine Suche nicht.>> genau.>> Dann erzähl dochmal, wonach gesucht werden soll.> Ich werde aus dem bisherigen überhaupt nicht schlau.
Ich habs mir bis jetzt so zusammengereimt.
Das ist die grundsätzliche Sytsemstruktur. Da gibt es einen Parser, der
Input analysiert und aufgrund der Analyse eine Funktion in Form eines
Funktionspointers bestimmt, der die Aktion dann implementiert.
Input
|
v
+-------------+
| Parser |
| |
| p bestimmen |
| |
| DoIt( p ) |
| ------------+ Funktionspointer
+-------------+ | der Funktion, die aufgrund eines
| Keywords im Input aufzurufen ist
v
+-----------------------+
| Runtime, die im |
| Prinzip einfach |
| nur über den Func- |
| pointer die ent- |
| sprechende Funktion |
| auführt |
| |
| void DoIt( FuncPtr p )|
| { |
| p(); |
| } |
+-----------------------+
Jetzt gibt es da noch eine Möglichkeit, das der Parser vor dem 'DoIt'
noch eine andere Funktion aufrufen kann, die anhand des festgestellten
Funktionspointers noch Modifikationen oder sonstige Dinge machen kann.
Input
|
v
+-------------+
| Parser |
| |
| p bestimmen |
| |
| PreCall( p )--------------> void PreCall( FuncPtr p )
| | { ... }
| DoIt( p ) |
| ------------+ Funktionspointer
+-------------+ | der Funktion, die aufgrund eines
| Keywords im Input aufzurufen ist
v
+-----------------------+
| Runtime, die im |
| Prinzip einfach |
| nur über den Func- |
| pointer die ent- |
| sprechende Funktion |
| auführt |
| |
| void DoIt( FuncPtr p )|
| { |
| p(); |
| } |
+-----------------------+
Und genau in diesem 'PreCall' sitzt jetzt sein Problem. Er hat nur den
Funktionspointer der aufzurufenden Funktion und muss den benutzen um
festzustellen, welche Aktionen er machen möchte, ehe dann der
eigentliche Aufruf der Funktion erfolgt. (zb Parameter bereitstellen).
D.h. er sucht in einem Array, in dem alle Funktionszeiger enthalten
sind, nach dem Index im Array und dieser Index sagt ihm daher, welche
Vorbereitungsschritte notwendig sind.
So hab ich das verstanden.
(Und ich finds ehrlich gesagt bescheuert. Was'n das für ein Parser, wenn
ich dann zum Argument-besorgen und überprüfen derartige Klimmzüge machen
muss. Sowas muss ein Parser out of the box mithaben, dass man solche
Dinge in der Parserbeschreibung erledigen kann)
Ich glaube, mir dämmerts. Er will das Array rückwärts benutzen, also vom
Funktionspointer zurück zum Index.
Ich sehe da allerdings nichts zeitkritisches, einfach in einer Schleife
zu vergleichen.
Es sei denn es sind wirklich viele Funktionen (>1000).
Peter
Peter Dannegger schrieb:> Ich sehe da allerdings nichts zeitkritisches, einfach in einer Schleife> zu vergleichen.
Seh ich auch so.
Auf der anderen Seite ist es auch nicht schwer, da erst mal Abhilfe zu
schaffen
* im Vorfeld einmalig ein qsort() auf das Array
* und dann mit einem bsearch() suchen, anstelle der Eigenbausuche.
Die Funktionen gibt es ja schon. Da muss er nichts selber erfinden und
der Rest kann erst mal so bleiben wie er ist.
Peter Dannegger schrieb:> Ich glaube, mir dämmerts. Er will das Array rückwärts benutzen, also vom> Funktionspointer zurück zum Index.
Ich dachte, daß er statt der Funktion eine andere aufrufen will und
daher quasi ein Mapping von einem Funktionszeiger zu einem anderen will.
Aber es gibt wohl viele Theorien darüber, was der Ursprungsposter will.
Karl Heinz Buchegger schrieb:> Auf der anderen Seite ist es auch nicht schwer, da erst mal Abhilfe zu> schaffen> * im Vorfeld einmalig ein qsort() auf das Array> * und dann mit einem bsearch() suchen, anstelle der Eigenbausuche.
Das geht aber wohl nicht, denn:
Stephan schrieb:> Mein Array liegt zur Zeit nur im Flash, da es zu groß ist um es noch ins> RAM zu kopieren!
Das Sortieren müßte also Compiler und/oder Linker übernehmen, und die
ursprüngliche Frage war, ob man die irgendwie dazu bringen kann.
Das ist immer die Sache, wenn man nicht sein eigentlich Problem
erläutert, sondern nur die Schwierigkeiten bei der Lösungsvariante, die
man sich überlegt hat. Sowas führt immer nur zu Verwirrung.
Peter Dannegger schrieb:> Ich glaube, mir dämmerts. Er will das Array rückwärts benutzen, also vom> Funktionspointer zurück zum Index.>> Ich sehe da allerdings nichts zeitkritisches, einfach in einer Schleife> zu vergleichen.
Was eventuell stören könnte, wäre, daß es unterschiedlich lange dauert,
bis er die aufzurufende Funktion gefunden hat, jenachdem wie weit hinten
im Array die gesuchte Funktion liegt.
Aber das kann man problemlos ausrechnen und schauen, ob die Laufzeit im
Worst-Case noch okay ist.
Ich denke, seine ursprüngliche Annahme war, daß der C "Switch" so
funktioniert, daß man die Adressen als Cases anlegt und dann direkt
anspringt (ohne langes Suchen), ohne daß man dabei alle anderen Adressen
auch als Cases benötigt. So etwas würde scho ngehen, aber nur, wenn man
den Adressraum der Funktionen ganz extrem einschränkt.
Ich hab tatsächlich mal eine Anwendung gesehen, wo ein C517A
CAN-Adressen mit einem 64kB großen Switch sortiert hat. Damit war aber
das Flash komplett voll.
Peter Dannegger schrieb:> Dann erzähl dochmal, wonach gesucht werden soll.> Ich werde aus dem bisherigen überhaupt nicht schlau.
Hat bei mir auch gedauert ;-)
> Eine Array ist ja keine Suche, sondern nur die Umsetzung einer Zahl in> eine andere, z.B. ein Index in einen Funktionspointer.
Ein Array ist eine Abbildung einer hanzeh Zahl >= 0 zu einem
(Funktions)pointer.
Was er brauch, ist die schnelle Berechnung der Umkehrfunktion.
Lösung #1:
Compiliere die Applikation mit -ffunction-sections und linke mit
--sort-section=name.
Zu Beginn der Applikation wird das Array der Größe nach sortiert (was
allerdings voraussetzt, daß das Array im RAM liegt), etwa mit qsort.
Zur Bestimmung der Umkehrfunktion geht dann eine binäre Suche auf das
Pointer-Array.
Um den Resource-Bedarf zu reduzieren kann der Parser das Array auch auch
so ablegen, daß die Funktionsnamen darin bereits lexikographisch
geordnet sind, oder ein Post-Prozessing Tool sortiert das Array nach den
Funktionsnamen (und damit wegen --sort-section=name auch deren
Adressen).
Schön ist das aber nicht.
Lösung #2:
Man legt kein Array mit Pointern an, sondern verwendet statt der Zeiger
IDs. Eine ID ist eine ganze Zahl, die eineindeutig einer Funktion
zugeordnet werden kann.
In der Folge hantiert man nur noch mit diesen IDs und wenn man die dazu
gehörende Funktion braucht, greift man in ein entsprechendes
Lookup-Array mit den Zeigern.
Thread beobachten
Seitenaufteilung abschalten