Я изучаю Unsafe Swift и пытаюсь понять, смогу ли я перевести на него некоторые алгоритмы C. Я некоторое время использовал некоторые алгоритмы C в своем коде Swift, чтобы получить сверхбыструю скорость выполнения для больших наборов данных, но я хотел бы получить аналогичные скорости, полностью написанные на Swift, без необходимости включать файлы C.
Для моего первого теста я перевел части LinkedList в UnsafeSwift. Вот версии C и UnsafeSwift и их функции для добавления элементов в любой конец списка:
// C Implementation
typedef struct LinkedList {
struct LinkedListNode *head;
struct LinkedListNode *tail;
} LinkedList;
typedef struct LinkedListNode {
void *data;
struct LinkedListNode *next;
} LinkedListNode;
void LinkedListInsertAtBeginning(struct LinkedList *list, void *newData) {
LinkedListNode *node = malloc(sizeof(LinkedListNode));
node->data = newData;
node->next = list->head;
list->head = node;
if (list->tail == NULL) {
list->tail = node;
}
}
void LinkedListInsertAtEnd(struct LinkedList *list, void *newData) {
if (list->head == NULL) {
LinkedListInsertAtBeginning(list, newData);
} else {
LinkedListNode *node = malloc(sizeof(LinkedListNode));
node->data = newData;
node->next = NULL;
list->tail->next = node;
list->tail = node;
}
}
// UnsafeSwift Implementation
class UnsafeLinkedList<Element> {
struct Node {
var data: UnsafePointer<Element>
var next: UnsafeMutableRawPointer?
}
var head: UnsafeMutableRawPointer?
var tail: UnsafeMutableRawPointer?
func addElementToFront(_ element: Element) {
let mutableData = UnsafeMutablePointer<Element>.allocate(capacity: 1)
mutableData.initialize(to: element)
var newNode = Node(data: mutableData)
newNode.next = head
let nodePointer = UnsafeMutableRawPointer.allocate(byteCount: MemoryLayout<Node>.stride, alignment: MemoryLayout<Node>.alignment)
nodePointer.initializeMemory(as: Node.self, to: newNode)
head = nodePointer
if tail == nil {
tail = head
}
}
func addElementToEnd(_ element: Element) {
let mutableData = UnsafeMutablePointer<Element>.allocate(capacity: 1)
mutableData.initialize(to: element)
let newNode = Node(data: mutableData)
let nodePointer = UnsafeMutableRawPointer.allocate(byteCount: MemoryLayout<Node>.stride, alignment: MemoryLayout<Node>.alignment)
nodePointer.initializeMemory(as: Node.self, to: newNode)
if head == nil {
head = nodePointer
tail = head
} else {
tail.unsafelyUnwrapped.assumingMemoryBound(to: Node.self).pointee.next = nodePointer
tail = nodePointer
}
}
}
Скорость выполнения модульных тестов примерно на 20% ниже, чем у C LinkedList. Я новичок в C и UnsafeSwift, поэтому пишу сюда за советом. Есть ли что-то в моем коде UnsafeSwift, что можно изменить, чтобы улучшить его производительность?
И что не менее важно для этого, посмотрите на источник, чтобы увидеть, как Apple это сделала: github.com/apple/swift-collections/tree/main/Sources/… (вы заметите использование ManagedBufferPointer)
Во-первых, я ожидаю, что большая проблема здесь заключается в том, что тест довольно несправедлив. Код Swift делает копию данных и берет на себя ответственность за управление их памятью, а код C просто держит указатель на них, предполагая, что что-то еще управляет памятью. Если вы собираетесь воспроизвести этот небезопасный подход к управлению памятью, обратите внимание на Unmanaged (или, возможно, ManagedBuffer). Я ожидаю, что почти все ваши 20% — это тот факт, что код Swift вызывает выделение дважды, а код C вызывает malloc один раз.
Невозможно сказать, как правильно переписать это в Swift, не зная, как вы обеспечиваете правильное управление памятью в C. Ваш пример предполагает, что вся эта работа выполняется вызывающей стороной. Таким образом, чтобы сделать это эквивалентным C, вы должны изменить функции, чтобы они принимали UnsafePointer<Element>
, а не Element
, и убрали лишние allocate
. (Но, конечно, это очень небезопасно, и вы должны убедиться, что весь остальной код идеален, как и в C.)
Тем не менее, вы сравнивали скорость этого, написанного на обычном Swift? Не думайте, что вы сможете победить оптимизатора, просто добавив «небезопасно». Начните с обычного Swift, посмотрите, какой SIL он производит (swiftc -O -emit-sil
), и исследуйте улучшения оттуда. Непонятно, как вы тестируете производительность здесь. Известно, что микротесты сложно разработать точно. (И, конечно же, для полноты картины вы строите с помощью -O
, верно?)
Спасибо! Похоже, я должен начать изучать ManagedBuffer
и много копаться в реализации Apple Deque
. Надеюсь, я не в своем уме!
Вы, наверное, правы насчет моих тестов. Я просто пишу классы в пакете Swift и выполняю тесты, помещая их в блоки XCTestCase measure { ... }
. Чтобы измерить код C, я создал класс-оболочку для взаимодействия с ним (это было намерением с самого начала — оболочка для взаимодействия с кодом C или другая оболочка для взаимодействия с UnsafeSwift). Я также написал версию на обычном Swift. Результаты скорости показали, что версия C была самой быстрой, версия Unsafe на 20% медленнее, а версия SafeSwift немного медленнее.
Ваш текущий подход в C не особенно оптимизирован для производительности. По сути, если вы хотите добиться очень высокой производительности, вам следует избегать выделения памяти ОС (т. е. вызова malloc). Это может быть очень медленно. Большинство хорошо настроенных структур данных производят выделение «кусков» (часто удваивая размер, когда им не хватает места), а затем сами управляют памятью. Вот для чего предназначен ManagedBuffer. Deque — отличное место для начала изучения этого вида кодирования в рабочей среде Swift.
Отмечаю этот ответ как правильный, потому что он направляет меня в правильном направлении. Спасибо!
Я предлагаю использовать github.com/apple/swift-collections/blob/main/Documentation/…