Prise en charge de l'allocation dynamique – Aréna aux paramètres fixes

Notez que les équations dans ce document sont affichées à l'aide de MathJax.

Il est présumé au préalable que vous êtes familière ou familier avec le schéma de conception singleton et l'idiome de programmation incopiable, de même qu'avec la programmation générique et l'idiome RAII.

Il peut arriver que, dans des applications spécialisées, on connaisse a priori la taille des blocs de mémoire à allouer et le nombre maximal de blocs à allouer pour un type donné.

Un cas possible serait celui d'un jeu vidéo où une guerre épouvantable entre deux tribus d'orques surviendrait en cours de route. Si les paramètres (sizeof(Orque) et nombre maximal d'orques défini par le scénario) sont connus, il est possible de faire aussi bien que les mécanismes standard de gestion de la mémoire allouée dynamiquement avec des algorithmes naïfs (par exemple avec les techniques proposées ici), ce qui implique qu'on pourrait faire mieux en travaillant un peu plus fort (ce que je vous laisse faire par vous-mêmes).

Dans ce document, quand j'écris sur new et delete, vous pouvez généralement supposer que je parle aussi de new[] et delete[].

S'il s'avère nécessaire de contrôler la mécanique d'allocation dynamique de mémoire pour un type X donné, alors on voudra définir les opérateurs new et delete sur ce type.

L'opérateur new sera invoqué pour déléguer à l'objet la tâche de se réserver lui-même un bloc de mémoire, donc avant l'appel du constructeur. L'opérateur delete sera quant à lui invoqué pour procéder à la libération du bloc de mémoire dans lequel réside l'objet, donc après le destructeur.

Clairement, dans les deux cas, il serait malsain d'utiliser un membre d'instance pour mettre en place la mécanique d'attribution dynamique de la mémoire, car ces membres n'existent alors pas encore. Il est légal en C++ de ne définir que l'opérateur new ou que l'opérateur delete sur un objet, par exemple pour insérer le code requis pour faire une trace de ces opérations.

Habituellement, toutefois, on voudra implémenter ces opérateurs par paire (souvent même par quartet, du fait qu'il soit probable qu'on veuille appliquer aux tableaux une stratégie semblable à celle appliquée aux scalaires).

En effet, s'il est décidé d'appliquer une stratégie spéciale d'allocation dynamique de mémoire pour un type donné, alors il est peu probable qu'on souhaite laisser la mécanique normale de C++ se charger de l'opération correspondante de libération dynamique de mémoire-ce serait presque nécessairement voué à l'échec.

Quatre opérateurs peuvent donc être surchargés pour une classe donnée dans l'optique de contrôler la mécanique d'attribution dynamique de la mémoire.

Les signatures de ces opérateurs sont telles qu'exposées à droite.

Les opérateurs new et new[] prennent en paramètre la taille du bloc à réserver. Leur rôle est donc d'obtenir une zone mémoire convenable à un X ou à une séquence de X pour que cette zone soit initialisée par des constructeurs qui ne sont connus que du moteur de C++ et de retourner un pointeur abstrait, donc un void*, vers le début de cette zone.

Les opérateurs new et new[] ne savent (sauf rares exceptions) pas lequel des constructeurs de X a été invoqué.

Les opérateurs delete et delete[] prennent quant à eux un pointeur abstrait (qu'on présume vers un X et préalablement attribué à l'aide de la méthode new() ou new[] de X) et libèrent la mémoire correspondante.

class X {
   // ...
public:
   // ...
   void* operator new(size_t);
   void operator delete(void *p);
   void* operator new[](size_t);
   void operator delete[](void *p);
   // ...
};

Exemple – Une armée d'orques

Imaginons que nous oeuvrions à un jeu vidéo de type médiéval fantastique et que nous sachions d'avance que nous aurons à gérer, fréquemment, des armées d'orques (aussi nommées des hordes). Imaginons aussi que nous pensions être capables de profiter du fait que la taille d'un Orque est connue à la compilation (après tout, tout Orque occupe sizeof(Orque) bytes en mémoire!).

Nous mettrons ici en place un programme de test qui crée plusieurs instances de la classe Orque, les utilise (de manière fictive) puis les détruit à la pièce. Nous utiliserons aussi une allocation en bloc d'un tableau d'instances d'Orque (des renforts pour ceux déjà créés!) pour vérifier la qualité de l'implémentation de l'opérateur new[].

En contrepartie, nous utiliserons l'opérateur delete[] pour nettoyer les renforts, puis nous appellerons massivement l'opérateur delete pour éliminer les instances de Orque créées à la pièce en début de programme.

Une fois des mesures faites pour les versions standard des opérateurs new, new[], delete et delete[], nous implémenterons notre propre petit mécanisme maison pour gérer la mémoire allouée dynamiquement et nous mesurerons le programme résultant. Ceci nous permettra de voir l'impact de nos choix d'implémentation.

Mesurer la vitesse d'exécution des mécanismes de gestion de la mémoire

Pour mesurer la vitesse des mécanismes de gestion de la mémoire allouée dynamiquement dans leurs déclinaisons par défaut et maison, nous passerons par une fonction tester() comme celle décrite dans cet article. Par exemple, nous mesurerons le temps d'exécution d'une fonction f() quelconque comme suit.

// ...
template <class F, class ... Args>
   auto tester(F f, Args &&... args) {
      auto pre = high_resolution_clock::now();
      auto res = f(std::forwars<Args>(args)...);
      auto post = high_resolution_clock::now();
      return make_pair(res, post - pre);
   }
int main() {
   auto res = tester([] {
      f();
   });
   // afficher le temps écoulé, logé dans res
   // ...
}

La variable res est alors une std::pair contenant le résultat du calcul réalisé par f() et le temps écoulé pendant son exécution. Ce temps écoulé sera typiquement converti pas un duration_cast dans l'unité de mesure souhaitée par le code client.

Décrire un Orque

Décrire un Orque est une chose simple en soi. Nous pourrions insérer un nom (une std::string), des points de vie et quelques attributs décoratifs et nous en tenir là.

Par principe, je vous proposerai ici une classe Orque légèrement plus complète et plus sérieuse, mais notez tout de suite que, pour nos fins, une version naïve aurait suffi-après tout, nous sommes intéressé(e)s par les mécanismes d'allocation dynamique de mémoire, pas par la représentation correcte d'une créature hideuse et agressive.

Tout Orque sera Frappable. Nous entendrons par là que chaque Orque sera voué à une existence violente et sera une créature de conflits, sujette à blesser et à être blessée.

Dans la plupart des sagas médiévales fantastiques, un Orque est la créature vilaine standard et tend à faire preuve d'une personnalité que je qualifierais de belliqueuse.

Pour faciliter les conflits, nous dirons ici que les créatures sujettes à se battre seront des instances de classes dérivées de Frappable.

La classe Frappable inclura les règles de gestion des points de vie, de guérison et de blessure.

#include <cassert>
#include <random>
mt19937& rand_();
/* Dans un .cpp :
mt19937& rand_() {
   using namespace std;
   static random_device rd;
   static mt19937 prng { rd() }; // not thread safe once constructed
   return prng;
}
*/
class Frappable {
public:
   using vie_t = short;
private:
   vie_t vie_;
public:
   static vie_t generer_points_vie() {
      std::uniform_int_distribution<int> de{5,20}; // vie min,max
      return de(rand_());
   }
public:
   Frappable(vie_t vie = generer_points_vie()) : vie_{vie} {
   }
   vie_t vie() const noexcept {
      return vie_;
   }
   bool est_decede() const noexcept {
      return vie() <= 0;
   }
   void endommager(vie_t degats) noexcept {
      assert(degats > 0);
      vie_ -= degats;
   }
   void guerir(vie_t soins) noexcept {
      assert(soins > 0);
      vie_ += soins;
   }
   virtual void frapper(Frappable&) = 0;
   virtual ~Frappable() = default;
};

Les diverses instances de la classe Orque auront un certain seuil de méchanceté. Ce seuil influencera les dégâts faits au Frappable avec lequel un Orque est en conflit lorsque l'instance de Orque en question lui portera un coup.

Considérant que chaque Orque est nommé (à l'aide d'un attribut de type std::string), on peut dire que sizeof(Orque) sera au moins aussi grand que

sizeof(Frappable) +
   sizeof(short) +
      sizeof(std::string)
class Orque : public Frappable {
   enum {
      MECHANCETE_DEFAUT = 5
   };
   std::string nom_;
   short mechancete_;
   vie_t generer_degats() const noexcept {
      std::uniform_int_distribution<int> de{0,mechancete_};
      return de(rand_());
   }
public:
   Orque(const std::string &nom = "Euh...") : nom_{ nom }, mechancete_{ MECHANCETE_DEFAUT } {
   }
   void frapper(Frappable &f) override {
      f.endommager(generer_degats());
   }
};

Ceci nous donne une classe Orque qui a au moins un minimum d'intérêt et dont chaque instance, en pratique, occupe probablement entre 30 et 40 bytes en mémoire, selon la plateforme et le compilateur.

Il nous faut maintenant un programme de test pour vérifier la vitesse à laquelle s'exécuteront les opérateurs d'allocation et de libération dynamique de mémoire dans leur déclinaison standard comme dans leur déclinaison maison.

Parmi les bibliothèques auxquelles nous aurons recours, remarquez la bibliothèque <list>.

Sans que ce soit strictement nécessaire avec le programme de test qui sera proposé ici, une masse d'orques en situation de conflit risquerait de générer des décès inopinés ici et là et des suppressions ailleurs qu'à la fin d'un conteneur sont beaucoup plus rapides sur une std::list que sur un std::vector.

#include "MesureDeTemps.h"
#include "Orque.h"
#include <iostream>
#include <list>
#include <string>
#include <algorithm>

Nous mettrons en scène une bande de N instances de Orque, réparties de manière aléatoire entre deux hordes (une néfaste et l'autre horrible).

int main() {
   using namespace std;
   uniform_int_distribution<int> de{ 0,1 };
   auto p = new Orque{ "Urg" };
   delete p;
   enum {  N = 100'000 };
   list<Orque *> HordeNefaste;
   list<Orque *> HordeHorrible;

La création des hordes exploite massivement new : elle crée chaque Orque et le positionne dans l'une ou l'autre des hordes avec une probabilité de .

Les membres de la horde néfaste se nomment Urg suivi d'un numéro de série alors que les membres de la horde horrible se nomment Arg suivi d'un numéro de série. Que voulez-vous : les orques sont comme ça.

   auto r0 = tester([&]{
      for (int i = 0; i < N; ++i)
         if (de(rand_()))
            HordeNefaste.push_back(
               new Orque{ "Urg " + to_string(i) }
            );
         else
            HordeHorrible.push_back(
               new Orque{ "Arg " + to_string(i) }
            );
   });
   // ... affichage du temps écoulé...

Un combat s'ensuit. J'ai censuré ce tronçon pour les âmes sensibles, mais sachez qu'aucun Orque ne sera retiré de son conteneur pendant le combat (pour éviter de fausser les données lorsque nous mesurerons la performance de delete).

Arrivent soudainement des renforts potentiels (non alignés). Ceci nous permet de tester et de mesurer les performandes de notre opérateur new[].

   Orque *pMoton = {};
   auto r1 = tester([&] {
      pMoton = new Orque[1000];
      // ...
   });
   // ... affichage du temps écoulé...

Un malheur survient et les renforts potentiels décèdent subitement d'un mal inconnu. N'écoutant que notre courage, nous en profitons pour tester et mesurer le comportement de notre opérateur delete[]).

   auto r2 = tester([&] {
      delete[] pMoton;
      // ...
   });
   // ... affichage du temps écoulé...

Vient enfin l'étape du nettoyage du champ de bataille, qui exploite massivement delete et nous permet de mesurer la vitesse d'exécution de cet opérateur.

// ...
   auto r3 = tester([&] {
      for(auto p : HordeHorrible) delete p;
      for(auto p : HordeNefaste) delete p;
   });
   // ... affichage du temps écoulé...
}

Tester le programme dans sa version actuelle permettra de connaître la vitesse d'exécution des quatre opérateurs standards de gestion de la mémoire allouée dynamiquement. Armés du résultat de ces tests, nous pourrons voir si nos propres opérateurs se comportent à la hauteur des attentes.

Implémenter les méthodes new, new[], delete et delete[] pour Orque

Nous allons maintenant implémenter des versions naïves (j'insiste!) des opérateurs de gestion de la mémoire allouée dynamiquement pour la classe Orque.

Étonnamment, nous obtiendrons des performances très similaires à celles obtenues par les opérateurs standard, ce qui suggère que nous pourrions faire beaucoup mieux si nous y investissions un peu plus d'énergie.

Exposer les méthodes new, new[], delete et delete[] sous forme de méthodes d'instance dans une classe donnée est chose banale, comme le montre l'exemple à droite.

Les signatures sont en effet les mêmes que dans le cas des versions globales de ces opérateurs. Cependant, la classe Orque a, dans son implémentation des méthodes en question, l'avantage de connaître la taille de ce qui sera alloué : présumant qu'on manipulera des instances de Orque, pas des instances de classes dérivées de Orque, la taille des blocs à allouer est connue a priori sera un multiple de sizeof(Orque).

En pratique, il vaudrait mieux éviter de dépendre de cette considération puisque les enfants de Orque hériteront de ses méthodes new/new[] et delete/delete[]. Il est clair que ces enfants ne seront pas nécessairement de taille sizeof(Orque).

#ifndef ORQUE_H
#define ORQUE_H
#include <string>
#include <vector>
#include <algorithm>
#include <cassert>
template <class T>
   class Tribu {
      std::string nom_;
      std::vector<T *> membres_;
   public:
      void enregistrer(T *p) {
         assert(p);
         membres_.push_back(p);
      }
      void desenregistrer(T *) {
      }
      Tribu(const std::string &nom) : nom_{nom} {
      }
   };
#include <cstdlib>
//
// class Frappable (omise; voir plus haut)
//
class Orque : public Frappable {
   //
   // seul ce qui a changé apparaît ici; voir
   // plus haut pour le reste
   //
   static Tribu<Orque> tribu;
public:
   Orque(const std::string &nom = "Euh...") : nom_{nom}, mechancete_{MECHANCETE_DEFAUT} {
      tribu.enregistrer(this);
   }
   ~Orque() {
      tribu.desenregistrer(this);
   }
   // ...
   void* operator new(size_t);
   void* operator new[](size_t);
   void operator delete(void *);
   void operator delete[](void *);
};

#endif

En pratique, il souvent est plus sage de spécialiser ces opérateurs en fonction d'un patron d'utilisation qu'en fonction de blocs de taille fixe. Cela dit, pour nos fins, travailler en fonction de blocs de taille sizeof(Orque) sera instructif.

L'implémentation de ces méthodes sera, elle aussi, relativement simple. Cette simplicité cache toutefois un effort de programmation un peu plus grand.

Tout d'abord, remarquons que toutes les stratégies d'allocation de mémoire reposant sur des blocs de taille fixe ont la particularité de reposer sur une mémoire à répartir dont la taille sera un multiple de la taille d'un seul bloc.

Nous utiliserons donc une classe générique spécialisée en ce sens, que nous nommerons ArenaFixe, et nous ferons en sorte que la classe Orque pige sa mémoire dans une ArenaOrque, un singleton spécialisant ArenaFixe pour des blocs de taille sizeof(Orque).

Les méthodes d'instance de la classe Orque pour allouer et libérer de la mémoire délégueront ces tâches au singleton ArenaOrque.

Les méthodes de ArenaOrque pour allouer un ou plusieurs orques se nommeront allouer_un() et allouer_n(), respectivement, alors que les méthodes pour libérer la mémoire pour un ou plusieurs orques se nommeront respectivement liberer_un() et liberer_n().

#include "Orque.h"
#include "ArenaFixe.h"
#include "Incopiable.h"

Tribu<Orque> Orque::tribu("Les garnements");
namespace {
   enum { POPULATION_MAX = 200'000 };
}
class ArenaOrque : public ArenaFixe<sizeof(Orque), ::POPULATION_MAX>, Incopiable {
   ArenaOrque() = default;
public:
   static ArenaOrque &get() {
      static ArenaOrque singleton;
      return singleton;
   }
};
void* Orque::operator new(size_t qte) {
   return ArenaOrque::get().allouer_un();
}
void* Orque::operator new[](size_t qte) {
   return ArenaOrque::get().allouer_n(qte / sizeof(Orque));
}
void Orque::operator delete(void *p) {
   ArenaOrque::get().liberer_un(p);
}
void Orque::operator delete[](void *p) {
   ArenaOrque::get().liberer_n(p);
}

La grande (et un peu plus complexe) question est donc : comment pourrait-on implémenter ArenaFixe? Une réponse simpliste mais opérationnelle suit.

Implémenter ArenaFixe – une approche possible

Nous mettrons en place une classe générique ArenaFixe basée sur deux paramètres :

Cette stratégie est naïve pour plusieurs raisons, mais en partie du fait que nous ne mettrons aucun mécanisme en place pour réagir si la population réelle dépasse les prévisions du code client. Notre ArenaFixe manquera simplement de mémoire et lèvera un std::bad_alloc si cela se produit.

Dans une instance de la classe ArenaFixe proposée ici, on trouvera un bassin de mémoire disponible (bêtement : un bloc d'octets dont la taille est le produit de la population par la taille d'un individu). Nos blocs ne seront donc pas nécessairement alignés sur la taille d'un mot mémoire, ce qui peut ralentir l'utilisation que le code client fera d'eux.

Pour simplifier la recherche de blocs alloués, nous utiliserons une séquence de bits (un std::bitset) qui contiendra, de manière compacte, un bit par individu. Nous considérerons qu'un bit à zéro signifie que le bloc correspondant dans le bassin est libre.

Une stratégie qui chercherait à partir du plus récent bloc libéré serait probablement encore plus efficace (complexité pour allouer un seul bloc).

Pour accélérer l'allocation de blocs en moyenne, nous conserverons la position du dernier bloc alloué dans un attribut (nommé plus_recent). Cette stratégie n'est pas sans faille (loin de là!) mais tend à accélérer l'allocation de mémoire en comparaison avec une stratégie qui chercherait toujours des blocs libres à partir du tout premier bloc du bassin.

La recherche d'un bloc libre se fera de manière cyclique à partir du plus récent bloc alloué. L'opération prochain() facilitera le passage d'un bloc à l'autre.

Du point de vue des inclusions, des attributs et des types internes et publics, donc, le portrait de cette stratégie simpliste ressemblerait à ce qui est proposé à droite.

Le raison du recours à une ArenaFixe générique est (en partie) de permettre de déclarer un bassin de mémoire sans avoir recours à de l'allocation dynamique de mémoire. Si la taille du bassin est grande, cette stratégie devient moins sage et, que ArenaFixe soit générique ou non, il devient alors avantageux d'allouer le bassin dynamiquement.

L'attribut tailles sert à retenir la taille des tableaux, au besoin, dans le but de simplifier la libération de gros blocs.

Il y a un problème de fond associé à la signature du template ArenaFixe à droite, le voyez-vous?

#ifndef ARENA_FIXE_H
#define ARENA_FIXE_H
#include <bitset>
#include <new>
template <size_t TailleBloc, size_t NBlocs> // discutable
   class ArenaFixe {
      static constexpr size_t TAILLE_BLOC = TailleBloc;
      static constexpr size_t NBLOCS = NBlocs;
      char bassin[TAILLE_BLOC * NBLOCS]; // discutable
      std::bitset<NBLOCS> pris;
      size_t tailles[NBLOCS]; // discutable
   public:
      using position_t = size_t;
   private:
      position_t plus_recent;

Un std::bitset représente de manière compacte un nombre de bits fixé à la déclaration. Ici, le nombre de bits à représenter correspond, tel qu'annoncé, au nombre de blocs dans le bassin de mémoire disponible.

La méthode prochain() retourne la prochaine position dans le bassin à partir d'un compteur. C'est une fonction utilitaire privée dont le principal rôle est d'alléger le code.

      static position_t prochain(position_t n) {
         return (n + 1) % NBLOCS;
      }

La méthode privée nommée compter_disponibles() compte le nombre de blocs libres à partir de base jusqu'à concurrence de max_pas blocs. Elle sert à trouver l'espace contigu nécessaire à l'allocation d'un tableau de max_pas blocs.

Elle retourne le nombre de blocs consécutifs disponibles dans le but d'accélérer la recherche (le code appelant sait qu'il peut escamoter ce nombre de blocs sans risque).

      size_t compter_disponibles(position_t base, position_t max_pas) {
         using std::bad_alloc;
         if (base + max_pas >= NB_BLOCS) throw bad_alloc{};
         auto cpt_pas = max_pas;
         while (!pris.test(base) && cpt_pas) {
            base = prochain(base);
            --cpt_pas;
         }
         return max_pas - cpt_pas;
      }

Remarquez le caractère potentiellement naïf de cette stratégie : si la recherche commence avec une base trop haute, il est possible que compter_disponibles() approche de la fin du bassin et lève un std::bad_alloc alors que le début du bassin contient peut-être assez de blocs disponibles pour servir une requête d'allocation.

Le throw ici est probablement trop hâtif; je doute qu'un try ... catch dans la méthode appelante soit acceptable étant donné le caractère fondamental et critique d'un mécanisme d'allocation de mémoire.

La méthode publique allouer_un() cherche et retourne un bloc de mémoire brute dans le bassin.

Tel que mentionné plus haut, la recherche de blocs disponibles commence juste après le plus récent bloc alloué et navigue à travers le bassin de manière circulaire jusqu'à ce qu'un bloc soit trouvé, levant un std::bad_alloc le cas échéant.

   public:
      void* allouer_un() {
         using std::bad_alloc;
         position_t i = prochain(plus_recent);
         while (pris.test(i) && i != plus_recent)
            i = prochain(i);
         if (i == plus_recent) throw bad_alloc{};
         pris.set(i);
         plus_recent = i;
         return bassin + i * TAILLE_BLOC;
      }

Le std::bitset permet de vérifier si un bloc est pris (méthode test()) et d'indiquer qu'un bloc a été pris (méthode set()).

La méthode allouer_n() alloue un séquence de n blocs consécutifs en mémoire dans le bassin (ce qui doit exclure une séquence circulaire qui commencerait à la fin du bassin et se terminerait au début).

Le recours à la méthode compter_disponibles() permet à la fois une recherche de blocs consécutifs et une progression rapide quand le nombre de blocs trouvé est insuffisant.

Notez que la boucle cherchant une séquence de blocs disponibles pourrait être raffinée (elle cherche toujours à partir du début) mais ce raffinement est plus subtil à implémenter qu'il n'y paraît.

// ...
      void* allouer_n(size_t n) {
         position_t i = 0;
         size_t nb_dispo = compter_disponibles(i, n);
         while (nb_dispo < n) {
            i += nb_dispo + 1;
            nb_dispo = compter_disponibles(i, n);
         }
         for (auto j = i, cpt = 0; cpt < n; j = prochain(j), ++cpt)
            pris.set(j);
         tailles[i] = n;
         plus_recent = i;
         return bassin + i * TAILLE_BLOC;
      }

L'une des difficultés de l'implémentation de stratégies d'allocation dynamique de mémoire est qu'elles doivent être à la fois sans failles et très efficaces. Un raffinement à la stratégie ci-dessus qui ralentirait un peu la recherche de blocs pourrait avoir un effet catastrophique sur la performance d'ensemble d'un programme.

Libérer un bloc est une chose relativement simple. À partir de l'adresse à libérer, on n'a qu'à retrouver l'indice du bloc dans le bassin et à modifier le bit indiquant si ce bloc est pris ou non.

      void liberer_un(const void *p) {
         position_t lequel = deduire_position(p);
         pris.set(lequel, false);
      }

La méthode deduire_position() est banale, se résumant à de l'artihmétique de pointeurs et à une division (du fait que la position s'exprime en termes de nombre de blocs, comme me l'a gentiment rappelé Jérôme Rampon).

      position_t deduire_position(const void *p) const {
         return static_cast<position_t>(
            static_cast<const char*>(p) - bassin
         ) / TAILLE_BLOC;
      }

Libérer une séquence de blocs implique de retrouver le bloc du début, le nombre de blocs à libérer et à modifier les différents bits indiquant si ces blocs sont pris ou non.

Remarquez que std::bitset n'est pas un conteneur standard et n'offre pas d'itérateurs.

      void liberer_n(const void *p) {
         auto lequel = deduire_position(p);
         const auto FIN = lequel + tailles[lequel];
         for (auto j = lequel; j < FIN; ++j)
            pris.set(j, false);
      }

Enfin, le constructeur et le destructeur sont des plus banals. Cependant, notez que cette implémentation fait le choix discutable d'allouer automatiquement certains attributs potentiellement lourds sur le plan de la consommation de ressources; en pratique, la banalité du constructeur par défaut et du destructeur pourraient mériter un nouveau regard.

// ...
      ArenaFixe() : plus_recent{} {
      }
   };
#endif

Valid XHTML 1.0 Transitional

CSS Valide !