c# - examples - String.Substring() parece bloquear este código

substring c# w3schools

Question

Introducción

Tengo este algoritmo favorito que he creado hace bastante tiempo, que siempre escribo y reescribo en nuevos lenguajes de programación, plataformas, etc. como una especie de punto de referencia. Aunque mi lenguaje de programación principal es C #, literalmente copié el código y lo modifiqué ligeramente, lo incorporé en Java y lo encontré para ejecutarlo 1000 veces más rápido.

El código

Hay bastante código, pero solo voy a presentar este fragmento, que parece ser el problema principal:

for (int i = 0; i <= s1.Length; i++)
{
for (int j = i + 1; j <= s1.Length - i; j++)
{
string _s1 = s1.Substring(i, j);
if (tree.hasLeaf(_s1))
...

Los datos

Es importante señalar que la cadena s1 en esta prueba en particular tiene una longitud de 1 millón de caracteres (1 MB).

Mediciones

He perfilado mi ejecución de código en Visual Studio porque pensé que la forma en que construyo mi árbol o la forma en que lo atravieso no es óptima. Después de examinar los resultados, parece que la string _s1 = s1.Substring(i, j); líneas string _s1 = s1.Substring(i, j); ¡Acomoda más del 90% del tiempo de ejecución!

Observaciones adicionales

Otra diferencia que he notado es que, aunque mi código es de un solo subproceso, Java logra ejecutarlo utilizando los 8 núcleos (100% de utilización de la CPU), mientras que incluso con Parallel.For () y las técnicas de subprocesamiento múltiple, mi código C # logra utilizar 35- 40% como máximo. Dado que el algoritmo se escala linealmente con el número de núcleos (y frecuencia), he compensado esto y aún así el fragmento de código de Java se ejecuta en orden de magnitud 100-1000x más rápido.

Razonamiento

Supongo que la razón por la que esto sucede tiene que ver con el hecho de que las cadenas en C # son inmutables, por lo que String.Substring () tiene que crear una copia y, dado que está dentro de un bucle anidado con muchas iteraciones, supongo que hay muchas copias y la recolección de basura está en marcha, sin embargo, no sé cómo se implementa Substring en Java.

Pregunta

¿Cuáles son mis opciones en este momento? No hay forma de evitar el número y la longitud de las subcadenas (esto ya está optimizado al máximo). ¿Hay algún método que no conozca (o quizás la estructura de datos) que pueda resolver este problema por mí?

Implementación mínima solicitada (a partir de comentarios)

He omitido la implementación del árbol de sufijos que es O (n) en construcción y O (log (n)) en transversal

public static double compute(string s1, string s2)
{
double score = 0.00;
suffixTree stree = new suffixTree(s2);
for (int i = 0; i <= s1.Length; i++)
{
int longest = 0;
for (int j = i + 1; j <= s1.Length - i; j++)
{
string _s1 = s1.Substring(i, j);
if (stree.has(_s1))
{
score += j - i;
longest = j - i;
}
else break;
};
i += longest;
};
return score;
}

Fragmento de captura de pantalla del generador de perfiles.

Tenga en cuenta que esto se probó con una cadena s1 del tamaño de 300.000 caracteres. Por alguna razón, 1 milion de caracteres nunca termina en C #, mientras que en Java tarda solo 0,75 segundos. La memoria consumida y el número de recolecciones de basura no parecen indicar un problema de memoria. El pico fue de aproximadamente 400 MB, pero considerando el enorme árbol de sufijos, esto parece ser normal. No hay patrones extraños de recolección de basura manchados tampoco.

Answer 1

Origen del tema

Después de tener una batalla gloriosa que duró dos días y tres noches (y las increíbles ideas y pensamientos de los comentarios) ¡finalmente logré solucionar este problema!

Me gustaría publicar una respuesta para cualquier persona que se encuentre con problemas similares donde la función string.Substring(i, j) no es una solución aceptable para obtener la subcadena de una cadena porque la cadena es demasiado grande y no puede pagar la copia realizada por string.Substring(i, j) (tiene que hacer una copia porque las cadenas de C # son inmutables, no hay forma de string.Substring(i, j) ) o la string.Substring(i, j) se llama un gran número de veces durante el La misma cadena (como en mi anidado para bucles) le da un mal momento al recolector de basura, o como en mi caso, ambos!

Intentos

He probado muchas cosas sugeridas, como StringBuilder , Streams , asignación de memoria no administrada usando Intptr y Marshal dentro del bloque unsafe{} e incluso creando un IEnumerable y devolviendo los caracteres por referencia dentro de las posiciones dadas. Todos estos intentos fracasaron en última instancia porque hubo que hacer algún tipo de unión de los datos, ya que no había una manera fácil para que yo pudiera atravesar mi personaje árbol por personaje sin poner en peligro el rendimiento. Si solo hubiera una forma de abarcar varias direcciones de memoria dentro de una matriz a la vez, como podría hacerlo en C ++ con algunos aritméticos de punteros ... excepto que hay ... (créditos para el comentario de @Ivan Stoev)

La solución

La solución fue utilizar System.ReadOnlySpan<T> (no podría ser System.Span<T> debido a que las cadenas son inmutables), lo que, entre otras cosas, nos permite leer matrices de direcciones de memoria dentro de una matriz existente sin crear copias.

Esta pieza del código publicado:

string _s1 = s1.Substring(i, j);
if (stree.has(_s1))
{
score += j - i;
longest = j - i;
}

Se cambió a lo siguiente:

if (stree.has(i, j))
{
score += j - i;
longest = j - i;
}

Donde stree.has() ahora toma dos enteros (posición y longitud de la subcadena) y hace:

ReadOnlySpan<char> substr = s1.AsSpan(i, j);

¡Observe que la variable substr es literalmente una referencia a un subconjunto de caracteres de la matriz s1 inicial y no a una copia! (La variable s1 se ha hecho accesible desde esta función)

Tenga en cuenta que, al momento de escribir esto, estoy usando C # 7.2 y .NET Framework 4.6.1, lo que significa que para obtener la función Span tenía que ir a Proyecto> Administrar paquetes de NuGet, marcar la casilla de verificación "Incluir versión preliminar" y buscar Sistema .Memoria e instálala.

Al volver a ejecutar la prueba inicial (en cadenas de caracteres de 1 millón de longitud, es decir, 1MB), la velocidad aumentó de más de 2 minutos (dejé de esperar después de 2 minutos) a ~ 86 milisegundos.