LINUX.ORG.RU

inline callback-функций как способ метапрограммирования

 , , , ,


1

7

Я вот задумался. Взять например функцию qsort() из стандартной библиотеки сей, ну которая принимает указатель на массив, количество элементов в этом самом массиве, размер одного элемента массива и функцию которая принимает два указателя на элементы массива, делает сравнение и возвращает int. Что если реализовать механизм встраивания всей этой фигни (за исключением разве что указателя на тот самый массив, который сортировать надо) и можно значительно ускорить процесс сортировки. Например, тут https://books.google.com/books?id=RPnWe6QKnCcC&pg=PA201&lpg=PA201&amp... говорят что std::sort быстрее qsort т.к. там компилятор может заинлайнить это. Но это не универсально. Если в компилтайме нам например неизвестен способ сравнивания двух элементов массива(т.е. мы это узнаем только на этапе выполнения), там ничего не заинлайнится. Например, как решать такую задачу : программа читает некий массив чисел(неизвестно заранее сколько, допустим читаем из файла. Пусть это будет тип float), пользователь вводит некую формулу, например y=x*x+2*(x-1) и каждое число из списка подставляются последовательно в эту формулу как x, вычисляется y и записывается потом куда-то в файл. Самый простой способ реализовать подобное на C - генерить в рантайме на основе введенной формулы некий исходник на C, компилировать его как .so, подгружать через dlopen и запустить. Желательно при этом, чтобы сам цикл с последовательным применением формулы был тоже сгенерирован внутри этой самой библиотеки, чтобы не было проседаний на каждый вызов функции. Шаблоны из плюсов тут ничем не помогут в плане оптимизации, они не могут отработать в процессе выполнения кода и что-либо там менять-добавлять. А через inline callback-функции это было бы очень просто сделать без особых проблем. Например, мы получаем от пользователя нуль-терминированную строку вида «x*x+2*(x-1)». Значит нам нужна функция, которая бы принимала указатель на строку, указатель на массив-источник, указатель на массив-назначение и кол-во элементов в массиве, которое надо по этой формуле преобразовать. Назовем эту функцию apply_ar. Получим что-то вроде

void (*apply_arr(char *str, float *src, float *dst, size_t nmemb))(void)
{
    какой-то_код;
    return somestuff;
}

Так оно просто вернет указатель на функцию, которая вообще ничего не принимает т.е. просто встроит в функцию все аргументы. Будет в итоге сгенерирована функция, которая по неким вшитым в код адресам в цикле читает флоаты, применяет вшитую в код формулу и записывает результат в заранее оговоренную область памяти. Получилось очень неуниверсально. Задачу можно изменить, например может потребоваться обрабатывать много массивов разной длины с разными адресами *src *dst но по одинаковой формуле. Тогда надо городить другую функцию, на этот раз принимающую только строку, описывающую формулу преобразования и которая возвращает функцию, принимающую указатель на источник, назначение, количество элементов. Примерно так:

void (*apply_arr(char *str))(float *src, float *dst, size_t nmemb)
{
    какой-то_код;
    return somestuff;
}
Получается что-то вроде каррирования с суперкомпиляцией, специализация программ методом частичных вычислений: http://keldysh.ru/papers/2008/prep12/prep2008_12.html#_Toc193602742

А теперь насчет callback-ов и их встраивания. Можно передавать в нашу функцию еще и код, который бы делал само вычисление по формуле. Для этого можно сделать функцию, в которую если передать например строку вида «x*x+2*(x-1)» вернет указатель на функцию вида

float calculate(float s)
{
    return x*x+2*(x-1);
}
И результат этой функции передавать в функцию apply_arr. Таким образом, если кто-нибудь захочет задавать формулу например в обратной польской записи, то мы просто напишем еще одну функцию и в случае чего будем передавать ее результат. Только тут просто указатель на функцию передать в рантайме не выйдет (нам ведь надо чтобы оно инлайнилось в функцию, которая будет сгенерирована функцией), таким образом нужно вводить некий байткод, промежуточное представление, которое потом бы компилировалось. Можно взять готовое, например формат промежуточного представления от какого-нибудь компилятора. В самой нашей функции apply_arr тогда тоже надо хранить этот байткод, и наша функция должна два эти байткода (свой и тот который в нее передается) уметь комбинировать и выдавать на выходе указатель на функцию с нативным кодом. Что самое интересное, если это все как следует продумать, можно сделать полноценный лисп поверх C, только с ручным управлением памятью. Самое замечательное, что это хоть сейчас можно в какой-то степени реализовать, только вместо байткода надо брать обычный сишный код, а для «встраивания» кода внутрь кода использовать что-то вроде
printf("some code;\n"
"%s\n"
"some code;\n");
, потом кормить этим компилятор и загружать получившийся код в исполняемую область памяти. Для более нормальной реализации всего этого, надо каким-то образом переделать компилятор. Саму специализацию можно делать как на этапе компиляции, так и в рантайме. Если промежуточное представление сделать как AST, это будет вообще замечательно. Всю программу можно собрать из этих коллбеков, и не будет ни одной нормальной привычной функции. Вся программа это функция, в которую передается массив из функций, каждая из функций может быть например оператором сложения int с int, float с float, разыменование указателя, операцией приведения типа, вызов какой-то функции. При том, необязательно все это дело инлайнить. Сами функции могут просто вызываться обычным путем, несмотря на возможность их заинлайнить. Таким образом можно переопределить любое действие, при том в рантайме (например можно сделать, что при попытке записи в или чтения из памяти по такому-то адресу, это событие логировалось. Или смотреть статистику, какие функции с какими аргументами вызываются)

Так вот, вопрос: какие могут быть сложности в реализации всего вышеописанного? Имеет ли смысл создавать такую систему метапрограммирования поверх C (если нет, то поверх чего)? В каких-нибудь языках программирования без сборки мусора, с ручным управлением памятью и с возможностью компилировать в нативный код (без всяких там интерпретаторов) уже реализовано подобное? Желательна так же возможность прямой работы с памятью, с сырыми указателями. Вообще, все это напоминает какой-то лисп, но лисп мне не подходит по вышеобозначенным критериям.

★★★★★

Последнее исправление: SZT (всего исправлений: 2)

Ответ на: комментарий от annulen

Тут не обязательно JIT. Функция может быть полностью «специализирована» под конкретные передаваемые в нее параметры еще на этапе обычной компиляции. Например если надо сделать qsort конкретно для типа float конкретно с такой-вот функцией сравнивания двух флоатов и конкретно для такого размера sizeof(float)

SZT ★★★★★
() автор топика

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

Cactus64k
()

Если промежуточное представление сделать как AST, это будет вообще замечательно. Всю программу можно собрать из этих коллбеков, и не будет ни одной нормальной привычной функции. Вся программа это функция, в которую передается массив из функций, каждая из функций может быть например оператором сложения int с int, float с float, разыменование указателя, операцией приведения типа, вызов какой-то функции.

полноценный лисп поверх C, только с ручным управлением памятью

Этот самый «массив функций» и будет камнем преткновения. Тебе надо будет вручную указывать, когда выделять под функции память, когда освобождать (как функция становится недоступна). Если добавить макросы, то аналогичная проблема по отношению к дереву AST.

В каких-нибудь языках программирования без сборки мусора, с ручным управлением памятью и с возможностью компилировать в нативный код (без всяких там интерпретаторов) уже реализовано подобное

Компиляция при выполнении? Да. Forth. Factor. Есть возможность компилировать функции (точнее «слова») при выполнении из строк.

monk ★★★★★
()

Вижу это как компиляция функции налету. Т.е брать уже готовую функцию сортировки (можно даже хранить её строкой), и вставлять туда сгенерированный своим мини-jit'ом callback. При этом разумеется учитывать адресацию (можно на ассемблере их генерировать) В любом случае jit придётся под каждую архитектуру делать разный.

mittorn ★★★★★
()
Ответ на: комментарий от Cactus64k

Тут компиляции на лету будет мало. Надо сделать так, чтобы эти встраивания функции в функцию, специализация программ методом частичных вычислений и компиляция в машинный код могли бы происходить и на этапе обычной компиляции из исходников(чтобы в рантайме на это время не тратить) и тут уже обычными костылями с printf-ом не обойтись, надо делать какой-то хитрый препроцессор. Да и сама идея хранить куски сишного кода и как-то их в компилтайме комбинировать - ущербна. Очень сложно будет делать нетривиальное преобразование кода. Например если я захочу чтобы любое(явное и неявное) приведение типа int к float сопровождалось например записью в лог-файл некоего отладочного сообщения (где и когда произошло такое приведение типа), то чтобы в кусок произвольного сишного кода добавить такие проверки, придется этот самый код изменять достаточно нетривиальным образом. Так что надо вводить какое-нибудь более удобное промежуточное представление, чтобы его было удобно преобразовывать как в рантайме, так и в компилтайме.

SZT ★★★★★
() автор топика

Самый простой способ реализовать подобное на C - генерить в рантайме на основе введенной формулы некий исходник на C, компилировать его как .so, подгружать через dlopen и запустить. Желательно при этом, чтобы сам цикл с последовательным применением формулы был тоже сгенерирован внутри этой самой библиотеки, чтобы не было проседаний на каждый вызов функции.

Это будет не только медленнее и сложнее чем std::sort, это будет даже медленнее чем qsort. Когда просто требуется сортировка, генерить исходник, компилировать его, запускать и ждать прироста скорости. Разупорись обратно.

Aswed ★★★★★
()
Ответ на: комментарий от Aswed

К тому же в процитированном куске я рассматривал не сортировку, а применение некой формулы к массиву из кучи флоатов

SZT ★★★★★
() автор топика

См. Linux's BPF JIT compiler, раздел JIT compiler. Этот компилятор, работающий в ядре Linux, может преобразовать псевдокод BPF в нативный код процессора. Если преобразование в нативный код выключено, то псевдокод интерпретируется.

Sorcerer ★★★★★
()
Последнее исправление: Sorcerer (всего исправлений: 1)

Видел когда нибудь OpenCL или шейдеры из OpenGL? Ах да, проприетарная вся из себя cuda в крайней версии уже умеет подможество с++-11 для своих kernels.

nikitos ★★★
()
Ответ на: комментарий от Aswed

Проблема этих c++ шаблонов в том, что они только компилтайм и умеют. А я хочу чтобы можно было написать один раз код, который бы мог и компилтайм, и рантайм делать.

SZT ★★★★★
() автор топика
Ответ на: комментарий от Gorthauer

Посмотри на трейты в расте. Если тебе дали ссылку, то оно в рантайме все делает, а если значение, то в compile time.

Автор же хочет уметь, при необходимости, генерить код в рантейме. Раст этого не делает.

DarkEld3r ★★★★★
()
Ответ на: комментарий от Gorthauer

Это не то. Разве там можно таким образом сделать функцию(1), которая бы генерировала функцию(2) на основе переданного байткода другой функции(3)(причем передаваемый байткод функции может быть порожден и в рантайме, и в компилтайме)? И чтобы если байткод той другой функции(3) может быть вычислен еще на этапе нормальной компиляции, то функция(1) бы отрабатывала тоже в компилтайме, при этом чтобы в бинарнике уже была откомпилированная сгенерированная в компилтайме функция(2). А функцию(1) и функцию, порождающую байткод функции(3) из бинарника вообще выкинуть можно, если они никак не задействуются при генерации кода в рантайме(генерация которого бы зависела от неких аргументов, которые могут быть получены только на этапе выполнения). Сомневаюсь, что в Rust есть такое

SZT ★★★★★
() автор топика
Ответ на: комментарий от cyanide_regime

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

SZT ★★★★★
() автор топика
Ответ на: комментарий от SZT

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

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

Cactus64k
()
Ответ на: комментарий от Cactus64k

Кстати говоря, чтобы указатель на функцию в qsort инлайнился можно исходник qsort прикладывать.

Эти исходники можно автоматически выдирать из стандартной библиотеки, например.

SZT ★★★★★
() автор топика
Ответ на: комментарий от monk

Компиляция при выполнении? Да. Forth. Factor. Есть возможность компилировать функции (точнее «слова») при выполнении из строк.

А встроенные механизмы комбинирования двух функций (заинлайнить вызов функции в функции) там есть? И в каком виде там представлен код, подлежащий компиляции?

SZT ★★★★★
() автор топика

Специализацию и partial evaluation изобрел? Ты тут осторожнее, а то о проекции Футамуры голову сломаешь.

anonymous
()
Ответ на: комментарий от SZT

А встроенные механизмы комбинирования двух функций (заинлайнить вызов функции в функции) там есть

На усмотрение компилятора.

: FOO DUP BAR BAZ

может вызвать функции BAR и BAZ, может заинлайнить их тело (если короткое). DUP почти наверняка заинлайнится.

И в каком виде там представлен код, подлежащий компиляции?

Он как и в лиспе весь подлежит компиляции (кроме того, который выполняется во время компиляции). Выбирай любой: http://rosettacode.org/wiki/Category:Forth

monk ★★★★★
()
Ответ на: комментарий от monk

На усмотрение компилятора.

Похоже что я немного не так выразил мысль. Интересует следующее. Допустим, есть функция

int do_funct(int *funct(int,int),
     int a, int b)
{
  return funct(a,b);
}
и функция
int plus(int a, int b)
{
  return a+b;
}
Можно ли в рантайме стандартными средствами скомбинировать две эти функции в одну? Не переводить в готовый машинный код, а сгенерировать некое представление(пусть даже это самое представление является обычным кодом программы), которое можно потом откомпилировать в рантайме? Как я смог определить, llvm со своим байткодом умеет делать некоторые подобные преобразования, которые например нужны для Link Time Optimization

SZT ★★★★★
() автор топика
Ответ на: комментарий от SZT

Правда вот встраивать коллбеки llvm не умеер

SZT ★★★★★
() автор топика
Ответ на: комментарий от SZT

Можно ли в рантайме стандартными средствами скомбинировать две эти функции в одну?

представление является обычным кодом программы

static inline int plus(int a, int b)
{
  return a+b;
}

int do_funct(int *funct(int,int),
     int a, int b)
{
  return plus(a,b);
}

Чтобы было проще делать такие штуки, алгоритм можно задавать макросом. Или шаблоном, если речь о С++

anonymous
()
Ответ на: комментарий от anonymous

Если в do_funct у нас может вызываться только plus, то никакой функции туда передавать не надо. И если функция plus находится в другой единице трансляции, то без применения LTO она встроена не будет.

Чтобы было проще делать такие штуки, алгоритм можно задавать макросом. Или шаблоном, если речь о С++

Сишные макросы и плюсовые шаблоны никак не помогут делать это в рантайме

SZT ★★★★★
() автор топика
Ответ на: комментарий от SZT

Норкоман, у тебя внимания на два сообщения не хватает?

сгенерировать некое представление(пусть даже это самое представление является обычным кодом программы)

Вот тебе выше было сгенерированное представление. В одной единице трансляции. Хотя, лучше даже так:

static inline int plus(int a, int b)
{
  return a+b;
}

int do_funct(int *funct(int,int),
     int a, int b)
{
#define funct plus
  return funct(a,b);
#undef funct
}

В рантайме вызываешь конпелятор и получаешь заинлайненый колбек. Если бы алгоритм был написан макросом или шаблоном, не нужно было бы морочиться с препроцессором (или вручную подменять вызов колбека на прямой вызов функции)

anonymous
()
Ответ на: комментарий от Cactus64k

Записывай, это путь к успеху.

Да, записал. Очень ценная информация, как бы теперь это не забыть

anonymous
()
Ответ на: комментарий от Cactus64k

Обвязываем си макросом. Макрос обвязываем макросом, который обвязан макросом.

А ты не пишешь на Си, так ведь? Три слоя макросов — это вполне обыденно. Ещё и отдельный кодогенератор на скриптовых языках бывает.

i-rinat ★★★★★
()
Ответ на: комментарий от anonymous

Вот тебе выше было сгенерированное представление. В одной единице трансляции. Хотя, лучше даже так:

Лучше тогда сингатуру вызова функции поменять нафиг, ибо передавать туда указатель на функцию уже не нужно. Но тогда и в коде, который эту самую функцию будет вызывать, надо что-то менять. Короче. Надо делать функцию

void *put_funct_b_in_a(void *a, void *b, int n /* указывает_какой_по_счету_аргумент_из_ф-ции_a_принимает_указатель_на_функцию_b*/)
{
  .........
  return somestuff;
}
При этом чтобы в сгенерированной таким образом функции, сингатура вызова была изменена, все передаваемые аргументы, идущие после аргумента, в котором должен был передаваться указатель на функцию сдвигаем влево на один. И например если у нас хренотень вида
int plus(int a, int b)
{
  return a+b;
}

int minus(int a, int b)
{
  return a-b;
}

int foo(int a, int b, int c, int funct1(int,int), int funct2(int,int))
{
  return funct1(funct2(a,b),c);
}
И если надо сделать из функции foo чтобы она return a-b+c то надо делать
int (*fun) (int, int, int) = put_funct_b_in_a(put_funct_b_in_a(foo, plus, 4), minus, 4)
И вот такой матрешкой из этих вложенных put_funct_b_in_a можно встроить любое количество функций, которые передаются внутрь другой функции стандартным образом. Аналогичным образом можно сделать встраивание некоторых переменных, которые передаются в функцию. Опять таки при комбинировании надо работать не с откомпилированными в машкод функциями, а с каким-то байткодом типа LLVM или промежуточным представлением из-под компилятора, типа GIMPLE или GENERIC из GCC (которые кстати очень похожи на сильно упрощенный сишный код).

SZT ★★★★★
() автор топика
Ответ на: комментарий от i-rinat

Три слоя макросов — это вполне обыденно. Ещё и отдельный кодогенератор на скриптовых языках бывает.

Ага, жаль только что макросом нельзя задефайнить макрос. В таких случаях видимо приходится кастомный препроцессор городить, или какой-нить M4 использовать

SZT ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.