пілотної частини я розповів про завдання як можна докладніше. Розповідь вийшов довгим і безпредметним — в ньому не було ні одного рядка коду. Але без розуміння завдання дуже складно займатися оптимізацією. Звичайно, деякі техніки можна застосовувати, маючи на руках тільки код. Наприклад, кешувати обчислення, скорочувати розгалуження. Але мені здається, що деякі речі без розуміння завдання просто ніколи не зробити. Це і відрізняє людину від оптимізуючого компілятора. Тому ручна оптимізація все ще відіграє величезну роль: у компілятора є тільки код, а у людини є розуміння завдання. Компілятор не може прийняти рішення, що значення "4" досить випадково, а людина може.

Нагадаю, що мова піде про оптимізацію операції ресайза зображення методом згорток у реально існуючій бібліотеці Pillow. Я буду розповідати про тих змінах, що я робив кілька років тому. Але це не буде повторення слово-в-слово: оптимізації будуть описані в порядку, зручному для оповідання. Для цих статей я зробив в репозиторії окрему гілку від версії 2.6.2 — саме з цього моменту і буде йти розповідь.
Читати далі →

Як я зробив найшвидший ресайз зображень. Частина 0

Привіт, мене звати Саша, я написав найшвидший ресайз зображень для сучасних процесорів х86. Я так стверджую, оскільки всі інші бібліотеки, які я зумів знайти і протестувати, виявилися повільніше. Я зайнявся цим завданням, коли працював над оптимізацією ресайза картинок на льоту Uploadcare. Ми вирішили відкрити код і в результаті з'явився проект Pillow-SIMD. Будь-хто з легкістю може використовувати його в додатку на мові Python.
Будь-код виконується на конкретному залозі і гарну оптимізацію можна домогтися, лише розуміючи його архітектуру. Всього я планую випустити 4 або 5 статей, в яких розповім як застосовувати знання архітектури заліза для оптимізації реальної задачі. Своїм прикладом я хочу спонукати вас оптимізувати інші прикладні задачі. Перші дві статті вийдуть протягом тижня, решта — по мірі готовності.
Читати далі →

Історія одного бага: вирівнювання даних на x86

Одного разу мені довелося вираховувати суму векторів цілих чисел.

Звучить незвично. Кому знадобиться робити це в реальному житті? Зазвичай такі обчислення зустрічаються тільки в задачках з початкової школи або бенчмарках компілятора. Але зараз це сталося насправді.

В реальності стояло завдання перевірити контрольну суму заголовків IPv4, яка є сумою обернених кодів (доповнень до одиниці) двухбайтных машинних слів. Простіше кажучи, це означає додавання всіх слів і всіх бітів перенесення, які виробляються в процесі. У цієї процедури є декілька приємних особливостей:

  • її можна ефективно виконати з допомогою процесорної інструкції
    ADC
    (на жаль, ця функція недоступна в C);
  • її можна виконати на словах будь-якого розміру (можете додати за бажанням восьмибайтные значення, тільки результат слід зменшити до двох байт і додати всі біти переповнення);
  • вона нечутлива до порядку проходження байтів (дивно, але це так).

Читати далі →

Нові рішення старої завдання

image
Або переклад велосипеда на реактивну тягу
Існує одна дуже стара завдання, вік якої дорівнює віком Американського Стандартного Коду для Обміну Інформацією. Конкретніше — це завдання перетворення цілого числа в його шістнадцяткове подання ASCII рядком.
В даній публікації будемо розглядати перетворення цілого беззнакового шестидесятичетырехбитного числа в рядок фіксованої довжини без скорочення старших нулів.
Завдання на перший погляд здається елементарною. Вона і була б такою, якби таблиця ASCII була іншою. Але маємо, те що маємо.
Всі рішення будуть тільки для IA-32 і Intel © 64 архітектури.

Читати далі →