optimización de cadena pequeña para vector?

Sé que varias implementaciones de STL implementan una optimización de "cadena pequeña" donde en lugar de almacenar los 3 punteros habituales para inicio, final y capacidad, una cadena almacenará los datos de caracteres reales en la memoria utilizada para los punteros si sizeof (caracteres) < = sizeof (punteros). Estoy en una situación en la que tengo muchos vectores pequeños con un tamaño de elemento < = sizeof (puntero). No puedo usar matrices de tamaño fijo, ya que los vectores deben poder cambiar el tamaño dinámicamente y pueden crecer bastante. Sin embargo, el tamaño mediano (no medio) de los vectores solo será de 4-12 bytes. Por lo tanto, una optimización de "cadena pequeña" adaptada a vectores sería bastante útil para mí. ¿Existe tal cosa?optimización de cadena pequeña para vector?

Estoy pensando en hacer rodar mi propia fuerza simplemente convirtiendo un vector en una cadena, es decir, proporcionando una interfaz vectorial a una cadena. ¿Buena idea?

Fuente

2010-02-01 BuschnicK

Su pregunta no es muy clara. Además, ¿qué quiere decir con una interfaz 'vector' con una' cadena'? ¿Estás hablando de una clase especial 'svector' para contener cadenas pequeñas? – dirkgently

No. Me refiero a una cadena que contiene valores arbitrarios en lugar de tipos de caracteres, como un vector. Una interfaz vectorial a una cadena significa envolver el objeto cadena y exponer una interfaz compatible con vectores, agregando las funciones que faltan como push_back. – BuschnicK

¿No sería más posible hacer algo con el asignador? No obtendría ni siquiera 3 puntos de memoria, ya que el vector también necesita una forma de saber si está en el modo "pequeño" o "grande". – UncleBens

Puede pedir prestada la implementación SmallVector de LLVM. (solo encabezado, ubicado en LLVM \ include \ llvm \ ADT)

Fuente

2010-02-01 17:29:49

Ya no es solo encabezado. – rightfold

encabezado está aquí: https://github.com/llvm-mirror/llvm/blob/master/include/llvm/ADT/SmallVector.h – Nick

Hace discussed años (y algunos de los nombres en ese hilo pueden parecer un poco familiares :-)), pero no sé de una implementación existente. No creo que intente adaptar std :: string a la tarea. Los requisitos exactos sobre el tipo sobre el cual std :: basic_string no están bien establecidos, pero el estándar es bastante claro que solo está destinado a algo que se parece mucho a char. Para los tipos que son sustancialmente diferentes, todavía podría funcionar, pero es difícil decir qué sucedería, nunca fue pensado y probablemente no se haya probado con muchos otros tipos de enteros pequeños.

Cuando llegue a este punto, implementar std::vector desde cero (incluso incluyendo una optimización vectorial pequeña) no será terriblemente difícil.

Fuente

2010-02-01 16:47:49

+11

Implementar 'std :: vector' * correctamente * desde cero es sorprendentemente difícil. Por supuesto, si elige ignorar la seguridad de excepciones, se vuelve mucho más fácil, pero ya no es una implementación de 'vector' significativa (o útil). – jalf

Gracias por el puntero - desafortunadamente la discusión nunca llegó a una conclusión. Implementar mi propio vector no sería tan difícil, estoy de acuerdo. Sin embargo, esperaba simplemente conectar algo de clase preparada y ver el efecto en el consumo de memoria. Actualmente estoy jugando con varias ideas para reducir nuestra huella de memoria y esta es solo una de ellas. – BuschnicK

Cuando eso se dice, creo que una implementación de vector personalizado sería la mejor manera de lograr esto. Envolver la clase vectorial existente dificultaría la explotación del tamaño del objeto de manera eficiente, y un vector personalizado no es una ciencia revolucionaria, siempre que tenga cuidado y sepa lo que hace. – jalf

Si T es un tipo de POD, ¿por qué no basic_string en lugar de vector?

Fuente

2010-03-14 18:21:11

Tenga en cuenta que tendría que escribir una especialización 'std :: char_traits' (o una clase de rasgos equivalentes) para el tipo de POD. Los requisitos no son tan severos, aparte de la necesidad de nominar un valor especial de 'eof', pero espero que sea algo tedioso. –

Además, no hay garantía de que 'basic_string ' usará una optimización de cadena pequeña, y ninguna forma portátil de especificar cuántos elementos, incluso si lo hace. –

Boost 1.58 acaba de lanzarse y su biblioteca Container tiene una clase small_vector basada en el LLVM SmallVector.

También hay un static_vector que no puede crecer más allá del tamaño inicialmente dado. Ambos contenedores son solo de encabezado.

facebook's folly biblioteca también tiene algunos contenedores increíbles.

Tiene un small_vector que se puede configurar con un parámetro de plantilla para actuar como los vectores static o small de boost. También se puede configurar para usar tipos enteros pequeños para su contabilidad de tamaño interno que, dado que son Facebook, no es sorprendente :)

Hay un trabajo en progreso para hacer que la biblioteca se multiplique para que el soporte de Windows/MSVC llegue algún día ...

Fuente

2015-04-17 10:47:24 onqtam

optimización de cadena pequeña para vector?

Respuesta

Cuestiones relacionadas