Comments 41
В кои-то веки толковая статья про C++ в которой на живом примере показан нетривиальный способ использования шаблонов. Автор молодец.
Ваши оптимизации работают только при фиксированном числе полей в таблице. Если число полей не известно во время компиляции, то С вы средствами С++ не сможете никак улучшить производительность.
То есть, я не вижу способов, если вы придумаете, был бы рад почитать :)
То есть, я не вижу способов, если вы придумаете, был бы рад почитать :)
А ещё тут нет Data Definition Language (DDL) и API, чтобы сообщить об изменении числа полей.
Это пример решения на C++ конкретной задачи. Но все приемлемые задачи решаются.
Добавляйте ещё раскрутки по числу полей и числу типов, если не лень ждать компиляции :)
Это пример решения на C++ конкретной задачи. Но все приемлемые задачи решаются.
Добавляйте ещё раскрутки по числу полей и числу типов, если не лень ждать компиляции :)
Дело даже не во времени компиляции, десять полей уже не влезет в инт. Собственно, по этому, не получится в компайл тайме все индексные пути построить. А значит, рантайм. А значит с++ и с одно и то же дадут.
Да, давно на Хабре не было таких крутых статей про C++. Аж, блин, мотивирует.
Конечно, хочется еще статей от Вас. И на разбор таких статей ночи пятницы как-то мало, нужно основательно садиться в выходные.
Конечно, хочется еще статей от Вас. И на разбор таких статей ночи пятницы как-то мало, нужно основательно садиться в выходные.
«единственная альтернатива C++–шаблонам для подобных оптимизаций – это писать десятки, сотни и тысячи функций – вот уж где действительно copy-paste.», альтернатива — использовать генераторы C кода, например XSLT, или скрипт который сгенерирует эти 3840 функций и отдать компилятору, при этом можно генерировать любой код, не ограничиваясь С++ шаблонизатором.
Можно. Только XSLT — это уже не достоинство C. Кстати, напишите такое решение, сравним.
Основной тезис: то, что возможно в C — возможно и в C++, а обратное не верно.
Основной тезис: то, что возможно в C — возможно и в C++, а обратное не верно.
Логично, ведь С++ практически надмножество С.
Учитывая, что С — это по сути кроссплатформенный ассемблер, то тезис неверный… Для генерации таких вещей в С обычно используют препроцессор. В былые времена были компиляторы, которые код C++ cредствами препроцессора преобразовывали в код C и компилировали стандартным компилятором С.
Собственно шаблоны в С++ реализуют то, что в C обычно делалось препроцессором.
Собственно шаблоны в С++ реализуют то, что в C обычно делалось препроцессором.
А ещё можно генерировать эти функции через препроцессор, например используя C-совместимую библиотеку Boost.Preprocessor.
Генератор кода можно написать на C и засунуть в Makefile, избавившись от лишних зависимостей. Шаблонами будут выступать строки формата для printf().
А вообще теперь можно факториалы и тому подобные вещи считать не шаблонами, а constexpr'ами. Заметно сокращает число строчек.
Все-таки шаблоны штука очень мощная, но громозкая.
Все-таки шаблоны штука очень мощная, но громозкая.
По-моему, раз часть вычислительной задачи с программы перевесилась на компилятор, то уместнее считать производительность как время компиляции + время исполнения.
Вот, скажем, если параметры поменяются?
Пишем скрипт: он берёт исходник, меняет в нём grep-ом параметры, потом собирает программу, запускает, получает результат.
Но в этом случае временем вычислений будет время от запуска до завершения всего скрипта, а не только лишь сгенерированного _промежуточного_ кода.
Вот, скажем, если параметры поменяются?
Пишем скрипт: он берёт исходник, меняет в нём grep-ом параметры, потом собирает программу, запускает, получает результат.
Но в этом случае временем вычислений будет время от запуска до завершения всего скрипта, а не только лишь сгенерированного _промежуточного_ кода.
Некорректно. Вы компилируете программу один раз, а исполняете сильно больше.
Это же не оптимально!
Дело в том, что компиляция программы — действие единичное, а вот запуск — регулярное.
Подправьте немного код, чтобы можно было вводить элементы массива и условия поиска, и запустите поиск миллиард раз, в сумме времени компиляции и времени работы, время компиляции уже будет ничтожно мало.
#offtop
Подобным образом люди ошибаются регулярно.
Мне часто приходится наблюдать такое, когда я говорю знакомым, что использую gentoo в качестве основной системы. Я не отрицаю, что сборка с нуля системы и всего софта, что я использую (ну не совсем с нуля, а со stage3) на моем ноуте занимает чуть больше суток, однако я получаю очень быструю и стабильную систему. Можно пытаться возражать, что оптимизация под машину не дает прибавки скорости, но пока не попробуешь сравнить, не увидишь реальное положение дел. Я пробовал использовать дистрибутивы, использующие бинарные пакеты, субъективно, скорость работы сильно различается, я склонен думать, что это связано с тем, что я один раз потратил время на то чтобы подобрать длинную строку флагов компилятора и дождался окончания сборки.
Дело в том, что компиляция программы — действие единичное, а вот запуск — регулярное.
Подправьте немного код, чтобы можно было вводить элементы массива и условия поиска, и запустите поиск миллиард раз, в сумме времени компиляции и времени работы, время компиляции уже будет ничтожно мало.
#offtop
Подобным образом люди ошибаются регулярно.
Мне часто приходится наблюдать такое, когда я говорю знакомым, что использую gentoo в качестве основной системы. Я не отрицаю, что сборка с нуля системы и всего софта, что я использую (ну не совсем с нуля, а со stage3) на моем ноуте занимает чуть больше суток, однако я получаю очень быструю и стабильную систему. Можно пытаться возражать, что оптимизация под машину не дает прибавки скорости, но пока не попробуешь сравнить, не увидишь реальное положение дел. Я пробовал использовать дистрибутивы, использующие бинарные пакеты, субъективно, скорость работы сильно различается, я склонен думать, что это связано с тем, что я один раз потратил время на то чтобы подобрать длинную строку флагов компилятора и дождался окончания сборки.
AlexeyAB, если не секрет, эти знания — результат наработок по проекту или чисто хобби? и с чем связан проект?
Конкретно эти примеры и статьи — чисто хобби. Подобные кросс-аппаратные оптимизации на шаблонах используются в реальных проектах для расчета аналитики в банковских хранилищах данных. Необходимы кросс-аппаратные оптимизации, т.к. исполнятся могут на Windows-HPC, AIX, HP-UX, Solaris, Linux. Или на CUDA GPU.
Попробую вопрос не в тему. Когда-то я хотел сделать функцию, которую можно запустить с любым количеством элементов. И что бы это было быстро, красиво и безопасно. В результате своего скудного знания С++ написал вот такое compilr.com/shchvova/ellipsis-function-test/ConsList.cpp
Может, есть совет как сделать лучше?
Спасибо!
Может, есть совет как сделать лучше?
Спасибо!
Спасибо за статьи. Действительно очень впечатляет. Но что насчет стоимости сопровождения такого варианта?
ИМХО использование контейнеров и запись вроде такой
здорово ускорит разработку, уменьшит количество кода( а заодно и багов), и на порядки понизит стоимость как разработки, так и сопровождения кода.
Ну а железо дешевеет с каждым днем
ИМХО использование контейнеров и запись вроде такой
auto endIterator = std::copy_if(rows.begin(),
rows.end(),
std::back_inserter(output),
[&] (const CashAccountRow& instance) -> bool {
// filter
});
});
здорово ускорит разработку, уменьшит количество кода( а заодно и багов), и на порядки понизит стоимость как разработки, так и сопровождения кода.
Ну а железо дешевеет с каждым днем
Стоимость разработки и сопровождения большая. Такая оптимизация применяется только в дорогих решениях и в критически важных местах.
Если в результате подобной оптимизации, мы снижая стоимость, экономим 1-10 млн, то оно того стоит.
Разница в цене 1 и 100 серверов в 100 раз, не считая скидок. Разницы в кросс-аппаратной оптимизации одного ПО для 1 и 100 серверов нет. Это ПО можно будет использовать и в будущем на новых серверах. А за железо каждый раз надо платить. Поэтому, это применимо только для фирм думающих наперёд.
Поверьте, аппетиты фирм и объем данных растут гораздо сильнее, чем дешевеет оборудование.
А насчет auto и lambda, конечно старый стандарт C++03 убогий и громоздкий по сравнению с новым C++11.
Если в результате подобной оптимизации, мы снижая стоимость, экономим 1-10 млн, то оно того стоит.
Разница в цене 1 и 100 серверов в 100 раз, не считая скидок. Разницы в кросс-аппаратной оптимизации одного ПО для 1 и 100 серверов нет. Это ПО можно будет использовать и в будущем на новых серверах. А за железо каждый раз надо платить. Поэтому, это применимо только для фирм думающих наперёд.
Поверьте, аппетиты фирм и объем данных растут гораздо сильнее, чем дешевеет оборудование.
А насчет auto и lambda, конечно старый стандарт C++03 убогий и громоздкий по сравнению с новым C++11.
Не понятно, почему общее число функций так велико — 3840. У меня получилось всего 325. Где ошибка?
считаем функции
Нужно учесть все перестановки из 5 элементов, плюс все уникальные префиксы длиной 1-4 от этих перестановок. Например для 35214 префиксы будут 3, 35, 352 и 3521.
Обозначим Fc(n) общее число функций. Очевидно, если проверяется только одно условие, нужна единственная функция.
Fc(1) = 1
Рекурсивное построение всех перестановок+уникальных префиксов для n элементов выглядит так. Сначала добавим n последовательностей длины 1 (сами элементы). Затем для каждого элемента i построим все перестановки и уникальные префиксы для оставшихся (n-1) элементов и припишем i спереди. Отсюда:
Fc(n) = n * (Fc(n-1)+1)
Fc(2) = 4,
Fc(3) = 15,
Fc(4) = 64,
Fc(5) = 325.
Обозначим Fc(n) общее число функций. Очевидно, если проверяется только одно условие, нужна единственная функция.
Fc(1) = 1
Рекурсивное построение всех перестановок+уникальных префиксов для n элементов выглядит так. Сначала добавим n последовательностей длины 1 (сами элементы). Затем для каждого элемента i построим все перестановки и уникальные префиксы для оставшихся (n-1) элементов и припишем i спереди. Отсюда:
Fc(n) = n * (Fc(n-1)+1)
Fc(2) = 4,
Fc(3) = 15,
Fc(4) = 64,
Fc(5) = 325.
немного кода
def permutationx(atoms):
if len(atoms)==1:
yield atoms
return
for pos,atom in enumerate(atoms):
yield atom,
for row in permutationx(atoms[:pos]+atoms[pos+1:]):
yield (atom,)+row
Большое спасибо за классный материал!
Божественная природа шаблонов видится во всем, начиная с простенькой стандартной sort и заканчивая вещами типа boost MultiIndex.
Божественная природа шаблонов видится во всем, начиная с простенькой стандартной sort и заканчивая вещами типа boost MultiIndex.
После слов «Вот рабочий вариант этого решения на C» идёт ссылка на C++ код. Исправьте, пожалуйста.
Чем он отличается от примера с C-оптимизацией из прошлой статьи можете посмотреть в diff с предыдущей версией
После этих слов, как я понимаю, должен идти diff двух кодов на C. Но вместо этого там сразу два diff'а: для C и C++
What a terrific coding standard.
Sign up to leave a comment.
Скорости разработки и исполнения, не достижимые на С