July 3rd, 2008

Book

Необходимость инлайна

Снова классический пример (Haskell). Я определил тип списка явно, чтобы было понятно, что Хаскелевские встроенные списки - это обычные алгебраические типы, просто с хитро названными CONS, LIST и NIL:
data LIST a = CONS a (LIST a) | NIL
 
prodx NIL a = a
prodx (CONS x xs) a = prodx xs (a * x)
Т.к. в HN0 нет ни ADT, ни pattern matching, то реализацией prodx будет
prodx x a = fold * a x
Collapse )
Таким образом, после инлайнинга и вывода типов при буквальной трансляции в C++ получаем вполне приличный код:
int prodx(const list<int> & l, int a) 
{
   while (not isNil(l)) 
   {
       a = a * head(l);
       l = tail(l);
   }
   return a;
}
Book

Aльтернативы HN: Glasgow Haskell Compiler

При компиляции prodx с помощью MSVC 2005 x64 SP1 выходит следующее (полноценные связные списки):
 prodx@hn0@@YAHU?$list@H@1@H@Z (int __cdecl hn0::prodx(struct hn0::list<int>,int)):
  0000000000000000: 48 85 C9           test        rcx,rcx
  0000000000000003: 74 17              je          000000000000001C
  0000000000000005: 66 66 66 90        xchg        ax,ax
  0000000000000009: 66 66 90           xchg        ax,ax
  000000000000000C: 66 66 66 90        xchg        ax,ax
  0000000000000010: 0F AF 11           imul        edx,dword ptr [rcx]
  0000000000000013: 48 8B 49 08        mov         rcx,qword ptr [rcx+8]
  0000000000000017: 48 85 C9           test        rcx,rcx
  000000000000001A: 75 F4              jne         0000000000000010
  000000000000001C: 8B C2              mov         eax,edx
  000000000000001E: C3                 ret
Collapse )

Самое лучшее, что удалось получить при тщательных аннотациях "strict" (!) и "unboxed" (#) c GHC 6.8:
  70:   89 f0                   mov    %esi,%eax
  72:   83 e0 03                and    $0x3,%eax
  75:   83 f8 02                cmp    $0x2,%eax
  78:   73 12                   jae    8c <_s8a_info+0x1c>
  7a:   8b 45 04                mov    0x4(%ebp),%eax
  7d:   0f af 46 07             imul   0x7(%esi),%eax
  81:   89 45 04                mov    %eax,0x4(%ebp)
  84:   8b 46 03                mov    0x3(%esi),%eax
  87:   89 45 00                mov    %eax,0x0(%ebp)
  8a:   eb 18                   jmp    a4 <_M_sumx_info>
  8c:   8b 75 04                mov    0x4(%ebp),%esi
  8f:   83 c5 08                add    $0x8,%ebp
  92:   ff 65 00                jmp    *0x0(%ebp)
 000000a4 <_M_sumx_info>:
  a4:   8b 75 00                mov    0x0(%ebp),%esi
  a7:   c7 45 00 70 00 00 00    movl   $0x70,0x0(%ebp)
  ae:   f7 c6 03 00 00 00       test   $0x3,%esi
  b4:   75 ba                   jne    70 <_s8a_info>
  b6:   ff 26                   jmp    *(%esi)
Book

Альтернативы HN0: Clean

Максимально эффективный код prodx на Clean по качеству совпадает с сишным:
00000000 :
   0:   81 39 02 00 00 00       cmpl   $0x2,(%ecx)
   6:   75 01                   jne    9 <e__M__ssumx+0x9>
   8:   c3                      ret    
   9:   0f af 41 08             imul   0x8(%ecx),%eax
   d:   8b 49 04                mov    0x4(%ecx),%ecx
  10:   eb ee                   jmp    0 <e__M__ssumx>
Clean даже поддерживает Win64, но, к сожалению, у него недоразвит FFI и активной разработкой он не блещет.
Book

Альтернативы HN: OCAML

В OCAML, к счастью, не нужно париться с аннотациями, он стабильный, активно разрабатывается, есть под Win64 и даже интегрируется с MSVC 2005 x64. Но вот что получается в коде:
00000000 <_camlM__code_begin>:
   0:   89 c1                   mov    %eax,%ecx
   2:   83 f9 01                cmp    $0x1,%ecx
   5:   74 19                   je     20 <_camlM__code_begin+0x20>
   7:   8b 11                   mov    (%ecx),%edx
   9:   d1 fa                   sar    %edx
   b:   4b                      dec    %ebx
   c:   0f af da                imul   %edx,%ebx
   f:   43                      inc    %ebx
  10:   8b 41 04                mov    0x4(%ecx),%eax
  13:   eb eb                   jmp    0 <_camlM__code_begin>
  15:   8d 74 26 00             lea    0x0(%esi,%eiz,1),%esi
  19:   8d bc 27 00 00 00 00    lea    0x0(%edi,%eiz,1),%edi
  20:   89 d8                   mov    %ebx,%eax
  22:   c3                      ret
Последние 4 инструкции, само собой, несущественны. Генератор кода отличный, но цикл все равно в 10 инструкций вместо 5 за счет меченых целых чисел, необходимых камловскому сборщику мусора. Эти же меченые данные усложняют обмен данными с C++, но обнадеживает, что за счет этих меток сборщик мусора (по идее, не тестировал что они намутили в реализации) значительно быстрее и точнее консервативного Boehm GC.

В целом, OCAML очень близок к тому, что мне нужно - бесит, в основном, толстый маршаллинг и кривой, по сравнению с хаскеллевско-клиновским, синтаксис.
Book

Двухминутка ненависти

Функциональные языки окружены неким ореолом славы. Дескать, благодаря чистоте возможно выполнять архисложные оптимизации, благодаря которым можно писать код левой ногой, а компилятор как-нибудь соптимизирует в tight loop. Вот и сегодня наткнулся на такой радостный пассаж в 8.2. Unboxed types and primitive operations:
GHC is built on a raft of primitive data types and operations. While you really can use this stuff to write fast code, we generally find it a lot less painful, and more satisfying in the long run, to use higher-level language features and libraries. With any luck, the code you write will be optimised to the efficient unboxed version in any case. And if it isn't, we'd like to know about it.
Выглядит так, как будто можно забыть о деталях и довериться компилятору. Хрен вам! Вот мой любимый prodx в своей наивной ипостаси:
module Main where

prodx a b = foldl (*) b a

main = print $ prodx [2..4] 5
Казалось бы, должно фьюзиться, и компилироваться в нечто такое:
int a = 5;
for (int i = 2; i <= 4; i ++)
{
   a *= i;
}

printf("%d\n", a);
Казалось бы, цикл из 3-4 инструкций, а то и просто вычисленная на этапе компиляции константа. Но не тут-то было! Авторы Хаскеля нашли миллион вполне легитимных причин, по которым эти 2 строчки должны компилироваться в хуйню.

Для начала 3 загадки фанатам Хаскеля:
  1. Какой тип имеет [2..4]?
  2. Фьюзится ли foldl и [2..4] и почему?
  3. Почему main = print $ foldr (+) 1 [1..1000000] приводит к stack overflow?