Эффективно печатать массив для текста в Haskell (фиктивно, извините)

Question

Обновление 2 : Этот вопрос является поддельным. Приношу извинения. Я добавил некоторый код для печати массива, пропуская остальную часть логики моей программы, и это почти мгновенно. Я думал, что медленная печать массива должна была быть медленной {что-то}, что было лениво вычислено после того, как была введена функция массива печати. ​​

Обновление 1 : приведенный ниже фрагмент неверно воспроизводит проблему с производительностью в моей исходной проблеме. Я, должно быть, неправильно объяснил источник медлительности, либо из-за неверного отслеживания ленивых выражений, либо из-за некоторых других изменений, которые я сделал, когда вытащил небольшой фрагмент из более крупной программы. Я постараюсь создать автономное воспроизведение медленной обработки.

Резюме: Форматирование распакованного массива Int32 в строку и вывод результирующего ~ 4 МБ текста на диск неэффективен, примерно 1 минута для печати 1 миллиона значений (60K циклов ЦП на значение). Зачем? Можно ли сделать это быстрее?

подробности:

Запуск в виде скомпилированной программы с флагом компилятора "-O2". GHC 7.0.4, платформа Haskell 2011.04, Windows 7 x64.

У меня есть программа на Haskell, которая создает массив размером от 100K до 1 миллиона Int32 значений.

Значения Int32 на самом деле Int8 значения из 4-х кортежей (Int8, Int8, Int8, Int8), упакованные в Int32 в (возможно, ошибочной) попытке повышения эффективности.

Я использую STUArray (но это может быть плохим выбором) для хранения и изменения массива.

В определенные моменты моей программы я печатаю массив на диск в следующем виде:

byte byte byte ...

, где каждый байт является ASCII-представлением десятичного значения байта (от «0» до «255»). Пример: * * тысяча тридцать пять

0 255 128 5 31 ...

Моя проблема заключается в том, что действие ввода-вывода при печати массива в Handle выполняется медленно: Требуется около минуты для форматирования печати ~ 1 миллиона байтов в текст на дескрипторе файла , на современном Процессор i5 с тактовой частотой 3,3 ГГц и диск SSD.

Мой код для печати в основном такой:

импорт Data.Array.Unboxed
импорт System.IO
импорт Contol.Monad
импорт данных. Биты

ручка printArray frozenArray = mapM _ ( hPutStr ручка. ShowPacked. (FrozenArray!)) [0..arrayLength]

showPacked x = (' ':) .  (shows $ (shift x (-24)) .&. 255) 
           . (' ':) .  (shows $ (shift x (-16)) .&. 255)
           . (' ':) .  (shows $ (shift x  (-8)) .&. 255) 
           . (' ':) .  (shows $        x        .&. 255)
           $ ""

Есть ли лучший способ?

Что может быть источником проблемы? У меня есть несколько догадок (в порядке убывания вероятности):

• Форматирование каждого Int32 с моим кодом неэффективно.
• mapM_ для массива с (!) Неэффективным.
• Вызов hPutStr миллион раз неэффективен.
• 1 минута для печати 1 миллиона значений на самом деле эффективна.

Предупреждение о потенциальной красной сельди: Существует некоторый риск того, что задержка, которую я вижу, связана с отложенными вычислениями, которые вызываются только при печати, а не вызваны самим форматированием / печатью, но я так не думаю, потому что даже когда Я печатаю массив в первой итерации (после создания исходного пустого массива), он все еще медленный. И я могу наблюдать, как выходной файл медленно растет, поэтому после печати первого байта происходит большая работа, даже с использованием строгого распакованного массива.

Answer 1

1. Вы действительно хотите это сделать?Вы действительно нуждаетесь в этом в текстовом виде, или какой-то двоичный формат будет в порядке?Потому что если это так, то это, вероятно, будет намного быстрее ...

2. Если вам действительно нужно , нужно, чтобы это был десятичный текст, читайте дальше.

Мой первый инстинкт - избегать ввода-вывода со значениями String.Вместо этого попробуйте собрать всю строку результата внутри ленивого ByteString, а затем записать весь лот на диск за один вызов ввода-вывода.Как преимущество, код становится чище.(Предполагая, что ваш массив действительно заморожен в тот момент, когда вы пытаетесь сохранить его на диск.) Затем вы можете позволить ленивому ByteString движку лениво генерировать текст и выполнять причудливую буферизацию и прочее.

К сожалению,Я не знаю ни одного способа прямого перехода от целого числа к текстовому представлению в ByteString без использования show для перехода по String.Но вы все равно можете увидеть некоторую выгоду от этого.Или нет ...

Answer 2

Что может быть источником проблемы?У меня есть несколько предположений (в порядке убывания вероятности):

• Форматирование каждого Int32 с моим кодом неэффективно.

Так себе.Я не уверен, насколько хорошо GHC оптимизирует shift x (-24), возможно, лучше использовать shiftR x 24, но мне нужно посмотреть на сгенерированное ядро, чтобы узнать.Редактировать: отлично, выдает uncheckedIShiftRA#, как можно было бы надеяться.

• mapM_ для массива с (!) Неэффективным.

Да, немного.Использование elems или unsafeAt немного быстрее из-за пропуска проверок границ.

• Вызов hPutStr миллион раз неэффективен.

Определенно.Но имеет меньшее влияние, чем я думал.

• 1 минута для печати 1 миллиона значений на самом деле эффективна.

Нет:

Prelude> writeFile "IntList.txt" $ unlines . map show $ [1 :: Int .. 1048576]
(0.37 secs, 836888976 bytes)

Это далекоболее эффективный - и вполне может быть более эффективным, чем использование промежуточного ByteString - для производства одного длинного String, который сразу печатается на ручке.Строка будет генерироваться лениво, поэтому она не будет использовать много памяти, и генерация String довольно эффективна (все еще настраиваемая, если это необходимо).

Теперь приступим к измерению.

Использование

printArray handle frozenArray = hPutStr handle $ showit (elems frozenArray)
  where
    showit :: [Int32] -> String
    showit (n:ns) = (' ' :) . shows ((n `shiftR` 24) .&. 255)
                  . (' ' :) . shows ((n `shiftR` 16) .&. 255)
                  . (' ' :) . shows ((n `shiftR` 8) .&. 255)
                  . (' ' :) . shows (n .&. 255) $ showit ns
    showit [] = ""

для печати значений привело к увеличению времени обработки [0 .. 1048575] с 0,9 до 0,4 секунды.Выделение уменьшилось с 2 031 716 528 байт до 779 086 856 байт, но использование памяти увеличилось с 6 МБ до 11 МБ, а количество байтов, скопированных во время GC, составило ~ 1M до ~ 5,5 М, однако ограничение размера кучи -M11M привело к тому, что ранее GC вернул память обратно в6 МБ и байтов скопировано во время GC до 676 744.(GHC-7.2.2) * 1 047 *