Eu notei que toda linguagem de programação OO moderna com a qual eu estou menos familiarizado (que é basicamente Java, C # e D) permite matrizes covariantes. Ou seja, uma matriz de string é uma matriz de objetos:
Object[] arr = new String[2]; // Java, C# and D allow this
Os arrays Covariant são um buraco no sistema de tipo estático. Eles tornam possíveis erros de tipo que não podem ser detectados em tempo de compilação, portanto, cada gravação em uma matriz deve ser verificada no tempo de execução:
arr[0] = "hello"; // ok
arr[1] = new Object(); // ArrayStoreException
Isso parece um péssimo desempenho se eu fizer muitas lojas de array.
C ++ não possui matrizes covariantes, portanto, não há necessidade de fazer tal 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];
pode-se argumentar que a loja não pode falhar. Tenho certeza de que há muitas outras otimizações possíveis que não pensei.
Os compiladores modernos realmente fazem esses tipos de otimizações, ou eu tenho que conviver com o fato de que, por exemplo, um Quicksort sempre faz verificações de tempo de execução desnecessárias em O (n log n)?
Podem as linguagens OO modernas evitar a sobrecarga criada pelo suporte de matrizes de co-variante?
D não tem matrizes covariantes. Permitiu-lhes antes da versão mais recente ( DMD 2.057 ), mas que 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 com -release . Portanto, no modo de lançamento, não há diferença real de desempenho entre arrays em C / C ++ e aqueles em D.
Sim, uma otimização crucial é esta:
sealed class Foo
{
}
Em C #, essa classe não pode ser um supertipo para qualquer tipo, portanto, você pode evitar a verificação de uma matriz do tipo Foo .
E para a segunda pergunta, em matrizes co-variantes do F # não são permitidas (mas eu acho que a verificação permanecerá no CLR a menos que seja encontrada desnecessária em otimizações em tempo de execução)
let a = [| "st" |]
let b : System.Object[] = a // Fails
Um problema um pouco relacionado é a verificação do limite da matriz. Isso pode ser uma leitura interessante (mas antiga) sobre as otimizações feitas no CLR (a covariância também é mencionada em 1 lugar): link
Resposta Java:
Acho que você não comparou o código, não é? Em geral, 90% de todos os elencos dinâmicos em Java são livres porque o JIT pode elidí-los (o quicksort deve ser um bom exemplo disso) e o restante é uma seqüência ld/cmp/br que é absolutamente previsível (se não, bem, por que diabos seu código jogando todas as exceções de elenco dinâmico?).
Fazemos a carga muito antes da comparação real, a ramificação está prevista corretamente em 99,9999% (estatística composta!) de todos os casos, portanto, não protelamos o pipeline (supondo que não atingimos a memória com o carga, se não bem que será perceptível, mas, em seguida, a carga é necessária de qualquer maneira). Portanto, o custo é de 1 ciclo de clock se o JIT não puder evitar a verificação.
Alguma sobrecarga? Claro, mas duvido que você perceba ...
Para ajudar a apoiar minha resposta, consulte este Dr. Cliff Click na postagem do blog discutindo o desempenho do Java x 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ê disse, seria um buraco no sistema de tipos permitir isso.
Você pode ser perdoado pelo erro, pois esse bug foi corrigido lastest 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 aproximadamente 1,0 ns. A diferença é provável que seja devido à verificação extra para o tipo.
Geralmente, os Objetos são usados apenas para lógica de nível superior, quando nem todos os ns são contados. Se você precisar salvar todos os ns, eu evitaria usar construções de nível superior como Objetos. Atribuições sozinhas provavelmente sã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 outros idiomas OO modernos? Bem, o Delphi evita esse problema inteiramente tendo string como um primitivo, não um objeto. Portanto, uma matriz de strings é exatamente uma matriz de strings e nada mais, e qualquer operação nelas é tão rápida quanto o código nativo pode ser, sem sobrecarga de verificação de tipo.
No entanto, os arrays de strings não são usados com muita frequência; Programadores Delphi tendem a favorecer a classe TStringList . Para uma quantidade mínima de sobrecarga, ele fornece um conjunto de métodos de grupo de strings que são úteis em muitas situações em que a classe foi comparada a um canivete suíço. Então, é idiomático usar um objeto de lista de strings em vez de uma matriz de strings.
Como para outros objetos em geral, o problema não existe porque no Delphi, como em C ++, as matrizes não são covariantes, a fim de evitar o tipo de buracos do sistema de tipos descrito aqui.
or do I have to live with the fact that, for example, a Quicksort always does O(n log n) unnecessary runtime checks?
O desempenho da CPU não é monótono, o que significa que programas mais longos podem ser mais rápidos do que os mais curtos (isso depende da CPU e é verdadeiro para as arquiteturas comuns x86 e amd64). Portanto, é possível que um programa que faz a verificação de limites em matrizes seja realmente mais rápido do que o programa deduzido do anterior, removendo a verificação de limites.
O motivo desse comportamento é que a verificação vinculada modifica o alinhamento do código na memória, modifica a frequência de ocorrências do cache, etc.
Então, sim, conviva com o fato de que o Quicksort sempre faz verificações espúrias O (n log n) e otimizar após a criação de perfil.
O Scala é uma linguagem OO que possui matrizes invariantes, em vez de covariantes. Ele tem como alvo a JVM, portanto, não há uma vitória por desempenho, mas evita um erro comum em Java e C # que compromete a segurança de tipos por motivos de compatibilidade com versões anteriores.