Object Pooling

23rd juillet, 2009 par Floz

Ça fait un moment que je veux mettre à plat ce que j’ai compris vis à vis des techniques d’Object Pooling et de Linked List, et nous y voilà. On va commencer par l’Object Pooling.

L’Object Pooling est une structure de programmation (ou Design Pattern) qui consiste en une liste d’objets disponibles à l’utilisation.

En gros, au lieu de passer par un new PooledObject( params… ), on utilisera une méthode similaire à Pool.create( params… ), qui nous renverra le PooledObject en question (comme nous l’aurait fait new PooledObject( params… )). La différence principale réside dans le fait que, derrière, la classe Pool regorge un certains nombres d’objets qui n’attendent qu’à être utilisés.

Instancier un objet, et passer par l’opérateur new s’avère assez gourmand en ressources. Du coup, créer une liste d’objet s’avère intéressant car :
- On instancie les objets par pack (la quantité est à définir en fonction des besoins),
- Une seule référence pour toute la liste (et donc tous les objets) est nécessaires.

Cette structure nous offre donc un gain en terme de performances, et de mémoire.

Voyons ce que ça donne au niveau du code. J’ai fais quelques schémas aussi pour représenter visuellement ce qu’il se passe
A noter que le modèle de code provient du wiki de Joa Ebert. C’est à partir de ce lien que j’ai appris quasiment tout ce que je sais à propos de l’Object Pooling.

1) L’initialisation de la liste.

Dans le lien ci dessus, l’initialisation de la liste se fait au premier appel de la méthode statique create();

// - CONSTS ----------------------------------------------------------------------

private const GROWTH_RATE:int = 4;

// - PRIVATE VARIABLES -----------------------------------------------------------

private var _allowInstanciation:Boolean;
private var _availableInPool:int;
private var _currentPooledCircle:PooledCircle;

private var _next:PooledCircle;

public static function create():PooledCircle
{
var pooledCircle:PooledCircle;

if ( !_availableInPool )
{
var i:int = GROWTH_RATE;
while ( --i > -1 )
{
_allowInstanciation = true; {
pooledCircle = new PooledCircle();
} _allowInstanciation = false;

pooledCircle._next = _currentPooledCircle;
_currentPooledCircle = pooledCircle;
}

_availableInPool = GROWTH_RATE;
}

pooledCircle = _currentPooledCircle;
_currentPooledCircle = pooledCircle._next;

--_availableInPool;

return pooledCircle;
}

Ici, l’instanciation des objets se fait à partir d’une boucle while. Dans cet exemple, le premier objet crée au sein de cette boucle, sera le dernier disponible de la liste.
On note aussi l’existence d’une variable _currentPooledCircle. Celle ci contient la référence au prochain objet qui sera utilisé, et donc à l’objet renvoyé lors de l’appel de la méthode create().

A l’appel de la méthode create(), la valeur de _currentPooledCircle change : elle devient _currentPooledCircle._next, soit le prochain objet disponible.

Si _availableInPool arrive à 0, c’est qu’il n’y a plus d’objets disponibles. Ainsi, nous devons “refaire le plein” d’objets. A noter que lorsque _availableInPool est égal à 0, la valeur de _currentPoolCircle est null.

Bon, visuellement ça donne ça :

Les pastilles vertes correspondent à des objets disponibles.
La pastille vertes clair/tournant au jaune correspond à _currentPooledCircle et donc au prochain objet qui sera utilisé.
La pastille avec une croix orange correspond à un élément null.
Les flèches correspondent au lien entre chaque objet. Elles représentent la valeur de _next.

2) Création (récupération) d’un élément : appel à la méthode create().

Dans notre cas, l’initialisation se fait lors du premier appel de la méthode create(). Ainsi, l’initialisation sera directement suivi de l’attribution du premier objet disponible. Il y aura donc un objet disponible en moins dans la liste.
Le schéma qui va suivre représente plusieurs appel de la méthode create(), jusqu’à ce que _availableInPool soit égal à 0.

Une nouvelle pastille fait son apparition : pastille rouge, pour illustrer un élément “utilisé”.

A la fin du schéma, nous sommes donc à :
- _availableInPool = 0;
- _currentPooledCircle = null;

Sur le schéma, _currentPooledCircle est représenté par la pastille avec la croix orange.

Le prochain appel à la méthode create() se résultera par un nouveau remplissage de la liste.

3) Ré-initialisation de la liste.

Voici le schéma représentatif :

Ainsi, on conserve bien nos anciens objets. Ils sont toujours “là”.
Mais de nouveaux font leurs apparition, et eux ils sont disponibles à l’utilisation. A cet instant, la valeur de _availableInPool vient de passer à 4 (qui est la valeur de GROWTH_RATE).

Les deux dernières étapes se répèteront infiniment, au besoin.

4) Suppression d’un élément de la liste.

L’Object Pooling offrant comme principal avantage l’économisation de l’instanciation d’un objet (on privilégie la réutilisation), il serait intéressant de pouvoir rendre de nouveau disponible un objet qui ne l’est plus.

Dans la structure proposé par Joa Ebert, on a le modèle suivant :

public static function release( pooledCircle:PooledCircle ):void
{
pooledCircle._next = _currentPooledCircle;
_currentPooledCircle = pooledCircle;

++_availableInPool;
}

public function dispose():void
{
release( this );
}

Ainsi, rendre disponible un objet se fera par l’appel de la méthode dispose() (public) de celui ci.
Ex : pooledCircle.dispose(); // Soit pooledCircle une instance renvoyée par la méthode create();

Ou par la méthode release (public static) de la classe PooledCircle.
Ex : PooledCircle.release( pooledCircle );

Il s’en suit donc la remise en disposition de l’objet qui vient d’être libérer. La valeur de _currentPooledCircle devient donc égale à pooledCircle de nos exemples précédents.
L’ancienne valeur de _currentPooledCircle est attribuée à pooledCircle.next();

Le schéma représentatif :

En 1), l’état de la liste après 3 appels de la méthode create().
En 2), l’état de la liste après un appel de la méthode release( pooledCircle:PooledCircle ) ou dispose() (cf plus haut), sur le second objet qui a été récupéré via la méthode create().
En 3), l’état de la liste après un autre appel de la méthode release( pooledCircle:PooledCircle ) ou dispose(), sur le premier objet qui a été récupéré via la méthode create().

Il faut donc bien noter qu’on ne supprime pas un objet, on le rend de nouveau disponible (ne pas oublier de libérer les références de l’ancienne vie de l’objet, pour libérer la mémoire et éviter les comportements chelou au moment d’une nouvelle attribution).

4) Conclusion

Il est donc intéressant de passer par une liste d’objets de la sorte, notamment lorsqu’un certain nombre d’objets doit être crée.
Tweensy, moteur de tween, utilise d’ailleurs une structure d’Objet Pooling, couplé a un Array pour pouvoir parcourir la liste des objets crées.

C’est aussi ce que j’ai souhaité faire avec M4Tween, couplé a une linked list (plus intéressant d’itérer de cette manière qu’à travers un tableau). Mais je dois revoir quelques trucs sur la classe de M4Tween…

Je pense que je posterai prochainement sur les LinkedList.
En attendant, vous trouverez pas mal d’infos à ce sujet sur wikipedia et encore et toujours sur le wiki de Joa Ebert. A noter que le wiki de Joa Ebert ne propose qu’une représentation unique d’une LinkedList. Vous verrez sur wikipedia qu’il en existe plusieurs

Si des choses ne sont pas claires, n’hésitez pas !

Tags: Design pattern, LinkedList, object pooling, tween, tweensy, wiki
Posté dans Flash | 2 Commentaires »