Linked List Tests

linked_list.c

#include <stdio.h>
#include <microtime.h>
#include <string.h>
#include <stdlib.h>

struct ll_t {
  float value;
  struct ll_t *next;
};

int main(int argc, char **argv)
{
  int i, ll_size = 20000000;
  struct ll_t *ll, *curr;
  double time1, time2;

  /* create a linked list with test data */
  ll = malloc(sizeof(struct ll_t));
  curr = ll;
  for (i = 0; i < ll_size; ++i) {
    curr->value = i * 10.0f;
    if (i == ll_size - 1) {
      /* Set the last value of the linked list to 0 so we know where the end is */
      curr->next = 0;
    } else {
      curr->next = malloc(sizeof(struct ll_t));
      curr = curr->next;
    }
  }

  /* some operation: square the value */
  time1 = microtime();
  for (curr = ll; curr->next != 0; curr = curr->next) {
     curr->value = curr->value * curr->value;
  }
  time2 = microtime();
  printf("Time = %g us\tTimer Resolution = %g us\tPerformance = %g Gflop/s\n", time2-time1, get_microtime_resolution(), ll_size*1e-3/(time2-time1));

  /* cleanup */
  // TODO

  return 0;
}

linked_list_sse.c

#include <stdio.h>
#include <microtime.h>
#include <string.h>
#include <stdlib.h>
#include <xmmintrin.h>

struct ll_t {
  float value;
  struct ll_t *next;
};

int main(int argc, char **argv)
{
  int i, ll_size = 20000000;
  struct ll_t *ll, *curr;
  float temp[4] __attribute__((aligned(16)));
  __m128 A;
  double time1, time2;

  /* create a linked list with test data */
  ll = malloc(sizeof(struct ll_t));
  posix_memalign((void **) &ll, 16, sizeof(struct ll_t));
  curr = ll;
  for (i = 0; i < ll_size; ++i) {
    curr->value = i * 10.0f;
    if (i == ll_size - 1) {
      /* Set the last value of the linked list to 0 so we know where the end is */
      curr->next = 0;
    } else {
      curr->next = malloc(sizeof(struct ll_t));
      posix_memalign((void **) &(curr->next), 16, sizeof(struct ll_t));
      curr = curr->next;
    }
  }

  curr = ll;

  /* some operation: square the value */
  time1 = microtime();
  for (i = 0; i < ll_size; i += 4) {
     /* Load 4 values into a temporary array so it can be placed in a __m128 */
     temp[0] = curr->value;
     temp[1] = curr->next->value;
     temp[2] = curr->next->next->value;
     temp[3] = curr->next->next->next->value;

     /* Load the 4 values into a __m128 */
     A = _mm_load_ps(&(temp[0]));

     /* Use mm_mul_ps to compute 4 values at a time */
     A = _mm_mul_ps(A, A);

     /* Use cache intrinsic _mm_stream_ps to see if we get improvement */
     _mm_stream_ps(&(temp[0]), A);
     //_mm_store_ps(&(temp[0]), A);

     /* Set the 4 values back */
     curr->value = temp[0];
     curr->next->value = temp[1];
     curr->next->next->value = temp[2];
     curr->next->next->next->value = temp[3];

     /* Move to the next 4 values */
     curr = curr->next->next->next->next;
  }
  time2 = microtime();
  printf("Time = %g us\tTimer Resolution = %g us\tPerformance = %g Gflop/s\n", time2-time1, get_microtime_resolution(), ll_size*1e-3/(time2-time1));


  /* cleanup */
  // TODO

  return 0;
}