El uso de realloc en C++

Question

std::realloc es peligroso en C++ si la memoria malloc'd contiene tipos no pod. Parece que el problema solo es que std::realloc no llamará a los destructores de tipo si no puede hacer crecer la memoria in situ.

Una solución trivial sería una función try_realloc. En lugar de mallocrar la nueva memoria si no se puede cultivar in situ, simplemente devolvería falsa. En ese caso, se podría asignar nueva memoria, copiar los objetos (o moverlos) a la nueva memoria y finalmente liberar la memoria anterior.

Esto parece sumamente útil. std::vector podría hacer un gran uso de esto, posiblemente evitando todas las copias/reasignaciones.
pirorretardante preventivo: Técnicamente, ese es el mismo rendimiento de Big-O, pero si el crecimiento del vector es un cuello de botella en su aplicación, una aceleración x2 es agradable incluso si el Big-O permanece inalterado.

PERO, no puedo encontrar ninguna API que funcione como try_realloc.

¿Echo de menos algo? ¿try_realloc no es tan útil como me lo imagino? ¿Hay algún error oculto que hace inutilizable try_realloc?

Mejor aún, ¿hay alguna API menos documentada que funcione como try_realloc?

NOTA: Obviamente, aquí, en código específico de biblioteca/plataforma. No estoy preocupado ya que try_realloc es intrínsecamente una optimización.

---

Actualización: siguiente comentario Steve Jessops es en si vector sería más eficiente el uso de realloc escribí una prueba de concepto para probar. El realloc-vector simula el patrón de crecimiento de un vector, pero tiene la opción de realloc en su lugar. Ejecuté el programa hasta un millón de elementos en el vector.

Para comparar un vector debe asignar 19 veces mientras crece a un millón de elementos.

Los resultados, si el realloc-vector es lo único que utiliza el montón, los resultados son impresionantes, la asignación de 3-4 crece al tamaño de millones de bytes.

Si el realloc-vector se usa junto con un vector que crece al 66% de la velocidad del realloc-vector Los resultados son menos prometedores, asignando 8-10 veces durante el crecimiento.

Por último, si el realloc-vector se utiliza junto con un vector que crece al mismo ritmo, el realloc-vector asigna 17-18 veces. Apenas se guarda una asignación sobre el comportamiento del vector estándar.

No dudo que un hacker pueda asignar tamaños de asignación para mejorar los ahorros, pero estoy de acuerdo con Steve en que el tremendo esfuerzo para escribir y mantener dicho asignador no es la ganancia.

Answer 1

vector generalmente crece en grandes incrementos. No puede hacer eso repetidamente sin reubicarse, a menos que arregle cuidadosamente las cosas de modo que exista una gran cantidad de direcciones libres justo encima del búfer interno del vector (que en efecto requiere asignar páginas enteras, porque obviamente no puede tener otras asignaciones más adelante en la misma página).

lo que creo que con el fin de conseguir una buena optimización de aquí, se necesita más que una "solución trivial" que hace una reasignación barato si es posible - que tiene que hacer de alguna manera un poco de preparación a hacer posible, y esa preparación le cuesta espacio de direcciones. Si solo lo haces para ciertos vectores, que indican que se convertirán en grandes, entonces es bastante inútil, porque pueden indicar con reserve() que se convertirán en grandes. Solo puede hacerlo de forma automática para todos los vectores si tiene un amplio espacio de direcciones, de modo que pueda "desperdiciar" una gran parte de él en cada vector.

Según tengo entendido, la razón por la cual el concepto Allocator no tiene una función de reasignación es para mantenerlo simple. Si std::allocator tenía una función try_realloc, entonces cada Allocator debería tener uno (que en la mayoría de los casos no podría implementarse, y tendría que devolver siempre falso), o bien, todo contenedor estándar debería estar especializado para std::allocator a Toma ventaja de eso. Ninguna de las opciones es una excelente interfaz de asignación, aunque supongo que no sería un gran esfuerzo para los implementadores de casi todas las clases de asignación solo para agregar una función try_realloc de no hacer nada.

Si vector es lento debido a la reasignación, deque podría ser un buen reemplazo.

Answer 2

Se podría implementar algo así como el try_realloc usted propuso, mediante mmap con MAP_ANONYMOUS y MAP_FIXED y mremap con MREMAP_FIXED.

Editar: apenas se dio cuenta de que la página del manual de mremap incluso dice:

mremap() utiliza la tabla de páginas esquema de Linux. mremap() cambia la asignación de entre direcciones virtuales y páginas de memoria. Esto se puede utilizar para implementar muy eficiente realloc (3).

Answer 3

realloc en C es apenas más que una función de conveniencia; tiene muy poco beneficio para el rendimiento/reducción de copias. La excepción principal en la que puedo pensar es el código que asigna una gran matriz y luego reduce el tamaño una vez que se conoce el tamaño necesario, pero incluso esto podría requerir el traslado de datos en algunas implementaciones malloc (que segregan bloques estrictamente por tamaño) así que considero este uso de realloc realmente mala práctica.

Siempre que no reasigne constantemente su matriz cada vez que agregue un elemento, sino que crezca la matriz exponencialmente (por ejemplo, en un 25%, 50% o 100%) cada vez que se quede sin espacio, solo manualmente la asignación de nueva memoria, copia y liberación de la antigua producirá aproximadamente el mismo rendimiento (e idéntico, en caso de fragmentación de la memoria) al uso de realloc. Este es sin duda el enfoque que utilizan las implementaciones de C++ STL, por lo que creo que toda su preocupación es infundada.

Editar: El uno (raro pero no inaudito) caso en el que realloc es realmente útil es para los bloques gigantes en sistemas con memoria virtual, donde la biblioteca C interactúa con el núcleo de trasladar páginas enteras a nuevas direcciones.La razón por la que digo que esto es raro es porque debe tratarse con bloques muy grandes (al menos varios cientos de kB) antes de que la mayoría de las implementaciones ingresen al ámbito de la asignación de granularidad de páginas, y probablemente sean mucho más grandes (quizás varios MB). antes de entrar y salir del espacio del kernel para reorganizar la memoria virtual es más barato que simplemente hacer la copia. Por supuesto try_realloc no sería útil aquí, ya que todo el beneficio proviene de realidad haciendo el movimiento a bajo costo.