Reformatage efficace du tampon circulaire (tampon circulaire) en matrice continue

Question

J'ai implémenté avec succès une fonction qui copie une quantité arbitraire de valeurs à partir d'un point arbitraire dans un tampon circulaire vers un tableau continu, mais je voudrais en faire plus efficace. Voici un exemple minimum de mon code:

#include <string.h> 
#include <iostream> 
#include <chrono> 
#include <thread> 

using namespace std; 


/*Foo: a function*/ 
void Foo(int * print_array, int print_amount){ 
    /*Simulate overhead*/ 
    this_thread::sleep_for(chrono::microseconds(1000)); 
    int sum = 0; 
    for (int i = 0; i < print_amount; i++){ 
     sum += print_array[i];   //Linear operation 
//  cout << print_array[i] << " "; //Uncomment to check if correct funtionality 
    } 
} 

/*Example function*/ 
int main(){ 
    /*Initialze ring buffer*/ 
    int ring_buffer_elements = 32;        //A largeish size 
    int ring_buffer_size = ring_buffer_elements * sizeof(int); 
    int * ring_buffer = (int *) malloc(ring_buffer_size); 
    for (int i = 0; i < ring_buffer_elements; i++) 
     ring_buffer[i] = i;          //Fill buffer with ordered numbers 

    /*Initialze array*/ 
    int array_elements = 16;         //A smaller largeish size 
    int array_size = array_elements * sizeof(int); 
    int * array = (int *) malloc(array_size); 

    /*Set reference pointers*/ 
    int * start_pointer = ring_buffer; 
    int * end_pointer = ring_buffer + ring_buffer_elements; 

    /*Set moving copy pointer*/ 
    int * copy_pointer = start_pointer; 

    /*Set "random" amount to be copied at each iteration*/ 
    int copy_amount = 11; 

    /*Set loop amount to check functionality or run time*/ 
    int loop_amount = 1000;         //Set lower if checking functionality 

    /***WORKING METHOD***/ 
    /*Start timer*/ 
    auto start_time = chrono::high_resolution_clock::now(); 

    /*"Continuous" loop*/ 
    for (int i = 0; i < loop_amount; i++){ 
     /*Copy loop*/ 
     for (int j = 0; j < copy_amount; j++){ 
      array[j] = *copy_pointer;   //Copy value from ring buffer 
      copy_pointer++;      //Move pointer 
      if (copy_pointer >= end_pointer)  
       copy_pointer = start_pointer; //Reset pointer if reached end of ring buffer 
     } 
     Foo(array, copy_amount); //Call a function 
    } 

    /*Check run time*/ 
    chrono::duration<double> run_time_ticks = chrono::high_resolution_clock::now() - start_time; 
    double run_time = run_time_ticks.count(); 

    /*Print result*/ 
    cout << endl << run_time << endl; 


/***NAIVE METHOD***/ 
    /*Reset moving pointer*/ 
    copy_pointer = start_pointer; 

    /*Start timer*/ 
    start_time = chrono::high_resolution_clock::now(); 

    /*"Continuous" loop*/ 
    for (int i = 0; i < loop_amount; i++){ 
     /*Compute how many elements must be copied after reaching end of ring buffer*/ 
     int copy_remainder = copy_pointer + copy_amount - end_pointer; //Ugly pointer arithmetic? 
     /*Check if we need to loop back or not*/ 
     if (copy_remainder <= 0){ 
      Foo(copy_pointer, copy_amount); //Call function 
      copy_pointer += copy_amount; //Move pointer 
     } else { 
      Foo(copy_pointer, copy_amount-copy_remainder); //Call function with part of values from copy pointer 
      Foo(start_pointer, copy_remainder);    //Call function with remainder of values from start of ring buffer 
      copy_pointer = start_pointer + copy_remainder; //Move pointer 
     } 
    } 

    /*Check run time*/ 
    run_time_ticks = chrono::high_resolution_clock::now() - start_time; 
    run_time = run_time_ticks.count(); 

    /*Print result*/ 
    cout << endl << run_time << endl; 


    /***memcpy METHOD***/ 
    /*Reset moving pointer*/ 
    copy_pointer = start_pointer; 

    /*Initialize size reference*/ 
    int int_size = (int) sizeof(int); 

    /*Start timer*/ 
    start_time = chrono::high_resolution_clock::now(); 

    /*"Continuous" loop*/ 
    for (int i = 0; i < loop_amount; i++){ 
     /*Compute how many elements must be copied after reaching end of ring buffer*/ 
     int copy_remainder = copy_pointer + copy_amount - end_pointer; //Ugly pointer arithmetic? 
     /*Check if we need to loop back or not*/ 
     if (copy_remainder <= 0){ 
      memcpy(array, copy_pointer, copy_amount*int_size); //Use memcpy 
      copy_pointer += copy_amount;      //Move pointer 
     } else { 
      memcpy(array, copy_pointer, (copy_amount-copy_remainder)*int_size);     //Use memcpy with part of values from copy pointer 
      memcpy(array+(copy_amount-copy_remainder), start_pointer, copy_remainder*int_size); //Use memcpy wih remainder of values from start of ring buffer 
      copy_pointer = start_pointer + copy_remainder;          //Move pointer 
     } 
     /*Call a function*/ 
     Foo(array, copy_amount); 
    } 

    /*Check run time*/ 
    run_time_ticks = chrono::high_resolution_clock::now() - start_time; 
    run_time = run_time_ticks.count(); 

    /*Print result*/ 
    cout << endl << run_time << endl; 

} 

Le tampon circulaire est utilisé pour un flux de mise à jour en continu des données audio et ainsi la quantité de latence introduite doit être maintenue à un minimum, pourquoi je suis en train de l'améliorer .

Je pensais que la copie des valeurs dans WORKING METHOD est redondante et qu'il devrait être possible de simplement passer à travers les données du tampon circulaire d'origine. Mon approche naïve de faire cela était d'écrire avec les données d'origine et chaque fois que les données rebouclées réécrivent (voir AMÉLIORATION NAIVE).

En effet, dans cet exemple minimal, cette amélioration est plus rapide. Cependant, dans ma vraie application, Foo est remplacée par une fonction qui écrit dans un buffer matériel et qui a un overhead ̣̣̣̣̣- le résultat final est plus lent que le code WORKING METHOD, ce qui signifie que je ne devrais jamais l'utiliser (ou Foo dans ce cas) plus d'une fois (par temps pour écrire des données audio). (EDIT un overhead simulé a été ajouté à Foo pour décrire précisément ce problème).

Ma question est donc de savoir s'il existe un moyen plus rapide de copier des données d'un tampon circulaire vers un seul tableau continu?

(En outre, le tampon d'anneau ne sera jamais besoin de boucler plus d'une fois par le temps d'écrire: copy_amount est toujours inférieur à ring_buffer_elements)

Merci!

EDIT Extrait de code original remplacé avec un minimum d'exemple selon la suggestion de Passer By.

EDIT 2 Ajout d'un préfixe simulé et d'un memcpy selon la suggestion de duong_dajgja. Dans l'exemple, la méthode memcpy et la méthode de travail ont essentiellement les mêmes performances (ce dernier ayant un peu d'avantage). Dans mon application memcpy est environ 3-4% plus rapide que la méthode de travail lors de l'utilisation du plus petit tampon possible. Si vite, mais malheureusement loin d'être significatif.

Answer 1

Je voudrais suggérer une structure semblable à un tampon en anneau qui est en fait un tableau.

Étant donné que vos données sont en flux audio, je suppose que les données entreraient dans l'ordre (par exemple, les données de séries chronologiques).

Supposons que le buff a une capacité de 100 éléments. Une fois que le buff est plein et que vous voulez ajouter un nouvel élément à la fin, vous devez d'abord déplacer la région de buff [1] vers buff [99] en utilisant memmove puis simplement mettre le nouvel élément à buff [99] . Ce faisant, vous êtes sûr que votre tampon circulaire est toujours un tableau avec l'ordre correct (de buff [0] à buff [99]). Maintenant, simplement memcpy région entière de buff [0] à buff [99] au tableau de destination comme vous le souhaitez.