Haskell: Data.HashSet (из неупорядоченного контейнера) Производительность для больших наборов
Данные
Прежде всего, давайте сгенерируем некоторые данные, чтобы у нас были конкретные данные для обсуждения:
python -c 'for f in xrange(4000000): print f' > input.txt
это сгенерирует файл input.txt содержит числа от 0 до 3999999, каждая на своей строке. Это означает, что у нас должен быть файл с 4 000 000 строк, добавляющий до 30 888 890 байт, что составляет примерно 29 МБ.
Все как список
Хорошо, давайте загрузим все в память как [Text]:
import Data.Conduit
import Data.Text (Text)
import Control.Monad.Trans.Resource (runResourceT)
import qualified Data.Conduit.Binary as CB
import qualified Data.Conduit.Text as CT
import qualified Data.Conduit.List as CL
main :: IO ()
main = do
hs <- (runResourceT
$ CB.sourceFile "input.txt"
$$ CT.decode CT.utf8
=$ CT.lines
=$ CL.fold (\b a -> a `seq` b `seq` a:b) [])
print $ head hs
и запустить его:
[1 of 1] Compiling Main ( Test.hs, Test.o )
Linking Test ...
"3999999"
2,425,996,328 bytes allocated in the heap
972,945,088 bytes copied during GC
280,665,656 bytes maximum residency (13 sample(s))
5,120,528 bytes maximum slop
533 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 4378 colls, 0 par 0.296s 0.309s 0.0001s 0.0009s
Gen 1 13 colls, 0 par 0.452s 0.661s 0.0508s 0.2511s
INIT time 0.000s ( 0.000s elapsed)
MUT time 0.460s ( 0.465s elapsed)
GC time 0.748s ( 0.970s elapsed)
EXIT time 0.002s ( 0.034s elapsed)
Total time 1.212s ( 1.469s elapsed)
%GC time 61.7% (66.0% elapsed)
Alloc rate 5,271,326,694 bytes per MUT second
Productivity 38.3% of total user, 31.6% of total elapsed
real 0m1.481s
user 0m1.212s
sys 0m0.232s
работает в 1.4s, занимает 533 МБ памяти. По состоянию памяти Haskell Wiki, 4M Text экземпляры должны занимать 6 слов + 2N байтов памяти. Я на 64 бит, поэтому одно слово составляет 8 байтов. Это означает, что оно должно быть (6 * 8 байт * 4000000) + (2*26888890) байт = 234 МБ. (26888890 - все байты в input.txt это не символы новой строки). Для списка, который будет содержать их все, нам понадобится дополнительная память (1 + 3N) слов + N * sizeof(v). sizeof(v) должно быть 8, потому что это будет указатель на Text, Список должен затем использовать (1 + 3 * 4000000) * 8 байт + 4000000 * 8 байт = 122 МБ. Таким образом, всего (список + строки) мы ожидаем, что будет использовано 356 МБ памяти. Я не знаю, куда ушла разница в 177 МБ (50%) нашей памяти, но давайте пока проигнорируем это.
Большой хэш-набор
Наконец, мы перейдем к варианту использования, который мне действительно интересен: хранение всех слов в большом Data.HashSet, Для этого я немного изменил программу
import Data.Conduit
import Data.Text (Text)
import Control.Monad.Trans.Resource (runResourceT)
import qualified Data.Conduit.Binary as CB
import qualified Data.Conduit.Text as CT
import qualified Data.Conduit.List as CL
import qualified Data.HashSet as HS
main :: IO ()
main = do
hs <- (runResourceT
$ CB.sourceFile "input.txt"
$$ CT.decode CT.utf8
=$ CT.lines
=$ CL.fold (\b a -> a `seq` b `seq` HS.insert a b) HS.empty)
print $ HS.size hs
если мы запустим это снова
$ ghc -fforce-recomp -O3 -rtsopts Test.hs && time ./Test +RTS -sstderr
[1 of 1] Compiling Main ( Test.hs, Test.o )
Linking Test ...
4000000
6,544,900,208 bytes allocated in the heap
6,314,477,464 bytes copied during GC
442,295,792 bytes maximum residency (26 sample(s))
8,868,304 bytes maximum slop
1094 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 12420 colls, 0 par 5.756s 5.869s 0.0005s 0.0034s
Gen 1 26 colls, 0 par 3.068s 3.633s 0.1397s 0.6409s
INIT time 0.000s ( 0.000s elapsed)
MUT time 3.567s ( 3.592s elapsed)
GC time 8.823s ( 9.502s elapsed)
EXIT time 0.008s ( 0.097s elapsed)
Total time 12.399s ( 13.192s elapsed)
%GC time 71.2% (72.0% elapsed)
Alloc rate 1,835,018,578 bytes per MUT second
Productivity 28.8% of total user, 27.1% of total elapsed
real 0m13.208s
user 0m12.399s
sys 0m0.646s
это довольно плохо: используется 13 с и 1094 МБ памяти. Страница памяти занимает список из 4,5N слов + N * sizeof (v) для хэш-набора, который должен стать (4,5 * 4000000 * 8 байтов) + (4000000 * 8 байтов) = 167 МБ. Добавляя хранилище для укусов (234 МиБ), я бы ожидал 401 МиБ, что более чем вдвое, и вдобавок это выглядит довольно медленно:(.
Мысленный эксперимент: ручное управление памятью
В качестве мысленного эксперимента: используя язык, на котором мы можем вручную управлять макетом памяти и реализовывать HashSet с открытой адресацией, я бы ожидал, что следующие размеры будут такими. Справедливости ради, я ожидаю, что строки все еще будут в UTF-16 (что Data.Text делает). Учитывая, что всего 26888890 символов (без перевода строки), строки в UTF-16 должны быть примерно 53777780 байт (2 * 26888890) = 51 МБ. Нам нужно будет хранить длину для каждой строки, которая будет 8 байтов * 4000000 = 30 МБ. И нам понадобится место для хэш-набора (4000000 * 8 байт), опять же 30 МБ. Учитывая, что хэш-наборы обычно увеличиваются экспоненциально, можно ожидать 32 МБ или 64 МБ в худшем случае. Давайте рассмотрим наихудший случай: 64 МБ для таблицы + 30 МБ для длин строки + 51 МБ для фактических данных строки, всего 145 МБ.
Итак, учитывая, что Data.HashSet не является специализированной реализацией для хранения строк, вычисленные 401 МиБ не будут слишком плохими, но фактически используемые 1094 МиБ кажутся немного бесполезными.
Вопросы наконец-то:)
И вот мы наконец добрались
- Где ошибка в моих расчетах?
- Есть ли какая-то проблема в моей реализации, или 1094MiB действительно лучшее, что мы можем получить?
Версии и прочее
- Я, наверное, должен использовать
ByteStringс вместоTextтак как мне нужны только символы ascii - Я нахожусь на GHC 7.10.1 и
unordered-containers-0.2.5.1
Для сравнения: 4 000 000 Int s:
import Data.List (foldl')
import qualified Data.HashSet as HS
main = do
let hs = foldl' (\b a -> a `seq` b `seq` HS.insert a b) (HS.empty :: HS.HashSet Int) [1..4000000]
print $ HS.size hs
выглядит не лучше
[...]
798 MB total memory in use (0 MB lost due to fragmentation)
[...]
real 0m9.956s
это почти 800 МБ для 4M Ints!