[Swift] Crash à la dé-allocation d'un certain nombre d'objets
Pyroh
Membre
Bonjour à tous,
J'ai un soucis de taille avec une linked list que j'ai implémenté à la main.
Problème:
Voilà la partie intéressante du code :
var allocCount = 0
public class ListNode<T> {
var next: ListNode<T>?
weak var previous: ListNode<T>?
var element: T
init(element: T) {
self.element = element
allocCount++
}
deinit {
allocCount--
}
}
public struct LinkedList<T> {
public typealias Element = T
private var head: ListNode<T>?
private var tail: ListNode<T>?
}
public extension LinkedList {
public mutating func append(element: Element) {
let node = ListNode<T>(element: element)
if head == nil || tail == nil {
self.head = node
self.tail = head
} else {
let old = tail
tail = node
old?.next = tail
tail?.previous = old
}
}
public mutating func removeAll() {
head = nil
tail = nil
}
}
allocCount ne sert qu'à vérifier qu'il n'y a a priori pas de leak et que tout est bien release avec une dealloc de liste.
Le code n'est pas fondamentalement compliqué, il est utilisé dans un projet plus gros et cause des plantages au moment où une instance de LinkedList est dé-alouée si et seulement si elle comporte un certain nombre d'éléments. Ce nombre varie selon ce qui est fait dans le code avant que la liste ne soit dé-allouée (une histoire de fou)...
Voilà le protocol de test :
var ll = LinkedList<Int>()
for i in 0..<count {
ll.append(i)
}
ll.removeAll()
assert(allocCount == 0)
Si count est dans les 75000 je suis gratifié d'un magnifique plantage. En dessous ça se passe sans ennui, au dessus c'est tout logiquement un plantage qui attend l'imprudent.
Tentative de solution:
J'ai réécris la méthode append en refactorisant le code: Echec
J'ai pensé que le côté générique de LinkedList pouvait être un soucis, je lui ai fait une cousine non générique nommée LinkedInt (le nom est évocateur) elle fait tout planter mais vers les 80000 éléments sans qu'on puisse définir un chiffre définitif comme avec la version générique...
Bref:
Je n'arrive pas à savoir d'où vient le problème, de moi, d'Xcode ou d'OSX.
A noter que je tourne avec Xcode 7 (testé avec β4 et β5) et sous El Capitan β6.
Si quelqu'un veut tester sur une config différente voilà un projet qui permet de reproduire le bug:
Réponses
Tu as lu les articles qu'on t'avait mentionné ? Tu as essayé de mieux travailler ta logique d'optimisation mémoire, d'utiliser isUniquelyReferenced() & co et de suivre les conseils de l'article similaire sur AirSpeed Velocity?
J'ai tout relu encore une fois, histoire d'être sur et franchement je ne vois pas où j'ai pu me planter.
Surtout sur un bout de code aussi concis.
J'ai pas mal testé l'implémentation avec des TU (un peu), de la Playground et les TU du projet principal (beaucoup, trop, j'aurai du mieux écrire les TU en rapport direct avec la liste). J'ai fait des schémas, déroulé du code sur feuille et debug manuellement avec des breakpoints. Tout cela n'est pas gage de qualité pour autant, on touche à un domaine un peu plus compliqué que ce que je fais d'habitude.
Et pourtant je n'arrive pas à voir ce qui ne va pas. Je n'essaie pas de découper ou copier la liste je fais juste un append tout simple ce qui fait qu'il n'y a pas de copie qui se fait a un moment. Il y a juste le cas d'element mais normalement c'est pas mon boulot ça...
Et surtout j'ai beaucoup de mal à comprendre pourquoi ça ne pose pas de problème en dessous d'un certain nombre d'objets...
MAJ:
J'ai compris ! Chaque fois qu'un ListNode va être deinit il va deinit next qui va deinit next qui va deinit next qui va deinit next etc...
Une récursive qui finit en function stack overflow...
Alors bug ou pas bug ? Si pas bug je fais quoi ?
ça je l'ai fait par la suite pensant que c'était le soucis. ça n'aide pas.
Mais si on regarde bien tail va certes être mis à nil en tant que next mais comme c'est une propriété il sera mis a nil de toute façon que ce soit par removeAll() ou le deinit de base.
Instruments montre bien que c'est un function stack overflow car chaque deinit appelle le deinit sur next et ainsi de suite, avec trop de nodes ça déborde...
Maintenant est-ce un bug ? J'ai l'impression que ça demanderait pas mal de changements pour fixer ça...
(ps: que je rêve de pouvoir taper mes posts en Markdown !)
Bon, alors personnellement, comment je ferais :
1) Je mettrais l'implémentation complète (donc y compris les variables head et tail) de ma liste dans une classe, ce qui permet d'écrire un deinit et éviter la récursion (en itérant sur les noeuds dans le "bon sens" pour maitriser l'ordre de destruction des noeuds) : En gros une boucle qui à chaque itération met à nil le next de l'avant dernier noeud. Donc plus de deinit recursifs, mais un deinit par itération.
2) Le contenu de la struct exposée ne serait du coup plus qu'une référence sur une instance de cette classe. Du coup le passage par valeur copie un minimum de chose (une référence).
3) Les fonctions entrainant une mutation de la liste et déclarées dans la struct se contentent de vérifier si une copie est nécessaire, font la copie le cas échéant, et délèguent ensuite l'opération à l'objet référencé.
On va dire que les grands esprits se rencontrent, je venais de trouver la solution quand j'ai été notifié de ton post !
J'ai modifié removeAll() de la sorte pour tester:
La ligne est un peu bizarre mais permet de limiter les itérations, j'ai les mêmes perfs qu'avec le dealloc classique. J'ai testé avec 70000 éléments ça s'effectue dans une fourchette de temps identique.
La prochaine étape est, comme tu dis, de mettre une classe intermédiaire pour controller tout ça lors du deinit.
ça serait bien qu'ils mettent un deinit sur les struct d'ailleurs...
Merci à tous !!
PS: J'ai quand même rempli un rdar si jamais mais je ne pense pas qu'ils feront quelque chose...
Je divise le nombre d'itérations par 10 en faisant ça. Mais le gain est négligeable au final...
Oui c'est vrai au final qu'il est bien plus qualifié que moi dans le domaine !
Par contre si j'arrive à gagner beaucoup de temps quand je scinde une LinkedList, j'en perds encore plus avec append(...) vu qu'il doit allouer un ListNode à chaque fois... J'en arrive a douter de l'utilité de la chose...