TechPulseTechPulse
Back to News
Advertisement
Advertisement

⚡ Community Insights

Discussion Sentiment

87% Positive

Analyzed from 828 words in the discussion.

Trending Topics

#array#struct#capacity#type#len#same#using#need#int#clever

Discussion (21 Comments)Read Original on HackerNews

flohofwoe•9 minutes ago
The most idiomatic and elegant 'dynamic array in C' solution is stb_ds.h, it's as simple as that :)

The 'public handle' is a pointer to the array elements so it has the same semantics as a regular C array, the meta-data (capacity and length) are stored directly in front of the array items. Growing the array has the same behaviour as realloc (e.g. you may get a new pointer back).

procaryote•about 1 hour ago
Why would you want to avoid using a struct? Add a macro that declares the appropriate struct and get at least a tiny bit of type checking.

With some clever use of _Generic you could even build specialised functions for that type and get pretty good type checking

sparkie•about 1 hour ago
In C23 this approach is nice, but in older versions of C we end up with awful macros where we need to define the structure before we use it.

    #define Array(T) struct array_##T
    #define DEFINE_ARRAY(T) struct array_##T { size_t len; T *elems; }
    
    DEFINE_ARRAY(int);
    Array(int) foo;
    Array(int) bar;
C23 has relaxed rules for redefining the same struct, so we can avoid having to create the struct up front.

    #define Array(T) struct array_##T { size_t len; T *elems; }

    Array(int) foo;
    Array(int) bar;
t-3•about 3 hours ago
No structs, just an array that accomplishes the same thing, without field names or other niceties. Enjoy the pleasure of not using a struct when you inevitably add/reduce/reorder fields later.
hibberl7•about 2 hours ago
Yeah this is nuts. It's like someone just discovered casting so they can be really clever and use the first pointer in an array for something non-pointy.

I can't make any sense of the aversion to a struct. Use a struct. You don't have to give its type a name, if that's the motivation here.

sparkie•about 1 hour ago
The reason the struct is avoided here is so the array can be typed to its element type (rather than casting to and from `void*`).

With a struct we would need one struct for each element type - at least prior to C23 which provides a better approach where we can declare the same struct multiple times in a translation unit.

    #define Array(T) struct array_##T { size_t len; T *elems; }
We can use `Array(int)` in multiple places in the same TU - but in C11 or earlier, this is an error.
dwroberts•about 1 hour ago
> First of all, structs aren't used so you don't have to invent names for them (e.g. there is no IntVec)

But since it’s storing a void pointer any way, they wouldn’t need separate names right? You could use one struct everywhere regardless of the type of the items

Which IMO is a better idea than using an array here because the fields can be properly named and typed to prevent accidental misuse

sparkie•44 minutes ago
If you use a struct with a `void*`, you also need to specify the type on usage, where here it's done with `typeof`.
gritzko•about 3 hours ago
https://github.com/gritzko/libabc/blob/main/Sx.h

https://github.com/gritzko/libabc/blob/main/S.md

ABC uses s[2] for slices, g[3] for gauges, b[4] for (ring) buffers. Also containers on top of those (heaps, hash sets, etc etc)

userbinator•about 2 hours ago
capacity isn't stored at all. Instead, it's computed on demand when the length of the vec is either zero or a power of two.

Brilliant insight. This is the first time I've seen this observation in over 3 decades of working with C.

OskarS•28 minutes ago
It doesn’t really work though for generic vectors. If you support not just vec_push but vec_pop as well, then you really do need to store capacity separately or else call realloc way more often than you normally need to.
sparkie•about 1 hour ago
Really? It's been done plenty and I thought was quite common knowledge. Some of the <stdbit.h> provided functions are basically for this purpose.

stdc_bit_ceil(len) gets the smallest power of 2 not less than len, which is our capacity. This is usually implemented with a clz instruction.

stdc_has_single_bit(len) determines if it's a power of 2 - typically implemented with a popcount instruction (popcount(len)==1).

The approach isn't used in older (90s and earlier) texts because hardware support for popcount/clz wasn't commonplace and the cost to do it in software wasn't worth it, but it is mentioned in some texts.

OskarS•26 minutes ago
Everyone knows about bit-fiddling functions, what the poster was referring to is using this trick to not have to store the capacity for a dynamic vector. Which is genuinely very clever and rare, I don’t think I’ve ever seen it done quite like this either. I think that’s probably because it’s not really that good of an idea, if the vector can shrink, you really should store the capacity.
sparkie•3 minutes ago
I don't think it's that rare. I've been using the technique for years, and I've seen it done in other work. Bagwell's VList[1] for example uses the equivalent of `bit_ceil` to determine the size of each block without having to store it - and there are earlier works based on the same trick (RAOTS, which is referenced by VList mentions it, but uses a slightly more complex trick where we can calculate the size of a block based on the approx square root of the length).

You can use the trick if the array can shrink as long as you always shrink it when length goes below the next power of 2 not greater than len (which may make use of stdc_bit_floor).

[1]:https://cl-pdx.com/static/techlists.pdf

astrobe_•about 1 hour ago
I think it was sarcasm. I have about as much experience as them in low-level C programming, and I was wondering why this is on front page. I've also discovered again a few things too, so I won't look down on OP. It's certainly better than vibe coding.
userbinator•33 minutes ago
No, I'm being serious.

I know about XOR-linked lists and a few other tricks for very efficient memory usage in embedded systems, but it's my first time seeing implicit allocation lengths.

dooglius•about 2 hours ago
Strictly speaking, the capacity is still stored internally to the allocation (it needs to be, in order to implement realloc)
Akronymus•about 2 hours ago
That's pretty clever code. Too clever for my tastes.
lefra•about 1 hour ago
Enjoy the annoying-to-debug errors when someone inevitably mixes arr[0] with arr[1] and tramples the heap (this could be mitigated by accessing the fields with macros), or writes arr[3] because they forgot this is not a regular array.
senderista•about 2 hours ago
This is just silly. You can't even reserve capacity because you only store size and capacity is implicitly the next power of 2 >= size.
sparkie•about 1 hour ago
The concept of not storing capacity isn't silly. If you need to reserve space then it's not the appropriate structure, but it's otherwise fine.

However, using an 2-element array to avoid using a struct is silly.