Notice removed Draw attention by CommunityBot

occurred Aug 14, 2021 at 21:06

Bounty Ended with no winning answer by CommunityBot

occurred Aug 14, 2021 at 21:06

added 69 characters in body

Source Link

edited Aug 6, 2021 at 19:21

221
1
9

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include <time.h>
#include <string.h>
#include <time.h>
#include <sys/sysinfo.h>


#define LENGTH 1000000

void print128(__uint128_t u) {
  if (u>9) print128(u/10);
  putchar(48+(int)(u%10));
}


// 2^(bitwidth) == count_size for counting sort. 16 is 128/bitwidth == num_passes (number of radix sort passes)
typedef __uint128_t u128;
typedef uint32_t u32;
u128* radix_sort128(u128* array, u32 size, u32 count_size, u32 num_passes, u32 bitwidth) {
  u32 counts[num_passes][count_size];
  memset(&counts, 0, count_size * num_passes * sizeof(u32));
  u128* cpy = (u128*) malloc(size * sizeof(u128));
  u32 o[num_passes];
  memset(o, 0, sizeof o);
  // u32 o[num_passes] = {0};
  u32 t, x, pos;
  u128* array_from, * array_to;
  for (x = 0; x < size; x++) {
    for (pos = 0; pos < num_passes; pos++) {
      t = (array[x] >> bitwidth * pos) &% 0xff;count_size;
      counts[pos][t]++;
    }
  }
  for (x = 0; x < count_size; x++) {
    for (pos = 0; pos < num_passes; pos++) {
      t = o[pos] + counts[pos][x];
      counts[pos][x] = o[pos];
      o[pos] = t;
    }
  }
  for (pos = 0; pos < num_passes; pos++) {
    array_from = pos % 2 == 0 ? array : cpy;
    array_to = pos % 2 == 0 ? cpy : array;
    for (x = 0; x < size; x++) {
      t = (array_from[x] >> bitwidth * pos) & 0xff;
      array_to[counts[pos][t]] = array_from[x];
      counts[pos][t]++;
    }
  }
  free(cpy);
  return array;
}

uint64_t wyhash64_x;


uint64_t wyhash64() {
  wyhash64_x += 0x60bee2bee120fc15;
  __uint128_t tmp;
  tmp = (__uint128_t) wyhash64_x * 0xa3b195354a39b70d;
  uint64_t m1 = (tmp >> 64) ^ tmp;
  tmp = (__uint128_t)m1 * 0x1b03738712fad5c9;
  uint64_t m2 = (tmp >> 64) ^ tmp;
  return m2;
}


int main() {
  u128* vals128 = malloc(LENGTH * sizeof(*vals128));
  u128 lower;
  u128 higher;
  struct timespec start, end;

  // make an array of random u128s 
  for (int i = 0; i < LENGTH; i++) {
    lower = (u128) wyhash64();
    higher = (u128) wyhash64();
    higher = higher << 64;
    vals128[i] = lower + higher;
  }
  for (u32 bitwidth = 8; bitwidth < 20; bitwidth+=2){
    u32 num_passes = 128/bitwidth;
    u32 count_size = 1 << bitwidth;
    printf("bitwidth %d num_passes %d count_size %d\n", bitwidth, num_passes, count_size);
    clock_gettime(CLOCK_MONOTONIC, &start);
    radix_sort128(vals128, LENGTH, count_size, num_passes, bitwidth);
    clock_gettime(CLOCK_MONOTONIC, &end);
    printf("%f seconds\n", (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1000000000.0);
  }
  free(vals128);
}

Any improvements gratefully received.

Edit

Corrected bug. & 0xff is now % count_size.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include <time.h>
#include <string.h>
#include <time.h>
#include <sys/sysinfo.h>


#define LENGTH 1000000

void print128(__uint128_t u) {
  if (u>9) print128(u/10);
  putchar(48+(int)(u%10));
}


// 2^(bitwidth) == count_size for counting sort. 16 is 128/bitwidth == num_passes (number of radix sort passes)
typedef __uint128_t u128;
typedef uint32_t u32;
u128* radix_sort128(u128* array, u32 size, u32 count_size, u32 num_passes, u32 bitwidth) {
  u32 counts[num_passes][count_size];
  memset(&counts, 0, count_size * num_passes * sizeof(u32));
  u128* cpy = (u128*) malloc(size * sizeof(u128));
  u32 o[num_passes];
  memset(o, 0, sizeof o);
  // u32 o[num_passes] = {0};
  u32 t, x, pos;
  u128* array_from, * array_to;
  for (x = 0; x < size; x++) {
    for (pos = 0; pos < num_passes; pos++) {
      t = (array[x] >> bitwidth * pos) & 0xff;
      counts[pos][t]++;
    }
  }
  for (x = 0; x < count_size; x++) {
    for (pos = 0; pos < num_passes; pos++) {
      t = o[pos] + counts[pos][x];
      counts[pos][x] = o[pos];
      o[pos] = t;
    }
  }
  for (pos = 0; pos < num_passes; pos++) {
    array_from = pos % 2 == 0 ? array : cpy;
    array_to = pos % 2 == 0 ? cpy : array;
    for (x = 0; x < size; x++) {
      t = (array_from[x] >> bitwidth * pos) & 0xff;
      array_to[counts[pos][t]] = array_from[x];
      counts[pos][t]++;
    }
  }
  free(cpy);
  return array;
}

uint64_t wyhash64_x;


uint64_t wyhash64() {
  wyhash64_x += 0x60bee2bee120fc15;
  __uint128_t tmp;
  tmp = (__uint128_t) wyhash64_x * 0xa3b195354a39b70d;
  uint64_t m1 = (tmp >> 64) ^ tmp;
  tmp = (__uint128_t)m1 * 0x1b03738712fad5c9;
  uint64_t m2 = (tmp >> 64) ^ tmp;
  return m2;
}


int main() {
  u128* vals128 = malloc(LENGTH * sizeof(*vals128));
  u128 lower;
  u128 higher;
  struct timespec start, end;

  // make an array of random u128s 
  for (int i = 0; i < LENGTH; i++) {
    lower = (u128) wyhash64();
    higher = (u128) wyhash64();
    higher = higher << 64;
    vals128[i] = lower + higher;
  }
  for (u32 bitwidth = 8; bitwidth < 20; bitwidth+=2){
    u32 num_passes = 128/bitwidth;
    u32 count_size = 1 << bitwidth;
    printf("bitwidth %d num_passes %d count_size %d\n", bitwidth, num_passes, count_size);
    clock_gettime(CLOCK_MONOTONIC, &start);
    radix_sort128(vals128, LENGTH, count_size, num_passes, bitwidth);
    clock_gettime(CLOCK_MONOTONIC, &end);
    printf("%f seconds\n", (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1000000000.0);
  }
  free(vals128);
}

Any improvements gratefully received.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include <time.h>
#include <string.h>
#include <time.h>
#include <sys/sysinfo.h>


#define LENGTH 1000000

void print128(__uint128_t u) {
  if (u>9) print128(u/10);
  putchar(48+(int)(u%10));
}


// 2^(bitwidth) == count_size for counting sort. 16 is 128/bitwidth == num_passes (number of radix sort passes)
typedef __uint128_t u128;
typedef uint32_t u32;
u128* radix_sort128(u128* array, u32 size, u32 count_size, u32 num_passes, u32 bitwidth) {
  u32 counts[num_passes][count_size];
  memset(&counts, 0, count_size * num_passes * sizeof(u32));
  u128* cpy = (u128*) malloc(size * sizeof(u128));
  u32 o[num_passes];
  memset(o, 0, sizeof o);
  // u32 o[num_passes] = {0};
  u32 t, x, pos;
  u128* array_from, * array_to;
  for (x = 0; x < size; x++) {
    for (pos = 0; pos < num_passes; pos++) {
      t = (array[x] >> bitwidth * pos) % count_size;
      counts[pos][t]++;
    }
  }
  for (x = 0; x < count_size; x++) {
    for (pos = 0; pos < num_passes; pos++) {
      t = o[pos] + counts[pos][x];
      counts[pos][x] = o[pos];
      o[pos] = t;
    }
  }
  for (pos = 0; pos < num_passes; pos++) {
    array_from = pos % 2 == 0 ? array : cpy;
    array_to = pos % 2 == 0 ? cpy : array;
    for (x = 0; x < size; x++) {
      t = (array_from[x] >> bitwidth * pos) & 0xff;
      array_to[counts[pos][t]] = array_from[x];
      counts[pos][t]++;
    }
  }
  free(cpy);
  return array;
}

uint64_t wyhash64_x;


uint64_t wyhash64() {
  wyhash64_x += 0x60bee2bee120fc15;
  __uint128_t tmp;
  tmp = (__uint128_t) wyhash64_x * 0xa3b195354a39b70d;
  uint64_t m1 = (tmp >> 64) ^ tmp;
  tmp = (__uint128_t)m1 * 0x1b03738712fad5c9;
  uint64_t m2 = (tmp >> 64) ^ tmp;
  return m2;
}


int main() {
  u128* vals128 = malloc(LENGTH * sizeof(*vals128));
  u128 lower;
  u128 higher;
  struct timespec start, end;

  // make an array of random u128s 
  for (int i = 0; i < LENGTH; i++) {
    lower = (u128) wyhash64();
    higher = (u128) wyhash64();
    higher = higher << 64;
    vals128[i] = lower + higher;
  }
  for (u32 bitwidth = 8; bitwidth < 20; bitwidth+=2){
    u32 num_passes = 128/bitwidth;
    u32 count_size = 1 << bitwidth;
    printf("bitwidth %d num_passes %d count_size %d\n", bitwidth, num_passes, count_size);
    clock_gettime(CLOCK_MONOTONIC, &start);
    radix_sort128(vals128, LENGTH, count_size, num_passes, bitwidth);
    clock_gettime(CLOCK_MONOTONIC, &end);
    printf("%f seconds\n", (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1000000000.0);
  }
  free(vals128);
}

Any improvements gratefully received.

Edit

Corrected bug. & 0xff is now % count_size.

Notice added Draw attention by Simd

occurred Aug 6, 2021 at 19:19

Bounty Started worth 50 reputation by Simd

occurred Aug 6, 2021 at 19:19

Tweeted twitter.com/StackCodeReview/status/1421893510698082304

occurred Aug 1, 2021 at 18:00

Became Hot Network Question

occurred Aug 1, 2021 at 15:35

Describe the code, not the concerns, in the title; add tags

Link

edited Aug 1, 2021 at 8:02

Toby Speight

81.7k
14
101
308

How to make my sorting/benchmarking code better Radix sort with benchmarks

Source Link

asked Aug 1, 2021 at 7:26

Simd

221
1
9

How to make my sorting/benchmarking code better

I am trying to time radix sort on 128 bit unsigned integers for different base sizes (that I call bitwidth). My code has at least the following problems:

The radix sort itself may run slower than it would otherwise as the bit width, number of passes etc are not constants that the compiler can understand and also maybe the use of variable length arrays.
I use variable length arrays. It might be better without those
It doesn't work (crashes due to stack overflow) for bitwidth > 18.

Here is the code:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include <time.h>
#include <string.h>
#include <time.h>
#include <sys/sysinfo.h>


#define LENGTH 1000000

void print128(__uint128_t u) {
  if (u>9) print128(u/10);
  putchar(48+(int)(u%10));
}


// 2^(bitwidth) == count_size for counting sort. 16 is 128/bitwidth == num_passes (number of radix sort passes)
typedef __uint128_t u128;
typedef uint32_t u32;
u128* radix_sort128(u128* array, u32 size, u32 count_size, u32 num_passes, u32 bitwidth) {
  u32 counts[num_passes][count_size];
  memset(&counts, 0, count_size * num_passes * sizeof(u32));
  u128* cpy = (u128*) malloc(size * sizeof(u128));
  u32 o[num_passes];
  memset(o, 0, sizeof o);
  // u32 o[num_passes] = {0};
  u32 t, x, pos;
  u128* array_from, * array_to;
  for (x = 0; x < size; x++) {
    for (pos = 0; pos < num_passes; pos++) {
      t = (array[x] >> bitwidth * pos) & 0xff;
      counts[pos][t]++;
    }
  }
  for (x = 0; x < count_size; x++) {
    for (pos = 0; pos < num_passes; pos++) {
      t = o[pos] + counts[pos][x];
      counts[pos][x] = o[pos];
      o[pos] = t;
    }
  }
  for (pos = 0; pos < num_passes; pos++) {
    array_from = pos % 2 == 0 ? array : cpy;
    array_to = pos % 2 == 0 ? cpy : array;
    for (x = 0; x < size; x++) {
      t = (array_from[x] >> bitwidth * pos) & 0xff;
      array_to[counts[pos][t]] = array_from[x];
      counts[pos][t]++;
    }
  }
  free(cpy);
  return array;
}

uint64_t wyhash64_x;


uint64_t wyhash64() {
  wyhash64_x += 0x60bee2bee120fc15;
  __uint128_t tmp;
  tmp = (__uint128_t) wyhash64_x * 0xa3b195354a39b70d;
  uint64_t m1 = (tmp >> 64) ^ tmp;
  tmp = (__uint128_t)m1 * 0x1b03738712fad5c9;
  uint64_t m2 = (tmp >> 64) ^ tmp;
  return m2;
}


int main() {
  u128* vals128 = malloc(LENGTH * sizeof(*vals128));
  u128 lower;
  u128 higher;
  struct timespec start, end;

  // make an array of random u128s 
  for (int i = 0; i < LENGTH; i++) {
    lower = (u128) wyhash64();
    higher = (u128) wyhash64();
    higher = higher << 64;
    vals128[i] = lower + higher;
  }
  for (u32 bitwidth = 8; bitwidth < 20; bitwidth+=2){
    u32 num_passes = 128/bitwidth;
    u32 count_size = 1 << bitwidth;
    printf("bitwidth %d num_passes %d count_size %d\n", bitwidth, num_passes, count_size);
    clock_gettime(CLOCK_MONOTONIC, &start);
    radix_sort128(vals128, LENGTH, count_size, num_passes, bitwidth);
    clock_gettime(CLOCK_MONOTONIC, &end);
    printf("%f seconds\n", (end.tv_sec - start.tv_sec) + (end.tv_nsec - start.tv_nsec) / 1000000000.0);
  }
  free(vals128);
}

Any improvements gratefully received.

c

Stack Exchange Network

Return to Question

How to make my sorting/benchmarking code better Radix sort with benchmarks

How to make my sorting/benchmarking code better