In this case, how to save data more efficiently and conveniently?-CodePudding

I am measuring the latency of some operations. There are many scenarios here. The delay of each scene is roughly distributed in a small interval. For each scenario, I need to measure 500,000 times. Finally I want to output the delay value and its corresponding number of times.

My initial implementation was:

#define range 1000
int rec_array[range];

for (int i = 0; i < 500000; i  ) {
  int latency = measure_latency();
  rec_array[latency]  ;
}
for (int i = 0; i < range; i  ) {
  printf("%d %d\n", i, rec_array[i]);
}

But this approach was fine at first, but as the number of scenes grew, it became problematic.

The delay measured in each scene is concentrated in a small interval. So for most of the data in the rec_array array is 0.
Since each scene is different, the delay value is also different. Some delays are concentrated around 500, and I need to create an array with a length greater than 500. But some are concentrated around 5000, and I need to create an array with a length greater than 5000.
Due to the large number of scenes, I created too many arrays. For example I have ten scenes and I need to create ten rec_arrays. And I also set them to be different lengths.

Is there any efficient and convenient strategy? Since I am using C language, templates like vector cannot be used.

I considered linked lists. However, considering that the interval of the delay value distribution is uncertain, and how many certain delay values are uncertain, and when the same delay occurs, the timing value needs to be increased. It also doesn't seem very convenient.

CodePudding user response：

how about using a Hash table so we would only save the latency used and maybe the keys in the Hash table can be ranges while the values of said keys be the actual latency?

CodePudding user response：

A linked list is probably (and almost always) the least efficient way to store things – both slow as hell, and memory inefficient, since your values use less storage than your pointers. Linked lists are very rarely a good solution for anything that actually stores significant data. The only reason they're so prevalent is that C still has no proper containers, and they're easy wheels to reinvent for every single C program you write.

#define range 1000
int rec_array[range];

So you're (probably! This depends on your compiler and where you write int rec_array[range];) storing rec_array on the stack, and it's large. (Actually, 4000 Bytes is not "large" by any modern computer's means, but still.) You should not be doing that; instead, this should be heap allocated, once, at initialization.

The solution is to allocate it:

/* SPDX-License-Identifier: LGPL-2.1  */
/* Copyright Marcus Müller and others */

#include <stdlib.h>
#define N_RUNS 500000

/*
 * Call as
 *   program maximum_latency
 */

unsigned int *run_benchmark(struct task_t task, unsigned int *latencies,
                            unsigned int *max_latency) {
  for (unsigned int run = 0; run < N_RUNS;   run) {
    unsigned int latency = measure_latency();
    if (latency >= *max_latency) {
      latency = *max_latency - 1;
      /*
       * alternatively: use realloc to increase the size of the `latencies`,
       * and update max_latency as well; that's basically what C   std::vector
       * does
       */
      (latencies[latency])  ;
    }
  }
  return latencies;
}

int main(int argc, char **argv) {
  // check argument
  if (argc != 2) {
    exit(127);
  }

  int maximum_latency_raw = atoi(argv[1]);
  if (maximum_latency_raw <= 0) {
    exit(126);
  }
  unsigned int maximum_latency = maximum_latency_raw;

  /*
   * note that the length does no longer have to be a constant
   * if you're using calloc/malloc.
   */
  unsigned int *latency_counters =
      (unsigned int *)calloc(maximum_latency, sizeof(unsigned int));

  for (; /* benchmark task in benchmark_tasks */;) {
    run_benchmark(task, latency_counters, &maximum_latency);
    print_benchmark_result(latency_counters, maximum_latency);

    // clear our counters after each run!
    memset(latency_counters, 0, maximum_latency * sizeof(unsigned int));
  }
}

void print_benchmark_result(unsigned int *array, unsigned int length) {
  for (unsigned int index = 0; index < length;   index) {
    printf("%d %d\n", i, rec_array[i]);
  }
  puts("============================\n");
}

Note especially the "alternatively: realloc" comment in the middle: realloc allows you to increase the size of your array:

unsigned int *run_benchmark(struct task_t task, unsigned int *latencies,
                            unsigned int *max_latency) {
  for (unsigned int run = 0; run < N_RUNS;   run) {
    unsigned int latency = measure_latency();
    if (latency >= *max_latency) {
      // double the size!
      latencies = (unsigned int *)realloc(latencies, (*max_latency) * 2 *
                                                         sizeof(unsigned int));

      // realloc doesn't zero out the extension, so we need to do that
      // ourselves.

      memset(latencies    (*max_latency), 0, (*max_latency)*sizeof(unsigned int);
      (*max_latency) *= 2;
      (latencies[latency])  ;
    }
  }
  return latencies;
}

This way, your array grows when you need it to!