ट्वेंटी हास्केल लाइन्स से जीतना: आपका Wc लिखना

हेलो, हैबर।

दूसरे दिन Siemarglहास्केल की मदद से यूनिक्स पर जीत के बारे में एक जिज्ञासु लेख का अनुवाद करने के लिए मुझे आमंत्रित किया wc। बेशक, मैं इसका अनुवाद नहीं करूंगा, और कई कारणों से:

• लेखक ने बिना किसी मतलब के एकल-थ्रेडेड संस्करण से निचोड़ लिया, और एकल-थ्रेडेड संस्करण बहुत धीमा था wc,
• उस लेख में, जीतने के लिए मल्टीथ्रेडिंग का उपयोग करना आवश्यक था (जो अपने आप में सामान्य ज्ञान के बजाय धोखा देने और जीत की थोड़ी सी बात है wc)
• इसके लिए, लेखक को तल्लीन होना पड़ा trichoमोनड्स और मोनॉयड्स - नहीं, यह मोनोडल सोच के आकर्षण का एक उत्कृष्ट चित्रण है, लेकिन आईएमएचओ इस तरह के कार्य के लिए बहुत अधिक है, खासकर क्योंकि इस वजह से
• कोड बहुत बड़ा निकला,
• और वास्तव में, इसके साथ प्रतिस्पर्धा करने के लिए wc, जिसमें विकल्पों और सुविधाओं का एक समूह होता है, यह एहसास होता है कि यह एक बहुत ही खिलौना एनालॉग है, सामान्य तौर पर यह किसी भी तरह अजीब और यहां तक ​​कि थोड़ा मूर्खतापूर्ण है।

फिर भी, अजीब चीजें करना एक अच्छी बात है, इसलिए आज हम ऊपर दिए गए पहले बिंदुओं को ठीक करने की कोशिश करेंगे और क्रिस (मूल लेख के लेखक का नाम) के परिणाम में सुधार करेंगे।

फिर, जैसा कि हमने पिछली बार पाया था, मैं सी कोड नहीं लिख सकता, इसलिए मैंने इसे या तो नहीं लिखा, और हास्केल कार्यान्वयन के लिए एक प्रतियोगी के रूप में, मैं (क्रिस की तरह) wcजीएनयू कोरुटिल्स से एक तालमेल रखता हूं। उन दोस्तों को निश्चित रूप से पता है कि सी में कैसे लिखना है, यह कोड एक दशक पुराना नहीं है, और उन्होंने ऐसे टुकड़ों को देखते हुए प्रदर्शन का ध्यान रखा:

/* 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थोड़ा कम खिलौना कैसे बनाया जाए, और यह भी मूल्यांकन करें कि यह प्रदर्शन को कैसे प्रभावित करेगा।