http://ache.vniz.net/demos.html охуительная история:

Своеобразный программисткий подвиг совершил Дима Бурков. В то время начали появляться первые PC. Unix на них выглядел неубедительно. Linux еще не появился, зато повился Venix. Хачить его было невозможно - не было исходных текстов ядра. Дима Бурков реассемблировал ядро, потом писал программы на Си, которые давали тот же текст ассемблера - так появились тексты ядра на Си ... работа не для слабонервных.

Проверял GCC на предмет того, как он умеет рекурсию оптимизировать.
Вот такая штука

unsigned int plus(unsigned int a, unsigned int b)
{
  if (b == 0) return a;
  return plus (a+1, b-1);
}

Относительно успешно сворачивается сложение. Получается такая шняга:

movl %edi, %eax
addl %esi, %eax
ret

Хотя в идеале можно было бы обойтись

leal (%rsi,%rdi), %eax
ret

Что касается умножения, там ситуация более печальная

inline unsigned long int product_0(const unsigned int a, const unsigned int b, const unsigned long int tmp)
{
  if (b == 0) return tmp;
  return product_0(a, b-1, tmp+a);
}

unsigned long int product(const unsigned int a, const unsigned int b)
{
  return product_0(a, b, 0);
}

В ассемблере получается такая фигня

product:
.LFB34:
.cfi_startproc
    xorl %eax, %eax
    testl %esi, %esi
    je .L7
    leal -1(%rsi), %eax
    mov %edi, %edi
    addq $1, %rax
    imulq %rdi, %rax
.L7:
    rep
    ret
.cfi_endproc

Тут оно зачем-то зануляет значение регистра, в котором хранится возврашемое из функции значение и сравнивает с нулем значение регистра, в котором в функцию передается число. Если ноль то прыгаем в конец функции, возвращая 0. Тогда внезапно появляется смысл в этом rep ret http://repzret.org/p/repzret/

Why? Because “The processor is unable to apply a branch prediction to the single-byte near-return form (opcode C3h) of the ret instruction.” Thus, “Use of a two-byte near-return can improve performance”, because it is not affected by this shortcoming.

Ну а дальше через leal из регистра rsi число копируется в eax, уменьшаясь при этом на 1 (нахрена?) и потом из регистра edi двигается в edi (НАХРЕНА??), увеличиваем rax на 1 через addq (ну тут понятно зачем, перед этим ведь оно было непонятно зачем уменьшено на 1, но нахрена уменьшать и потом увеличивать? И вообще, для увеличения на 1 лучше incq использовать) ну и в итоге компилятор таки вставляет инструкцию imulq. Распознать умножение в этой рекурсивной хрени компилятор смог, но при этом как-то через жопу все, нагенерировал кучу говна всякого. Можно было намного проще сделать

movl %esi, %eax
imull %edi, %eax

gcc version 4.5.1 если что

http://ideone.com/NlMluL
Умножение двух 16-битных беззнаковых чисел с получением 32-битного беззнакового, без условных переходов

https://research.microsoft.com/en-us/um/people/simonpj/papers/ndp/haskell-beats-C.pdf

Abstract
Stream fusion [6] is a powerful technique for automatically transforming high-level sequence-processing functions into efficient implementations. It has been used to great effect in Haskell libraries for manipulating byte arrays, Unicode text, and unboxed vectors. However, some operations, like vector append, still do not perform well within the standard stream fusion framework. Others, like SIMD computation using the SSE and AVX instructions available on modern x86 chips, do not seem to fit in the framework at all.
In this paper we introduce generalized stream fusion, which solves these issues. The key insight is to bundle together multiple stream representations, each tuned for a particular class of stream consumer. We also describe a stream representation suited for ef ficient computation with SSE instructions. Our ideas are implemented in modified versions of the GHC compiler and vector library. Benchmarks show that high-level Haskell code written using our compiler and libraries can produce code that is faster than both compiler- and hand-vectorized C.

На ассемблере такие вещи надо делать. Алсо, тут http://benchmarksgame.alioth.debian.org/u64q/benchmark.php?test=all&lang=gcc&lang2=ghc&data=u64q хаскель сливает сишке почти по всем пунктам. И я бы не сказал, что кода на х-е сильно меньше, чем кода на Си

http://gcc.1065356.n5.nabble.com/Ways-to-fill-the-stack-td912561.html#none
Если через запятую объявлять члены массива из char в C и откомпилить это в GCC, оно это запишет как куча mov-ов по байтику
sztfg - я