“Qualquer um pode resolver o paradoxo de Grey com golfinhos, e você tenta fazê-lo sem golfinhos. "
Na verdade, eu planejava passar o fim de semana de uma maneira um pouco diferente, ir ao Copter Huck (não que eu fosse fã de helicópteros, apenas para ver o que os jovens estavam inventando, para sair assim), mas a irmã mais velha era categoricamente contra. Obviamente, eu insisti (ou seja, eu ri algumas vezes e disse: "Bem, talvez ... seja divertido, de qualquer maneira"), mas ela era implacável e, quando minha esposa ficou do seu lado, não havia chance de uma viagem. Bem, tudo bem, "eu realmente não queria", mas sentei-me um pouco sobre um quebra-cabeça engraçado do campo de programação, que pensei por mim mesmo, sobre o qual estou relatando.
(Observação necessária - o fim de semana anterior foi feito, é sempre assim - a elaboração de um programa requer algumas horas, a elaboração de um relatório sobre o assunto e cinco dias de viagem em transporte público não são concluídos.)
Em um post recente, o autor considerou o problema de acelerar (entre outras coisas) o cálculo das curvas de Bezier (KB) no MK com parâmetros relativamente fracos. Bem, de fato, esses parâmetros estão no nível do mainframe médio dos anos 70, mas atualmente são considerados claramente insuficientes. Como resultado de certas ações, o autor conseguiu acelerar um pouco os cálculos, na minha opinião, claramente não é suficiente, então decidi escrever como isso deve ser feito como uma primeira aproximação. Conheço perfeitamente a receita universal para resolver problemas de desempenho - levar o MK com uma frequência mais alta ou mudar para outra família, mas venho do momento em que o estudamos custou o que é, simplesmente porque não havia mais nada da palavra. Atualmente, a abordagem está desatualizada, mas me pareceu que não seria desinteressante para os leitores modernos de Habr.
Afirmamos o problema - queremos calcular as coordenadas dos pontos na curva de Bezier definidas pelos pontos extremos A e B e o foco imaginário C. o mais rápido possível.A fórmula para calcular o ponto P na curva é dada por
onde T varia de 0 a 1 inclusive. (No Wiki, eles escrevem que essa fórmula era secreta ao mesmo tempo, era estranho assim, mas tudo é possível). É claro que não o tomaremos de forma complexa, em vez disso, procuraremos separadamente as coordenadas X e Y. Estimaremos a complexidade do cálculo usando essa fórmula, simplesmente contando o número de sinais de operações aritméticas nesta expressão - 7 multiplicações e 5 adições (=> 7 * 5 + ) É possível que um bom compilador (e agora todos os compiladores sejam bons e otimize perfeitamente se você não os proibir explicitamente) reduza os custos para 7 * 3 +, embora seja melhor ajudá-lo calculando (1-T) com antecedência. De um modo geral, um bom compilador geralmente pode fazer maravilhas se todos os valores na fórmula são representados por constantes, mas assumimos que todos os valores são estaticamente indefinidos.
Parte Um, Matemática
Iniciamos o processo de otimização, para o qual expandimos os colchetes e agrupamos os termos em T (talvez um dia o compilador possa fazer isso por nós, mas até agora essa parte do trabalho é atribuída à inteligência natural), obtendo
=> 5 * 5 +, que é claramente melhor que o valor inicial de 7 * 5 +, mas 7 * 3 + relativamente melhorado ainda deve ser considerado.
Se dedicarmos algum tempo para concluir a operação de adição como um só, o tempo para concluir a multiplicação será exatamente não menos que um, como regra, mais longo, mas quanto isso depende da implementação do MK (primeiro escrita - na arquitetura, mas isso não é totalmente verdade). Quando não houver multiplicador de hardware no cristal, o tempo de execução da multiplicação será dez (30+) vezes maior que um e, quando estiver presente, será várias vezes (1-6). Portanto, podemos acreditar com confiança que substituir a multiplicação pela adição gera um ganho (e geralmente significativo) no tempo de execução quase sempre. Bem, notamos imediatamente que a transição de números de ponto fixo para ponto flutuante (deixamos de lado a prova desse fato) leva a um aumento no tempo de execução em mais de 20 vezes para adição (o alinhamento é muito influente aqui), mas apenas para um pequeno aumento na multiplicação . Portanto, para números de ponto flutuante, os tempos de adição e multiplicação diferem pouco, especialmente em termos relativos (podemos esperar um máximo de 2 vezes), mas eles ainda diferem e não são a favor da multiplicação, portanto, há um ganho aqui.
Voltando ao parágrafo anterior, descobrimos que para a PT a classificação 5 * 5 + não deve ter uma vantagem significativa sobre 7 * 3 +, mas ainda temos reservas. Preste atenção ao fato de que devemos calcular o conjunto de pontos na curva de Bezier quando o parâmetro T mudar e todos os outros parâmetros da curva forem fixos (mas não constantes, mas desculpe), o restante da fórmula poderá ser calculado antecipadamente e obter
=> 3 * 2 +, em que
e
já é bom, mas se você se lembra do esquema de Horner e escreve
=> 2 * 2 +, em comparação com a decisão "na testa", temos que vencer mais de 2 vezes, quase 3, e essas otimizações são completamente óbvias.
Vamos verificar a teoria com prática (embora isso seja completamente redundante, estamos confiantes em nossas estimativas, mas de repente subestimei o compilador), para o qual precisamos medir o tempo real de execução de diferentes opções em hardware real. Bem, aconteceu que em casa eu tenho muitos tipos de placas de depuração para MK de várias empresas (incluindo raridades como depurações da Luminary Micro ou Intel Edisson, tentamos comprar uma agora), mas não existe uma única placa Arduino ("Bem não temos abacaxi "). Parece um beco sem saída, mas existem opções - um site muito interessante que o tinkercad.com vem em nosso auxílio, no qual você pode construir seu circuito em uma placa de ensaio usando o módulo Arduino, escrever um esboço e executá-lo imediatamente. Ao mesmo tempo, você pode definir pontos de interrupção, executar o programa passo a passo e até (uma coisa sem precedentes para um Arduino real) visualizar os valores das variáveis no momento da falha.
Nos voltamos para este site e começamos a medir. Para começar, verificamos nossas suposições sobre o tempo de execução das operações e, depois de esclarecidas as circunstâncias, obtemos os seguintes dados para números inteiros:
8 + 8 => 8-1 batida, 16 + 16 => 16-2,
8 * 8 => 16 - 2, 16 * 16 => 16 - 14 (a única coisa que acabou sendo inesperada, pensei em obter 4 * 2 + 4 * 2 = 16, há otimizações interessantes),
8/8 => 8 - 230, 16/16 => 16 - 230.
Preste atenção nos dois últimos dígitos, é claro que a operação de divisão é proibida se realmente quisermos contar rapidamente. Agora (finalmente) medimos o tempo necessário para executar operações nos números de PTs com uma mantissa de 24 bits
a + b - 126 (e depende muito de operandos), a * b - 140, a / b - 482.
Os dados obtidos se correlacionam bem com nossos pressupostos teóricos, é claro que existe uma implementação de hardware a bordo deste MK: para multiplicação, divisão, e não operações, PT.
Agora começamos a medir o tempo do cálculo completo. Definimos os valores A = 140, B = 120, C = 70 e construímos 170 pontos distribuídos uniformemente no departamento de design. Por que exatamente esses valores - eles foram dados no post especificado ao avaliar o desempenho. Abaixo estão os algoritmos e o tempo de execução do teste correspondente.
Fórmula (1) => 20ms ou 1.900 ciclos de relógio por amostra
Fórmula (1) => 18ms ou 1660 ciclos de relógio por amostra (considere separadamente 1-T)
Fórmula (2) => 16ms ou 1540 ciclos de relógio por amostra
Fórmula (3) => 10ms ou 923 ciclos de relógio por amostra
Fórmula (4) => 8ms ou 762 medidas por contagem
Pode-se observar que a redução resultante no tempo de execução (de 20ms para 8ms) correlaciona-se bem com o esperado e conseguimos acelerar os cálculos mais de 2 vezes. Observe que, além de considerações e matemática completamente óbvias, não indo além do curso do ensino médio, não precisávamos.
E agora vamos falar sobre o que fazer se o resultado não for suficiente e já extraímos tudo das fórmulas de cálculo. Eles escreveram aqui para mim (nos comentários de outro post) que, em geral, qualquer problema pode ser reduzido à computação com FT e, apesar da óbvia controvérsia da suposição (tente fazer isso para a solução numérica das equações de Navier-Stokes), neste caso específico, essa recomendação é aplicável Embora, como sempre, haja nuances.
Parte Dois, Computação
Uma vez esgotadas as modificações no algoritmo, apenas as estruturas de dados permanecem e entramos no solo dos números de ponto fixo. Aqui encontraremos muitas armadilhas nas quais não pensamos em termos de alcance e precisão do PT (em geral, para o PT deve-se pensar sobre essas questões, mas aqui tudo é mais simples, muito foi feito por nós). É necessário realizar um pequeno estudo do problema para determinar a representação necessária da TF (selecionada no post 9.7 acima mencionado, a julgar pelos resultados, é claramente insuficiente), mas proponho um caminho ligeiramente diferente. A propósito, se não dermos 170 passos no intervalo, mas 128 (não vejo razão para nos proibir dessa etapa), essa ideia nos servirá perfeitamente. Se levarmos em conta o fato de que as constantes que definem o KB são dadas por números inteiros, e o único parâmetro T pode ser representado por uma fração do formulário e / e usaremos o resultado para renderizar na tela, ou seja, traduzir em coordenadas inteiras, podemos basta fazer tudo em números inteiros, que processam muito mais rápido.
Usamos apenas a última fórmula e a reescrevemos na nova notação
(=> 2 * 2 + 2 /), em que A1 e B1 são calculados da mesma maneira que para PT. Obviamente, todos os números são inteiros e as operações correspondentes devem ser executadas muito mais rapidamente. Para não perder a precisão durante a operação da divisão inteira (2/3 = 1! = 1,5) e fazer a divisão no último momento, transformamos levemente a fórmula na forma
(=> 4 * 2 + 2 /). Todos os números do FT, então implementamos esse algoritmo e obtemos ... aqui está, avó e o dia de Yuryev ... 1869 ciclos, mas isso é muito pior do que para o FT, partimos disso, algum tipo de lixo, porque os números inteiros são muito mais rápidos.
Começamos a análise e acontece que apenas alterar o tipo de variáveis não é suficiente. Primeiro, devemos usar números não 8 ou mesmo 16, mas 32 bits, caso contrário, ocorrerá um excesso e números longos, embora mais rápidos que o PT, mas não tanto para compensar as falhas do algoritmo. novamente tivemos constantes calculadas em cada medida - as removemos por cálculo preliminar B2 = B1 * I, A2 = A * I * I. Então nós temos
(=> 2 * 2 + 2 /) com um resultado de 1684 é melhor que o anterior, mas ainda não nos afastamos.
Excluímos o cálculo de mais uma constante And2 = And * E obtemos
(=> 2 * 2 + 1 /), com o tempo de execução de 956 ciclos - mas isso é interessante, a exclusão de uma operação levou a um aumento significativo na produtividade.
Isso é o que nos atrasa - a divisão, porque é uma operação muito demorada, mas temos um truque interessante para lidar com isso. Para calcular a expressão 1 / E podemos realizar transformações elementares 1 / = 1 / * ( / ) = 1 * ( / ) / . Se escolhermos o grau de dois como H, a divisão por H poderá ser substituída por turnos, e se o expoente for múltiplo de 8, não serão necessários turnos pares. E o valor de N / A terá que ser calculado honestamente, mas apenas uma vez, após o qual somente a multiplicação permanece no ciclo de cálculo.
Preste atenção ao fato de que fizemos uma conversão não muito correta e substituímos o N / A pelo seu valor arredondado K para passar às operações exclusivamente com números inteiros. O erro consiste na perda de precisão e pesquisas adicionais devem ser realizadas para comprovar a aplicabilidade dessa abordagem ao nosso caso. Escrevemos H / I na forma (K * I + d) / I = K + (d / I), onde q é menor que I. Então o erro absoluto em ir de H / I a K será d / I e o erro relativo será d / I I / (K + d / I)> = d / I / (K + 1) ~ d / I / K, desde que K >> 1 (isto não é uma mudança). Daqui resulta que o valor de H deve ser escolhido o maior possível, uma vez que o erro de cálculo absoluto é igual a A * d / I / K> = A * 1 / N / I. Se queremos que o erro não seja mais do que unidade, devemos suportar a condição A / K <= 1, então K> = A, converter K * I> = A * I, o que significa H> = A * I, então não o fazemos perdendo em precisão. No nosso caso, A <= 256 e I <= 256, obtemos H> = 2 ** 16, o que é bastante aceitável. Obviamente, nas fórmulas acima, os módulos dos números originais devem ser usados.
Observamos no futuro que, se arredondarmos não para baixo, mas em direção ao número inteiro mais próximo, os requisitos serão um pouco reduzidos e H deverá ser a metade o suficiente, embora haja nuances.
De qualquer forma, podemos fornecer a precisão necessária e obter o seguinte algoritmo: H = 2 ** 16; K = [N / A] (I <256); 0 <= e <= AND;
(=> 4 * 2 + 2 >> 16) onde todas as operações são realizadas em números inteiros longos. Implementamos esse algoritmo e obtemos 583 ciclos de relógio ... mas isso já está próximo do ideal, mas ainda não é o ideal.
Em seguida, vêm as pequenas configurações para um MK específico - trabalhar com variáveis globais é mais rápido. do que com os locais, mas ainda mais rápido com os locais registrados, o que leva a uma redução no tempo para 506 ciclos de relógio.
Além disso, observamos que a última multiplicação antes do turno pode ser realizada com números de 16 bits, o que dará 504 - um pouco, mas é legal.
No total, aceleramos os cálculos em comparação com a implementação da “testa” em 1900/504 - mais de três vezes e não perdemos exatamente a palavra. Esse é o resultado que chamo de otimização de tempo, e não 20% recebido no post original.
É possível alcançar indicadores ainda melhores - é possível, mas este é o tópico do próximo post.