Hola Hoy me gustaría volver a hablar sobre el análisis estático. Y nuevamente sobre C ++. Solo, a diferencia de PVS-Studio, no buscaremos ningún error en nuestros programas (aunque no solo busquen errores), sino también lugares que no estén escritos de manera óptima. Y uno de estos lugares es elegir un contenedor para los datos en el programa. Si estoy interesado en ti, ¡entonces bienvenido a cat!
El problema
En CoreHard 2018 Autumn (una muy buena conferencia, venga) hablé sobre cómo los compiladores de C ++ no se optimizan bien en este momento. Y
una de mis quejas fue que los compiladores no pueden optimizar el uso de contenedores en nuestros programas. Veamos algunos ejemplos de código.
void foo() { std::vector<int> v(42); }
Parecería que en un caso tan simple, el compilador debería poder optimizar esta función y simplemente arrojar una declaración variable del tipo std :: vector, ya que a partir de C ++ 14 el compilador puede eliminar asignaciones de memoria dinámica, pero el compilador no lo hace. La razón de esto es que, por el momento, solo un compilador de C ++ implementa la optimización para eliminar las asignaciones dinámicas: Clang. Todos los otros compiladores hasta ahora no saben cómo hacer esto. Pero incluso Clang puede hacer esto en un número limitado de casos.
En este caso, podríamos reemplazar std :: vector con std :: array, siempre que el tamaño del vector seleccionado no sea demasiado grande, ya que es posible que no tengamos suficiente pila para dicho reemplazo. Tal reemplazo eliminará una asignación de memoria bastante costosa para el montón, y la ventaja es que cuando se usa std :: array, ¡el compilador ya puede arrojar std :: array de la función por completo!
Si hablamos de optimización del rendimiento, proponemos considerar el siguiente ejemplo:
void foo() { std::vector<int> v; for(int i = 0; i < 42; ++i) { v.insert(v.begin(), 42); } for(const auto val : v) { std::cout << val << ' '; } }
En este caso, vemos el uso de una operación extremadamente ineficaz en el caso de std :: vector - insertion al comienzo del contenedor. Todos los programadores de C ++ saben que esto es extremadamente malo, ya que hace que todos los elementos cambien cada vez, lo que conlleva grandes costos para copiar / mover. Sería mucho mejor en este caso reemplazarlo con std :: list, que no le importa dónde se realiza la inserción, o std :: deque (aunque es en este caso que puede ver claramente que no solo necesita usar insert. Pero este es solo un ejemplo, no más :)
Veamos otro código de ejemplo:
void foo() { std::list<int> v; for(int i = 0; i < 3; ++i) { v.push_front(i); } for(const auto val : v) { std::cout << val << ' '; } }
En este caso, podemos notar que podemos reemplazar sin problemas std :: list (sí, sé que pocas personas lo usan) con std :: forward_list. En este caso, en este caso, no perderemos absolutamente nada, pero obtendremos ahorros de memoria. Naturalmente, el compilador no hace tal optimización ahora.
Se puede hacer un truco similar en el siguiente ejemplo:
void foo() { std::deque<int> v; for(int i = 0; i < 3; ++i) { v.push_back(i); } for(int i = 0; i < 3; ++i) { std::cout << v.back() << ' '; v.pop_back(); } }
Aquí podemos ver que lo que realmente necesitamos no es std :: deque, sino std :: stack. Esto no se puede llamar optimización, ya que std :: stack es un adaptador, y por defecto usa std :: deque en su interior (a menos que el usuario especifique lo contrario). Aquí podemos hablar más sobre la optimización semántica, es decir simplificando el código para entender. Desde mi punto de vista, esto también es importante. Si usted pregunta: "¿Tal reemplazo de este tipo también proporciona un aumento de rendimiento?", Responderé "Tal vez. Consulte los detalles de implementación en su versión de la biblioteca estándar ".
Bueno, creo que hay suficientes ejemplos. Cada uno de ustedes también puede pensar en muchos de ellos.
Herramientas usadas
Para implementar el analizador estático, utilicé Clang Static Analzyer (CSA) y Clang Tidy, que forman parte del paquete LLVM. Elegí estas herramientas, ya que las considero las más prometedoras entre las herramientas abiertas para el análisis estático. Además, Clang proporciona uno de los analizadores de C ++ de la más alta calidad que otros analizadores estáticos no pueden presumir (a menos que, por supuesto, usen libclang).
Tanto CSA como Clang Tidy son analizadores estáticos, los cuales forman parte de LLVM. Cual es la diferencia La diferencia es que Clang Tidy está diseñado para escribir verificaciones simples, que básicamente consisten en encontrar algún tipo de patrón en el árbol de sintaxis abstracta, mostrar algún tipo de advertencia y posiblemente reemplazarlo automáticamente por otro. Puedes aprender más sobre Clang Tidy
aquí .
CSA está diseñado para escribir comprobaciones más "serias" e intensivas en recursos (tanto desde el punto de vista de la implementación como desde el punto de vista del tiempo de ejecución / memoria gastada). Allí, por ejemplo, hay disponible un mecanismo de ejecución simbólico.
Decidí implementar la verificación en CSA, ya que no me parece un lugar común, además, en el futuro será cada vez más difícil. Y se decidió ejecutar Clang Tidy, ya que este analizador estático tiene
muchas integraciones con varios IDE.
Cómo (intentaremos) resolver los problemas
Para empezar, vale la pena introducir un par de restricciones bastante fuertes, que están relacionadas principalmente con el hecho de que hasta ahora es solo un prototipo:
- Análisis solo a nivel de funciones; Esta limitación significa que no habrá análisis entre funciones, así como entre unidades de traducción. La restricción en el análisis entre funciones se impuso para simplificar la implementación de este análisis y en el futuro se puede solucionar con relativa facilidad ejecutando un análisis estático para toda la unidad de traducción, y no solo para cada función. La restricción en el análisis entre las unidades de traducción está impuesta por las restricciones existentes en el CSA, que se solucionarán pronto (ya se están enviando confirmaciones en el flujo ascendente);
- Soporte solo para un número limitado de contenedores. Esto se soluciona relativamente fácilmente en el futuro al agregar nuevas reglas para nuevos contenedores.
- Use para el análisis solo un árbol de sintaxis abstracta. Dado que para la creación de prototipos, este es el tipo de análisis más simple. Para obtener resultados más precisos, por supuesto, puede intentar usar al menos una ejecución simbólica, pero este método tiene sus inconvenientes. Puedes leer más sobre métodos aquí .
Ahora el prototipo implementa el siguiente algoritmo simple:
- Primero, en el árbol de sintaxis abstracta, encontramos los vértices que son responsables de declarar las variables de tipo contenedor que admitimos.
- Luego, encontramos las operaciones relacionadas con estos contenedores, las clasificamos y guardamos esta información en un caché temporal.
- Después de llegar al final de la función, analizamos las estadísticas recopiladas y, en base a reglas predefinidas, emitimos una recomendación sobre el uso de un contenedor.
La clasificación de las operaciones de contenedores en este momento es la siguiente (se ampliará en el futuro):
- Agregue un artículo a la parte superior del contenedor.
- Agregar un artículo a la mitad del contenedor.
- Agregar un artículo al final del contenedor.
- Eliminar un artículo desde el principio del contenedor.
- Retirar un artículo del medio del contenedor.
- Eliminar un artículo del final del contenedor.
La clasificación en este momento es incompleta e incluso en esta lista no funciona correctamente. Por ejemplo, la operación de inserción, incluso si se realiza al principio, el analizador clasifica como inserción en el medio, aunque en realidad no lo es en absoluto.
Lucha contra falsos positivos
En cualquier análisis estático, los falsos positivos son el principal dolor de cabeza. Si hay demasiados, se pierden mensajes útiles en la basura. Por lo tanto, en este caso, debe actuar de manera muy conservadora y emitir advertencias solo en los casos en que tengamos mucha confianza en nuestros diagnósticos y podamos decir que algo está realmente mal en algún lugar del código.
Si estamos hablando de la optimización del compilador, entonces todavía es más triste allí: la optimización adecuada no puede cambiar el comportamiento del programa de acuerdo con el Estándar C ++ (de lo contrario, dicho optimizador no tiene valor). Y la optimización tampoco debería introducir pesimismo :) Así que aquí debes ser mucho más cuidadoso en tus decisiones.
En este analizador, esta lucha resultó en el hecho de que si el analizador ve que actualmente se está realizando una operación no admitida, el análisis de este contenedor está desactivado.
Desventajas y posibles soluciones.
Hay varios problemas con este método.
El primer problema es que para el analizador en este momento todas las ramas del código son igualmente probables. Más precisamente, él ni siquiera sabe acerca de algo como las diferentes ramas de ejecución de código.
Esto se traduce en problemas con el análisis de algo como este código:
void foo(int* ptr, std::vector<int>& v) { if(ptr == nullptr) { v.insert(v.begin(), 42); } else { v.push_back(84); } }
Lo más probable es que, en nuestra aplicación, estas ramas de código no tengan las mismas probabilidades de ejecución, ya que en el mundo real un puntero generalmente indica algo normal, y no nullptr. En el mismo LLVM hay heurísticas estáticas en este puntaje. Por ejemplo, tiene en cuenta el caso anterior al comparar punteros con nullptr, y al comparar entre sí la igualdad de valores de dos variables con un punto flotante, y algunos otros casos interesantes. Pero esto se parece cada vez más a las muletas, y desde mi punto de vista, la solución real a este problema es agregar análisis dinámico o instrumentación.
El segundo problema es la falta de soporte para contenedores personalizados. Vivimos en el mundo de C ++, les gusta viajar aquí (dejemos la discusión de las razones de este fenómeno no siempre malo fuera del alcance de este artículo) todo, incluidos nuestros contenedores. Los ejemplos incluyen el mismo LLVM, LibreOffice y muchos otros. A este respecto, surge la pregunta: ¿cómo analizar los contenedores que no provienen de la biblioteca STL? Después de todo, me gustaría incluir el análisis de tantos contenedores como sea posible.
Hay diferentes formas de resolver el problema.
El primero es que el usuario anota sus contenedores de alguna manera (un tipo especial de comentario, atributos de C ++, algo más). El problema con este método es que necesitamos entender cómo anotar, en general, qué información necesitamos para un análisis cualitativo. Otro problema puede ser la modificación del código de los propios contenedores, que no siempre es posible.
El segundo método ofrece al usuario un mecanismo para escribir sus propias reglas. Por el momento, las reglas en el analizador están cosidas en el código fuente del analizador en sí, y si el usuario desea agregar sus propias reglas, entonces deberá descargar el código fuente del analizador, armarlo, descubrir cómo escribir cheques, escribir, reconstruir, etc. Puede proporcionar al usuario una forma de configurar sus comprobaciones en algunos DSL, donde el usuario escribe solo comprobaciones para sus contenedores y el analizador participa en toda la rutina. Considero que este método es más prometedor que el anterior.
Además, el reemplazo automático de contenedores no es compatible, ya que esta funcionalidad no está en CSA (pero sí en Clang Tidy). Pero en casos difíciles, realizar la Autocorrección no siempre es una tarea trivial, y el analizador funciona más probablemente en modo semi-manual.
Posibles aplicaciones
Veo varias aplicaciones para este tipo de análisis:
- Como un analizador estático. Aquí todo es simple: otra prueba de análisis estático, que ejecuta según lo desee su corazón (con sus manos, en el IDE automáticamente durante el desarrollo, en CI, etc.), donde probablemente se le dará una pista de que en algún lugar podría recoger un contenedor y mejor.
- Como optimización en el compilador. En algunos casos, podemos garantizar que reemplazar el contenedor definitivamente no afectará negativamente el rendimiento. Por ejemplo, reemplazando std :: vector por tamaños pequeños conocidos en tiempo de compilación con std :: array o reemplazando std :: list por std :: forward_list cuando no necesitamos biconnectness y no tomamos el tamaño de la lista. El compilador podría reemplazar los contenedores con otros más óptimos sin nuestro conocimiento, como ya lo hace para una gran cantidad de cosas.
- Como un analizador dinámico. Esta es la dirección que me parece más prometedora para este tipo de análisis. De hecho, con la ayuda del conocimiento sobre el perfil de ejecución del programa, nosotros, por ejemplo, podemos obtener información tan importante para nosotros como las probabilidades de cada ejecución de ramificación de código. Y esto es necesario para una evaluación más precisa. Y con tal análisis, ya puede pensar en la dirección de integración con PGO ...
También vale la pena señalar que este método es aplicable, por supuesto, no solo para los programas de C ++. Realmente me gustaría ver este tipo de análisis / optimización estática en el compilador y para otros lenguajes de programación. Por ejemplo, el analizador estático de SAP para ABAP ya sabe cómo llevar a cabo análisis de optimización estática a un nivel básico, lo cual es una buena noticia. Si conoce proyectos similares para otros lenguajes de programación, escriba en los comentarios y los agregaré al artículo.
Trabaja en direcciones similares
Para el mundo C ++, no he encontrado analizadores de este tipo en ningún lado. Para el mundo ABAP, mencioné el analizador anterior, que puede encontrar operaciones ineficientes para alguna parte de los contenedores estándar, pero que yo sepa, se implementa un análisis estático muy simple allí.
Un trabajo mucho más interesante es
Chameleon , un analizador dinámico para Java, que se realiza de manera muy inteligente. Ajustaron un poco la JVM, y durante la operación recopilan varias estadísticas sobre el uso de contenedores y, según el perfil de carga actual, seleccionan ciertos contenedores y los reemplazan automáticamente durante la operación. Desafortunadamente, las fuentes están cerradas y no hay posibilidad de obtenerlas (lo intenté).
También recomiendo mirar varios trabajos (hay muchos) en
SETL . En ellos, los autores también solían plantear preguntas sobre la selección automática del contenedor.
Referencias
- Implementación actual en github
- C ++ Rusia 2017: Yuri Efimochev, clang-tidy: un viaje dentro del árbol de sintaxis abstracta de C ++
- Camaleón: selección adaptativa de colecciones
- Guía de analizador estático de Clang
- Chat en idioma ruso sobre el desarrollo de compiladores en Telegram. Si estás interesado, entra, es muy interesante allí. Solo ten cuidado con la inundación, inmediatamente lo castigarán :)
En lugar de una conclusión, me gustaría centrarme en el hecho de que hasta ahora es solo un prototipo y tiene demasiados "agujeros" en la implementación. En este artículo, solo quiero compartir con ustedes la idea de tal análisis y su popularización. Bueno, tal vez alguien esté interesado en este tema y haya un deseo de conectarse con el proyecto. ¡Solo estaré feliz! Además, siempre puede recopilar este analizador en su propio lugar para probarlo en sus ejemplos de prueba.
Si tiene algo para complementar el material, ha encontrado una tarea similar o simplemente tiene alguna información que puede ser útil sobre este tema, no dude en compartir esta información en los comentarios.
Gracias por su atencion!