50-Percent Rule

Question

I am writing a program that tests dynamic memory allocation to see how well the 50-percent rule holds.

The program has 10,000 pointers to dynamically allocated blocks of memory. It also has an array to store the size of each block. It should:

1. Use malloc() to dynamically allocated a block of memory for every element of ptrList. These blocks should have sizes that are selected randomly in the range of 1 to 10,000 bytes and the block size should be stored in the sizeList array.
2. After initial block allocation, the program should repeatedly free blocks and allocate new ones. This should loop for 100,000 iterations. On each iteration, an index in ptrList is chosen at random, the block is freed, and then replaced with a new dynamically allocated block with random size.
3. After every 100 iterations, it should print out a line that shows the iteration count, the approximate heap size (determined by the difference between the highest and lowest memory addresses contained in any of the blocks), and the total size of all blocks pointed to by ptrList.

I have my program coded like so:

#include <stdio.h>
#include <pthread.h>   /* for pthreads */
#include <stdlib.h>    /* for exit */

/** Number of memory blocks to allocate/deallocate. */
#define BLOCK_COUNT 10000

/** Number of free/malloc operations to perform */
#define TEST_LENGTH 100000

/** Maximum size of an allocated block. */
#define SIZE_LIMIT 10000

int main( int argc, char *argv[] ) {
  // Array of pointers to all blocks that have been allocated.
  char *ptrList[ BLOCK_COUNT ];

  // Array of sizes for each block, so we can know how much memory we're using.
  int sizeList[ BLOCK_COUNT ];

  // Insert your code here
  for (int j = 0; j < 1000; j++) {

      int minimum = 0;
      int maximum = 0;
      int total = 0, remainder = 0;

      for (int i = 0; i < BLOCK_COUNT; i++) {
          int size = (rand() % SIZE_LIMIT) + 1;
          ptrList[i] = malloc (size);
          sizeList[i] = size;
          total += size;
          int heapsize = (int)ptrList[i];

          if (i == 0) {
              maximum = heapsize;
              minimum = heapsize;
          }
          else {
              if (heapsize > maximum) {
                  maximum = heapsize;
              }
              if (heapsize < minimum) {
                  minimum = heapsize;
              }
          }
      }

      for (int i = 0; i < TEST_LENGTH; i++) {
          int index = rand() % BLOCK_COUNT;
          int size = (rand() % SIZE_LIMIT) + 1;
          free(ptrList[index]);
          total -= sizeList[index];
          ptrList[index] = malloc (size);
          sizeList[index] = size;
          total += sizeList[index];
          int heapsize = (int)ptrList[index];

          if (heapsize > maximum) {
              maximum = heapsize;
          }
          if (heapsize < minimum) {
              minimum = heapsize;
          }
      }

      if (j > 0) {
          remainder = j % 100;
      }

      if (remainder == 0 ) {
          //printf("%d", example);
          printf("%d %d %d\n", j, maximum - minimum, total);
      }

      for (int i = 0; i < BLOCK_COUNT; i++) {
          free(ptrList[i]);
      }

  }

  return 0;
}

Am I approaching the allocation/deallocation of memory the right way? My program compiles and runs (without output) before I implemented the for loop with int j. It hangs after I implemented it, so perhaps someone can help me pin the problem there as well.

Edit: The 50-percent rule is the total size of all blocks divided by the approximation of the heap size will generally be around 50 percent.

Answer 1

Besides cruft (egregiously unnecessary code) you've got some problems with variables and loops: Your for (int i = 0; i < TEST_LENGTH; i++)... loop, which implements step 2 of the spec, is the loop within which, every 100 steps, you should print current stats. Having an outer for (int j = 0; j < 1000; j++) loop and testing j%100 remainders is nonsense.

For debugging a problem like that, knock two or three zeroes off each of the big numbers BLOCK_COUNT, TEST_LENGTH, SIZE_LIMIT, change the j loop limit to 10, and add a printf("j=..." ...) after for (int j ...) { so you can tell what's happening. With such changes, you will see:

  j=0 0 0
  0 556736 507760
  j=1 0 0
  j=2 0 0
  j=3 0 0
  ...

and then can conclude that your program seemed to hang because it was slowly counting j up to 100 to get to j%100 == 0.

Now I'll mention two minor cruft items to remove, and after that will mention a major problem with your program.

Instead of

  int minimum = 0;
  int maximum = 0;
  ...
     if (i == 0) {
        maximum = heapsize;
        minimum = heapsize;
     }
     else {
       if (heapsize > maximum) {
          maximum = heapsize;
     }
     if (heapsize < minimum) {
          minimum = heapsize;
     }

write

  int minimum = MAX_INT;
  int maximum = 0;
  ...
     if (heapsize > maximum)
        maximum = heapsize;
     if (heapsize < minimum)
        minimum = heapsize;

(or possibly a variant of MAX_INT) and (if you needed j and/or remainder, which you don't) instead of

  if (j > 0) {
      remainder = j % 100;
  }

  if (remainder == 0 ) {
     ...

you would write

  if (j>0 && j%100 == 0 ) {
     ...

A major problem with your program: When you say free(ptrList[index]); in part 2, you might be freeing the item that accounted for the current minimum or maximum memory addresses. One way to solve this problem is maintain priority queues with min/max values and fifo discipline too; what you will find simpler, I think, is to not track min/max while allocating, but instead just have a loop to find min/max right before each printout.

A minor problem with your program: The maximum address used is not ptrList[index] for some index, but ptrList[index]+sizeList[index].