4
\$\begingroup\$

I had some multithreading C programming experience from school last year but I wanted a bit more so I tried to program a Conway's Game of Life implementation from scratch.

Code is mainly written in C but is invoked via a JNI call from the GameOfLifeMultithread.java class. The java code is also responsible for maintaining a "lookup-table" which the native code uses for performance reasons.

The primary goal of this code was to run as fast as possible, which made the code a bit complicated and clarity suffered. As best as I can tell there are no bugs but I'm trying to learn C (and to a lesser extent Java) documentation and code style rules so I'd really appreciate advice on how to refactor in that respect.

In particular, I don't have a great grasp of initializing and deinitializing resource patterns. My code uses a bunch of mallocs, and I'm struggling on how best to handle partial failures.

The entry point for the code is GameOfLifeMultithread#getNGeneration(int n) which runs for n generations mutating the board and returning the changes.

The native C entry point is Java_game_1of_1life_GameOfLifeMultithread_getNGenerationNative (sorry, I don't get to name the methods)

Steps for the native code are:

  1. Initialize native game boards and dirty bit boards copying from the Java array to the native array: initialize_all_resources(), initialize_lookup_table(), initialize_dirty_bits()
  2. Split code into threads do_all_thread_work(), thread_do_work()
  3. Have each thread run n generations synching at the end of generation using synch_thread()
  4. Copy the native array back to the Java array and freeing all resources free_all_resources()

In each generation (i.e. step 3):

  1. Check if its value or adjacent values were changed in the previous gen by consulting the dirty_bit board, if they weren't, skip this gen
  2. Use the lookup table to calculate the new value
  3. If the new value is different set the dirty bits on the board

All this is done in one method: perform_single_line()

Here is my Java code:

package game_of_life;

public class GameOfLifeMultithread {
    static {
        System.loadLibrary("binary/" + "native_multithread");
    }
    /*-
     * Indexing will look like this (P is padding, C is center:                 
     *      PPPPPP
     *      PCCCCP
     *      PPPPPP
     *  However, when indexing these values will be concatenated giving the following 
     *  bit string:
     *      PPPPPPPCCCCPPPPPPP
     */

    // Size of the value returned by a lookup
    public static final int LOOKUP_LEN = 4;
    // The row length should be the lookup length +2 for padding on either side
    public static final int ROW_LEN = LOOKUP_LEN + 2;
    // Additionally, pad the top and bottom
    public static final int TOTAL_LOOKUP_SIZE = ROW_LEN * 3;

    public static final int threadcount = 8;
    private final static String name = "Multithreaded Technique";
    private final static String description = "Uses a lookuptable and dirty bits with multithreading";
    private static byte[] lookuptable;

    private final boolean[][] board;

    public GameOfLifeMultithread(boolean[][] board) {
        this.board = board;
    }

    public boolean[][] getNGeneration(int n) {
        if (lookuptable == null) {
            lookuptable = generateLookup();
        }
        getNGenerationNative(threadcount, lookuptable, n, this.board);
        return this.board;
    }

    private native void getNGenerationNative(int threadcount, byte[] lookuptable, int n, boolean[][] array);

    private static byte[] generateLookup() {
        byte[] lookup = new byte[1 << (TOTAL_LOOKUP_SIZE)];
        // Adjacency count for center cells, give +2 padding, 1 for each side, not
        // because we need it, but to simplify indexing the array and avoid checking for
        // under/over-flow
        byte[] count = new byte[ROW_LEN + 2];
        // Skip 0 because this doesn't work through underflow
        // An all 0 bitfield should return 0 either way, so no special logic is needed
        for (int i = 1; i < lookup.length; i++) {
            // Track changes between the current bit-field and the previous one
            int change = i ^ (i - 1);
            for (int j = 0; j < TOTAL_LOOKUP_SIZE; j++) {
                // Check if a given position was changed between this one and the last
                if ((change & (1 << j)) != 0) {
                    // If it was changed, add 1 to all adjacent if it was "born" or -1 if it "died"
                    int delta = ((i & (1 << j)) != 0) ? 1 : -1;
                    count[(j) % ROW_LEN] += delta;
                    // In GOL, you don't count the cell itself in the live count, so if we're in the
                    // center row, don't increment the current cell's count, only the adjacent cells
                    if (j < ROW_LEN || j > TOTAL_LOOKUP_SIZE - ROW_LEN) {
                        count[(j + 1) % ROW_LEN] += delta;
                    }
                    count[(j + 2) % ROW_LEN] += delta;
                }
            }
            byte result = 0;
            for (int j = LOOKUP_LEN; j > 0; j--) {
                result <<= 1;
                // Because we gave count array padding, we need to +1 to get the actual value
                if (count[j + 1] == 3 || (count[j + 1] == 2 && (i & (1 << (j + ROW_LEN))) != 0)) {
                    result++;
                }
            }
            lookup[i] = result;
        }
        return lookup;
    }

    public boolean[][] getBoard() {
        return this.board;
    }
}

Header file (automatically created by Java):

/* DO NOT EDIT THIS FILE - it is machine generated */
#include <jni.h>
/* Header for class game_of_life_GameOfLifeMultithread */

#ifndef _Included_game_of_life_GameOfLifeMultithread
#define _Included_game_of_life_GameOfLifeMultithread
#ifdef __cplusplus
extern "C" {
#endif
#undef game_of_life_GameOfLifeMultithread_threadcount
#define game_of_life_GameOfLifeMultithread_threadcount 8L
/*
 * Class:     game_of_life_GameOfLifeMultithread
 * Method:    getNGenerationNative
 * Signature: (I[BI[[Z)V
 */
JNIEXPORT void JNICALL Java_game_1of_1life_GameOfLifeMultithread_getNGenerationNative
  (JNIEnv *, jobject, jint, jbyteArray, jint, jobjectArray);

#ifdef __cplusplus
}
#endif
#endif

C code (did my best to document the technique used, but I'm not sure about the details):

/**
 * @brief
 * JNI implementation for a hyper-optimized Conway's Game of Life
 * 
 * @author Shmuel Newmark <https://github.com/synewmark>
 * Except barrier_wait() which was taken from User Tsyvarev on StackOveflow: 
 * https://stackoverflow.com/questions/33598686/spinning-thread-barrier-using-atomic-builtins
 * 
 * @details
 * Code packs 8 booleans into a single char value (@see pack_8(), and unpack_8() methods)
 * 
 * For example a boolean array like this:
 * [0] [1] [2] [3] [4] [5] [6] [7] [8] ... 
 * ..0 ..0 ..1 ..0 ..1 ..0 ..1 ..1 ..1 ...
 * Will turn into:
 *   [0]        [1]
 * 00101011  1.......
 * 
 * #IMPORTANT# Throughout code, "leftmost" bit is the highest bit and "rightmost" is lowest
 * However, the lowest value on the array is left and highest is right
 * Because numerical values are usually read most sig to least, this simplifies
 * the intuition when it comes to merging values but must be kept consistent
 * 
 * Code uses a parallel "dirty bit" array of the same size as the board to track changes
 * If the board is unchanged for a generation the corresponding value in the dirty bit array is cleared 
 * If a cell is changed all adjacent cells' dirty bits are set allowing changes to propogate
 * Note: because we pack cells each char cell (i.e. 8 normal cells) share a dirty bit value
 * 
 * Code uses a "lookup table" to calculate values
 * Lookup is done 18 bits at a time as a 6x3.
 * Because we're storing values packed in 8 bits this requires 2 lookups
 * For example suppose the following section of a life board:
 * ... ........ ...
 * ..0 00101011 1..
 * ..1 10100101 1..
 * ..1 01010010 0..
 * ... ........ ...
 * If we wanted to lookup the value of the middle row we'd need to follow 2 steps
 * Step 1. split the row in half and attach the adjacent values on either side
 * For the left value that would look like:
 * 1 10100
 * But we also need to the row on top and bottom so,
 * 0 00101
 * 1 10100
 * 1 01010
 * Step 2. we'd need to combine those into a single bit string: 000101110100101010
 * Same deal for the right:
 * 01011 1
 * 00101 1
 * 10010 0
 * As a string: 010111001011100100
 * We'll use the int value of both of these bit strings as indices on our lookup table
 * 
 * Code favors speed over clarity for all innermost loop functions:
 * @see get_integral_val_left(), get_integral_val_right(), perform_single_line(), thread_do_work()
 */

#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include "game_of_life_GameOfLifeMultithread.h"

#define is_alive(char, pos) ((1 << (pos)) & (char))
#define set_alive(char, pos) (char |= (1 << (pos)))
// Don't use mod for wrapping because division is too expensive
#define get_low(n, len) (n-1 >= 0 ? n-1 : len-1)
#define get_high(n, len) (n+1 < len ? n+1 : 0)
// Step 1 for left: get the 5 left bits and the rightmost bit on the one to the left
#define get_integral_row_left(left, center) (((left & 1) << 5)) | (center >> 3)
// Step 1 for right: get the 5 right bits and the leftmost bit on the one to the right
#define get_integral_row_right(center, right) (((center & 0x1F) << 1) | (right & (1 << 7)) >> 7)
#define swap_board(x, y) ({unsigned char** _temp = x; x = y; y =_temp;})


jbyte* lookuptable = NULL;
unsigned char** board1 = NULL;
unsigned char** board2 = NULL;
unsigned char** dirty_bit1 = NULL;
unsigned char** dirty_bit2 = NULL;


int xlen;
int ylen;
int ylenpacked;

int global_thread_count = 8;

struct thread_work{
    int genlength;
    int start;
    int end;
};

static void barrier_wait();

static void* safe_calloc(size_t NumOfElements, size_t SizeOfElements) {
  // malloc family can return NULL for 0 allocs
  // Want to distinguish between a failure and a "succesful" 0 allocation
  if (!NumOfElements || !SizeOfElements) {
    return NULL;
  }
  errno = 0;
  void* result = calloc(NumOfElements, SizeOfElements);
  if (!result) {
    printf("Calloc of size %lld failed with code: %d\n", NumOfElements*SizeOfElements, errno);
  }
  return result;
}

static void free2d(int x, unsigned char** array) {
  if (!array) {
    return;
  }
  for (int i = 0; i < x; i++) {
    if (!array[i]) {
      return;
    }
    free(array[i]);
  }
  free(array);
}

static unsigned char** malloc2d(int x, int y) {
  unsigned char** board = safe_calloc(x, sizeof(*board));
  if (!board) {
    return NULL;
  }
  for (int i = 0; i < x; i++) {
    if (!(board[i] = safe_calloc(y, sizeof(*board[i])))) {
      free2d(x, board);
      return NULL;
    }
  }
  return board;
}

static int set_length_values(JNIEnv * env, jobjectArray array, int* xlen_store, int* ylen_store, int* ylenpacked_store) {
  // Caller ensures the array is not of 0 length and is a square 
  // so we just need the x and any y lengths
  int xlen = (*env)->GetArrayLength(env, array);
  jobjectArray dim1 = (*env)->GetObjectArrayElement(env, array, 0);
  int ylen = (*env)->GetArrayLength(env, dim1);
  if (ylen % 8) {
    return -1;
  }
  *xlen_store = xlen;
  *ylen_store = ylen;
  *ylenpacked_store = ylen/8;
  return 0;
}

static int pack_8(JNIEnv * env, jobjectArray array, unsigned char** board) {
  for (int i = 0; i < xlen; i++) {
      jbooleanArray boolArrayi = (*env)->GetObjectArrayElement(env, array, i);
      jboolean isCopy = JNI_FALSE;
      //entering critical
      jboolean* boolElementsi = (*env)->GetPrimitiveArrayCritical(env, boolArrayi, &isCopy);
      if (isCopy) {
          return -1;
      }
      //pack 8 boolean values into each char
      for (int j = 0; j < ylenpacked; j++) {
        unsigned char c = 0;
        // This places the lowest bit as the most significant
        // @see @details
        for (int k = 0; k < 8; k++) {
          c<<=1;
          c+=(boolElementsi[j*8+k]);
        }
        board[i][j] = c;
      }
    (*env)->ReleasePrimitiveArrayCritical(env, boolArrayi, boolElementsi, 0);
    //exiting critical
  }
  return 0;
}

static void unpack_8(JNIEnv* env, jobjectArray array, unsigned char** board){
  for (int i = 0; i < xlen; i++) {
      jbooleanArray boolArrayi = (*env)->GetObjectArrayElement(env, array, i);
      jboolean* boolElementsi = (*env)->GetPrimitiveArrayCritical(env, boolArrayi, 0);
      for (int j = 0; j < ylenpacked; j++) {
        for (int k = 0; k < 8; k++) {
          // We cannot simply mask and place back into the array because Java only reliably treats values with the lowest bit set as true
          boolElementsi[j*8+(7-k)] = is_alive(board[i][j], k) ? JNI_TRUE : JNI_FALSE;
          // We want to put the value in k-7 because we reversed the bits when packing
          // So we need to un-reverse the bits when unpacking
          // @see @details
        }
      }
      (*env)->ReleasePrimitiveArrayCritical(env, boolArrayi, boolElementsi, 0);
    }
}

// Very performance sensitive: Runs g*x*(y/8) times
static inline unsigned int get_integral_val_left(unsigned int nw, unsigned int n, unsigned int w, unsigned int c, unsigned int sw, unsigned int s) {
    unsigned int top = get_integral_row_left(nw, n);
    unsigned int mid = get_integral_row_left(w, c);
    unsigned int bot = get_integral_row_left(sw, s);
    // Step 2: combine all 3 rows into a single bit string
    return ((top << 12) | (mid << 6) | bot);
}
// Very performance sensitive: Runs g*x*(y/8) times
static inline unsigned int get_integral_val_right(unsigned int n, unsigned int ne, unsigned int c, unsigned int e, unsigned int s, unsigned int se) {
    unsigned int top = get_integral_row_right(n, ne);
    unsigned int mid = get_integral_row_right(c, e);
    unsigned int bot = get_integral_row_right(s, se);
    // Step 2: combine all 3 rows into a single bit string
    return ((top << 12) | (mid << 6) | bot);
}
// Very performance sensitive: runs g*x times
static inline void perform_single_line(int xpos, unsigned char** board1, unsigned char** board2, unsigned char** dirty_bit1, unsigned char** dirty_bit2) {
  // inner loop runs: runs g*x*y times
  for (int i = 0; i < ylenpacked; i++) {
        // If dirty bit is clear we don't run
        if(!dirty_bit1[xpos][i]) {
          continue;
        }
        // Watch for over and underflow when wrapping
        int up = get_low(xpos, xlen);
        int down = get_high(xpos, xlen);
        int left = get_low(i, ylenpacked);
        int right = get_high(i, ylenpacked);
        // Split the lookup into 2 request: left and right
        // Each request is 18 bits, or 6 for each row
        unsigned int lookupvalleft = get_integral_val_left(board1[up][left], board1[up][i], board1[xpos][left], board1[xpos][i], board1[down][left], board1[down][i]);
        unsigned char newvalleft = lookuptable[lookupvalleft];
        
        unsigned int lookupvalright = get_integral_val_right(board1[up][i], board1[up][right], board1[xpos][i], board1[xpos][right], board1[down][i], board1[down][right]);
        unsigned char newvalright = lookuptable[lookupvalright];

        unsigned char newval = (newvalleft << 4) | newvalright;
        char xc = newval^board1[xpos][i];
        
        // Set all dirty bits around the just changed value
        // Even though we may have a race condition on access it's safe 
        // because char access is atomic and we're only ever setting them, never clearing

        if (xc) {
          // If there's any difference between the curr and prev value we must set the dirty on the ones above and below
          dirty_bit2[down][i] = 1;
          dirty_bit2[xpos][i] = 1;
          dirty_bit2[up][i] = 1;
          // But we only need to set the left and right dirty values if the left and right-most values were changed
          if (is_alive(xc, 0)) {
            dirty_bit2[down][right] = 1;
            dirty_bit2[xpos][right] = 1;
            dirty_bit2[up][right] = 1;
          }

          if (is_alive(xc, 7)) {
            dirty_bit2[down][left] = 1;
            dirty_bit2[xpos][left] = 1;
            dirty_bit2[up][left] = 1;
          }
        }
        // Note: we need to set the next board to this value regardless of whether it was changed on *this* iteration
        // However, if the dirty bit was not set and it wasn't changed on the *prev* iteration it will already be the correct val
        board2[xpos][i] = newval;
      }
}

void* thread_do_work(void* threadwork) {
  struct thread_work* work = (struct thread_work*) threadwork;
  unsigned char** cache_board1 = board1;
  unsigned char** cache_board2 = board2;
  unsigned char** cache_dirtybit1 = dirty_bit1;
  unsigned char** cache_dirtybit2 = dirty_bit2;
  // Somewhat performace sensitive: each barrier_wait runs g times
  for (int i = 0; i < work->genlength; i++) {
    for (int j = work->start; j < work->end; j++) {
        perform_single_line(j, cache_board1, cache_board2, cache_dirtybit1, cache_dirtybit2);
    }
    barrier_wait();
    swap_board(cache_board1, cache_board2);
    swap_board(cache_dirtybit1, cache_dirtybit2);
    for (int j = work->start; j < work->end; j++) {
      // clear all dirty bits after reading them
      // The big drawback of the approach is that it requires 2 barrier waits
      // Otherwise we risk clearing the bits while another thread is reading them
      memset(cache_dirtybit2[j], 0, ylenpacked);
    }
    barrier_wait();
  }
  return NULL;
}

static int initialize_boards(JNIEnv* env, jobjectArray array) {
  board1 = malloc2d(xlen, ylenpacked);
  if (!board1) {        
    printf("Indeterminate error, terminating\n");
    return -1;
  }
  if (pack_8(env, array, board1)) {
    printf("Indeterminate error, terminating\n");
    return -1;
  }
  board2 = malloc2d(xlen, ylenpacked);
  if (!board2) {
    printf("Indeterminate error, terminating\n"); 
    return -1;
  }
  return 0;
}

static int initialize_dirty_bits(int xlen, int ylenpacked) {
  dirty_bit1 = malloc2d(xlen, ylenpacked);
  if (!dirty_bit1) {
    return -1;
  }
  // turn on all dirty bits on the first run so nothing gets skipped
  for (int i = 0; i < xlen; i++) {
    memset(dirty_bit1[i], 0xFF, ylenpacked);
  }

  dirty_bit2 = malloc2d(xlen, ylenpacked);
  if (!dirty_bit2) {
    return -1;
  }
  return 0;
}

static void initialize_lookup_table(JNIEnv* env, jarray array) {
  lookuptable = (*env)->GetPrimitiveArrayCritical(env, array, NULL);
}

static void free_all_resources() {
  free2d(xlen, board1);
  free2d(xlen, board2);
  free2d(xlen, dirty_bit1);
  free2d(xlen, dirty_bit2);
}

static int do_all_thread_work(int threadcount, int runlength) {
  // Each thread works on it's own x range, no reason to make more threads than xlen
  global_thread_count = xlen < threadcount ? xlen : threadcount;
  struct thread_work workpool[global_thread_count];
  int startwork = 0;
  for (int i = 0; i < global_thread_count-1; i++) {
    // If the x value is not divisble by 8 
    int amountofwork = (xlen/global_thread_count) + ((xlen%global_thread_count) > i);
    workpool[i] = (struct thread_work) {runlength, startwork, startwork+amountofwork};
    // The possibility of some threads being created succesfully, but choking on the rest is unhandled
    int error;
    if ((error = (pthread_create(NULL, 0, thread_do_work, workpool+i)))) {
      printf("Creating thread: %d failed with code: %d\n", i+1, error);
      return -1;
    }
    startwork+=amountofwork;
  }
  int amountofwork = (xlen/global_thread_count);
  struct thread_work finalwork = (struct thread_work) {runlength, startwork, startwork+amountofwork};
  thread_do_work(&finalwork);
  return 0;
}

static int initialize_all_resources(JNIEnv* env, jint threadcount, jbyteArray lookup, jint runlength, jobjectArray array) {
  if (set_length_values(env, array, &xlen, &ylen, &ylenpacked)) {
    printf("Array must have a y size divisable by 8\n");
    return -1;
  }
  if (initialize_boards(env, array)) {
    return -1;
  }
  if (initialize_dirty_bits(xlen, ylenpacked)) {
    return -1;
  }
  initialize_lookup_table(env, lookup);
  do_all_thread_work(threadcount, runlength);
  return 0;
}

JNIEXPORT void JNICALL Java_game_1of_1life_GameOfLifeMultithread_getNGenerationNative
  (JNIEnv* env, jobject object, jint threadcount, jbyteArray lookup, jint runlength, jobjectArray array) {
  printf("Running for %d generations!\n", runlength);
  if (!initialize_all_resources(env, threadcount, lookup, runlength, array)) {
    unsigned char** finalboard = runlength % 2 ? board2 : board1;  
    unpack_8(env, array, finalboard);
  }
  free_all_resources();
}

// Barrier code is taken from User Tsyvarev: 
// https://stackoverflow.com/questions/33598686/spinning-thread-barrier-using-atomic-builtins

// Because we're saturating the cores and denying multitasking, there's no reason to sleep on waits
// So we're busy-waiting instead to squeeze out a bit more performance

int bar = 0; // Counter of threads, faced barrier.
volatile int passed = 0; // Number of barriers, passed by all threads.

// Due to __sync primitives, code is GCC/Clang dependant
static void barrier_wait()
{
    int passed_old = passed; // Should be evaluated before incrementing *bar*!

    if(__sync_fetch_and_add(&bar,1) == (global_thread_count - 1))
    {
        // The last thread, faced barrier.
        bar = 0;
        // *bar* should be reseted strictly before updating of barriers counter.
        __sync_synchronize(); 
        passed++; // Mark barrier as passed.
        // return 1;
    }
    else
    {
        // Not the last thread. Wait others.
        while(passed == passed_old) {};
        // Need to synchronize cache with other threads, passed barrier.
        __sync_synchronize();
        // return 0;
    }
}

As indicated in the comments my code is non-portable because it relies on GCC/Clang primitives for the barrier. If anyone has any advice on how to implement in a portable fashion that would be appreciated.

Mainly though, I'd love advice on how to simplify steps 1, 2, and 4 even at cost of performance because they only run once.

Additionally, any advice on how to simplify step 3 without costing too much performance would be appreciated.

Also, as mentioned above, advice on how to handle failed nested malloc calls or thread creation failing partially through.

\$\endgroup\$
2
  • 3
    \$\begingroup\$ Don't use mod for wrapping because division is too expensive. ====> Don't do the compiler's job. \$\endgroup\$
    – Harith
    Mar 27 at 21:02
  • \$\begingroup\$ @Haris Thanks! Is there a better way to do that? Mod doesn't have the same semantics as the macro in the case where n>len*2. So I don't think the compiler can do it on its own. But is fine for my use-case where over/underflow can only be by 1. \$\endgroup\$ Mar 27 at 21:12

2 Answers 2

4
\$\begingroup\$

safe_calloc() weaknesses

  • errno = 0; best left for calling code.

  • calloc() does not certainly set errno on allocation failure. So using errno to signify something is not portable here.

  • NumOfElements*SizeOfElements may overflow size_t math. If wanting unsigned long long math, use (unsigned long long) NumOfElements*SizeOfElements or the like. IAC, the multiplication is not really needed since if allocation failed, debugging would want to know the exact values passed to calloc(), not a derived value.

  • NumOfElements*SizeOfElements has size_t product. That does not match "%lld".

  • "succesful" spelling error. Run spell checker on code.

  • Style issue: I find comparing with == clearer than !. Avoid negations: I don't know half of you half as well as I should like; and I like less than half of you half as well as you deserve.

  • Write error messages on stderr.

Candidate re-write:

static void* calloc_log(size_t NumOfElements, size_t SizeOfElements) {
  if (NumOfElements == 0 || SizeOfElements == 0) {
    return NULL;
    // Or adjust parameters so a return value of NULL is always an error.
    NumOfElements = SizeOfElements = 1; 
  }
  void* result = calloc(NumOfElements, SizeOfElements);
  if (result == NULL) {
    fprintf(stderr, "calloc(%zu, %zu) failed.\n", NumOfElements, SizeOfElements);
  }
  return result;
}

The usage of safe_calloc() is amiss too as code ignores negative x issues and quietly changes such a value to a large unsigned value that may successfully allocate.

static unsigned char** malloc2d(int x, int y) {
  unsigned char** board = safe_calloc(x, sizeof(*board));  // Weak code

Consider using size_t or unsigned x, y or test for negative values.

\$\endgroup\$
2
\$\begingroup\$

Style:

The convention is to use snake-case in C. When in Rome, do as the Romans do.

I find some variable names overly verbose. NumOfElements is better as nelems. SizeOfElements is better as just size. But perhaps that's just personal preference.

Most people prefer to call abort() if malloc() and family returns NULL.

/* Don't write diatribes. */
void *xmalloc (size_t sz) 
{
    void *p = malloc (sz);
    
    if (!p) {
       /* Log an error here. Even fprintf(3) may not succeed. */
       abort ();
    }
    return p;
}

Though, I find the above method lazy.

Unnecessary resetting of errno:

There's no need to set errno to 0 before calling a library function. We can be sure it will be set on failure as documented. calloc() doesn't normally shy away from setting it if it's already non-zero. But then we don't even check whether errno was changed, so I don't see the point. Where it might be useful to set errno to 0 before calling a function is when one is documented to may set errno on failure, as is the case with sysconf(), strtol(), setvbuf(), etc. and check whether errno was set before calling perror() / strerror().

Error messages go to stderr, not stdout:

// printf("Calloc of size %lld failed with code: %d\n", NumOfElements*SizeOfElements, errno);


fprintf (stderr, "calloc() of size %lld failed: %s\n", strerror (errno));

You may use perror() / strerror() to convert an errno code to a human-readable string.

The correct format specifier for size_t is %zu:

Mismatching types and format specifiers lead to undefined behaviour:

From the C standard:

If any argument is not the correct type for the corresponding conversion specification, the behavior is undefined.

inline functions are short and concise:

inline functions don't normally span over 28 lines. Rather leave it to the compiler, it knows what to inline.

Undocumented return values:

The functions have not been documented. What does a return value of 0 mean? Is it following the POSIX convention to return 0 on success and -1 otherwise? Or is it following C's semantics that 0 is false and all else is true?

There's a bool type that you can use. Though, you'd have to include stdbool.h for it.

Use unsigned types for sizes, cardinalities, and ordinal numbers:

Array and loop indexes should be size_t — which is an unsigned integer type — not int.

Use const and restrict:

restrict allows for select compiler optimizations because it can assume the pointers do not overlap.

//static int set_length_values(JNIEnv * env, jobjectArray array, int* xlen_store, int* ylen_store, int* ylenpacked_store) {
  
static int set_length_values(JNIEnv *restrict env, jobjectArray array, int *restrict xlen_store, int *restrict ylen_store, int *restrict ylenpacked_store) {

The parameters that are not changed anywhere in the function should be const-qualified.

Variables that do not change should be declared with the const-qualifier.

Avoid prefixing identifiers with the an underscore:

Identifiers beginning with an underscore are reserved by the ISO C standard.

Minor:

Simplify:

#if 0
if (initialize_boards(env, array)) {
    return -1;
  }
  if (initialize_dirty_bits(xlen, ylenpacked)) {
    return -1;
#endif

if (initialize_boards(env, array) 
    || initialize_dirty_bits(xlen, ylenpacked)) {
    return -1;
}
  

Don't substitute functions for macros. Write static inline functions whenever possible. swap_board and others should be functions.


While the modulo operation is indeed expensive, it's a very basic optimization that the compiler would be able to perform. Focus on readability.


Did gcc/clang with -O3 not live upto your expectations?

\$\endgroup\$
7
  • \$\begingroup\$ Appreciate the help. safe_calloc is just poorly named, it should really be calloc_with_logging. I just want it log any errors and return null on failures. I can't have it immediately terminate because I need to free any prev successful mallocs before returning to the caller. I see your points regarding error handling though. I was trying to follow POSIX convention, but I need to document better. I'll switch it to a boolean return val and make your suggested changes to error logging. Likewise for variable names and macro usage. \$\endgroup\$ Mar 28 at 2:12
  • \$\begingroup\$ I take your point regarding inline as well. As best as I can tell it's just a compiler hint, but there's no reason for it on perform_single_line. Thanks again. \$\endgroup\$ Mar 28 at 2:14
  • 1
    \$\begingroup\$ About inline it is basically a recommendation that an optimizing compiler ignores, but in rare cases where the code can't be optimized such as embedded programming it becomes important, that said anything that doesn't fit in the cache memory can't be inlined. \$\endgroup\$
    – pacmaninbw
    Mar 28 at 14:27
  • 1
    \$\begingroup\$ "Most people prefer to call abort() if malloc() and family returns NULL." --> no. \$\endgroup\$ Apr 25 at 16:28
  • \$\begingroup\$ "calloc() of size %ll failed: %s\n" looks like a typo without the d. \$\endgroup\$ Apr 25 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.