• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

pedrotuga

A falácia de eficiencia do C/C++ (ingles)

30 mensagens neste tópico

Aqui vai um artigo interessante de se ler.

Penso que é um pouco irónico o título. Tipo... basicamente o artigo diz que o C é eficiente mas não para programas de cálculo científico.

Uma coisa engraçada... reparem na lentidão do java.

The "C is Efficient" Language Fallacy

Category: programming

Posted on: November 2, 2006 9:31 AM, by Mark C. Chu-Carroll

I came across an article yesterday about programming languages, which hit on one of my major peeves, so I can't resist responding. The article is at greythumb.org, and it's called Programmer's rant: what should and should not be added to C/C++.

It's a variation on the extremely common belief that C and C++ are the best languages to use when you need code to run fast. They're not. They're good at things that need to get very close to the hardware - not in the efficiency sense, but in the sense of needing to be able to fairly directly munge the stack, address specific hardware registers, etc. But they are dreadful languages for writing real scientific and/or numerical code.

To quote the part of the article that set me off:

    First of all, these fears are nonsense. C and C++ are never going to disappear. Why? Because there are classes of programming problems that are still and will always be CPU bound and there is still no language as fast as C or C++ for these problems. I highly doubt that there ever will be.

    I'm talking about things like: scientific number crunching, game/simulation physics, raytracing, real-time 3d graphics, audio processing, codec implementation, high-speed network packet routing, evolutionary computation (my personal favorite :P, and of course implementing all these high-level languages' runtimes. There are also problems like OS and hardware driver implementation where you need something "close to the metal" that can interact closely with and even embed assembly language. C is basically shorthand for assembler, which is why it's the preferred language for that kind of thing.

    For these tasks, premature optimization at the level of language and framework choice is not evil. In some cases it's a requirement. I predict that at least some of these tasks will still be done in C, C++, or some language with similar characteristics 50 years from now. To give you an idea of just how much faster C can be for tasks like this, I have found that evolvable instruction set based evolutionary computation is almost twice as fast when competently implemented in C than a similar competent implementation in Java.

Here's the problem. C and C++ suck rocks as languages for numerical computing. They are not the fastest, not by a longshot. In fact, the fundamental design of them makes it pretty much impossible to make really good, efficient code in C/C++. There's a good reason that Fortran is still the language of choice for real, intense scientific applications that require the absolute best performance that can be drawn out of our machines - applications like computational fluid dynamics.

Making real applications run really fast is something that's done with the help of a compiler. Modern architectures have reached the point where people can't code effectively in assembler anymore - switching the order of two independent instructions can have a dramatic impact on performance in a modern machine, and the constraints that you need to optimize for are just more complicated than people can generally deal with.

So for modern systems, writing an efficient program is sort of a partnership. The human needs to careful choose algorithms - the machine can't possibly do that. And the machine needs to carefully compute instruction ordering, pipeline constraints, memory fetch delays, etc. The two together can build really fast systems. But the two parts aren't independent: the human needs to express the algorithm in a way that allows the compiler to understand it well enough to be able to really optimize it.

And that's where C and C++ fall down. C and C++ are strongly pointer-based languages. The real semantics of almost anything interesting end up involving pretty much unrestricted pointers. In C and C++, there's no such thing as an array - there's just pointers, which you can subscript and a shorthand for pointer arithmetic and indirection(x[n'] in C/C++ is the same thing as *(x+n).)

That pointer based nature means that in a C or C++ program, it's very hard for a compiler to figure out what things are independent. It comes down to a problem called alias detection. Alias detection is identifying when two variables might be referencing the same location. Alias detection becomes a horrific mess in the presence of unrestricted pointers. Let me show you an example:

for (int i=0; i < 20000) {

  for (int j=0; j < 20000) {

      x[j] = y[i-2][j+1] * y[i+1][j-2];

  }

}

If you look at that loop, it can be parallelized or vectorized without any problem if and only if the array pointed to by x and the array pointed to by y are completely distinct with no overlap. But there's no way to write code in C or C++ that guarantees that. If it were Fortran-77, you could easily check if they were distinct. If it were Fortran-98, you could check if x or y were declared as possible pointer targets, and the programmer could make it obvious that they didn't overlap if they wanted to. But you can't do that in C or C++. (And Fortran isn't even the best - an experimental language called Sisal from Lawrence Livermore labs used to be able to beat Fortran by around 20% on typical code!)

That example involves parallelization of code, but alias related problems aren't just an issue for parallelism; it's just easiest to show an example for parallelism. The aliasing issues in C and C++ have a very direct impact on real code.

Let me tell you about a concrete example of this, and then I'll stop ranting. About six years ago, I was working on a project where I needed to implement a rather messy algorithm to compute something called the "longest common subsequence" (LCS) of two arrays. The standard algorithm for computing LCS is using something called dynamic programming; it's O*(n3) time, and O(n2) space. There's an algorithm that was designed by people doing computational biology that can do it in the same time, but using on average O(n) space.

I didn't know what language to use for this project, so I decided to do an experiment. I wrote the LCS algorithm in a bunch of different languages, to compare how complex the code was, and how fast it ran. I wrote the comp bio algorithm in C, C++, OCaml, Java, and Python, and recorded the results. What I got timing-wise for running the programs on arrays of 2000 elements each was:

    * C: 0.8 seconds.

    * C++: 2.3 seconds.

    * OCaml: 0.6 seconds interpreted, 0.3 seconds fully compiled.

    * Java: 1 minute 20 seconds.

    * Python: over 5 minutes.

About a year later, testing a new JIT for Java, the Java time was down to 0.7 seconds to run the code, plus about 1 second for the JVM to start up. (The startup times for C, C++, and Ocaml weren't really measurable - they were smaller than the margin of error for the measurements.)

The Objective-Caml bytecode interpreter was faster than the carefully hand-optimized C program! Why? Because the OCaml compiler could recognize that the arrays were completely independent - it didn't need to worry about one iteration of the loop stepping on the values used by another. The C compiler couldn't apply a lot of useful optimizations, because it couldn't be sure that they were valid.

And it's not just non-assignment based functional languages where you can see supposedly less-efficient high level languages crushing the performance of C/C++. CMU CommonLisp can beat C/C++ on numeric code. There was a paper a few years back documenting it: using a Sun SPARC workstation, if you use the optional type declarations, and write scientific/numeric code in Lisp, using vectors (Lisp arrays) and assignments to implement exactly the same algorithm as C, the CMU CommonLisp code will perform better than C code generated by either the Solaris C compiler or GCC with maximum optimization.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

se eu percebi bem o que aqui é dito (o meu inglês não é grande coisa :P), o problema de eficiência do C/C++ tem a ver com o facto de ser difícil ao compilador verificar se o código é paralelizável ou não.

é claro que este trabalho pode ser feito por nós. podemos usar funções para criar vários processos aumentando a eficiência do código. a vantagem de outras linguagens é que isto é feito pelo compilador, poupando-nos (muito) trabalho. mas esta é também uma das razões pela qual o paradigma de programação orientada aos aspectos começa a ganhar cada vez mais importância, pois permite-nos facilmente adaptar o código à plataforma onde vai correr.

a grande vantagem do C é que nos disponibiliza uma quantidade enorme de recursos que, quando bem aproveitados, produzem código muito eficiente, para qualquer tipo de aplicação. o problema é que muitas vezes não usamos todos os recursos que ele nos disponibiliza (em parte porque a complexida dos nossos programas aumenta muito).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Exacto.

No ramo de processos concorrentes existe por vezes falta de informação e por isso o código pode não ser o melhor. Gostava de ver o código de C++ desse teste. Provavelmente não teve em conta o uso de alguns recursos que C++ disponibiliza nesses aspectos. Tal como o OpenMP.

Um bom local para ver isso será http://en.wikipedia.org/wiki/OpenMP

Evidente será dizer que de facto o código poderá ser mais complexo. Mas nem por isso deixa de ser uma hipotese para bater outras linguagens em processos concorrentes.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O problema que focam é o facto de na verdade não existirem arrays. Basicamente uma variável array é um ponteiro para o endereço do inicio da memória. Isto acaba por ocupar um carradão de momória.

O C não é lambão em termos de memória, mas é preciso geri-la senão ... boooom!

Por isso é que eu gosto destas linguagens novas e interpretadas... php, python, etc... se não estamos a fazer calculo pesado qual é a cena de poupar milisegundos. Tipo... até agora nenhum script em php me demorou mais de 20ms a ser executado...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O problema que focam é o facto de na verdade não existirem arrays. Basicamente uma variável array é um ponteiro para o endereço do inicio da memória. Isto acaba por ocupar um carradão de momória.

O C não é lambão em termos de memória, mas é preciso geri-la senão ... boooom!

podemos ver a forma como o C gere a memória de dois pontos de vista: por um lado dá-nos montes de trabalho a geri-la, por outro, quando bem geriada, permite-nos obter ganhos de eficiência.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O problema que focam é o facto de na verdade não existirem arrays. Basicamente uma variável array é um ponteiro para o endereço do inicio da memória. Isto acaba por ocupar um carradão de momória.

O C não é lambão em termos de memória, mas é preciso geri-la senão ... boooom!

Yaps... doi precisamente isso que quis dizer

podemos ver a forma como o C gere a memória de dois pontos de vista: por um lado dá-nos montes de trabalho a geri-la, por outro, quando bem geriada, permite-nos obter ganhos de eficiência.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O problema que focam é na verdade a própria natureza da linguagem C. A base da versatilidade do C, da facilidade de mexer quase a nível de hardware. A vantagem dos ponteiros é o próprio calcanhar de Aquiles da linguagem.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O problema que focam é na verdade a própria natureza da linguagem C. A base da versatilidade do C, da facilidade de mexer quase a nível de hardware. A vantagem dos ponteiros é o próprio calcanhar de Aquiles da linguagem.

Até pode ser mas como o Rui Carlos disse, a memória bem gerida é sinónimo de sucesso em C. Eu próprio estou a fazer neste momento um programa em C e tenho de me preocupar e muito com isso. Trabalho? Claro que dá mas existem muitas técnicas para isso...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não se está a falar de memória mal ou bem gerida. É claro que todos os programas precisam de memória bem gerida, estamos a falar de coisas que saem fora do controlo do programador. As optimizações que o compilador faz, ou neste caso, não pode fazer.

O que o artigo foca é o que todos os programadores de Fortran sabem há muito, comparado com Fortran, C é lento. É claro que isto depende do problema em questão e não se pode dizer que C é sempre mais lento que C, tal como Java não é sempre mais lento que C, até pelo que é afirmado no artigo, o Java correu o código em 0.7s em oposição aos 0.8 do C. Sim, falta somar 1s correspondente ao arranque da máquina, mas esse arranque em muitos problemas pode ser ignorado.

Artigos como este existem imensos, comparações de C vs Java então são às centenas no fim a conclusão é sempre a mesma, devido aos ponteiros o compilador C não pode optimizar o código como pode o de Fortran, ou o de Java.

Peace.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

o compilador não pode optimizar o código mas o programador pode, só precisa saber fazê-lo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
o compilador não pode optimizar o código mas o programador pode, só precisa saber fazê-lo.

?!? O compilador não só pode como faz. Faz quantas pesquisas quiseres que encontras muita informação sobre o assunto. No próprio artigo que abre este tópico o autor fala sobre as optimizações do compilador, é esse o assunto do artigo...

(...) But the two parts aren't independent: the human needs to express the algorithm in a way that allows the compiler to understand it well enough to be able to really optimize it. (...)

E são essas optimizações que importam... novamente não estamos a falar de optimizações de programador mas sim de compilador.

Peace.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Em C é mais do que possível o compilador optimizar o código, e existem vários tipos de optimizações.

Se compilarmos em gcc usando a flag -O3 ele vai optimizar o código a nível de velocidade de processamento, se compilarmos usando -O2 ele vai optimizar o código em termos de velocidade, mas não usando optimizações que envolvam troca de espaço por tempo etc..

A lista contínua.

Uma coisa que eu não percebo, é como é possível o C++ demorar tanto tempo, visto poder recorrer a tudo o que o C usa, mais algumas bibliotecas. (C++ é só uma extensão de C)

Simplesmente não faz sentido.

Só mais um pormenor, usando programação dinâmica é possível resolver-se o problema "longest common subsequence" em O(n*m), sendo n o tamanho do primeiro vector e m o tamanho do segundo, o que generalizando (considerando os vectores iguais) dá O(n2), bastante mais rápido do que o referido no artigo. (usando O(n) espaço)

Podem ver mais informações aqui:

http://www.ics.uci.edu/~eppstein/161/960229.html

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
o compilador não pode optimizar o código mas o programador pode, só precisa saber fazê-lo.

?!? O compilador não só pode como faz. Faz quantas pesquisas quiseres que encontras muita informação sobre o assunto. No próprio artigo que abre este tópico o autor fala sobre as optimizações do compilador, é esse o assunto do artigo...

(...) But the two parts aren't independent: the human needs to express the algorithm in a way that allows the compiler to understand it well enough to be able to really optimize it. (...)

E são essas optimizações que importam... novamente não estamos a falar de optimizações de programador mas sim de compilador.

Peace.

Não se está a falar de memória mal ou bem gerida. É claro que todos os programas precisam de memória bem gerida, estamos a falar de coisas que saem fora do controlo do programador. As optimizações que o compilador faz, ou neste caso, não pode fazer.

tu é que falaste em optimizações que o compilador não pode fazer... e eu disse que as optimizações que o compilador (de C) não faz, podemos fazê-las nós.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Acho que não perceberam o problema...

A questão é que um compilador de Fortran, para exemplo, porque o Fortran não tem ponteiros comsegue fazer optimizações que um compilador de C/C++ não pode fazer. E é simplesmente esse ponto que faz o código final em Fortran ser mais rápido que em C/C++.

Peace.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Acho que não perceberam o problema...

A questão é que um compilador de Fortran, para exemplo, porque o Fortran não tem ponteiros comsegue fazer optimizações que um compilador de C/C++ não pode fazer. E é simplesmente esse ponto que faz o código final em Fortran ser mais rápido que em C/C++.

Peace.

tu é que não estás a perceber o problema!!!

aquilo que no Fortran o compilador faz, podemos nós, programadores, fazer em C (em vez do compilador de C).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Parece que existe aqui alguma falta de comunicação...

Quando falo em optimizações de compilador falo das que nós programadores não podemos fazer, falo das transformações que o código C sofre ao passar para assembly, algo que só o compilador faz. Não estou a falar em optimizações de algoritmos, trocas de linhas, ciclos mais bem delineados e afins, estou a falar da simples transformação de uma linha como 'int x=0;', ou um ciclo 'for'.

Essas são as optimizações que se falam e são esses os problemas. Como é que o compilador de C sabe em tempo de compilação se uma variável é um ponteiro ou não? Como é que compilador sabe que duas variáveis referenciam o mesmo valor? A mesma zona de memória?

Aí é que entra o problema de 'alias' e aí é que o compilador de C perde, gerando código mais lento. Mas é sempre mais lento? Claro que não, normalmente C perde em casos de computação numérica, porque é aí que o problema de 'alias' se manifesta mais fortemente.

Este é um problema um pouco complicado de explicar e de perceber, é preciso ter muito bom conhecimento do que é a compilação e do que faz cada compilador ao gerar código. Sinceramente não sei como me fazer entender... ou talvez não esteja a perceber.

Peace.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

que tipo de optimizações faz o compilador de fortran que tu não podes fazer em C.

por exemplo, no caso dos ciclos, podemos optimizar o código através da criação de vários processos e da divisão do "trabalho" entre eles, do "desenrolar" dos cilcos, etc. optimizações que se calhar te permitem obter código tão eficiente como em fortran.

estás a assumir que o compilador de fortran faz optimizações que os programadores não podem fazer. mas existem muitos "truques" para optimizar código em C (nomeadamente em ciclos), o problema é eles variam de arquitectura para arquitectura e é muito complicado saber aplicá-los. parece-me que é apenas aqui que o fortran poderá levar vantagem, é que o programador não precisa de conhecer esses truques.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Que optimizações fazes neste ciclo?

for(z = 0; z < 15; z++)
    printf("Simples ciclo");

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Que optimizações fazes neste ciclo?

for(z = 0; z < 15; z++)
    printf("Simples ciclo");

dependendo da máquina que estou a usar, posso desenrolar o cilco e criar vários processos.

desenrolar do cilco

for(i=0;i<15;z+=5)
{
  printf("Simples ciclo");
  printf("Simples ciclo");
  printf("Simples ciclo");
  printf("Simples ciclo");
  printf("Simples ciclo");
}

fiz isto para 5, mas penso que nesta situação ainda poderia fazer para mais, embora para cálculos numéricos (em máquinas com arquitectura IA32) normalmente não dê para mais de 4 devido aos poucos registos disponíveis nessa arquitectura.

no exemplo que deste nem vale a pena optimizar introduzir programação concorrente, mas fiz uma experiência para o programa

for(i=0;i<100000;i++)
  puts("xpto");

para o qual fiz as seguinte optimizações

pid_t pid;
pid=fork();

if(!pid)
{
  for(i=0;i<50000;i+=4)
  {
    puts("xpto");
    puts("xpto");
    puts("xpto");
    puts("xpto");
  }
}
else
{
  for(i=50000;i<100000;i+=4)
  {
    puts("xpto");
    puts("xpto");
    puts("xpto");
    puts("xpto");
  }

  wait(NULL);
}

enquanto que a versão não optimizada executava em 2 ou 3s, a optimizada executou quase sempre em 1s, e ocasionalmente em 2s. não sei como medir os tempos de execução de forma mais precisa, mas penso que já dá para ter uma ideia da diferença.

EDIT: neste último programa apenas criei dois processos pois o meu computador apenas tem um processador, para que tem dual core's penso que obteria melhor desempenho com mais algum processo.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ok, essas são optimizações válidas e chegaste ao ponto que eu queria, não retiraste os ciclos 'for' nem fizeste a optimização mais simples de todas: inverter o ciclo! Mas não queria ensinar optimizações, isso sei que consegues fazer mas repara... O compilador de C "vê" o teu ciclo for e vai passá-lo para assembly e vai optimizar esse mesmo ciclo. Agora distribuiste o ciclo e dividiste o número de operações que são necessárias, optimo, mas mesmo assim o compilador de C agarrava nessa optimização e optimizava mais.

Pegando no exemplo, e para dar algo de concreto, o compilador de Delphi, quando tem as flags de optimização ligadas, inverte todos so ciclos que não levem a comparações com zero, no nosso caso o compilador ia inverter o ciclo fazendo com que a variável tivesse inicio no valor 15 e fosse decrementada por cada iteração. Está certo, esta também o programador pode fazer, mas este é apenas um exemplo, cada compilador optimiza o código que gera. Por mais voltas que dês ao código o compilador terá sempre de passar as tuas instruções para assembly e vai sempre analizar e, caso seja necessário, optimizar o assembley gerado.

Uma forma de veres isto a funcionar é compilares o teu código sem flags de optimização e com flags e analizares o assembley que resulta. No caso do compilador da Borland o assembly parece esparguete :P, no caso do compilador da sun, embora o código também seja um pouco estranho, as optimizações são de notar e fazem-se notar quando executas bechmarks.

Espero que entedas que não me refiro ao código que tu fazes em C/C++ mas sim ao que é gerado pelo compilador.

Em relação aos bechmarks, medir execuções de programas é bastante complicado. Tenho alguma experiência em fazer isso em Java vs C e é um verdadeiro inferno.

Peace.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Em linux medes facilmente o tempo de execução de um programa usando a instrução "time".

"time ./teste"

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Em linux medes facilmente o tempo de execução de um programa usando a instrução "time".

"time ./teste"

Boa, não conhecia.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Knitter, o artigo tentou transmitir a ideia de que o C/C++ em certos casos não é eficiente, pois o compilador de C/C++ não fazia certas optimizações que outros compiladores podem fazer.

o que eu tentei dizer é que isso acontece quando o código que escrevemos não está tão optimizado quanto poderia estar se usassemos os recursos todos que a linguagem nos disponibiliza.

tu falaste no caso de inverter o ciclo, que é um optimização feita pelo compilador de Delphi, mas isto só é uma vantagem para o Delphi se tu não fizeres a inversão no ciclo no código que escreveste, caso contrário o código C será tão eficiente como o Delphi.

por isso, do meu ponto de vista, o artigo é que é falacioso e não a eficiência do C/C++, pois embora para determinados "códigos" outras linguagens podem ser mais eficientes do que o C/C++, podemos rearranjar o código em C/C++ de forma a que produza o mesmo resultado e de forma tão ou mais eficiente.

não coloco em causa aquilo que tu tens dito relativamente às possibilidades de optimização que são melhores nos compiladores de outras linguagens que não o C. mas não podemos comparar a eficiência das linguagens apenas pela capacidade de optimização do compilador, é necessário ter também em contas as optimizações que as linguagens nos permitem fazer ao escrevermos o código. o artigo fez a comparação entre linguagens e não entre compiladores.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O C é verdadeiramente mais rápido.

Em concursos, é dado mais 1.5x o tempo aos programadores de JAVA do que em C, isto porque java é 2x mais lento. (os outros 0.5 vão para compensar a facilidade do JAVA a lidar com big integers e outras estruturas, que em C têm que ser programados manualmente)

Chega a ser 4x mais rapido que Pascal com o mesmo algoritmo.

Só um outro aparte, se quiserem comparar velocidades a realizar determinado processamento, comparem linguagens com o mesmo paradigma. Já JAVA vs C é puxado, colocar linguagens como LISP no meio parece-me enormemente desnecessário. São linguagens para fins distintos.

Era o mesmo que dizer que é mais fácil realizar-se cálculos no MathLab do que em C..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora