Placement new, allocateur et conteneur

Article suivant: Référence constante sur référence
Article précédent: Ne pas empêcher la NRVO

new est généralement utilisé pour allouer un bloc mémoire et – où il diffère de malloc(), – appelle le constructeur de la classe demandée (si constructeur il y a). Il fait donc deux choses en une.

Mais new fait une troisième chose: il lance une exception std::bad_alloc si l’espace mémoire est insuffisant.

Ou pas. Car new est un opérateur surchargeable qui prend des paramètres. Le standard définit dans l’en-tête <new> un type (std::nothrow_t) et une variable (std::nothrow) qui permettent de retourner un pointeur nul plutôt que lancer une exception.

Machin* machin = new (std::nothrow) Machin(/*params...*/);

Voici ce qui clôt l’utilisation courante et voyons comment faire chaque étape séparément.

Allouer de la mémoire

Comme on veut juste réserver un espace mémoire, malloc() peut suffire, mais prenons les bonnes habitudes, utilisons la fonction ::operator new() !

void* p = ::operator new(sizeof(Machin));

Ou la version sans exception.

void* p = ::operator new(sizeof(Machin), std::nothrow);

Maintenant qu’on a un joli espace mémoire tout fraîchement alloué, construisons l’objet.

Placement new

Le placement new permet d’appeler le constructeur d’un objet sur une zone mémoire prédéfinie.

Machin* machin = new (p) Machin(/*params…*/);
// machin == p (même zone mémoire)

Mais attention aux fuites mémoire si le constructeur de Machin lance une exception.

Et maintenant que c’est construit, on détruit :D

Destruction

Un appel explicite au destructeur et le tour est joué.

machin->~Machin();

Étape inutile pour les types scalaires. De toute façon ils n’ont pas de destructeur. En C++17, la STL contient std::destroy_at.

Évidemment, si machin possède un destructeur virtuel et est en réalité une classe fille, alors c’est le destructeur de la classe dérivée qui est appelé.

Il ne reste plus qu’à libérer la mémoire.

Libération de la mémoire

De la même manière qu’il faut utiliser delete/delete[] pour new/new[], il existe un ::operator delete() associé à ::operator new().

::operator delete (p);

Allocation de tableau

::operator new[] et ::operator delete[] fonctionnent de la même manière, mais sont plus sûrs qu’une gestion manuelle de tableau avec leurs homologues sans crochets. Ne serait-ce que pour détruire proprement les objets si un des constructeurs jette une exception.

void* p = ::operator new[](sizeof(Machin) * n); // identique que la version sans crochet
Machin* machin = new(p) Machin[n]/*{params...}*/;

Surcharge de new et delete

Toutes les formes de new et delete sont surchargeables de façon locale ou globale. Local quand l’opérateur est implémenté à l’intérieur d’une classe (son prototype sera implicitement statique) et global lorsqu’implémenté dans le namespace global.

De plus, comme new peut prendre des paramètres, il est possible de les personnaliser et d’en ajouter.

#include <new>
struct A
{
  A(int i=0)
  {
    std::cout << "A(" << i << ")" << std::endl;
  }

  void* operator new (std::size_t size, int x, int y) throw(std::bad_alloc)
  {
    std::cout << "new A " << x << ' ' << y << std::endl;
    return ::operator new (sizeof(A));
  }
};

new(1,2) A; // affiche "new A 1 2 A(0)"

L’alignement mémoire

L’alignement mémoire est une histoire à part entière, je n’en parle donc pas plus que ça :p.

Toutefois, renseignez-vous dessus, des variables non alignées peuvent faire chuter les performances et planter certaines architectures de processeur. Présent dans boost et la dernière norme du C++, il existe aligned_storage et co pour aider.

Allocateurs de la SL

Les allocateurs sont des objets qui s’occupent de faire tout ce qui a été dit auparavant à travers des fonctions comme allocate/desallocate, construct/destroy, etc, mais sans faire de surcharge. En fait, tous les conteneurs dynamiques de la STL utilisent un std::allocator comme allocateur par défaut paramétrable à travers le dernier type template du conteneur.

Depuis C++11, il existe std::allocator_traits qui simplifie grandement la création d’un allocateur en rendant la plupart des fonctions optionnelles. Et à partir de C++17 un allocateur polymorphique voit le jour avec quelques gestionnaires de mémoire.

Allocateurs et conteneurs

Utiliser un allocateur personnalisé permet d’avoir un contrôle plus fin de la mémoire pour répondre plus efficacement au besoin et augmenter les performances.

Évidemment, l’allocateur peut être personnalisable et dans certaines circonstances permet un gain de performance en évitant l’allocation/dés-allocation répété.

Par exemple, il y a quelques semaines, j’ai fait un algorithme qui faisait au total 2'100'000 new pour au final ne garder que 100'000 objets. Donc 2'000'000 de delete.

Dans le pire des cas, il y avait une suite de 25 objets à supprimer. Avec un allocateur qui ne vide pas la mémoire mais garde un tableau des pointeurs alloués je n’avais plus qu’à faire 25 dés-allocations au lieu de 2'000'000. Le nombre de new effectuées descendait quant à lui à 100'025.

Seul le nombre d’appels au destructeur et au placement new restait inchangé. Respectivement 2'000'000 et 2'100'000.

Au final l’algorithme était quand même 30% plus rapide. J’aurais aussi pu allouer directement tous mes objets et les réutiliser, mais là n’est pas le propos :).

Ce type d’optimisation reste toutefois exceptionnel et n’est pas adapté à tous les conteneurs. Par exemple, std::vector se prête mal à ce genre d’exercice car il demande toujours une allocation d’au moins la taille du nombre d’éléments qu’il possède.

Par contre, les conteneurs comme std::list ou std::map, qui allouent toujours un seul élément à la fois sont un meilleur choix pour utiliser ce type d’allocateur. Cependant, comme les conteneurs retournent une copie de leur allocateur, il sera difficile de supprimer de manière simple la mémoire non utilisée par l’allocateur du conteneur.

En ce moment, j’ajoute plusieurs allocateurs dans falcon/memory. Même si celui dont je viens de parler n’est pas encore présent car son implémentation était vraiment basique et spécifique, il fait quand même partie de ma todo-list.

Ne pas empêcher la NRVO

Article suivant: Placement new, allocateur et conteneur
Article précédent: Sqlite, reconstruire la bdd pour l'alléger

La NRVO et la RVO sont des optimisations des compilateurs pour retourner un objet sans le copier. Je renvoie directement sur la FAQ C++ developpez.com.

Cependant, ces optimisations ne s’appliquent que sur une variable de type T sans référence. Ce qui veut dire qu’une référence ne sera pas optimisée.

iterator operator+(const iterator& other, int n)
{
  return iterator(other) += n; // pas de RVO
}

Alors qu’une décomposition de la fonction active la NRVO.

iterator operator+(const iterator& other, int n)
{
  iterator ret(other);
  ret += n;
  return ret;
}

C’est une optimisation facile à faire et il est tout aussi facile de passer à côté ;).

Sqlite, reconstruire la bdd pour l'alléger

Article suivant: Ne pas empêcher la NRVO
Article précédent: Différence entre $@, $*, "$@" et "$*"

Il existe sur les bases de données SQLite une commande pour réduire la fragmentation des tables et optimiser l’espace disque. J’ai nommé: VACUUM.

Cette commande reconstruit la bdd pour éliminer les lignes vides et réorganise les index (plus de détails dans la doc en lien).

Comme certains logiciels se servent de sqlite comme BDD, il peut être intéressant d’utiliser cette commande de temps en temps. La première fois que je l’ai fait pour firefox (fichier ~/.mozilla/firefox/nom-du-profil/*.sqlite sur linux) j’ai gagné ½ giga :).

Voici un petit script qui va permettre de le faire sur tous les fichiers sqlite du système (du moins, ceux indexés) et connaître la taille totale avant et après utilisation:

#!/bin/sh
tmpf=${TMPDIR:=/tmp}/sqlite_file_path
locate \.sqlite \
| xargs -d'\n' mimetype \
| grep 'application/x-sqlite3$' \
| sed 's/:\s*application\/x-sqlite3\s*$//' \
> "$tmpf"
xargs --arg-file "$tmpf" -d'\n' du -hc | tail -n1
while read f ; do
  sqlite3 "$f" 'VACUUM;' || echo "\tfor $f"
done < "$tmpf"
xargs --arg-file "$tmpf" -d'\n' du -hc | tail -n1
rm "$tmpf"

Et une petite version qui prend des fichiers en paramètre:

#!/bin/sh
du -hc "$@"
for f in "$@" ; do
  sqlite3 "$f" 'VACUUM;'
done
du -hc "$@"

Différence entre $@, $*, "$@" et "$*"

Article suivant: Sqlite, reconstruire la bdd pour l'alléger
Article précédent: Délégation d'événement en js

Dans un script shell, il existe 2 variables pour accéder aux paramètres de la commande (aussi nommées argv dans pas mal d’autres langages): $* et $@.

  • $* est une variable ce qu’il y a de plus normale et ne diffère pas d’une autre variable. Cependant, le comportement des variables diffère en fonction du shell, notamment sur zsh (j’y reviens après).
  • $@ est une variable au comportement différent entre les shells.

Sur bash, il n’y a aucune différence entre $* et $@. Par contre, sur ksh et zsh, $@ représente un tableau d’arguments. Il faut savoir que sur bash, utiliser une variable sans guillemet revient à créer autant d’arguments qu’il y a de mots. Les mots sont séparés en fonction des caractères dans $IFS (la variable contient par défaut : espace, tabulation et saut de ligne). C’est pour cela qu’il est conseillé d’entourer ces variables de guillemets doubles.

Un petit exemple pour comprendre :).

a='a b c'
for v in $a ; do
  echo $v
done
> a
> b
> c

Le résultat est 3 lignes pour 1 paramètre, la chaîne 'a b c' contenant des espaces s’est fait couper. Ce n’est pas le cas pour zsh qui ne fait pas cette césure (raison historique, j’y reviens à la fin).

Maintenant il reste "$*" et "$@" qui ne diffèrent pas entre les shells.

  • "$*" correspond à une seule chaîne, tout est géré en un seul bloc.
  • "$@" représente les paramètres réels. C’est identique à $@ avec ksh et zsh.

Démonstration

# test.sh
for v in XXX ; do
  echo $v
done

Le code ci-dessus est utilisé avec ./test.s 'a b' c et pour lequel XXX est remplacé par une des 4 variables précédemment citées.

XXX bash ksh zsh
$* a
b
c
a
b
c
a b
c
$@ a
b
c
a b
c
a b
c
"$*" a b c a b c a b c
"$@" a b
c
a b
c
a b
c

Pour que zsh boucle sur des mots, il faut ajouter un flag à la variable (${=*} ou $=*), comme ci-dessous.

a='a b c';
for v in ${=a} ; do
  echo $v
done

Délégation d'événement en js

Article suivant: Différence entre $@, $*, "$@" et "$*"
Article précédent: La vis cachée de getopt

En règle générale les événements sont attachés à l’élément qui va le traiter.

Par exemple en javascript, un menu (ul) contenant 10 entrées (li) où chaque entrée est associée à une action crée, au total, 10 événements. 10 événements attachés à la même action.

Pour dire vrai, cette méthode est peu performante et peut la plupart du temps être remplacée par un seul événement sur le parent. À ce moment le parent vérifie si l’événement est généré par un de ses fils et fait le traitement en conséquence.

var ul = document.getElementById("menu");
ul.onclick = function(e){
  if (e.target.parentNode === ul) // est-ce toi mon fils ?
    openWithAjax(e)
}

On peut trouver le même type de fonction dans JQuery: .on().

La vis cachée de getopt

Article suivant: Délégation d'événement en js
Article précédent: Taguer vos classes, cataloguées-les

Voici une petite information très mal connue et peu utilisée du getopt de la lib C et de la commande shell. Ainsi que Boost.Program_options. Parce que boost c’est bien :p.

Les noms des options longues n’ont pas besoin d’être écrites entièrement.

function parsecmd()
{
  getopt -o '' --long \
    option-longue,option-encore-plus-longue,une-autre-option: \
    -n 'example' -- "$@"
}

parsecmd --option-l --u plop bidule

Donne

--option-longue --une-autre-option 'plop' -- 'bidule'

La commande shell getopt est un peu plus souple que les autres. Si ambiguïté, la première option correspondante sera sélectionnée. Si l’option -a existe ce n’est plus le cas et le code d’erreur 1 est retourné ainsi qu’un petit message listant les options possibles. Mais avec -a les options longues peuvent commencer par un simple tiret.

La plupart des commandes Linux utilisant getopt, cette astuce peut s’utiliser assez souvent.

Taguer vos classes, cataloguées-les

Article suivant: La vis cachée de getopt
Article précédent: Zsh et le danger des modificateurs

Le C++ a l’avantage de faire de la surcharge de fonction et permet ainsi de spécifier des algorithmes selon des critères. Ici ce seront des “tags”.

Comme exemple je vais utiliser les tags présents dans les itérateurs de la STL et une implémentation de la fonction std::advance().

Première implémentation

La fonction std::advance() permet d’incrémenter un itérateur de N éléments (ou décrémenter si N est négatif). D’après cette description, un premier algorithme peut être émis:

template<class InputIt, class Distance>
void advance(InputIt& it, Distance n)
{
  if (n < 0){
    while (n++)
      --it;
  }
  else {
    while (n--)
      ++it;
  }
}

Optimisation

Maintenant, que se passe-t-il quand l’itérateur est un pointeur ? Réponse: une boucle.

Ne serait-il pas préférable de faire it += n !?

C’est là que les tags entrent en jeu.

Utilisation des tags

Les itérateurs possèdent des types prédéfinis qui sont: pointer, value_type, reference, difference_type et iterator_category. C’est ce dernier qui correspond au tag de l’itérateur.

En réalité un tag est une classe vide. Cela suffit, le type est porteur de l’information. Les tags des itérateurs possèdent aussi une hiérarchie et certains sont donc hérités.

Pour récupérer le type contenu dans un itérateur il faut passer par std::iterator_traits<>, cela permet de fonctionner même avec un type scalaire comme le pointeur qui ne possède pas de type interne.

Le tag d’un pointeur étant std::random_access_iterator_tag voici une implémentation:

template<class It>
std::iterator_traits<It>::iterator_category
iterator_category(const It&)
{
  return typename std::iterator_traits<It>::iterator_category();
}

template<class RandomIt, class Distance>
void advance(RandomIt& it, Distance n, std::random_access_iterator_tag)
{
  it += n;
}

template<class InputIt, class Distance>
void advance(InputIt& it, Distance n)
{
  advance(it, n, iterator_category(it));
}

Bien sûr, on change aussi le prototype de la précédente implémentation.

template<class InputIt, class Distance, class Tag>
void advance(InputIt& it, Distance n, Tag);

Problème avec ForwardIterator

Toutefois un problème persiste, lorsqu’un ForwardIterator est utilisé, il n’y a pas d’opération de décrémentation, et la compilation ne se fait pas. Il faut de nouveau changer notre première implémentation pour qu’elle ne fonctionne qu’avec bidirectional_iterator_tag et une implémentation généraliste qui fait une incrémentation.

template<class InputIt, class Distance, class Tag>
void advance(InputIt& it, Distance n, Tag)
{
  while (n--)
    ++it;
}

template<class InputIt, class Distance>
void advance(InputIt& it, Distance n, std::bidirectional_iterator_tag)
{
  if (n < 0){
    while (n++)
      --it;
  }
  else {
    while (n--)
      ++it;
  }
}

Conclusion

Les tags sont un moyen simple de spécifier les comportements liés à une classe. On peut les voir comme une liste d’interface disponible pour cibler précisément ce qu’il est possible de faire ou ne pas faire.

Zsh et le danger des modificateurs

Article suivant: Taguer vos classes, cataloguées-les
Article précédent: La récursivité et le mauvais exemple de Fibonacci

Zsh est très bien comme shell, mais fait plus de choses que bash ce qui peut engendrer des bugs quand celui-ci est le shell par défaut et que des scripts ne définissent pas l’interpréteur utilisé. J’ai eu le coup une fois lorsqu’il fallait charger le module canberra-gtk pour les programmes java.

Une variable $GTK_MODULES est définie et contient tous les modules gtk séparés par des deux points (:). Visiblement, j’ai 2 modules gtk. Tous 2 servant à ajouter canberra-gtk-module. Les fautifs ? 52libcanberra-gtk-module_add-to-gtk-modules et 52libcanberra-gtk3-module_add-to-gtk-modules Avec un contenu identique:

if [ -z "$GTK_MODULES" ] ; then
    GTK_MODULES="canberra-gtk-module"
else
    GTK_MODULES="$GTK_MODULES:canberra-gtk-module"
fi

export GTK_MODULES

Et là, paf ! C’est le drame. $GTK_MODULES = canberra-gtk-moduleanberra-gtk-module, naturellement :D.

Vous venez d’assister à l’effet du modificateur c (dans :c) qui ajoute le chemin de l’executable présent dans $GTK_MODULES. Comme canberra-gtk-module n’est pas un executable, rien n’est fait, mais :c disparaît. Avec l’auto-complétion on peut voir qu’il y en a une petite quinzaine de disponibles, de quoi tomber plusieurs fois dans le piège.

Les modificateurs existent aussi dans bash, mais ils sont moins nombreux et ne s’utilisent qu’avec l’historique (paragraphe HISTORY EXPANSION du manuel).

echo unfichier.txt
echo !:1:r

Résultat :

unfichier.txt
unfichier

Quasiment jamais utilisé en fait.

Mais voilà, zsh les généralise aussi aux variables ce qui engendre une erreur dans GTK_MODULES.

Alors comment faire ? Simple, entourer la variable d’accolades:

GTK_MODULES="${GTK_MODULES}:canberra-gtk-module"

La récursivité et le mauvais exemple de Fibonacci

Article suivant: Zsh et le danger des modificateurs
Article précédent: Sed tout puissant

Quasiment toute personne ayant suivi un cours sur la récursivité a eu un exercice de la forme:

Coder la suite de Fibonacci en récursive et en itérative.

Mais partout où j’ai vu une implémentation récursive, je suis tombé sur un algorithme inefficace. Voici ce qu’on peut trouver.

//itérative
long long fib(unsigned n)
{
  if (n == 0)
    return n;
  long long a = 0, b = 1, tmp;
  while (--n)
  {
    tmp = a + b;
    a = b;
    b = tmp;
  }
  return b;
}

// récursive
long long fib_r(unsigned n)
{
  if (0 == n || 1 == n)
    return n;
  return fib_r(n-1) + fib_r(n-2);
}

Sauf que cet algorithme récursif est pourri. Il recalcule sans cesse fib-1 et fib-2 et fait monter la pile d’appel jusqu’à explosion là où l’algorithme itératif additionne une variable.

Pour avoir un algorithme récursif équivalent à celui itératif, il faut garder le même comportement. C’est à dire garder a et b.

long long fib_r_impl(unsigned n, long long r, long long rp)
{
  if (0 == n)
    return r;
  return fib_r_impl(n-1, r+rp, r);
}

long long fib_r(unsigned n)
{
  return fib_r_impl(n, 0, 1);
}

Cet algo est strictement identique au premier car applique la récursion terminale. Ainsi, le code généré par un compilateur (avec les options d’optimisation) donnera un binaire identique (ou très proche). Des langages comme OCaml ou Haskel optimisent la pile quand il y a une récursion terminale.

Sed tout puissant

Article suivant: La récursivité et le mauvais exemple de Fibonacci
Article précédent: Rendre accessible le chargement de lien avec AJAX

Il y a 3 semaines environ je cherchais le moyen d’utiliser la commande sed avec une regex sur plusieurs lignes. Je voulais transformer tous les /\+\n\s+""/ en rien du tout (oui, les supprimer…). Sauf que comme tel, ça ne fonctionne pas, sed comme beaucoup de commandes unix fonctionne par ligne. Après de lourdes et pompeuses recherches d’au moins 7 secondes montre en main, je suis tombé sur la solution.

Pour ce faire, il suffit d’un identifiant, un petit label, une information de multi-ligne au milieu et 3 autres bricoles ; rien que ça :D.

Ce qui se traduit par:

sed -e :a -e N -e '$!ba' -e s'/+\n\s\+""//g'

Et en version courte:

sed ':a;N;$!ba;s/+\n\s\+""//g'

Je sais ce que vous vous demandez: pourquoi il n’y a pas -e dans la version courte ?

Mais parce que c’est la version courte, évidemment !

Sinon dans une moindre mesure.

  • :a: pour créer un identifiant nommé “a”, mais il peut très bien se nommer bidule.
  • N: pour lire la ligne suivante et l’ajouter dans l’espace de recherche.
  • $!ba: Si on n’est pas (!) sur la dernière ligne ($), sauter au label (b) nommé “a”. C’est une boucle.

L’espace de recherche est la partie sur laquelle s’applique une regex. Par défaut, l’espace de recherche ne contient qu’une ligne à la fois qui sont manipulées individuellement. Avec cette boucle, l’espace de recherche contient toutes les lignes (avec saut de ligne) et la regex est appliquée sur l’ensemble du document.

Et en bonus, quelques commandes supplémentaires bons à savoir.

  • sed 2,5s/e/U/g remplace e par U à partir de la ligne 2 jusqu’à la 5.
  • sed "/$debut/,/$fin/"s/A/a/g depuis $debut jusqu’à $fin.
  • sed "/$debut/,+5"s/A/a/g depuis $debut et sur 5 lignes.
Revenir en haut