¿Hay una rutina rápida GetToken para Delphi?

optimization parsing (7)

En mi programa, proceso millones de cadenas que tienen un carácter especial, por ejemplo, "|" para separar tokens dentro de cada cadena. Tengo una función para devolver el token n''th, y esto es:

Desarrollé esta función cuando estaba usando Delphi 4. Llama a la rutina PosEx muy eficiente que fue desarrollada originalmente por Fastcode y ahora está incluida en la biblioteca StrUtils de Delphi.

Recientemente me actualicé a Delphi 2009 y mis cadenas son todas Unicode. Esta función GetTok todavía funciona y aún funciona bien.

He revisado las nuevas bibliotecas en Delphi 2009 y hay muchas nuevas funciones y adiciones.

Pero no he visto una función GetToken como la que necesito en ninguna de las nuevas bibliotecas Delphi, en varios proyectos de código rápido, y no puedo encontrar nada con una búsqueda en Google que no sea Zarko Gajic: Funciones Delphi Split / Tokenizer , que no es tan optimizado como lo que ya tengo.

Cualquier mejora, incluso el 10% sería notable en mi programa. Sé que una alternativa es StringLists y mantener siempre los tokens por separado, pero esto tiene un gran gasto de memoria y no estoy seguro de si hice todo ese trabajo para convertir si sería más rápido.

Uf. Entonces, después de toda esta charla larga, mi pregunta realmente es:

¿Conoces alguna implementación muy rápida de una rutina GetToken? Una versión optimizada ensamblador sería ideal?

Si no, ¿hay alguna optimización que pueda ver en mi código anterior que pueda mejorarla?

Seguimiento: Barry Kelly mencionó una pregunta que hice hace un año sobre la optimización del análisis sintáctico de las líneas en un archivo. En ese momento ni siquiera había pensado en mi rutina GetTok que no se usó para la lectura o el análisis sintáctico. Es solo ahora que vi la sobrecarga de mi rutina GetTok que me llevó a hacer esta pregunta. Hasta las respuestas de Carl Smotricz y Barry, nunca había pensado en conectar las dos. Tan obvio, pero simplemente no se registró. Gracias por señalar eso.

Sí, mi Delim es un personaje único, así que obviamente tengo una gran optimización que puedo hacer. Mi uso de Pos y PosEx en la rutina GetTok (arriba) me cegó a la idea de que puedo hacerlo más rápido con una búsqueda de personaje por personaje, con bits de código como:

while (cp^ > #0) and (cp^ <= Delim) do Inc(cp);

Voy a repasar las respuestas de todos y probar las diversas sugerencias y compararlas. Luego publicaré los resultados.

Confusión: Bien, ahora estoy realmente perplejo.

Tomé la recomendación de Carl y Barry de ir con PChars, y aquí está mi implementación:

En el papel, no creo que puedas hacer mucho mejor que esto.

Así que puse ambas rutinas en la tarea y utilicé AQTime para ver qué está sucediendo. La ejecución incluí 1,108,514 llamadas a GetTok.

AQTime sincronizó la rutina original en 0,40 segundos. El millón de llamadas a Pos tomó 0.10 segundos. Medio millón de TokenNum = 1 copias tomó 0.10 segundos. Las 600,000 llamadas PosEx solo tomaron 0.03 segundos.

Luego sincronicé mi nueva rutina con AQ Time para la misma ejecución y exactamente las mismas llamadas. AQTime informa que mi nueva rutina "rápida" tomó 3.65 segundos, que es 9 veces más larga. El culpable según AQ Time fue el primer bucle:

while (PLine^ <> #0) and (PLine^ <> Delim) do inc(PLine);

La línea while, que se ejecutó 18 millones de veces, se informó a 2,66 segundos. La línea inc, ejecutada 16 millones de veces, tomó 0.47 segundos.

Ahora pensé que sabía lo que estaba sucediendo aquí. Tuve un problema similar con AQTime en una pregunta que planteé el año pasado: ¿Por qué CharInSet es más rápido que Case?

De nuevo, fue Barry Kelly quien me dio seguimiento. Básicamente, un perfilador de instrumentos como AQ Time no necesariamente hace el trabajo de microoptimización. Agrega una sobrecarga a cada línea que puede saturar los resultados que se muestran claramente en estos números. Las 34 millones de líneas ejecutadas en mi nuevo "código optimizado" sobrepasan los varios millones de líneas de mi código original, con aparentemente poca o ninguna sobrecarga de las rutinas Pos y PosEx.

Barry me dio una muestra de código usando QueryPerformanceCounter para comprobar que estaba en lo correcto, y en ese caso lo estaba haciendo.

De acuerdo, hagamos lo mismo ahora con QueryPerformanceCounter para demostrar que mi nueva rutina es más rápida y no 9 veces más lenta, como dice AQTime. Así que ahí voy:

function TimeIt(const Title: string): double; var i: Integer; start, finish, freq: Int64; Seconds: double; begin QueryPerformanceCounter(start); for i := 1 to 250000 do GetTokOld(''This is a string|that needs|parsing'', ''|'', 1); for i := 1 to 250000 do GetTokOld(''This is a string|that needs|parsing'', ''|'', 2); for i := 1 to 250000 do GetTokOld(''This is a string|that needs|parsing'', ''|'', 3); for i := 1 to 250000 do GetTokOld(''This is a string|that needs|parsing'', ''|'', 4); QueryPerformanceCounter(finish); QueryPerformanceFrequency(freq); Seconds := (finish - start) / freq; Result := Seconds; end;

Por lo tanto, esto probará 1,000,000 llamadas a GetTok.

Mi antiguo procedimiento con las llamadas Pos y PosEx tomó 0.29 segundos. El nuevo con PChars tomó 2.07 segundos.

¡Ahora estoy completamente aturdido! ¿Alguien puede decirme por qué el procedimiento de PChar no solo es más lento, sino que es de 8 a 9 veces más lento?

¡Misterio resuelto! Andreas dijo en su respuesta para cambiar el parámetro Delim de una cuerda a un Char. Siempre usaré solo un Char, así que al menos para mi implementación esto es muy posible. Me sorprendió lo que sucedió.

El tiempo para el millón de llamadas disminuyó de 1.88 segundos a .22 segundos.

Y sorprendentemente, el tiempo para mi rutina de Pos / PosEx original subió de .29 a .44 segundos cuando cambié su parámetro Delim a un Char.

Francamente, estoy decepcionado por el optimizador de Delphi. Ese Delim es un parámetro constante. El optimizador debería haber notado que la misma conversión está sucediendo dentro del ciclo y debería haberlo movido para que solo se haga una vez.

Comprobando dos veces mis parámetros de generación de código, sí, tengo Optimization True y String format Off.

La conclusión es que la nueva rutina PChar con la solución de Andrea es aproximadamente un 25% más rápida que la original (.22 frente a .29).

Todavía quiero hacer un seguimiento de los otros comentarios aquí y probarlos.

Desactivar la optimización y activar la verificación de formato de cadena solo aumenta el tiempo de .22 a .30. Agrega casi lo mismo al original.

La ventaja de usar código ensamblador o rutinas de llamada escritas en ensamblador como Pos o PosEx es que NO están sujetas a las opciones de generación de código que haya establecido. Siempre se ejecutarán de la misma manera, una forma pre-optimizada y no hinchada.

He reafirmado en los últimos días que la mejor forma de comparar el código para la microoptimización es observar y comparar el código del Ensamblador en la ventana de la CPU. Sería bueno que Embarcadero pudiera hacer que esa ventana sea un poco más conveniente, y permitirnos copiar porciones en el portapapeles o imprimir secciones de la misma.

Además, bloqueé injustamente AQTime anteriormente en esta publicación, pensando que el tiempo adicional agregado para mi nueva rutina se debió únicamente a la instrumentación que agregó. Ahora que regreso y verifico con el parámetro Char en lugar de String, el ciclo while está abajo a .30 segundos (desde 2.66) y la línea inc está abajo a .14 segundos (desde .47). Es extraño que la línea de inc también caiga. Pero ya me estoy cansando de todas estas pruebas.

Tomé la idea de Carl de bucles por personajes, y reescribí ese código con esa idea. Hace otra mejora, hasta .19 segundos desde .22. Así que aquí está el mejor hasta ahora:

function GetTok(const Line: string; const Delim: Char; const TokenNum: Byte): string; { LK Nov 8, 2009 - Reoptimized using PChars instead of calls to Pos and PosEx } { See; https://stackoverflow.com/questions/1694001/is-there-a-fast-gettoken-routine-for-delphi } var I, CurToken: Integer; PLine, PStart: PChar; begin CurToken := 1; PLine := PChar(Line); PStart := PLine; for I := 1 to length(Line) do begin if PLine^ = Delim then begin if CurToken = TokenNum then break else begin CurToken := CurToken + 1; inc(PLine); PStart := PLine; end; end else inc(PLine); end; if CurToken = TokenNum then SetString(Result, PStart, PLine - PStart) else Result := ''''; end;

Todavía puede haber algunas optimizaciones menores en esto, como la comparación CurToken = Tokennum, que debería ser del mismo tipo, entero o byte, lo que sea más rápido.

Pero digamos, estoy feliz ahora.

Gracias de nuevo a la comunidad de StackOverflow Delphi.

Delphi compila a un código MUY eficiente; en mi experiencia, fue muy difícil mejorar en ensamblador.

Creo que deberías apuntar un PChar (todavía existen, ¿no?) Me separé de Delphi alrededor de 4.0) al comienzo de la cadena e incrementarlo al contar "|" s, hasta que hayas encontrado n-1 de ellos. Sospecho que será más rápido que llamar a PosEx repetidamente.

Tome nota de esa posición, luego incremente el puntero un poco más hasta que llegue a la siguiente tubería. Saca tu subcadena. Hecho.

Solo estoy adivinando, pero no me sorprendería si esto fuera lo más rápido posible para resolver este problema.

EDITAR: Esto es lo que tenía en mente. Este código, por desgracia, no está compilado ni probado, pero debe demostrar lo que quise decir.

En particular, Delim se trata como un solo carácter, que creo que hace una gran diferencia si eso cumple con los requisitos, y el personaje de PLine se prueba una sola vez. Finalmente, no hay más comparación contra TokenNum; Creo que es más rápido disminuir un contador a 0 para contar delimitadores.

function GetTok(const Line: string; const Delim: string; const TokenNum: Byte): string; var Del: Char; PLine, PStart: PChar; Nth, I, P0, P9: Integer; begin Del := Delim[1]; Nth := TokenNum + 1; P0 := 1; P9 := Line.length + 1; PLine := PChar(line); for I := 1 to P9 do begin if PLine^ = Del then begin if Nth = 0 then begin P9 := I; break; end; Dec(Nth); if Nth = 0 then P0 := I + 1 end; Inc(PLine); end; if (Nth <= 1) or (TokenNum = 1) then Result := Copy(Line, P0, P9 - P0); else Result := '''' end;

En tu código, creo que esta es la única línea que se puede optimizar:

Result := copy(Line, P+1, MaxInt)

Si calcula la nueva longitud allí, puede ser un poco más rápido, pero no el 10% que está buscando.

Tu algoritmo de tokenización parece bastante correcto. Para optimizarlo, lo ejecutaría a través de un generador de perfiles (como AQTime de AutomatedQA) con un subconjunto representativo de sus datos de producción. Eso te llevará al punto más débil.

La única función de RTL que se acerca es esta en la unidad de Clases:

procedure TStrings.SetDelimitedText(const Value: string);

Tokenizes, pero usa tanto QuoteChar como Delimiter , pero solo usa un Delimitador.

Utiliza la función SetString en la unidad del sistema, que es una manera bastante rápida de establecer el contenido de una cadena basada en PChar / PAnsiChar / PUnicodeChar y una longitud.

Eso también podría mejorarlo un poco; por otro lado, Copy también es muy rápido.

Esta es una función que he tenido en mi biblioteca personal durante bastante tiempo y que uso extensamente. Creo que esta es la versión más actual de esto. He tenido múltiples versiones en el pasado optimizadas por una variedad de razones diferentes. Éste trata de tener en cuenta las cadenas entre comillas, pero si se elimina ese código, la función se vuelve un poco más rápida.

De hecho, tengo un número de otras rutinas, CountSections y ParseSectionPOS son algunos ejemplos.

Desafortunadamente, esta rutina solo se basa en ansi / pchar. Aunque no creo que sea difícil moverlo a unicode. Tal vez ya lo hice ... Tendré que verificar eso.

Nota: Esta rutina se basa en 1 en la indexación de ParseNum.

function ParseSection(ParseLine: string; ParseNum: Integer; ParseSep: Char; QuotedStrChar:char = #0) : string; var wStart, wEnd : integer; wIndex : integer; wLen : integer; wQuotedString : boolean; begin result := ''''; wQuotedString := false; if not (ParseLine = '''') then begin wIndex := 1; wStart := 1; wEnd := 1; wLen := Length(ParseLine); while wEnd <= wLen do begin if (QuotedStrChar <> #0) and (ParseLine[wEnd] = QuotedStrChar) then wQuotedString := not wQuotedString; if not wQuotedString and (ParseLine[wEnd] = ParseSep) then begin if wIndex=ParseNum then break else begin inc(wIndex); wStart := wEnd+1; end; end; inc(wEnd); end; result := copy(ParseLine, wStart, wEnd-wStart); if (length(result) > 0) and (QuotedStrChar <> #0) and (result[1] = QuotedStrChar) then result := AnsiDequotedStr(result, QuotedStrChar); end; end; { ParseSection }

Hace una gran diferencia lo que se espera que sea "Delim". Si se espera que sea un solo personaje, es mucho mejor que recorras la cadena carácter por personaje, idealmente a través de un PChar y pruebas específicas.

Si se trata de una cadena larga, Boyer-Moore y búsquedas similares tienen una fase de configuración para tablas de salto, y la mejor manera sería construir las tablas una vez, y reutilizarlas para cada descubrimiento posterior. Eso significa que necesita estado entre llamadas, y esta función sería mejor como un método en un objeto en su lugar.

Puede que le interese esta respuesta que le hice una pregunta hace un tiempo, sobre la forma más rápida de analizar una línea en Delphi. (¡Pero veo que fue usted quien hizo la pregunta! Sin embargo, al resolver su problema, me gustaría saber cómo describí el análisis, no utilizando PosEx como lo está utilizando, dependiendo de cómo se vea Delim normalmente).

ACTUALIZACIÓN : OK, pasé unos 40 minutos mirando esto. Si sabes que el delimitador va a ser un personaje, casi siempre estás mejor con la segunda versión (es decir, el escaneo de PChar), pero debes pasar a Delim como personaje. En el momento de escribir esto, está convirtiendo la expresión PLine^ , de tipo Char, en una cadena para compararla con Delim. Eso será muy lento; incluso indizar en la cadena, con Delim[1] también será algo lento.

Sin embargo, dependiendo de qué tan grandes sean sus líneas y cuántas piezas delimitadas desee extraer, es posible que sea mejor con un enfoque reanudable, en lugar de omitir las piezas delimitadas no deseadas dentro de la rutina de tokenización. Si llama a GetTok con índices en aumento sucesivo, como lo hace actualmente en su mini índice de referencia, terminará con un rendimiento O (n * n), donde n es el número de secciones delimitadas. Esto se puede convertir en O (n) si guarda el estado del escaneo y lo restaura para la siguiente iteración, o empaqueta todos los ítems extraídos en una matriz.

Aquí hay una versión que hace tokenización una vez y devuelve una matriz. Sin embargo, necesita tokenizar dos veces, para saber qué tan grande hacer la matriz. Por otro lado, solo la segunda tokenización necesita extraer las cadenas:

// Do all tokenization up front. function GetTok4(const Line: string; const Delim: Char): TArray<string>; var cp, start: PChar; count: Integer; begin // Count sections count := 1; cp := PChar(Line); start := cp; while True do begin if cp^ <> #0 then begin if cp^ <> Delim then Inc(cp) else begin Inc(cp); Inc(count); end; end else begin Inc(count); Break; end; end; SetLength(Result, count); cp := start; count := 0; while True do begin if cp^ <> #0 then begin if cp^ <> Delim then Inc(cp) else begin SetString(Result[count], start, cp - start); Inc(cp); Inc(count); end; end else begin SetString(Result[count], start, cp - start); Break; end; end; end;

Aquí está el enfoque reanudable. Sin embargo, las cargas y los almacenamientos de la posición actual y del carácter delimitador tienen un costo:

type TTokenizer = record private FSource: string; FCurrPos: PChar; FDelim: Char; public procedure Reset(const ASource: string; ADelim: Char); inline; function GetToken(out AResult: string): Boolean; inline; end; procedure TTokenizer.Reset(const ASource: string; ADelim: Char); begin FSource := ASource; // keep reference alive FCurrPos := PChar(FSource); FDelim := ADelim; end; function TTokenizer.GetToken(out AResult: string): Boolean; var cp, start: PChar; delim: Char; begin // copy members to locals for better optimization cp := FCurrPos; delim := FDelim; if cp^ = #0 then begin AResult := ''''; Exit(False); end; start := cp; while (cp^ <> #0) and (cp^ <> Delim) do Inc(cp); SetString(AResult, start, cp - start); if cp^ = Delim then Inc(cp); FCurrPos := cp; Result := True; end;

Aquí está el programa completo que utilicé para la evaluación comparativa.

Aquí están los resultados:

*** count=3, Length(src)=200 GetTok1: 595 ms GetTok2: 547 ms GetTok3: 2366 ms GetTok4: 407 ms GetTokBK: 226 ms *** count=6, Length(src)=350 GetTok1: 1587 ms GetTok2: 1502 ms GetTok3: 6890 ms GetTok4: 679 ms GetTokBK: 334 ms *** count=9, Length(src)=500 GetTok1: 3055 ms GetTok2: 2912 ms GetTok3: 13766 ms GetTok4: 947 ms GetTokBK: 446 ms *** count=12, Length(src)=650 GetTok1: 4997 ms GetTok2: 4803 ms GetTok3: 23021 ms GetTok4: 1213 ms GetTokBK: 543 ms *** count=15, Length(src)=800 GetTok1: 7417 ms GetTok2: 7173 ms GetTok3: 34644 ms GetTok4: 1480 ms GetTokBK: 653 ms

Dependiendo de las características de sus datos, si el delimitador es probable que sea un personaje o no, y cómo trabaja con él, los diferentes enfoques pueden ser más rápidos.

(Cometí un error en mi programa anterior, no estaba midiendo las mismas operaciones para cada estilo de rutina. Actualicé el enlace pastebin y los resultados del benchmark).

No soy la persona que siempre culpa al algoritmo, pero si miro la primera fuente, el problema es que para la cadena N, usted hace POS / posexes para la cadena 1..n-1 otra vez también.

Esto significa que para N elementos, debe sumar (n, n-1, n-2 ... 1) POSes (= + / - 0.5 * N ^ 2), mientras que solo se necesitan N.

Si simplemente almacena en caché la posición del último resultado encontrado, por ejemplo, en un registro pasado por el parámetro VAR, puede ganar mucho.

tipo
TLastPosition = record elementnr: integer; // last tokennumber elementpos: integer; // índice de caracteres del último final del partido;

y luego algo

si tokennum = (lastposition.elementnr + 1) entonces comienza newpos: = posex (delim, line, lastposition.elementpos); fin;

Desafortunadamente, no tengo tiempo ahora para escribirlo, pero espero que entiendas la idea

Su nueva función (la de PChar) debería declarar "Delim" como Char y no como String . En su implementación actual, el compilador debe convertir PLine ^ char en una cadena para compararla con "Delim". Y eso sucede en un circuito cerrado que resulta en un enorme golpe de rendimiento.

Usar ensamblador sería una micro-optimización. Se obtienen ganancias mucho mayores optimizando el algoritmo. No hacer el trabajo es mejor que hacer el trabajo de la manera más rápida posible, todo el tiempo.

Un ejemplo sería si tiene lugares en su programa donde necesita varios tokens de la misma línea. Otro procedimiento que devuelve un conjunto de tokens en el que puede indexar debe ser más rápido que llamar a su función más de una vez, especialmente si permite que el procedimiento no devuelva todos los tokens, sino solo tantos como necesite.

Pero, en general, estoy de acuerdo con la respuesta de Carl (+1), el uso de PChar para escanear probablemente sea más rápido que su código actual.