Performance des UUIDs

(English version)

Dernièrement, en analysant les performances d'une application au moyen de l'excellent outil blackfire, nous avons constaté un temps non-négligeable passé à transformer des UUIDs binaires en chaînes et vice-versa.

Il faut dire que le stockage des UUIDs dans la base de données est au format binaire, et l'application disposant d'une API Rest, les UUIDS sont donc tout le temps convertis en chaîne de caractères sous la forme "xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxx", que ce soit pour retourner la réponse en JSON ou pour traiter des requêtes avec des UUIDs.

Comme beaucoup, les développeurs de l'application se sont tournés vers le paquet "Ramsey/UUID", qui semble être la solution majoritairement exploitée dans le cadre de la manipulation d'UUIDs. L'excellente réputation de ce composant, nous a conduit à chercher des solutions d'optimisation dans l'application, sans remettre en doute la pertinence de Ramsey/UUID.

Récemment, à la lecture de l'article de Jolicode "UUID generation in PHP" et du débat autour d'une pull request sur Symfony UID, nous nous sommes penchés un peu plus sur la façon dont l'application manipule les UUIDs, car comme le dit Grégoire Pineau, si le polyfill de Symfony est aussi performant, il faudrait peut-être remettre en cause l'utilisation de Ramsey/UUID.

Seulement, quand on fait quelques statistiques sur l'application, on passe surtout beaucoup de temps à coder/décoder les UUIDs plutôt qu'à en générer, et ça doit être le cas de beaucoup d'applications.

Mais dans ce cas, le benchmark de Jolicode est-il toujours pertinent, dans la mesure où celui-ci fait une comparaison sur la génération d'UUID ?

Nous avons donc fait d'autres benchmarks, mais cette fois-ci, en comparant une opération qui converti un UUID binaire en chaîne et une chaîne en binaire.

Avec Ramsey/UUID, cela est fait quand on crée un objet Uuid depuis un binaire, puis que l'on retransforme cet objet en binaire :

<?php
\Ramsey\Uuid\Uuid::fromBytes($bytes)->getBytes();

Nous avons créé une classe Uuid qui utilise l'extension PHP "uuid", sous la forme d'un ValueObject:

<?php
final class Uuid {
    /**
     * @var string
     */
    private $uuid;

    public function __construct(string $uuid)
    {
        if (\uuid_is_valid($uuid) === false) {
            throw new RuntimeException("Wrong UUID format");
        }
        $this->uuid = $uuid;
    }

    public function equals(Uuid $other): bool
    {
        return $this->uuid === $other->uuid;
    }

    public static function fromBytes(string $bytes): self
    {
        return new self(\uuid_unparse($bytes));
    }

    public function getBytes(): string
    {
        return \uuid_parse($this->uuid);
    }

    public function toString(): string
    {
        return $this->uuid;
    }
}

Avant même de benchmarker un Uuid::fromBytes($bytes)->getBytes(), on sait déjà que ça sera plus performant que Ramsey car il n'y a pas d'appel sur des factories et autres codecs. De plus, en interne, Ramsey conserve l'UUID sous une forme décomposée en plusieurs champs, alors que dans notre code précédent, l'UUID est mémorisé sous sa forme chaîne de caractères.

Nous avons du coup regardé comment était réalisé le polyfill Symfony qui permet de remplacer les fonctions de l'extension UUID quand elles n'existent pas, et nous nous sommes dit qu'il était possible de l'optimiser, car un traitement un peu gourmand était fait lors du uuid_unparse pour valider la structure de l'UUID.

Voici comment nous pourrions réaliser cette optimisation :

<?php
final class Uuid {
    /**
     * @var string
     */
    private $uuid;

    public function __construct(string $uuid)
    {
        if (\preg_match('`^[0-9a-f]{8}(-[0-9a-f]{4}){3}-[0-9a-f]{12}$`Di', $uuid) === 0) {
            throw new RuntimeException("Wrong UUID format");
        }
        $this->uuid = $uuid;
    }

    public function equals(Uuid $other): bool
    {
        return $this->uuid === $other->uuid;
    }

    public static function fromBytes(string $bytes): self
    {
        if (\strlen($bytes) !== 16) {
            throw new RuntimeException("Invalid binary UUID. Length is not 16 bytes");
        }

        $hex = \substr_replace(\bin2hex($bytes), '-', 8, 0);
        $hex = \substr_replace($hex, '-', 13, 0);
        $hex = \substr_replace($hex, '-', 18, 0);
        return new self(\substr_replace($hex, '-', 23, 0));
    }

    public function getBytes(): string
    {
        return \hex2bin(\str_replace('-', '', $this->uuid));
    }

    public function toString(): string
    {
        return $this->uuid;
    }
}

Le temps d’exécution pour 1 million d'itérations nous donne :

Ramsey => 2583 ms
ext-uuid => 1260 ms
polyfill-symfony => 4020 ms
custom => 642 ms

(l'environnement n'a pas beaucoup d'importance, sachez juste que le test a été fait sur Ubuntu 19.10 avec PHP 7.3.11)

Nous avons ré-exécuté ce benchmark plusieurs fois pour en être sûr, mais oui, le code est deux fois plus rapide que l'extension UUID !

Quant à la génération des UUIDs, comme c'est une opération peu courante pour nous, nous avons continué à utiliser Ramsey pour cela.

Dans notre contexte, on s'aperçoit que Ramsey/UUID n'est pas forcement pertinent, mais ce qui est le plus surprenant, c'est que notre code PHP est plus performant dans l'encodage/décodage d'UUID que l'extension.
Donc, si vous n'avez pas cette extension, ce n'est pas bien grave, car elle est moins performante que sa version en PHP.

Update: Depuis l'écriture de cet article, Nicolas Grekas a soumis une PR pour optimiser le polyfill de Symfony.
Voici le benchmark avec le résultat de sa PR:

Ramsey => 2583 ms
ext-uuid => 1260 ms
polyfill-symfony => 4020 ms
polyfill-symfony-optim => 1145 ms
custom => 642 ms

---

Voici le code utilisé pour le benchmark (+ un test complémentaire de l'impact sur le check à la construction)

https://gist.github.com/f2r/4f21279732cc1ba81dddc05ef042a1f5

Comments

[Aurélien Lajoie]

ext-uuip c'est le résultat via l'extension PECL ?
Est-il possible d'avoir le code des tests ?

Sur le custom on peut gagner encore un peu. fromBytes appelle le constructeur qui vérifie la chaîne avec preg_match, la chaîne étant valide par construction, il faudrait essayer avec un constructeur sans vérification de format. Un million de preg_match ça doit même être assez important.

[Frédéric Bouchery]

Je viens d'ajouter le code en fin d'article ;)

[Aurélien Lajoie]

J'ai refait un module en C pour voir pour aller encore plus loin.
J'ai modifié le module pecl pour garder les tests et les signatures de fonction
Premier test, sans validation du uuid sur le constructeur, deuxième en gardant la validation, troisième la version custom de git:

ext-uuid => 2753 ms
ext-uuid_c => 3735 ms
custom => 4816 ms

Là où il y a le plus à gagner c'est sur le unparse.
Les deux fonctions modifiées

#define UUID_STRING_LEN 36
static inline int hex_to_bin(int x)
{
    switch (x) {
      case '0' ... '9': return x - '0';
      case 'a' ... 'f': return 10 + x - 'a';
      case 'A' ... 'F': return 10 + x - 'A';
      default:          return -1;
    }
}

static int __uuid_parse(const char *str, unsigned char uuid[16])
{
    int j = 0;
    for (int i = 0; i < UUID_STRING_LEN; i++) {
        if (i == 8 || i == 13 || i == 18 || i == 23) {
            if (str[i] != '-')
                return -1;
        } else if (!isxdigit(str[i])) {
            return -1;
        } else {
            int hi = hex_to_bin(str[i]);
            int lo = hex_to_bin(str[++i]);
            uuid[j++] = (hi << 4) | lo;
        }
    }
    return 0;
}

PHP_FUNCTION(uuid_parse)
{

    const char * uuid = NULL;
    size_t uuid_len = 0;
    uuid_t uuid_bin;



    if (zend_parse_parameters(ZEND_NUM_ARGS(), "s", &uuid, &uuid_len) == FAILURE) {                                    
        return;                                                                                                        
    }

    if (__uuid_parse(uuid, uuid_bin)) {                                                                                
        RETURN_FALSE;
    }                                                                                                                  

    RETURN_STRINGL((char *)uuid_bin, sizeof(uuid_t));                                                                  
}   

char const __str_digits_lower[36] = "0123456789abcdefghijklmnopqrstuvwxyz";                                            

static void __uuid_fmt(char buf[UUID_STRING_LEN + 1], const uuid_t uuid)                                               
{                                                                                                                      
    char *p = buf;                                                                                                     

    for (int i = 0; i < 16; i++) {                                                                                     
        if (i == 4 || i == 6 || i == 8 || i == 10) {                                                                   
            *p++ = '-'; 
        }
        *p++ = __str_digits_lower[uuid[i] >> 4];                                                                       
        *p++ = __str_digits_lower[uuid[i] & 15];                                                                       
    }   
    *p = '\0';                                                                                                         
}   

PHP_FUNCTION(uuid_unparse)
{

    const char * uuid = NULL;
    size_t uuid_len = 0;
    char uuid_txt[UUID_STRING_LEN + 1];



    if (zend_parse_parameters(ZEND_NUM_ARGS(), "s", &uuid, &uuid_len) == FAILURE) {
        return;
    }

    if (uuid_len != sizeof(uuid_t)) {
        RETURN_FALSE;
    }

    __uuid_fmt(uuid_txt, uuid);

    RETURN_STRINGL(uuid_txt, UUID_STRING_LEN);
}

[Aurélien Lajoie]

Allez, améliorons directement util-linux spinics.net/lists/util-linux-ng/ms... sur le unparse ça divise par 10 le temps

[Aurélien Lajoie]

Du coup en descendant les étages on finit par arriver à l'assembleur et aux instructions SIMD

stackoverflow.com/questions/538237...

[Frédéric Bouchery]

Beau travail !

[Aurélien Lajoie]

C'est mergé github.com/karelzak/util-linux/com...

[Grégoire Pineau]

Coucou

Mais dans ce cas, le benchmark de Jolicode est-il toujours pertinent, dans la mesure où celui-ci fait une comparaison sur la génération d'UUID ?

Dans le cas des applications que je conçoit, il n'y a jamais besoin de convertir des UUID du format string au format binaire (ou vice versa). Je n'utilise que uuid_create(). Soit ces lignes la

Je ne vois pas bien l’intérêt de passer de string a binaire :( Ah si peut être : Si on utilise un SGBD qui ne support pas les UUID nativement. Heureusement que j'utilise PostgreSQL :)

---

Sinon si tu trouves des optims à backporté dans le polyfill, je suis preneur :)

[Frédéric Bouchery]

Sinon si tu trouves des optims à backporté dans le polyfill, je suis preneur :)

Nicolas, suite à mon article, a déjà soumis une PR pour optimiser le polyfill :)
github.com/symfony/polyfill/pull/244
Il est réactif le bougre :)

[Alban Baixas]

Merci pour ton post,

Il est encore possible d'améliorer les performances de fromBytes (au prix d'un peu de lisibilité).

// 1_000_000 itérations
custom-without-check    => 541 ms
custom-without-check-v2 => 521 ms

    public static function fromBytes(string $bytes): self
    {
        if (\strlen($bytes) !== 16) {
            throw new RuntimeException("Invalid binary UUID. Length is not 16 bytes");
        }

        return new self(
            \substr_replace(
                \substr_replace(
                    \substr_replace(
                        \substr_replace(\bin2hex($bytes), '-', 8, 0)
                        , '-', 13, 0
                    ), '-', 18, 0
                ), '-', 23, 0
            ), false
        );
    }

ps: dans le gist le nombre d'itération est de 10_000_000

[Frédéric Bouchery]

En effet, il y a un très léger gain. C'est intéressant de voir que cette écriture puisse faire gagner quelques "ms".
(Oui, sur le gist, j'était resté à 10 millions, car j'avais fait pas mal de tests avec cette valeur)