C: Volviendo un vacío contra el retorno de una doble * de una función parcial

Question

estoy trabajando en tratar de acelerar algún tipo de procesamiento de datos generales en C. He escrito varias subrutinas de la forma:

double *do_something(double *arr_in, ...) { 
    double *arr_out; 
    arr_out = malloc(...) 

    for (...) { 
    do the something on arr_in and put into arr_out 
    } 

    return arr_out; 
} 

I al igual que este estilo porque es fácil de leer y usar, pero a menudo me llaman como:

array = do_something(array,...); 

Tendría de código más rápido (y tal vez evitar pérdidas de memoria) si tuviera que usar en su lugar subfunciones vacío como:

void do_something(double *arr_in, ...) { 
    for (...) { 
     arr_in = do that something; 
    } 
    return; 
} 

actualización 1: Ejecuté valgrind --leak-check = completo en el ejecutable y parece que no hubo pérdidas de memoria con el primer método. Sin embargo, el ejecutable se vincula a una biblioteca que contiene todas las subrutinas que hice con este formulario, por lo que podría no detectar fugas de la biblioteca.

Tengo curiosidad sobre cómo escribiría las envolturas para liberar la memoria y lo que ** realmente hace, o lo que es un puntero a un puntero, así que evito usar ** la ruta (eso y tal vez lo hice mal porque no se compiló en mi mac).

Aquí hay una subrutina actual:

double *cos_taper(double *arr_in, int npts) 
{ 
int i; 
double *arr_out; 
double cos_taper[npts]; 
int M; 
M = floor(((npts - 2)/10) + .5); 

arr_out = malloc(npts*sizeof(arr_out)); 

for (i=0; i<npts; i++) { 
    if (i<M) { 
     cos_taper[i] = .5 * (1-cos(i * PI/(M + 1))); 
    } 
    else if (i<npts - M - 2) { 
     cos_taper[i] = 1; 
    } 
    else if (i<npts) { 
     cos_taper[i] = .5 * (1-cos((npts - i - 1) * PI/(M + 1))); 
    } 
    arr_out[i] = arr_in[i] * cos_taper[i]; 
} 
return arr_out; 
} 

De los consejos que he recibido aquí, suena como un método mejor sería:

void *cos_taper(double *arr_in, double *arr_out, int npts) 
{ 
int i; 
double cos_taper[npts]; 
int M; 
M = floor(((npts - 2)/10) + .5); 

for (i=0; i<npts; i++) { 
    if (i<M) { 
     cos_taper[i] = .5 * (1-cos(i * PI/(M + 1))); 
    } 
    else if (i<npts - M - 2) { 
     cos_taper[i] = 1; 
    } 
    else if (i<npts) { 
     cos_taper[i] = .5 * (1-cos((npts - i - 1) * PI/(M + 1))); 
    } 
    arr_out[i] = arr_in[i] * cos_taper[i]; 
} 
return 
} 

llamada:

int main() { 
    int npts; 
    double *data, *cos_tapered; 

    data = malloc(sizeof(data) * npts); 
    cos_tapered = malloc(sizeof(cos_tapered) * npts); 

//fill data 

    cos_taper(data, cos_tapered, npts); 
    free(data); 
    ... 
    free(cos_tapered); 
    ... 
    return 0; 
} 

Answer 1

La primera invocación puede filtrar fácilmente la memoria si no hay otro puntero a la asignación de memoria original, ya que probablemente sea ware ya que estás preguntando.

Sí, si puede escribir sensiblemente la segunda versión de la función llamada sin asignación de memoria, es probable que sea más rápido, porque la asignación de memoria lleva tiempo. Si solo modifica la función llamada para que haya preasignado las matrices de entrada y salida, podría simplemente transferir el costo de asignación de memoria a la función de llamada.

Pero el uso disciplinado de la primera versión está bien; la función asigna espacio, y mientras mantenga un registro del espacio original pasado y el nuevo espacio pasado y pueda liberar ambos, no hay problema.

Puede ejecutar a sí mismo en el 'mismo' problema:

xyz = realloc(xyz, newsize); 

Si xyz es el único puntero a la memoria asignada, que se fuga de memoria en un error de asignación, ya que acaba de Demolí XYZ con una puntero nulo. Si hay otro puntero que utilizará para liberar el espacio original, este modismo no importa, pero tenga cuidado con él.

---

No he vuelto a digerir completamente la información adicional en la pregunta desde que escribí la versión original de esta respuesta.

Answer 2

Si puede hacer su operación en su lugar, hacerlo probablemente ayudará a prevenir errores (al menos relacionados con la memoria) y será más rápido por lo menos el tiempo necesario para hacer la operación malloc(). El tipo de retorno real de su función probablemente no afecte la velocidad de ninguna manera.

Answer 3

En su función

 
void do_something(double *arr_in, ...) { 
    for (...) { 
     arr_in = do_that_something; 
    } 
} 

Eso sería incorrecto, ya que usted no tiene ningún parámetro por referencia a pasar de nuevo a la matriz una vez que la función de do_something sale de scope..it debería ser algo como esto

 
void do_something(double **arr_in, ...) { 
    for (...) { 
     *arr_in = do_that_something; 
    } 
} 
/* 
** Would be called like this: 
** do_something(&array, ...); 
*/ 

Observe el primer ejemplo, ya que es más fácil de leer. Es necesario añadir la comprobación de errores en el primer ejemplo, si la llamada a malloc falló y continuar con el procesamiento con un puntero NULL ...

Espero que esto ayude, Saludos, Tom.

Answer 4

La devolución del doble no le cuesta mucho en términos de tiempo de ejecución.

Mucho más importante es la asignación de memoria cada vez que ingresas a la función. Si puede preasignar, o almacenar el resultado en su lugar como sugirió, eso debería mejorar la velocidad.

Otra cosa a considerar es si realmente necesita toda la precisión que proporciona un doble (frente a un tipo de flotador). En muchos casos, los flotadores son mucho más rápidos.

Answer 5

El malloc puede ser costoso en relación con el procesamiento que está realizando, dependiendo de qué se trate. En lugar de restringirse al procesamiento en el lugar, simplemente use dos parámetros, dentro y fuera, y deje la asignación a la persona que llama. Esto brinda al que llama la opción de reutilizar la memoria sin asignar una nueva matriz para cada llamada.

Answer 6

Ahorraría una pequeña cantidad de tiempo al no tener el malloc, pero esto puede acumularse rápidamente y marcar una diferencia notable si llama do_something en un círculo cerrado. También ahorrarías una pequeña cantidad de tiempo al no tener que devolver el doble * pero, de nuevo, esto puede sumar si haces algo con frecuencia.

En cuanto a la transformación propiamente dicha, no habría ninguna diferencia ya que ambos casos están operando en un doble *

Puesto que usted no está utilizando la asignación de memoria dinámica en el método propuesto ya no hay posibilidad de pérdidas de memoria.

Answer 7

También tiene la opción de pasar un segundo parámetro como su parámetro de salida. Por ejemplo

int do_something (double * in , double * out) { 
    /* 
    * Do stuff here 
    */ 
    if (out is modified) 
     return 1; 
    return 0; 
} 

O similar sin la devolución.

Answer 8

Sugeriría que si asigna memoria dentro de una subfunción, crea un contenedor correspondiente para la limpieza, libera la memoria asignada, o hace que sea obvio que la función asigna memoria, para evitar el olvido para liberar la memoria.

En cuanto a la huella de memoria, el segundo enfoque usaría menos memoria, pero solo funciona si las funciones no modifican el tamaño de la matriz inicial. Dependiendo del uso, esto no siempre es cierto.

En cuanto a velocidad, el segundo enfoque debería ser teóricamente más rápido, porque un puntero menos se inserta en la pila al final de la llamada de función (do_something), pero un solo puntero es mínima diferencia a menos que haya un uso repetido , en cuyo caso, considerar detenidamente la posibilidad de inline debería ser una consideración.Por lo tanto, a menos que haya medido la sobrecarga de la llamada a la función como problema (por perfilando), no me molestaría con tales micro-optimizaciones sin un buen motivo (huella de memoria o creación de perfiles).

Answer 9

Optaría por permitir que la persona que llama aloje la memoria si así lo desean, pero también puede optar por realizar la operación en su lugar, o hacer que realice la asignación.

Para operaciones que no se pueden realizar en su lugar, puede verificar manualmente si la persona que llama le ha dado las mismas ubicaciones de entrada y salida, y hacer una copia de la entrada usted mismo. Luego procese usando esa copia como entrada. Esto hace que se vea en su lugar el llamador de la función.

Por ejemplo, supongamos que desea crear una función que lleva una combinación de índices aleatorios como output[i] == input[ input[i] ] (una función tonta, verdadera, pero que no es trivial).

#include <stdlib.h> 
#include <string.h> 
int shuffle(size_t const * input, size_t const size, size_t ** p_output) 
{ 
    int retval = 0; 
    size_t i; 
    char in_place = 0; 
    char cleanup_output = 0; 

    if (size == 0) 
    { 
     return 0; // nothing to do 
    } 
    // make sure we can read our input and write our output 
    else if (input == NULL || p_output == NULL) 
    { 
     return -2; // illegal input 
    } 
    // allocate memory for the output 
    else if (*p_output == NULL) 
    { 
     *p_output = malloc(size * sizeof(size_t)); 
     if (*p_output == NULL) return -1; // memory allocation problem 
     cleanup_output = 1; // free this memory if we run into errors 
    } 
    // use a copy of our input, since the algorithm doesn't operate in place. 
    // and the input and output overlap at least partially 
    else if (*p_output - size < input && input < *p_output + size) 
    { 
     size_t * const input_copy = malloc(size * sizeof(size_t)); 
     if (input_copy == NULL) return -1; // memory allocation problem 
     memcpy(input_copy, input, size * sizeof(size_t)); 
     input = input_copy; 
     in_place = 1; 
    } 

    // shuffle 
    for (i = 0; i < size; i++) 
    { 
     if (input[i] >= size) 
     { 
      retval = -2; // illegal input 
      break; 
     } 
     (*p_output)[i] = input[ input[i] ]; 
    } 

    // cleanup 
    if (in_place) 
    { 
     free((size_t *) input); 
    } 
    if (retval != 0 && cleanup_output) 
    { 
     free(*p_output); 
     *p_output = NULL; 
    } 

    return retval; 
} 

Esto hace que su función más robusto - la persona que llama función puede asignar memoria para la salida (si es que quieren mantener la entrada de alrededor), o tener la salida aparecerá en el mismo lugar que el de entrada, o si tiene asigna la memoria para la salida. Esto es especialmente bueno si obtuvieron las ubicaciones de entrada y salida desde otro lugar, y no están seguros de si son distintas. No tienen que saber nada sobre el funcionamiento de la función.

// caller allocated memory 
my_allocated_mem = malloc(my_array_size * sizeof(size_t)); 
if(my_allocated_mem == NULL) { /*... */ } 
shuffle(my_array, my_array_size, &my_allocated_mem); 

// function allocated memory 
my_allocated_mem = NULL; 
shuffle(my_array, my_array_size, &my_allocated_mem); 

// in place calculation 
shuffle(my_array, my_array_size, &my_array); 

// (naughty user isn't checking the function for error values, but you get the idea...) 

Se puede ver un ejemplo completo de uso here.

Como C no tiene excepciones, es bastante estándar usar el valor de retorno de una función para informar errores y pasar valores calculados a través del puntero de función.

Answer 10

El tipo de función determina la interfaz entre la función y los lugares en el código que la llama, lo que quiere decir que es probable que existan problemas importantes de diseño de código en la elección. Como regla general, vale más la pena pensar que la velocidad (siempre que el problema de velocidad no sea una pérdida de memoria tan grande como para que la aplicación sufra DOS por agolpamiento ...)

El segundo tipo indica bastante ineficiente para mutar la matriz. El primero es ambiguo: tal vez usted siempre mute la matriz, tal vez siempre proporcione un resultado recién asignado, tal vez su código a veces hace una y otras veces hace otra. La libertad viene con un campo minado de dificultades para asegurarse de que el código sea correcto. Si sigue esta ruta, el esfuerzo de poner una aspersión liberal de assert() s a través de su código, para afirmar invariantes sobre la frescura y la compartición de los punteros, probablemente se pagará por sí mismo con gran interés cuando se depure.

Answer 11

Bueno, comenzaste tu pregunta hablando de velocidad y no creo que este tema haya sido realmente respondido. Lo primero que hay que decir es que trabajar en el paso de parámetros no parece ser la mejor manera de acelerar las cosas ...

Estoy de acuerdo con otras respuestas: la primera propuesta que utiliza malloc es una carretera con fugas de memoria (y es probablemente más lenta de todos modos), la otra propuesta que surgió es mucho mejor. Siguiendo las sugerencias de ergosys en el comentario, puedes mejorarlo fácilmente y obtener un buen código C.

Ahora con algunas matemáticas aún puede mejorar.

En primer lugar, no es necesario utilizar llamadas dobles y de piso para calcular enteros. Obtiene la misma M sin piso y no agrega 0.5 simplemente escribiendo M = (nbelts-2)/10; (Sugerencia: división entera truncada a entero).

Si también nota que siempre tiene M < nbelt - M - 2 < nbelt (Bueno, ciertamente ya lo sabe) puede evitar probar los límites dentro de los bucles dividiendo el bucle en tres partes independientes. Y esto aún puede optimizarse en el caso en que en array sea lo mismo que out array.

Su función podría llegar a ser algo como esto:

void cos_taper(double *arr_in, double *arr_out, int npts) 
{ 
int i; 
int M; 
M = (npts - 2)/10; 

if (arr_out == arr_in) { 
    for (i=0; i<M; i++) { 
     arr_out[i] *= .5 * (1-cos(i * PI/(M + 1))); 
    } 
    for (i = npts - M - 2; i<npts; i++) { 
     arr_out[i] *= .5 * (1-cos((npts - i - 1) * PI/(M + 1))); 
    } 
} 
else { 
    for (i=0; i<M; i++) { 
     arr_out[i] = arr_in[i] * (.5 * (1-cos(i * PI/(M + 1)))); 
    } 
    for (; i<npts - M - 2; i++) { 
     arr_out[i] = arr_in[i]; 
    } 
    for (; i<npts; i++) { 
     arr_out[i] = arr_in[i] * (.5 * (1-cos((npts - i - 1) * PI/(M + 1)))); 
    } 
} 
} 

eso no es positiva al final de la misma y con son posibles algunas optimizaciones más más pensado, por ejemplo, expresiones como (.5 * (1-cos(i * PI/(M + 1)))); parece que se podría conseguir un número relativamente pequeño de valores (depende del tamaño de nbelt ya que es una función de iy nbelt, el número de resultados diferentes es una ley cuadrada, pero cos debería reducir ese número nuevamente ya que es periódico). Pero todo depende del nivel de rendimiento que necesite.

Answer 12

Acabo de ejecutar su código (después de corregir una serie de pequeños errores). Luego tomé varios stackshots. Las personas que dijeron malloc serían su culpable si tuvieran razón. Casi todos los de su tiempo lo pasan allí. Comparado con eso, el resto de tu código no es muy significativo. Aquí está el código:

#include <math.h> 
#include <stdlib.h> 
const double PI = 3.1415926535897932384626433832795; 

void cos_taper(double *arr_in, double *arr_out, int npts){ 
    int i; 
// double taper[npts]; 
    double* taper = (double*)malloc(sizeof(double) * npts); 
    int M; 
    M = (int)floor(((npts - 2)/10) + .5); 

    for (i=0; i<npts; i++){ 
     if (i<M) { 
      taper[i] = .5 * (1-cos(i * PI/(M + 1))); 
     } 
     else if (i<npts - M - 2) { 
      taper[i] = 1; 
     } 
     else if (i<npts) { 
      taper[i] = .5 * (1-cos((npts - i - 1) * PI/(M + 1))); 
     } 
     arr_out[i] = arr_in[i] * taper[i]; 
    } 
    free(taper); 
    return; 
} 

void doit(){ 
    int i; 
    int npts = 100; 
    double *data, *cos_tapered; 

    data = (double*)malloc(sizeof(double) * npts); 
    cos_tapered = (double*)malloc(sizeof(double) * npts); 

    //fill data 
    for (i = 0; i < npts; i++) data[i] = 1; 

    cos_taper(data, cos_tapered, npts); 
    free(data); 
    free(cos_tapered); 
} 

int main(int argc, char* argv[]){ 
    int i; 
    for (i = 0; i < 1000000; i++){ 
     doit(); 
    } 
    return 0; 
} 

EDIT: Lo conté el código anterior, que tuvo 22 US en mi máquina (sobre todo en malloc). Luego lo modifiqué para hacer los mallocs solo una vez en el exterior. Eso redujo el tiempo a 5.0us, que estaba principalmente en la función cos. Luego cambié de Debug a Release build, que redujo el tiempo a 3.7us (ahora incluso más en la función cos, obviamente). Entonces, si realmente quieres hacerlo rápido, te recomiendo los stackshots para descubrir qué es lo que más haces, y luego ver si puedes evitar hacerlo.