The Computer Language
Benchmarks Game

binary-trees C gcc #3 program

source code

// The Computer Language Benchmarks Game
// Contributed by Jeremy Zerfas
// Based on the C++ program from Jon Harrop, Alex Mizrahi, and Bruno Coutinho.
// *reset*

// This controls the width of lines that are output by this program.

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>

typedef off_t off64_t; // This is needed to keep APR happy on 32 bit systems.
#include <apr_pools.h>

// intptr_t should be the native integer type on most sane systems.
typedef intptr_t intnative_t;

typedef struct tree_node{
   struct tree_node   * left_Node, * right_Node;
} tree_node;

// Create a binary tree of depth tree_Depth in memory_Pool, set the root node's
// value to root_Node_Value, and finally return a pointer to the created binary
// tree.
static inline tree_node * create_Tree(const intnative_t tree_Depth, 
  apr_pool_t * const memory_Pool){
   tree_node * const root_Node=apr_palloc(memory_Pool, sizeof(tree_node));

   // If tree_Depth is one or more then recursively call create_Tree() in order
   // to create the left and right subtrees using 2*root_Node_Value-1 and
   // 2*root_Node_Value respectively as the root values for those subtrees.
      root_Node->left_Node=create_Tree(tree_Depth-1, memory_Pool);
      root_Node->right_Node=create_Tree(tree_Depth-1, memory_Pool);

   return root_Node;

// Compute and return the checksum for the binary tree that has root_Node as the
// root node.
static inline intnative_t compute_Tree_Checksum(
  const tree_node * const root_Node){
   // If there are subtrees then recursively call compute_Tree_Checksum() on
   // them and factor their values into the checksum, otherwise just return
   // the value of root_Node.
      return compute_Tree_Checksum(root_Node->left_Node)+
      return 1;

int main(int argc, char ** argv){
   // Set minimum_Tree_Depth to 4 and maximum_Tree_Depth to the maximum of what
   // was specified as the argument to the program and minimum_Tree_Depth+2.
   const intnative_t minimum_Tree_Depth=4;
   intnative_t maximum_Tree_Depth=atoi(argv[1]);
   if(maximum_Tree_Depth < minimum_Tree_Depth+2)

   apr_pool_t * memory_Pool;

   // Create a memory pool, create a binary tree of depth maximum_Tree_Depth+1,
   // compute the checksum of the binary tree, print the statistics, and then
   // delete the memory pool.
   tree_node * stretch_Tree=create_Tree(maximum_Tree_Depth+1, memory_Pool);
   printf("stretch tree of depth %jd\t check: %jd\n",

   // Create a memory pool and then create a long-lived binary tree of depth
   // maximum_Tree_Depth which will be left alone for a while while
   // more binary trees get allocated and deallocaited as required by the
   // rules. We'll finish working with this later.
   tree_node * long_Lived_Tree=create_Tree(maximum_Tree_Depth, memory_Pool);

   // Create a lot of binary trees in parallel of depths ranging from
   // minimum_Tree_Depth to maximum_Tree_Depth, compute and tally up all their
   // checksums, destroy the trees, and then record the statistics to
   // output_Buffer[] so they can be displayed in order later.
   char output_Buffer[maximum_Tree_Depth+1][MAXIMUM_LINE_WIDTH+1];
   intnative_t current_Tree_Depth;
   #pragma omp parallel for
     current_Tree_Depth<=maximum_Tree_Depth; current_Tree_Depth+=2){
      intnative_t iterations=1<<(maximum_Tree_Depth-current_Tree_Depth+

      // Create a memory pool for this thread to use.
      apr_pool_t * thread_Memory_Pool;

      intnative_t i=1, total_Trees_Checksum=0;
      for(; i<=iterations; ++i){
         // Create a binary tree of depth current_Tree_Depth
         tree_node * const tree_1=create_Tree(current_Tree_Depth,




      // Record the statistics for the trees of depth current_Tree_Depth.
        "%jd\t trees of depth %jd\t check: %jd\n", (intmax_t)iterations,
        (intmax_t)current_Tree_Depth, (intmax_t)total_Trees_Checksum);

   // Print the statistics for all of the various tree depths.
     current_Tree_Depth<=maximum_Tree_Depth; current_Tree_Depth+=2)
      printf("%s", output_Buffer[current_Tree_Depth]);

   // Compute the checksum of the long-lived binary tree that we created
   // earlier, print the statistics, and then delete the memory pool.
   printf("long lived tree of depth %jd\t check: %jd\n",

   return 0;

notes, command-line, and program output

64-bit Ubuntu quad core
gcc (Ubuntu 6.3.0-12ubuntu2) 6.3.0 20170406

Fri, 14 Apr 2017 17:22:32 GMT

/usr/bin/gcc -pipe -Wall -O3 -fomit-frame-pointer -march=native -fopenmp -D_FILE_OFFSET_BITS=64 -I/usr/include/apr-1.0 binarytrees.gcc-3.c -o binarytrees.gcc-3.gcc_run -lapr-1 -lgomp -lm
rm binarytrees.gcc-3.c
0.50s to complete and log all make actions

./binarytrees.gcc-3.gcc_run 21

stretch tree of depth 22	 check: 8388607
2097152	 trees of depth 4	 check: 65011712
524288	 trees of depth 6	 check: 66584576
131072	 trees of depth 8	 check: 66977792
32768	 trees of depth 10	 check: 67076096
8192	 trees of depth 12	 check: 67100672
2048	 trees of depth 14	 check: 67106816
512	 trees of depth 16	 check: 67108352
128	 trees of depth 18	 check: 67108736
32	 trees of depth 20	 check: 67108832
long lived tree of depth 21	 check: 4194303