Эффективных потоков в Haskell

В постоянном стремлении эффективно манипулировать битами (например, см. Этоттак вопрос ) новейшей проблемой является эффективное потоковое использование и потребление битов.

В качестве первой простой задачи я выбираю поиск самой длинной последовательности идентичных битов в битовом потоке, генерируемом /dev/urandom. Типичным заклинанием было бы head -c 1000000 </dev/urandom | my-exe. Фактическая цель состоит в том, чтобы передавать биты и декодировать код Elias gamma , например, т. е. коды, которые не являются кусками байтов или кратными из этого.

Для таких кодов переменной длины хорошо иметь take, takeWhile, group, и т.д. язык для работы со списком. Поскольку BitStream.take фактически поглотил бы часть Бистрема, в игру, вероятно, вступила бы какая-то монада.

Очевидной отправной точкой является ленивый байтестринг от Data.ByteString.Lazy.

A. подсчет байтов

Эта очень простая программа Haskell работает наравне с программой C, как и должно быть ожидаемый.

import qualified Data.ByteString.Lazy as BSL

main :: IO ()
main = do
    bs <- BSL.getContents
    print $ BSL.length bs

B. добавление байтов

Как только я начну использовать unpack, все должно стать еще хуже.

main = do
    bs <- BSL.getContents
    print $ sum $ BSL.unpack bs

Удивительно, но Хаскелл и Си показывают почти одинаковую производительность.

C. Самая длинная последовательность идентичных битов

В качестве первой нетривиальной задачи самая длинная последовательность идентичных битов может быть найдена следующим образом:

module Main where

import           Data.Bits            (shiftR, (.&.))
import qualified Data.ByteString.Lazy as BSL
import           Data.List            (group)
import           Data.Word8           (Word8)

splitByte :: Word8 -> [Bool]
splitByte w = Prelude.map (i-> (w `shiftR` i) .&. 1 == 1) [0..7]

bitStream :: BSL.ByteString -> [Bool]
bitStream bs = concat $ map splitByte (BSL.unpack bs)

main :: IO ()
main = do
    bs <- BSL.getContents
    print $ maximum $ length <$> (group $ bitStream bs)

Ленивый байтестринг преобразуется в список [Word8] , а затем, используя сдвиги, каждый Word разбивается на биты, в результате получается список [Bool]. Этот список списков затем выравнивается с помощью concat. Получив (ленивый) список Bool, используйте group для разбиения списка на последовательности идентичных битов и затем сопоставьте length над ним. Наконец maximum дает желаемый результат. Довольно просто, но не очень быстро:

# C
real    0m0.606s

# Haskell
real    0m6.062s

Эта наивная реализация ровно на порядок медленнее. Профилирование показывает, что выделяется довольно много памяти (около 3 ГБ для разбора 1 МБ входных данных). Здесь нет однако следует отметить массовую утечку информации из космоса.

Отсюда я начинаю копаться:

• существует bitstream пакет , который обещает " быстрые, упакованные, строгие битовые потоки (т. е. список Булов) с полуавтоматическим слиянием потоков.". К сожалению, он не соответствует текущему пакету vector, см. здесь для получения подробной информации.
• далее я исследую streaming. Я не совсем понимаю, зачем мне нужна "эффектная" трансляция, которая приносит некоторые монада в игре - по крайней мере, пока я не начну с обратной поставленной задачи, то есть кодирования и записи битовых потоков в файл.
• как насчет того, чтобы просто fold - над ByteString? Мне пришлось бы ввести штат, чтобы отслеживать потребленные биты. Это не совсем приятно.take, takeWhile, group, и т.д. язык, который является желательным.

А теперь я не совсем понимаю, куда идти.

Обновление :

Я понял, как это сделать с помощью streaming и еще streaming-bytestring. Вероятно, я делаю это неправильно, потому что результат катастрофически плох.

import           Data.Bits                 (shiftR, (.&.))
import qualified Data.ByteString.Streaming as BSS
import           Data.Word8                (Word8)
import qualified Streaming                 as S
import           Streaming.Prelude         (Of, Stream)
import qualified Streaming.Prelude         as S

splitByte :: Word8 -> [Bool]
splitByte w = (i-> (w `shiftR` i) .&. 1 == 1) <$> [0..7]

bitStream :: Monad m => Stream (Of Word8) m () -> Stream (Of Bool) m ()
bitStream s = S.concat $ S.map splitByte s

main :: IO ()
main = do
    let bs = BSS.unpack BSS.getContents :: Stream (Of Word8) IO ()
        gs = S.group $ bitStream bs ::  Stream (Stream (Of Bool) IO) IO ()
    maxLen <- S.maximum $ S.mapped S.length gs
    print $ S.fst' maxLen

Это проверит ваше терпение с чем-либо, кроме нескольких тысяч байт ввода от stdin. Профилировщик говорит, что он тратит безумное количество времени (квадратичное по размеру входного сигнала) в Streaming.Internal.>>=.loop и Data.Functor.Of.fmap. Я не совсем уверен, что первое, но fmap указывает (?) что жонглирование этими Of a b не приносит нам никакой пользы, и поскольку мы находимся в монаде ИО, этого не может быть оптимизирован в сторону.

У меня также есть потоковый эквивалент байтового сумматора здесь: SumBytesStream.hs, что немного медленнее, чем простая ленивая реализация ByteString, но все же прилично. Поскольку streaming-bytestring являетсяпровозглашенным "bytestring io сделано правильно ", я ожидал лучшего. Тогда, наверное, я делаю это неправильно.

В любом случае, все эти битовые вычисления не должны происходить в монаде IO. Но BSS.getContents заставляет меня войти в монаду ИО, потому что getContents :: MonadIO m => ByteString m () и нет никакого выхода.

Обновление 2

Следуя совету @dfeuer, я использовал streaming пакет в master@HEAD. И вот результат.

longest-seq-c       0m0.747s    (C)
longest-seq         0m8.190s    (Haskell ByteString)
longest-seq-stream  0m13.946s   (Haskell streaming-bytestring)

Проблема O(n^2) Streaming.concat решена, но мы все еще не приближаемся к эталону C.

Обновление 3

Решение Cirdec производит производительность наравне с C. используемая конструкция называется "церковные закодированные списки", см. Это так ответьте или Haskell Wiki натипах ранга N .

Исходные файлы:

Все исходные файлы можно найти на github. У Makefile есть все различные цели для выполнения экспериментов и профилирования. По умолчанию make просто соберет все (сначала создайте каталог bin/!) и затем make time будет выполнять синхронизацию исполняемых файлов longest-seq. Исполняемые файлы C получают a -c, добавленное для их различения.