Concatenación de cadenas en C# con cadenas internas

Question

Conozco esta pregunta tiene estado hecho pero le doy un toque ligeramente diferente.Varios han señalado que se trata de una optimización prematura, lo cual es completamente cierto si estuviera preguntando por motivos prácticos y únicamente por motivos prácticos.Mi problema tiene su origen en un problema práctico, pero de todos modos sigo teniendo curiosidad.

---

Estoy creando un montón de declaraciones SQL para crear un script (ya que se guardará en el disco) para recrear un esquema de base de datos (fácilmente muchos cientos de tablas, vistas, etc.).Esto significa que mi concatenación de cadenas es solo para agregar.StringBuilder, según MSDN, funciona manteniendo un buffer interno (seguramente un char[]) y copiando caracteres de cadena en ello y reasignando la matriz según sea necesario.

Sin embargo, mi código tiene muchas cadenas repetidas ("CREATE TABLE [", "GO ", etc.), lo que significa que puedo aprovecharlas. siendo internado pero no si uso StringBuilder ya que se copiarían cada vez.Las únicas variables son esencialmente nombres de tablas y aquellas que ya existen como cadenas en otros objetos que ya están en la memoria.

Por lo que puedo decir, después de leer mis datos y crear mis objetos que contienen la información del esquema, toda la información de mi cadena se puede reutilizar mediante prácticas, ¿no?

Suponiendo eso, ¿no sería más rápida una Lista o Lista Enlazada de cadenas porque retienen punteros a cadenas internas?Entonces es solo una llamada a String.Concat() para una única asignación de memoria de toda la cadena que tenga exactamente la longitud correcta.

Una Lista tendría que reasignar una cadena [] de punteros internos y una lista vinculada tendría que crear nodos y modificar punteros, por lo que no son "libres" de hacer, pero si estoy concatenando muchos miles de cadenas internas entonces parecerían más eficientes.

Ahora supongo que podría idear alguna heurística sobre el recuento de caracteres para cada declaración SQL y contar cada tipo y tener una idea aproximada y preestablecer mi capacidad de StringBuilder para evitar la reasignación de su carácter [], pero tendría que excederme por un margen justo. para reducir la probabilidad de reasignación.

Entonces, para este caso, cuál sería la forma más rápida de obtener una única cadena concatenada:

• Constructor de cadenas
• Lista<cadena> de cadenas internas
• LinkedList<cadena> de cadenas internadas
• StringBuilder con heurística de capacidad
• ¿Algo más?

Como un pregunta separada (Es posible que no siempre vaya al disco) a lo anterior:¿Sería más rápido un solo StreamWriter para un archivo de salida?Alternativamente, use una Lista o Lista Vinculada y luego escríbalas en un archivo de la lista en lugar de concatenarlas primero en la memoria.

EDITAR:De acuerdo a lo pedido, la referencia (.NET 3.5) a MSDN.Dice: "Los datos nuevos se agregan al final del búfer si hay espacio disponible;de lo contrario, se asigna un búfer nuevo y más grande, los datos del búfer original se copian al nuevo búfer y luego los nuevos datos se agregan al nuevo búfer". Para mí, eso significa un char[] que se reasigna para hacerlo más grande (lo que requiere copiar datos antiguos a la matriz redimensionada) y luego agregarlos.

Answer 1

Para su pregunta separada , Win32 tiene un función WriteFileGather , que podría escribir eficientemente una lista de cadenas (internados) en el disco, pero marcaría una diferencia notable solo cuando se llama de forma asíncrona, ya que el disco escribe eclipsará todas las concatenaciones excepto las extremadamente grandes.

Para su pregunta principal : a menos que esté alcanzando megabytes de script, o decenas de miles de scripts, no se preocupe.

Puede esperar que StringBuilder duplique el tamaño de asignación en cada reasignación. Eso significaría que aumentar un búfer de 256 bytes a 1 MB es solo 12 reasignaciones, bastante bueno, dado que su estimación inicial fue de 3 órdenes de magnitud fuera del objetivo.

Simplemente como ejercicio, algunas estimaciones: construir un búfer de 1 MB barrerá aproximadamente 3 MB de memoria (fuente de 1 MB, objetivo de 1 MB, 1 MB debido a copia durante la reasignación).

Una implementación de lista vinculada barrerá aproximadamente 2 MB (y eso ignora la sobrecarga de 8 bytes / objeto por referencia de cadena). Por lo tanto, está ahorrando 1 MB de lecturas / escrituras de memoria, en comparación con un ancho de banda de memoria típico de 10 Gbit / sy 1 MB de caché L2.)

Sí, la implementación de una lista es potencialmente más rápida, y la diferencia sería importante si sus memorias intermedias son un orden de magnitud mayor.

Para el caso mucho más común de cadenas pequeñas, la ganancia algorítmica es insignificante y se compensa fácilmente por otros factores: el código StringBuilder ya está probablemente en el caché de código y es un objetivo viable para las microoptimizaciones. Además, usar una cadena internamente significa que no hay copia si la cadena final se ajusta al búfer inicial.

El uso de una lista vinculada también reducirá el problema de reasignación de O (número de caracteres) a O (número de segmentos): ¡su lista de referencias de cadenas enfrenta el mismo problema que una cadena de caracteres!

---

Por lo tanto, en mi opinión, la implementación de StringBuilder es la opción correcta, optimizada para el caso común, y se degrada principalmente para buffers de destino inesperadamente grandes. Esperaría que la implementación de una lista se degrade primero para muchos segmentos pequeños, que en realidad es el tipo extremo de escenario para el que StringBuilder está tratando de optimizar.

Aún así, sería interesante ver una comparación de las dos ideas y cuándo la lista comienza a ser más rápida.

Answer 2

Si estuviera implementando algo como esto, nunca construiría un StringBuilder (o cualquier otro en el búfer de memoria de su script). Simplemente lo transmitiría a su archivo y haría que todas las cadenas estén en línea.

Aquí hay un pseudocódigo de ejemplo (no sintácticamente correcto ni nada):

FileStream f = new FileStream("yourscript.sql");
foreach (Table t in myTables)
{
    f.write("CREATE TABLE [");
    f.write(t.ToString());
    f.write("]");
    ....
}

Entonces, nunca necesitará una representación en memoria de su script, con toda la copia de cadenas.

Opiniones?

Answer 3

En mi experiencia, asigné correctamente StringBuilder supera a casi todo lo demás para grandes cantidades de datos de cadena. Vale la pena desperdiciar algo de memoria, incluso, sobrepasando su estimación en un 20% o 30% para evitar la reasignación. Actualmente no tengo números duros para hacer una copia de seguridad utilizando mis propios datos, pero eche un vistazo a esta página para obtener más .

Sin embargo, como a Jeff le gusta señalar, ¡no optimices prematuramente!

EDITAR: Como señaló @Colin Burnett, las pruebas que realizó Jeff no concuerdan con las pruebas de Brian, pero el punto de vincular la publicación de Jeff fue sobre la optimización prematura en general. Varios comentaristas en la página de Jeff notaron problemas con sus pruebas.

Answer 4

De hecho StringBuilder utiliza una instancia de String internamente. String es de hecho mutable dentro del System asamblea, por eso StringBuilder se puede construir encima de él.Puedes hacer StringBuilder un poquito más efectivo asignando una longitud razonable al crear la instancia.De esa forma eliminarás/reducirás el número de operaciones de cambio de tamaño.

La pasantía de cadenas funciona para cadenas que se pueden identificar en tiempo de compilación.Por lo tanto, si genera muchas cadenas durante la ejecución, no serán internadas a menos que lo haga usted mismo llamando al método interno en la cadena.

La pasantía sólo te beneficiará si tus condiciones son idénticas.Las cadenas casi idénticas no se benefician de la pasantía, por lo que "SOMESTRINGA" y "SOMESTRINGB" Serán dos cadenas diferentes incluso si están internadas.

Answer 5

Si todas (o la mayoría) de las cadenas que se concatenan están internados, entonces su esquema PODRÍA darle un aumento de rendimiento, ya que podría usar menos memoria y podría ahorrar algunas copias de cadenas grandes.

Sin embargo, si realmente mejora o no el rendimiento depende del volumen de datos que está procesando, porque la mejora está en factores constantes, no en el orden de magnitud del algoritmo.

La única forma de saberlo realmente es ejecutar su aplicación de ambas maneras y medir los resultados. Sin embargo, a menos que esté bajo una presión de memoria significativa y necesite una forma de guardar bytes, no me molestaría y solo usaría el generador de cadenas.

Answer 6

A StringBuilder no usa un char[] para almacenar los datos, usa una cadena mutable interna. Eso significa que no hay ningún paso adicional para crear la cadena final, ya que cuando concatena una lista de cadenas, el <=> simplemente devuelve el búfer de cadena interno como una cadena normal.

Las reasignaciones que hace el <=> para aumentar la capacidad significa que los datos se copian en promedio 1.33 veces adicionales. Si puede proporcionar una buena estimación del tamaño cuando crea el <=> puede reducir aún más.

Sin embargo, para tener un poco de perspectiva, debe observar qué es lo que está tratando de optimizar. Lo que tomará la mayor parte del tiempo en su programa es escribir realmente los datos en el disco, por lo que incluso si puede optimizar el manejo de su cadena para que sea dos veces más rápido que usar un <=> (lo cual es muy poco probable), la diferencia general será sigue siendo solo un pequeño porcentaje.

Answer 7

¿Has considerado C ++ para esto? ¿Existe una clase de biblioteca que ya construye expresiones T / SQL, preferiblemente escritas en C ++.

Lo más lento de las cadenas es malloc. Toma 4KB por cadena en plataformas de 32 bits. Considere optimizar el número de objetos de cadena creados.

Si debe usar C #, le recomendaría algo como esto:

string varString1 = tableName;
string varString2 = tableName;

StringBuilder sb1 = new StringBuilder("const expression");
sb1.Append(varString1);

StringBuilder sb2 = new StringBuilder("const expression");
sb2.Append(varString2);

string resultingString = sb1.ToString() + sb2.ToString();

Incluso iría tan lejos como permitir que la computadora evalúe la mejor ruta para la creación de instancias de objetos con marcos de inyección de dependencia, si perf es TAN importante.