Ich beschäftige mich gerade etwas intensiver mit String-Matching-Algorithmen (also das, was pos macht) und bin da auf einen heute etwas kurios erscheinenden Artikel gestoßen. Dort wird u.a. ein Verfahren vorgestellt, was ganz besonders gut auf Maschinen der IBM 360-370 Reihe läuft, oder auch auf dem dazu kompatiblen Amdahl V7 Computer. Der Artikel ist von 1980, die 360-370er Serie sind Schränke.

Dabei wird vorausgesetzt, dass die Hardware eine Anweisung kennt, die es ermöglicht, bis zu 256 Zeichen (gleichzeitig) auf das Vorkommen eines bestimmten Characters hin zu untersuchen. Es ist da von "Translate and Test (TRT)" die Rede, oder auch von "Search While not equal (SNEU)", was wohl der Burroughs B6500 kann, während der UNIVAC 1100 die Anweisung "Search Equal (SE)" hat.

Gibt es auf den heutigen PC-Architekturen auch eine solche Anweisung, oder ist das ein Relikt aus den Zeiten, wo "moderne Computer in einen Raum passten"? Mir ist klar, dass sich das softwareseitig mit einer einfachen Schleife lösen lässt, aber das ist nicht der Punkt - es geht hier um die Effizienz des Verfahrens.

bin mir nicht wirklich sicher, was du machen willst, aber mir kam spontan der scasb-Befehl in den Sinn

de.wikibooks.org/wik...erung:_Stringbefehle

hab jetzt nicht nachgeguckt, aber wenn du weiter schmöckerst, wirst du feststellen, dass diese kisten auch indexsequentielle dateiverarbeitung (mit einem assemblerbefehl) drauf hatten. aber nicht nur, die ibm kisten, auch bspw. die vax'n. gefunden hab ich so etwas ähnliches bislang noch nie auf 'ner pc architektur. aber vielleicht kennt ja jemand 'n befehl und strings effizient zu verarbeiten und diese indexsequentiell zu speichern und zu lesen.

der TRT befehl testet auf eine beliebige anzahl (0 bis 255) von char im string. der scas, scasb, scasw, scasd, scasq nur auf eine spezifizierte anzahl (je nach opcode von 1 bis 8 byte) von zeichen. der opcode vom TRT ist jedoch der selbe, egal wie viele (bis 255) bytes im string gesucht werden.

Was die Effizienz des Verfahrens angeht... steht in Deinem Manual da auch, wie viele Cycles dieser Befehl benötigt? Plus Speicherzugriffe... Wenn Du Effizienz nur danach bemisst, wie viele Opcodes Du für eine bestimmte Aufgabe brauchst, hast Du natuerlich recht, allerdings kann auf einer anderen Hardwarearchitektur eine Schleife durchaus schneller ablaufen, womit sich dann wieder die Frage stellt, welche Kategorien man zur Bewertung heranziehen will. Ich erinnere mich da an die Anekdote mit dem Acorn Archimedes auf ner Messe kurz vor Markteinführung. Auf dem Ding lief eine 3D-Animationsdemo, für die damalige Zeit (1987) ziemlich abgefahrener Kram. Richtig blass wurden die Zuschauer auf dem Stand erst, als ein Techniker das Basic-Programm (!) das die Animation zeichnete abbrach und eine Warteschleife (!!!) entfernte - und die Animation danach mit mehrfacher Geschwindigkeit lief

Der Grund dafür war simpel: Im Gegensatz zu den damals üblichen CPUs (die CISC waren) besass der Archimedes eine RISC-CPU die zwar einen recht spartanischen Befehlssatz hatte, den dafür aber rasend schnell abarbeitete.

Lange Rede, kurzer Sinn: Es kommt ganz darauf an, was Du unter Effizienz verstehst.

Unter Effizienz verstehe ich folgendes: Man drückt auf START, und der Computer spuckt so schnell wie möglich das Ergebnis aus.

Wieviele Cycles TRT braucht, davon steht in dem Manual nichts. Der Autor kommt experimentell zu dem Ergebnis, dass sein Verfahren bei kurzen Mustern (das ist der Parameter Substr bei pos) dem Verfahren von Boyer-Moore überlegen ist, d.h. es werden mehr Chars/sec durchsucht. Auf seinem Amdahl V7 war die Grenze bei sechs Zeichen.
Die Frage, die sich mir stellt ist, ob es Sinn macht, diese Experimente auf einem PC zu wiederholen, oder ob das sinnfrei ist, weil die Hardwarevoraussetzungen nicht erfüllt sind.

Die Antwort auf meine Frage wäre also ein klares Jein? Zwar gibt es spezielle String-Befehle auf der PC-Architektur, allerdings sind diese dem TRT-Befehl unterlegen, weil scasX jeweils nur 1-4 Byte scannen kann (halt soviel, wie in ein Register der CPU passt ??, d.h. bei 64 Bit auch bis zu 8 Byte ??), TRT aber irgendwie 256 Byte auf einmal?

Du deutest es doch schon selbst an: Ohne einen 256 x 8 Bit breiten Datenbus wird das nicht auf einmal gehen. Es mag also vielleicht nur ein Opcode sein, aber im Microcode des Prozessors werden Schleifen ablaufen.

mittels rep prefix lässt sich ja auch auf x86 ein weiterer Speicherbereich durchsuchen. Für längere Suchmuster muss man dann halt entsprechend verketten. TRT wird auch nix anderes machen sondern nur eine höhere Kapselungsebene haben. Intern macht die CPU wohl ziemlich genau das gleiche wie auf x86 der code mit rep und scas* - intern werden die Befehle ja eh in mehr oder weniger umfangreichen Microcode zerlegt. In Delphi machts im Endeffekt auch keinen Unterschied ob ich eine Substringsuche diskret programmiere oder Pos() benutze, der Unterschied zeigt sich eher im Quelltextumfang und in der Größe der generierten Exe als im Zeitbedarf. Der kleine Zeitvorteil von TRT gegenüber einem diskreten Algorithmus ergibt sich schon konstruktionsbedingt und dürfte fast alleinig auf reduzierte Wartezyklen, also verbesserte interne Synchronisation zurückzuführen sein. Der Microcode des TRT-Befehls ist fast zwangsläufig besser an die internen Abläufe in der CPU angepasst und profitiert daher von Optimierungspotentialen die einem Programm nicht ohne weiteres zur Verfügung stehen. Das ist alles.

Fazit: Einen direkten Vergleich mit TRT kann man sich natuerlich schenken, aber eine rep/scas*-Kette gegen Boyer-Moore antreten lassen kann man durchaus

OldGrumpy hat folgendes geschrieben:

Der Grund dafür war simpel: Im Gegensatz zu den damals üblichen CPUs (die CISC waren) besass der Archimedes eine RISC-CPU die zwar einen recht spartanischen Befehlssatz hatte, den dafür aber rasend schnell abarbeitete

tja, hier liegt zwei mal 'ne CISC architektur vor..., von daher hinkt der vergleich.

Gausi hat folgendes geschrieben:

bei kurzen Mustern (das ist der Parameter Substr bei pos) dem Verfahren von Boyer-Moore überlegen ist, d.h. es werden mehr Chars/sec durchsucht. .... weil scasX jeweils nur 1-4 Byte scannen kann (halt soviel, wie in ein Register der CPU passt ??, d.h. bei 64 Bit auch bis zu 8 Byte ??), TRT aber irgendwie 256 Byte auf einmal?

tja, und so darf man bei 'n 7 byte langen suchstring mit scasb, scasw und scasd verketten, bis man die suche zusammenbekommen hat. wenn ich mir da den code von pos, ansehe, ... so ist das 'n richtiges codemonster. wenn ich 'ne dyn. suche über TRT dynamisch aufbaue kommt dann so etwas dabei raus:



*mal nix zu sag*

@Grenzgaenger: Wie ich oben schonmal sagte, verschleiert TRT nur die Komplexität des dahinterliegenden Microcodes besser als das beim Codeäquivalent auf x86 der Fall ist. So what? Nur weil der Assemblercode weniger Zeilen hat, muss er nicht schneller sein. Wie war das damals noch beim Intel Pentium vs. AMD K6, NOP auf Intel 27 Taktzyklen, auf AMD 2? Stichwort "Runtime Error 200" Interessant wäre eine Messung wie "mittlere Anzahl Taktzyklen pro Suchzeichen", davon abgesehen ist ein Vergleich zwischen unterschiedlichen Architekturen immer eine schwierige Sache. Das sieht man ja an den diversen Benchmarks die es für diesen Bereich gibt, die beziehen sich in der Regel nur auf den kleinsten gemeinsamen Nenner, z.B. FLOPs.

geb, dir recht, dass die logik ja irgendwo abgelegt sein muss (z.b. indexsequentielle dateibearbeitung, mit einem asm befehl). aber IMHO haben die kisten mehrere prozessoren welche für unterschiedliche aufgaben spezialisiert sind. die intel architektur kennt hier iaR nur einem. von daher ist das auch schwer zu prüfen oder zu messen. auf so 'ner kiste, vor 20 jahren konnten problemlos ein paar hundert leutchen ihre arbeit machen... wenn es z.b. nur nach der taktfrequenz geht, müssten heutzutage auf 'n prozessor 'n paar tausend leut ihre tätigkeit machen können, inkl. 'n paar programmierer... aber dem ist ja auch nicht so...

ein simples benchmark ist IMHO nicht machbar, selbst wenn man z.b. sagt, prüf 1mio mal den string mit 60KB auf das vorhandensein des 77b langen suchstrings. denn da kommen dann noch andere faktoren, wie bufferung, cache, etc. mit zu.

Tja, was die Taktfrequenz angeht, so ist leistungsfähigere Hardware ja immer nur die Plattform für noch ineffizientere Bloatware. Früher habe ich immer recht viel optimiert, aber ich gebe zu, inzwischen macht es in vielen Fällen einfach gar keinen Sinn mehr, viel Zeit in Optimierungen zu stecken (klassische Gegenbeispiele wie Datenbanken jetzt mal ausgenommen). Es macht heutzutage überhaupt keinen Unterschied mehr ob meine Exe nun 500 oder 800kb gross ist. oder gar 1 oder 5 MB. Vielleicht noch beim Download aber das ist ja auch nur ne relativ seltene Geschichte. Aber wenns einmal auf dem System ist... Da bau ich in den drei Stunden doch lieber noch ein Wunschfeature mehr ein

Ich hab das erst letztes Jahr bei meiner Mutter im Baumarkt gesehen (die arbeitet da an der Kasse) - das alte EDV-System war dosbasiert und plain text, jetzt ist das alles auf hochgezüchtete Windowskisten umgestellt worden. Sicherlich gibts Gründe dafür, aber das System ist seitdem so schnarchlahm geworden... Profitabilität -10%, aber das liegt dann natuerlich nicht an der EDV sondern an den Leuten *hust*
Allein das Erfassen einer Retoure dauert jetzt 2-3 Minuten statt wie vorher 5-10 Sekunden (inkl. Ausdruck für den Kunden).

Aber ich schweife ab Trotzdem wären so nackte Messwerte von der Plattform mit TRT doch mal interessant, nur um mal zu sehen wie der Durchsatz überhaupt so liegt