頭の悪い最適化してるつもりのコード

OCamlが遅くなる一番の原因はGCらしいです。某.NETや某JavaみたいにGCが他のアプリケーション用のメモリを食い潰すような実装にはなっていない良心的なGCらしいことは評価していいと思いますが具体的にどうなのかはさっぱり知りません。
↑のコードでは、いちいち_iとか用意してますが、int32はBoxing型のためにof_intする度にメモリ割り当てが行われて嫌な感じなので、UTF32でも所詮有効なのは31ビットなので、(負値があるので大小比較はできませんが)ビット演算だけでやる分にはintで事足りますのでint32回避のために分けてあります。
タプル使わずに、thenで代入してint値を返すようなことをやってますが、これもタプルがメモリ割り当てを必要とするからです。
参照は、代入する分にはメモリ割り当ては不要です。refで新しく作るときはメモリ割り当てが必要です。スコープ内の使用で外に持ち出されない時ぐらいスタックに割り当てられてもいいんじゃないかと思うのですがそんなことはありません。
ループ用の関数内関数に、使う値全部引数で渡しているのも、そうしないとカリー化(違いますクロージャあたりの呼称が正しいですが-Sで出てくるラベルがそうなので)が起きてしまってまた大きなロスが発生するからです。関数型記法効率悪いです。
大体、-Sしたのを見る限り、効率的そうな順にこーなります。

使用する引数(ただしレジスタに載る4個以内とかその辺)を全部渡して末尾再帰
forやwhile、ただしrefはあんまり使わないこと
(壁)
カリー化もといクロージャを駆使したOCamlらしいとされるコード

本当にそうかはプロファイル取って時間測った方がいいと思いますがWindowsでは素晴らしいことに-pが動かないのでそんなことはせずに笑って済ませられます。はっはっはー。