Get best of the week

Explication: pourquoi le wc sur Haskell s'est avéré «plus rapide» que l'analogue sur C


Après des articles récents ( n ° 10xd34df00d, №2chapuza, №3picul) en comparant la vitesse des implémentations de l'utilitaire wc simplifié , je n'avais qu'une seule question - Comment une implémentation simple dans Haskell s'est-elle avérée plus rapide qu'une implémentation simple en C ?!


2020-02-27 : Les résultats et conclusions pourghc 8.8.3et sur les textes de Shakespeare sont confirmés(à la fin sous le spoiler).


Rappelez brièvement les savoirs traditionnels


Pour un fichier texte de 1,8 Go (1_871_822_210 octets), vous devez compter le nombre de lignes, de mots et de caractères. Avec un certain nombre de simplifications: seulement codage de caractères 8 bits, fin de lignes uniquement dans le style Unix, les limites des mots sont des espaces et tous les caractères sont moins Char(14), lisant uniquement à partir d'un fichier (le mappage vers la mémoire est acceptable).


Exemples de données de test

Region,Country,Item Type,Sales Channel,Order Priority,Order Date,Order ID,Ship Date,Units Sold,Unit Price,Unit Cost,Total Revenue,Total Cost,Total Profit
Sub-Saharan Africa,South Africa,Fruits,Offline,M,7/27/2012,443368995,7/28/2012,1593,9.33,6.92,14862.69,11023.56,3839.13
Middle East and North Africa,Morocco,Clothes,Online,M,9/14/2013,667593514,10/19/2013,4611,109.28,35.84,503890.08,165258.24,338631.84
Australia and Oceania,Papua New Guinea,Meat,Offline,M,5/15/2015,940995585,6/4/2015,360,421.89,364.69,151880.40,131288.40,20592.00
Sub-Saharan Africa,Djibouti,Clothes,Offline,H,5/17/2017,880811536,7/2/2017,562,109.28,35.84,61415.36,20142.08,41273.28
Europe,Slovakia,Beverages,Offline,L,10/26/2016,174590194,12/4/2016,3973,47.45,31.79,188518.85,126301.67,62217.18
Asia,Sri Lanka,Fruits,Online,L,11/7/2011,830192887,12/18/2011,1379,9.33,6.92,12866.07,9542.68,3323.39
Sub-Saharan Africa,Seychelles ,Beverages,Online,M,1/18/2013,425793445,2/16/2013,597,47.45,31.79,28327.65,18978.63,9349.02
Sub-Saharan Africa,Tanzania,Beverages,Online,L,11/30/2016,659878194,1/16/2017,1476,47.45,31.79,70036.20,46922.04,23114.16
Sub-Saharan Africa,Ghana,Office Supplies,Online,L,3/23/2017,601245963,4/15/2017,896,651.21,524.96,583484.16,470364.16,113120.00
Sub-Saharan Africa,Tanzania,Cosmetics,Offline,L,5/23/2016,739008080,5/24/2016,7768,437.20,263.33,3396169.60,2045547.44,1350622.16
Asia,Taiwan,Fruits,Offline,M,2/9/2014,732588374,2/23/2014,8034,9.33,6.92,74957.22,55595.28,19361.94
Middle East and North Africa,Algeria,Cosmetics,Online,M,2/18/2011,761723172,2/24/2011,9669,437.20,263.33,4227286.80,2546137.77,1681149.03
Asia,Singapore,Snacks,Online,C,1/28/2013,176461303,2/7/2013,7676,152.58,97.44,1171204.08,747949.44,423254.64
Australia and Oceania,Papua New Guinea,Clothes,Offline,L,6/20/2011,647164094,7/14/2011,9092,109.28,35.84,993573.76,325857.28,667716.48
Asia,Vietnam,Personal Care,Online,M,4/4/2010,314505374,5/6/2010,7984,81.73,56.67,652532.32,452453.28,200079.04
Sub-Saharan Africa,Uganda,Personal Care,Online,M,6/19/2014,539471471,7/21/2014,451,81.73,56.67,36860.23,25558.17,11302.06
Sub-Saharan Africa,Zimbabwe,Office Supplies,Offline,C,3/28/2011,953361213,4/8/2011,9623,651.21,524.96,6266593.83,5051690.08,1214903.75
Sub-Saharan Africa,Ethiopia,Cosmetics,Online,M,7/7/2011,807785928,7/25/2011,662,437.20,263.33,289426.40,174324.46,115101.94
Europe,France,Cosmetics,Online,M,12/7/2015,324669444,1/18/2016,5758,437.20,263.33,2517397.60,1516254.14,1001143.46


Résultats précédents


"" , . i7-4600U CPU @ 2.10GHz. — . , /dev/shm/ (tmpfs).


" ", Haskell- ( , CPU):


wc-19.416
Haskellghc 8.0.2, -O22.811
gcc 8, -Ofast3.067
gcc 8, -Ofast0.637

, () - Haskell. - "". ghc (2.811 < 3.067), Haskell 2:3 Haskell. .


, . , AVX2:


Haskellghc 8.0.2, -O2 -mavx22,789
gcc 8, -Ofast -march=haswell2.914
clang 8, -Ofast -march=haswell1.124
gcc 8, -Ofast -march=haswell0.634
AVX2gcc 8, -Ofast -march=haswell0.269

, AVX2 Haskell, clang ( CompilerExplorer), . , AVX2 .


- Haskell


. , .


, -ddump-asm. wc.hs 24 . - , grep cmp : cmpq $33,%rbx; cmpq $32,%rbx; cmpq $10,%rbx; cmpb $4,%bl. .


- . C:


static _Bool process_chunk(const unsigned char *text, const size_t bytes,
                           _Bool prev) {
  result.chars += bytes;
  for (size_t i = 0; i < bytes;) {
    if (text[i] > ' ') {
      // -  ""
      result.words += !prev;
      prev = 1;
      while (++i < bytes && text[i] > ' ')
        ;
    } else {
      // -  
      prev = 0;
      do {
        _Bool non_space = text[i] != ' ' && text[i] - 9 > 4;
        result.words += !prev && non_space;
        result.lines += text[i] == '\n';
        prev = non_space;
      }
      while (++i < bytes && text[i] <= ' ');
    }
  }
  return prev;
}

Haskell-, . , "" :


Haskellgcc 8, -Ofast1.331
Haskellghc 8.0.2, -O22.811
gcc 8, -Ofast3.067
gcc 8, -Ofast0.637

"" Haskell- , ! , , ghc .


Haskell C, ( ):


  • ghc decision tree , . -: " " " ".
  • - " " , -. , , "" 1.8 ;)
  • , . , "" - ( ). — .

, 1871822210 / 44774631 = 41.8 , 44774631 / 15000000 = 2.98 .
-. - , . ?


1.8 (3068561 * 610 = 1871822210):


$ dd if=/dev/urandom of=/dev/shm/rand.dat bs=3068561 count=610

, " " , "" . 1871822210 / 210195110 = 8.9, . , "" . , "" 41 . "" :


Haskellgcc 8, -Ofast1.331 => 3.532
Haskellghc 8.0.2, -O22.811 => 4.812
gcc 8, -Ofast3.062 => 3.071

- — . , C. .


Haskell "" , . , , C - ;)


ghc 8.8.3 (2020-02-27)

:


  1. - LLVM.
  2. gcc clang.
  3. , .
  4. , "" Haskell () .
  5. wc .

. i7-7820HQ CPU @ 2.90GHz 64- Fedora 31.


5_777_367 . " " 1.8:


$ wget http://www.gutenberg.org/files/100/100-0.txt
$ for i in `seq 1 333`; do cat 100-0.txt >> test.txt; done

1_923_863_211 . C :


wc-12.687
Haskellgcc 9.2.1, -Ofast4.947
Haskellclang 9.0.1, -Ofast4.689
Haskellghc 8.8.3, -O36.339 (!)
Haskellghc 8.8.3, -O3 -fllvm4.893 (!)
gcc 9.2.1, -Ofast2.445
clang 9.0.1, -Ofast2.347

/dev/urandom 1_871_822_210 :


wc-16.878
Haskellgcc 9.2.1, -Ofast3.322
Haskellclang 9.0.1, -Ofast3.344
Haskellghc 8.8.3, -O33.976
Haskellghc 8.8.3, -O3 -fllvm2.513
gcc 9.2.1, -Ofast2.376
clang 9.0.1, -Ofast2.244

ghc 8.8.3 8.0.2, LLVM ( 9.0.1) . , C - , . " " /dev/urandom, .


, 0xd34df00d, Haskell . , .


, , .


!

: "" "" C ( ), : "" . , zero cost abstraction , zero cost abstraction .

More articles:


All Articles