A orientação a objetos realmente afeta o desempenho do algoritmo?

A orientação a objetos me ajudou muito na implementação de muitos algoritmos. No entanto, as linguagens orientadas a objetos às vezes o guiam na abordagem "direta" e duvido que essa abordagem seja sempre uma coisa boa.

OO é realmente útil para codificar algoritmos de maneira rápida e fácil. Mas esse POO poderia ser uma desvantagem para o software baseado no desempenho, ou seja, com que rapidez o programa é executado?

Por exemplo, armazenar nós de gráfico em uma estrutura de dados parece "direto" em primeiro lugar, mas se os objetos Node contiverem muitos atributos e métodos, isso pode levar a um algoritmo lento?

Em outras palavras, muitas referências entre muitos objetos diferentes ou o uso de muitos métodos de várias classes resultam em uma implementação "pesada"?

A orientação a objetos pode impedir certas otimizações algorítmicas, devido ao encapsulamento. Dois algoritmos podem funcionar particularmente bem juntos, mas se estiverem ocultos atrás das interfaces OO, a possibilidade de usar sua sinergia será perdida.

Veja as bibliotecas numéricas. Muitos deles (não apenas os escritos nos anos 60 ou 70) não são OOP. Há uma razão para isso: algoritmos numéricos funcionam melhor como um conjunto de moduleshierarquias dissociadas do que como OO com interfaces e encapsulamento.

O que determina o desempenho?

Os fundamentos: estruturas de dados, algoritmos, arquitetura de computadores, hardware. Mais sobrecarga.

Um programa de POO pode ser projetado para se alinhar exatamente com a escolha de estruturas de dados e algoritmos que são considerados ideais pela teoria de CS. Ele terá a mesma característica de desempenho do programa ideal, além de algumas despesas gerais. A sobrecarga geralmente pode ser minimizada.

No entanto, um programa que é inicialmente projetado com apenas preocupações com POO, sem se preocupar com os fundamentos, pode ser inicialmente subótimo. Às vezes, a subotimalidade é removível por refatoração; às vezes não é - exigindo uma reescrita completa.

Advertência: o desempenho importa no software comercial?

Sim, mas o tempo de colocação no mercado (TTM) é mais importante, por ordens de magnitude. O software comercial enfatiza a adaptabilidade do código a regras comerciais complexas. As medições de desempenho devem ser realizadas durante todo o ciclo de vida do desenvolvimento. (Consulte a seção: o que significa desempenho ideal? ) Somente aprimoramentos comercializáveis ​​devem ser feitos e devem ser gradualmente introduzidos em versões posteriores.

O que significa desempenho ideal?

Em geral, o problema com o desempenho do software é o seguinte: para provar que "existe uma versão mais rápida", essa versão mais rápida deve existir primeiro (ou seja, nenhuma prova além de si mesma).

Às vezes, essa versão mais rápida é vista pela primeira vez em um idioma ou paradigma diferente. Isso deve ser tomado como uma dica para a melhoria, não para julgar a inferioridade de algumas outras línguas ou paradigmas.

Por que estamos fazendo POO se isso pode atrapalhar nossa busca pelo desempenho ideal?

OOP introduz sobrecarga (no espaço e na execução), em troca de melhorar a "trabalhabilidade" e, portanto, o valor comercial do código. Isso reduz o custo de desenvolvimento e otimização adicionais. Veja @MikeNakis .

Quais partes do OOP podem incentivar um design inicialmente subótimo?

As partes do POO que (i) incentivam a simplicidade / intuitividade, (ii) usam métodos de design coloquial em vez de fundamentos, (iii) desencorajam várias implementações personalizadas do mesmo objetivo.

• BEIJO
• YAGNI
• SECO
• Design de objetos (por exemplo, com cartões CRC) sem dar a mesma opinião aos fundamentos)

A aplicação estrita de algumas diretrizes de OOP (encapsulamento, passagem de mensagens, faça uma coisa bem) resultará em código mais lento no início. As medições de desempenho ajudarão a diagnosticar esses problemas. Desde que a estrutura e o algoritmo dos dados estejam alinhados com o projeto ideal previsto pela teoria, a sobrecarga geralmente pode ser minimizada.

Quais são as atenuações comuns às despesas gerais de OOP?

Como mencionado anteriormente, usando estruturas de dados que são ideais para o design.

Alguns idiomas suportam inlining de código que pode recuperar algum desempenho em tempo de execução.

Como podemos adotar OOP sem sacrificar o desempenho?

Aprenda e aplique o POO e os fundamentos.

É verdade que a adesão estrita ao OOP pode impedir que você escreva uma versão mais rápida. Às vezes, uma versão mais rápida só pode ser escrita do zero. É por isso que ajuda a escrever várias versões de código usando diferentes algoritmos e paradigmas (OOP, genérico, funcional, matemático, espaguete) e depois usar ferramentas de otimização para fazer com que cada versão se aproxime do desempenho máximo observado.

Existem tipos de código que não serão beneficiados pelo OOP?

(Expandido da discussão entre [@quant_dev], [@ SK-logic] e [@MikeNakis])

1. Receitas numéricas, originárias da matemática.
   • As equações matemáticas e as transformações podem ser entendidas como objetos.
   • Técnicas de transformação de código muito sofisticadas são necessárias para gerar código executável eficiente. A implementação ingênua ("quadro branco") terá um desempenho péssimo.
   • No entanto, os compiladores convencionais de hoje são incapazes de fazê-lo.
   • Softwares especializados (MATLAB e Mathematica, etc) têm JIT e solucionadores simbólicos capazes de gerar código eficiente para alguns subproblemas. Esses solucionadores especializados podem ser vistos como compiladores para fins especiais (mediadores entre código legível por humanos e código executável por máquina) que se beneficiarão de um design de POO.
   • Cada subproblema requer seu próprio "compilador" e "transformações de código". Portanto, esta é uma área de pesquisa aberta muito ativa, com novos resultados aparecendo a cada ano.
   • Como a pesquisa leva muito tempo, os criadores de software precisam realizar a otimização em papel e transcrever o código otimizado em software. O código transcrito pode realmente ser ininteligível.
2. Código de nível muito baixo.
   *

Não se trata realmente de orientação a objetos, mas de contêineres. Se você usou uma lista de links duplos para armazenar pixels no seu player de vídeo, ela sofrerá.

No entanto, se você usar o contêiner correto, não há razão para um std :: vector ser mais lento que um array, e como você já possui todos os algoritmos comuns escritos para ele - por especialistas - provavelmente é mais rápido que o código do array em casa.

OOP é obviamente uma boa ideia e, como qualquer boa ideia, pode ser superutilizada. Na minha experiência, é muito usado. Baixo desempenho e baixo resultado de manutenção.

Não tem nada a ver com a sobrecarga de chamar funções virtuais e não tem muito a ver com o que o otimizador / jitter faz.

Tem tudo a ver com estruturas de dados que, apesar de terem o melhor desempenho de grande O, têm fatores constantes muito ruins. Isso é feito assumindo que, se houver algum problema de limitação de desempenho no aplicativo, ele estará em outro lugar.

Uma maneira de manifestar isso é o número de vezes por segundo em que novas são executadas, o que se supõe ter desempenho O (1), mas pode executar centenas a milhares de instruções (incluindo a exclusão correspondente ou o tempo do GC). Isso pode ser atenuado ao salvar objetos usados, mas isso torna o código menos "limpo".

Outra maneira de se manifestar é a maneira como as pessoas são encorajadas a escrever funções de propriedade, manipuladores de notificação, chamadas para funções de classe base, todos os tipos de chamadas de função subterrâneas existentes para tentar manter a consistência. Para manter a consistência, eles são de sucesso limitado, mas são extremamente bem-sucedidos em desperdiçar ciclos. Os programadores entendem o conceito de dados normalizados, mas tendem a aplicá-lo apenas ao design do banco de dados. Eles não o aplicam ao design da estrutura de dados, pelo menos em parte porque o OOP diz que eles não precisam. Tão simples quanto definir um bit modificado em um objeto pode resultar em um tsunami de atualizações percorrendo a estrutura de dados, porque nenhuma classe que vale seu código recebe uma chamada modificada e apenas a armazena .

Talvez o desempenho de um determinado aplicativo seja bom como está escrito.

Por outro lado, se houver um problema de desempenho, aqui está um exemplo de como eu o ajusto. É um processo de várias etapas. Em cada estágio, alguma atividade específica é responsável por uma grande fração de tempo e pode ser substituída por algo mais rápido. (Eu não disse "gargalo". Esse não é o tipo de coisa que os criadores de perfil são bons em encontrar.) Esse processo geralmente exige, para obter a aceleração, a substituição por atacado da estrutura de dados. Muitas vezes, essa estrutura de dados existe apenas porque é uma prática recomendada de POO.

Em teoria, isso poderia levar à lentidão, mas, mesmo assim, não seria um algoritmo lento, seria uma implementação lenta. Na prática, a orientação a objetos permitirá que você tente vários cenários hipotéticos (ou revisite o algoritmo no futuro) e, portanto, forneça aprimoramentos algorítmicos , que você nunca poderia esperar obter se tivesse escrito da maneira espaguete no primeiro lugar, porque a tarefa seria assustadora. (Você basicamente teria que reescrever a coisa toda.)

Por exemplo, ao dividir as várias tarefas e entidades em objetos limpos, você poderá facilmente entrar mais tarde e, digamos, incorporar um recurso de armazenamento em cache entre alguns objetos (transparentes para eles), o que pode gerar milhares de dobra melhoria.

Geralmente, os tipos de aprimoramentos que você pode obter usando uma linguagem de baixo nível (ou truques inteligentes com uma linguagem de alto nível) oferecem melhorias de tempo constantes (lineares), que não aparecem em termos de notação do tipo "oh-oh". Com melhorias algorítmicas, você pode conseguir melhorias não lineares. Isso não tem preço.

Mas esse POO poderia ser uma desvantagem para o software baseado no desempenho, ou seja, com que rapidez o programa é executado?

Muitas vezes sim !!! MAS...

Em outras palavras, muitas referências entre muitos objetos diferentes ou o uso de muitos métodos de várias classes resultam em uma implementação "pesada"?

Não necessariamente. Isso depende do idioma / compilador. Por exemplo, um compilador C ++ otimizado, desde que você não use funções virtuais, geralmente reduz o zero da sobrecarga do objeto. Você pode fazer coisas como escrever um invólucro em um intlocal ou um ponteiro inteligente com escopo definido em um ponteiro antigo simples, que executa tão rápido quanto usar esses tipos de dados antigos simples diretamente.

Em outras linguagens como Java, há um pouco de sobrecarga em um objeto (geralmente bastante pequeno em muitos casos, mas astronômico em alguns casos raros com objetos realmente pequenininhos). Por exemplo, Integerhá consideravelmente menos eficiente que int(leva 16 bytes em vez de 4 em 64 bits). No entanto, isso não é apenas desperdício flagrante ou qualquer coisa desse tipo. Em troca, Java oferece coisas como reflexão sobre cada tipo definido pelo usuário de maneira uniforme, bem como a capacidade de substituir qualquer função não marcada como final.

No entanto, vamos considerar o melhor cenário: o compilador C ++ otimizado, que pode otimizar as interfaces de objetos até a sobrecarga zero . Mesmo assim, o POO geralmente prejudicará o desempenho e impedirá que ele atinja o pico. Isso pode parecer um paradoxo completo: como poderia ser? O problema está em:

Design de interface e encapsulamento

O problema é que, mesmo quando um compilador pode esmagar a estrutura de um objeto até zero de sobrecarga (o que é pelo menos muitas vezes verdadeiro para otimizar compiladores C ++), o encapsulamento e o design de interface (e dependências acumuladas) de objetos refinados geralmente impedem o representações de dados mais ideais para objetos que devem ser agregados pelas massas (que geralmente é o caso de software crítico para o desempenho).

Veja este exemplo:

class Particle
{
public:
    ...

private:
    double birth;                // 8 bytes
    float x;                     // 4 bytes
    float y;                     // 4 bytes
    float z;                     // 4 bytes
    /*padding*/                  // 4 bytes of padding
};
Particle particles[1000000];     // 1mil particles (~24 megs)

Digamos que nosso padrão de acesso à memória seja simplesmente percorrer seqüencialmente essas partículas e movê-las repetidamente em cada quadro, saltando nos cantos da tela e renderizando o resultado.

Já podemos ver uma sobrecarga gritante de 4 bytes necessária para alinhar o birthmembro adequadamente quando as partículas são agregadas de forma contígua. Já ~ 16,7% da memória é desperdiçada com o espaço morto usado para alinhamento.

Isso pode parecer discutível, porque temos gigabytes de DRAM atualmente. No entanto, mesmo as máquinas mais bestiais que temos hoje geralmente têm apenas 8 megabytes quando se trata da região mais lenta e maior do cache da CPU (L3). Quanto menos cabermos lá, mais pagaremos por isso em termos de acesso repetido à DRAM, e as coisas ficarão mais lentas. De repente, desperdiçar 16,7% da memória não parece mais um negócio trivial.

Podemos facilmente eliminar essa sobrecarga sem nenhum impacto no alinhamento do campo:

class Particle
{
public:
    ...

private:
    float x;                     // 4 bytes
    float y;                     // 4 bytes
    float z;                     // 4 bytes
};
Particle particles[1000000];     // 1mil particles (~12 megs)
double particle_birth[1000000];  // 1mil particle births (~8 bytes)

Agora reduzimos a memória de 24 megas para 20 megas. Com um padrão de acesso seqüencial, a máquina agora consumirá esses dados um pouco mais rápido.

Mas vamos olhar para este birthcampo um pouco mais de perto. Digamos que registre o horário de início em que uma partícula nasce (criada). Imagine que o campo seja acessado apenas quando uma partícula é criada pela primeira vez e a cada 10 segundos para ver se uma partícula deve morrer e renascer em um local aleatório na tela. Nesse caso, birthé um campo frio. Ele não é acessado em nossos loops de desempenho crítico.

Como resultado, os dados críticos de desempenho reais não são 20 megabytes, mas na verdade um bloco contíguo de 12 megabytes. A memória quente real que estamos acessando com frequência diminuiu para metade do seu tamanho! Espere acelerações significativas em relação à nossa solução original de 24 megabytes (não precisa ser medida - já fiz esse tipo de coisa mil vezes, mas fique à vontade em caso de dúvida).

No entanto, observe o que fizemos aqui. Nós quebramos completamente o encapsulamento desse objeto de partícula. Seu estado agora está dividido entre Particleos campos privados de um tipo e uma matriz paralela separada. E é aí que o design granular orientado a objetos atrapalha.

Não podemos expressar a representação ideal dos dados quando confinados ao design da interface de um único objeto muito granular, como uma única partícula, um único pixel, até um único vetor de 4 componentes, possivelmente até um único objeto de "criatura" em um jogo. , etc. A velocidade de uma chita será desperdiçada se ela estiver em uma ilha pequenina de 2 metros quadrados, e é isso que o design orientado a objetos muito granular costuma fazer em termos de desempenho. Limita a representação de dados a uma natureza subótima.

Para levar isso adiante, digamos que, como estamos apenas movendo partículas, podemos acessar seus campos x / y / z em três loops separados. Nesse caso, podemos nos beneficiar das intrínsecas SIMD do estilo SoA com registros AVX que podem vetorizar 8 operações SPFP em paralelo. Mas, para fazer isso, precisamos agora usar esta representação:

float particle_x[1000000];       // 1mil particle X positions (~4 megs)
float particle_y[1000000];       // 1mil particle Y positions (~4 megs)
float particle_z[1000000];       // 1mil particle Z positions (~4 megs)
double particle_birth[1000000];  // 1mil particle births (~8 bytes)

Agora estamos voando com a simulação de partículas, mas veja o que aconteceu com o nosso design de partículas. Ele foi completamente demolido, e agora estamos olhando para 4 matrizes paralelas e nenhum objeto para agregá-las. Nosso Particledesign orientado a objetos se tornou sayonara.

Isso aconteceu comigo muitas vezes trabalhando em campos críticos de desempenho, em que os usuários exigem velocidade, sendo apenas a correção a única coisa que exigem mais. Esses pequenos projetos orientados a objetos tiveram que ser demolidos, e as quebras em cascata frequentemente exigiam o uso de uma estratégia de depreciação lenta para o design mais rápido.

Solução

O cenário acima apenas apresenta um problema com projetos orientados a objetos granulares . Nesses casos, muitas vezes acabamos tendo que demolir a estrutura para expressar representações mais eficientes como resultado de representantes de SoA, divisão de campo quente / frio, redução de preenchimento para padrões de acesso sequencial (o preenchimento às vezes é útil para desempenho com acesso aleatório padrões em casos de AoS, mas quase sempre um obstáculo para padrões de acesso seqüencial), etc.

No entanto, podemos pegar a representação final em que estabelecemos e ainda modelar uma interface orientada a objetos:

// Represents a collection of particles.
class ParticleSystem
{
public:
    ...

private:
    double particle_birth[1000000];  // 1mil particle births (~8 bytes)
    float particle_x[1000000];       // 1mil particle X positions (~4 megs)
    float particle_y[1000000];       // 1mil particle Y positions (~4 megs)
    float particle_z[1000000];       // 1mil particle Z positions (~4 megs)
};

Agora estamos bem. Podemos obter todos os itens orientados a objetos que gostamos. A chita tem um país inteiro para atravessar o mais rápido possível. Nossos designs de interface não nos prendem mais a um ponto de gargalo.

ParticleSystempotencialmente pode ser abstrato e usar funções virtuais. É discutível agora, estamos pagando a sobrecarga no nível de coleta de partículas em vez de no nível por partícula . A sobrecarga é 1 / 1.000.000º do que seria de outra forma se estivéssemos modelando objetos no nível de partículas individuais.

Portanto, essa é a solução em verdadeiras áreas críticas de desempenho que lidam com uma carga pesada e para todos os tipos de linguagens de programação (essa técnica beneficia C, C ++, Python, Java, JavaScript, Lua, Swift, etc.). E não pode ser rotulado facilmente como "otimização prematura", pois isso se refere ao design e arquitetura da interface . Não podemos escrever uma base de código modelando uma única partícula como um objeto com um monte de dependências do cliente para umParticle'sinterface pública e depois mudar de idéia mais tarde. Eu fiz muito isso ao ser chamado para otimizar as bases de código herdadas, e isso pode levar meses a reescrever dezenas de milhares de linhas de código com cuidado para usar o design mais volumoso. Isso afeta idealmente como projetamos as coisas antecipadamente, desde que possamos antecipar uma carga pesada.

Eu continuo ecoando essa resposta de uma forma ou de outra em muitas questões de desempenho, e especialmente aquelas relacionadas ao design orientado a objetos. O design orientado a objetos ainda pode ser compatível com as necessidades de desempenho de maior demanda, mas precisamos mudar um pouco a maneira de pensar sobre isso. Temos que dar a esse guepardo algum espaço para correr o mais rápido possível, e isso geralmente é impossível se projetarmos pequenos objetos que mal armazenam qualquer estado.

Sim, a mentalidade orientada a objetos pode definitivamente ser neutra ou negativa quando se trata de programação de alto desempenho, tanto no nível algorítmico quanto na implementação. Se o OOP substituir a análise algorítmica, ele poderá levar à implementação prematura e, no nível mais baixo, as abstrações do OOP deverão ser deixadas de lado.

A questão decorre da ênfase da OOP em pensar em instâncias individuais. Acho justo dizer que a maneira de pensar em um algoritmo em POO é pensar em um conjunto específico de valores e implementá-lo dessa maneira. Se esse for o seu caminho de mais alto nível, é improvável que você realize uma transformação ou reestruturação que levaria a grandes ganhos de O.

No nível algorítmico, ele geralmente pensa na imagem maior e nas restrições ou relações entre valores que levam a grandes ganhos em O. Um exemplo pode ser que não há nada na mentalidade de OOP que o leve a transformar "soma um intervalo contínuo de números inteiros" de um loop para(max + min) * n/2

No nível da implementação, embora os computadores sejam "rápidos o suficiente" para a maioria dos algoritmos no nível do aplicativo, no código crítico de desempenho de baixo nível, preocupa-se bastante a localidade. Novamente, a ênfase da OOP em pensar em uma instância individual e os valores de uma passagem pelo loop podem ser negativos. No código de alto desempenho, em vez de escrever um loop direto, você pode desenrolar parcialmente o loop, agrupar várias instruções de carregamento na parte superior, transformá-las em um grupo e gravá-las em um grupo. Durante todo o tempo, você prestaria atenção nos cálculos intermediários e, imensamente, no cache e no acesso à memória; problemas em que as abstrações OOP não são mais válidas. E, se seguido, pode ser enganoso: nesse nível, você precisa conhecer e pensar nas representações no nível da máquina.

Quando você olha para algo como as Primitivas de desempenho da Intel, você tem literalmente milhares de implementações da Fast Fourier Transform, cada uma delas aprimorada para funcionar melhor para um tamanho de dados específico e uma arquitetura de máquina. (De maneira fascinante, verifica-se que a maior parte dessas implementações é gerada por máquina: Markus Püschel Automatic Performance Programming )

Obviamente, como a maioria das respostas disse, para o maior desenvolvimento, para a maioria dos algoritmos, o POO é irrelevante para o desempenho. Contanto que você não esteja "pessimizando prematuramente" e adicionando muitas chamadas não locais, o thisponteiro não está aqui nem ali.

É relacionado e muitas vezes esquecido.

Não é uma resposta fácil, depende do que você deseja fazer.

Alguns algoritmos têm melhor desempenho usando programação estruturada simples, enquanto outros são melhores usando orientação a objetos.

Antes da Orientação a Objetos, muitas escolas ensinam o design de algoritmos (ed) com programação estruturada. Hoje, muitas escolas ensinam programação orientada a objetos, ignorando o design e o desempenho de algoritmos.

É claro que havia escolas que ensinavam programação estruturada, que nem ligavam para algoritmos.

O desempenho se resume a ciclos de CPU e memória no final. Mas a diferença percentual entre a sobrecarga do sistema de mensagens e encapsulamento OOP e uma semântica de programação aberta mais ampla pode ou não ser uma porcentagem significativa o suficiente para fazer uma diferença notável no desempenho do aplicativo. Se um aplicativo estiver vinculado a falta de disco ou cache de dados, qualquer sobrecarga de OOP poderá ser completamente perdida no ruído.

Porém, nos loops internos do processamento de imagens e sinais em tempo real e em outros aplicativos de computação numérica, a diferença pode muito bem ser uma porcentagem significativa de ciclos de CPU e memória, o que pode tornar a sobrecarga de POO muito mais cara de executar.

A semântica de uma linguagem OOP específica pode ou não expor oportunidades suficientes para o compilador otimizar esses ciclos ou para que os circuitos de previsão de ramificação da CPU sempre adivinhem corretamente e cubram esses ciclos com pré-busca e pipelining.

Um bom design orientado a objetos me ajudou a acelerar um aplicativo consideravelmente. A teve que gerar gráficos complexos de maneira algorítmica. Fiz isso através da automação do Microsoft Visio. Eu trabalhei, mas era incrivelmente lento. Felizmente, eu inseri um nível extra de abstração entre a lógica (o algoritmo) e o material do Visio. Meu componente Visio expôs sua funcionalidade por meio de uma interface. Isso me permitiu substituir facilmente o componente lento por outro arquivo SVG criado, que era pelo menos 50 vezes mais rápido! Sem uma abordagem limpa e orientada a objetos, os códigos para o algoritmo e o controle Vision teriam sido emaranhados de uma maneira que transformaria a mudança em um pesadelo.