[ФП] Примеры работы с БОЛЬШИМИ файлами

Вот, набросал небольшой примерчик: http://paste.org/pastebin/view/22005

Оптимизировать лисп, правда, я слабо умею. Думаю, там стоит в некоторых ключевых местах прописать типы переменных и проставить параметры оптимизации, но мне дальше ковырять лениво.

Криво запостилось, вот полный вариант: http://paste.org/pastebin/view/22006

Там напрашивается обыкновенная функция, нет смысла городить никакие макросы и кодогенерации

> я очень сомневаюсь что он будет отставать от Сишного варианта.

Но ты, конечно, не мерял.

Хоть кто-нибудь может объяснить, какой прок от ФП, если надо перемолотить огромный массив?

http://common-lisp.net/project/iolib/

(:use #:iolib.syscall)

Возможно. Но do-object - в данном случае do-image - это обычный тип весьма общих макросов которые покрывают многие задачи - и данный повторяющийся код тоже. Ну а так как кодогенерация трувее вызов функций (в других случаях бывает наоборот), то - вот я и привёл тот пример.

Но ты, конечно, не мерял.

Я сравнивал C и SBCL на подобных простых задачах - массивы, foreign структуры, лисповые vs. сишные структуры. И был доволен результатом - отсюда такая догадка. Я конечно не говорю, что так будет всегда - на более сложно коде Си будет намного лучше выглядеть (возможно, это зависит от очень многих параметров).

Хоть кто-нибудь может объяснить, какой прок от ФП, если надо перемолотить огромный массив?

Если что - CL не разу не ФП, а самая «жуткая» императивщина. Но влюбом случае - попытка вкорячит ФП (или CL) это попытка избавится от лищних проблем - типа мы пишем очень мало ясного кода и надеемся на «достаточно умный компилятор»(с).

> Криво запостилось, вот полный вариант: http://paste.org/pastebin/view/22006

спасибо большое, в том числе и за комментарии, ваш код гораздо приятней читать чем код от Love5an

>1. с чего ты носишься с этим 2.5Гб? я тебе говорил про 0.5Гб

Ты сказал очевидную глупость, и уже два раза получил внятное объяснение - 536870911 это максимальное колличество элементов в массиве.

2. man PAE

Ну так прочитай его, не позорься.

> Я сравнивал C и SBCL на подобных простых задачах - массивы, foreign структуры, лисповые vs. сишные структуры. И был доволен результатом

доволен результатом

Афигеть.

попытка вкорячит ФП (или CL) это попытка избавится от лищних проблем - типа мы пишем очень мало ясного кода

Неплохая отмазка для соло-программиста.

еще один «одаренный»

Ты сказал очевидную глупость, и уже два раза получил внятное объяснение - 536870911 это максимальное колличество элементов в массиве.

напряги свою извилину - у нас массив __БАЙТ__, и чтоб убрать это ограничение - Love5an предложил __КОСТЫЛЬ___

Ну так прочитай его, не позорься.

это называется - ляпнуть глупость с умным видом, ты не знаешь, что на 32-й системе в данном случае программа на С сможет себе спокойно «отгрызть» 2.5Гб (с) памяти, не переживая за остальные процессы? хотя учитывая твое сообщение - не знаешь

> у нас массив __БАЙТ_

Эээ, откуда инфа? ТС ясно сказал: «глубина пикселя 32 бита».

> Эээ, откуда инфа? ТС ясно сказал: «глубина пикселя 32 бита».

image[row*width+col][c]

доволен результатом

Афигеть.

Ага - я тоже удивился. Там были сравнимое время (память сравнить не возможно :)) +/- 10%

попытка вкорячит ФП (или CL) это попытка избавится от лищних проблем - типа мы пишем очень мало ясного кода

Неплохая отмазка для соло-программиста.

Это не отмазка. Я что-то не видел чтобы для решения задачи обработки массива (обычный тип данных, обычные алгоритмы) собиралась команда из десяти одарённых мужей и начиналось кодописание - один программист вполне справится с такой задачей (другой возьмёт его API и буде делать что-то ещё).

> Я что-то не видел чтобы для решения задачи обработки массива (обычный тип данных, обычные алгоритмы) собиралась команда

А ты почитай начальное сообщение топика.

из десяти одарённых мужей

Здесь ХЗ

>>> у нас массив __БАЙТ_

Эээ, откуда инфа? ТС ясно сказал: «глубина пикселя 32 бита».

image[row*width+col][c]

И что с того? Не говоря о том, что это код из просто другой программы.

А ты почитай начальное сообщение топика.

Уже, там телескопы, обработка изображений и всё такое - явно не одному человеку это делать. Но изобрести представление базовых данных (то как обращаться с этими файлами - как и в какие структуры данных их «закачивать») - это должен сделать одни человек (видимо TC :). В общем, если есть такой импульс всё переписать с Си на более высокоурож^Wуровневом языке то варианты:

1) Остаться на си, использовать mmap.

2) Использовать кодогенерацию, CL.

3) Брать тот же CL но строить FFI интерфейс к си (можно и не CL в этом случае, если не хочется).

4) Посмотреть в сторону Lazy IO (это вряд ли, просто пришло на ум).

> И что с того?

хорошо, покажи мне как ты эффективно будешь работать с uint32_t( ARGB ) отдельно по каждому каналу, в С можно взять указатель на image + c, и дальше шагать по смещению, а как ты это сделаешь для (list m n) :element-type 'u32, про который идет речь?

Не говоря о том, что это код из просто другой программы.

как бы ТС сказал, что у них все также - вплоть до макросов

> если есть такой импульс всё переписать с Си на более высокоурож^Wуровневом языке то варианты:

...

2 bp 4-х вариантов - Лисп. Почему я не удивлен?

> Хоть кто-нибудь может объяснить, какой прок от ФП, если надо перемолотить огромный массив?

Я могу. Никакого.

Лисп. Почему я не удивлен?

ты видишь то что хочешь увидеть (как и я)

> один программист вполне справится с такой задачей (другой возьмёт его API и буде делать что-то ещё).

Отличный план. Потом программист нумер два захочет поправить одну мелочь в реализации «библиотечной» функции, откроет код... тут ему и пиздец. Старая чукотская ловушка [s]на тараканов[s] на плюсистов.

> откроет код... тут ему и пиздец. Старая чукотская ловушка [s]на тараканов[s] на плюсистов.

это совершенно не зависит от языка

>> Лисп. Почему я не удивлен?

ты видишь то что хочешь увидеть

Хм. А что там реально?

Тут, кстати, можно совсем упростить задачу, если разделить файл на три, по цветам, перед обработкой. Ф-ии сбора статистики будут полностью одинаковы и не будет проблем с не 1чными сдвигами.

(read-file-into-vector "/mnt/hard-1/gentoo-lcd.iso" :element-size 32))

а) занимал в памяти столько же места сколько на диске

да. Всего до 2 гб, т.е. 512 мега пиксилей.

б) доступ к элементам был быстрый (О(1))?

тоже да.

Скорость считывания зависит от скорости шлейфоф - есть смысл попробовать mmap, но в этом случае придётся переехать на foreign массивы, но тут есть и плюс - их GC не контролирует.

read-file-into-vector (или что-то в этом роде) это библиотечная функция из alexandria.

А что там реально?

Для меня - что CL лучше всего подойдёт для быстрой разработки и для кодогенерации (просто макросы). Писать основные вещи на Си и делать FFI можно хоть на Python. Ну а Lazy IO это Haskell. Вот три вполне себе высокоуровневых языка. В первом случае мы имеем специфичный подход, который требует обмолотки массивов на самом лиспе (А зачем брать CL? Там всё лучше делать своими инструментами). Во втором - обычная работа с массивами остаётся обычной (на Си), Python (или делать используя CPython)- для каких-то удобств. И третий вариант - тоже специфичный подход со своими массивами и с ленивым IO.

А если файл размером 2 гб? Получится 8 гб (оригинал + 3 копии), если конечно не хитрить. Тут видимо смысл в том, что должен быть один (большой) файл который мапится в память и обрабатывается. Копирование его - это обязательный оверхед ресурсов.

Один файл в 2 гб даст два в 512мб (каналы R и B) и один 1гб (канал G), т.е. общий объём увеличится в два раза. Да, на разделение уйдёт время, но можно будет получить профит в виде юнификации алгоритмов обработки и их упрощения: сбор статистики, например, для канлов можно будет делать одной ф-ией (нет проблем с офсетами и шагом 1/2 для разных каналов). Специфика остальных алгоритмов не ясна, но вполне вероятно разделение и других обработок на канальной основе.

> Да, на разделение уйдёт время, но можно будет получить профит в виде юнификации алгоритмов обработки и их упрощения: сбор статистики, например, для канлов можно будет делать одной ф-ией

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

а на С++ это будет еще быстрее - так как в приведенном вначале примере используется переменная colors( равная 3 или 4 как я понял ), на С++ пишется все шаблонами - и вместо colors получаем везде константу ( т.е. по два варианта каждой функции )

Балбес. Я это и пишу безотносительно ЯП, везде от такого разделения можно получить профит, и в си в т.ч. Время можно не терять, если совмещать разделения с другими стадиями обработки.

> Балбес

приятно познакомится

Я это и пишу безотносительно ЯП

тогда ты еще глупее, чем я думал

везде от такого разделения можно получить профит

какой профит? в чем профит? на каких задачах это даст выигрыш? я тебе четко сказал на чем проигрываешь ты, теперь ты назови задачу, где ты получиш выигрыш

>> И что с того?

хорошо, покажи мне как ты эффективно будешь работать с uint32_t( ARGB ) отдельно по каждому каналу,

Не уходи от вопроса - с чего ты взял, что у ТС по байту на пиксель?

в С можно взять указатель на image + c, и дальше шагать по смещению, а как ты это сделаешь для (list m n) :element-type 'u32, про который идет речь?

Я в гробу видел Лисп.

Не говоря о том, что это код из просто другой программы.

как бы ТС сказал, что у них все также - вплоть до макросов

Как бы ТС сказал, что у них код похож (тот же BAYER паттерн). Про разрядность он сказал тоже: 32 бита на пиксель.

Спасибо большое за пример, и что не западло возиться с новичками :) Код на первый взгляд, конечно, громоздок (особенно по сравнению с сишными несколькими строчками malloc / fopen / for ... fread / fclose). Но будем надеяться что принесёт профит в дальнейшем, за счёт использования макросов, first order functions и так далее. Кстати функция доступа к элементам массива, aref если не ошибаюсь, есть-ли гарантия что она работает за O(1) время?

А то что массивы 2,5Гб не влезают на 32-битной системе - это конечно плохо :( Счётному кластеру года три, он конечно не самый современный но и не древний вовсе. Когда конструировали кластер, архитекторы дали чёткое «одобрямс» 32-битным узлам. Никакого смысла делать 64-битные не было: программы на Си без проблем работают со всеми 4ГБ ОЗУ, так что картинка влезает целиком. Да и применение 64-битных Xeon'ов в то время привело бы к удорожанию кластера где-то на 30%, а это извините десятки тысяч $. Мы не госконтора, копеечку приходится считать :)

А это только в SBCL такая проблема, с 512МБ массивами? Я бы мог попытаться запустить программу на Clozure CL или даже Аллегро, все эти #+sbcl #-sbcl там прокатят?

> на 32битных системах 2.5 гигабайтный массив в памяти это нонсенс?

Ну кстати это уже перегиб, я же говорю, у нас сейчас программы на Си нормально всасывают такой массив и не поперхиваються. Память благополучно mlock()'аеться, свап не задействован, всё в порядке, никаких нонсенсов :)

> А нельзя ли при выгрузки данных с телескопа сохранить их сразу в более удобном виде?

С которым потом будет приятнее работать.

Разумеется, потом работает BAYER алгоритм аналогичный тому, что есть в RAW-конвертерах, и исходник превращаеться в обычное цветное изображение. Конечно, насколько может считаться «обычным» изображение с 32 бит, уже на _канал_, а не на пиксель :)

Но есть некоторые важные статистики, которые надо посчитать раздельно по каналам. И их выгоднее считать по исходной «мозайке», нежели по полноцветному результату, полагаю не надо объяснять почему.

> то что массивы 2,5Гб не влезают на 32-битной системе - это конечно плохо :(

есть разбиение 3G/1G - его тоже не хватает?

> Кстати, Ignatik, объясните мне, непутевому, как у вас профессиональная ПЗС-камера дает RAW-изображения, да еще цветные о_О? Во-первых, научная матрица цветной быть по-определению не может

Странные у вас определения :) Ну да, я можно сказать смешал несколько задач в одну. Для буквоедов навроде вас поясняю. Оптические приборы, с которыми приходится работать, совершенно разнообразные. Есть и такие «телескопы», которые смотрят не в космос, а на матушку-Землю :) ака satellite imaging. Может вы и удивитесь, но там старый добрый BAYER, только сто- и тысячемегапиксельных порядков. А ПЗС телескопов в обсерваториях, да, выдают FITS.

Ну так тем более, MIDAS вам в руки. Я, правда, им не пользуюсь (хоть и астрофизик), т.к. у меня другие занятия: проектирование и моделирование аппаратуры, разработка систем управления и удаленного доступа.

У нас, внезапно, тоже проектирование и тестирование. И результаты рассчётов обычно выдают не характеристику изображения, а характеристики матрицы. Но это уже не столь важно :) поэтому кстати и приходится писать математику самому, MIDAS немножко для других целей

>> но Sclala тут не подходит по понятным причинам :(

ну кстати, а почему?

Потому что JVM = оверхед по драгоценной памяти и быстродействию. Хотя ради спортивного интереса можно реализовать загрузку картинки и составление гистограмм на Java и Scala, посмотреть, какой конкретно оверхед будет. Не хотите заняться? :)

> Вот, набросал небольшой примерчик:

Вам тоже спасибо огромное. Особенно за демонстрацию применения макросов для кодогенерации вложенных for-циклов, многое становиться понятным

>> то что массивы 2,5Гб не влезают на 32-битной системе - это конечно плохо :(

есть разбиение 3G/1G - его тоже не хватает?

Что за разбиение? Не въехал, честно говоря. А невлезающие массивы - так это они в SBCL не влезают, «конечно плохо» это я имел в виду, что у SBCL для наших задач на нашем железе нет перспектив :(

Уточнение насчёт конфигурации изображения. Исходник (BAYER) имеет по 32 бита на пиксель, причём пиксели только красные/синие/зелёные (см. картинку из Википедии). После конвертации получается изображение той же размерности с 32 битами на _канал_, оно занимает уже под 8ГБ и это совсем отдельная песня, для них у нас есть пара специальных узлов

>> есть разбиение 3G/1G - его тоже не хватает?

Что за разбиение? Не въехал, честно говоря

Ну, в комплекте с вот этим:

невлезающие массивы - так это они в SBCL не влезают

это неважно.

P.S. жаль мне твоих коллег

Есть и такие «телескопы», которые смотрят не в космос, а на матушку-Землю :) ака satellite imaging.

И ЛОР - основное место тусовки специалистов по сабжу :)

так это они в SBCL не влезают, «конечно плохо» это я имел в виду, что у SBCL для наших задач на нашем железе нет перспектив :(

Почему не влезают? Можно же начать резать (или юзать foreign массивы - там ограничение только на то сколько сможет отдать malloc).

Ни хера себе четыре действия. Я как увидел, то офигел. Такие сраные четыре действия засунь себе знаешь куда. Но нет, я говорю тебе засунуть их себе не голословно, а подробно обосновывая почему ты должен их туда себе засунуть. Потому, что если ты собрался тут пропагандировать ФП и CL, то этод код - последний гвоздь в могилу лиспа. После этого кода, заслуживающего первые места в хит-парадах на govnokod.ru ни один человек, заинтересовавшийся в лиспе даже и думать не станет его изучать, а тем более использовать в продакшне. А эксперты еще спорят, какой стиль именования переменных лучше читаем для человеческих глаз и более удобен в плане поддержки. Да тут верх нечитаемости, это инородно и для глаз, и для мозга и для машины. Понимаешь - программирование должно быть между человеком и между машиной. А тут и далеко от человека с нормальным способом мышления и от машинного кода. Я годами такой дисгармонии не видел. Это пылает маргинальностью. Такой код надо жечь напалмом.

Таких четырех действий в жизни не видел. При том что у тебя до того еще гора какого-то кода написана. Допиши еще одну функцию, в ней вызови read-u32-matrix и скажи что сделал все одно действие. А мы посмеемся.

class matrix{
    unsigned *buffer;
    int m, n;
public:
    matrix(const char* filename, int _m, int _n): m(_m), n(_n)
    {
        ifstream file(filename);
        buffer = new unsigned[m*n];
        file.read(reinterpret_cast<char*>(buffer), m*n*sizeof(unsigned));
    }

    unsigned& get(int i, int j){
        return buffer[i*n+j];
    }

    ~matrix(){
        delete[] buffer;
    }
};

И можешь мне не рассказывать о четырех действиях. Они все сдесь. Но меньше строчек, меньше букв и меньше непонятных манипуляций и вызовов функций, которые ничего не говорят вменяемому программисту. Я тебе для улучшеной читаемости даже reinterpret_cast вставил, чтобы было понятно «reinterpret и cast». Тут сокращенно только ifstream.

А у тебя без угубленного курса квантовой физики не разберешься что такое declaim, logior, ash, logand, body, -sbcl, +sbcl, ignore, start-var, end-var и т.д. Тут даже различить нельзя где твои индентификаторы, а где готовые.

Такого упоротого я еще не видел. При том что до вчерашнего дня нормально относился к лиспу. Но вывалить такой треш на форум и умничать что это очень читаемо и кратко, тупо лгать не прикрываясь, не - это ты уже слишком.

Почему не влезают? Можно же начать резать (или юзать foreign массивы - там ограничение только на то сколько сможет отдать malloc).

32х битное приложение всё равно не получит больш 3гб, а на практике будет порядка 2.7гб. По сравнению 2.5гб пирост всё равно будет незначительным.

Спасибо. Найден минорный баг ЛОРа. Ты написал сообщение, потом удалил и мой коммент опять выпал на первое место в списке Последние сообщения )

>Код на первый взгляд, конечно, громоздок (особенно по сравнению с сишными несколькими строчками malloc / fopen / for ... fread / fclose)

Это на первый взгляд только. Потому что имена операций в CL длинные. Плюс тут несколько моментов.

Первый - в with-array-data я применил небольшую оптимизацию для SBCL(вот эти вот #+sbcl #-sbcl это навроде как #IFDEF). Дело в том, что в нем любой многомерный, или расширяемый(adjustable), или с указаталем заполнения(fill-pointer), массив имеет внутренний вектор данных, который есть вектор с таким же типом элементов, как и у исходного массива, но с минимальной структурой(ну, буквально, метка типа в нем и длина)(массивы с такой минимальной структурой являются подтипами simple-array, а с simple-array работа в SBCL, и не только в нем, идет гораздо быстрее, чем с векторами/массивами со сложной структурой).

Для других реализаций у меня там создается «array slice», т.е. просто вектор-отображение на данные исходного массива.

Вообще, именно _вектор_ нужен для того, чтобы применить к нему read-sequence, функцию блочного чтения из потока(можно, конечно, не применять все эти манипулиции, и просто заполнять матрицу, считывая поэлементно, но это было бы гораздо медленнее). Собственно все эти манипуляции нужны потому что кастов к (void*) и другого подобного говна в CL нет(т.к. высокоуровневый язык, и сильная типизация).

Второй момент - повсюду расставлены декларации(declare) типов. Это для того, чтобы компилятор смог генерировать более эффективный код.

Третий - у меня там еще дополнительная проверка на валидность размера потока("(if (= (file-length in) (* m n)) ...")

И последний - возможная необходимость вот этого вот переворачивания байтов, т.к. лисп считывает из потока с типом (unsigned-byte 32) именно числа в соответствующем системе endianness.

Т.е. если по-тупому, и не учитывать endianness, можно вот так упростить код:

(defun read-u32-matrix (filename m n)
  ;;Открываем бинарный файловый поток, состоящий из 32битных
  ;;беззнаковых целых. WITH-OPEN-FILE это RAII-стайл макрос
  ;;для работы с файловыми потоками:
  (with-open-file (in filename :element-type 'u32)
    ;;LET* - форма связывания переменных.
    ;;Тут мы объявляем две переменных, собственно матрицу,
    ;;переменную array
    ;;           (функцией make-array с лиспе создается массивы,
    ;;            в данном случае - двумерный массив 32битных целых),
    ;;и переменную contents(вектор-отображение данных array,
    ;;                      аргумент :displaced-to указывает, что мы не
    ;;                      выделяем память под данные, а берем их из другого
    ;;                      массива)
    (let* ((array (make-array (list m n) :element-type 'u32))
           (contents (make-array (* m n) :element-type 'u32
                       :displaced-to array)))
      ;;считываем данные из потока в contents
      (read-sequence contents in)
      ;;возвращаем сам массив
      array)))

>А то что массивы 2,5Гб не влезают на 32-битной системе - это конечно плохо

Не влезают не массивы больше 512 мб, еще раз, а именно массивы больше MOST-POSITIVE-FIXNUM элементов(ну вообще-то, если точнее, больше ARRAY-TOTAL-SIZE-LIMIT, который в SBCL есть где-то (most-positive-fixnum - 3) элементов). Т.е. массив из 4байтовых целых может занимать, ну вплоть до 2 гигабайт.

Ну если это прям вот так вот плохо, что не 64битная система, то можно, как уже выше предложили, использовать сишные массивы, написав над ними к-либо минимальную структуру-обертку. Попозже напишу пример.

>Кстати функция доступа к элементам массива, aref если не ошибаюсь, есть-ли гарантия что она работает за O(1) время? Да, она работает за константное время. Более того, при соответствующих декларациях это вообще всего пара инструкций(пример для sbcl-x86-32):

(defun foo (a i j)
  (declare ;;a - матрица произвольных размеров,
           ;;способная хранить любой тип элементов(T)
           (type (simple-array T (* *)) a)
           ;;i и j - числа типа fixnum
           (type fixnum i j)
           ;;указание оптимизации для компилятора. 3 - максимум.
           (optimize (speed 3) (space 0) (safety 0) (debug 0)))
  (aref a i j))

; disassembly for FOO
; 241C86CA:       8B421D           MOV EAX, [EDX+29]          ; no-arg-parsing entry point
;       CD:       C1FF02           SAR EDI, 2
;       D0:       0FAFF8           IMUL EDI, EAX
;       D3:       01F7             ADD EDI, ESI
;       D5:       8B4209           MOV EAX, [EDX+9]
;       D8:       8B543801         MOV EDX, [EAX+EDI+1]
;       DC:       8BE5             MOV ESP, EBP
;       DE:       F8               CLC
;       DF:       5D               POP EBP
;       E0:       C3               RET

Ну тут дело в том, что современныt реализации CL используют fixnum для хранения размера массива.
Это издержки динамической типизации.
FIXNUM, как я уже говорил, это целое из машинного слова, часть которого отдана под метку типа. Числа размером больше FIXNUM в CL это BIGNUM, т.е. длинные целые, т.е. там уже структура данных, выделение памяти в куче, боксинг, анбоксинг и т.п.