Folha de dicas da abreviação de C ++ e muito mais. Parte 2: "e não apenas"

Esta é a segunda e a última parte da minha planilha de abreviaturas que um desenvolvedor de C ++ deve conhecer. O C ++ é mencionado aqui apenas porque eu criei a folha de dicas principalmente para mim e sou apenas o mesmo desenvolvedor do C ++.

De fato, esta parte contém conceitos cujo escopo não se limita ao C ++. Portanto, a seleção pode ser de interesse para um público mais amplo.



Como na primeira parte , as abreviações são agrupadas, se isso faz sentido. Se não fizer sentido, eles serão listados em ordem alfabética.

Concorrência e operações atômicas:
• CAS
• ABA
FAA
• RCU

Armazenamento de dados:
• ÁCIDO
• CAP
• PACELC
• BASE

Princípios de desenvolvimento de software:
• SECO
• BEIJO
• YAGNI
NIH
• FTSE
• GRASP
• SÓLIDO

Outro:
• ABI
• VACA
• FBC, FBCP
• LRU

Concorrência e operações atômicas

Cas

Compare E Troque. Comparação com a troca. Esta é uma instrução atômica com três argumentos: variável atômica ou endereço de memória, valor esperado, novo valor. Se e somente se o valor da variável corresponder ao valor esperado, a variável receberá um novo valor e a instrução será concluída com êxito. O CAS simplesmente retorna um valor booleano (e pode ser chamado Compare And Set) ou, se falhar, também retorna o valor atual do primeiro argumento.


No C ++, o CAS é representado pelas famílias dos métodos std::atomic<T>::compare_exchange_weak , std::atomic<T>::compare_exchange_strong e as funções livres std::atomic_compare_exchange_weak , std::atomic_compare_exchange_strong . A diferença entre * fraco e * forte é que o primeiro pode produzir resultados falsos negativos. I.e. se o valor for esperado, eles retornarão false e não o substituirão por um novo. A razão para a existência de * operações fracas é que em algumas arquiteturas * fortes são relativamente caras. Na maioria dos casos, as instruções CAS giram em um loop (o chamado loop CAS); portanto, usar * fraco em vez de * forte não muda a lógica, mas pode melhorar o desempenho.

As instruções CAS são usadas para implementar primitivas de sincronização (como mutexes e semáforos) e algoritmos sem bloqueio. Muitas vezes levam a um problema ABA .

Leia mais: uma vez (russo) , dois (inglês)

ABA

Problema ABA. Problema ABA. Esse problema surge em algoritmos paralelos com base em comparações com trocas (consulte o CAS ), por exemplo, em algoritmos sem bloqueio. A conclusão é que o thread lê o valor da variável atômica, faz outra coisa e atualiza essa variável por comparação com a troca. I.e. a lógica do fluxo é a seguinte: se a variável ainda contém o valor anterior, nada mudou, tudo está em ordem. Mas isso pode não ser verdade. Uma descrição mais formal do problema:

• o thread 1 lê o valor da variável, é igual a A
• o segmento 1 está sendo forçado a sair, o segmento 2 está iniciando
• o encadeamento 2 altera o valor da variável de A para B, faz várias alterações (altera algum valor associado à variável ou apenas libera memória) e depois altera novamente o valor - de B para A
• o thread 1 retoma a operação, compara o valor obtido anteriormente com o atual e conclui que nada mudou

Possíveis soluções para o problema:

1. O mais simples e mais óbvio é usar bloqueios. Isso resultará no algoritmo usual de segurança de thread com seções críticas. Mas deixará de estar livre de bloqueios. Mas se se tratasse de CAS e ABA , provavelmente não é uma opção.
2. Adicione rótulos especiais aos valores comparados. Por exemplo, um contador do número de alterações. Por um lado, esse contador pode estourar, mas, por outro lado, os modernos processadores x86_64 suportam operações CAS de 128 bits. I.e. ao comparar ponteiros com um contador, você pode fornecer até 64 bits e alguém achou que isso é suficiente para 10 anos de operação contínua do algoritmo.
3. Algumas arquiteturas (ARM, por exemplo) fornecem instruções LL / SC (carga vinculada, armazenamento condicional) que não apenas permitem obter o valor atual do endereço na memória, mas também entender se esse valor foi alterado desde a última leitura.

Para usar estruturas de dados como uma pilha, lista ou fila, livres de bloqueios, em geral, onde existe o risco de ficar com um ponteiro pendurado em um nó remoto, há toda uma família de soluções para o problema ABA com base na remoção adiada de nós. Isso inclui o coletor de lixo, os indicadores de perigo e o mecanismo de leitura-modificação-gravação (consulte RCU ).

Leia mais: um (russo) , dois (inglês) , três (inglês)

FAA

Buscar e adicionar. Ah ... obtenha e adicione (parece que esse conceito nunca é traduzido para o russo). Uma operação atômica com dois argumentos: uma variável atômica ou um endereço na memória e o valor pelo qual essa variável deve ser alterada. Se a arquitetura permitir, a operação retornará o valor anterior da variável alterada (x86 permite desde i486). Ao contrário do CAS , a FAA sempre é bem-sucedida.


No C ++, ele é implementado como as famílias dos métodos std::atomic<T>::fetch_add , fetch_sub , fetch_and , fetch_or , fetch_xor e as funções livres correspondentes std::atomic_fetch_add , etc.

Como convém a uma instrução atômica, o FAA é usado em implementações de primitivas de sincronização e algoritmos sem bloqueio e estruturas de dados.

Leia mais: uma vez (russo) , dois (inglês)

RCU

Leitura-cópia-atualização. Leitura-modificação-gravação. Este é um mecanismo sem bloqueio para sincronizar o acesso à estrutura de dados (sem bloqueios, é claro). É usado nos casos em que a velocidade de leitura é crítica. É um exemplo da troca de tempo e memória (troca espaço-tempo).

A idéia do RCU é que o fluxo do gravador não altere os dados no local, mas crie uma cópia, faça as alterações necessárias e troque atomicamente os dados atuais e a cópia alterada. Ao mesmo tempo, os threads do leitor constantemente têm acesso a dados - antigos ou novos, quem quer que tenha tempo. Quando não há leitores trabalhando com a versão desatualizada, o gravador exclui os dados que não são mais necessários, liberando memória.

O RCU muito simplificado funciona assim:

• Muitos leitores, um escritor.
• Leitura e mudança ocorrem simultaneamente.
• Os leitores usam sincronização muito leve. De fato, o leitor só precisa notificar o escritor no momento de entrar na seção crítica e no momento de sair dela. O trabalho com dados sincronizados ocorre apenas na seção crítica.
• O escritor, assim que substitui atentamente os dados por uma cópia, anuncia o início do chamado período de carência (período de carência). O período de carência termina quando todos os leitores que estavam em seções críticas no início deste período deixaram suas seções críticas. Agora, o gravador pode excluir com segurança dados obsoletos. Está implícito que todas as seções críticas são finitas, o que garante a finitude do período de carência.

O RCU é ótimo para dados que são frequentemente lidos e raramente atualizados. Esse mecanismo é usado ativamente no kernel do Linux, onde é bastante simples determinar quando o período de carência termina.

Desvantagens:

• Fraco para sincronizar o acesso a dados modificados com frequência.
• Difícil de implementar no espaço do usuário.
• Depende da capacidade de alterar atomicamente os ponteiros para um endereço na memória, mas nem todas as arquiteturas fornecem esse recurso.

Leia mais: uma vez (russo) , dois (inglês)

Armazenamento de dados

ÁCIDO

Atomicidade, Consistência, Isolamento, Durabilidade. Atomicidade, consistência, isolamento, durabilidade. Este é um conjunto de requisitos de transação em um DBMS. O ACID fornece operação DBMS confiável e previsível, mesmo em caso de erros.

• A atomicidade assegura que a transação seja concluída completamente ou não faça nada. Um estado intermediário é impossível, não será tal que uma operação de transação tenha sido bem-sucedida e a outra não. Tudo ou nada.
• A consistência garante que todos os dados no banco de dados atendam a todas as regras e restrições especificadas antes do início da transação e após sua conclusão. Durante a execução da transação, a consistência pode ser violada.
• O isolamento garante que transações simultâneas não afetem uma à outra. Nenhuma transação tem acesso a dados inconsistentes processados ​​por outra transação.
• Durabilidade significa que o resultado de uma transação bem-sucedida é armazenado no banco de dados e não pode ser perdido, não importa o que aconteça com o banco de dados imediatamente após a conclusão da transação.

Todos os principais DBMSs relacionais suportam totalmente o ACID . No mundo NoSQL, esse suporte completo provavelmente é uma exceção.

Leia mais: uma vez (inglês) , duas (inglês)

Cap

Teorema da PAC. Teorema da PAC. O teorema afirma que qualquer sistema distribuído pode ter mais de duas propriedades da lista: consistência dos dados ( consistência ), disponibilidade ( disponibilidade ), resistência à separação ( tolerância de partição ).

• Consistência neste caso significa consistência (simplificada) consistente. I.e. assim que a operação de atualização de dados em um nó for concluída com êxito, todos os outros nós já terão esses dados atualizados. Assim, todos os nós estão em um estado consistente. Essa não é a consistência exigida pelo ACID .
• Disponibilidade significa que cada nó com falha retorna uma resposta correta para cada solicitação (tanto para leitura quanto para gravação) em um período de tempo razoável. Não há garantia de que as respostas de diferentes nós correspondam.
• Resistência à separação significa que o sistema continuará funcionando corretamente em caso de perda de um número arbitrário de mensagens entre seus nós.

Porque todas as três propriedades são inatingíveis; do ponto de vista do teorema da PAC , todos os sistemas distribuídos se enquadram em três classes: CA , CP e AP . Os sistemas CA obviamente não têm resistência à separação. Porque na grande maioria dos casos, a distribuição implica a distribuição em uma rede real e, em uma rede real, sempre há uma probabilidade diferente de zero de perder um pacote, e os sistemas CA são de pouco interesse.

A escolha é entre CP e AP , ou seja, entre consistência e disponibilidade. DBMSs relacionais tradicionais que seguem os princípios do ACID preferem consistência. Enquanto muitas soluções NoSQL escolhem acessibilidade e BASE .

No caso de operação normal da rede, ou seja, quando não há separação de rede, o teorema da CAP não impõe restrições à consistência e disponibilidade. I.e. doar algo não é necessário.

Leia mais: um (russo) , dois (inglês) , três (inglês)

Pacelc

Teorema do PACELC. Teorema do PACELC. Essa é uma extensão do teorema do CAP , que afirma que um sistema distribuído no caso de uma partição de rede ( Partição ) é forçado a escolher entre Disponibilidade ( Consistência ) e, no caso de operação normal de rede ( Else ), é necessário escolher entre latência ( Consistência) )

Portanto, se o teorema do CAP distinguir duas classes de sistemas estáveis ​​com a separação de rede, o PACELC possui quatro deles: PA / EL , PA / EC , PC / EL e PC / EC . Alguns bancos de dados NoSQL podem mudar de classe, dependendo das configurações.

Leia mais: uma vez (russo) , dois (inglês)

BASE

Basicamente disponível, estado suave, consistência eventual. Disponibilidade básica, estado frágil, consistência a longo prazo. De acordo com o teorema da PAC em sistemas distribuídos, algo terá que ser abandonado. A coerência estrita é geralmente abandonada em favor da coerência a longo prazo. O que significa que, na ausência de alterações de dados, o sistema algum dia chegará a um estado consistente.

Para indicar tal compromisso, a abreviatura BASE começou a ser usada com certa rigidez e resultou em um jogo de termos químicos ( ACID - acidez, BASE - basicidade).

• Basicamente disponível significa que o sistema garante a disponibilidade dos dados, responde a cada solicitação. Mas a resposta pode ser dados desatualizados ou inconsistentes (ou a falta deles)
• Estado suave significa que o estado do sistema pode mudar com o tempo, mesmo na ausência de solicitações de alterações de dados. Porque a qualquer momento, os dados podem ser trazidos para um estado consistente.
• A consistência eventual significa que, se os dados pararem de mudar, eles obviamente terminarão em um estado consistente. I.e. a mesma solicitação para nós diferentes levará às mesmas respostas.

Leia mais: uma vez (inglês) , duas (inglês)

Princípios de desenvolvimento de software

SECO

Não se repita. Não repita. Esse é o princípio do desenvolvimento de software, cuja principal idéia é reduzir a quantidade de informações duplicadas no sistema, e o objetivo é reduzir a complexidade do sistema e aumentar sua capacidade de gerenciamento.

No original ( O livro do programador pragmático , de Andrew Hunt e David Thomas ), esse princípio é formulado da seguinte maneira: "Cada conhecimento deve ter uma representação única, consistente e autorizada dentro do sistema". Nesse caso, entende-se por conhecimento qualquer parte de uma área ou algoritmo de assunto: um código, um esquema de banco de dados, um determinado protocolo de interação etc. Assim, para fazer uma alteração no sistema, apenas um "conhecimento" precisa ser atualizado em um só lugar.

Um exemplo idiota: o cliente e o servidor transmitem dados estruturados um para o outro. Porque Como são aplicativos diferentes executados em máquinas diferentes, os dois devem ter suas próprias implementações dessas estruturas. Se algo mudar, as alterações terão que ser feitas em dois lugares. Um passo óbvio para evitar essa repetição é alocar o código comum em uma biblioteca separada. O próximo passo é gerá-lo de acordo com a descrição das estruturas (Google Protocol Buffers, por exemplo), para não escrever o mesmo tipo de código para acessar os campos das estruturas.

A duplicação de código é apenas um caso especial de violação de DRY . E esse nem sempre é o caso. Se dois pedaços de código parecerem iguais, mas cada um implementar sua própria lógica de negócios, o DRY não será quebrado.

Como qualquer outro princípio, o DRY é uma ferramenta, não um dogma. Quanto maior o sistema, mais fácil é violar esse princípio. Primeiro, o ideal é inatingível. E segundo, se seguir cegamente o DRY levar a um código mais complicado e dificultar a compreensão, é melhor abandoná-lo.

Leia mais: um (russo) , dois (russo)

KISS

Mantenha-o simples, estúpido. Torne mais fácil (estúpido, neste caso, não é uma ligação). Esse é o princípio de design de que a maioria dos sistemas funciona melhor se permanecer simples. O princípio se originou na indústria aeronáutica e é aplicado muito onde, inclusive no desenvolvimento de software.

Neste último caso, o KISS é útil para projetar e escrever diretamente o código. Arquitetura e código simples não são apenas mais fáceis de entender, mas também mais fáceis de usar, manter e desenvolver. O MapReduce não deve ser enganado se um par produtor-consumidor for suficiente. A mágica da metaprogramação é excessivamente complexa se você puder executar algumas funções comuns e atingir o nível de desempenho necessário.

Com tudo isso, não se deve esquecer que a simplicidade não é uma meta, mas apenas um requisito não-funcional. O principal é atingir a meta de design / implementação, e é aconselhável fazer isso da maneira mais simples possível.

Leia mais: um (russo) , dois (russo) , três (inglês)

YAGNI

Você não vai precisar disso. Você não precisa disso. Esse é o princípio do desenvolvimento de software, cuja idéia principal é a rejeição de funcionalidade excessiva e o objetivo é economizar recursos gastos no desenvolvimento.

YAGNI diz que você não precisa projetar ou implementar funções que não são necessárias no momento. Mesmo se você tiver certeza de que eles serão necessários no futuro. Não há necessidade de adicionar abstrações desnecessárias, cujos benefícios aparecerão algum tempo depois.

O problema é que as pessoas não prevêem bem o futuro. Portanto, provavelmente tudo o que é feito "em reserva" simplesmente não será útil. E acontece que o tempo e o dinheiro gastos em tais desenvolvimentos, testes e documentação são desperdiçados. Além disso, o software se tornou mais complicado; recursos adicionais devem ser gastos no suporte novamente. Pior ainda, quando era necessário fazer diferente. Dinheiro e tempo serão gastos também na correção.

O princípio YAGNI é um pouco mais radical que o DRY e o KISS . Se eles dividem o sistema em partes compreensíveis e tomam decisões simples, a YAGNI simplesmente elimina peças e soluções desnecessárias.

Leia mais: um (russo) , dois (inglês) , três (inglês)

Nih

Não inventado aqui. Não inventado aqui. Esta é uma síndrome de rejeição do desenvolvimento de outras pessoas, uma posição que praticamente beira a invenção de uma bicicleta. Freqüentemente, a síndrome é acompanhada pela crença de que a criação de tecnologia dentro da empresa será mais rápida e barata, e a própria tecnologia atenderá melhor às necessidades da empresa. No entanto, na maioria dos casos, esse não é o caso, e o NIH é um anti-padrão.

Aqui estão alguns casos que justificam o NIH :

• A qualidade da solução de terceiros não é alta o suficiente ou o preço não é baixo o suficiente.
• Uma solução de terceiros tem restrições de licenciamento.
• O uso de uma solução de terceiros cria dependência de seu fornecedor e, portanto, ameaça os negócios.

Leia mais: um (russo) , dois (inglês) , três (inglês)

Ftse

Teorema Fundamental da Engenharia de Software. Teorema fundamental do desenvolvimento de software. Na verdade, este não é um teorema, não tem prova. Este é um ditado famoso de Andrew Koenig:

Qualquer problema pode ser resolvido adicionando outra camada de abstração.

Às vezes, eles adicionam a esta frase "... exceto pelo problema de muitas camadas de abstração". Em geral, o “teorema” não é uma coisa séria, mas vale a pena conhecer.

Leia mais: uma vez (inglês) , duas (inglês)

GRASP

Padrões de software de atribuição de responsabilidade geral. Modelos de alocação de responsabilidade geral. Esses nove padrões são formulados em Applying UML and Patterns por Craig Larman . Cada modelo é uma solução típica para um problema de design de software (mas bastante geral).

1. Especialista em informação . Problema: qual é o princípio geral da distribuição de responsabilidades entre objetos? Decisão: atribua um dever a alguém que possua as informações necessárias para cumprir essa obrigação.
2. Criador Problema: quem deve ser responsável pela criação de um novo objeto? Solução: a classe B deve criar instâncias da classe A se uma ou mais das seguintes condições for verdadeira:
   - classe B agrega ou contém instâncias de A
   - B escreve A
   - B usa ativamente A
   - B possui dados de inicialização A
3. Baixo acoplamento Problema: como reduzir o impacto da mudança? Como aumentar a possibilidade de reutilização? Solução: distribua responsabilidades para que a conectividade seja baixa. O acoplamento é uma medida de quão rigidamente os elementos estão conectados, o quanto eles dependem um do outro. I.e. Recomenda-se conectar objetos para que eles conheçam um ao outro apenas o mínimo necessário.
4. Alta engrenagem ( alta coesão ). Problema: Como gerencio a complexidade? Solução: distribua responsabilidades para que o alto envolvimento seja mantido. Alto engajamento significa que as responsabilidades de um elemento estão focadas em uma área.
5. Controlador Problema: quem deve ser responsável por lidar com eventos de entrada? Solução: atribua uma classe a ser responsável, que representa todo o sistema ou subsistema como um todo (controlador externo) ou um script específico (controlador de script ou sessão). Ao mesmo tempo, o controlador não implementa uma reação a eventos, delegando isso aos executores relevantes.
6. Polimorfismo ( Polimorfismo ). Problema: como lidar com comportamentos diferentes com base no tipo? : , , , .
7. ( Pure Fabrication ). : , ? : , .
8. ( Indirection ). : , Low Coupling ? : .
9. ( Protected Variations ). : , ? : , .

GRASP SOLID . , . . — .

: (.) , (.) , (.)

SOLID

SOLID. - ( ). (Robert Martin) 2000-. — , , .

1. ( Single Responsibility Principle, SRP ). . « , ».
2. / ( Open Closed Principle, OCP ). (, , ) , . : , .
3. ( Liskov Substitution Principle, LSP ). , . I.e. - .
4. ( Interface Segregation Principle, ISP ). , . , . , , . , .
5. ( Dependency Inversion Principle, DIP ). . . . . , , , , ( Java C#).

: (.) , (.) , (.)

Outros

ABI

Application Binary Interface. . , ( , , ). ABI – , (, ).

ABI ELF Linux PE Windows. , (, , etc.) . , ELF PE , .

ABI , , , , , . . . .

C++ ABI , , . . . , C++ Unix- (Linux, FreeBSD, MacOS) x86_64 System V AMD64 ABI , ARM – ARM C++ ABI . Visual C++ ABI , . System V ABI, (mangling) ( Linux 6 , Windows – 4), .

API ABI , , . C++11 ( ). - GCC 5 ( COW ), .

: (.) , (.) .

COW

Copy On Write. . , implicit sharing lazy copy. , , , . — «» — .

COW : . , , .

COW :

• Linux. fork() , .
• (snapshots) (Btrfs, ZFS) (MS SQL Server).
• ++11 std::string COW . C++11 std::string (. ABI ).
• Qt COW .

: (.) , (.)

FBC, FBCP

Fragile Base Class (Problem). . , , .


FBC , , Java ( C++ ). FBCP :

• , ( final C++ Java).
• , .
• , , .

: (.) , (.) , (.)

LRU

Least Recently Used. . ( ). «-», — (hit ratio). , . , . — , , .

LRU , . , , . , . LRU — O(n), — O(1), — O(1). - .


LRU , . . n . LRU : MRU (Most Recently Used), LFU (Least Frequently Used), Segmented LRU, 2Q . .

: (.) , (.) , (.)

PS

- - — .