>> Во-первых, говоря о стеке процессора, ты забыл про пересылку данных.
> "стеке процессора"? Что за странное словосочетание?

Обычное название для стека, который адресуется регистром процессора (RSP в случае AMD64).

> Ты хочешь сказать, что ocaml использует
> два стека?

Да, именно о том я и писал выше.

> Один для нужд рантайма и параллельный стек для собственно
> программы? Да ладно, не может быть.

    Instruct(PUSH): Instruct(PUSHACC0):
      *--sp = accu; Next;
    Instruct(PUSHACC1):
      *--sp = accu; accu = sp[1]; Next;
    Instruct(PUSHACC2):
      *--sp = accu; accu = sp[2]; Next;
    Instruct(PUSHACC3):
      *--sp = accu; accu = sp[3]; Next;
    Instruct(PUSHACC4):
      *--sp = accu; accu = sp[4]; Next;
    Instruct(PUSHACC5):
      *--sp = accu; accu = sp[5]; Next;
    Instruct(PUSHACC6):
      *--sp = accu; accu = sp[6]; Next;
    Instruct(PUSHACC7):
      *--sp = accu; accu = sp[7]; Next;

> И да, о какой пересылке речь?

Пересылка данных из сохраняемого регистра в память (и наоборот).

>> Во-вторых, для своего стека OCaml по очевидным причинам не может использовать стековые
>> инструкции; кроме того, проверяет выход за пределы выделенного блока, при необходимости
>> переаллоцируя весь "стек".
> Большую часть этих проверок можно делать статически. Или даже все эти проверки
> можно выполнять статически. Но тут уже от языка зависит, скажем от
> того, позволяет ли он выделять со стека куски памяти динамического размера,
> и используется ли при этом рекурсия, глубину которой компилятор просчитать не
> в состоянии.

/* Stack checks */
    check_stacks:
      if (sp < caml_stack_threshold) {
        caml_extern_sp = sp;
        caml_realloc_stack(Stack_threshold / sizeof(value));
        sp = caml_extern_sp;
      }
      /* Fall through CHECK_SIGNALS */

>> переаллоцируя весь "стек".
> Ну, вообще, на мой взгляд, переаллокация стека -- это в любом случае
> плохо, и если на это идёт заточка, то переаллокации должны происходить
> только в сторону увеличения, чтобы их было бы немного за всё
> время выполнения программы. А вообще, я бы просто выкидывал исключение --
> за стеком надо следить, и если его мало, то надо заранее
> заказать побольше.

Так и сделано. Лимит можно задать перед выполнением.

> Вообще мне странны твои слова, в том смысле, что я в Common
> Lisp'е постоянно выделял на стеке, и я был уверен в том,
> что стоимость этого выделения в большинстве ситуаций O(1) -- то есть
> проверка на переполнение и сложение. Что там sbcl делал в случае
> переполнения, я не задумывался никогда.

В OCaml на уровне языка отсутствует понятие "выделить на стеке". В случае ocamlopt целые числа могут быть аллоцированы в регистрах процессора, за что приходится платить проверкой младшего бита (что бы отличать их от boxed) и суженным вдвое диапазоном возможных значений. Кстати, в MLton эти проблемы решены, как и бесшовное взаимодействие с С.

С другой стороны, даже несмотря на простор для низкоуровневых оптимизаций, OCaml действительно в ряде случаев конкурирует с C, значит выигрыш достигается за счёт простоты реализации сложных алгоритмов и компетенции разработчиков.