title: 50-Percent Rule
body: <p>I am writing a program that tests dynamic memory allocation to see how well the 50-percent rule holds.</p>
  
  <p>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:  </p>
  
  <ol>
  <li>Use <code>malloc()</code> to dynamically allocated a block of memory for every element of <code>ptrList</code>. 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 <code>sizeList</code> array.</li>
  <li>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 <code>ptrList</code> is chosen at random, the block is freed, and then replaced with a new dynamically allocated block with random size.</li>
  <li>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 <code>ptrList</code>.</li>
  </ol>
  
  <p>I have my program coded like so:</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;pthread.h&gt;   /* for pthreads */
  #include &lt;stdlib.h&gt;    /* 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 &lt; 1000; j++) {
  
        int minimum = 0;
        int maximum = 0;
        int total = 0, remainder = 0;
  
        for (int i = 0; i &lt; 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 &gt; maximum) {
                    maximum = heapsize;
                }
                if (heapsize &lt; minimum) {
                    minimum = heapsize;
                }
            }
        }
  
        for (int i = 0; i &lt; 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 &gt; maximum) {
                maximum = heapsize;
            }
            if (heapsize &lt; minimum) {
                minimum = heapsize;
            }
        }
  
        if (j &gt; 0) {
            remainder = j % 100;
        }
  
        if (remainder == 0 ) {
            //printf("%d", example);
            printf("%d %d %d\n", j, maximum - minimum, total);
        }
  
        for (int i = 0; i &lt; BLOCK_COUNT; i++) {
            free(ptrList[i]);
        }
  
    }
  
    return 0;
  }
  </code></pre>
  
  <p>Am I approaching the allocation/deallocation of memory the right way? My program compiles and runs (without output) before I implemented the <code>for</code> loop with <code>int j</code>. It hangs after I implemented it, so perhaps someone can help me pin the problem there as well.</p>
  
  <p><strong>Edit:</strong> 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.</p>