let rec qsort array = match array with 
     []              -> []
     | pivot::rest   -> let left,right = List.partition (function x -> x < pivot) rest
                        in (qsort left) @ pivot::(qsort right);;

V>Считаю, что подбная оптимизация — это вообще оптимизация 0-го уровня.

Write this to int.ml:

print_int 3;;

and compile with ocamlopt -S int.ml -o int to generate assembly language in int.s. Recall from the discussion above that we are expecting OCaml to inline the print_int function as output_string (string_of_int 3), and examining the assembly language output we can see that this is exactly what OCaml does:

        .text
        .globl  Int__entry
Int__entry:

        ; Call Pervasives.string_of_int (3)

        movl    $7, %eax
        call    Pervasives__string_of_int_152

        ; Call Pervasives.output_string (stdout, result_of_previous)

        movl    %eax, %ebx
        movl    Pervasives + 92, %eax
        call    Pervasives__output_string_212

The important code is shown in red. It shows two things: Firstly the integer is unboxed (not allocated on the heap), but is instead passed directly to the function in the register %eax. This is fast. But secondly we see that the number being passed is 7, not 3.

This is a consequence of the representation of integers in OCaml. The bottom bit of the integer is used as a tag — we'll see what for next. The top 31 bits are the actual integer. The binary representation of 7 is 111, so the bottom tag bit is 1 and the top 31 bits form the number 11 in binary = 3. To get from the OCaml representation to the integer, divide by two and round down.

Why the tag bit at all? This bit is used to distinguish between integers and pointers to structures on the heap, and the distinction is only necessary if we are calling a polymorphic function. In the case above, where we are calling string_of_int, the argument can only ever be an int and so the tag bit would never be consulted. Nevertheless, to avoid having two internal representations for integers, all integers in OCaml carry around the tag bit.

GN>>ocalmopt                                        MSVC 8 
GN>>(Microsoft-based native Win32 port  3.09.0)     (14.00.50727.42 for 80x86)

GN>>30,60 сек                                       18,54 сек
GN>>30,69 сек                                       18,54 сек
GN>>30,59 сек                                       18,55 сек

Вне конкурса проходит тот же MSVC с ключиком /clr
Время выполнения ~ 28-29 сек.