As linguagens OO modernas podem competir com o desempenho da loja de array do C ++?

Acabei de notar que toda linguagem de programação OO moderna com a qual estou familiarizado (que é basicamente apenas Java, C # e D) permite matrizes covariantes. Ou seja, uma matriz de cadeias de caracteres é uma matriz de objetos:

Object[] arr = new String[2];   // Java, C# and D allow this

Matrizes covariantes são um orifício no sistema de tipo estático. Eles possibilitam erros de tipo que não podem ser detectados em tempo de compilação, portanto, toda gravação em uma matriz deve ser verificada em tempo de execução:

arr[0] = "hello";        // ok
arr[1] = new Object();   // ArrayStoreException

Parece um desempenho terrível se eu fizer muitas lojas de matriz.

O C ++ não possui matrizes covariantes, portanto, não há necessidade de fazer essa verificação de tempo de execução, o que significa que não há penalidade de desempenho.

Existe alguma análise feita para reduzir o número de verificações de tempo de execução necessárias? Por exemplo, se eu disser:

arr[1] = arr[0];

alguém poderia argumentar que a loja não pode falhar. Tenho certeza de que existem muitas outras otimizações possíveis em que não pensei.

Os compiladores modernos realmente fazem esse tipo de otimização ou eu tenho que conviver com o fato de que, por exemplo, um Quicksort sempre verifica O (n log n) verificações de tempo de execução desnecessárias?

Os idiomas OO modernos podem evitar a sobrecarga criada pelo suporte a matrizes de co-variantes?

D não possui matrizes covariantes. Permitiu-os antes da versão mais recente ( dmd 2.057 ), mas esse bug foi corrigido.

Uma matriz em D é efetivamente apenas uma estrutura com um ponteiro e um comprimento:

struct A(T)
{
    T* ptr;
    size_t length;
}

A verificação de limites é feita normalmente ao indexar uma matriz, mas é removida quando você compila -release. Portanto, no modo de liberação, não há diferença real de desempenho entre matrizes em C / C ++ e aquelas em D.

Sim, uma otimização crucial é esta:

sealed class Foo
{
}

Em C #, essa classe não pode ser um supertipo para nenhum tipo, para evitar a verificação de uma matriz de tipos Foo.

E para a segunda pergunta, em matrizes de co-variantes F # não são permitidas (mas acho que a verificação permanecerá no CLR, a menos que seja desnecessário em otimizações em tempo de execução)

let a = [| "st" |]
let b : System.Object[] = a // Fails

https://stackoverflow.com/questions/7339013/array-covariance-in-f

Um problema um pouco relacionado é a verificação de limites de matriz. Pode ser uma leitura interessante (mas antiga) sobre otimizações feitas no CLR (covariância também é mencionada em 1 local): http://blogs.msdn.com/b/clrcodegeneration/archive/2009/08/13/array-bounds -check-eliminação-in-the-clr.aspx

Resposta Java:

Presumo que você não tenha comparado o código, não é? Em geral, 90% de todas as transmissões dinâmicas em Java são gratuitas porque o JIT pode eliminá-las (o quicksort deve ser um bom exemplo disso) e o restante é uma ld/cmp/brsequência absolutamente previsível (se não, bem, por que diabos seu código está sendo lançado) todas essas exceções de elenco dinâmico?).

Fazemos a carga muito antes da comparação real, a ramificação é predita corretamente em 99,9999% (estatística composta!) De todos os casos, para que não paremos o pipeline (supondo que não atingimos a memória com a carga, se não é bem isso será perceptível, mas a carga é necessária de qualquer maneira). Portanto, o custo é de 1 ciclo de relógio, se o JIT não puder evitar a verificação.

Alguma sobrecarga? Claro, mas duvido que você alguma vez notará ..

Para ajudar a apoiar minha resposta, consulte este post do Dr. Cliff Click discutindo o desempenho de Java vs. C.

D não permite matrizes covariantes.

void main()
{
    class Foo {}
    Object[] a = new Foo[10];
}  

/* Error: cannot implicitly convert expression (new Foo[](10LU)) of type Foo[]
to Object[] */

Como você diz, haveria um buraco no sistema de tipos para permitir isso.

Você pode ser perdoado pelo erro, pois esse bug foi corrigido apenas no último DMD, lançado em 13 de dezembro.

O acesso à matriz em D é tão rápido quanto em C ou C ++.

Do teste que fiz em um laptop barato, a diferença entre usar int[]e Integer[]é de cerca de 1,0 ns. É provável que a diferença se deva à verificação extra do tipo.

Geralmente, os objetos são usados ​​apenas para lógica de nível superior quando nem todos os ns contam. Se você precisar salvar todos os ns, evitaria o uso de construções de nível superior, como Objetos. Somente as atribuições provavelmente serão um fator muito pequeno em qualquer programa real. por exemplo, criar um novo objeto na mesma máquina é 5 ns.

As chamadas para compareTo provavelmente serão muito mais caras, especialmente se você estiver usando um objeto complexo como String.

Você perguntou sobre outras linguagens OO modernas? Bem, Delphi evita esse problema inteiramente por stringser um objeto primitivo, não um objeto. Portanto, uma matriz de cadeias de caracteres é exatamente uma matriz de cadeias de caracteres e nada mais, e qualquer operação nelas é tão rápida quanto o código nativo pode ser, sem verificação de tipo de sobrecarga.

No entanto, matrizes de seqüência de caracteres não são usadas com muita frequência; Os programadores Delphi tendem a favorecer a TStringListclasse. Para uma quantidade mínima de sobrecarga, ele fornece um conjunto de métodos de grupos de cordas que são úteis em tantas situações que a classe foi comparada a um canivete suíço. Portanto, é idiomático usar um objeto de lista de cadeias em vez de uma matriz de cadeias.

Quanto a outros objetos em geral, o problema não existe porque no Delphi, como no C ++, as matrizes não são covariantes, a fim de evitar o tipo de tipo de buracos do sistema descritos aqui.

ou tenho que conviver com o fato de que, por exemplo, um Quicksort sempre verifica O (n log n) runtime desnecessário?

O desempenho da CPU não é monotônico, o que significa que os programas mais longos podem ser mais rápidos que os mais curtos (isso depende da CPU e isso é verdade para as arquiteturas comuns x86 e amd64). Portanto, é possível que um programa que faça a verificação vinculada em matrizes seja realmente mais rápido que o programa deduzido do anterior removendo essas verificações vinculadas.

A razão desse comportamento é que a verificação vinculada modifica o alinhamento do código na memória, modifica a frequência de acertos do cache etc.

Portanto, sim, viva com o fato de que o Quicksort sempre faz verificações espúrias O (n log n) e otimiza após a criação de perfil.

Scala é uma linguagem OO que possui matrizes invariantes e não covariantes. Ele tem como alvo a JVM, portanto, não há ganho de desempenho por lá, mas evita um erro comum de Java e C # que compromete sua segurança de tipo por motivos de compatibilidade com versões anteriores.