> В терминах интерпретируемого языка это был бы eval,

а мне такой изврат очень хочется для компилируемого.

Дык, CL же компилируемый и eval реально компилирует в машинный код.

libtcc

Надо было использоваать CL, а не строить из себя крутого кулхацкера и не дрочить байтики.

В чём вопрос? парсишь запрос, строишь дерево, оптимизируешь при необходимости, транслируешь в машинный код. Для последнего можно использовать liblightning.

gnu lightning

.net expression trees?

> Дано: больщой массив записей (умещается в 8 GB оперативки) и некий поисковый запрос, формируемый пользователем. Хочется этот запрос скомпилировать в нативный код и дальше уже выполнять максимально быстро.

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

* Если поиск полным перебором - единственное решение, почему ты выбрал направление «оптимизировать один поток», а не распараллеливать поиск? Распараллеливаться оно должно хорошо, а сейчас уже даже нетбуки многоядерные...

* Если тебе приспичило генерить машинный код - почему бы не использовать java, там вроде был JIT? :-)

>создать над этими данными какие-нибудь индексы

ОП не говорил, что у него нет индексов, что поиск идет полным перебором и в один поток.

Компиляция запросов пользователя в какое-нибудь исполнимое представление - обычно дело для СУБД (только скорее не в машинный код, а байт-код виртуальной машины). Как минимум такое преобразование обычно правильно с точки зрения архитектуры и разделения зон ответственности (парсер - отдельно, генератор плана выполнения/программы запроса - отдельно, исполнение запроса - отдельно).

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

Ну и о преимуществах Common Lisp для кодогенерации в рантайме уже сказали.

А на каком языке, вы таки пишете? И какой язык запросов?

>Дык, CL же компилируемый и eval реально компилирует в машинный код.

Если бы мне нужны были скобочные тормоза, тормозный скобочный gc и его неуемное потребление памяти, я бы так и сделал.

>Для последнего можно использовать liblightning.

Посмотрел. Неэффективный код генерирует, однако.

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

Эффективнее, но из-за достаточно большого количества элементов в этом массиве (порядка 10 млн) размеры индексов будут некислые. Самая главная проблема в разнообразии запросов. Все требуемые индексы в памяти не поместятся, поэтому и понадобился быстрый «select»,

Если поиск полным перебором - единственное решение, почему ты выбрал направление «оптимизировать один поток», а не распараллеливать поиск?

Потому что я хочу избавиться от выборок «select FOO from TABLE where PREDICATE order by BAR offset X limit Y». Причем Y очень маленькое по сравнению с общим числом записей.

Если тебе приспичило генерить машинный код - почему бы не использовать java, там вроде был JIT? :-)

Мне не приспичило. Мне надо, чтобы реактивно прошаривало сотни мегабайт данных. Java отпадает, потому что невзирая на ее посредственную прлизводительность, задача сведется к борьбе в вызовом gc в самое неподходящее время. Я хочу облегчить себе жизнь, а не усложнить.

>Только мне кажется, что не стоит на каждый чих компилировать запрос в машинный код - вполне может оказаться, что накладные расходы на компиляцию превышают расходы на интерпретацию байт-кода или интерпретацию непосредственно запроса.

Согласен, но к сожалению

Например, если запросы очень простые и выполняются на малом объеме данных.

Не мой случай (объем данных достаточно велик и ключей поиска порядка 10).

>А на каком языке, вы таки пишете?

На C++.

И какой язык запросов?

Для начала никакого — просто некая структура данных, описывающая поисковый предикат, который по задумке компилируется и применяется к имеющемуся набору данных.

LLVM!

Пока искал информацию о lightning наткнулся в вики на example JIT'инья встроенного языка с помощью LLVM. Судя по всему, LLVM самое то.

> Эффективнее, но из-за достаточно большого количества элементов в этом массиве (порядка 10 млн) размеры индексов будут некислые.

Дадим им 1G памяти (стоимость - 1 тыр. Если ты не user:Hokum, это меньше, чем ты за день зарабатываешь) 1G / 10М = 100 байт/элемент. Для большинства типов индексов уже хватит. Если нужно очень много индексов или особо толстые индексы - тоже не проблема, пусть вместо конкретных записей можно указывать на пачки записей (например по 1 тыс штук). Тогда индекс уменьшится в #записей_в_пачке раз сразу.

Самая главная проблема в разнообразии запросов. Все требуемые индексы в памяти не поместятся, поэтому и понадобился быстрый «select»

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

> Самая главная проблема в разнообразии запросов.

man SQL-ные СУБД и использование индексов оными :-)

>Дадим им 1G памяти

Во-первых, обращение к памяти тоже не мгновенно. Чем меньше размер индекса, тем лучше.

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

Хотя мой прогноз - ускорение будет максимум в 3 раза

Вдумайся в фразу «3 раза». Если бы линукс вместо 30 секунд грузился за 10, это сделало бы меня счастливым. Вот и здесь: три раза — это очень круто. На деле будет гораздо больше, потому как количество условных переходов по сравнению с «интрепретацией байт-кода» уменьшается очень сильно.

Если нужно очень много индексов или особо толстые индексы - тоже не проблема, пусть вместо конкретных записей можно указывать на пачки записей (например по 1 тыс штук). Тогда индекс уменьшится в #записей_в_пачке раз сразу.

Мне интересно, как ты собираешься одним указателем (+ константа для указания количества) адресовать тысячу записей. В общем, поверь на слово, в моем случае каждый индекс будет занимать минимум 28 мегабайт (более реалистичная оценка — 52 мб). Таких много не налепишь.

В отличие от параллелизации, и индексов, которые откроют значительно большие перспективы.

Почему параллелизация мне не нужна, я уже объяснял. Кроме того, при 800 запросах в секунду, чего параллелить-то? Достаточно сделать CPU_CORES+1 рабочих потоков и забыть о параллельности.

А индексы из-за описанных ограничений будут строится динамически с использованием откомпилированных предикатов.

>man SQL-ные СУБД и использование индексов оными :-)

Угадай с первого раза, почему мне вообще приходится делать такой костыль? Правильный ответ начинается с буквы «M» и состоит из 5 букв.