Méthode la plus rapide pour mettre toutes les valeurs d'un tableau à 0

[Kaluza]

Bonjour.

Petite question basique : quelle est la méthode la plus rapide pour remettre (ie pas à l'initialisation mais ailleurs dans le programme) à 0 toutes les valeurs d'un tableau du type T myarray[100] (avec T : int, unsigned int, long long int, unsigned long long int ...). Même question pour un tableau dynamique T *myarray = new T[100]. (peut être un memset ?)

Merci beaucoup.

[DonQuiche]

Bonjour.

D'abord les deux cas ne font aucune différence Dans le premier le tableau est alloué sur la pile alors que dans le second il l'est sur le tas. Mais ça reste la même chose.

Ensuite, de toutes les façons simples, memset est probablement la plus rapide en général et suffisamment rapide pour presque tous les besoins. Cela dit, deux bémols :
* Puisqu'elle est écrite de façon à pouvoir convenir à tous les cas (indifférente au padding, contenant peut-être quelques mesures de sécurité, etc), il est possible que l'on puisse faire plus rapide.
* Elle n'est pas forcément optimisée pour le processeur visé. Si la plateforme visée est bien définie, tu peut-être faire mieux.

[cob59]

std::fill ou std::fill_n.

Sauf erreur, je crois que le template de ces algos est spécialisé pour appeler memset si T est un type primitif.

[DonQuiche]

Je me demande si on gagnerait à paralléliser. J'imagine en effet que ce n'est pas la bande passante mais la latence qui limite les performances, avec un CPU qui se tourne souvent les pouces. Si c'est le cas, on pourrait augmenter le nombre de coeurs exploités jusqu'à un certain point avant de saturer la bande passante.

Cela dit je me plante peut-être, il se peut que les architectures actuelles soient assez malignes pour anticiper les accès jusqu'au point où la bande passante serait déjà saturée par un seul coeur. Voire que la bande passante soit si élevée qu'elle permette de faire mouliner à bloc plusieurs coeurs.

[Klaim]

Ils en ont parlé lors des conférences Going Native... il se peut que le prochain standart inclue des algorithmes parallélisé, mais totalement repensés pour être suffisamment générique.


Dans ton cas, j'imagine qu'utiliser std::async sur différentes parties de ton array marcherait tout à fait. Un async par coeur je pense, mais c'est le système derrière qui déciderait du nombre de threads de toutes façons.

[Joel F]

pour avoir une efficacité parallele superierue à pouilleme % sur un

a[i] = 0;

va falloir vraiment en enquillés des i.

Juste mes 2 eurocents.

[Klaim]

J'étais justement en train de me dire que ça vaut vraiment pas le coup...

[Kaamui]

bonjour,

juste par curiosité, on considère qu'on gagne en complexité si on rempli un tableau avec deux cœurs en parallèle ? Parce qu'en pratique, j'ai du mal à voir comment on peut descendre en dessous de n itérations pour un tableau de taille n...

J'ai l'impression que théoriquement on reste dans une complexité de O(n/2) donc O(n) et qu'en pratique on gagne du temps à faire 2 coups par coups mais qu'au final on reste sur un nombre d'itérations égal quelque soit la méthode...

Mais bon le principal d'est d'aller plus vite

[Ekleog]

On gagne en complexité si on considère qu'on remplit avec k coeurs.
On passe alors à O(n/k).
Mais, dès que l'on fixe k constante, la complexité revient en O(n).

Bref, de toute façon pour remplir un tableau à 0 créer un thread sera souvent plus lent que de remplir le tableau en mono-thread, donc ...

[DonQuiche]

En réalité mes suppositions étaient justes : utiliser plusieurs coeurs accroît la vitesse à laquelle l'opération est traitée, même si le gain est faible.

Tests sur un espace mémoire de 1Go sur un i5 quacoeurs (windows 64)
1 thread : environ 250 ms
2, 3 ou 4 threads : environ 205 ms

Voici le code du test, en C# (écrire le code multithread était plus rapide dans ce langage) avec import de memset depuis mscvrt.

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
    unsafe class Program
    {
        [DllImport("msvcrt.dll", EntryPoint = "memset", CallingConvention = CallingConvention.Cdecl, SetLastError = false)]
        public static extern IntPtr MemSet(IntPtr dest, int c, IntPtr count);
        private static byte* thePtr;
 
        static void Main(string[] args)
        {
            int size = 1 << 30;
            byte[] array = new byte[size];
            unsafe
            {
                fixed (byte* ptr = array)
                {
                    thePtr = ptr;
                    Action[] actions = new Action[4];
                    for (int i = 0; i < actions.Length; i++) 
                    {
                        int start = i* (array.Length / actions.Length);
                        int count = array.Length / actions.Length;
                        actions[i] = () => CleanArray(start, count);
                    }
 
                    Stopwatch sw = new Stopwatch();
                    sw.Start();
 
                    //CleanArray(0, array.Length);
                    Parallel.Invoke(actions);
 
                    var result = sw.ElapsedMilliseconds;
                    Console.WriteLine((result));
                    Console.ReadLine();
                }
            }
        }
 
        private static unsafe void CleanArray(int start, int count)
        {
            MemSet((IntPtr)(thePtr + start), 0, (IntPtr)count);
        }

EDIT: le code original contenait un bug, mise à jour.