Gaperton (gaperton) wrote,
Gaperton
gaperton

Category:

Быстрый файловый ввод-вывод в 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К.

Собственно, все. Смотрите на таблицу, делайте выводы.
Tags: benchmark, erlang, дизайн
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 46 comments