Программирование
Swift
20 августа 2014

Секреты скорости Swift

Автор оригинала: Mike Ash
Перевод
С момента анонса языка Swift скорость была ключевым элементом маркетинга. Еще бы – она упоминается в самом названии языка (swift, англ. — «быстрый»). Было заявлено, что он быстрее динамических языков наподобие Python и Javascript, потенциально быстрее Objective C, а в некоторых случаях даже быстрее, чем C! Но как именно они это сделали?

Спекуляции


Несмотря на то, что сам язык предоставляет огромные возможности для оптимизации, у нынешней версии компилятора с этим не все в порядке, и получить хоть какие-то успехи в тестах производительности стоило мне немало сил. В основном это происходит из-за того, что компилятор генерирует массу излишних действий retain-release. Думаю, что это быстро поправят в следующих версиях, но пока мне придется говорить о том, благодаря чему Swift может быть потенциально быстрее Objective C в будущем.

Более быстрая диспетчеризация методов


Как известно, каждый раз, когда мы вызываем метод в Objective C, компилятор транслирует его в вызов функции objc_msgSend, которая занимается поиском и вызовом нужного метода в рантайме. Она получает селектор метода и объект, в таблицах методов которого производится поиск непосредственного куска кода, который будет обрабатывать этот вызов. Функция работает очень быстро, но зачастую делает куда больше работы, чем действительно нужно.

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

С другой стороны, в 99.999% случаев вы не будете врать компилятору. Когда объект объявлен как NSView *, это либо непосредственно NSView, либо дочерний класс. Динамическая диспетчеризация необходима, а вот настоящая пересылка сообщений практически не нужна, но природа Objective C заставляет всегда использовать самый «дорогой» вид вызовов.

Вот пример кода на Swift:

class Class {
    func testmethod1() { print("testmethod1") }
    @final func testmethod2() { print("testmethod2") }
}

class Subclass: Class {
    override func testmethod1() { print("overridden testmethod1") }
}

func TestFunc(obj: Class) {
    obj.testmethod1()
    obj.testmethod2()
}

В эквивалентном коде на Objective C компилятор превратил бы оба вызова методов в вызовы obj_msgSend – и дело с концом.

В Swift же компилятор может воспользоваться более строгими гарантиями, предоставляемыми языком. Мы не можем соврать компилятору. Если тип выражения – Class, то объект может быть либо непосредственно этого типа, либо дочернего.

Вместо вызова objc_msgSend компилятор Swift генерирует код, который вызывает метод с помощью таблицы виртуальных вызовов. По сути, это просто массив указателей на функции, хранящийся внутри класса. Код, который компилятор сгенерирует для первого вызова, будет примерно такой:

methodImplementation = object->class.vtable[indexOfMethod1]
methodImplementation()

Несмотря на все кеширование и ассемблерные оптимизации в objc_msgSend, обычное обращение к индексу массива всегда будет значительно быстрее, и это ощутимый плюс.

С вызовом testMethod2 все еще лучше. Поскольку он объявлен с модификатором @final, компилятор может гарантировать, что этот метод нигде не переопределен. Что бы ни происходило дальше, вызов метода всегда будет связан с его реализацией в классе Class. Благодаря этому можно даже не использовать обращение к таблице виртуальных методов, а напрямую вызвать реализацию, в моем случае располагавшуюся в методе со внутренним именем __TFC9speedtest5Class11testmethod2fS0_FT_T_.

Разумеется, это не такой уж колоссальный прорыв в плане производительности. Кроме того, Swift все равно будет использовать objc_msgSend для обращения к объектам Objective C. Но сколько-то процентов это все равно обеспечит.

Более умные вызовы методов


Оптимизации вызова методов могут быть куда более значительными, чем просто использование более оптимальной схемы диспетчеризации. Компилятор может производить их, анализируя поток управления. Например, вызовы метода могут быть встроены или же убраны насовсем.

Например, мы возьмем и удалим тело метода testmethod2, оставив его пустым:

@final func testmethod2() {}

Компилятор смог догадаться, что теперь данный метод ничего не делает. При включенных оптимизациях вызов этого метода вообще не генерируется. Вызывается testmethod1 – и все.

Подобные подходы работают не только с методами, помеченными атрибутом @final. Например, если код слегка изменить следующим образом:

let obj = Class()
obj.testmethod1()
obj.testmethod2()

Поскольку компилятор видит, где и чем инициализируется переменная obj, он может быть уверен, что к моменту вызова testmethod1 в нее не может попасть объект дочернего класса, а следовательно динамическая диспетчеризация не нужна ни в первом, ни во втором случае.

Рассмотрим еще один крайний случай:

for i in 0..1000000 {
    obj.testmethod2()
}

В Objective C данный код пошлет миллион сообщений и будет выполняться значительное время. Swift же знает о том, что метод не имеет никаких побочных эффектов, и с чистой совестью может убрать весь цикл, позволяя коду выполняться моментально.

Меньше операций выделения памяти


Располагая достаточной информации, компилятор может убирать лишние операции выделения памяти. Например, если создание и все случаи использования объекта ограничиваются локальной областью видимости, его можно разместить на стеке вместо кучи, что гораздо быстрее. В редких случаях, когда вызовы методов на объекте не используют сам объект, его размещение вообще можно не производить! Вот, например, довольно смешной код на Objective C:

for(int i = 0; i < 1000000; i++)
    [[[NSObject alloc] init] self];

Objective C честно создаст и удалит миллион объектов, послав три миллиона сообщений. Эквивалентный код на Swift, при наличии достаточного компилятора, сможет вообще не генерировать никаких инструкций для этого кода, если метод self не делает ничего полезного и никак не ссылается на объект, на котором он был вызван.

Более эффективное использование регистров


Каждый метод на Objective C принимает два неявных параметра – self и _cmd, после которых передаются все остальные. На большинстве архитектур (в том числе x86-64, ARM, ARM64) первые параметры передаются через регистры, а оставшиеся кладутся в стек. Регистры работают гораздо быстрее, поэтому передача параметров через них может сказаться на производительности.

Неявный параметр _cmd практически никогда не используется. Он нужен только в том случае, если вы пользуетесь настоящей динамической пересылкой сообщений, чего 99.999% кода на Objective C никогда не делает. Регистр при этом все равно занимается, а их не так уж много: на ARM – четыре, x86-64 – шесть, а на ARM64 – восемь.

В Swift такого параметра нет, что позволяет передавать больше «полезных» параметров через регистры. Для методов, которые принимают много аргументов, это также означает небольшой прирост производительности при каждом вызове.

Дублирующие указатели


Можно привести много примеров того, когда Swift работает быстрее чем Objective C, но как насчет обычного C?

Указатель считается дублирующим, когда кроме него существует еще один указатель на эту же область памяти. Например:

int *ptrA = malloc(100 * sizeof(*ptrA));
int *ptrB = ptrA;

Ситуация непростая: запись в ptrA повлияет на чтение из ptrB, и наоборот. Это может негативно повлиять на то, какие оптимизации компилятор сможет провести.

Вот, например, наивная реализация функции memcpy из стандартной библиотеки:

void *mymemcpy(void *dst, const void *src, size_t n) {
    char *dstBytes = dst;
    const char *srcBytes = src;

    for(size_t i = 0; i < n; i++)
        dstBytes[i] = srcBytes[i];

    return dst;
}

Разумеется, копировать данные побайтово абсолютно неэффективно. Скорее всего, нам бы хотелось копировать данные более крупными кусками: инструкции SIMD позволяют переносить сразу по 16 или 32 байта, что в разы ускорило бы функцию. В теории, компилятору следовало бы догадаться о предназначении данного цикла и использовать эти инструкции – но из-за возможности дублирования указателей он не имеет право этого делать.

Для понимания посмотрим на следующий код:

char *src = strdup("hello, world");
char *dst = src + 1;
mymemcpy(dst, src, strlen(dst));

При использовании стандартной функции memcpy вы бы получили ошибку, поскольку она не позволяет копировать перекрывающиеся области данных. Наша же функция таких проверок не содержит и в данном случае будет вести себя неожиданным образом: в первой итерации символ ‘h’ будет скопирован c позиции 1 на позицию 2, во второй – с 2 на 3, и так до тех пор, пока вся строка не будет забита одним и тем же символом. Не совсем то, чего мы ждали.
Именно по этой причине memcpy не принимает перекрывающиеся указатели. Для такого случая есть специальная функция memmove, но она требует дополнительных операций и, соответственно, работает медленнее.

Компилятор ничего не знает о данном контексте. Ему невдомек, что мы предполагаем передавать в функцию неперекрывающиеся указатели. Если рассмотреть два случая – когда указатели перекрываются и когда нет – то оптимизация не может быть проведена для одного, если она меняет результат в другом. На данный момент компилятор понимает только то, что мы хотим получить строку «hhhhhhhhhhhh». Она нам необходима. Код, который мы написали, требует этого. Любая оптимизация обязана оставить поведение в данном случае именно таким, даже если нам на него абсолютно наплевать.

Clang постарался над этой функцией на славу. Он генерирует код, который проверяет перекрытие указателей, и только в противном случае использует оптимизированный алгоритм. Вычислительная сложность этой проверки, которую компилятор вынужден проводить по причине незнания контекста, довольно мала, но все же не равна нулю.

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

Распространенность этой проблемы вынудила добавить в стандарт C99 новое ключевое слово restrict. Оно говорит компилятору, что указатели не пересекаются. Если применить этот модификатор к нашим параметрам, сгенерированный код будет более оптимальным:

 void *mymemcpy(void * restrict dst, const void * restrict src, size_t n) {
    char *dstBytes = dst;
    const char *srcBytes = src;

    for(size_t i = 0; i < n; i++)
        dstBytes[i] = srcBytes[i];

    return dst;
}

Можно считать, что проблема решена? Но… как часто вы использовали это ключевое слово в своем коде? Чувствую, что ответом большинства читателей будет «ни разу». В моем случае, я впервые в жизни использовал его, пока писал пример выше. Оно используется для самых критичных к производительности мест, в остальных же случаях мы просто плюем на неоптимальность и идем дальше.

Перекрытие указателей может всплыть в местах, где вы этого совсем не ждете. Например:

- (int)zero {
    _count++;
    memset(_ptr, 0, _size);
    return _count;
}

Компилятор вынужден предполагать вариант, когда _count указывает туда же, куда и _ptr. Поэтому он генерирует код, который увеличивает _count, сохраняет его значение, вызывает memset, а потом снова считывает _count для возврата. Мы-то знаем, что _count не может поменяться за время работы memset, и в повторном чтении нет необходимости, но компилятор обязан это сделать – на всякий пожарный. Сравните этот пример со следующим:

- (int)zero {
    memset(_ptr, 0, _size);
    _count++;
    return _count;
}

Если вызов memset сдвинуть вверх, потребность в повторном считывании _count исчезает. Это крошечный выигрыш, но все же он есть.

Даже безобидный на первый взгляд NSError ** может повлиять на ситуацию. Представим себе метод, интерфейс которого предполагает возможность ошибки, однако текущая реализация никогда ее не вызывает:

 - (int)increment: (NSError **)outError {
    _count++;
    *outError = nil;
    return _count;
}

Опять же, компилятор вынужден генерировать избыточное повторное чтение _count на тот случай, если вдруг outError смотрит туда же, куда и count. Это было бы очень странно, поскольку правила C обычно не позволяют указателям разных типов перекрываться, и выкинуть данное считывание было бы вполне безопасно. Видимо, Objective C каким-то образом ломает эти правила своими надстройками. Конечно, можно добавить restrict – но едва ли вы вспомните об этом в нужный момент.

В коде на Swift такое встречается гораздо реже: как правило, вам не приходится оперировать указателями на произвольные объекты, а семантика массивов не позволяет указателям перекрываться. Это позволяет компилятору Swift генерировать более оптимальный код с меньшим количеством дополнительных сохранений и считываний на тот случай, если вы все-таки воспользуетесь перекрывающимися указателями.

Подводя итоги


В Swift есть несколько хитростей, позволяющих генерировать код более оптимальный, чем на Objective C. Меньше динамической диспетчеризации, возможность встраивания методов, отказ от передачи ненужных аргументов – все это приводит к повышению скорости вызовов. Также, поскольку указатели в Swift встречаются очень редко, компилятор может проводить более эффективные оптимизации.

Примечание переводчика:

Статья написана полтора месяца назад. С тех пор уже появились посты, подтверждающие отличную работу оптимизатора на практике. Знание английского не обязательно, достаточно посмотреть на таблицы.
+28
23,6k 131
Комментарии 13