10
votes

Pourquoi cette liste est-elle <>. Index de code si plus rapide que la liste [i] et manuelle comparer?

Je suis exécuté AQTime sur ce morceau de code, j'ai constaté que .indexof prend 16% du temps vs proche de 80% pour l'autre pièce ... Ils semblent utiliser les mêmes routines iséliques et autres. Appelé 116 000 fois l'insertion de 30 000 articles. Aucune de la liste Objets ne reçoit plus de 200 éléments. (J'utilise peut-être de manière incorrecte AQTime, je regarde cela)

class PointD : IEquatable<PointD>
{
    public double X, Y, Z;

    bool IEquatable<PointD>.Equals(PointD other)
    {
        return ((X == other.X) && (Y == other.Y) && (Z == other.Z));
    }
}

class PerfTest
{
    readonly List<PointD> _pCoord3Points = new List<PointD>();
    public int NewPoints;
    public int TotalPoints;

    public PerfTest()
    {
        NewPoints = 0;
        TotalPoints = 0;
    }
    public int CheckPointIndexOf(PointD pt)
    {
        int retIndex = _pCoord3Points.IndexOf(pt);
        if (retIndex < 0)
        {
            _pCoord3Points.Add(pt);
            NewPoints++;
        }
        TotalPoints++;
        return retIndex;    
    }

    public int CheckPointForBreak(PointD pt)
    {
        int retIndex = -1;
        for (int i = 0; i < _pCoord3Points.Count; i++)
        {
            PointD otherPt = _pCoord3Points[i];
            if ((pt.X == otherPt.X) &&
                (pt.Y == otherPt.Y) &&
                (pt.Z == otherPt.Z))
            {
                retIndex = i;
                break;
            }
        }
        if (retIndex == -1)
        {
            NewPoints++;
            _pCoord3Points.Add(pt);
        }
        TotalPoints++;
        return retIndex;
    }

    static void Main()
    {
        const int xmax = 300;
        const int ymax = 10;
        const int zmax = 10;
        const int imax = 4;

        var test = new PerfTest();
        //test.Init();
        Stopwatch sw = Stopwatch.StartNew();
        for (int i = 0; i < imax; i++)
        {
            for (int x = 0; x < xmax; x++)
            {
                for (int y = 0; y < ymax; y++)
                {
                    for (int z = 0; z < zmax; z++)
                    {
                        var pt = new PointD { X = x, Y = y, Z = z };
                        test.CheckPointIndexOf(pt);
                    }
                }
            }

        } 
        sw.Stop();
        string output = string.Format("Total: {0:0} New: {1:0} IndexOf: ", test.TotalPoints, test.NewPoints);
        Console.Write(output);
        Console.WriteLine(sw.Elapsed);

        test = new PerfTest();
        sw = Stopwatch.StartNew();
        for (int i = 0; i < imax; i++)
        {
            for (int x = 0; x < xmax; x++)
            {
                for (int y = 0; y < ymax; y++)
                {
                    for (int z = 0; z < zmax; z++)
                    {
                        var pt = new PointD { X = x, Y = y, Z = z };
                        test.CheckPointForBreak(pt);
                    }
                }
            }

        } 
        sw.Stop();
        output = string.Format("Total: {0:0} New: {1:0} PointD[] ", test.TotalPoints, test.NewPoints);
        Console.Write(output);
        Console.WriteLine(sw.Elapsed);
        Console.ReadLine();
    }
}


3 commentaires

Est vraiment indexof plus rapide? Lorsque j'ai essayé de reproduire indexofof était significativement plus lent, et je suppose que la spéculation de Jon sur la boxe est correcte.


Je reçois le résultat opposé exact, Indexof est 20 fois plus lent lorsque des points sont une structure. La méthode égale () d'une structure n'est pas bon marché. Publier un Véritable Exemple vérifiable.


Ah, si l'indexof est plus rapide sur votre machine, mais pas avec quelqu'un d'autre, c'est probablement à cause de votre profileur. Beaucoup de profileurs ne pénalisent pas également de code qu'ils ne peuvent pas fouiller.


3 Réponses :


0
votes

Quel est le type de _pcoord3points ? Si le type d'élément est un type de valeur qui ne remplace que égaux (objet) , il est possible que indexof est de boxe de manière répétée pour vérifier l'égalité. Que pourrait l'expliquer. Ce n'est vraiment que des devinations à ce stade, cependant ... si vous pouviez fournir un programme court mais complet qui démontre le problème, cela en ferait beaucoup plus facile de vous aider.


2 commentaires

Mais si index de a impliqué la boxe, il devrait être plus lent, pas plus rapide que l'OP affirme, n'est-ce pas?


En effet, Jon, vous semblez avoir raison. J'ai mesuré et indexofof est significativement plus lent (dans ma mesure autour du facteur 1000) pour les types de valeur et toujours autour d'un facteur de 100 plus lents pour les types de référence.



4
votes

Normalement, avant d'accéder à un élément de tableau, il vérifie que l'index est> = 0 et tampon débordant .

inutile Pour dire, cela empêche la performance si vous avez très peu de code au sein de votre boucle. Pour atténuer ce problème, le compilateur JIT optimise pour les boucles de la forme pour (i = 0; i - c'est-à-dire une boucle qui accède à tous les indices d'un tableau de 0 à longueur - 1. Il omet la vérification des limites de ce cas. (L'optimisation échoue si vous accédez à des choses comme une matrice [i + 1], pour la raison pour laquelle vous pourriez passer sur les limites.) P>

Malheureusement, cela fonctionne uniquement avec des tableaux, pas avec la liste s. Donc, votre dernier code ne sera pas optimisé. P>

mais depuis une liste contient en interne contient un tableau, et list.indexof () utilise une boucle pour accéder à chaque valeur dans la matrice directement, elle peut être optimisée. p>

Au fait, il vaut mieux dire pour (int i = 0; i qu'il ne veut dire int longueur = Array.Longueur; pour (int i = 0; i - car il ne peut pas être sûr que longueur code> est vraiment la longueur de la matrice. P> Edit: En regardant l'index du code à l'aide de réflecteur, la boucle optimisera en effet, mais comme les autres personnes ici ont mentionnées, il appelle égale () - ce qui nécessite un LOCKUPT et divers chèques de santé mentale. Donc, dans ce cas, l'index peut en fait être plus lente lorsque vous n'agissez pas avec un profileur. P>

Le code démonté: p>

internal virtual int IndexOf(T[] array, T value, int startIndex, int count)
{
    int num = startIndex + count;
    for (int i = startIndex; i < num; i++)
    {
        if (this.Equals(array[i], value))
        {
            return i;
        }
    }
    return -1;
}


1 commentaires

Connaissance aléatoire folle de .net là-bas!



10
votes

J'ai fait les hypothèses suivantes:

  • pointeur est une structure
  • indexof est en effet plus lent que manuellement itération manuelle de la liste

    Vous pouvez accélérer indexof en implémentant l'interface iéquatif xxx

    Sans implémenter l'interface , indexof comparera les deux éléments pointed à l'aide de ValueType.equals (objet autre) qui implique des opérations de boxe coûteuses.

    la documentation du IQEEQADABLE états d'interface:

    L'interface iéquatif est utilisée par des objets de collecte génériques tels que le dictionnaire , , et linkedlist Lorsque vous testez l'égalité dans de telles méthodes que contient , indexof , lastIndexof et et Supprimer . il devrait être mis en œuvre pour tout objet pouvant être stocké dans une collection générique.

    Voici mon code de référence complet: xxx

    sur Windows 7, x64, .NET 4.0 x64 Build I Obtenez les horaires suivants (environ): < / p> xxx

    Lorsque vous tournez pointed dans une classe Les horaires changent de xxx

    Lors de l'utilisation d'un struct pointed implémentation IEQADABLE Je reçois plus de résultats "similaires", mais indexof est toujours plus lent (il y a toujours Pas de différence significative lors de l'utilisation d'une classe maintenant): xxx


4 commentaires

@ 0XA3: Pourriez-vous appeler Liste .indexof une fois avant de démarrer la montre d'arrêt pour éliminer l'initialisation JIT Coût + une initialisation ponctuelle (constructeur statique de Equalitalcander Pour déterminer le bon comparateur, etc.) qui se passe sous la hotte? Non pas que je considère que cela importerait, compte tenu de l'ordre de la différence de magnitude que nous voyons.


@Ani: Oui, vous avez raison que le repère n'est pas précis en ce qui concerne les frais généraux JIT. Mais j'ai décidé de négliger l'effet. En fait, si vous réchauffez d'abord, vous verrez que la surcharge de JIT pour la boucle de la boucle est plus significative, ce qui semble raisonnable que la liste .indexof est contenue dans l'image native de mscorlib.dll .


Il finit par l'index de 8,08 ... et [] 10.018 ... c'est ma question pourquoi? Merci pour tout le travail de votre réponse actuelle


Quand j'ai changé de struct en classe qui l'a changé. J'ai compris. Merci encore