Быстрый файловый ввод-вывод в Erlang
Думаете, такого не бывает, да? :) Сейчас мы увидим, что будет, если полагаться на сильные стороны платформы, а не на слабые :). Мы сделаем самое быстрое в мире на момент публикации построчное чтение текстовых файлов для Эрланга.
Действительно, файловый ввод-вывод в Эрланге имеет репутацию очень медленного. Просто ужасно медленного. Отдыхая на новогодних каникулах от менеджерской работы, я решил разобраться, почему так.
Вскрытие показало, что ацки медленно работает исключительно модуль io, на что и налетают новички, используя функции io форматированного воода-вывода, скажем, для чтения файла по строкам. Но не модуль file. Причина в том, что у file есть два режима работы - raw (в котором дескриптор файла является идентификатором драйвера, дающего прямой интерфейс к функциям ввода-вывода оперсистемы), и обычный, когда создается оберточный процесс, PID-ом которого и является дескриптор файла.
Чего еще хорошего есть в режиме raw? То, что в нем можно указать опцию binary, и в этом случае не будет происходить копирования данных при чтении и записи, потому что binaries длиннее 64 байт хранятся в разделяемом хипе. Так и надо делать в том случае, если требуется производительность.
Если не указать binary, то ввод-вывод будет возвращать прочитанные данные в виде списков байт. Что в 8 (восемь) раз больше по объему, плюс - ЭТО еще и копируется между процессами. А если вы кроме этого не укажете raw, то копироваться данные будут два раза.
Кроме того, можно при открытии файла в любом из режимов указать ему опции read_ahead и delayed_write. Это приводит к выделению буфера внутри драйвера file, и системные вызовы будут дергаться реже. Кроме того, очень сильно ускорится последовательное чтение/запись - диск будет меньше дергать головки.
Чем плох режим raw? Тем, что файл открыый в этом режиме может быть использован только процессом, который его открыл, и только на том узле, где существует данный файл. Оказывается, если пользоваться io и стандартным режимом, файлы доступны на любом узле кластера, и неважно, разделяются у них диски, или нет. Прикольно, правда? Еще тем, что вам доступны только тупые функции file:read и file:write, форматированный ввод-вывод из io работать не будет.
Так вот, потеря на мой взгляд невелика, поэтому протестируем режим raw. А именно, я напишу для этого режима эффективную реализацию get_line. После чего проверим, с какой скоростью я буду читать файл длиной 821 мегабайт.
Идея следующая. Читаем в raw-режиме данные блоками фиксированной длины. Естественно, в режиме [ raw, binary ], чтобы избежать копирования. После чего, выделяем в блоках строки, поиском символа конца строки и выделением под-бинариса. Что также не приводит к копированию данных. Когда буфер кончится, считаем новый. И так, пока не кончится файл.
Для начала нам потребуется функция, которая будет быстро-быстро искать заданный символ в бинарисе. Выглядит она так:
find_8( Buffer, Char ) -> find_8( Buffer, Char, 0 ).
find_8( Buffer, Char, Pos ) ->
case Buffer of
<< _:Pos/bytes, Char:8, _/bytes >> -> Pos;
<< _:Pos/bytes, _:1/bytes, Char:8, _/bytes >> -> Pos + 1;
<< _:Pos/bytes, _:2/bytes, Char:8, _/bytes >> -> Pos + 2;
<< _:Pos/bytes, _:3/bytes, Char:8, _/bytes >> -> Pos + 3;
<< _:Pos/bytes, _:4/bytes, Char:8, _/bytes >> -> Pos + 4;
<< _:Pos/bytes, _:5/bytes, Char:8, _/bytes >> -> Pos + 5;
<< _:Pos/bytes, _:6/bytes, Char:8, _/bytes >> -> Pos + 6;
<< _:Pos/bytes, _:7/bytes, Char:8, _/bytes >> -> Pos + 7;
<< _:Pos/bytes, _:8/bytes, Char:8, _/bytes >> -> Pos + 8;
<< _:Pos/bytes, _:9/bytes, Char:8, _/bytes >> -> Pos + 9;
<< _:Pos/bytes, _:10/bytes, Char:8, _/bytes >> -> Pos + 10;
<< _:Pos/bytes, _:11/bytes, Char:8, _/bytes >> -> Pos + 11;
<< _:Pos/bytes, _:12/bytes, Char:8, _/bytes >> -> Pos + 12;
<< _:Pos/bytes, _:13/bytes, Char:8, _/bytes >> -> Pos + 13;
<< _:Pos/bytes, _:14/bytes, Char:8, _/bytes >> -> Pos + 14;
<< _:Pos/bytes, _:15/bytes, Char:8, _/bytes >> -> Pos + 15;
<< _:Pos/bytes, _:16/bytes, Char:8, _/bytes >> -> Pos + 16;
<< _:Pos/bytes, _:17/bytes, Char:8, _/bytes >> -> Pos + 17;
<< _:Pos/bytes, _:18/bytes, Char:8, _/bytes >> -> Pos + 18;
<< _:Pos/bytes, _:19/bytes, Char:8, _/bytes >> -> Pos + 19;
<< _:Pos/bytes, _:20/bytes, Char:8, _/bytes >> -> Pos + 20;
<< _:Pos/bytes, _:21/bytes, Char:8, _/bytes >> -> Pos + 21;
<< _:Pos/bytes, _:22/bytes, Char:8, _/bytes >> -> Pos + 22;
<< _:Pos/bytes, _:23/bytes, Char:8, _/bytes >> -> Pos + 23;
<< _:Pos/bytes, _:24/bytes, Char:8, _/bytes >> -> Pos + 24;
<< _:Pos/bytes, _:25/bytes, Char:8, _/bytes >> -> Pos + 25;
<< _:Pos/bytes, _:26/bytes, Char:8, _/bytes >> -> Pos + 26;
<< _:Pos/bytes, _:27/bytes, Char:8, _/bytes >> -> Pos + 27;
<< _:Pos/bytes, _:28/bytes, Char:8, _/bytes >> -> Pos + 28;
<< _:Pos/bytes, _:29/bytes, Char:8, _/bytes >> -> Pos + 29;
<< _:Pos/bytes, _:30/bytes, Char:8, _/bytes >> -> Pos + 30;
<< _:Pos/bytes, _:31/bytes, Char:8, _/bytes >> -> Pos + 31;
<< _:Pos/bytes, _:32/bytes, _/bytes >> -> find_8( Buffer, Char, Pos + 32 );
_ -> not_found
end.
Страшно? :) Здесь я руками раскрутил цикл, для того, чтобы дать возможность компилятору сгенерировать длинный кусок native кода, оптимально скомпилировав паттерн-матчинг. В принципе, 32 строки - это перебор. Вполне адекватно работает уже на 8 строках. Но мне 10% производительности не лишние. Вообще - по хорошему эта функция должна быть реализована как BIF.
Теперь сделаем функцию, которая разделяет наш бинарис на два, по первому вхождению заданного символа. Вот так:
%% split_char( binary(), byte() ) -> { binary(), binary() } | not_found
split_char( Buffer, Char ) ->
case find_8( Buffer, Char, 0 ) of
not_found -> not_found;
Pos ->
<< Before:Pos/bytes, _:8, After/bytes >> = Buffer,
{ Before, After }
end.
Разумеется, никакого копирования данных опять не происходит. :) Все тихо и мирно :).
Ну вот. Теперь мы готовы к тому, чтобы сделать наш get_line. Начинается самое интересное. Hardcore erlang.
%% file_reader( File, Len ) -> Handle
%% Handle = { NextF, binary() } | eof
%% NextF = fun() -> Handle
file_reader( File, Len ) -> file_reader( File, Len, << >> ).
file_reader( File, LenI, BufferB ) ->
NextF = fun() ->
case file:read( File, LenI ) of
{ ok, DataB } -> file_reader( File, LenI, DataB );
eof -> eof
end
end,
{ NextF, BufferB }.
Вот так. Эта штука возвращает "итератор". Итератор на блоки данных, мы ведь блоками данные читать собрались. А именно - это тупл, второй элемент которого содержит текущий прочитанный блок данных, а первый элемент - это функция без аргументов, которая продвинет итератор вперед, и вернет следующий. Нафиг нам не нужно никакое гребанное ООП, чтоб писать такие штуки, оно только под руками путается да думать мешает.
Вот. Теперь осталость написать сам get_line.
get_line( { NextF, BufferB } ) ->
case split_char( BufferB, 10 ) of
{ LineB, RestB } -> { { NextF, RestB }, LineB };
not_found ->
case NextF() of
eof -> { eof, BufferB };
Handl_1 ->
{ Handl_2, LineB } = get_line( Handl_1 ),
{ Handl_2, << BufferB/bytes, LineB/bytes >> }
end
end.
Собственно, все. Обратите внимание, забавный момент, у меня это само собой получилось. get_line совершенно ничего не знает о файлах. Он знает, что надо дернуть функцию, и магически появится следующий блок. Поэтому, ее можно использовать с произвольным источником данных. Кто-то еще думает, что повторное использование и полиморфный код - прерогатива ООП, и для этого необходимы классы, и куча дизайн-паттернов? :)
get_line( iterator() ) -> { iterator(), line() }
теперь проверим, с какой скоростью работает ввод-вывод в Эрланге на самом деле.
tf( Name, Len ) ->
{ ok, Fl } = file:open( Name, [ read, raw, binary ] ),
tf_loop( file_reader( Fl, Len ) ),
file:close( Fl ).
%% where
tf_loop( eof ) -> done;
tf_loop( Hnd ) ->
{ Hnd_2, _ } = get_line( Hnd ),
tf_loop( Hnd_2 ).
Len - это длина буфера. Ее мы будем варьировать. Вот результаты тестирования. Чтение файла длиной 821 мегабайт. Компьютер - iMac G5 1,9 Gz. Компилируем с флагом native. Время - в секундах.
Buffer size (bytes) 256 1024 4096 8192 16384
default 91,3 53,6 44,1 42,1 41,7
read_ahead 60,6 44,9 42,1 41,2 40,9
async 265,2 102,1 59,2 46,9 44,6
async, read_ahead 59,7 45,7 42,6 41,7 40,3
default - без async threads и read ahead режимов. Далее - включаем эти два режима по очереди и одновременно. Делаем выводы.
Скорость чтения достигает 20 мегабайт в секунду. То есть, в Эрланге вполне адекватный ввод.-вывод. Впрочем, будь там оптимизированный BIF для поиска по binaries - было бы еще лучше, я думаю. Надо завести proposal.
В режиме async threads лучше всегда применять read ahead. Режим рантайма async threads - позволяет накладывать вычисления на ожидание ввода-вывода, это необходимая штука для приложений выполняющих активный ввод-вывод.
Тем более, что при включенном read ahead производительность не зависит от того, async или не async у нас threads.
Далее. Меньше килобайта размер буфера делать не надо ни при каких обстоятельствах, это понятно. Оптимальный размер окна в большинстве случаев - 4К.
Собственно, все. Смотрите на таблицу, делайте выводы.
Действительно, файловый ввод-вывод в Эрланге имеет репутацию очень медленного. Просто ужасно медленного. Отдыхая на новогодних каникулах от менеджерской работы, я решил разобраться, почему так.
Вскрытие показало, что ацки медленно работает исключительно модуль io, на что и налетают новички, используя функции io форматированного воода-вывода, скажем, для чтения файла по строкам. Но не модуль file. Причина в том, что у file есть два режима работы - raw (в котором дескриптор файла является идентификатором драйвера, дающего прямой интерфейс к функциям ввода-вывода оперсистемы), и обычный, когда создается оберточный процесс, PID-ом которого и является дескриптор файла.
Чего еще хорошего есть в режиме raw? То, что в нем можно указать опцию binary, и в этом случае не будет происходить копирования данных при чтении и записи, потому что binaries длиннее 64 байт хранятся в разделяемом хипе. Так и надо делать в том случае, если требуется производительность.
Если не указать binary, то ввод-вывод будет возвращать прочитанные данные в виде списков байт. Что в 8 (восемь) раз больше по объему, плюс - ЭТО еще и копируется между процессами. А если вы кроме этого не укажете raw, то копироваться данные будут два раза.
Кроме того, можно при открытии файла в любом из режимов указать ему опции read_ahead и delayed_write. Это приводит к выделению буфера внутри драйвера file, и системные вызовы будут дергаться реже. Кроме того, очень сильно ускорится последовательное чтение/запись - диск будет меньше дергать головки.
Чем плох режим raw? Тем, что файл открыый в этом режиме может быть использован только процессом, который его открыл, и только на том узле, где существует данный файл. Оказывается, если пользоваться io и стандартным режимом, файлы доступны на любом узле кластера, и неважно, разделяются у них диски, или нет. Прикольно, правда? Еще тем, что вам доступны только тупые функции file:read и file:write, форматированный ввод-вывод из io работать не будет.
Так вот, потеря на мой взгляд невелика, поэтому протестируем режим raw. А именно, я напишу для этого режима эффективную реализацию get_line. После чего проверим, с какой скоростью я буду читать файл длиной 821 мегабайт.
Идея следующая. Читаем в raw-режиме данные блоками фиксированной длины. Естественно, в режиме [ raw, binary ], чтобы избежать копирования. После чего, выделяем в блоках строки, поиском символа конца строки и выделением под-бинариса. Что также не приводит к копированию данных. Когда буфер кончится, считаем новый. И так, пока не кончится файл.
Для начала нам потребуется функция, которая будет быстро-быстро искать заданный символ в бинарисе. Выглядит она так:
find_8( Buffer, Char ) -> find_8( Buffer, Char, 0 ).
find_8( Buffer, Char, Pos ) ->
case Buffer of
<< _:Pos/bytes, Char:8, _/bytes >> -> Pos;
<< _:Pos/bytes, _:1/bytes, Char:8, _/bytes >> -> Pos + 1;
<< _:Pos/bytes, _:2/bytes, Char:8, _/bytes >> -> Pos + 2;
<< _:Pos/bytes, _:3/bytes, Char:8, _/bytes >> -> Pos + 3;
<< _:Pos/bytes, _:4/bytes, Char:8, _/bytes >> -> Pos + 4;
<< _:Pos/bytes, _:5/bytes, Char:8, _/bytes >> -> Pos + 5;
<< _:Pos/bytes, _:6/bytes, Char:8, _/bytes >> -> Pos + 6;
<< _:Pos/bytes, _:7/bytes, Char:8, _/bytes >> -> Pos + 7;
<< _:Pos/bytes, _:8/bytes, Char:8, _/bytes >> -> Pos + 8;
<< _:Pos/bytes, _:9/bytes, Char:8, _/bytes >> -> Pos + 9;
<< _:Pos/bytes, _:10/bytes, Char:8, _/bytes >> -> Pos + 10;
<< _:Pos/bytes, _:11/bytes, Char:8, _/bytes >> -> Pos + 11;
<< _:Pos/bytes, _:12/bytes, Char:8, _/bytes >> -> Pos + 12;
<< _:Pos/bytes, _:13/bytes, Char:8, _/bytes >> -> Pos + 13;
<< _:Pos/bytes, _:14/bytes, Char:8, _/bytes >> -> Pos + 14;
<< _:Pos/bytes, _:15/bytes, Char:8, _/bytes >> -> Pos + 15;
<< _:Pos/bytes, _:16/bytes, Char:8, _/bytes >> -> Pos + 16;
<< _:Pos/bytes, _:17/bytes, Char:8, _/bytes >> -> Pos + 17;
<< _:Pos/bytes, _:18/bytes, Char:8, _/bytes >> -> Pos + 18;
<< _:Pos/bytes, _:19/bytes, Char:8, _/bytes >> -> Pos + 19;
<< _:Pos/bytes, _:20/bytes, Char:8, _/bytes >> -> Pos + 20;
<< _:Pos/bytes, _:21/bytes, Char:8, _/bytes >> -> Pos + 21;
<< _:Pos/bytes, _:22/bytes, Char:8, _/bytes >> -> Pos + 22;
<< _:Pos/bytes, _:23/bytes, Char:8, _/bytes >> -> Pos + 23;
<< _:Pos/bytes, _:24/bytes, Char:8, _/bytes >> -> Pos + 24;
<< _:Pos/bytes, _:25/bytes, Char:8, _/bytes >> -> Pos + 25;
<< _:Pos/bytes, _:26/bytes, Char:8, _/bytes >> -> Pos + 26;
<< _:Pos/bytes, _:27/bytes, Char:8, _/bytes >> -> Pos + 27;
<< _:Pos/bytes, _:28/bytes, Char:8, _/bytes >> -> Pos + 28;
<< _:Pos/bytes, _:29/bytes, Char:8, _/bytes >> -> Pos + 29;
<< _:Pos/bytes, _:30/bytes, Char:8, _/bytes >> -> Pos + 30;
<< _:Pos/bytes, _:31/bytes, Char:8, _/bytes >> -> Pos + 31;
<< _:Pos/bytes, _:32/bytes, _/bytes >> -> find_8( Buffer, Char, Pos + 32 );
_ -> not_found
end.
Страшно? :) Здесь я руками раскрутил цикл, для того, чтобы дать возможность компилятору сгенерировать длинный кусок native кода, оптимально скомпилировав паттерн-матчинг. В принципе, 32 строки - это перебор. Вполне адекватно работает уже на 8 строках. Но мне 10% производительности не лишние. Вообще - по хорошему эта функция должна быть реализована как BIF.
Теперь сделаем функцию, которая разделяет наш бинарис на два, по первому вхождению заданного символа. Вот так:
%% split_char( binary(), byte() ) -> { binary(), binary() } | not_found
split_char( Buffer, Char ) ->
case find_8( Buffer, Char, 0 ) of
not_found -> not_found;
Pos ->
<< Before:Pos/bytes, _:8, After/bytes >> = Buffer,
{ Before, After }
end.
Разумеется, никакого копирования данных опять не происходит. :) Все тихо и мирно :).
Ну вот. Теперь мы готовы к тому, чтобы сделать наш get_line. Начинается самое интересное. Hardcore erlang.
%% file_reader( File, Len ) -> Handle
%% Handle = { NextF, binary() } | eof
%% NextF = fun() -> Handle
file_reader( File, Len ) -> file_reader( File, Len, << >> ).
file_reader( File, LenI, BufferB ) ->
NextF = fun() ->
case file:read( File, LenI ) of
{ ok, DataB } -> file_reader( File, LenI, DataB );
eof -> eof
end
end,
{ NextF, BufferB }.
Вот так. Эта штука возвращает "итератор". Итератор на блоки данных, мы ведь блоками данные читать собрались. А именно - это тупл, второй элемент которого содержит текущий прочитанный блок данных, а первый элемент - это функция без аргументов, которая продвинет итератор вперед, и вернет следующий. Нафиг нам не нужно никакое гребанное ООП, чтоб писать такие штуки, оно только под руками путается да думать мешает.
Вот. Теперь осталость написать сам get_line.
get_line( { NextF, BufferB } ) ->
case split_char( BufferB, 10 ) of
{ LineB, RestB } -> { { NextF, RestB }, LineB };
not_found ->
case NextF() of
eof -> { eof, BufferB };
Handl_1 ->
{ Handl_2, LineB } = get_line( Handl_1 ),
{ Handl_2, << BufferB/bytes, LineB/bytes >> }
end
end.
Собственно, все. Обратите внимание, забавный момент, у меня это само собой получилось. get_line совершенно ничего не знает о файлах. Он знает, что надо дернуть функцию, и магически появится следующий блок. Поэтому, ее можно использовать с произвольным источником данных. Кто-то еще думает, что повторное использование и полиморфный код - прерогатива ООП, и для этого необходимы классы, и куча дизайн-паттернов? :)
get_line( iterator() ) -> { iterator(), line() }
теперь проверим, с какой скоростью работает ввод-вывод в Эрланге на самом деле.
tf( Name, Len ) ->
{ ok, Fl } = file:open( Name, [ read, raw, binary ] ),
tf_loop( file_reader( Fl, Len ) ),
file:close( Fl ).
%% where
tf_loop( eof ) -> done;
tf_loop( Hnd ) ->
{ Hnd_2, _ } = get_line( Hnd ),
tf_loop( Hnd_2 ).
Len - это длина буфера. Ее мы будем варьировать. Вот результаты тестирования. Чтение файла длиной 821 мегабайт. Компьютер - iMac G5 1,9 Gz. Компилируем с флагом native. Время - в секундах.
Buffer size (bytes) 256 1024 4096 8192 16384
default 91,3 53,6 44,1 42,1 41,7
read_ahead 60,6 44,9 42,1 41,2 40,9
async 265,2 102,1 59,2 46,9 44,6
async, read_ahead 59,7 45,7 42,6 41,7 40,3
default - без async threads и read ahead режимов. Далее - включаем эти два режима по очереди и одновременно. Делаем выводы.
Скорость чтения достигает 20 мегабайт в секунду. То есть, в Эрланге вполне адекватный ввод.-вывод. Впрочем, будь там оптимизированный BIF для поиска по binaries - было бы еще лучше, я думаю. Надо завести proposal.
В режиме async threads лучше всегда применять read ahead. Режим рантайма async threads - позволяет накладывать вычисления на ожидание ввода-вывода, это необходимая штука для приложений выполняющих активный ввод-вывод.
Тем более, что при включенном read ahead производительность не зависит от того, async или не async у нас threads.
Далее. Меньше килобайта размер буфера делать не надо ни при каких обстоятельствах, это понятно. Оптимальный размер окна в большинстве случаев - 4К.
Собственно, все. Смотрите на таблицу, делайте выводы.