Semantic locality

[vitus_wagner]

http://esr.ibiblio.org/?p=7421

Раймонд умный пост написал по поводу концепций, которые лежат под Unix way. Я эту мысль про семантическую локальность три дня думать буду.

Comments

[amarao-san.livejournal.com]

Но потоковые парсеры при этом всё-таки есть. Собственно, в любом потоковом протоколе нам могут подсунуть объект больше нашего буффера размером. Например, строку длиной в гигабайт во внутрь авка. Как только мы эти данные начинаем считать не потоком байтов (для которых локальность 1) или потоком чего-то простого (4 байтовых последовательностей), так тут же локальность начинает становиться величиной условной.

Хотя в том же json'е, например, задача "извлечь 100 Гб значение по ключу из 10000 Гб json'а" вполне решается. Мы просто вешаем обработчик на чтение значения, которое выдаёт значение на stdout по мере чтения, а всё остальное пропускаем. Если у нас при этом нет превышения по размеру ключа (очевидно, что мы не можем найти что-то по ключу, который больше нашей оперативной памяти, т.к. не сможем его передать как параметр программы), то это вполне рабочее.

Я баловался с потоковыми парсерами json'ов, на удивление, это вещь и она может существовать в константной памяти при неконстантных входных данных.

[livelight]

Я поэтому и оговорил ограниченную длину строки. Притом команде sort, например, это не поможет, поскольку она по сути нелокальна, но большинству фильтров этого достаточно. А вот с настоящим JSON этот фокус не пройдёт, даже если мы ограничим длины всех констант, всех массивов и всех хэш-таблиц. Впрочем, если ограничить ещё и глубину деревьев, то таки получится.

[amarao-san.livejournal.com]

Скажи, какую операцию в json'е ты хочешь делать? Многие из них могут выполняться в локальном контексте.

[livelight]

Банальный фильтр, который должен бы быть поточным: читаем входной поток неких токенов с полями, а для тех, у которых выполняется некое условие на поле1 и поле2, выводим в выходной поток поле3 целиком, не вникая в содержимое.

Соответственно, в случае JSON мы всегда можем получить на вход что-нибудь такое:
{
поле1: значение,
поле3: { развесистое и глубокое дерево },
поле2: значение
}

в результате мы должны запомнить всё, что в поле1 и в поле3, прежде чем считаем поле2 и сможем принять решение, выводить ли нам поле3. А это уже нелокальность, приходится помнить много лишнего.

[anonim_legion]

Как часто требуется обрабатывать преогромные деревья, да еще и сортировать их?

Для XML существуют SAX-парсеры, вполне себе работают на многогигабайтных данных.

[livelight]

Там нет проблемы 2, так что при хорошей структуре XML и соответствующих запросах, связка SAX + заточенный под запрос фильтр вполне справляется на ограниченной памяти.