الفوز بعشرين خطًا هاسكل: كتابة مرحاض

مرحبا يا هابر.

اليوم الآخر سيمارجلدعاني لترجمة مقالة غريبة عن الانتصار على يونكس wcبمساعدة هاسكل. بالطبع ، لن أترجمها ، ولعدة أسباب:

• قام المؤلف بطرد النسخة ذات الخيوط الفردية بأي حال من الأحوال ، وكانت النسخة ذات الخيوط الفردية أبطأ بكثير wc،
• في هذه المقالة ، من أجل الفوز ، كان من الضروري استخدام مؤشرات متعددة (والتي هي في حد ذاتها جزء من الغش والنصر بدلاً من الحس السليم وليس أكثر wc) ،
• لهذا ، كان على المؤلف الخوض في تريكوmonads و monoids - لا ، هذا توضيح ممتاز لسحر التفكير الأحادي ، لكن IMHO كثيرًا جدًا لمثل هذه المهمة ، خاصة لأنه بسبب هذا
• تبين أن الرمز كبير جدًا ،
• وبالفعل ، للتنافس معها wc، والتي تحتوي على مجموعة من الخيارات والميزات ، تدرك أنها لعبة تناظرية للغاية ، بشكل عام أنها غريبة نوعًا ما وحتى غبية قليلاً.

ومع ذلك ، فإن القيام بأشياء غريبة أمر جيد ، لذلك سنحاول اليوم إصلاح أول النقاط أعلاه وتحسين نتيجة Chris (اسم مؤلف المقالة الأصلية).

مرة أخرى ، كما اكتشفنا في المرة الأخيرة ، لا يمكنني كتابة رمز C ، لذلك لن أكتبه أيضًا ، wcوبصفتي منافسًا لتنفيذ Haskell ، لدي (مثل كريس) نظام GNU Coreutils. يعرف هؤلاء الرجال بالتأكيد كيفية الكتابة في لغة C ، وهذا الرمز ليس عمره عشر سنوات ، وقد اهتموا بالأداء ، بالحكم على هذه القطع:

/* If the average line length in the block is >= 15, then use
   memchr for the next block, where system specific optimizations
   may outweigh function call overhead.
   FIXME: This line length was determined in 2015, on both
   x86_64 and ppc64, but it's worth re-evaluating in future with
   newer compilers, CPUs, or memchr() implementations etc.  */

Spoiler: سنفوق النظام wcبحوالي حجم دون أي مشاكل ، بعد أن تلقينا رمزًا اصطلاحيًا تمامًا وننفق أقل من نصف ساعة على تغيير وتحسين الشفرة الأصلية.

شروط التجربة

لذا ، نناقش أولاً الإعداد التجريبي.

البيانات

لقد قمت بتنزيل هذا الملف ولصقه معي ، لذا يبلغ الحجم الإجمالي حوالي 1.8 غيغابايت:

% for i in `seq 1 10`; cat part.txt >> test.txt
% du -sh test.txt
1.8G    test.txt

, test.txt tmpfs-, , IO.

Gentoo Linux Core i7 4770 32 .

- ghc 8.8.2.

wc coreutils 8.31, gcc 9.2 -O2 -march=native:

% wc --version
wc (GNU coreutils) 8.31
Packaged by Gentoo (8.31-r1 (p0))

, -march=native — C, - - , : x86_64-, wc coreutils ( SIMD-, ).

, -O3 -O2 — , -O2.

, time. time , , ,

1. 0.3 ,
2. , , .

, ( ) , .

? wc!

Unicode ( ), C-, wc LANG=C LC_ALL=C wc /path/to/test.txt. ? 10.4 . .

, (ru_RU.UTF-8) wc (7.20 ), , , , C- — , .

, ( ), 0.2 — , IO-bound-.

Haskell

, ?

, cs bs ( , ):

import qualified Data.ByteString.Lazy.Char8 as BS
import Data.Char

wc :: BS.ByteString -> (Int, Int, Int)
wc s =
    let (bs, ws, ls, _) = BS.foldl' go (0, 0, 0, False) s
     in (bs, ws, ls)
  where
    go :: (Int, Int, Int, Bool) -> Char -> (Int, Int, Int, Bool)
    go (!bs, !ws, !ls, !wasSpace) c =
        let addLine | c == '\n' = 1
                    | otherwise = 0
            addWord | wasSpace = 0
                    | isSpace c = 1
                    | otherwise = 0
         in (bs + 1, ws + addWord, ls + addLine, isSpace c)

, , ( ).

, , 9 wc. : 31.2 , 306% wc. 9 , , .

, ( , ), , , , .

?

-, , — . :

{-# LANGUAGE Strict #-}
{-# LANGUAGE RecordWildCards #-}

import qualified Data.ByteString.Lazy.Char8 as BS
import Data.Char

data State = State
  { bs :: Int
  , ws :: Int
  , ls :: Int
  , wasSpace :: Bool
  }

wc :: BS.ByteString -> (Int, Int, Int)
wc s = (bs, ws, ls)
  where
    State { .. } = BS.foldl' go (State 0 0 0 False) s

    go State { .. } c = State (bs + 1) (ws + addWord) (ls + addLine) (isSpace c)
      where
        addLine | c == '\n' = 1
                | otherwise = 0
        addWord | wasSpace = 0
                | isSpace c = 1
                | otherwise = 0

bang-, - {-# LANGUAGE Strict #-}. , ?

, , — 4 ! 7.56 , 75% wc, ! ?

, : , , . -

data State = State
  { bs :: {-# UNPACK #-} !Int
  , ws :: {-# UNPACK #-} !Int
  , ls :: {-# UNPACK #-} !Int
  , wasSpace :: !Bool
  }

Int- . , nursery area, , , — , .

CSE

, isSpace c , — . , , go :

    go State { .. } c = State (bs + 1) (ws + addWord) (ls + addLine) isSp
      where
        isSp = isSpace c
        addLine | c == '\n' = 1
                | otherwise = 0
        addWord | wasSpace = 0
                | isSp = 1
                | otherwise = 0

? — 2.93 , 28% wc.

? ghc , , ? — isSpace ( ) , common subexpression elimination.

— ( ). , wc , . - , :

1. LLVM- ( -fllvm) — , .
2. ( -O2) — -O , -O2 , ?
3. ( {-# INLINE wc #-}). , - , , , - . , , , .

, , , .

:

. -, . , -O2 , , LLVM- , ( ).

, . , C (19%!). , .

.

, State, .

, Bool , . , Int, 1 True, 0 — False? , , !

data State = State
  { bs :: Int
  , ws :: Int
  , ls :: Int
  , wasSpace :: Int
  }

wc :: BS.ByteString -> (Int, Int, Int)
wc s = (bs, ws, ls)
  where
    State { .. } = BS.foldl' go (State 0 0 0 0) s

    go State { .. } c = State (bs + 1) (ws + addWord) (ls + addLine) isSp
      where
        isSp | isSpace c = 1
             | otherwise = 0
        addLine | c == '\n' = 1
                | otherwise = 0
        addWord | wasSpace == 1 = 0
                | isSp == 1 = 1
                | otherwise = 0

(, Bool), . , , addWord guard' ( if) :

        addWord = (1 - wasSpace) * isSp

.

? , , 1.91 , 18% wc. , .

, ?

ASCII, isSpace. , . , , , .

, Data.ByteString.Lazy Data.ByteString.Lazy.Char8, Char.

:

{-# LANGUAGE Strict #-}
{-# LANGUAGE RecordWildCards #-}

module Data.WordCount where

import qualified Data.ByteString.Lazy as BS

data State = State
  { bs :: Int
  , ws :: Int
  , ls :: Int
  , wasSpace :: Int
  }

wc :: BS.ByteString -> (Int, Int, Int)
wc s = (bs, ws, ls)
  where
    State { .. } = BS.foldl' go (State 0 0 0 0) s

    go State { .. } c = State (bs + 1) (ws + addWord) (ls + addLine) isSp
      where
        isSp | c == 32 || c - 9 <= 4 = 1
             | otherwise = 0
        addLine | c == 10 = 1
                | otherwise = 0
        addWord = (1 - wasSpace) * isSp
{-# INLINE wc #-}

, 1.45 , 14% wc.

, — , , .

, , . , : wasSpace , , :

wc s = (bs, ws + 1 - wasSpace, ls)
  where
    State { .. } = BS.foldl' go (State 0 0 0 1) s
    ...

, .

:

0.35 , ? - - ?

, , wc. :

main :: IO ()
main = do
  [path] <- getArgs
  contents <- BS.readFile path
  print $ wc contents

readFile . mmap. bytestring-mmap, ByteString' mmap- , main

main :: IO ()
main = do
  [path] <- getArgs
  contents <- unsafeMMapFile path
  print $ wc contents

, unsafeMMapFile ByteString, wc, . , unsafeMMapFile, , mmap- , .

— , 0.04-0.06 0.35 . , .

mmap , : , , . , : , .

?

, , Unix-, . , , ST .

, , : , wc, , « » wc , , . , .

حسنًا ، حتى لا نتعذب ، سنناقش خطط المستقبل: في المقالة التالية سنتعامل مع شيء أكثر إثارة للاهتمام ، حيث سيتألق هاسكل حقًا. بشكل أكثر تحديدًا ، نقوم بتعديل ما لدينا اليوم ، ونرى كيف نجعل لعبتنا haskell wcأقل قليلاً ، ونقيم أيضًا كيف سيؤثر ذلك على الأداء.