¿Cuánto crecer buffer en un módulo C tipo StringBuilder?

Question

En C, estoy trabajando en una "clase" que gestiona un búfer de bytes, permitiendo que los datos arbitrarios se anexen al final. Ahora estoy investigando el cambio de tamaño automático a medida que el conjunto subyacente se llena usando llamadas al realloc. Esto debería tener sentido para cualquiera que alguna vez haya usado Java o C# StringBuilder. Entiendo cómo solucionar el cambio de tamaño. Pero, ¿alguien tiene alguna sugerencia, con los motivos proporcionados, en cuánto para hacer crecer el búfer con cada cambio de tamaño?

Obviamente, hay que hacer una compensación entre el espacio desperdiciado y las llamadas a realloc excesivas (lo que podría provocar una copia excesiva). He visto algunos tutoriales/artículos que sugieren doblar. Eso parece un desperdicio si el usuario logra proporcionar una buena conjetura inicial. ¿Vale la pena intentar redondear a una potencia de dos o un múltiplo del tamaño de alineación en una plataforma?

¿Alguien sabe lo que Java o C# hace bajo el capó?

Answer 1

En C# la estrategia utilizada para hacer crecer el búfer interno utilizado por un StringBuilder ha cambiado con el tiempo.

Existen tres estrategias básicas para resolver este problema, y ​​tienen diferentes características de rendimiento.

La primera estrategia básica es:

• Hacer una serie de caracteres
• Cuando se acaba el espacio, crear una nueva matriz con k más caracteres, por alguna constante k.
• Copie la matriz anterior a la nueva matriz y huérfana la matriz anterior.

Esta estrategia tiene una serie de problemas, el más evidente de los cuales es que es O (n 2 ) en el tiempo si la cadena que se está construyendo es extremadamente grande. Digamos que k tiene mil caracteres y la cadena final tiene un millón de caracteres. Terminas reasignando la cadena a 1000, 2000, 3000, 4000, ... y, por lo tanto, copiando 1000 + 2000 + 3000 + 4000 + ... + 999000 caracteres, ¡lo que equivale al orden de 500 mil millones de caracteres copiados!

Esta estrategia tiene la bonita propiedad de que la cantidad de memoria "desperdiciada" está limitada por k.

En la práctica, esta estrategia rara vez se utiliza debido a ese problema n-cuadrado.

La segunda estrategia básica es

• Hacer una gama
• Cuando se acaba el espacio, crear una nueva matriz con k% más caracteres, por alguna constante k.
• Copie la matriz anterior a la nueva matriz y huérfana la matriz anterior.

k% suele ser 100%; si es así, esto se denomina estrategia "doble cuando está lleno".

Esta estrategia tiene la buena propiedad de que su costo amortizado es O (n). Supongamos nuevamente que la última cuerda es un millón de caracteres y comienzas con mil. Hace copias en 1000, 2000, 4000, 8000, ... y termina copiando 1000 + 2000 + 4000 + 8000 ... + 512000 caracteres, que suman alrededor de un millón de caracteres copiados; mucho mejor.

La estrategia tiene la propiedad de que el costo amortizado es lineal sin importar el porcentaje que elija.

Esta estrategia tiene una serie de pega que veces una operación de copia es extremadamente caro y que puede estar perdiendo hasta k% de la longitud de la cadena final en la memoria no utilizada.

La tercera estrategia es hacer una lista vinculada de matrices, cada matriz de tamaño k. Cuando desborda una matriz existente, se asigna una nueva y se agrega al final de la lista.

Esta estrategia tiene la buena propiedad de que ninguna operación es particularmente costosa, la memoria desperdiciada total está limitada por k, y no es necesario que pueda ubicar grandes bloques en el montón de forma regular. Tiene la desventaja de que, finalmente, convertirlo en una cadena puede ser costoso, ya que las matrices de la lista enlazada podrían tener una ubicación pobre.

El generador de cadenas en .NET Framework solía usar una estrategia de doble cuando completo; ahora usa una estrategia de lista enlazada de bloques.

Answer 2

Es específico de la implementación, de acuerdo con the documentation, pero comienza con 16:

La capacidad predeterminada para esta aplicación es de 16, y la capacidad máxima por defecto es Int32.MaxValue.

Un objeto StringBuilder puede asignar más memoria para almacenar caracteres cuando se amplía el valor de una instancia, y la capacidad es ajustada en consecuencia. Por ejemplo, los métodos Append, AppendFormat, EnsureCapacity, Insertar y Reemplazar pueden ampliar el valor de una instancia.

La cantidad de memoria asignada es específica de la implementación, y una excepción (ya sea ArgumentOutOfRangeException o OutOfMemoryException) se lanza si la cantidad de memoria requerida es mayor que la máxima capacidad .

En base a algunas otras cosas del framework .NET, sugiero multiplicarlo por 1.1 cada vez que se alcanza la capacidad actual. Si necesita espacio adicional, solo tiene un equivalente a EnsureCapacity que lo ampliará al tamaño necesario manualmente.

Answer 3

Al trabajar con búferes en expansión y contracción, la propiedad clave que desea es crecer o reducirse por un múltiplo de su tamaño, no una diferencia constante.

Considere el caso en el que tiene una matriz de 16 bytes, lo que aumenta su tamaño en 128 bytes es excesivo; sin embargo, si en cambio tuvieras una matriz de 4096 bytes y la aumentaras en solo 128 bytes, terminarías copiando mucho.

Me enseñaron a doblar o dividir a la mitad siempre las matrices. Si realmente no tiene ninguna pista sobre el tamaño o el máximo, multiplicar por dos garantiza que tendrá mucha capacidad durante mucho tiempo y, a menos que esté trabajando en un sistema con recursos limitados, asignar como máximo el doble del espacio no es demasiado terrible. Además, mantener las cosas en poderes de dos puede permitirle usar cambios de bits y otros trucos, y la asignación subyacente generalmente está en potencias de dos.

Answer 4

traducir esto a C.

Probablemente voy a maitain una lista List<List<string>>.

class StringBuilder 
{ 
    private List<List<string>> list; 

    public Append(List<string> listOfCharsToAppend) 
    { 

     list.Add(listOfCharsToAppend); 
    } 

} 

De esta manera usted se acaba de mantener una lista de listas y la asignación de memoria en la demanda en lugar de asignar memoria muy por delante.

Answer 5

Por lo general, desea mantener el factor de crecimiento un poco más pequeño que el promedio de oro (~ 1.6). Cuando es más pequeño que el promedio de oro, los segmentos descartados serán lo suficientemente grandes como para satisfacer una solicitud posterior, siempre que estén adyacentes entre sí. Si su factor de crecimiento es mayor que el promedio de oro, eso no puede suceder.

He encontrado que reducir el factor a 1.5 todavía funciona muy bien, y tiene la ventaja de ser fácil de implementar en matemáticas enteras (size = (size + (size << 1))>>1; - con un compilador decente se puede escribir como (size * 3)/2, y todavía debe compilar para codificar rápidamente).

Me parece recordar una conversación hace algunos años en Usenet, en la cual PJ Plauger (o tal vez era Pete Becker) de Dinkumware, diciendo que habrían hecho pruebas bastante más extensas que nunca, y llegaron a la misma conclusión (Entonces, por ejemplo, la implementación de std::vector en su biblioteca estándar de C++ usa 1.5).

Answer 6

¿Alguien sabe lo que Java o C# hace bajo el capó?

Echa un vistazo al siguiente enlace para ver cómo se hace en StringBuilder de Java a partir de JDK7, en particular, el método expandCapacity. http://hg.openjdk.java.net/build-infra/jdk7/jdk/file/0f8da27a3ea3/src/share/classes/java/lang/AbstractStringBuilder.java

Answer 7

La lista en .NET framework usa este algoritmo: si se especifica capacidad inicial, crea un búfer de este tamaño; de lo contrario, no se asigna ningún búfer hasta que se agreguen los primeros elementos, que asignan espacio igual al número de elementos (s)) agregado, pero no menos de 4. Cuando se necesita más espacio, asigna un nuevo búfer con 2 veces la capacidad anterior y copia todos los elementos del búfer antiguo al búfer nuevo. Anteriormente, StringBuilder usaba un algoritmo similar.

En .NET 4, StringBuilder asigna el búfer inicial de tamaño especificado en el constructor (el tamaño predeterminado es de 16 caracteres). Cuando el búfer asignado es demasiado pequeño, no se realiza ninguna copia. En su lugar, llena el búfer actual y luego crea una nueva instancia de StringBuilder, que asigna un búfer de tamaño * MAX (length_of_remaining_data_to_add, MIN (length_of_all_previous_buffers, 8000)) * para que al menos todos los datos restantes se ajusten al nuevo búfer y al tamaño total de todos los buffers al menos está duplicado. New StringBuilder mantiene una referencia al antiguo StringBuilder y, por lo tanto, las instancias individuales crean una lista vinculada de almacenamientos intermedios.