Ennixo

Derniers articles

Comparaison de tableaux d'octets ultra rapide

Mercredi 22 juillet 2009

En ce moment pour le taf, je bosse sur une application dans laquelle je dois comparer l'égalité entre diverses valeurs et notamment des tableaux d'octets d'assez grande taille (plusieurs mégaoctets).

Au départ je comparais octet par octet mais je n'étais guère satisfait des performances, j'ai alors cherché sur le net et j'ai trouvé une idée intéressante, consistant à comparer directement des blocs de 8 octets via un cast du pointeur d'octet vers un pointeur d'UInt64. Résultat : c'était 6 fois plus rapide, pas mal mais à mon avis il y avait mieux.

C'est alors que je me suis souvenu avoir aperçu dans le code source d'un certain OS nommé "Fenêtres" que dans l'algorithme de comparaison de chaînes de caractère, il y avait 8 comparaisons par itération afin de gagner en performances. J'ai donc tenté cette approche, n'y croyant qu'à moitié.

Et là, stupéfaction, cet algorithme est environ 65 fois plus rapide que le premier algorithme. Ceci s'explique par le fait que la comparaison s'effectue par blocs de 64 octets au lieu d'un seul octet.

Pour ajouter une petite cerise sur le gâteau, mais surtout pour subvenir parfaitement à mes besoins (c'est à dire comparer des tableaux de quelques mégaoctets) je compare par blocs de 256.

J'ai donc un algorithme qui est 285 fois plus rapide que l'algorithme de base et qui me permet de ne plus me soucier du temps nécessaire à la comparaison des tableaux.

Mais sans plus attendre, voici le fameux algorithme :

public unsafe static bool ArrayEquals(byte[] b1, byte[] b2)
{
    if (b1 == null && b2 == null) return true;
    if (b1 == null || b2 == null) return false;
    if (b1.Length != b2.Length) return false;

    int ints = b1.Length >> 3;
    int byteStart = (ints >> 5) << 8;
    int bytes = b1.Length - byteStart;
    int byteMax = byteStart + bytes;

    fixed (byte* bp1 = b1, bp2 = b2)
    {
        UInt64* ip1 = (UInt64*)bp1;
        UInt64* ip2 = (UInt64*)bp2;

        for (int i = 0; i < ints; i += 32)
        {
            if (ip2[i] != ip1[i]
                || ip2[i + 1] != ip1[i + 1]
                || ip2[i + 2] != ip1[i + 2]
                || ip2[i + 3] != ip1[i + 3]
                || ip2[i + 4] != ip1[i + 4]
                || ip2[i + 5] != ip1[i + 5]
                || ip2[i + 6] != ip1[i + 6]
                || ip2[i + 7] != ip1[i + 7]
                || ip2[i + 8] != ip1[i + 8]
                || ip2[i + 9] != ip1[i + 9]
                || ip2[i + 10] != ip1[i + 10]
                || ip2[i + 11] != ip1[i + 11]
                || ip2[i + 12] != ip1[i + 12]
                || ip2[i + 13] != ip1[i + 13]
                || ip2[i + 14] != ip1[i + 14]
                || ip2[i + 15] != ip1[i + 15]
                || ip2[i + 16] != ip1[i + 16]
                || ip2[i + 17] != ip1[i + 17]
                || ip2[i + 18] != ip1[i + 18]
                || ip2[i + 19] != ip1[i + 19]
                || ip2[i + 20] != ip1[i + 20]
                || ip2[i + 21] != ip1[i + 21]
                || ip2[i + 22] != ip1[i + 22]
                || ip2[i + 23] != ip1[i + 23]
                || ip2[i + 24] != ip1[i + 24]
                || ip2[i + 25] != ip1[i + 25]
                || ip2[i + 26] != ip1[i + 26]
                || ip2[i + 27] != ip1[i + 27]
                || ip2[i + 28] != ip1[i + 28]
                || ip2[i + 29] != ip1[i + 29]
                || ip2[i + 30] != ip1[i + 30]
                || ip2[i + 31] != ip1[i + 31])
                return false;
        }

    }

    for (int i = byteStart; i < byteMax; i++)
    {
        if (b1[i] != b2[i]) return false;
    }

    return true;
}

C'est tout simple en plus. Have fun =)



Conversion RGB <=> HSL précise et rapide

Mercredi 23 avril 2008

Actuellement, je travaille au développement d'un logiciel de graphisme dans le but d'apporter une nouvelle alternative à Photoshop, GIMP, Krita, Paint.Net mais aussi pour satisfaire mon égo. Ce dernier point fait que je tends vers ce que je pense être la perfection via des optimisations particulières, même si je dois parfois passer plusieurs jours "juste pour" diviser le temps de calcul par 2.



Mon œuvre musicale

Samedi 20 octobre 2007

Ca faisait un moment que ça me trottait dans la tête, je me suis enfin décidé à publier et à distribuer l'intégralité de mon œuvre musicale. Evidement il faut relativiser, il ne s'agit là que de musique auto-produite dont la majorité à été composée et enregistrée entre 1997 et 2002.



"IE"

Mardi 17 avril 2007

En tant que développeur Web, mon travail consiste — entre autres — à écrire des pages HTML, lesquelles s'appuient sur des feuilles de styles CSS. Celà nécessite toujours un peu de travail mais à force d'écrire des feuilles de style, un constat éloquant m'apparait : Internet Explorer est ma plus grande contrainte !



Blazing Inferno

Samedi 03 mars 2007

Voici une nouvelle nébuleuse qui ressemble vaguement à un brasier.