Tại sao `(bản đồ digitToInt). show` quá nhanh?

Question

chuyển đổi không âm Integer vào danh sách các chữ số thường được thực hiện như thế này:

import Data.Char 

digits :: Integer -> [Int] 
digits = (map digitToInt) . show 

Tôi đã cố gắng tìm một cách trực tiếp hơn để thực hiện các nhiệm vụ, mà không liên quan đến một sự chuyển đổi chuỗi, nhưng tôi không thể để tìm ra thứ gì đó nhanh hơn.

Những điều tôi đã cố gắng cho đến nay:

Các cơ sở:

digits :: Int -> [Int] 
digits = (map digitToInt) . show 

Got này từ một câu hỏi khác trên StackOverflow:

digits2 :: Int -> [Int] 
digits2 = map (`mod` 10) . reverse . takeWhile (> 0) . iterate (`div` 10) 

Đang cố gắng để cuộn của riêng tôi:

digits3 :: Int -> [Int] 
digits3 = reverse . revDigits3 

revDigits3 :: Int -> [Int] 
revDigits3 n = case divMod n 10 of 
       (0, digit) -> [digit] 
       (rest, digit) -> digit:(revDigits3 rest) 

Cái này được lấy cảm hứng từ showInt trong Numeric:

digits4 n0 = go n0 [] where 
    go n cs 
     | n < 10 = n:cs 
     | otherwise = go q (r:cs) 
     where 
     (q,r) = n `quotRem` 10 

Bây giờ điểm chuẩn. Lưu ý: Tôi đang buộc đánh giá bằng cách sử dụng filter.

λ>:set +s 
λ>length $ filter (>5) $ concat $ map (digits) [1..1000000] 
2400000 
(1.58 secs, 771212628 bytes) 

Đây là tham chiếu. Bây giờ cho digits2:

λ>length $ filter (>5) $ concat $ map (digits2) [1..1000000] 
2400000 
(5.47 secs, 1256170448 bytes) 

Đó là 3,46 còn lần.

λ>length $ filter (>5) $ concat $ map (digits3) [1..1000000] 
2400000 
(7.74 secs, 1365486528 bytes) 

digits3 là 4,89 thời gian chậm hơn. Chỉ cần cho vui, tôi đã thử chỉ sử dụng revDigits3 và tránh reverse.

λ>length $ filter (>5) $ concat $ map (revDigits3) [1..1000000] 
2400000 
(8.28 secs, 1277538760 bytes) 

Kỳ lạ thay, điều này thậm chí còn chậm hơn, 5,24 lần chậm hơn.

Và mới nhất:

λ>length $ filter (>5) $ concat $ map (digits4) [1..1000000] 
2400000 
(16.48 secs, 1779445968 bytes) 

Đây là 10.43 thời gian chậm hơn.

Tôi đã có ấn tượng rằng chỉ sử dụng số học và khuyết điểm sẽ tốt hơn bất kỳ điều gì liên quan đến chuyển đổi chuỗi. Rõ ràng, có điều gì đó tôi không thể nắm bắt được.

Vậy mẹo là gì? Tại sao là digits quá nhanh?

Tôi đang sử dụng GHC 6.12.3.

Answer 1

Xem như tôi chưa thể thêm nhận xét, tôi sẽ thực hiện thêm một chút công việc và chỉ phân tích tất cả chúng. Tôi đang đưa phân tích lên hàng đầu; tuy nhiên, các dữ liệu liên quan là dưới đây. (Lưu ý: tất cả điều này được thực hiện trong 6.12.3 - không có phép thuật GHC 7.)

---

Phân tích:

Phiên bản 1: chương trình là khá tốt cho ints, đặc biệt là những người như ngắn như chúng ta. Làm cho dây thực sự có xu hướng được phong nha trong GHC; tuy nhiên đọc các chuỗi và viết các chuỗi lớn vào các tệp (hoặc stdout, mặc dù bạn không muốn làm điều đó) là nơi mã của bạn hoàn toàn có thể thu thập thông tin. Tôi sẽ nghi ngờ rằng rất nhiều chi tiết đằng sau lý do tại sao điều này là quá nhanh là do tối ưu hóa thông minh trong chương trình cho Ints.

Phiên bản 2: Đây là gói chậm nhất khi được biên dịch. Một số vấn đề: ngược lại là nghiêm ngặt trong đối số của nó. Điều này có nghĩa là bạn không được hưởng lợi từ việc có thể thực hiện tính toán trên phần đầu tiên của danh sách trong khi bạn đang tính toán các phần tử tiếp theo; bạn phải tính toán tất cả, lật chúng, và sau đó thực hiện các phép tính của bạn (cụ thể là (`mod` 10)) trên các phần tử của danh sách. Trong khi điều này có vẻ nhỏ, nó có thể dẫn đến sử dụng bộ nhớ lớn hơn (lưu ý 5GB bộ nhớ heap được phân bổ ở đây là tốt) và tính toán chậm hơn. (Dài câu chuyện ngắn: không sử dụng ngược lại.)

Phiên bản 3: Hãy nhớ cách tôi vừa nói không sử dụng ngược lại? Hóa ra, nếu bạn lấy nó ra, cái này giảm xuống còn 1.79s tổng thời gian thực hiện - hầu như không chậm hơn đường cơ sở. Vấn đề duy nhất ở đây là khi bạn đi sâu hơn vào con số, bạn đang xây dựng cột sống của danh sách theo hướng sai (về cơ bản, bạn đang kết hợp "vào" danh sách với đệ quy, trái ngược với việc chấp nhận "lên" danh sách).

Phiên bản 4: Đây là triển khai rất thông minh. Bạn được hưởng lợi từ một số điều tốt đẹp: cho một, quotRem nên sử dụng thuật toán Euclide, là logarit trong đối số lớn hơn của nó. (Có lẽ nó nhanh hơn, nhưng tôi không tin rằng có bất cứ điều gì đó là nhiều hơn một yếu tố liên tục nhanh hơn Euclid.) Hơn nữa, bạn chống lại danh sách như thảo luận thời gian qua, để bạn không phải giải quyết bất kỳ thunks danh sách như bạn đi - danh sách đã được xây dựng hoàn toàn khi bạn quay lại để phân tích nó. Như bạn có thể thấy, lợi ích hiệu suất từ ​​việc này.

Mã này có lẽ là chậm nhất trong GHCi vì có rất nhiều tối ưu được thực hiện với cờ -O3 trong thỏa thuận GHC với việc tạo danh sách nhanh hơn, trong khi GHCi sẽ không làm điều đó.

Bài học: theo đúng cách vào danh sách, xem mức độ nghiêm ngặt trung gian có thể làm chậm tính toán và thực hiện một số tác vụ trong việc xem xét thống kê chi tiết về hiệu suất của mã. Đồng thời biên dịch với các lá cờ -O3: bất cứ khi nào bạn không làm, tất cả những người đã dành nhiều thời gian để làm cho GHC siêu nhanh có được đôi mắt to lớn của bạn.

---

dữ liệu:

Tôi chỉ mất tất cả bốn chức năng, mắc kẹt chúng vào một .hs tập tin, và sau đó đã thay đổi khi cần thiết để phản ánh các chức năng sử dụng. Ngoài ra, tôi đã tăng giới hạn của bạn lên tới 5e6, bởi vì trong một số trường hợp, mã được biên dịch sẽ chạy trong chưa đầy nửa giây trên 1e6 và điều này có thể bắt đầu gây ra sự cố chi tiết với các phép đo mà chúng tôi đang thực hiện.

Tùy chọn trình biên dịch: sử dụng ghc --make -O3 [tên tệp] .hs để GHC thực hiện một số tối ưu hóa. Chúng tôi sẽ kết xuất số liệu thống kê thành lỗi chuẩn bằng cách sử dụng chữ số + RTS -sstderr.

bán phá giá để -sstderr cho chúng ta đầu ra trông như thế này, trong trường hợp của digits1:

digits1 +RTS -sstderr 
12000000 
    2,885,827,628 bytes allocated in the heap 
     446,080 bytes copied during GC 
      3,224 bytes maximum residency (1 sample(s)) 
      12,100 bytes maximum slop 
       1 MB total memory in use (0 MB lost due to fragmentation) 

    Generation 0: 5504 collections,  0 parallel, 0.06s, 0.03s elapsed 
    Generation 1:  1 collections,  0 parallel, 0.00s, 0.00s elapsed 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT time 1.61s ( 1.66s elapsed) 
    GC time 0.06s ( 0.03s elapsed) 
    EXIT time 0.00s ( 0.00s elapsed) 
    Total time 1.67s ( 1.69s elapsed) 

    %GC time  3.7% (1.5% elapsed) 

    Alloc rate 1,795,998,050 bytes per MUT second 

    Productivity 96.3% of total user, 95.2% of total elapsed 

Có ba thống kê then chốt ở đây:

1. Tổng bộ nhớ sử dụng: chỉ 1MB phương tiện phiên bản này rất hiệu quả về mặt không gian.
2. Tổng thời gian: 1.61 có nghĩa là không có gì ngay bây giờ, nhưng chúng tôi sẽ xem nó trông như thế nào so với các triển khai khác.
3. Năng suất: Đây chỉ là thu gom rác thải 100% trừ; vì chúng ta đang ở 96,3% điều này có nghĩa rằng chúng tôi không tạo ra rất nhiều đối tượng mà chúng ta để lại nằm xung quanh trong bộ nhớ ..

Được rồi, chúng ta hãy chuyển sang phiên bản 2.

digits2 +RTS -sstderr 
12000000 
    5,512,869,824 bytes allocated in the heap 
     1,312,416 bytes copied during GC 
      3,336 bytes maximum residency (1 sample(s)) 
      13,048 bytes maximum slop 
       1 MB total memory in use (0 MB lost due to fragmentation) 

    Generation 0: 10515 collections,  0 parallel, 0.06s, 0.04s elapsed 
    Generation 1:  1 collections,  0 parallel, 0.00s, 0.00s elapsed 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT time 3.20s ( 3.25s elapsed) 
    GC time 0.06s ( 0.04s elapsed) 
    EXIT time 0.00s ( 0.00s elapsed) 
    Total time 3.26s ( 3.29s elapsed) 

    %GC time  1.9% (1.2% elapsed) 

    Alloc rate 1,723,838,984 bytes per MUT second 

    Productivity 98.1% of total user, 97.1% of total elapsed 

Được rồi, vì vậy chúng ta đang thấy một mô hình thú vị.

1. Cùng một lượng bộ nhớ được sử dụng. Điều này có nghĩa rằng đây là một thực hiện khá tốt, mặc dù nó có thể có nghĩa là chúng ta cần phải thử nghiệm trên các đầu vào mẫu cao hơn để xem chúng ta có thể tìm thấy sự khác biệt hay không.
2. Mất gấp đôi. Chúng tôi sẽ trở lại với một số suy đoán về lý do tại sao điều này là sau này.
3. Nó thực sự hiệu quả hơn một chút, nhưng cho rằng GC không phải là một phần lớn của một trong hai chương trình này không giúp chúng tôi bất cứ điều gì đáng kể.

Phiên bản 3:

digits3 +RTS -sstderr 
12000000 
    3,231,154,752 bytes allocated in the heap 
     832,724 bytes copied during GC 
      3,292 bytes maximum residency (1 sample(s)) 
      12,100 bytes maximum slop 
       1 MB total memory in use (0 MB lost due to fragmentation) 

    Generation 0: 6163 collections,  0 parallel, 0.02s, 0.02s elapsed 
    Generation 1:  1 collections,  0 parallel, 0.00s, 0.00s elapsed 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT time 2.09s ( 2.08s elapsed) 
    GC time 0.02s ( 0.02s elapsed) 
    EXIT time 0.00s ( 0.00s elapsed) 
    Total time 2.11s ( 2.10s elapsed) 

    %GC time  0.7% (1.0% elapsed) 

    Alloc rate 1,545,701,615 bytes per MUT second 

    Productivity 99.3% of total user, 99.3% of total elapsed 

Alright, vì vậy chúng tôi đang nhìn thấy một số mẫu lạ.

1. Chúng tôi vẫn đang ở mức tổng dung lượng 1MB đang sử dụng. Vì vậy, chúng tôi đã không nhấn bất cứ điều gì bộ nhớ-không hiệu quả, đó là tốt.
2. Chúng tôi không hoàn toàn ở số 1, nhưng chúng tôi đã có chữ số 2 khá dễ dàng.
3. Rất ít GC. (Hãy nhớ rằng bất cứ điều gì năng suất hơn 95% là rất tốt, vì vậy chúng tôi không thực sự đối phó với bất cứ điều gì quá quan trọng ở đây.)

Và cuối cùng, phiên bản 4:

digits4 +RTS -sstderr 
12000000 
    1,347,856,636 bytes allocated in the heap 
     270,692 bytes copied during GC 
      3,180 bytes maximum residency (1 sample(s)) 
      12,100 bytes maximum slop 
       1 MB total memory in use (0 MB lost due to fragmentation) 

    Generation 0: 2570 collections,  0 parallel, 0.00s, 0.01s elapsed 
    Generation 1:  1 collections,  0 parallel, 0.00s, 0.00s elapsed 

    INIT time 0.00s ( 0.00s elapsed) 
    MUT time 1.09s ( 1.08s elapsed) 
    GC time 0.00s ( 0.01s elapsed) 
    EXIT time 0.00s ( 0.00s elapsed) 
    Total time 1.09s ( 1.09s elapsed) 

    %GC time  0.0% (0.8% elapsed) 

    Alloc rate 1,234,293,036 bytes per MUT second 

    Productivity 100.0% of total user, 100.5% of total elapsed 

Wowza! Hãy chia nhỏ nó:

1. Chúng tôi vẫn ở mức tổng cộng 1MB. Điều này gần như chắc chắn là một tính năng của những triển khai này, vì chúng vẫn ở mức 1MB trên đầu vào của 5e5 và 5e7. Một minh chứng cho sự lười biếng, nếu bạn muốn.
2. Chúng tôi cắt giảm khoảng 32% thời gian ban đầu, điều này khá ấn tượng.
3. Tôi nghi ngờ rằng tỷ lệ phần trăm ở đây phản ánh mức độ chi tiết trong giám sát -sstderr hơn là bất kỳ tính toán nào trên các hạt siêu âm.

Answer 2

Trả lời câu hỏi "tại sao lại thay vì mod?" trong các ý kiến.Khi xử lý các giá trị dương rem x y === mod x y do đó, chỉ xem xét lưu ý là hiệu suất:

> import Test.QuickCheck 
> quickCheck (\x y -> x > 0 && y > 0 ==> x `rem` y == x `mod` y) 

Vì vậy, hiệu suất là gì? Trừ khi bạn có một lý do chính đáng không (và lười biếng không phải là một lý do chính đáng, không phải là không biết Criterion) sau đó sử dụng một công cụ benchmark tốt, tôi sử dụng tiêu chí:

$ cat useRem.hs 
import Criterion 
import Criterion.Main 

list :: [Integer] 
list = [1..10000] 

main = defaultMain 
     [ bench "mod" (nf (map (`mod` 7)) list) 
     , bench "rem" (nf (map (`rem` 7)) list) 
     ] 

Chạy điều này cho thấy rem là cách đo tốt hơn hơn mod (được biên soạn với -O2):

$ ./useRem 
... 
benchmarking mod 
... 
mean: 590.4692 us, lb 589.2473 us, ub 592.1766 us, ci 0.950 

benchmarking rem 
... 
mean: 394.1580 us, lb 393.2415 us, ub 395.4184 us, ci 0.950