我正在编写一个函数
int are_non_negatives(int* start, int n) {
...
}
如果数组start
中接下来的n
个整数都是非负数,此函数返回1。否则返回0。
我的问题是是否有比遍历和检查每个位置都更快的技巧?
脏/不可移植的技巧也可以。我也想知道那些。谢谢!
我正在编写一个函数
int are_non_negatives(int* start, int n) {
...
}
如果数组start
中接下来的n
个整数都是非负数,此函数返回1。否则返回0。
我的问题是是否有比遍历和检查每个位置都更快的技巧?
脏/不可移植的技巧也可以。我也想知道那些。谢谢!
在所有元素都需要检查的最坏情况下,您可以利用一个稍微“不干净/非便携”的技巧:在二进制补码int表示中,当且仅当值为负时,最高位设置。因此,您可以对它们进行按位 OR 运算并检查最高位。这可以使用矢量指令批处理执行,例如每次8个元素,假设32位整数和256位AVX指令。
尝试提高性能是C程序员经常探讨的话题。基准测试不可或缺,以测试优化是否有用并值得付出努力。以下是一个供参考的幼稚实现:
int are_non_negatives_naive(const int *start, int n) {
while (n --> 0) {
if (*start++ >= 0)
return 0;
}
return 1;
}
int are_non_negatives_full(const int *start, int n) {
int combined = 0;
while (n --> 0) {
combined |= *start++;
}
return combined >= 0;
}
int are_non_negatives_chunks(const int *start, int n) {
int combined;
for (; n >= 8; n -= 8, start += 8) {
combined = (start[0] | start[1] | start[2] | start[3] |
start[4] | start[5] | start[6] | start[7]);
if (combined < 0)
return 0;
}
combined = 0;
while (n --> 0) {
combined |= *start++;
}
return combined >= 0;
}
通过矢量化上述内容,可以进一步提高性能,可以使用便携式的构造或更具体的硬件特定内部函数,例如使用64位类型。如果编译器可以自己对上述算法进行矢量化,则不需要这种努力:如clang所示,使用SIMD指令可以在Godbolt Compiler Explorer中看到。
您可以通过转换为可用的最大整数并制作正确的掩码来一次检查k
个元素,例如:如果您有一个char或int8_t数组,则可以一次检查8个元素。
掩码被制作成全零,除了符号位。
这样,如果其中一个chars为负数,则掩码和转换迭代器的按位与将是> 0
int8_t _i8[8] = { INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN };
uint64_t mask = *(uint64_t *)_i8;
uint64_t *it = (uint64_t *)a;
size_t i = 0;
if (it[i] & mask)
return FALSE;
n % k
的余数,可以通过以下简单的 switch 语句来完成:size_t i = 0;
switch (n % 8) {
case 0: if (a[i++] < 0) return FALSE;
case 7: if (a[i++] < 0) return FALSE;
case 6: if (a[i++] < 0) return FALSE;
case 5: if (a[i++] < 0) return FALSE;
case 4: if (a[i++] < 0) return FALSE;
case 3: if (a[i++] < 0) return FALSE;
case 2: if (a[i++] < 0) return FALSE;
case 1: if (a[i++] < 0) return FALSE;
}
你可以在这里运行它https://onlinegdb.com/SyliIUrSZO
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <time.h>
#define CLOCKS_PER_MSEC (CLOCKS_PER_SEC/1000)
#define TRUE (0 == 0)
#define FALSE (!TRUE)
// 8 bit integers
int are_non_negatives_naive_i8(int8_t *a, size_t n)
{
size_t i;
for (i = 0; i < n; ++i)
if (a[i] < 0)
return FALSE;
return TRUE;
}
int are_non_negatives_unrolled_i8(int8_t *a, size_t n)
{
size_t M = (n + 7) / 8;
size_t i = 0;
switch (n % 8) {
case 0: do { if (a[i++] < 0) return FALSE;
case 7: if (a[i++] < 0) return FALSE;
case 6: if (a[i++] < 0) return FALSE;
case 5: if (a[i++] < 0) return FALSE;
case 4: if (a[i++] < 0) return FALSE;
case 3: if (a[i++] < 0) return FALSE;
case 2: if (a[i++] < 0) return FALSE;
case 1: if (a[i++] < 0) return FALSE;
} while (--M > 0);
}
}
int are_non_negatives_unrolled_masked_i8(int8_t *a, size_t n)
{
int8_t _i8[8] = { INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN, INT8_MIN };
uint64_t mask = *(uint64_t *)_i8;
uint64_t *it = (uint64_t *)a;
size_t i = 0;
switch (n % 8) {
case 0: if (a[i++] < 0) return FALSE;
case 7: if (a[i++] < 0) return FALSE;
case 6: if (a[i++] < 0) return FALSE;
case 5: if (a[i++] < 0) return FALSE;
case 4: if (a[i++] < 0) return FALSE;
case 3: if (a[i++] < 0) return FALSE;
case 2: if (a[i++] < 0) return FALSE;
case 1: if (a[i++] < 0) return FALSE;
}
size_t N = n / 8;
// for (i = 0; i < N; ++i)
// if (it[i] & mask)
// return FALSE;
size_t M = (N + 7) / 8;
switch (N % 8) {
case 0: do { if (it[i++] & mask) return FALSE;
case 7: if (it[i++] & mask) return FALSE;
case 6: if (it[i++] & mask) return FALSE;
case 5: if (it[i++] & mask) return FALSE;
case 4: if (it[i++] & mask) return FALSE;
case 3: if (it[i++] & mask) return FALSE;
case 2: if (it[i++] & mask) return FALSE;
case 1: if (it[i++] & mask) return FALSE;
} while (--M > 0);
}
return TRUE;
}
//----------------------------------------------------------------
// 16 bit integers
int are_non_negatives_naive_i16(int16_t *a, size_t n)
{
size_t i;
for (i = 0; i < n; ++i)
if (a[i] < 0)
return FALSE;
return TRUE;
}
int are_non_negatives_unrolled_i16(int16_t *a, size_t n)
{
size_t M = (n + 7) / 8;
size_t i = 0;
switch (n % 8) {
case 0: do { if (a[i++] < 0) return FALSE;
case 7: if (a[i++] < 0) return FALSE;
case 6: if (a[i++] < 0) return FALSE;
case 5: if (a[i++] < 0) return FALSE;
case 4: if (a[i++] < 0) return FALSE;
case 3: if (a[i++] < 0) return FALSE;
case 2: if (a[i++] < 0) return FALSE;
case 1: if (a[i++] < 0) return FALSE;
} while (--M > 0);
}
}
int are_non_negatives_unrolled_masked_i16(int16_t *a, size_t n)
{
int16_t _i16[4] = { INT16_MIN, INT16_MIN, INT16_MIN, INT16_MIN };
uint64_t mask = *(uint64_t *)_i16;
uint64_t *it = (uint64_t *)a;
size_t i = 0;
switch (n % 8) {
case 0: if (a[i++] < 0) return FALSE;
case 7: if (a[i++] < 0) return FALSE;
case 6: if (a[i++] < 0) return FALSE;
case 5: if (a[i++] < 0) return FALSE;
case 4: if (a[i++] < 0) return FALSE;
case 3: if (a[i++] < 0) return FALSE;
case 2: if (a[i++] < 0) return FALSE;
case 1: if (a[i++] < 0) return FALSE;
}
size_t N = n / 4;
// for (i = 0; i < N; ++i)
// if (it[i] & mask)
// return FALSE;
size_t M = (N + 7) / 8;
switch (N % 8) {
case 0: do { if (it[i++] & mask) return FALSE;
case 7: if (it[i++] & mask) return FALSE;
case 6: if (it[i++] & mask) return FALSE;
case 5: if (it[i++] & mask) return FALSE;
case 4: if (it[i++] & mask) return FALSE;
case 3: if (it[i++] & mask) return FALSE;
case 2: if (it[i++] & mask) return FALSE;
case 1: if (it[i++] & mask) return FALSE;
} while (--M > 0);
}
return TRUE;
}
//----------------------------------------------------------------
// 32 bit integers
int are_non_negatives_naive_i32(int32_t *a, size_t n)
{
size_t i;
for (i = 0; i < n; ++i)
if (a[i] < 0)
return FALSE;
return TRUE;
}
int are_non_negatives_unrolled_i32(int32_t *a, size_t n)
{
size_t M = (n + 7) / 8;
size_t i = 0;
switch (n % 8) {
case 0: do { if (a[i++] < 0) return FALSE;
case 7: if (a[i++] < 0) return FALSE;
case 6: if (a[i++] < 0) return FALSE;
case 5: if (a[i++] < 0) return FALSE;
case 4: if (a[i++] < 0) return FALSE;
case 3: if (a[i++] < 0) return FALSE;
case 2: if (a[i++] < 0) return FALSE;
case 1: if (a[i++] < 0) return FALSE;
} while (--M > 0);
}
}
int are_non_negatives_unrolled_masked_i32(int32_t *a, size_t n)
{
int32_t _i32[2] = { INT32_MIN, INT32_MIN };
uint64_t mask = *(uint64_t *)_i32;
uint64_t *it = (uint64_t *)a;
size_t i = 0;
switch (n % 8) {
case 0: if (a[i++] < 0) return FALSE;
case 7: if (a[i++] < 0) return FALSE;
case 6: if (a[i++] < 0) return FALSE;
case 5: if (a[i++] < 0) return FALSE;
case 4: if (a[i++] < 0) return FALSE;
case 3: if (a[i++] < 0) return FALSE;
case 2: if (a[i++] < 0) return FALSE;
case 1: if (a[i++] < 0) return FALSE;
}
size_t N = n / 2;
// for (i = 0; i < N; ++i)
// if (it[i] & mask)
// return FALSE;
size_t M = (N + 7) / 8;
switch (N % 8) {
case 0: do { if (it[i++] & mask) return FALSE;
case 7: if (it[i++] & mask) return FALSE;
case 6: if (it[i++] & mask) return FALSE;
case 5: if (it[i++] & mask) return FALSE;
case 4: if (it[i++] & mask) return FALSE;
case 3: if (it[i++] & mask) return FALSE;
case 2: if (it[i++] & mask) return FALSE;
case 1: if (it[i++] & mask) return FALSE;
} while (--M > 0);
}
return TRUE;
}
//----------------------------------------------------------------
void fill_array(void *array, size_t type, size_t n, int contains_negatives)
{
size_t i;
switch (type) {
case 1: {
int8_t *a = array;
for (i = 0; i < n; ++i)
a[i] = rand() % INT8_MAX;
break;
}
case 2: {
int16_t *a = array;
for (i = 0; i < n; ++i)
a[i] = rand() % INT16_MAX;
break;
}
case 4: {
int32_t *a = array;
for (i = 0; i < n; ++i)
a[i] = rand() % INT32_MAX;
break;
}
case 8: {
int64_t *a = array;
for (i = 0; i < n; ++i)
a[i] = rand();
break;
}
}
if (contains_negatives) {
int how_many = rand() % n;
for (int i; i < how_many; ++i) {
int j = rand() % n;
switch (type) {
case 1: {
int8_t *a = array;
a[j] *= -1;
break;
}
case 2: {
int16_t *a = array;
a[j] *= -1;
break;
}
case 4: {
int32_t *a = array;
a[j] *= -1;
break;
}
case 8: {
int64_t *a = array;
a[j] *= -1;
break;
}
}
}
}
}
int main()
{
time_t t;
clock_t clock_start;
clock_t clock_end;
clock_t clock_naive = 0;
clock_t clock_unrolled = 0;
clock_t clock_unrolled_masked = 0;
/* Intializes random number generator */
srand((unsigned long) time(&t));
printf("8 bit integers\n");
printf("----------------------------------------------------------------\n");
int8_t *array_i8;
for (int i = 3; i < 7; ++i) {
size_t size = pow(10, i);
array_i8 = malloc(size * sizeof(int8_t));
printf("------------------------------------------------\n");
printf("%lu elements\n", size);
for (int has_neg = 0; has_neg < 2; ++has_neg) {
printf("--------------------------------\n");
printf("Has negatives: %s\n", has_neg ? "yes": "no");
fill_array(array_i8, sizeof(int8_t), size, has_neg);
int neg_naive;
int neg_unrolled;
int neg_unrolled_masked;
clock_start = clock();
neg_naive = are_non_negatives_naive_i8(array_i8, size);
clock_end = clock();
clock_naive = clock_end - clock_start;
clock_start = clock();
neg_unrolled = are_non_negatives_unrolled_i8(array_i8, size);
clock_end = clock();
clock_unrolled = clock_end - clock_start;
clock_start = clock();
neg_unrolled_masked = are_non_negatives_unrolled_masked_i8(array_i8, size);
clock_end = clock();
clock_unrolled_masked = clock_end - clock_start;
if (!has_neg) {
if (!neg_naive)
printf("Error: neg_naive\n");
if (!neg_unrolled)
printf("Error: neg_unrolled\n");
if (!neg_unrolled_masked)
printf("Error: neg_unrolled_masked\n");
}
printf(" clock_naive: %lu\n", clock_naive);
printf(" clock_unrolled: %lu\n", clock_unrolled);
printf("clock_unrolled_masked: %lu\n", clock_unrolled_masked);
printf("--------------------------------\n");
}
printf("------------------------------------------------\n");
free (array_i8);
array_i8 = NULL;
}
printf("----------------------------------------------------------------\n");
printf("16 bit integers\n");
printf("----------------------------------------------------------------\n");
int16_t *array_i16;
for (int i = 3; i < 7; ++i) {
size_t size = pow(10, i);
array_i16 = malloc(size * sizeof(int16_t));
printf("------------------------------------------------\n");
printf("%lu elements\n", size);
for (int has_neg = 0; has_neg < 2; ++has_neg) {
printf("--------------------------------\n");
printf("Has negatives: %s\n", has_neg ? "yes": "no");
fill_array(array_i16, sizeof(int16_t), size, has_neg);
int neg_naive;
int neg_unrolled;
int neg_unrolled_masked;
clock_start = clock();
neg_naive = are_non_negatives_naive_i16(array_i16, size);
clock_end = clock();
clock_naive = clock_end - clock_start;
clock_start = clock();
neg_unrolled = are_non_negatives_unrolled_i16(array_i16, size);
clock_end = clock();
clock_unrolled = clock_end - clock_start;
clock_start = clock();
neg_unrolled_masked = are_non_negatives_unrolled_masked_i16(array_i16, size);
clock_end = clock();
clock_unrolled_masked = clock_end - clock_start;
if (!has_neg) {
if (!neg_naive)
printf("Error: neg_naive\n");
if (!neg_unrolled)
printf("Error: neg_unrolled\n");
if (!neg_unrolled_masked)
printf("Error: neg_unrolled_masked\n");
}
printf(" clock_naive: %lu\n", clock_naive);
printf(" clock_unrolled: %lu\n", clock_unrolled);
printf("clock_unrolled_masked: %lu\n", clock_unrolled_masked);
printf("--------------------------------\n");
}
printf("------------------------------------------------\n");
free (array_i16);
array_i16 = NULL;
}
printf("----------------------------------------------------------------\n");
printf("32 bit integers\n");
printf("----------------------------------------------------------------\n");
int32_t *array_i32;
for (int i = 3; i < 7; ++i) {
size_t size = pow(10, i);
array_i32 = malloc(size * sizeof(int32_t));
printf("------------------------------------------------\n");
printf("%lu elements\n", size);
for (int has_neg = 0; has_neg < 2; ++has_neg) {
printf("--------------------------------\n");
printf("Has negatives: %s\n", has_neg ? "yes": "no");
fill_array(array_i32, sizeof(int32_t), size, has_neg);
int neg_naive;
int neg_unrolled;
int neg_unrolled_masked;
clock_start = clock();
neg_naive = are_non_negatives_naive_i32(array_i32, size);
clock_end = clock();
clock_naive = clock_end - clock_start;
clock_start = clock();
neg_unrolled = are_non_negatives_unrolled_i32(array_i32, size);
clock_end = clock();
clock_unrolled = clock_end - clock_start;
clock_start = clock();
neg_unrolled_masked = are_non_negatives_unrolled_masked_i32(array_i32, size);
clock_end = clock();
clock_unrolled_masked = clock_end - clock_start;
if (!has_neg) {
if (!neg_naive)
printf("Error: neg_naive\n");
if (!neg_unrolled)
printf("Error: neg_unrolled\n");
if (!neg_unrolled_masked)
printf("Error: neg_unrolled_masked\n");
}
printf(" clock_naive: %lu\n", clock_naive);
printf(" clock_unrolled: %lu\n", clock_unrolled);
printf("clock_unrolled_masked: %lu\n", clock_unrolled_masked);
printf("--------------------------------\n");
}
printf("------------------------------------------------\n");
free (array_i32);
array_i32 = NULL;
}
printf("----------------------------------------------------------------\n");
}
#include <stdio.h>
#include <stdint.h>
#include <stdalign.h>
int main()
{
printf(
"alignof(int8_t ): %lu\n"
"alignof(int16_t): %lu\n"
"alignof(int32_t): %lu\n"
"alignof(int64_t): %lu\n",
alignof(int8_t),
alignof(int16_t),
alignof(int32_t),
alignof(int64_t)
);
return 0;
}
*(uint64_t *)_i8
和 uint64_t *it = (uint64_t *)a;
都是严格别名规则的违反,因此会导致未定义行为。它们还通过违反C11 6.3.2.3p7而冒着未定义行为的风险:“指向对象类型的指针可以转换为指向不同对象类型的指针。如果所得到的指针对于引用的类型没有正确对齐,则其行为未定义。” - Andrew Henle根据你的问题背景,我怀疑这种方法对你可能不适用。但是如果你的代码允许捕获数组操作(初始化、插入、修改、删除),那么你可以一致地维护一个单独的负值元素列表。如果你有这个自由,那么这只是一个空间和速度的权衡。
int
元素进行按位或操作,最后测试符号位是否为1。(在符号-数值实现中,这将把 −0 视为负数。)一些处理器上,一系列的按位或操作可能比比较更快。你也可以展开循环以并行计算。然后,你可以考虑使用 SIMD 等扩展功能。 - Eric Postpischil