Project

General

Profile

« Previous | Next » 

Revision d286d445

Added by David Sorber over 10 years ago

Adding bit position test program used to benchmark various approaches and a couple of support scripts.

View differences:

software/misc/bit_position/bit_position.c
#define _XOPEN_SOURCE
#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
#include <x86intrin.h>
// To compile:
// gcc -std=c99 -mlzcnt -O3 -mtune=native -o bit_position bit_position.c
int timeval_subtract(struct timeval *result, struct timeval *x, struct timeval *y)
{
/* Perform the carry for the later subtraction by updating y. */
if (x->tv_usec < y->tv_usec) {
int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1;
y->tv_usec -= 1000000 * nsec;
y->tv_sec += nsec;
}
if (x->tv_usec - y->tv_usec > 1000000) {
int nsec = (x->tv_usec - y->tv_usec) / 1000000;
y->tv_usec += 1000000 * nsec;
y->tv_sec -= nsec;
}
/* Compute the time remaining to wait.
tv_usec is certainly positive. */
result->tv_sec = x->tv_sec - y->tv_sec;
result->tv_usec = x->tv_usec - y->tv_usec;
/* Return 1 if result is negative. */
return x->tv_sec < y->tv_sec;
}
// Approach 0: naive version
void approach0(uint32_t count, uint64_t* vectors)
{
for (uint32_t idx = 0; idx < count; idx++) {
uint64_t copy = vectors[idx];
printf("Index: %" PRIu32 "\n", idx);
uint64_t compare = 1;
for (uint32_t ctr = 0; ctr < 64; ctr++)
{
if (compare & copy)
{
printf("%" PRIu32 " ", ctr);
}
compare = (compare << 1);
}
printf("\n\n");
}
}
// Approach 1: use intrinsic and bitwise clear
void approach1(uint32_t count, uint64_t* vectors)
{
for (uint32_t idx = 0; idx < count; idx++) {
uint64_t copy = vectors[idx];
printf("Index: %" PRIu32 "\n", idx);
uint64_t position = 0;
while (copy) {
position = __builtin_ctzll(copy);
printf("%" PRIu64 " ", position);
copy &= ~((uint64_t)1 << position);
}
printf("\n\n");
}
}
// Approach 2: use intrinsic and lookup table
void approach2(uint32_t count, uint64_t* vectors)
{
uint64_t masks[64] = {
0xFFFFFFFFFFFFFFFE,
0xFFFFFFFFFFFFFFFD,
0xFFFFFFFFFFFFFFFB,
0xFFFFFFFFFFFFFFF7,
0xFFFFFFFFFFFFFFEF,
0xFFFFFFFFFFFFFFDF,
0xFFFFFFFFFFFFFFBF,
0xFFFFFFFFFFFFFF7F,
0xFFFFFFFFFFFFFEFF,
0xFFFFFFFFFFFFFDFF,
0xFFFFFFFFFFFFFBFF,
0xFFFFFFFFFFFFF7FF,
0xFFFFFFFFFFFFEFFF,
0xFFFFFFFFFFFFDFFF,
0xFFFFFFFFFFFFBFFF,
0xFFFFFFFFFFFF7FFF,
0xFFFFFFFFFFFEFFFF,
0xFFFFFFFFFFFDFFFF,
0xFFFFFFFFFFFBFFFF,
0xFFFFFFFFFFF7FFFF,
0xFFFFFFFFFFEFFFFF,
0xFFFFFFFFFFDFFFFF,
0xFFFFFFFFFFBFFFFF,
0xFFFFFFFFFF7FFFFF,
0xFFFFFFFFFEFFFFFF,
0xFFFFFFFFFDFFFFFF,
0xFFFFFFFFFBFFFFFF,
0xFFFFFFFFF7FFFFFF,
0xFFFFFFFFEFFFFFFF,
0xFFFFFFFFDFFFFFFF,
0xFFFFFFFFBFFFFFFF,
0xFFFFFFFF7FFFFFFF,
0xFFFFFFFEFFFFFFFF,
0xFFFFFFFDFFFFFFFF,
0xFFFFFFFBFFFFFFFF,
0xFFFFFFF7FFFFFFFF,
0xFFFFFFEFFFFFFFFF,
0xFFFFFFDFFFFFFFFF,
0xFFFFFFBFFFFFFFFF,
0xFFFFFF7FFFFFFFFF,
0xFFFFFEFFFFFFFFFF,
0xFFFFFDFFFFFFFFFF,
0xFFFFFBFFFFFFFFFF,
0xFFFFF7FFFFFFFFFF,
0xFFFFEFFFFFFFFFFF,
0xFFFFDFFFFFFFFFFF,
0xFFFFBFFFFFFFFFFF,
0xFFFF7FFFFFFFFFFF,
0xFFFEFFFFFFFFFFFF,
0xFFFDFFFFFFFFFFFF,
0xFFFBFFFFFFFFFFFF,
0xFFF7FFFFFFFFFFFF,
0xFFEFFFFFFFFFFFFF,
0xFFDFFFFFFFFFFFFF,
0xFFBFFFFFFFFFFFFF,
0xFF7FFFFFFFFFFFFF,
0xFEFFFFFFFFFFFFFF,
0xFDFFFFFFFFFFFFFF,
0xFBFFFFFFFFFFFFFF,
0xF7FFFFFFFFFFFFFF,
0xEFFFFFFFFFFFFFFF,
0xDFFFFFFFFFFFFFFF,
0xBFFFFFFFFFFFFFFF,
0x7FFFFFFFFFFFFFFF};
for (uint32_t idx = 0; idx < count; idx++) {
uint64_t copy = vectors[idx];
printf("Index: %" PRIu32 "\n", idx);
uint64_t position = 0;
while (copy) {
position = __builtin_ctzll(copy);
printf("%" PRIu64 " ", position);
copy &= masks[position];
}
printf("\n\n");
}
}
int main(int argc, char** argv)
{
// Make sure an argument, the file name of the file containing the vectors
// was specified
if (argc < 3) {
fprintf(stderr, "Please specify file containing vectors and approach "
"index (0-2)\n");
return -1;
}
// Loop over the file and convert the string vectors into uint64_t's
// stored in the "vectors" array
uint64_t* vectors = NULL;
uint32_t count = 0;
FILE* file = fopen(argv[1], "r");
char line[256];
while (fgets(line, sizeof(line), file)) {
count++;
if (vectors == NULL) {
vectors = (uint64_t*)malloc(sizeof(uint64_t));
} else {
vectors = realloc(vectors, count * sizeof(uint64_t));
}
vectors[count - 1] = strtoull(line, NULL, 16);
//~ printf("%s", line);
}
fclose(file);
// Start time
struct timeval t0_time;
gettimeofday(&t0_time, NULL);
// Decide which approach to use
switch (argv[2][0]) {
case '0':
approach0(count, vectors);
break;
case '1':
approach1(count, vectors);
break;
case '2':
approach2(count, vectors);
break;
default:
fprintf(stderr, "ERROR: invalid approach index\n");
}
// Grab stop time
struct timeval t1_time;
gettimeofday(&t1_time, NULL);
struct timeval elapsed;
timeval_subtract(&elapsed, &t1_time, &t0_time);
printf("Elapsed time: %ld.%06ld s\n", elapsed.tv_sec, elapsed.tv_usec);
return 0;
}
software/misc/bit_position/make_vectors.py
import sys
def main():
if len(sys.argv) < 2:
print('ERROR: must specify number of output vectors')
return 1
num_vectors = 0
try:
num_vectors = int(sys.argv[1])
except ValueError:
print('ERROR: argument must be an integer')
return 1
with open('/dev/urandom', 'rb') as random_input:
for idx in range(num_vectors):
raw = random_input.read(8)
vector = int.from_bytes(raw, byteorder='little')
print('{:016X}'.format(vector))
if __name__ == '__main__':
sys.exit(main())
software/misc/walking_zeros.py
import sys
def main():
# Print out ASCII hex walking zeros pattern
base = 0xffffffffffffffff
for idx in range(64):
foo = base
foo &= ~(1 <<idx);
print('{:016X}'.format(foo))
if __name__ == '__main__':
sys.exit(main())

Also available in: Unified diff