Pull to refresh
  • by relevance
  • by date
  • by rating

Как перезапустить закон Мура программными методами. Ускорение софта в тысячи раз

VDSina.ru corporate blogDesigning and refactoringAlgorithmsDevelopment ManagementSoftware
Профессор Никлаус Вирт был прав. Создатель языка Pascal, соавтор технологии структурного программирования, лауреат премии Тьюринга в 1995 году заметил:

«Замедление программ происходит куда быстрее, чем ускорение компьютеров»


С тех пор это высказывание считается законом Вирта. Он фактически нивелирует закон Мура, согласно которому количество транзисторов в процессорах удваивается примерно с 1965 года. Вот что пишет Вирт в статье «Призыв к стройному софту»:

«Около 25 лет назад интерактивный текстовый редактор умещался всего в 8000 байт, а компилятор в 32 килобайта, тогда как их современные потомки требуют мегабайтов. Стало ли всё это раздутое программное обеспечение быстрее? Нет, совсем наоборот. Если бы не в тысячу раз более быстрое железо, то современное программное обеспечение было бы совершенно непригодным».

С этим трудно не согласиться.
Читать дальше →
Total votes 90: ↑76 and ↓14 +62
Views53.2K
Comments 467

Ускоряем на 70% игру на процессоре в 1 МГц

AssemblerGame developmentOld hardwareGames and game consoles
Translation

Давным-давно, во времена студенчества в колледже я немного занимался разработкой компьютерных видеоигр. Это была эпоха 8-битных PC, когда игровое оборудование по современным стандартам было почти невозможно медленным.

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

Это история об одном из таких трюков.

Я постараюсь припомнить все важные подробности, однако в чём-то могу ошибиться. Если так случится, простите меня, это было очень давно.

Исходные данные


Мой друг, одарённый программист, почти закончил свою новую игру. Каким-то образом ему удалось почти без изменений уместить в компьютер эпохи 1980-х довольно впечатляющую графически на то время игру, популярную на аркадных автоматах.

Единственная проблема заключалась в том, что его версия игры оказалась неиграбельной. Она работала слишком медленно, а дёрганые движения мешали вовлечённости игрока, ведь игра была сайд-скроллером.

Мой друг, работавший над игрой параллельно с учёбой в колледже, начал уже ощущать себя немного вымотанным. Опасаясь, что мог упустить какую-нибудь простую оптимизацию, он попросил посмотреть код меня.

Я посмотрел. Но там нельзя было найти никакой простой оптимизации.
Читать дальше →
Total votes 125: ↑125 and ↓0 +125
Views28.5K
Comments 96

Дискретный арктангенс в процессоре NES

Game development
Translation

Геймплей моей игры Star Versus основан на поворотах. Объекты отслеживают направление, в котором они смотрят, и на каждом цикле движка двигаются в этом направлении. В такой ситуации требуется много тригонометрии, бо́льшую часть которой можно ради эффективности вычислить заранее, однако иногда это невозможно. В частности, паре геймплейных элементов нужно находить арктангенсы, и делать это быстро.


Определение арктангенса: в прямоугольном треугольнике arctan вычисляет один из непрямых углов, используя в качестве входных данных длину стороны, противоположной этому углу, разделённую на длину прилежащей стороны. В случае Star Versus сторонами треугольника являются расстояния X/Y между двумя объектами, например, снарядом и кораблём, а угол — это направление, в котором должен двигаться первый, чтобы достичь второго.
Читать дальше →
Total votes 12: ↑11 and ↓1 +10
Views2.3K
Comments 13

Ищем простые числа до триллиона за тридцать минут

High performanceAlgorithmsC#Mathematics
image

Поиск простых чисел — популярная задача среди программистов, увлекающихся математикой. Самый известный алгоритм, придуманный, по-видимому, больше двух тысяч лет назад, — решето Эратосфена; в настоящее время существует бесчисленное множество его вариантов и оптимизаций.

Сегодня я хотел бы поделиться с вами различными вариантами реализации поиска простых чисел на языке C#, начиная с классических алгоритмов — решета Эратосфена, Сундарама и Аткина, и кончая различными оптимизациями (сегментация, факторизация). Особый упор я делал на простоту: самый быстрый из алгоритмов, который мне удалось получить, содержит 120 строк кода и ищет простые числа до триллиона меньше, чем за 30 минут, а до миллиарда — меньше, чем за секунду (это далеко от производительности лучших из существующих библиотек по поиску простых чисел, но эти библиотеки обычно содержат свыше 4000 строк кода).
В заключение мы применим самую быструю реализацию для поиска максимального расстояния между двумя соседними простыми числами до триллиона. Прежде чем заходить под кат, я предлагаю вам попытаться угадать ответ. Для сравнения, для простых чисел до 100 максимальное растояние равно 8 (между соседними простыми числами 89 и 97), а до тысячи — 20 (между 887 и 907).

Весь исходный код можно найти на гитхабе.
Читать дальше →
Total votes 37: ↑37 and ↓0 +37
Views7.4K
Comments 14

Оптимизация сборок Android приложений: ProGuard, D8, R8. Тайны обфускации

Development for Android

Оптимизация сборки — вишенка на торте мобильного приложения. К счастью, существуют инструменты, проверенные временем и заслужившие доверие сообщества. К сожалению, ее не всегда воспринимают всерьез и не уделяют ей должного внимания. Почему в оптимизации должны быть заинтересованы все? Как выжать максимум из мобильного приложения? Как работают инструменты, которыми мы привыкли пользоваться в паре строк? И что нам продают под словом «обфускация»?

Читать далее
Total votes 17: ↑16 and ↓1 +15
Views4.9K
Comments 2

«Любовь. Python. C++». Доклад Яндекса

Яндекс corporate blogAbnormal programmingPythonC++Server optimization
Что связывает языки Python и C++? Как извлечь из этого выгоду лично для себя? На большой конференции Pytup Александр Букин показал способы, благодаря которым можно оптимизировать свой код, а также выбирать и эффективно использовать сторонние библиотеки.

— Всем привет, меня зовут Александр Букин, я разрабатываю Яндекс.Погоду. Вы еще можете знать меня как сооснователя Pytup. Также я состою в программных комитетах таких классных конференций, как PyCon.ru и YaTalks.

Сегодня мы с вами поговорим о любви Python и C++. А точнее — о том, что же их объединяет, эти два прекрасных языка и, на самом деле, еще C, и что мы можем почерпнуть из этих прекрасных отношений.
Читать дальше →
Total votes 14: ↑11 and ↓3 +8
Views5.2K
Comments 2