那些遇到过的问题

C - 实现快速将许多元素推送到数组的末尾

Mic*_*has 16 c arrays optimization c99

我有一个简单的结构来保存数组:

struct array_of_a_type {
        size_t allocated_size;
        size_t elements; /* 1-index based */
        a_type *array;
};
Run Code Online (Sandbox Code Playgroud)

我想写一个简单的函数,如下所示:

bool simple_function(struct array_of_a_type *my_array, int a, int b, int c, int d)
{
    a_type new_chunk[] = {
        a,   b,   a+b, d,   c,
        c,   c,   c+d, b+d, a,
        a+c, b+c, c+d, c+d, c,
    };
    size_t size = sizeof(new_chunk) / sizeof(a_type);
    return push_to_array(my_array, new_chunk, size);
}
Run Code Online (Sandbox Code Playgroud)

my_array是一个静态的全局变量.下面是push_to_array的实现.

static bool push_to_array(struct array_of_a_type *a, a_type *new_chunk, size_t size)
{
    const size_t new_size = a->elements + size;
    const size_t old_size = a->elements;
    if (new_size > a->allocated_size) {
        /* The allocated_size is most of the time big enough.
           I’ve stripped this part of code to minimum. */
        a_type *tmp = realloc(a->array, new_size * sizeof(a_type));
        if (!tmp) {
            return true;
        } else {
            a->array = tmp;
            a->allocated_size = new_size;
        }
    }
    a->elements = new_size;
    memcpy(a->array + old_size, new_chunk, size * sizeof(a_type));
    return false;
}
Run Code Online (Sandbox Code Playgroud)

我的问题:
如何重写'simple_function'以使更多的编译器生成直接写入目标的代码？我希望代码保持简短和灵活.

我的代码有效.不幸的是,gcc(和一个旧的clang)在堆栈上创建临时数据,然后将其复制到目标.下面是生成的x86_64汇编程序的片段.

movq    8(%rsp), %rdx
movq    %rdx, 8(%rax)
movq    16(%rsp), %rdx
movq    %rdx, 16(%rax)
movq    24(%rsp), %rdx
movq    %rdx, 24(%rax)
movq    32(%rsp), %rdx
movq    %rdx, 32(%rax)
Run Code Online (Sandbox Code Playgroud)

对于AMD,汇编程序有:

rep movsq
Run Code Online (Sandbox Code Playgroud)

新的铿锵声很好.我用-O3编译了.

我尝试过一次添加一个元素的代码.不幸的是,有很多条件跳转来调用realloc.

Nom*_*mal 9

为了提高效率,您需要分离用于增长数组的逻辑,并将值分配给(未使用的)插槽,以避免额外的副本(从堆栈到数组).

为了美化代码,您可以创建一组帮助程序宏.我将假设"推"是指"附加到数组".如果你的意思是"prepend",那么还memmove()需要额外的东西.

我们假设你有

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

typedef int  array_data_type;

typedef struct {
    size_t           size;
    size_t           used;
    array_data_type *item;
} array_type;

#define ARRAY_INITIALIZER { 0, 0, NULL }

void array_free(array_type *const array)
{
    free(array->item);
    array->size = 0;
    array->used = 0;
    array->item = NULL;
}

void array_init(array_type *const array)
{
    array->size = 0;
    array->used = 0;
    array->item = NULL;
}

void array_init_size(array_type *const array, const size_t size)
{
    if (!size) {
        array->size = 0;
        array->used = 0;
        array->item = NULL;
        return;
    }

    array->item = malloc(size * sizeof array->item[0]);
    if (!array->item) {
        fprintf(stderr, "array_init_size(%p, %zu): Out of memory.\n", (void *)array, size);
        exit(EXIT_FAILURE);
    }
    array->size = size;
    array->used  = 0;
}

void array_grow_to(array_type *const array, size_t size)
{
    array_data_type *temp;

    if (size < 4)
        size = 4;
    else
    if (size < 16777216) {
        size |= size >> 1;
        size |= size >> 2;
        size |= size >> 4;
        size |= size >> 8;
        size |= size >> 16;
        size++;
    } else
        size = (size | 8388607) + 8388609;

    temp = realloc(array->item, size * sizeof array->item[0]);
    if (!temp) {
        fprintf(stderr, "array_grow_to(%p, %zu): Out of memory.\n", (void *)array, size);
        exit(EXIT_FAILURE);
    }

    array->item = temp;
    array->size = size;
}

static inline array_data_type *array_grow_by(array_type *const array, size_t const count)
{
    array_data_type *retval;

    if (array->used + count > array->size)
        array_grow_to(array, array->used + count);

    retval = array->item + array->used;
    array->used += count;
    return retval;
}
Run Code Online (Sandbox Code Playgroud)

我喜欢使用used数组中size的元素数量,以及数组为内存分配的元素数量.如果您习惯了其他名称,请进行搜索和替换.

array_grow_to()将新大小调整为至少4,或者如果小于16,777,216则调整为2的下一个幂,或者调整为8,388,608的较大倍数.这限制了非常大的列表的已分配但未使用的内存量.

array_grow_by()确保数组有count新元素的空间,并返回指向第一个未使用的新元素的指针.

如果您定义以下C99预处理器宏,

#define MACRO_CONCATENATE(part1, ...)   part1 ## __VA_ARGS__

#define ARRAY_SET_N(array, count, ...)  MACRO_CONCATENATE(ARRAY_SET_, count)(array, count, __VA_ARGS__)
#define ARRAY_SET_0(...)
#define ARRAY_SET_1(a, n, v)        a[n-1] = v
#define ARRAY_SET_2(a, n, v, ...)   a[n-2] = v; ARRAY_SET_1(a, n, __VA_ARGS__)
#define ARRAY_SET_3(a, n, v, ...)   a[n-3] = v; ARRAY_SET_2(a, n, __VA_ARGS__)
#define ARRAY_SET_4(a, n, v, ...)   a[n-4] = v; ARRAY_SET_3(a, n, __VA_ARGS__)
#define ARRAY_SET_5(a, n, v, ...)   a[n-5] = v; ARRAY_SET_4(a, n, __VA_ARGS__)
#define ARRAY_SET_6(a, n, v, ...)   a[n-6] = v; ARRAY_SET_5(a, n, __VA_ARGS__)
#define ARRAY_SET_7(a, n, v, ...)   a[n-7] = v; ARRAY_SET_6(a, n, __VA_ARGS__)
#define ARRAY_SET_8(a, n, v, ...)   a[n-8] = v; ARRAY_SET_7(a, n, __VA_ARGS__)
#define ARRAY_SET_9(a, n, v, ...)   a[n-9] = v; ARRAY_SET_8(a, n, __VA_ARGS__)
#define ARRAY_SET_10(a, n, v, ...)  a[n-10] = v; ARRAY_SET_9(a, n, __VA_ARGS__)
#define ARRAY_SET_11(a, n, v, ...)  a[n-11] = v; ARRAY_SET_10(a, n, __VA_ARGS__)
#define ARRAY_SET_12(a, n, v, ...)  a[n-12] = v; ARRAY_SET_11(a, n, __VA_ARGS__)
#define ARRAY_SET_13(a, n, v, ...)  a[n-13] = v; ARRAY_SET_12(a, n, __VA_ARGS__)
#define ARRAY_SET_14(a, n, v, ...)  a[n-14] = v; ARRAY_SET_13(a, n, __VA_ARGS__)
#define ARRAY_SET_15(a, n, v, ...)  a[n-15] = v; ARRAY_SET_14(a, n, __VA_ARGS__)
#define ARRAY_SET_16(a, n, v, ...)  a[n-16] = v; ARRAY_SET_15(a, n, __VA_ARGS__)
#define ARRAY_SET_17(a, n, v, ...)  a[n-17] = v; ARRAY_SET_16(a, n, __VA_ARGS__)
#define ARRAY_SET_18(a, n, v, ...)  a[n-18] = v; ARRAY_SET_17(a, n, __VA_ARGS__)
#define ARRAY_SET_19(a, n, v, ...)  a[n-19] = v; ARRAY_SET_18(a, n, __VA_ARGS__)
#define ARRAY_SET_20(a, n, v, ...)  a[n-20] = v; ARRAY_SET_19(a, n, __VA_ARGS__)
#define ARRAY_SET_21(a, n, v, ...)  a[n-21] = v; ARRAY_SET_20(a, n, __VA_ARGS__)
#define ARRAY_SET_22(a, n, v, ...)  a[n-22] = v; ARRAY_SET_21(a, n, __VA_ARGS__)
#define ARRAY_SET_23(a, n, v, ...)  a[n-23] = v; ARRAY_SET_22(a, n, __VA_ARGS__)
#define ARRAY_SET_24(a, n, v, ...)  a[n-24] = v; ARRAY_SET_23(a, n, __VA_ARGS__)
#define ARRAY_SET_25(a, n, v, ...)  a[n-25] = v; ARRAY_SET_24(a, n, __VA_ARGS__)
#define ARRAY_SET_26(a, n, v, ...)  a[n-26] = v; ARRAY_SET_25(a, n, __VA_ARGS__)
#define ARRAY_SET_27(a, n, v, ...)  a[n-27] = v; ARRAY_SET_26(a, n, __VA_ARGS__)
#define ARRAY_SET_28(a, n, v, ...)  a[n-28] = v; ARRAY_SET_27(a, n, __VA_ARGS__)
#define ARRAY_SET_29(a, n, v, ...)  a[n-29] = v; ARRAY_SET_28(a, n, __VA_ARGS__)
#define ARRAY_SET_30(a, n, v, ...)  a[n-30] = v; ARRAY_SET_29(a, n, __VA_ARGS__)
#define ARRAY_SET_31(a, n, v, ...)  a[n-31] = v; ARRAY_SET_30(a, n, __VA_ARGS__)
#define ARRAY_SET_32(a, n, v, ...)  a[n-32] = v; ARRAY_SET_31(a, n, __VA_ARGS__)
#define ARRAY_SET_33(a, n, v, ...)  a[n-33] = v; ARRAY_SET_32(a, n, __VA_ARGS__)
#define ARRAY_SET_34(a, n, v, ...)  a[n-34] = v; ARRAY_SET_33(a, n, __VA_ARGS__)
#define ARRAY_SET_35(a, n, v, ...)  a[n-35] = v; ARRAY_SET_34(a, n, __VA_ARGS__)
#define ARRAY_SET_36(a, n, v, ...)  a[n-36] = v; ARRAY_SET_35(a, n, __VA_ARGS__)
#define ARRAY_SET_37(a, n, v, ...)  a[n-37] = v; ARRAY_SET_36(a, n, __VA_ARGS__)
#define ARRAY_SET_38(a, n, v, ...)  a[n-38] = v; ARRAY_SET_37(a, n, __VA_ARGS__)
#define ARRAY_SET_39(a, n, v, ...)  a[n-39] = v; ARRAY_SET_38(a, n, __VA_ARGS__)
#define ARRAY_SET_40(a, n, v, ...)  a[n-40] = v; ARRAY_SET_39(a, n, __VA_ARGS__)
#define ARRAY_SET_41(a, n, v, ...)  a[n-41] = v; ARRAY_SET_40(a, n, __VA_ARGS__)
#define ARRAY_SET_42(a, n, v, ...)  a[n-42] = v; ARRAY_SET_41(a, n, __VA_ARGS__)
#define ARRAY_SET_43(a, n, v, ...)  a[n-43] = v; ARRAY_SET_42(a, n, __VA_ARGS__)
#define ARRAY_SET_44(a, n, v, ...)  a[n-44] = v; ARRAY_SET_43(a, n, __VA_ARGS__)
#define ARRAY_SET_45(a, n, v, ...)  a[n-45] = v; ARRAY_SET_44(a, n, __VA_ARGS__)
#define ARRAY_SET_46(a, n, v, ...)  a[n-46] = v; ARRAY_SET_45(a, n, __VA_ARGS__)
#define ARRAY_SET_47(a, n, v, ...)  a[n-47] = v; ARRAY_SET_46(a, n, __VA_ARGS__)
#define ARRAY_SET_48(a, n, v, ...)  a[n-48] = v; ARRAY_SET_47(a, n, __VA_ARGS__)
#define ARRAY_SET_49(a, n, v, ...)  a[n-49] = v; ARRAY_SET_48(a, n, __VA_ARGS__)
#define ARRAY_SET_50(a, n, v, ...)  a[n-50] = v; ARRAY_SET_49(a, n, __VA_ARGS__)
#define ARRAY_SET_51(a, n, v, ...)  a[n-51] = v; ARRAY_SET_50(a, n, __VA_ARGS__)
#define ARRAY_SET_52(a, n, v, ...)  a[n-52] = v; ARRAY_SET_51(a, n, __VA_ARGS__)
#define ARRAY_SET_53(a, n, v, ...)  a[n-53] = v; ARRAY_SET_52(a, n, __VA_ARGS__)
#define ARRAY_SET_54(a, n, v, ...)  a[n-54] = v; ARRAY_SET_53(a, n, __VA_ARGS__)
#define ARRAY_SET_55(a, n, v, ...)  a[n-55] = v; ARRAY_SET_54(a, n, __VA_ARGS__)
#define ARRAY_SET_56(a, n, v, ...)  a[n-56] = v; ARRAY_SET_55(a, n, __VA_ARGS__)
#define ARRAY_SET_57(a, n, v, ...)  a[n-57] = v; ARRAY_SET_56(a, n, __VA_ARGS__)
#define ARRAY_SET_58(a, n, v, ...)  a[n-58] = v; ARRAY_SET_57(a, n, __VA_ARGS__)
#define ARRAY_SET_59(a, n, v, ...)  a[n-59] = v; ARRAY_SET_58(a, n, __VA_ARGS__)
#define ARRAY_SET_60(a, n, v, ...)  a[n-60] = v; ARRAY_SET_59(a, n, __VA_ARGS__)
#define ARRAY_SET_61(a, n, v, ...)  a[n-61] = v; ARRAY_SET_60(a, n, __VA_ARGS__)
#define ARRAY_SET_62(a, n, v, ...)  a[n-62] = v; ARRAY_SET_61(a, n, __VA_ARGS__)
#define ARRAY_SET_63(a, n, v, ...)  a[n-63] = v; ARRAY_SET_62(a, n, __VA_ARGS__)
#define ARRAY_SET_64(a, n, v, ...)  a[n-64] = v; ARRAY_SET_63(a, n, __VA_ARGS__)

#define ARRAY_APPEND_N(array, count, ...)                           \
    do {                                                            \
        array_data_type *const _base = array_grow_by(array, count); \
        ARRAY_SET_N(_base, count, __VA_ARGS__);                     \
    } while(0)
Run Code Online (Sandbox Code Playgroud)

然后你可以把你的简单函数写成

void simple_function(array_type *array,
                     const array_data_type a, const array_data_type b,
                     const array_data_type c, const array_data_type d)
{
    ARRAY_APPEND_N(array, 15, a,   b,   a+b, d,   c,
                              c,   c,   c+d, b+d, a,
                              a+c, b+c, c+d, c+d, c);
}
Run Code Online (Sandbox Code Playgroud)

并将其预处理(缩进除外)

void simple_function(array_type *array,
                     const array_data_type a, const array_data_type b,
                     const array_data_type c, const array_data_type d)
{
    do {
        array_data_type *const _base = array_grow_by(array, 15);
        _base[15 - 15] = a;
        _base[15 - 14] = b;
        _base[15 - 13] = a+b;
        _base[15 - 12] = d;
        _base[15 - 11] = c;
        _base[15 - 10] = c;
        _base[15 -  9] = c;
        _base[15 -  8] = c+d;
        _base[15 -  7] = b+d;
        _base[15 -  6] = a;
        _base[15 -  5] = a+c;
        _base[15 -  4] = b+c;
        _base[15 -  3] = c+d;
        _base[15 -  2] = c+d;
        _base[15 -  1] = c;
    } while(0);
}
Run Code Online (Sandbox Code Playgroud)

这通常可编译为Intel/AMD64架构(以及支持相对寻址模式的其他架构)上的出色机器代码.在其他一些体系结构中,最好不要使_base常量,而是自动增量(*(_base++) = v;).

如果实现PP_NARG()宏来计算宏参数的数量,则可以添加宏

#define ARRAY_APPEND(array, ...) ARRAY_APPEND_N(array, PP_NARG(__VA_ARGS__), __VA_ARGS__)
Run Code Online (Sandbox Code Playgroud)

在这种情况下,您的功能简化为

void simple_function(array_type *array,
                     const array_data_type a, const array_data_type b,
                     const array_data_type c, const array_data_type d)
{
    ARRAY_APPEND(array, a,   b,   a+b, d,   c,
                        c,   c,   c+d, b+d, a,
                        a+c, b+c, c+d, c+d, c);
}
Run Code Online (Sandbox Code Playgroud)

在某些编译器中,预处理器宏参数的数量限制为64,这限制了单个宏可以添加到62的最大元素数.根据您使用的编译器,您可以扩展宏以支持更多的参数,但其他编译器可能会扼杀这些.

  • @Michas:没有*"可能"*关于它; 它适用于C99预处理器,我已经检查过了.为什么不在你的问题中添加你的额外要求,比如*"我只会考虑我认为漂亮和粉红色的答案"？ (4认同)
  • 这可能有用但不优雅. (2认同)

250*_*501 6

必须完成一些代码重构.

首先,您需要一个与函数push_to_array类似的辅助函数,但是这个函数只为元素分配新的内存:

static inline bool increase_size(struct array_of_a_type *a, size_t size)
{
    const size_t new_size = a->elements + size;
    if (new_size > a->allocated_size) {
        a_type *tmp = realloc(a->array, new_size * sizeof(a_type));
        if (!tmp) {
            return true;
        } else {
            a->array = tmp;
            a->allocated_size = new_size;
        }
    }
    a->elements = new_size;
    return false;
}
Run Code Online (Sandbox Code Playgroud)

巧合的是,必须更改函数push_to_array以避免代码重复:

static bool push_to_array(struct array_of_a_type *a, a_type *new_chunk, size_t size)
{
    bool failed = increase_size( a , size );
    if( failed )
    {
        return failed;
    }
    memcpy(a->array + ( a->elements - size ), new_chunk, size * sizeof(a_type));
    return false;
}
Run Code Online (Sandbox Code Playgroud)

现在,simple_function非常容易编写,无需使用临时数组:

bool simple_function(struct array_of_a_type *my_array, int a, int b, int c, int d)
{
    bool failed = increase_size( my_array , 15 );
    if( failed )
    {
        return failed;
    }

    size_t i = my_array->elements - 15;
    my_array->array[i] = a;
    my_array->array[i+1] = b;
    my_array->array[i+2] = a+b;
    my_array->array[i+3] = d;
    //... write the rest of the assignments
    my_array->array[i+14] = c;

    return false;
}
Run Code Online (Sandbox Code Playgroud)

  • 我会建议同样的答案.非常明确的解决方案.构建到位而不是创建临时.@Michas这不是元编程,因为答案的所有者说,只是重构你的代码. (2认同)

Jac*_*all 4

你对你的数组在堆栈上感到生气simple_function吗a_type？那是因为您将其设置为一个数组，并[]在堆栈上创建了它。您需要像这样制作数组：

a_type *ap = malloc(<size> * sizeof(a_type));
atype[0] = a;
...
Run Code Online (Sandbox Code Playgroud)

然后你就可以return ap在最后。

此外，您可能希望一次将一个成员推送到数组，这样您就可以保留静态数组，然后执行以下操作：

int i;
for (i = 0; i < <size>; i++)
    push_to_array(&my_array, new[i]);
Run Code Online (Sandbox Code Playgroud)

并让你的push_to_array函数稍微改变一下。

可以在此处找到推送堆栈的实现，请注意，增长函数处理重新分配：https://github.com/minshallj/my_clib/blob/master/stack.c#L24-L31您应该能够调整这到你的数组“类”。

另外，my_array全局变量是否存在于程序中的其他位置？我没有看到它在任何地方声明。

归档时间：

查看次数：

648 次

最近记录：

8 年，11 月 前
相关归档
C的智能指针/安全内存管理？ 43
是否有一个常量来定义long或整数的最大值？ 26
为什么Arrays.equals(char [],char [])比其他所有版本快8倍？ 24
在C中使用STRUCT时的命名约定 20
如何在没有循环的情况下初始化散列中的值？ 17
用于计算有向图上非循环路径数的快速算法 10
如何在numpy数组中的元素之间插入零？ 8
将BYTE缓冲区(0-255)转换为浮点缓冲区(0.0-1.0) 7
有什么工具可以优化 C 中的结构大小吗？ 5
C99标准中的默认参数促销 4
难疑归档
如何从异步调用返回响应？ 5208
使用Git将最近的提交移动到新分支 4647
如何更改一个特定提交的提交作者？ 1949
PHP'foreach'如何实际工作？ 1926
JavaScript切断/切片/修剪字符串中的最后一个字符 1840
如何在Python中删除尾部换行符？ 1593
如何离开/退出/停用python virtualenv？ 1461
为什么文本文件以换行符结尾？ 1375
有条件地申请课程的最佳方式是什么？ 1172
如何将包含文件的文件夹复制到Unix/Linux中的另一个文件夹？ 1145