Get best of the week

التفسير: لماذا تبين أن المرحاض على هاسكل "أسرع" من التماثلية على C


بعد المقالات الأخيرة ( رقم 10xd34df00d، №2تشابوزا، №3بيكول) مقارنة بين سرعة تنفيذ الأداة المساعدة المبسطة للحمام ، كان لدي سؤال واحد فقط - كيف تبين أن التنفيذ البسيط في هاسكل أصبح أسرع من التنفيذ البسيط في لغة سي ؟


2020-02-27 : تم تأكيد النتائج والاستنتاجاتghc 8.8.3ونصوص شكسبير (في النهاية تحت المفسد).


أذكر باختصار المعارف التقليدية


لملف نصي بحجم 1.8 غيغابايت (1_871_822_210 بايت) ، تحتاج إلى حساب عدد الأسطر والكلمات والأحرف. مع عدد من التبسيط: ترميز الأحرف 8 بت فقط ، نهاية الأسطر فقط في نمط Unix ، حدود الكلمات هي مسافات وجميع الأحرف أقل Char(14)، القراءة فقط من ملف (تعيين الذاكرة مقبول).


عينة بيانات الاختبار

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


النتائج السابقة


"" , . 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