Function: the atomic unit of code

The First Nine Guide. Блок 1

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

1. По сложности алгоритма внутри функции
2. По типу ресурса, который потребляет функция
3. Потокобезопасность

Погнали по порядку!

Алгоритмическая сложность

Функция - это базовый кирпич производительности.

Первая и самая грубая оценка её поведения — это Big-O (О-большое).

Перед тем как вы будете закатывать глаза, скажу - не буду мучать математикой и тут все предельно просто. Чтобы не потеряться при анализе медленного кода достаточно:

• отличать O(1) от O(n^2)
• понимать, то что O(n log n) - граница, за ней только вечная боль
• и замечать, когда алгоритм внезапно становится O(n!)

Выше желтой линии начинает деградировать перформанс при увеличении объема обрабатываемых данных.

Вот примеры и пороги для n (для O(n!) реальные примеры придумать не смог ):

Типы потребляемых ресурсов

Скорость выполнения - это не всё, мы ж про перформанс!

Некоторые функции ждут диск, сеть или кэш, другие - кушают CPU.

Нам важно классифицировать функцию (желательно на этапе ее написания):

• IO-bound - ждёт сеть, диск, БД
• CPU-bound - парсит, считает
• Memory-bound - тащит данные из RAM, но не нагружает CPU
• GPU-bound - аналогично и понятно, кушает GPU

Это важно, чтобы понимать, где может быть зарыт ботлнек: в ядре, памяти, сокете или просто в алгоритме.

Потокобезопасность

Если код запускается параллельно - а он почти всегда запускается параллельно - важно ответить на вопросы:

• а мы не испортим ли общие данные?
• а мы не заблокируем ли соседей?

Разделяют 3 категории функций:

• Thread-safe - можно вызывать из любого потока
• Thread-unsafe - может всё поломать (знайте их в лицо!)
• Conditionally-safe - безопасен только при соблюдении условий

Потокобезопасные (Thread-Safe):

1. Работают с неизменяемыми (immutable) данными.
2. Не имеют общего изменяемого состояния.
3. Доступ к общим данным синхронизирован (через локи).
4. Используют только атомарные операции.

Потоконебезопасные (Thread-Unsafe):

1. Изменяют глобальное состояние.
2. Используют статичные изменяемые переменные.
3. Выполняют неатомарные операции "чтение-модификация-запись".
4. Примеры: strtok() в C, SimpleDateFormat в Java.

Условно-безопасные:

1. Безопасны при использовании внешней синхронизации.
2. Операции только для чтения над общими данными.

Call Overhead

Каждый инициализирующий вызов, любой функции создает отдельный участок памяти под себя,

он называется stack frame. 

Каждый новый вызов создает новый фрейм наверху стека, когда функция выполнена тогда кадр удаляется. Даже int sum(int a, int b) создаёт 16-64 байта накладных расходов.

Зачем это вообще знать?

Прост! (Ладно, расскажу)

• Сколько времени требуется на создание stack frame?
• 10-50 CPU циклов (очень быстро, но вот в цикле может быть больно)

Чем глубже закопана функция в коде через цепочку вызовов тем дороже ее вызывать (привет, stack overflow). Лямбды/анонимные функции еще дороже.

Грязный хак: inline-функция, она не кастует под собой создание stack frame, но try/catch/finally - ломают inlining

Типичные ловушки (заворачиваем с собой)

Циклы:

• Конкатенация строк в цикле (str += char часто дает O(n²)).
• Вложенные циклы по большим коллекциями (особенно не конечным коллекциям).

Риск переполнения стека (Stack Overflow):

• Каждый вызов функции создает фрейм на стеке (~100-1000 байт).
• Слишком глубокая рекурсия исчерпает стек (обычно ~1 МБ по умолчанию).

Hybrid-bound функции, смешивание типов:

• Blocking I/O в CPU функции это сложно дебажить и скейлить, лучше избегать

В следующем выпуске — разбор Runtime моделей.

Подписывайся на канал @r9yo11yp9e - будем искать девятки вместе :)