“¿No es hora, amigos míos, de que nos acerquemos a William? ".
Recientemente leí una publicación sobre un teclado personalizado y una vez más pensé que sería bueno escribir una referencia (es decir, una que no se avergüence de firmar con su nombre y ponerla en exhibición pública) una implementación de teclado. Esta idea no se me ocurre por primera vez, pero de alguna manera se detiene en la primera etapa: leer la información inicial, porque quiero que esta etapa sea fácilmente personalizable, fácil de usar, universal y efectiva, y no me gusta la oferta "elige dos".
Nota necesaria: veo 4 capas de implementación de teclado: 0: detección de eventos, 1: lectura de datos, 2: limpieza y almacenamiento de datos, 3: generación de mensajes, 4: transcodificación, etc. Lo más prometedor para la capa 1 y la capa 0 asociada con él me parece el uso de plantillas de Anton Chizhov para trabajar con pines MK (basados en la clase Loki) y, quizás, algún día, el resultado resultante no se avergonzará de compartir, pero ciertamente no hoy. Ahora estoy pensando en la capa 2.
Formulemos el problema: es necesario almacenar información sobre un conjunto fijo de interruptores que toman uno de los dos valores predefinidos: "cerrado" y "no cerrado". Los candidatos más naturales son las variables booleanas y la biblioteca de conjuntos de bits, como una forma de almacenar un conjunto. Dado que el requisito de eficiencia es un imperativo categórico, es deseable evaluar la implementación del módulo desde este punto de vista.
Lo primero que pensé fue mirar los códigos fuente y todo se aclaró de inmediato, pero después de un breve conocimiento de ellos, me di cuenta de que aprender sobre las plantillas de otras personas no era muy interesante (y no muy productivo). Además, las fuentes no ofrecen una evaluación precisa de la efectividad de la implementación, ya que está directamente cerrada al compilador. De hecho, el texto fuente aún tenía que estudiarse, de lo contrario, realizar cambios en él se convierte en un proceso muy largo (a menos, por supuesto, que estemos interesados en lograr un cierto resultado), pero este es un tema para una publicación separada.
Por lo tanto, se adopta la técnica de estudiar la "caja negra": alimentamos varios fragmentos de código a la entrada y consideramos el ensamblador generado. Desafortunadamente, no es posible usar el sitio godbolt favorito para la arquitectura AVR familiar, ya que no hay una biblioteca en estudio en esta implementación. Por supuesto, puede arrastrarlo con lápices, pero no hay garantía de que sea el código fuente correcto.
Por lo tanto, veremos una arquitectura diferente. x51 no se presenta para el compilador gcc, nunca me gustó x86, ARM tiene un ensamblador no muy conveniente (para una persona) y comprensible, MIPS es muy específico y no muy común, todo tipo de SPARC es aún peor (bueno, bueno, no ofenderé a nadie con tu arquitectura favorita, no mejor), pero hay un gran candidato MSP430, que se basó en la arquitectura cristalina y elegante de PDP y TI no pudo estropearlo mucho (aunque los chicos lo intentaron). Se presenta una biblioteca de muchos bits para esta arquitectura, por lo que puede comenzar a estudiar.
Comencemos, ya que no suena trivial, desde el principio, es decir, con el anuncio de la multitud. Inmediatamente veremos que la memoria para el almacenamiento se asigna en palabras de cuatro bytes, a pesar de que la unidad natural en esta arquitectura es una palabra de dos bytes, y se proporciona un trabajo bastante conveniente y eficiente con bytes, lo que conduce a incidentes extraños. Puede entender al autor, la implementación de un número de 32 bits debe estar en todas partes y depender de él de forma bastante natural, pero en este caso, sería preferible 8 bits, y para AVR, 8 bits sería la única solución razonable.
Una pregunta interesante, pero ¿cómo puede determinar la profundidad de bits de la arquitectura durante el proceso de compilación? Deberá probar a través de uint8_t_fast. Observamos una posible optimización y seguimos adelante.
Además de asignar memoria, la inicialización es interesante: para los conjuntos globales se realiza de la manera estándar, la puesta a cero antes de llamar a main, para los conjuntos locales también se realiza de la manera estándar, es decir, de ninguna manera si el valor inicial no se especifica explícitamente. Bueno, y, como siempre, si es posible describir un conjunto estático con un valor inicial fuera de la función, esto debería usarse para no activar indicadores innecesarios y no perder tiempo de ejecución en ellos. Pero aquí no esperábamos ninguna revelación, solo verificamos las reglas generales.
Comencemos a trabajar modificando el conjunto, para lo cual hemos dejado corchetes y establecer y restablecer métodos. Podemos esperar ver algo como esto para establecer el elemento n en el conjunto M:
M[n / w] |= (1<<(n % w))
donde w es el número de bits en el elemento base, que para una arquitectura dada, estáticamente definido n (por ejemplo, 4) y la optimización incluida conduce a un código de la forma:
bis.w #0x0010, m
De hecho, vemos dicho código en la mitad derecha de la ventana, y es poco probable que alguien se arriesgue seriamente a afirmar que es posible una solución más efectiva. Pero esto es solo para las condiciones indicadas, para un arbitrario n la imagen cambia completamente, para los métodos observamos la validación del argumento de admisibilidad con la generación de la excepción correspondiente, y para los corchetes vemos la restricción del argumento con una máscara de bits del rango permisible con un comportamiento indefinido completamente predecible, ambos casos son bastante consistentes con la documentación. Los valores negativos se procesan correctamente, ya que los índices se consideran números sin signo.
Llamamos la atención sobre el hecho de que el valor asignado para un elemento de un conjunto puede ser no solo 0 y 1, como cabría esperar, sino también cualquier número entero para el cual la regla “¿Qué es unidad? No es cero ”, es bastante lógico, pero está mal reflejado en la documentación. Un poco extraño, sin embargo, los valores booleanos serían más naturales, marcarían y seguirían.
La comparación del código generado para el caso de un número de elemento estáticamente indeterminado del conjunto muestra que la eficiencia del código en ambos casos ([] y métodos) es muy estrecha y pequeña, ya que se llama a una subrutina de la biblioteca estándar para calcular (1 << n), y esta subrutina cambia Número de 32 bits 0x00000001, colocado en dos registros. No podemos ver su texto fuente, pero el hecho mismo de la llamada conduce a pensamientos tristes. El hecho es que en la arquitectura bajo consideración no hay desplazamiento hacia la izquierda (y tampoco hay derecha) por un número arbitrario de posiciones, como en todas (muchas) ARM queridas. Hay un cambio por 1 posición (sería extraño si no existiera), hay un cambio por 2,3,4 posiciones (pero por un número estrictamente fijado en el comando, no por un parámetro), hay un prefijo REPT (pero su velocidad de ejecución se va desear lo mejor). Puede implementar el cambio de la unidad más pequeña (esto es importante, solo una unidad), es decir, obtener una máscara de bits por el número de bits en un tiempo relativamente corto mediante trucos como el intercambio de tétradas, pero esta será una parte muy dependiente y, en el caso general, es mejor no hacerlo.
Por lo tanto, un método universal y rápido sería almacenar máscaras de bits en una matriz e índice, y en esta arquitectura también es muy eficiente, el código se ve así:
M[n/w] |= BitArray[n %w]
conseguir ensamblador como:
bis.b BitArray(r0),M(r1)
Como estamos hablando de patrones yw es un múltiplo del tamaño de un byte, las operaciones de división se implementan de manera muy eficiente aquí. Observamos la clara ventaja de un elemento de almacenamiento mínimamente implementado: para un byte, se requiere una matriz de 8 bytes para un byte, -2 * 16 = 32 bytes para la organización de palabras, y 4 * 32 = 128 bytes para una palabra larga de 32 bits para almacenar todo lo requerido Máscaras, ¿por qué pagar más si el resultado no cambia? Recordemos una posible optimización más y sigamos adelante.
Observamos un hecho más: son posibles implementaciones mucho más eficientes de operaciones con un elemento establecido si la arquitectura de destino tiene una región de memoria marcada con bits (aquí nuevamente, se recupera el ARM rechazado anteriormente), donde la operación de instalación del elemento generalmente se convierte en un BitSetAddr [n] = calabaza 1, que se traduce en un comando de ensamblador para n constante, pero ya hay suficientes cambios efectivos allí, por lo que dicha optimización será más redundante, especialmente teniendo en cuenta sus limitaciones. En principio, hay un área de direccionamiento de bits similar tanto en x51 como en AVR, pero hay comandos efectivos solo para números de elementos constantes y, en el caso general, no todo es tan bueno (francamente malo).
Bueno, ahora observe detenidamente el código resultante y observe que observamos artefactos asociados con el almacenamiento del conjunto en palabras dobles. El compilador para la operación de modificar un elemento de un conjunto genera una secuencia de comandos que leen la palabra doble correspondiente de la memoria en 2 registros (recuerdo que tenemos registros de 16 bits), los modifica y envía los resultados de vuelta a la memoria. Si cambiamos solo un elemento, la máscara de operación contendrá exactamente una unidad de 32 posibles, los ceros restantes. Cuando aplicamos un número de elemento definido estáticamente, las operaciones que no cambian el resultado deben excluirse en la etapa de optimización. Como regla, esto sucede, pero para varios operandos algo sale mal y los artefactos de la forma se filtran en el código final:
bic #0,r0
lo que se ve especialmente divertido si notas que el registro no se vuelve a escribir en la memoria, aunque se lee. Estrictamente hablando, los resultados de las optimizaciones no están regulados en ninguna parte, por lo que pueden ser cualquier cosa, y no hay nada de qué ofenderse, pero de todos modos, "no está claro cómo funciona". No podemos influir directamente en este proceso, si no consideramos seriamente el código fuente del compilador, así que omitámoslo: ayudaremos al optimizador simplificando su tarea.
Por cierto, todavía no puedo encontrar la respuesta a la pregunta: ¿es posible en C ++ a nivel de macro o plantilla definir una implementación diferente para lo estáticamente definido en la etapa de compilación contra el parámetro estáticamente indefinido? Si alguien conoce el camino del samurai, dígame en los comentarios, probé constexpr, no funcionó.
Continuamos nuestra investigación y descubrimos que el compilador está optimizando incontrolablemente las llamadas al conjunto (por supuesto, si la optimización está activada), es decir, el orden de instalación / limpieza de varios elementos no está completamente garantizado y no está conectado de ninguna manera con el orden de los operadores de código fuente. Pero no pude crear un conjunto volátil, ¿tal vez estoy haciendo algo mal? Como en el caso de cualquier optimización local, la llamada a una función externa obliga al compilador a forzar todas las operaciones preparadas para la matriz global, pero esta es una solución demasiado fuerte y no ayuda con las locales. Bueno, probablemente no haya nada que hacer, y solo necesita tener en cuenta una característica similar y no usar conjuntos para transferir información entre flujos utilizando interfaces seriales (es decir, sus contrapartes de software).
Se puede llegar a una conclusión general: no se puede recomendar el uso de bitset en su forma actual para arquitecturas con recursos limitados debido a costos excesivos tanto en memoria como en tiempo de ejecución. Una posible modificación, que tiene en cuenta todos los datos en el texto del comentario, recae en Github, todos pueden usarlo. La historia de la creación de este mod pronto se publicará en Habré, hubo momentos divertidos.
En conclusión, una pequeña observación: la implementación del almacén de datos "de frente", incluso en la versión optimizada del conjunto, requerirá N / 8 bytes de memoria de datos (para 128 conmutadores, se requerirán 16 bytes) y aunque las operaciones requerirán tiempo O (1), el multiplicador será de muchas unidades ( e incluso hasta 10 o más) ciclos de MK. Por lo tanto, teniendo en cuenta los requisitos del problema e introduciendo ciertas restricciones, podemos ofrecer una implementación alternativa de almacenamiento de datos.
Si creemos que no se puede cerrar más de un interruptor en cualquier momento (ignoramos todos los demás hasta que se abra el botón que se presiona en ese momento), entonces podemos omitir un byte (siempre que no haya más de 256 interruptores) y la escritura / lectura tomará O (1) ciclos de procesador, y el multiplicador será bastante modesto.
Este enfoque es fácil de expandir y almacenar información sobre n interruptores cerrados simultáneamente, pero no debe hacer n demasiado grande, ya que la cantidad requerida de memoria aumenta, y el tiempo para realizar operaciones de inversión aumenta linealmente con un aumento en el número de elementos en el conjunto, aunque permanece O (1) por en relación con el número de interruptores. El aumento de tiempo indicado puede reducirse significativamente usando la implementación triangular del árbol binario a O (loq2 (n)), pero para n pequeña esto no es tan importante. Sí, y es dudoso que la complejidad de calcular el siguiente índice durante la búsqueda compense la disminución en el número de iteraciones simples. Las desventajas de esta implementación incluyen una posible falla al registrar el elemento del conjunto, que debe procesarse en el programa de llamada (rechazamos la opción con un tamaño de búfer cambiante inmediatamente y con indignación; esto no es para soluciones integradas).
La implementación de este enfoque se dará allí.