Comments 93
Интересен вариант с генерацией test_predicate с помощью LLVM в рантайме — может быть быстрее и гибче.
Как насчёт такой оптимизации?
static inline unsigned char test_predicate_12(struct T_cash_account_row const*const __restrict row, struct T_range_filters const*const __restrict range_filters)
{
const char p0 = (row->age - range_filters->begin.age) <= (range_filters->end.age - range_filters->begin.age);
const char p1 = (row->code - range_filters->begin.code) <= (range_filters->end.code - row->begin.code);
return p0 & p1;
}static inline size_t search_12(struct T_cash_account_row const*const __restrict array_ptr, const size_t c_array_size, struct T_cash_account_row *const __restrict result_ptr, struct T_range_filters const*const __restrict range_filters)
{
size_t result_size = 0;
size_t i; /* loop index */
for(i = 0; i < c_array_size; ++i) {
result_ptr[result_size] = array_ptr[i];
result_size += test_predicate_12(array_ptr + i, range_filters);
}
return result_size;
}
Вы хоть попробуйте прежде, чем писать :)
Во-первых, у типичных запросов достаточно маленькая селективность, поэтому выгодней делать && с условным переходом, чем &. Аналогично и с записью в массив — быстрее с условным переходом. Этот теоретический шаблонный совет о бездумном избегании условных переходов тянется ещё со времен длиннющих конвейеров.
Во-вторых, ваш вариант возвращает неверное число строк :)
Это помимо множества синтаксических ошибок.
В свое время был написан bench с несколькими десятками вариантов. Так что, чтобы вы ни написали — скорее всего уже проверялось. Но вы ещё попробуйте.
Во-первых, у типичных запросов достаточно маленькая селективность, поэтому выгодней делать && с условным переходом, чем &. Аналогично и с записью в массив — быстрее с условным переходом. Этот теоретический шаблонный совет о бездумном избегании условных переходов тянется ещё со времен длиннющих конвейеров.
Во-вторых, ваш вариант возвращает неверное число строк :)
Это помимо множества синтаксических ошибок.
В свое время был написан bench с несколькими десятками вариантов. Так что, чтобы вы ни написали — скорее всего уже проверялось. Но вы ещё попробуйте.
>Казалось бы, что здесь можно ещё ускорить и оптимизировать при полном проходе без индексов?
Сменить AoS на SoA.
Сменить AoS на SoA.
Знатный наброс :)
Также я бы хотел увидеть красивое решение для инициализации массива с 32 специализированными функциями поиска, для выбора оптимальной реализации в рантайме.
Также, интересны какой эффект будет при отказе от битфилдов.
Неплохо, но есть небольшая проблемка – C-разработчикам придется вручную создать эти 32 функции, нигде в них не ошибиться перебирая все варианты и при любом изменении числа и имен полей менять нужные функции.В С есть макросы и инлайновые функции, так что не все так плохо, как вы пытаетесь показать.
Также я бы хотел увидеть красивое решение для инициализации массива с 32 специализированными функциями поиска, для выбора оптимальной реализации в рантайме.
Также, интересны какой эффект будет при отказе от битфилдов.
для поиска, я бы использовал hash_table. Есть много разных реализаций.
Вопрос был не про то, смотрите — автор создает кучу специализированных функций, из них надо в рантайме выбрать наиболее подходящую для входных данных. Решение влоб — инициализировать таблицу указателей на специализированные функции вручную, но это не красиво.
В своей другой статье автор предлагает решение основанное на инициализации таблицы в рантайме при помощи рекурсивной шаблонной функции, в принципе годный вариант.
В своей другой статье автор предлагает решение основанное на инициализации таблицы в рантайме при помощи рекурсивной шаблонной функции, в принципе годный вариант.
Годный run-time вариант на C во второй главе ускоряет только в 1.6-1.8 раза, против в 3.5-5.3 раза на C++. Если готовы купить в 2-3 раза больше/дороже серверов и заплатить за оборудование вместо 2 млн, 6 млн, то C годный вариант :)
Кстати, если читали внимательно, то и в этой статье сравнивается run-time вариант на C в конце второй главы, который только замедляет выполнение.
Кстати, если читали внимательно, то и в этой статье сравнивается run-time вариант на C в конце второй главы, который только замедляет выполнение.
Просто вы не умеете его готовить (с)
Пустословие. Выкладывайте своё решение, сравним :)
Сначала сделайте так, чтобы ваш тест нормально собирался, и вобще соответствовал принципам правильного бенчмарка. Тогда может быть кто-то и захочет с вами померяться.
Научитесь пользоваться компилятором GCC 4.7.2 на ideone.com, тогда может кто-то захочет с вами дискутировать.
Справедливости ради замечу, что действительно в моем примере нет полноценного бенчмарка. Он будет в третье статье, в более реальном примере с Ordered Hash/IOT/IOS.
Справедливости ради замечу, что действительно в моем примере нет полноценного бенчмарка. Он будет в третье статье, в более реальном примере с Ordered Hash/IOT/IOS.
Использовать hash_table для поиска по диапазонам нескольких полей — круто!
Прочитайте последнюю главу второй статьи, там упоминается кое-что об упорядоченным хэш-индексе.
Прочитайте последнюю главу второй статьи, там упоминается кое-что об упорядоченным хэш-индексе.
В С есть макросы и инлайновые функции, так что не все так плохо, как вы пытаетесь показать.
Что значит есть инлайновые функции, как будто я их здесь не использовал при сравнении?
Ну, а использовать макросы вместо шаблонов, что зря теоретизировать, приведите решение на них и вы увидите почему так делать нельзя никогда.
Также я бы хотел увидеть красивое решение для инициализации массива с 32 специализированными функциями поиска, для выбора оптимальной реализации в рантайме.
Если вам не лень писать 32 специализированных функций на C, выкладывайте пример. А потом вам вдруг приходит задача добавить 2 поля, и вы пишите уже 128 функций :)
На C++ шаблоны пишутся быстрее и гораздо гибче при изменении числа полей и их названий.
Также, интересны какой эффект будет при отказе от битфилдов.
Это оффтопик. Но что вам мешает попробовать?
Что значит есть инлайновые функции, как будто я их здесь не использовал при сравнении?Подумайте, как инлайновые функции можно использовать в задаче кодогенерации (подсказка: устранение константных выражений при оптимизации).
Ну, а использовать макросы вместо шаблонов, что зря теоретизировать, приведите решение на них и вы увидите почему так делать нельзя никогда.
Если вам не лень писать 32 специализированных функций на C, выкладывайте пример. А потом вам вдруг приходит задача добавить 2 поля, и вы пишите уже 128 функций :)Я не собираюсь вам ничего доказывать. Это вы тут доказываете превосходство C++, а мне такая постановка вопроса кажется скучной — для разных задач я использую и Си и C++ и еще штук пять других языков. На случай, если вы считаете всех собеседников по умолчанию идиотами, прошу ознакомиться.
Также, интересны какой эффект будет при отказе от битфилдов.Это оффтопик. Но что вам мешает попробовать?
У меня ваш пример не собирается — clang 4.2 просто падает.
На счет оффтопика категорически не согласен. Во-первых, обращение к битфилдам не бесплатное (нужно применять маски и делать сдвиги), и на таком микробенчмарке это может быть заметно. Во-вторых, это нас вплотную подводит к мысли — какое влияние на производительность окажет увеличение размера элемента? А что если элемент «размазан» по памяти (например имеет два строковых поля, строки аллоцируются отдельно от самого элемента)? Стоимость кеш-промаха сотни тактов. Вам в самом деле надо искать по неупорядоченному списку элементов с целочисленными полями, все поля сумарно влезают в 64 бита? В противном случае, ваши оптимизации станут неэффективны.
Вот, интересная статистика.
Подумайте, как инлайновые функции можно использовать в задаче кодогенерации (подсказка: устранение константных выражений при оптимизации).
Вы у меня видели не inline функции, кроме main() и тех, что должны быть виртуальными?
я использую и Си и C++ и еще штук пять других языков
Использовать языки и знать их — это разные вещи.
«Сами придумали — сами обиделись». Только вы могли придумать использовать для скоростного поиска строки аллоцируемые отдельно от элемента.
Я не считаю никого идиотом. Мне все равно. Меня интересуют только решение и результат.
Разница в том, что мой аргумент рабочий пример и результат тестов, а ваш аргумент, что вам скучно. И от скуки пишите что попало.
Т.е. вы обсуждаете то, что даже не смогли скомпилировать? Попросите кого-нибудь скомпилировать за вас. Могу только доказать, что это возможно: GCC 4.7.2 на ideone.com
Когда осилите скомпилировать и предложите свой вариант — продолжим.
Ответ не в тему. Подумайте-подумайте, гуру шаблонов вы наш.Подумайте, как инлайновые функции можно использовать в задаче кодогенерации (подсказка: устранение константных выражений при оптимизации).Вы у меня видели не inline функции, кроме main() и тех, что должны быть виртуальными?
Только вы могли придумать использовать для скоростного поиска строки аллоцируемые отдельно от элемента.Ну-ну успокойтесь же) Представьте, что у вас два строковых поля, как бы вы их не стали хранить, без кеш-промаха тут не обойдется.
Разница в том, что мой аргумент рабочий пример и результат тестов, а ваш аргумент, что вам скучно. И от скуки пишите что попало.
Ваш аргумент — синтетический тест. Мой аргумент — я знаю об этой теме не меньше вашего.
Впрочем, если вы не способны к нормальному общению, и стремитесь любую беседу превратить в бокс по переписке, то я пожалуй от дальнейшего участия воздержусь.
Куда уж мне до вас знающего C, C++ и ещё 5 языков программирования.
Вы действительно думаете, что я сейчас буду гадать, что за фантазии пришли в вашу голову, которые вы стесняетесь прямо сказать в виде кода?
Спасибо Кэп.
Вы действительно думаете, что я сейчас буду гадать, что за фантазии пришли в вашу голову, которые вы стесняетесь прямо сказать в виде кода?
Только вы могли придумать использовать для скоростного поиска строки аллоцируемые отдельно от элемента.
Ну-ну успокойтесь же) Представьте, что у вас два строковых поля, как бы вы их не стали хранить, без кеш-промаха тут не обойдется.
Спасибо Кэп.
Куда уж мне до вас знающего C, C++ и ещё 5 языков программирования.У меня еще и ВО есть)
Давайте подведем итоги?
- В статье представлена техника для генерации специализированных вариантов функций, с целью сократить число условных переходов, методами шаблонного метапрограммирования на C++.
Если рассматривать статью как описание метода решения практической задачи — откровенно слабо, так как не учитывает другие важные факторы, вносящие вклад в производительность (те же особенности работы кеша), а также не дает нормального описания решаемой задачи.
Если рассматривать статью исключительно в контексте сравнения возможностей языков Си и C++, то все более менее ок. Задача специально подобрана так, чтобы лучше показать превосходство C++. Решение на Си или потребует кодогенерации или будет сложнее (LLVM) или будет хуже поддерживаемым чем на C++ (макросы), я с вами согласен.
Скажу больше. Эта статья написана только для того, чтобы проще было понять вторую статью.
Вторая статья о кросс-аппаратной оптимизации через шаблоны, и очень странно ждать рассказы об аппаратно-зависимых кэшах.
К тому же строка занимает 8 байт и выровнена по границам кэшей.
Исходя из выше сказанного, все ваши голословные придирки не подтвержденные кодом, и воспринимаются как не уместные.
Конкретно в данной постановке задачи поиска полным проходом, с данным числом и типами полей, prefetching-cache ничего не даст, о чем написано в первой главе.
Вторая статья о кросс-аппаратной оптимизации через шаблоны, и очень странно ждать рассказы об аппаратно-зависимых кэшах.
К тому же строка занимает 8 байт и выровнена по границам кэшей.
Исходя из выше сказанного, все ваши голословные придирки не подтвержденные кодом, и воспринимаются как не уместные.
Конкретно в данной постановке задачи поиска полным проходом, с данным числом и типами полей, prefetching-cache ничего не даст, о чем написано в первой главе.
При чем тут префетч? Нужно понимать, что с чуть менее cache-friendly структурой данных, чем что-то с целочисленными полями, умещаюшимися в 8 байта, значимость вычислительных оптимизаций упадет из-за cash miss. Подавляющее число реальных данных — именно такие.
Поэтому я и говорю — пример игрушечный. Код есть ниже.
Поэтому я и говорю — пример игрушечный. Код есть ниже.
Послушайте, есть реальные проекты с реальными данными, на которых это реально дает существенный профит.
Не упадет, вы не знаете что такое IOT и стратегия IOS, вы плохо в этом разбираетесь потому, что подобные оптимизации применяются для последовательного доступа после сужения поиска при Index Range Scan используя IOT/IOS. Мы уже убедились, у вас может упасть что угодно, хоть компилятор, хоть доступ к строкам, которые вы додумались аллоцировать отдельно. Надеюсь больше не надо объяснять, что аппаратно зависимые вещи не предмет статей о кросс-аппаратной оптимизации через шаблоны?
Не упадет, вы не знаете что такое IOT и стратегия IOS, вы плохо в этом разбираетесь потому, что подобные оптимизации применяются для последовательного доступа после сужения поиска при Index Range Scan используя IOT/IOS. Мы уже убедились, у вас может упасть что угодно, хоть компилятор, хоть доступ к строкам, которые вы додумались аллоцировать отдельно. Надеюсь больше не надо объяснять, что аппаратно зависимые вещи не предмет статей о кросс-аппаратной оптимизации через шаблоны?
Послушайте, я вас целый день пытаю на предмет практической применимости а вы все упражняетесь в остроумии. Так держать!
Вы действительно думаете, что я сейчас вам вышлю ТЗ реальной задачи, где все это решено и дам VPN в банки, где это практически применено, что у вас в голове вообще происходит?
А просто сказать СУБД/банковская аналитика и не вставать в позу нельзя было?
в соседней теме автор ведь ответил давно habrahabr.ru/post/182428/#comment_6338862
На правах взгляда со стороны:
>Ваш аргумент — синтетический тест. Мой аргумент — я знаю об этой теме не меньше вашего.
Если честно, то даже самый синтетический тест — куда более весомый аргумент, чем «яавтор статей, текстов и постов знаю пять языков, и ваще очень умный».
Вы бы куда меньше времени потратили на написание своего правильного теста, чем на голые комментарии с пустой критикой.
Кстати, то, что компилятор «просто падает» на каком-либо коде — это камень в первую очередь в огород компилятора. И не просто камень, а здоровенный булыжник. Даже если код написан с нарушением всех мыслимых и немыслимых стандартов, компилятор падать не должен.
>Ваш аргумент — синтетический тест. Мой аргумент — я знаю об этой теме не меньше вашего.
Если честно, то даже самый синтетический тест — куда более весомый аргумент, чем «я
Вы бы куда меньше времени потратили на написание своего правильного теста, чем на голые комментарии с пустой критикой.
Кстати, то, что компилятор «просто падает» на каком-либо коде — это камень в первую очередь в огород компилятора. И не просто камень, а здоровенный булыжник. Даже если код написан с нарушением всех мыслимых и немыслимых стандартов, компилятор падать не должен.
стати, то, что компилятор «просто падает» на каком-либо коде — это камень в первую очередь в огород компилятора. И не просто камень, а здоровенный булыжник. Даже если код написан с нарушением всех мыслимых и немыслимых стандартов, компилятор падать не должен.
Рекурсивное инстанцирование шаблонов глубиной в 5000 это весьма серьезный стресс для компилятора. Стандарт языка C++ рекомендует поддерживать глубину не менее 17.
Вы бы куда меньше времени потратили на написание своего правильного теста, чем на голые комментарии с пустой критикой.
Тут мы с вами расходимся во мнениях. Критика была аргументированная.
>Рекурсивное инстанцирование шаблонов глубиной в 5000 это весьма серьезный стресс для компилятора. Стандарт языка C++ рекомендует поддерживать глубину не менее 17.
Клики мышкой с частотой 10 раз в секунду — это весьма серьёзный стресс для любого приложения.
Текстовый файл размером 2 гигабайта… ну вы поняли, да?
Да, ситуация выбивается из ряда «обычных» и «рекомендованных», но падать программа всё равно не должна.
>Критика была аргументированная.
Но по-прежнему ничем не подтверждённая.
«Я не собираюсь вам ничего доказывать. Это вы тут доказываете превосходство C++» — да, он доказывает превосходство С++ на данной конкретной задаче, и у него есть на это основания — конкретный тест. Если вы хотите опровергать — опровергайте предметно, а не «я знаю лучше, вот тут будет так-то и так-то, но доказывать ничего не собираюсь». Это на опровержение ну никак не тянет.
Клики мышкой с частотой 10 раз в секунду — это весьма серьёзный стресс для любого приложения.
Текстовый файл размером 2 гигабайта… ну вы поняли, да?
Да, ситуация выбивается из ряда «обычных» и «рекомендованных», но падать программа всё равно не должна.
>Критика была аргументированная.
Но по-прежнему ничем не подтверждённая.
«Я не собираюсь вам ничего доказывать. Это вы тут доказываете превосходство C++» — да, он доказывает превосходство С++ на данной конкретной задаче, и у него есть на это основания — конкретный тест. Если вы хотите опровергать — опровергайте предметно, а не «я знаю лучше, вот тут будет так-то и так-то, но доказывать ничего не собираюсь». Это на опровержение ну никак не тянет.
«Я не собираюсь вам ничего доказывать. Это вы тут доказываете превосходство C++» — да, он доказывает превосходство С++ на данной конкретной задаче, и у него есть на это основания — конкретный тест. Если вы хотите опровергать — опровергайте предметно, а не «я знаю лучше, вот тут будет так-то и так-то, но доказывать ничего не собираюсь». Это на опровержение ну никак не тянет.
Вот скрипт на python который генерирует все возможные специализированные варианты функции—компаратора на Си. Это канает?
from itertools import permutations as p
from math import pow
fields = ['','code','gender','age','amount_of_money','height']
def field_list_to_index(fl):
return sum(fields.index(i)*int(pow(len(fields),n)) for n,i in enumerate(fl))
for params in set(fl[:fl.index('')] for fl in p(fields) if fl[0]):
index = field_list_to_index(params)
print 'BEGINF(%s)'%index
print '\n'.join(' COMPAR(%s)'%p for p in params)
print 'ENDF(%s)'%index
Генерируется такая портянка кода:
BEGINF(377)
COMPAR(height)
COMPAR(gender)
COMPAR(amount_of_money)
COMPAR(code)
ENDF(377)
BEGINF(31)
COMPAR(code)
COMPAR(height)
ENDF(31)
Исходный код таблицы функций. Время компиляции полученного Си кода — 2 мс.
Кстати, это хороший повод запостить багрепорт.
UFO just landed and posted this here
К слову, эта оптимизация не применима в Java и C#, т.к. в generics невозможно использовать параметром значение, а не тип.
Ради справедливости стоит отметить, что в том же C# можно довольно легко средствами фреймфорка сгенерировать код фильтра во время исполнения и запускать вариант с нужным набором проверок.
Приведите пример и результаты тестов.
Ну сольются на этом синтетическом тесте и джава, и шарп. Скажем, будут в два раза медленнее.
Но ваш код — будет в пять раз дольше писаться, в десять раз дороже поддерживаться. Подходит не каждый компилятор — это минус, как и любая дополнительная зависимость, особенно не идущая из коробки. Разобраться в вашем коде могут немногие — это минус: сложно найти реально сильного программиста, и стОят такие дофига. Кто может разобраться, тот будет разбираться долго — это минус: нужно добавлять новые фичи, а он будет разбираться в том, как добавить поле в этого монстра.
Я не спорю, код крутой, быстрый. И в отличие от многих статей с финтами ушами, как вы заметили, может быть успешно применён. Но он в индустрии мало кому нужен. Железо в долгосрочной перспективе — почти всегда дешевле.
Скажите, этот код у вас из реального проекта, или это зарядка для мозгов?
Но ваш код — будет в пять раз дольше писаться, в десять раз дороже поддерживаться. Подходит не каждый компилятор — это минус, как и любая дополнительная зависимость, особенно не идущая из коробки. Разобраться в вашем коде могут немногие — это минус: сложно найти реально сильного программиста, и стОят такие дофига. Кто может разобраться, тот будет разбираться долго — это минус: нужно добавлять новые фичи, а он будет разбираться в том, как добавить поле в этого монстра.
Я не спорю, код крутой, быстрый. И в отличие от многих статей с финтами ушами, как вы заметили, может быть успешно применён. Но он в индустрии мало кому нужен. Железо в долгосрочной перспективе — почти всегда дешевле.
Скажите, этот код у вас из реального проекта, или это зарядка для мозгов?
Кстати, даже у Java не так все плохо. На Q8200 (который слабее i750) решение в лоб для 10 000 000 работает около 110ms. Правда выжирает больше гигабайта.
Решение для миллиона: ideone.com/LFe228 (иначе падает). Нолик добавлять в первой строке метода main
Второй тест — без функции сравнение, она руками инлайнена в цикл, проверял собственно работу в JVM инлайна.
Что выжирает так память я не понял.
Решение для миллиона: ideone.com/LFe228 (иначе падает). Нолик добавлять в первой строке метода main
Второй тест — без функции сравнение, она руками инлайнена в цикл, проверял собственно работу в JVM инлайна.
Что выжирает так память я не понял.
На домашней машине (Core i3 380M):
Неоптимизированный алгорит C с максимальными настройками компилятора -march=native -O3 —
82мс
Java сверху по ссылке java -Xms3g -Xmx3g -server -verbose:gc Test
от 51мс до 150мс, потребление память — чуть меньше 300Миб
Результаты Java сильно разняться по-видимому из-за рантайм оптимизаций, лучший результат был, когда выбрались все строки, то есть JVM пыталась сделать в рантайме оптимизации по типу тех, что автор статьи делает во время компиляции.
От себя добавлю, что если вы не готовы к оптимизациям, описанным в статье, лучше брать Яву.
P.S.Насчет выжирания гигабайта, я ошибся, просто с менее чем гигабайтом выделенной памяти включался GC.
Неоптимизированный алгорит C с максимальными настройками компилятора -march=native -O3 —
82мс
Java сверху по ссылке java -Xms3g -Xmx3g -server -verbose:gc Test
от 51мс до 150мс, потребление память — чуть меньше 300Миб
Результаты Java сильно разняться по-видимому из-за рантайм оптимизаций, лучший результат был, когда выбрались все строки, то есть JVM пыталась сделать в рантайме оптимизации по типу тех, что автор статьи делает во время компиляции.
От себя добавлю, что если вы не готовы к оптимизациям, описанным в статье, лучше брать Яву.
P.S.Насчет выжирания гигабайта, я ошибся, просто с менее чем гигабайтом выделенной памяти включался GC.
Пересчитал для 100 итераций. Если вручную встроить провеку в цикл — то 117мс, если не встраивать, то 147мс.
Интересно ведет себя garbage collector. Если его вызов не форсировать, то удаляет обекты он в средним по 270 мс, очищая память примерно на половину, после примерно каждой второй итерации.
Если же перед каждой новой итерацией, перед генерацие нового массива данных делать Runtime.getRuntime().gc(), то делается 2 вызова (GC и Full GC), общее время которых не привышает 8мс, что уже намного лучше.
Интересно ведет себя garbage collector. Если его вызов не форсировать, то удаляет обекты он в средним по 270 мс, очищая память примерно на половину, после примерно каждой второй итерации.
Если же перед каждой новой итерацией, перед генерацие нового массива данных делать Runtime.getRuntime().gc(), то делается 2 вызова (GC и Full GC), общее время которых не привышает 8мс, что уже намного лучше.
Ради справедливости стоит отметить, что в том же C# можно довольно легко средствами фреймфорка сгенерировать код фильтра во время исполнения и запускать вариант с нужным набором проверок.
Во-первых, компиляция на ходу приводит к ощутимым задержкам, поэтому не во всех случаях удобна.
Во-вторых, построение кода на Expression'ах — это тоже нехилые простыни, которые в подходе write-only составят достойную конкуренцию коду на шаблонах из соседнего топика.
Я бы трижды подумал, прежде чем внедрять в реальный проект такое шаманство.
А почему сразу на Expression'ах? Я обычно Reflection.Emit использую...
По поводу задержек — они все равно окупаются дальнейшим ускорением, особенно на больших наборах данных.
По поводу задержек — они все равно окупаются дальнейшим ускорением, особенно на больших наборах данных.
Во-первых, компиляция на ходу приводит к ощутимым задержкам, поэтому не во всех случаях удобна.
В случае автора все фильтры генерируются заранее. Здесь тоже можно сделать во время инициализации программы или ленивым образом, так что это операция которая выполняется один раз.
Во-вторых, построение кода на Expression'ах — это тоже нехилые простыни, которые в подходе write-only составят достойную конкуренцию коду на шаблонах из соседнего топика.
По поводу простыней не знаю, как по мне подход несколько более логичный, по крайней мере это использование инструмента по назначению. Все-таки шаблоны изначально задумывались несколько с другими целями.
Я бы трижды подумал, прежде чем внедрять в реальный проект такое шаманство.
Это вещь которая применяется в разовых случаях, это понятно. Равно как и подобные извращения с шаблонами.
Ради справедливости стоит также отметить, что преимущества в производительности C# могут достигаться за счет менеджера памяти. C# может легко перемещать блоки памяти, снижая фрагментацию. С++ после активной работы с памятью будет сидеть с фрагментированной кучей…
Если быть совсем уж справедливыми, то стоит отметить, что из-за оверхеда связанного с о сборщиком мусора и другими особенностями виртуальной машины лично у меня никогда не получалось достичь лучших относительно нативного кода производительности.
Виртуальная память жеж давно.
А что, если виртуальная, то фрагментация ей не страшна, что ли?
C# может легко перемещать блоки памяти, снижая фрагментацию. С++ после активной работы с памятью будет сидеть с фрагментированной кучей…
Это же умеет делать ОС на уровне виртуальной памяти. В крайнем случае можно использовать какой-нибудь nedmalloc c пулингом.
Тот момент, когда код на асме понятнее, чем шаманства с шаблонами...)
извините, что не совсем по теме статьи, но мне стало любопытно, а есть ли практический смысл в конструкциях const*const? я знаю, что оно обозначает, но на практике больше одного const-модификатора в типе не видел.
IMHO, смысл есть — более сильная константность (транзитивная в случае const *const — измениться не может ни значение (в случае отсутствие последующей индирекции), ни указатель на него) дает компилятору больше потенциальных возможностей оптимизировать этот код.
И я, например, всегда стараюсь использовать модификатор const, и не использую его лишь в редких случаях.
И я, например, всегда стараюсь использовать модификатор const, и не использую его лишь в редких случаях.
Но Google C++ Style Guide рекомендует передавать неизменяемые параметры по константной ссылке const&, а изменяемые по константному указателю *const
Я, наверное, что-то путаю, но в Google C++ Style Guide говорится о
const T*, а не о T* const ??Скорее всего да, ибо const T * — указатель на константный объект типа Т, а T * const — константный указатель на изменяемый объект.
пруф линк для сомневающихся
пруф линк для сомневающихся
об этом я и говорю — автор что-то напутал немножко.
Нет, напутали вы.
В Google C++ Style Guide идёт речь об
const T*, тогда как в статье говорится о том, что Google C++ Style Guide рекомендует «константный указатель *const», т.е. T* const, что не одно и тоже. Смысл говорить об одном и давать ссылку на немножко другое? Ладно, не столь важно, статья не об этом.Ну как вы передадите изменяемый параметр по
Так что можно сказать, что автор немного ошибся — Google C++ Style Guide не отдает предпочтения ни одному варианту из
const T*? Другое дело, что в Google C++ Style Guide я вообще не нашел раздела про указатели.Так что можно сказать, что автор немного ошибся — Google C++ Style Guide не отдает предпочтения ни одному варианту из
T* или T* constимеенно об этом я и говорю — ничего о
И я ничего не говорил о передаче изменяемого параметра как
Меня просто не поняли, глупо получилось.
T* const Google C++ Style Guide не говорит.И я ничего не говорил о передаче изменяемого параметра как
const T* — имелось в виду, что Google C++ Style Guide если уж и что-то говорит о передаче параметров — то только о const T*, а не о T* const (или const T* const).Меня просто не поняли, глупо получилось.
Google рекомендует при любой возможности использовать const, если нет необходимости в обратном. Если нет необходимости в адресной арифметике, то для изменяемых параметров он отдает предпочтение: T *const.
А почему нельзя передать по ссылке?
All parameters passed by reference must be labeled const.
Через T const& нельзя менять значение.
Через T const& нельзя менять значение.
Потому что при использовании ссылок неочевидно, может функция менять аргумент или нет.
Если ссылка константная, то не может, и наоборот, очевидно же.
Вот вам кусок кода:
Если следовать рекомендациям Google, то программа может вывести только 5 и ничего другого.
int x = 5;
foo(x);
cout << x;
Если следовать рекомендациям Google, то программа может вывести только 5 и ничего другого.
Заменю на const int x = 5;, а вообще пример из пальца высосан. Я также могу сказать вам, что передача указателя на int вызовет у меня больше сомнений, ибо чё там дальше с указателем делается, я тоже не знаю.
В виде бонуса ссылка позволяет отловить ошибки, гарантируя передачу рельного объекта. Если вы, конечно, не сделаете foo(*ptr), такой код заслуживет отдельных лучей поноса.
Неоднократно замечал, что при проэктировинии баз данных поле «пол» делают булевым. При чем «true» означает мужской пол, а «false» — женский.
bash.im/quote/396500
unsigned gender:1;
В данном случае, видимо, 1 означает мужской пол, а 0 — женский, т. к. цифры 0 и 1 похожи на… Ладно, не буду продолжать.
Помимо этого, даже, существуют статьи показывающие преимущества в скорости языков с компиляцией налету (JIT — Just-in-time compilation), таких как Java и C#. Сравнить последние мы оставим тем, кто считает их быстрыми, но мы объясним почему это не такНебольшой пример, использующий динамическую генерацию кода и JIT: Ищем на java, оптимизация во время исполнения. За счет генераци «плана исполнения запроса» на лету и JIT, скорость получилась сравнимая со статической оптимизацией.
Отлично.
Из всех предлагаемых вариантов осталась только не раскрыта тема LLVM в рантайме :)
Из всех предлагаемых вариантов осталась только не раскрыта тема LLVM в рантайме :)
Вот есть пример, как использовать этот LLVM: www.opensource.apple.com/source/lldb/lldb-69/llvm/examples/HowToUseJIT/HowToUseJIT.cpp.
Достаточно просто
Достаточно просто
Но в C, где нет ссылок, такой подход не возможен, т.к. если функция всегда принимает только по указателю, то на стороне вызывающего нельзя гарантировать невозможность их модификации
Почему это? Можно написать так:
void func(int const *a, int *b) {}Вы, конечно, можете возразить, что a здесь можно поменять при помощи
*(int *)a = 0Но тогда и в вашем решении с int const& a переменную a тоже можно поменять с помощью
(int&)a = 0Естественно, я не хочу сказать, что int const *a лучше
Выше уже 100 раз обсудили.
Приведите мне код вызывающий функцию в Google C++ Style, и я вам только по этому вызову на 100% скажу, какие переменные могут быть изменены, а какие нет.
Если бы вы писали код в Google C++ Style, то функция выглядела бы так:
А код вызова так:
Откуда очевидно, что a — не меняется, b — меняется.
В C такое не получиться.
Код вызова вашей функции:
Это крайне важно, когда вы не хотите, чтобы ваша переменная менялась при использовании чужой функции, которую её автор может поменять, а падать будет у вас.
на стороне вызывающего нельзя гарантировать невозможность их модификации
Приведите мне код вызывающий функцию в Google C++ Style, и я вам только по этому вызову на 100% скажу, какие переменные могут быть изменены, а какие нет.
Если бы вы писали код в Google C++ Style, то функция выглядела бы так:
void func(int const& a, int *b) {}
А код вызова так:
int a, b; func(a, &b);
Откуда очевидно, что a — не меняется, b — меняется.
В C такое не получиться.
Код вызова вашей функции:
int a, b; func(&a, &b);
Это крайне важно, когда вы не хотите, чтобы ваша переменная менялась при использовании чужой функции, которую её автор может поменять, а падать будет у вас.
C++ не быстрее C. Всё, что можно сделать в C++, можно и в C. Возможно, не так красиво, но можно. В данном случае, решение на C, возможно, было бы красивее, чем эти выкрутасы с шаблонами. И никаких «C-разработчикам придется вручную создать эти 32 функции». Можно просто сделать как-то на макросах C. Например (для примера рассмотрены только три поля):
Обратите внимание, что здесь use_amount_of_money — это выражение времени компиляции, и на этапе препроцессинга оно превратится в 0 или 1. Поэтому в (!use_amount_of_money || ...) компилятор выкинет этот use_amount_of_money. Поэтому скорость будет такая же, как и в вашем решении на шаблонах C++. Тестировать не буду — не хочу. Сами тестируйте, если хотите. Скорость будет такая же, так как суть одна. Просто то, что можно было сделать на шаблонах, сделано на макросах. Можно ещё попробовать просто сгенерировать C-код скриптом.
/* Compare row with filters */
#define DECLARE(use_amount_of_money, use_gender, use_age) \
static inline unsigned char test_predicate_ ## use_amount_of_money ## _ ## use_gender ## _ ## use_age(struct T_cash_account_row const*const row, \
struct T_range_filters const*const range_filters) \
{ \
return \
(!use_amount_of_money || \
(row->amount_of_money >= range_filters->begin.amount_of_money && \
row->amount_of_money <= range_filters->end.amount_of_money)) && \
(!use_gender || \
(row->gender >= range_filters->begin.gender && \
row->gender <= range_filters->end.gender)) && \
(!use_age || \
(row->age >= range_filters->begin.age && \
row->age <= range_filters->end.age)); \
}
#define DECL2(m, g) DECLARE(m, g, 0) DECLARE(m, g, 1)
#define DECL1(m) DECL2(m, 0) DECL2(m, 1)
DECL1(0)
DECL1(1)
Обратите внимание, что здесь use_amount_of_money — это выражение времени компиляции, и на этапе препроцессинга оно превратится в 0 или 1. Поэтому в (!use_amount_of_money || ...) компилятор выкинет этот use_amount_of_money. Поэтому скорость будет такая же, как и в вашем решении на шаблонах C++. Тестировать не буду — не хочу. Сами тестируйте, если хотите. Скорость будет такая же, так как суть одна. Просто то, что можно было сделать на шаблонах, сделано на макросах. Можно ещё попробовать просто сгенерировать C-код скриптом.
Можно сделать, но на макросах никогда не было красивее. И на макросах всегда в разы хуже с поддержкой кода. Почти никто не захочет тестировать ваш код на макросах и использовать в production. В макросах почти ничего не контролируется, ни тело, ни входные параметры. Словив ошибку при разработке или при слияниях веток в Git/Mercurial, вам придется часами гадать на хрустальном шаре. Содержательность сообщений компилятора при ошибках в макросах на порядок ниже, чем при ошибках в шаблонах. На ошибку в любой строке тела макросах компилятор всегда выдаст ошибку в одной и той же строке — в месте использования макроса. По этому и придумали шаблоны, со строгим синтаксисом и содержательными сообщениями компилятора.
Тот же Google C++ Style, предпочитает макросам даже Prefer inline functions, enums, and const variables to macros. А использовать их вместо шаблонов — это вообще за гранью адекватности.
Тот же Google C++ Style, предпочитает макросам даже Prefer inline functions, enums, and const variables to macros. А использовать их вместо шаблонов — это вообще за гранью адекватности.
Содержательность сообщений компилятора при ошибках в макросах на порядок ниже, чем при ошибках в шаблонах
pascalg.wordpress.com/2008/02/24/stl-error-messages-are-so-great :)
Всё там понятно.
А затем приведены две сигнатуры функции insert().
note: candidates are: typename std::vector<_Tp, _Alloc>::iteratorПрямо написано, что передавать надо итератор, а не значение.
А затем приведены две сигнатуры функции insert().
Да, эти сообщения слишком подробные. Но слишком подробное сообщение все равно лучше, чем ничего не содержащее.
По поводу LLVM.
Я хотел реализовать этот пример на LLVM, но не стал, так как там надо писать кучу кода. Вот, например, чтобы скомпилировать return x + 1;, нужно написать:
(пример взят из ссылки, которую я уже кидал выше)
Но всё-таки посмотреть, как будет работать генерация кода на лету, хотелось. Поэтому я сделал некий псевдо-JIT. JIT без JIT'а. А именно: в рантайме генерирую код на си, потом компилирую его вызывая обычный компилятор, создаю таким образом разделяемую библиотеку (.so в GNU/Linux, .dll в Windows), подгружаю её в свой процесс и вызываю только что скомпилированную функцию. Да, это немного через пятую точку. И в реальных приложениях, наверное, нужно использовать настоящий JIT (например, на основе LLVM), потому что в настоящем JIT'е не тратится время на парсинг кода. Зато в моём способе не нужно писать кучу громоздкого кода для конструирования return x + 1;: просто пишем
Для начала Hello world, который демонстрирует этот трюк: paste.org.ru/?ga0au3 (для Windows и UNIX-подобных ОС). За одно этот трюк показывает, что в си можно реализовать eval (а вы думали, что eval есть только в интерпретируемых языках?).
А теперь применим всё это дело к нашей задаче: paste.org.ru/?09yt9c. Код получился быстрее, чем ваш код на шаблонах: 0.54 секунды против 0.88 «шаблонного» решения на моём компьютере. При сравнении времени я во всех алгоритмах использовал200 000 000 , а не 10 000 000 , а то на моём компьютере выполнялось слишком быстро.
Причина такого ускорения в том, что в моём способе в момент псевдо-JIT'а известен не только шаблон поиска (т. е. массив
Чтобы убедиться в том, что причина такого ускорения именно в константности
Я проверил, что весь код компилируется в следующих двух окружениях:
Тестирование времени проводил в первой из них. Ещё раз табличка с результатами:
Функция clock, которую вы используете, совсем неточная, выдаёт время лишь с точностью до 0.01 на GNU/Linux. Надо было какую-нибудь другую. Но мне не хотелось разбираться, так что я использовал её. Вдобавок я не учитывал советы, данные тут: habrahabr.ru/post/180161. И вообще, все тесты я проводил по одному разу. Так что можете всё перетестить и получить более точные результаты.
И хватит всем говорить «Приведите пример и результаты тестов». У человека может быть время написать коммент, но не быть времени для написания примера.
Я хотел реализовать этот пример на LLVM, но не стал, так как там надо писать кучу кода. Вот, например, чтобы скомпилировать return x + 1;, нужно написать:
// Get pointers to the constant `1'.
Value *One = ConstantInt::get(Type::getInt32Ty(Context), 1);
// Get pointers to the integer argument of the add1 function...
assert(Add1F->arg_begin() != Add1F->arg_end()); // Make sure there's an arg
Argument *ArgX = Add1F->arg_begin(); // Get the arg
ArgX->setName("AnArg"); // Give it a nice symbolic name for fun.
// Create the add instruction, inserting it into the end of BB.
Instruction *Add = BinaryOperator::CreateAdd(One, ArgX, "addresult", BB);
// Create the return instruction and add it to the basic block
ReturnInst::Create(Context, Add, BB);
(пример взят из ссылки, которую я уже кидал выше)
Но всё-таки посмотреть, как будет работать генерация кода на лету, хотелось. Поэтому я сделал некий псевдо-JIT. JIT без JIT'а. А именно: в рантайме генерирую код на си, потом компилирую его вызывая обычный компилятор, создаю таким образом разделяемую библиотеку (.so в GNU/Linux, .dll в Windows), подгружаю её в свой процесс и вызываю только что скомпилированную функцию. Да, это немного через пятую точку. И в реальных приложениях, наверное, нужно использовать настоящий JIT (например, на основе LLVM), потому что в настоящем JIT'е не тратится время на парсинг кода. Зато в моём способе не нужно писать кучу громоздкого кода для конструирования return x + 1;: просто пишем
fprintf(fout, "return x + 1;");. Вдобавок такой способ портируем на любую ОС, в которой есть компилятор си, который может создавать разделяемые библиотеки.Для начала Hello world, который демонстрирует этот трюк: paste.org.ru/?ga0au3 (для Windows и UNIX-подобных ОС). За одно этот трюк показывает, что в си можно реализовать eval (а вы думали, что eval есть только в интерпретируемых языках?).
int main(void){
eval("printf(\"Hello, world!\\n\")");
return 0;
}
А теперь применим всё это дело к нашей задаче: paste.org.ru/?09yt9c. Код получился быстрее, чем ваш код на шаблонах: 0.54 секунды против 0.88 «шаблонного» решения на моём компьютере. При сравнении времени я во всех алгоритмах использовал
c_array_size, равный Причина такого ускорения в том, что в моём способе в момент псевдо-JIT'а известен не только шаблон поиска (т. е. массив
use_filter), но и сами граничные значения (begin и end). В вашем же решении на шаблонах генерируются шаблоны для каждого варианта use_filter, но begin и end по-прежнему остаются runtime-переменными. Естественно, то же самое получилось бы и при использовании LLVM (в смысле LLVM имел бы такую же скорость, как и мой псевдо-JIT).Чтобы убедиться в том, что причина такого ускорения именно в константности
begin и end, я написал специальный вариант моего кода, в котором begin и end являются переменными времени исполнения. Вот он: paste.org.ru/?q7gu4p. Как и следовало ожидать, время выполнения получилось такое же, как и у решения на шаблонах: 0.88 секунд.Я проверил, что весь код компилируется в следующих двух окружениях:
- Debian GNU/Linux Wheezy amd64, gcc 4.7.2, физическая машина, Intel Core i7, 2 ГГц
- Windows 8 Release Preview x86_64, MVC++ 2010 Express, виртуальная машина
Тестирование времени проводил в первой из них. Ещё раз табличка с результатами:
Неоптимизированный поиск на C | 1.41, 1.34, 1.47 (было 3 теста) Шаблоны C++ | 0.88 Псевдо-JIT | 0.54 (+0.02 на саму "компиляцию на лету") Псевдо-JIT с переменными begin и end | 0.88 (+0.02 на "компиляцию")
Функция clock, которую вы используете, совсем неточная, выдаёт время лишь с точностью до 0.01 на GNU/Linux. Надо было какую-нибудь другую. Но мне не хотелось разбираться, так что я использовал её. Вдобавок я не учитывал советы, данные тут: habrahabr.ru/post/180161. И вообще, все тесты я проводил по одному разу. Так что можете всё перетестить и получить более точные результаты.
И хватит всем говорить «Приведите пример и результаты тестов». У человека может быть время написать коммент, но не быть времени для написания примера.
Молодец, что нашли время не только писать комментарии, но и сделать что-то работающее :)
Но надеюсь вы понимаете, что:
1. Поддерживать такой код тоже очень «удобно», не знаю даже лучше или хуже, чем с макросами. Для ошибок кода из строковых переменных вы получаете в пост-процессинговом исходнике при второй компиляции, а править их надо в первоначальном исходнике.
2. И первая, и вторая статьи — это лишь одна из оптимизаций, которая применяется после сужения индексного поиска за счет IOT/IOS до 50 — 1000 элементов, и выполняется этот алгоритм за 1мкс — 20мкс, примерно до 10^6 запросов в секунду на одно ядро. Тут уж не по компилируешь каждый раз.
Будет свободное время — напишу третью статью, где это покажу.
Но надеюсь вы понимаете, что:
1. Поддерживать такой код тоже очень «удобно», не знаю даже лучше или хуже, чем с макросами. Для ошибок кода из строковых переменных вы получаете в пост-процессинговом исходнике при второй компиляции, а править их надо в первоначальном исходнике.
2. И первая, и вторая статьи — это лишь одна из оптимизаций, которая применяется после сужения индексного поиска за счет IOT/IOS до 50 — 1000 элементов, и выполняется этот алгоритм за 1мкс — 20мкс, примерно до 10^6 запросов в секунду на одно ядро. Тут уж не по компилируешь каждый раз.
Будет свободное время — напишу третью статью, где это покажу.
А знаете что? Ваш пример показывает, что, оказывается, всё-таки имеет смысл делать self-modifying machine code. Вот смотрите:
Решение на шаблонах
Решение на JIT (ну или псевдо-JIT, сейчас это не важно)
А теперь посмотрим на self-modifying code: просто нужно на этапе компиляции скомпилировать, скажем, 32 варианта функции
В результате получаем такую же скорость, как и в решении с JIT'ом, т. к. переменные
Непонятно только, как это реализовать на практике. Ведь, как я понимаю, во всех нормальных ОС текущий выполняемый код защищён от записи. Собственно, этот пример показывает, что такую защиту иногда бывает нужно снимать.
Да, теперь я понимаю, что self-modifying code — это не пережиток времён DOS. Он реально бывает нужен.
Решение на шаблонах
- Плюс: не надо компилировать в рантайме
- Минус: медленнее, чем JIT
Решение на JIT (ну или псевдо-JIT, сейчас это не важно)
- Плюс: быстрее, чем на шаблонах
- Минус: надо делать JIT в рантайме
А теперь посмотрим на self-modifying code: просто нужно на этапе компиляции скомпилировать, скажем, 32 варианта функции
test_predicate, потом в рантайме выбрать нужный из этих вариантов, а потом записать прямо в (уже скомпилированный) машинный код значения begin и end и передать управление этому модифицированному коду. (Если непонятно, могу подробнее объяснить.)В результате получаем такую же скорость, как и в решении с JIT'ом, т. к. переменные
begin и end будут с точки зрения самой функции test_predicate константами. Но при этом не надо делать JIT. Достаточно лишь поменять машинный код во время исполнения, а это занимает лишь единицы тактов процессора, в отличие от JIT.Непонятно только, как это реализовать на практике. Ведь, как я понимаю, во всех нормальных ОС текущий выполняемый код защищён от записи. Собственно, этот пример показывает, что такую защиту иногда бывает нужно снимать.
Да, теперь я понимаю, что self-modifying code — это не пережиток времён DOS. Он реально бывает нужен.
Как мне кажется, в случае константных begin и end компилятор оптимизирует код под эти константы, и просто так заменить их в получившемся машинном коде не получится.
А по поводу защиты от записи — тут все просто. Например, в Windows достаточно вызвать функцию VirtualProtect.
А по поводу защиты от записи — тут все просто. Например, в Windows достаточно вызвать функцию VirtualProtect.
Как мне кажется, в случае константных begin и end компилятор оптимизирует код под эти константы, и просто так заменить их в получившемся машинном коде не получится.
Всё равно можно что-то придумать. Можно подобную оптимизацию в рантайме замутить. Но, опять-таки, не полноценный JIT, а именно немножко манипуляций байтами, чтоб укладывалось в маленькое число тактов.
Sign up to leave a comment.
Возможности оптимизации в языках C и C++