Ответы пользователя по тегу Языки программирования
  • Есть ли основные правила супер оптимизации?

    ErmIg
    @ErmIg
    Программист
    Есть развернутый ответ для С++ кода, но его можно обобщить и на другие языки и платформы:

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

    1) Важно понимать, что алгоритмическая оптимизация практически всегда может дать лучший эффект, чем программная. Так, если алгоритм имеет сложность O(n^2), то на больших исходных данных он при любой оптимизации будет медленнее, чем неоптимизированный алгоритм сложности O(n). Впрочем, при выборе алгоритма, опираться только на его сложность не стоит: если объем исходных данных не велик, то вполне может оказаться, что алгоритм со сложностью O(n^2) будет работать быстрее, чем с O(n).
    2) Очень важно повторное использование (кеширование) промежуточных данных, вычисленных в программе – ибо быстрее всего выполняется работа, которую не надо делать. Тем не менее, не надо чрезмерно кешированием увлекаться – если объем кэшируемых данных слишком велик, то это может отрицательно сказаться на общей производительности программы (некоторые данные быстрее вычислять на лету, чем считывать из памяти).
    3) Следует избегать излишнего копирования данных (например, передавать сложные типы данных по ссылке, а не по значению).
    4) По возможности следует избегать условных операторов во вложенных циклах. Так как условные переходы, вызываемые такими операторами, плохо обрабатываются современными процессорами с конвейерной архитектурой.
    5) Данные в памяти, которые используются алгоритмами, должны по возможности лежать упорядочено, и использоваться последовательно. Это позволит процессору их эффективно кешировать. Важно помнить, что доступ к кэшу процессора значительнее быстрее, чем к оперативной памяти.
    6) Если алгоритмы это позволяют, то возможно стоит реализовать их параллельное исполнение (в отдельных потоках или процессах). Это позволит эффективно задействовать современные многоядерные процессы.
    7) В некоторых случаях (например обработка изображений) большого эффекта можно достичь применением специализированных расширений процессора (SSE, SSE2, AXX, AVX2 и другие). Стоит отметить, что большинство современных компиляторов (GCC, MSVS, ICC) поддерживают непосредственное использование данных расширений непосредственно из С++ кода при помощи специальных встроенных функций (intrinsics). Минусами такого подхода является потеря переносимости (впрочем, эта проблема решается наличием разных веток программы под разные процессоры) и значительное усложнение программы.
    8) Также большого эффекта можно достичь применением специализированных ускорителей, например GPU (технологии CUDA, OpenCL). Минусами таких решений являются потеря универсальности и значительное усложнение программы, а также то, что на специализированных ускорителях, как правило, хорошо работает далеко не каждый алгоритм.
    Ответ написан