Generic Containers in C: Vec
uecker.codeberg.page
uecker.codeberg.page
I think this is the wrong decision (for a generic array library).
Is Martin claiming that realloc is "often" maintaining a O(1) growable array for us?
That's what the analogous types in C++ or Rust, or indeed Java, Go, C# etc. provide.
I then mention that for other use cases, you can maintain a capacity field only in the part of the code where you need this.
Whether this is the right design for everybody, I do not know, but so far it is what I prefer for myself.
In all my current code where I tried it makes no noticeable difference, and I am not a fan of premature optimization. But then, I could always switch to the alternative API.
One valid reason might be that I can't rely on realloc not be poor, but then I would rather use my own special allocation function. Other valid reasons would be to have very precise control or certain guarantees, but then I would prefer a different interface. In any case, I do not think that this logic belongs into my vector. But it is also possible that I change my mind on this...
It can't preallocate, so when adding many items it will make many expensive realloc calls that could have been avoided. Though you could have an interface that allows pushing or popping many items at once to make up for it, but this is less convenient.
You can currently forgo shrinking on pop but you can't if mixing popping and pushing. You need to know the capacity for that, otherwise it may actually shrink on a consequent push. This could incur many expensive reallocs if used similarly to a stack.
Even the cheap realloc calls will cost more than checking an int in code that's likely small, inlined, and with its data in one cache line (number of items and capacity next to each other in one struct, which are also next to the first item). The realloc function is probably dynamically linked, more complex, and has to access additional data.
If you don't want to add more memory overhead to the vector, consider just using two ints and it won't be any larger, that's enough unless a vector should be many gigabytes. Otherwise if you think that's not enough and feel like leaning into the complexity instead, use bit fields or bit twiddling to split up one 64 bit int into say, 56+8 bit ints. Let the smaller int track additional capacity rather than total capacity and also use that to solve your hysteresis problem. Well, or just use two 64 bit ints, but what's the fun in that?
But realloc also does overallocate a little bit, and for large blocks it would remap the pages. The inlining argument makes sense though. (Edit: Pushing and then popping a billion integers takes about 2 seconds with std::vector<int>, 10 with vec(int) and realloc each time, and 4.3 seconds with a simple preallocation logic that does not require a capacity on my laptop. Having a call to "rand" in it already adds more overhead.).
However one possible issue is if someone pushes and pops repeated just at the boundary where f increases in value. To address that you would have to use more advanced techniques, and I think "cheat" by inspecting internal structures of the allocator.
Edit: malloc_usable_size could be used for this purpose I think.
I try do this here (this code is not tested and may not be up-to-date): https://github.com/uecker/noplate/blob/main/src/vec.h#L30
The issue with the boundary is what I meant with hysteresis in the article.
That said, generic programming in C isn't that bad, just very annoying.
To me the best approach is to write the code for a concrete type (like Vec_int), make sure everything is working, and then do the following:
A macro Vec(T) sets up the struct. It can then be wrapped in a typedef like typedef Vec(int) Vec_i;
For each function, like vec_append(...), copy the body into a macro VEC_APPEND(...).
Then for each relevant type T: copy paste all the function declarations, then do a manual find/replace to give them some suffix and fill in the body with a call to the macro (to avoid any issues with expressions being executed multiple times in a macro body).
Is it annoying? Definitely. Is it unmanageable? Not really. Some people don't even bother with this last bit and just use the macros to inline the code everywhere.
Some macros can delegate to void*-based helpers to minimize the bloating.
EDIT: I almost dread to suggest this but CMake's configure_file command works great to implement generic files...
The first is to put this into an include file
#define type_argument int
#include <vector.h>
foo_ ## type_argument ( ... )
I do not think that templates are less annoying in practice. My experience with templates is rather poor.
Sometimes the best option is an external script to instantiate a template file.
BTW, here is some generic code in C using a variadic type. I think this quite nice. https://godbolt.org/z/jxz6Y6f9x
Running a program for meta programming are always a possibility, and I would agree that sometimes the best solution.
T ## _foo (T foo, ...)
<T>::foo (T foo, ...)
foo (Object * a)
foo (void * a) #include <vector.h(int32_t)>
#include <vector.h(int64_t)>
Eg, if `vector.h(type_argument)` was an m4 file containing:
`#ifndef VECTOR_'type_argument`_INCLUDED'
`#define VECTOR_'type_argument`_INCLUDED'
typedef struct `vector_'type_argument {
size_t length;
type_argument values[];
} `vector_'type_argument;
...
#endif
#ifndef VECTOR_int32_t_INCLUDED
#define VECTOR_int32_t_INCLUDED
typedef struct vector_int32_t {
size_t length;
int32_t values[];
} vector_int32_t;
...
#endif
Its only real issue is that people will constantly tell you how bad it is and how their language of choice is so much better. But if you look at how things work out in practice, you can usually do things very nicely in C.
Perfect hashing that you’d ideally use two different approaches for depending on whether the platform has a cheap popcount (hi AArch32), but to avoid complicating the build you give up and emulate popcount instead. Hundreds of thousands of lines of asynchronous I/O code written in a manual continuation-passing style, with random, occasionally problematic blocking synchronization sprinkled all over because the programmer simply could not be bothered anymore to untangle this nested loop, and with a dynamic allocation for each async frame because that’s the path of least resistance. The intense awkwardness of the state-machine / regular-expression code generators, well-developed as they are. Hoping the compiler will merge the `int` and `long` code paths when their machine representations are identical, but not seeing it happen because functions must have unique addresses. Resorting to .init_array—and slowing down startup—because the linker is too rigid to compute this one known-constant value. And yes, polymorphic datastructures.
I don’t really see anybody do noticeably better than C; I think only Zig and Odin (perhaps also Hare and Virgil?) are even competing in the same category. But I can’t help feeling that things could be much better. Then I look at the graveyard of attempted extensions both special-purpose (CPC[1]) and general (Xoc[2]) and despair.
Many example I see where people argue for metaprogramming features are not all convincing to me. For example, there was recently a discussion about Zig comp-time. https://news.ycombinator.com/item?id=44208060 This is the Zig example: https://godbolt.org/z/1dacacfzc Here is the C code: https://godbolt.org/z/Wxo4vaohb
Or there was a recent example where someone wanted to give an example for C++ coroutines and showed pre-order tree traversal (which I can't find at the moment), but the C code using vec(node) IMHO was better: https://godbolt.org/z/sjbT453dM compared to the C++ coroutine version: https://godbolt.org/z/fnGzszf3j (from https://news.ycombinator.com/item?id=43831628 here). Edited to add source.
That's also a major reason why you'd use C rather than C++. The C++ ABI is terrible for language interoperability. It's common for C++ libraries to wrap their API in C so that it can be used from other language's FFIs.
Aside from that another reason we prefer C to C++ is because we don't want vtables. I think there's room for a `C+` language, by which I mean C+templates and not C+classes - perhaps with an ABI which is a subset of the C++ ABI but superset of the C ABI.
indeed, i have spoken to a lot of my colleagues about just that. if overloading is not allowed, perhaps there is still some hope for a backwards compatible abi ?
We might be able to make this ABI compatible with C if no templates are used, which wouldn't cause breaking changes - but for other compilers to be able to use templates they would need to opt-in to the new scheme. For that we'd probably want to augment libffi to include completely new functions for dealing with templates. Eg, we'd have an ffi_template_type, and an ffi_prep_template for which we supply its type arguments - then an ffi_prep_templated_cif for calls which use templates, and so forth. It would basically be a new API - but probably still more practical than trying to support the C++ ABI.
Another issue is that if we compile some library with templates and expose them in the ABI, we need some way to instantiate the template with new types which were not present when the library was compiled. There's no trivial solution to this. We'd really need to JIT-compile the templates.
may you please elaborate on _why_ you think this is needed ?
Then don't use virtual functions. Then there will be no vtables.
You might have known that already, but in general I'm surprised how many engineers think that all C++ classes have vtables. No, most in fact do not. C++ classes generally have the same memory layout as a C struct as long as you don't use virtual functions.
It's perfectly possible to do generic vectors in C without twisting the language. This implementation isn't as safe as alternatives in other languages, but plays well on C's strengths.
If you want that level of safety, why not use a language that provides it for you?
It is also not clear how you get tap completion with code generation. But you could also get tab completion here, somebody just has to add this to the tab completion logic.
struct Vec {
void *data;
size_t len;
size_t cap;
size_t sizeof_ty;
}
IntVec {
struct Vec inner;
int ty[0];
}
All of the methods are implemented on the base Vec type and have a small wrapper which casts/assets the type of the things you are trying to push.
E.g. in production code this
if (!vec_ptr) // memory out
abort();
for (int i = 0; i < 10; i++)
vec_push(int, &vec_ptr, i);
if (!vec_ptr) // memory out
abort();
for (int i = 0; i < 10; i++)
if (! vec_push(int, &vec_ptr, i))
abort();
For those afraid of C++: you don't have to use all of it at once, and compilers have been great for the last few decades. You can easily port C code to C++ (often you don't have to do anything at all). Just try it out and reassess the objections you have.
Now, Resource Aquisition Is Initialization is correct, but the corollary is not generally true, which is to say, my variable going out of scope does not generally mean I want to de-aquire that resource.
So, sooner or later, everything gets wrapped in a reference counting smart pointer. And reference counting always seemed to me to be a primitive or last-resort memory managment strategy.
But it does! When an object goes out of scope, nobody can/shall use it anymore, so of course it should release its (remaining) resources. If you want to hold on the object, you need to revisit its lifetime and ownership, but that's independent from RAII.
Same thing as what Rust does with `String` and `str`.
In fact, we are at the moment ripping out some template code in a C code base which has some C++ for cuda in it, and this one file with C++ templates almost doubles the compilation time of the complete project (with ~700 source files). IMHO it is grotesque how bad it is.
We're applying a patch over a patch over a patch... no surprise the end result looks like a patchwork!
A neat project that was posted here a while back uses it: https://x.com/kotsoft/status/1792295331582869891
If you have two dependencies in C which both use the same generic container macros, and both instantiate vec(int) you'll fail-out with redefinition errors.
His code is here: https://github.com/drh/cii
Instead, what is missing is an automatic deallocator, one that's automatically called when the variable goes out of scope. For example:
{
vec(int) v={}; /* no extra room allocated */
vec_push(v,1); /* space allocated */
... use v ...
} /* here the space is dellocated, then v is released */
#define ARRAY(T,S) T S;size_t S##_length;size_t S##_capacity
ARRAY(int,xs);
#define ARRAY_INIT(S) \
do { \
S=NULL; \
(S##_length)=0; \
(S##_capacity)=0; \
} while(0)
#define ARRAY_DESTROY(S) \
do { \
Array_Free(S); \
ARRAY_INIT(S); \
} while(0)
#define ARRAY_ADD(S,X) \
do { \
if((S##_length)>=(S##_capacity)) { \
S=Array_Grow(S, \
sizeof *S, \
&(S##_length), \
&(S##_capacity)); \
} \
S[S##_length++]=(X); \
} while(0)
ARRAY(int,xs);
ARRAY_INIT(xs);
for(int i=0;i<100;++i)
ARRAY_ADD(xs,i);
ARRAY_DESTROY(xs);
void Array_Free(void *p) {
free(p);
}
void *Array_Grow(void *base,size_t stride,size_t *length,size_t *capacity) {
*capacity+=*capacity/2;
*capacity=MAX(*capacity,MAX(MIN_CAPACITY,*length));
return realloc(base,*capacity*stride);
}
for(size_t i=0;i<xs_length;++i) {
printf("%d\n",xs[i]);
}
#define ARRAY_LENGTH(S) (S##_length)
For a full implementation you'll probably also need a way of generating a static array. (I mainly found myself needing this for test code, which uses globals for convenience; most arrays I create normally are locals, or parts of structs.)
You'll also need a parameters list for use in a function declaration or definition, and a macro that expands to all 3 variables.
#define ARRAY_PARAMS(T,S) T *S,size_t S##_length,size_t S##_capacity
#define ARRAY_ARG(S) S,S##_length,S##_capacity
void FunctionThatTakesAnArray(ARRAY_PARAMS(T,*p));
ARRAY(T,myarray);
FunctionThatTakesAnArray(ARRAY_ARG(&myarray));
There's more you can do, but the above is the long and the short of it.
This might all look terrible - or perhaps it sort of looks OK, but you're just not sure that it would actually work - but I've used this in a prototype project and thought it worked out well. (I mainly do C++ nowadays, but I had a good stint of C before that. So even if I've got no taste, hopefully I've at least got a rough feel for what'll work out OK and what'll end up a disaster.)