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

Version imprimable

05/02/2012, 03h33
Kaluza

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

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. ;)
05/02/2012, 11h59
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.
05/02/2012, 14h07
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.
06/02/2012, 09h22
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.
06/02/2012, 11h26
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.
06/02/2012, 13h40
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.:aie:
06/02/2012, 16h03
Klaim

J'étais justement en train de me dire que ça vaut vraiment pas le coup... :aie:
08/02/2012, 17h33
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 :)
08/02/2012, 18h05
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 ...

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.