Alocação de heap Java mais rápido que C ++

Eu já postei esta pergunta no SO e deu certo. Infelizmente, porém, ele foi fechado (é necessário apenas um voto para reabrir), mas alguém sugeriu que eu o publicasse aqui, pois é um ajuste melhor, portanto o seguinte é literalmente uma cópia da pergunta

Eu estava lendo os comentários sobre esta resposta e vi essa citação.

A instanciação de objetos e os recursos orientados a objetos são extremamente rápidos de usar (mais rápidos que o C ++ em muitos casos), porque foram projetados desde o início. e Coleções são rápidas. O Java padrão supera o C / C ++ padrão nessa área, mesmo para o código C mais otimizado.

Um usuário (com um representante realmente alto, devo acrescentar) defendeu com ousadia essa reivindicação, afirmando que

1. a alocação de heap em java é melhor que a de C ++

2. e adicionou esta declaração defendendo as coleções em java

   E as coleções Java são rápidas em comparação às coleções C ++, devido em grande parte aos diferentes subsistemas de memória.

Portanto, minha pergunta é: será que isso pode realmente ser verdade? Se sim, por que a alocação de heap do java é muito mais rápida?

Esta é uma pergunta interessante, e a resposta é complexa.

No geral, acho justo dizer que o coletor de lixo da JVM é muito bem projetado e extremamente eficiente. É provavelmente o melhor sistema de gerenciamento de memória de uso geral .

O C ++ pode superar o GC da JVM com alocadores de memória especializados projetados para fins específicos. Exemplos podem ser:

• Alocadores de memória por quadro, que limpam toda a área da memória em intervalos periódicos. Eles são freqüentemente usados ​​em jogos C ++, por exemplo, onde uma área de memória temporária é usada uma vez por quadro e descartada imediatamente.
• Alocadores personalizados que gerenciam um conjunto de objetos de tamanho fixo
• Alocação baseada em pilha (embora observe que a JVM também faz isso em várias circunstâncias, por exemplo, através da análise de escape )

Alocadores de memória especializados são, obviamente, limitados por definição. Eles geralmente têm restrições no ciclo de vida do objeto e / ou restrições no tipo de objeto que pode ser gerenciado. A coleta de lixo é muito mais flexível.

A coleta de lixo também oferece algumas vantagens significativas do ponto de vista de desempenho:

• A instanciação de objetos é realmente extremamente rápida. Devido à maneira como novos objetos são alocados seqüencialmente na memória, geralmente é necessário pouco mais de uma adição de ponteiro, o que é certamente mais rápido que os algoritmos de alocação de heap C ++ típicos.
• Você evita a necessidade de custos de gerenciamento do ciclo de vida - por exemplo, a contagem de referência (às vezes usada como uma alternativa ao GC) é extremamente ruim do ponto de vista de desempenho, uma vez que o aumento e a diminuição decrescentes das contagens de referência adicionam muita sobrecarga de desempenho (geralmente muito mais que o GC) .
• Se você usar objetos imutáveis, poderá aproveitar o compartilhamento estrutural para economizar memória e melhorar a eficiência do cache. Isso é muito usado por linguagens funcionais na JVM, como Scala e Clojure. É muito difícil fazer isso sem o GC, porque é extremamente difícil gerenciar a vida útil dos objetos compartilhados. Se você acredita (como eu) que a imutabilidade e o compartilhamento estrutural são essenciais para a criação de grandes aplicativos simultâneos, essa é provavelmente a maior vantagem de desempenho do GC.
• Você pode evitar a cópia se todos os tipos de objetos e seus respectivos ciclos de vida forem gerenciados pelo mesmo sistema de coleta de lixo. Contraste com o C ++, onde você geralmente precisa fazer cópias completas dos dados porque o destino requer uma abordagem de gerenciamento de memória diferente ou possui um ciclo de vida do objeto diferente.

O Java GC tem uma desvantagem importante: como o trabalho de coletar lixo é adiado e realizado em pedaços de trabalho em intervalos periódicos, causa ocasionais pausas no GC para coletar lixo, o que pode afetar a latência. Isso geralmente não é um problema para aplicativos típicos, mas pode descartar o Java em situações em que o tempo real é um requisito (por exemplo, controle robótico). Tempo real suave (por exemplo, jogos, multimídia) normalmente é bom.

Esta não é uma afirmação científica. Estou simplesmente dando uma reflexão sobre esse assunto.

Uma analogia visual é a seguinte: você recebe um apartamento (uma unidade residencial) que é atapetado. O tapete está sujo. Qual é a maneira mais rápida (em termos de horas) de limpar o piso do apartamento?

Resposta: simplesmente enrole o tapete velho; jogar fora; e estenda um tapete novo.

O que estamos negligenciando aqui?

• O custo de mudar os pertences pessoais existentes e depois se mudar.
  • Isso é conhecido como custo de coleta de lixo "pare o mundo".
• O custo do novo tapete.
  • Que, coincidentemente para RAM, é grátis.

A coleta de lixo é um tópico enorme e há muitas perguntas no Programmers.SE e no StackOverflow.

Em uma questão secundária, um gerenciador de alocação de C / C ++ conhecido como TCMalloc, juntamente com a contagem de referência de objeto, é teoricamente capaz de atender às melhores reivindicações de desempenho de qualquer sistema de GC.

O principal motivo é que, quando você solicita um novo lote de memória ao Java, ele vai direto para o final do heap e oferece um bloqueio. Dessa forma, a alocação de memória é tão rápida quanto a alocação na pilha (que é como você faz isso na maioria das vezes em C / C ++, mas além disso ..)

Portanto, as alocações são rápidas como tudo, mas ... isso não conta o custo de liberar a memória. Só porque você não libera nada até muito mais tarde não significa que não custa muito, e no caso do sistema GC, o custo é muito mais do que as alocações de heap 'normais' - não apenas o O GC precisa percorrer todos os objetos para ver se estão vivos ou não, mas também precisa liberá-los e (o grande custo) copiar a memória para compactar a pilha - para que você possa ter a alocação rápida no final mecanismo (ou você ficará sem memória, o C / C ++, por exemplo, percorrerá a pilha em todas as alocações procurando o próximo bloco de espaço livre que possa caber no objeto).

Esse é um dos motivos pelos quais os benchmarks Java / .NET mostram um desempenho tão bom, mas os aplicativos do mundo real mostram um desempenho tão ruim. Eu só preciso olhar para os aplicativos no meu telefone - os realmente rápidos e responsivos são todos escritos usando o NDK, tanto que até fiquei surpreso.

Atualmente, as coleções podem ser rápidas se todos os objetos forem alocados localmente, por exemplo, em um único bloco contíguo. Agora, em Java, você simplesmente não recebe blocos contíguos, pois os objetos são alocados um de cada vez a partir do final gratuito do heap. Você pode acabar com eles felizes contíguos, mas apenas por sorte (ou seja, até o capricho das rotinas de compactação do GC e como ele copia objetos). O C / C ++, por outro lado, suporta explicitamente alocações contíguas (via pilha, obviamente). Geralmente, os objetos heap no C / C ++ não são diferentes do BTW do Java.

Agora, com C / C ++, você pode obter melhores resultados do que os alocadores padrão projetados para economizar memória e usá-la com eficiência. Você pode substituir o alocador por um conjunto de conjuntos de blocos fixos, para sempre encontrar um bloco exatamente do tamanho certo para o objeto que você está alocando. Andar a pilha apenas se torna uma questão de pesquisa de bitmap para ver onde está um bloco livre e a desalocação está simplesmente redefinindo um pouco nesse bitmap. O custo é que você usa mais memória ao alocar em blocos de tamanho fixo, para ter um monte de blocos de 4 bytes, outro para blocos de 16 bytes, etc.

Eden Space

Portanto, minha pergunta é: será que isso pode realmente ser verdade? Se sim, por que a alocação de heap do java é muito mais rápida?

Eu estudei um pouco sobre como o Java GC funciona, pois é muito interessante para mim. Estou sempre tentando expandir minha coleção de estratégias de alocação de memória em C e C ++ (interessado em tentar implementar algo semelhante em C), e é uma maneira muito, muito rápida de alocar muitos objetos de maneira rápida a partir de um perspectiva prática, mas principalmente devido ao multithreading.

A maneira como a alocação do Java GC funciona é usar uma estratégia de alocação extremamente barata para alocar objetos inicialmente ao espaço "Eden". Pelo que sei, é usando um alocador de pool seqüencial.

Isso é muito mais rápido apenas em termos de algoritmo e redução de falhas de página obrigatórias do que de propósito geral mallocem C ou padrão, jogando operator newem C ++.

Mas os alocadores seqüenciais têm uma fraqueza evidente: eles podem alocar pedaços de tamanho variável, mas não podem liberar nenhum pedaço individual. Eles apenas alocam de maneira sequencial direta com preenchimento para alinhamento e podem apenas limpar toda a memória que alocaram de uma só vez. Eles são úteis normalmente em C e C ++ para a construção de estruturas de dados que precisam apenas de inserções e não remoções de elementos, como uma árvore de pesquisa que só precisa ser criada uma vez quando o programa é iniciado e depois é pesquisada repetidamente ou apenas novas chaves foram adicionadas ( nenhuma chave removida).

Eles também podem ser usados ​​mesmo para estruturas de dados que permitem a remoção de elementos, mas esses elementos não serão realmente liberados da memória, pois não podemos desalocá-los individualmente. Essa estrutura usando um alocador seqüencial consumiria cada vez mais memória, a menos que houvesse alguma passagem diferida na qual os dados fossem copiados para uma cópia compacta e nova usando um alocador sequencial separado (e essa é uma técnica muito eficaz se um alocador fixo ganhar por algum motivo - apenas aloque sequencialmente uma nova cópia da estrutura de dados e despeje toda a memória da antiga).

Coleção

Como no exemplo acima da estrutura de dados / pool sequencial, seria um grande problema se o Java GC apenas alocasse dessa maneira, mesmo que seja super rápido para uma alocação intermitente de muitos blocos individuais. Não seria possível liberar nada até que o software fosse desligado; nesse momento, ele poderia liberar (limpar) todos os conjuntos de memórias de uma só vez.

Portanto, depois de um único ciclo de GC, é feita uma passagem pelos objetos existentes no espaço "Eden" (alocados sequencialmente), e os que ainda são referenciados são alocados usando um alocador de uso geral, capaz de liberar pedaços individuais. Os que não são mais referenciados serão simplesmente desalocados no processo de limpeza. Então, basicamente, é "copiar objetos do espaço Eden, se eles ainda são referenciados e depois limpar".

Normalmente, isso seria muito caro, por isso é feito em um encadeamento em segundo plano separado para evitar um bloqueio significativo do encadeamento que originalmente alocava toda a memória.

Depois que a memória é copiada do espaço Eden e alocada usando esse esquema mais caro que pode liberar blocos individuais após um ciclo inicial do GC, os objetos são movidos para uma região de memória mais persistente. Esses blocos individuais são liberados em ciclos subsequentes de GC se deixarem de ser referenciados.

Rapidez

Portanto, de maneira grosseira, a razão pela qual o Java GC pode muito bem superar o C ou C ++ na alocação direta de heap é porque ele está usando a estratégia de alocação totalmente mais barata e totalmente degeneralizada no encadeamento que solicita a alocação de memória. Em seguida, ele economiza o trabalho mais caro que normalmente precisaríamos ao usar um alocador mais geral, como diretamente mallocpara outro encadeamento.

Portanto, conceitualmente, o GC realmente precisa fazer mais trabalho, mas está distribuindo isso entre os threads, para que o custo total não seja pago antecipadamente por um único thread. Ele permite que o thread que aloca memória faça com que seja super barato e adie a verdadeira despesa necessária para fazer as coisas corretamente, de modo que objetos individuais possam realmente ser liberados para outro thread. Em C ou C ++, quando ligamos mallocou ligamos operator new, temos que pagar o custo total antecipadamente no mesmo encadeamento.

Essa é a principal diferença, e por que o Java pode muito bem superar o C ou C ++ usando apenas chamadas ingênuas para mallocou operator newalocar um monte de pequenos pedaços individualmente. É claro que normalmente haverá algumas operações atômicas e algum bloqueio potencial quando o ciclo do GC entrar em ação, mas provavelmente é otimizado um pouco.

Basicamente, a explicação simples se resume a pagar um custo mais alto em um único encadeamento ( malloc) vs. pagar um custo mais barato em um único encadeamento e depois pagar o custo mais alto em outro que possa ser executado em paralelo ( GC). Como desvantagem, fazer isso dessa maneira implica que você precisa de dois indiretos para obter referência de objeto a objeto, conforme necessário, para permitir que o alocador copie / mova a memória sem invalidar as referências de objeto existentes e também poderá perder a localidade espacial quando a memória do objeto for saiu do espaço "Eden".

Por último, mas não menos importante, a comparação é um pouco injusta, porque o código C ++ normalmente não aloca uma carga de objetos individualmente no heap. O código C ++ decente tende a alocar memória para muitos elementos em blocos contíguos ou na pilha. Se ele alocar uma carga cheia de objetos minúsculos, um de cada vez, no armazenamento gratuito, o código é uma merda.

Tudo depende de quem mede a velocidade, qual velocidade de implementação eles medem e o que eles querem provar. E o que eles comparam.

Se você apenas alocar / desalocar, em C ++ você pode ter 1.000.000 de chamadas para malloc e 1.000.000 de chamadas para free (). Em Java, você teria 1.000.000 de chamadas para new () e um coletor de lixo sendo executado em um loop, encontrando 1.000.000 de objetos que ele pode liberar. O loop pode ser mais rápido que a chamada free ().

Por outro lado, malloc / free melhorou outro tempo e, normalmente, malloc / free apenas define um bit em uma estrutura de dados separada e é otimizado para acontecer malloc / free no mesmo encadeamento, portanto, em um ambiente multithread, nenhuma variável de memória compartilhada são usados ​​em muitos casos (e as variáveis ​​de bloqueio ou memória compartilhada são muito caras).

Por outro lado, existem coisas como contagem de referência que você pode precisar sem coleta de lixo e que não é de graça.