collapse

* Posts Recentes

OpAmp Rail2Rail, 30V ... e mais umas coisinhas por Njay
[Ontem às 17:31]


Por que nunca se deve confiar no que diz o cliente por dropes
[03 de Dezembro de 2021, 14:17]


Loja a EVITAR por dropes
[27 de Novembro de 2021, 19:35]


Projecto LED fundem por pouco funcionamento? por filjoa
[24 de Novembro de 2021, 10:45]


Um recurso muito completo com implementações de algoritmos. por blabla
[23 de Novembro de 2021, 12:04]


Como resolver "uhmmm" 50Hz Colunas de PC por dropes
[22 de Novembro de 2021, 14:12]


Software TV sala espera + Publicidades por m90mine
[19 de Novembro de 2021, 14:32]


Stenography - Using programming to save ancient writing method por blabla
[18 de Novembro de 2021, 13:55]


Identificador Via Verde por almamater
[15 de Novembro de 2021, 16:20]


Meu novo robô por josecarlos
[13 de Novembro de 2021, 12:12]

Autor Tópico: How to put 1 ref and 2 booleans inside a reference address?  (Lida 455 vezes)

0 Membros e 1 Visitante estão a ver este tópico.

Offline blabla

  • Mini Robot
  • *
  • Mensagens: 80
How to put 1 ref and 2 booleans inside a reference address?
« em: 04 de Novembro de 2021, 12:08 »
Bom dia a todos,

Este hack pode ser usado em qualquer linguagem de programação que permita mexer nos endereços de memória (referências), por exemplo C, C++, Rust, D entre outras.

Hoje bem cedo estava a ler um excelente livro de Rust pela segunda vez quando me deparei com um exemplo que é um hack muito engraçado, e que pode ser útil em algumas circunstâncias.
Este hack está documentado na página 642 do fantástico livro:

Programming Rust: Fast, Safe Systems Development 2nd Edition
by Jim Blandy, Jason Orendorff, Leonora F. S. Tindall

Eu recomendo a todos este livro! É mesmo um excelente livro!

No livro ensinam a técnica de como colocar uma referência e uma flag booleana, dentro de um único endereço de memória, isto para referencias para tipos de dados de mais de 2 bytes que sejam por natureza alinhados a pelo menos 2 bytes.

Eu explico a técnica com detalhes no meu projeto de github, derivado e estendido do exemplo do livro.
No meu exemplo estendido, eu coloco 1 referência e 2 flags booleanas no espaço de uma referência.

Isto é muito usado sempre que se pretende poupar memória, por exemplo no caso da implementação de um Garbage Collector.

How to put 1 ref and 2 booleans inside a reference address?
https://github.com/joaocarvalhoopen/How_to_put_1_ref_and_2_booleans_inside_a_reference_address

Obrigado,

Cumprimentos,
João

Offline KammutierSpule

  • Mini Robot
  • *
  • Mensagens: 1.453
Re: How to put 1 ref and 2 booleans inside a reference address?
« Responder #1 em: 04 de Novembro de 2021, 14:40 »
O próximo desafio: colocar flags em variáveis float  8)

Offline blabla

  • Mini Robot
  • *
  • Mensagens: 80
Re: How to put 1 ref and 2 booleans inside a reference address?
« Responder #2 em: 04 de Novembro de 2021, 15:37 »
@ KammutierSpule:
É também um desafio interessante e se calhar ainda mais útil do que o das referencias para a maior parte dos casos, nomeadamente os sistemas embarcados / embebidos.

Como pode ser visto aqui que:

Wikipedia – IEEE-754 - Single-precision floating-point format
https://en.wikipedia.org/wiki/Single-precision_floating-point_format

Os 32 bits de um FP32 são divididos em:
bit 31Sign 1 bit
bit [30 a 23]Expoente 8 bits.
bit [22 a 0]Fraction 23 bits.

O valor é calculado da seguinte forma:

Value = (-1)^b31 x 2^( [b30 b29 ...b23] - 127) x (1.b22 b21 … b0)


A forma mais simples de atacar este problema com por exemplo por um float com uma flag no espaço de um float 32 bits, seria de usar 1 bit da precisão ou seja de passar de 23 bits de parte fracionaria para 22 bits de parte fracionaria (nesse caso usaria-se o b0). Esta seria a forma mais simples, as desvantagens desta forma é que se perde um pouco de precisão.


Mas ainda existe uma outra forma, por exemplo, em muitos cálculos com fp32 não são necessários valores com  expoente muito grandes, nem muito pequenos, por exemplo fazer um número fp32 com expoente entre -127 e +127, certo? Apesar de esse valor ser E – 127, podemos ter uma representação interna que não usa o bit mais elevado do expoente b30 e assim só conseguiria representar valores de expoente entre -2^6 bits até 2^6 bits logo valores entre [-2^64, 2^64], o que para a maior parte dos casos é mais do que suficiente e assim ganhava-se 1 bit, logo uma flag boleana e não se perdia precisão, só se perdia range!

Na pratica para fazer isto, não se precisava de usar pointers ou referencias e bastava definir-se um novo tipo de dados que fosse internamente um float 32 depois tinha-se um método que devolvia o valor fp32 normal com o range de interesse shiftado (valor somado ao original nos bit's de expoente) (não se esqueçam que não se pode tirar só o bit pois ele não é centrado em zero) e no range correto para os cálculos e ele internamente usa o bit que tinha ganho para colocar a flag.

Ex. de utilização:

let fps1 = FP32WithFlag(10.0, true);
let fps2 = FP32WithFlag(2.0, false);
let fp3 = fps1.val() * fps2.val();
fps1.set(fp3);
let flag: bool = fps1.get_flag();
if flag { println!( “{}”, fps1.val() );

// Cria-se um array de 100 fp32 modificados.
let mut vec_tmp = [FP32WithFlag(7.0, false); 100];

// Marca os números que se pretende usar no calculo.
for i in 0..vec_tmp.len() {
    if i % 2 == 0 { vec_tmp.set_flag(true); }
}

// Condicionalmente executa-se o calculo para cada elemento.
let mut accu: fp32 = 0.0;
for elm in vec_tmp {
    if elem.get_flag() {
       accu += elm.val();
   }
}
println!(“{}”, accu);

Assim não se perde nenhuma funcionalidade e ganha-se espaço, e só tem um pequeno peso em termos de performance.

Cumprimentos,
João
« Última modificação: 04 de Novembro de 2021, 15:49 por blabla »

Offline blabla

  • Mini Robot
  • *
  • Mensagens: 80
Re: How to put 1 ref and 2 booleans inside a reference address?
« Responder #3 em: 04 de Novembro de 2021, 16:58 »
Na realidade e depois de pensar um pouco mais no problema a técnica da diminuição dos bit’s do expoente não poderia ser usada, pois essa técnica interferia com os valores de +-0 (Expoente = 0000 0000) e com os valores +-infinity FF (Expoente = 1111 1111), logo nunca se poderia usar o bit 30, mas poderia-se facilmente usar a primeira técnica da precisão, apesar de se perder um pouco de precisão passando de 23 bits para 22 bits na parte fracionaria. Outro motivo para não se mexer no expoente é que o expoente não é só usado para representar os range entre [2^-127, 2^+127], mas sim para representar [-2^+127, -2^-127]   0   [+2^-127, +2^+127] e logo não se pode mexer no expoente sem que os cálculos da representação fracionaria sejam alterados incorretamente.
Mas o método de alterar a precisão fracionaria já não tem esse problema.

Como os cálculos intermédios seriam todos feitos na mesma em FP32 normal e isto seria só usado para guardar os valores, a perda de precisão poderia não ser assim tão relevante e fazer sentido em muitos casos.

Cumprimentos,
João

Offline jm_araujo

  • Mini Robot
  • *
  • Mensagens: 2.792
  • NERD!
Re: How to put 1 ref and 2 booleans inside a reference address?
« Responder #4 em: 04 de Novembro de 2021, 23:51 »
Parece-me uma solução à procura de um problema.
Também já perdi tempo a esmifrar o último bit de memória, mas fica um código ilegível se não for muito bem documentado, e portabilidade  (que tão importante é nos dias de hoje)  vai à vida, fica-se dependente da arquitetura (se alinhada a 1, 2 ou 4 bits).

Offline blabla

  • Mini Robot
  • *
  • Mensagens: 80
Re: How to put 1 ref and 2 booleans inside a reference address?
« Responder #5 em: 05 de Novembro de 2021, 08:09 »
@ jm_araujo
Bom dia,

1º Hack REFWith2Flags
Tem toda a razão que esta primeira técnica é um hack e que depende do alinhamento do tipo de dados a 1 byte, a 2 bytes, a 4 bytes ou a 8 bytes. E que esses alinhamentos são dependentes do compilador, ou das opções do compilador, que variam com a arquitetura ex: x86_64, ARM ou RISC-V e que até podem variar dentro do mesmo compilador default para sistemas operativos diferentes no mesmo hardware. Mas dito isto, todos os compiladores em todas as linguagens tem uma instrução para testar o alinhamento de um determinado tipo de dados e esse alinhamento é fixo dentro de uma compilação de uma linguagem. Este código que eu coloquei e derivado do exemplo do livro faz precisamente um teste ao alinhamento e neste caso faz um assert,   assert!(align_of::<T>() % 4 == 0);   por isso termina imediatamente o código com uma mensagem de erro que indica se o programa está a usar algum tipo de dados como parâmetro genérico T que não tenha o alinhamento correto. Logo não é possível ser usado por um tipo de dados com alinhamento incorreto. Contudo para um interface mais ergonômico e para não gerar o Panic (a paragem do código gerada pelo assert) a condição do assert poderia ser colocada num if e devolvido em Rust um Option<T> com None em vez do valor para o objeto e assim testar em run-time no momento da criação do objeto, se pode criar o objeto. Numa outra linguagem como o C ou o C++ poderia-se devolve um NULL como retorno que teria de ser obrigatoriamente testado quando se criava uma referência, tal como se faz para o malloc(). Numa linguagem como Rust esta referencia seria altamente tipificada para o tipo de dados RefWith2Flags e como tal não poderia ser mal usada como uma referencia normal sem que se fizesse nome_da_variavel.get_ref() e logo o compilador assegurava que a interface correta teria de ser usada, depois de obter a referencia com o get_ref(), ela passa a ser uma referencia normal e o seu uso é perfeitamente normal, mas quando é guardado em memoria no RefWith2Flags ele efetivamente consegue fazer o “passo de magica” de colocar mais dados no mesmo espaço, e sim apesar de ser um hack, é um hack muito giro.

2º Hack float 32 com 1 flag
Tal como disse numa mensagem anterior nesta thread, acho que este 2º hack poderá ter muito mais aplicação no dia a dia do que o 1º Hack, pois aplica-se em muitos mais casos. A degradação da precisão é muito pequena, a poupança de memoria é bastante (Se pensarmos que normalmente teria-mos de ter um array ao lado com boolean’s mapeados para um byte, caso não se usa-se um tipo de dados com um bitfield), se pensarmos em caches e no seu tamanho limitado então ainda é mais relevante. E também que os tipos de dados de FP que existem acelerados por hardware no CPU são só fp32, fp64, sendo que fp16 tem pouca precisão e pouco range e só é acelerado em alguns GPU’s recentes como modelos mais novos do que a série RTX2000 da Nvidia ou os mais recentes da AMD Radeon e não nos CPU’s. E para muitos casos o que se perde de precisão de um step de fp32 não é mesmo muito relevante, isto tendo em conta que os cálculos intermédios continuariam a ser feitos em FP32 normal e que só seriam guardados neste FP32Modificado. Volto a dizer, totalmente tipificado para que o tipo de dados não permitisse um mau uso e que se assegura-se do uso correto da interface do tipo de dados em todas as ocorrências do código. O exemplo que eu dei de operações de fp32 bits com mascaras é um bom exemplo disso, em que cada float sabe se tem de participar num calculo ou não.

Seja como for como é óbvio e no final do dia são simplesmente mais uma ou duas técnicas que ficam na nossa “caixa de ferramentas” para que possam um dia ser usadas quando a necessidade aparecer e não ferramentas de uso do quotidiano de um programador.

Contudo, achei especial piada a estas duas, achei-as engraçadas e merecedoras de serem divulgadas.

Cumprimentos,
João

Offline jm_araujo

  • Mini Robot
  • *
  • Mensagens: 2.792
  • NERD!
Re: How to put 1 ref and 2 booleans inside a reference address?
« Responder #6 em: 05 de Novembro de 2021, 09:05 »
Corrige-me se estiver errado: uma das "vantagens" do rust enumerada pelos seus paladinos  era não precisar de apontadores, e assim evitar os "malvados" segfaults e memory leaks do "terrível" C/C++? Our era só os malloc()/new()/free(), e ponteiros não mexe?


A técnica é uma ideia boa. Mas não é novidade para quem começou bare metal em 16c84, z80, 80C51 e mesmo 8086, era até ao tutano.
Suponho também que os compiladores modernos agrupem os bools espalhados num só registo 32/64/128 bits de forma automática, pelo o que se acaba a poupar não sei se compensa a complexidade extra.

O meu espírito de engenheiro sempre me levou a tentar otimizar ao máximo, mas fui forçado a perceber que os paradigmas mudam, e a produtividade e qualidade do trabalho aumenta se trocarmos essa otimização por uma menor complexidade, mesmo que custe mais uns kb ou ms. O resultado final nunca vai ser tão bonito (diria mesmo que artístico), mas no fim do dia o que importa é se está pronto e a funcionar, e se quem vier a seguir é capaz de lhe pegar sem  fazer tudo de novo. E quem não é engenheiro (e muitas vezes em posições superiores) é tudo que lhe importa, e secalhar com alguma razão: o recurso mais caro é a mão de obra. Um GB de RAM custa menos que 1h de trabalho, e dá para amortizar na contabilidade :D

Ps: Desculpa o rant, nenhuma animosidade para contigo ou a rua ideia!

EDIT: se gostas de otimização de código,, tens de dar uma vista de olhos à "demoscene". É alucinante o que conseguem fazer nas categorias de tamanho reduzido (64k, 4k, 256bytes)
« Última modificação: 05 de Novembro de 2021, 09:52 por jm_araujo »

Offline KammutierSpule

  • Mini Robot
  • *
  • Mensagens: 1.453
Re: How to put 1 ref and 2 booleans inside a reference address?
« Responder #7 em: 05 de Novembro de 2021, 11:21 »
Relativamente ao uso de flags em floats, a primeira vez que me lembro de ter conhecimento (e é de certo modo relacionado com demoscene / programação gráfica) foi de um exemplo usado num livro ver aqui

Naquele caso era uma implementação CPU, mas penso que possa servir / fazer sentido para GPU.

Aqui o problema não é dinheiro, mas criar a implementação computacionalmente melhor.
E neste caso, também é dinheiro, porque estamos a considerar processamentos que demoram horas.

Nestes casos existem duas limitações que se tem de jogar (trade offs): velocidade CPU vs largura de banda (velocidade/quantidade de dados que chegam ao CPU).

Quando a velocidade do CPU é muito alta, a limitação pode estar na largura de banda.

Então em certas implementações, pode-se gastar mais instruções no CPU e optimizar a largura de banda, daí empacotar flags em floats.

Nestes casos, até chegam ao ponto de optimizar o algoritmo ao tamanho (em bytes) das linhas de cache do CPU, criando estruturas que possam ser lidas em multiplos desses tamanhos (fetch & cache reuse)

Citar
It is worth going through a bit of trouble to ensure that all interior nodes and many leaf nodes use just 8 bytes of memory (assuming 4-byte Floats) because doing so ensures that eight nodes will fit into a 64-byte cache line. Because there are often many nodes in the tree and because many nodes are generally accessed for each ray, minimizing the size of the node representation substantially improves cache performance. Our initial implementation used a 16-byte node representation; when we reduced the size to 8 bytes we obtained nearly a 20% speed increase.
« Última modificação: 05 de Novembro de 2021, 11:25 por KammutierSpule »

Offline blabla

  • Mini Robot
  • *
  • Mensagens: 80
Re: How to put 1 ref and 2 booleans inside a reference address?
« Responder #8 em: 05 de Novembro de 2021, 13:19 »
Bom dia,

@ jm_araujo
Obrigado pelo comentário.
O Rust tem referencias e pointers por todo o lado! Heheheheh Só que eles são em dois modos, ou é Rust normal, em que tens a restrições do Borrow Checker e em que uma zona de memória (tipos em memoria) têm um owner específico e esse ownership pode ser atribuído a outra variável, ou então tens variáveis que tem referencias de não mutáveis (const do C) e pode ter N referências ao mesmo tempo, ou então tens uma e só uma referencia mutável (não const do C). Ao contrário de C ou C++ o compilador de Rust faz o check destas regras todas e assegura que não à segmentation fault, ou des-referenciação de NULL pointers. Depois tem uma coisa engraçada que é as life-times, pois apesar de em muitos casos o compilador conseguir determinar o tempo de vida de uma referencia em relação ao tempo de vida do “objeto” no stack ou no heap para o qual ela aponta, em algumas circunstâncias ele não consegue determinar e por isso tem de se anotar as life-times de entrada e saida de parâmetros ou tipo de retorno de uma função ou estrutura.
Depois existe o wild west, que são as funções e os blocos Rust Unsafe e aí tudo vale, é como se tivesse o C ou o C++ para escrever tudo o que se pode imaginar e aí pode dar Segmentation fault Core Dump :-) . Mas a esmagadora maioria das coisas não necessita de código Rust Unsafe e quando necessita são zonas muito pequenas que estão bem delimitadas e por isso é como se fosse o foco de uma lanterna a apontar para aquele sitio e é ali que se tem o erro!

Em relação à “demoscene” concordo plenamente consigo, muitos tipos com conhecimento técnico muito  conseguem fazer literalmente magia num executável inacreditavelmente pequeno e com uma performance incrível.

@ KammutierSpule
Muito obrigado pelo link do livro e pela exposição do caso de uso, estava só a pensar no espaço ocupado e nos seus espaço dentro da hierarquia das caches para permitir maior performance, mas a menor largura de banda necessária na transferência de grandes volumes de dados, faz todo o sentido. Tal como diz, quer no BUS CPU para a memória, quer no caminho memoria -> DMA -> PCI-E -> GPU. E também na largura de banda memoria do GPU, GDDR, para GPU nos dois sentidos.   
     
@ Estado atual
Eu neste momento já tenho a implementação de FP32WithFlag e testada com unit tests, dediquei a manhã a fazer esse código, usei um bit de precisão de menor peso da parte fracionária.
Escrevi testes para os casos de -0.0, +0.0, -inf, +inf e NAN.
Ele está a passar todos os testes, mas internamente, não posso suportar os NAN pois existem muitos NAN cada um para os seus casos diferentes e não sei, nem encontro quais, são todos eles em Rust.
Logo tive de colocar um assert na criação do número se for um NAN e retorno um erro runt-time quando se faz o set_val() de um NAN. Neste momento é o melhor que eu estou a ver que consigo fazer neste caso, pois não sei quais são os padrões dos bit’s de todos os NAN.
Em Rust NAN não podem ser comparados como iguais, pois de facto são muitos, mas podem ser testados se um f32::is_nan() e é isso que eu estou a usar. 
Agora falta-me escrever um README.md para explicar um pouco do funcionamento do  FP32WithFlag e depois já o publico no meu GitHub  :-)  .

Cumprimentos,
João

Offline blabla

  • Mini Robot
  • *
  • Mensagens: 80
Re: How to put 1 ref and 2 booleans inside a reference address?
« Responder #9 em: 05 de Novembro de 2021, 15:03 »
Boa tarde,

eu coloquei esta minha implementação FP32WithFlag no meu github no link seguinte:

FP32WithFlag - How to put 1 float32 and 1 flag inside a float32?
https://github.com/joaocarvalhoopen/FP32WithFlag__1_float32_and_1_flag_in_a_float32

Esta implementação tem unit tests e uma descrição pormenorizada de como ela funciona, ela funciona em CPU’s little endian (como por exemplo x86_64) e em CPU’s big endian, na representação interna eu uso little endian para que seja otimizado para x86_64.

A licença é MIT Open Source.

Cumprimentos,
João