Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Generic Containers in C: Vec

uecker.codeberg.page

Post reply on HN
Print view View original

31–40 of 91 posts

Re: Generic Containers in C: Vec

#31

Post by ioasuncvinvaer »

sirwhinesalot wrote: post #24
cyber1 wrote: post #22

Many C programmers need proper generic programming mechanisms (perhaps something like Zig's comptime) in C, but macros are the worst possible approach, and they don't want to switch to a different language like C++. As a result, they struggle with these issues. This is what I think the standardization committee should focus on, but instead, they introduced _Generic.

The most insulting thing about _Generic is the name. Really? _Generic? For a type-based switch with horrific syntax? What were they thinking... 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…

username checks out

Re: Generic Containers in C: Vec

#32

Post by uecker »

gsliepen wrote: post #20

It's amazing how many people try to write generic containers for C, when there is already a perfect solution for that, called C++. It's impossible to write generic type-safe code in C, and this version resorts to using GCC extensions to the language (note the ({…}) expressions). 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 por…

Except that I find C++ far from being perfect. In fact, I switched from C++ to C (a while ago) to avoid its issues and I am being much happier I also find my vec(int) much nicer.

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.

Re: Generic Containers in C: Vec

#33

Post by cyber1 »

uecker wrote: post #29
cyber1 wrote: post #22

Many C programmers need proper generic programming mechanisms (perhaps something like Zig's comptime) in C, but macros are the worst possible approach, and they don't want to switch to a different language like C++. As a result, they struggle with these issues. This is what I think the standardization committee should focus on, but instead, they introduced _Generic.

I don't struggle, I switch from C++ to C and find this much nicer.

I'm currently at a crossroads: C++ or Zig. One is very popular with a large community, amazing projects, but has lots of ugly design decisions and myriad rules you must know (this is a big pain, it seems like even Stroustrup can't handle all of them). The other is very close to what I want from C, but it's not stable and not popular.

Re: Generic Containers in C: Vec

#34

Post by uecker »

cyber1 wrote: post #33
uecker wrote: post #29

Earlier quoted context omitted.

I don't struggle, I switch from C++ to C and find this much nicer.

I'm currently at a crossroads: C++ or Zig. One is very popular with a large community, amazing projects, but has lots of ugly design decisions and myriad rules you must know (this is a big pain, it seems like even Stroustrup can't handle all of them). The other is very close to what I want from C, but it's not stable and not popular.

Why not C?

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.

Re: Generic Containers in C: Vec

#35

Post by im3w1l »

uecker wrote: post #17
tialaramex wrote: post #13

Earlier quoted context omitted.

> realloc often does this already internally 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.

No, I claim that the performance of realloc is good enough for most use cases because it also does not move the memory in case there is already enough space left. 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.

I think it's a very interesting design choice. I haven't read the code, so maybe you already thought of this, but one idea that comes to mind is that instead of reallocing new_size, you realloc f(new_size) where f is some function that rounds up to discrete steps. This should ensure good asymptotics as realloc can then realize that the requested allocation size is identical to the current one and nothing needs to be done.

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.

Re: Generic Containers in C: Vec

#36

Post by swinglock »

uecker wrote: post #28
tialaramex wrote: post #25

Earlier quoted context omitted.

I think the claim that it's good enough for "most use cases" to have an O(n) growable array container needs some serious backing data.

If I have some time, I will do some benchmarking. 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.

Popular allocators will indeed grow your allocation in-place without moving when possible. This is essentially the same as if you'd tracked it yourself in your vector and grown it once in a while, though it will work with bytes instead of number of items. See for instance the size classes in jemalloc at https://jemalloc.net/jemalloc.3.html. If you ask for 1 byte, you actually have 8 bytes, so realloc within the same size class will be cheap compared to actually moving.

Re: Generic Containers in C: Vec

#37

Post by gpderetta »

serbuvlad wrote: post #21
gsliepen wrote: post #20

It's amazing how many people try to write generic containers for C, when there is already a perfect solution for that, called C++. It's impossible to write generic type-safe code in C, and this version resorts to using GCC extensions to the language (note the ({…}) expressions). 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 por…

My problem with C++, and maybe this is just me, is RAII. 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…

Your problem is not with RAII, but with reference counting, which you correctly identified should be the last resort, not the default; at least for the applications typically written in C++.

Re: Generic Containers in C: Vec

#39

Post by uecker »

im3w1l wrote: post #35
uecker wrote: post #17

Earlier quoted context omitted.

No, I claim that the performance of realloc is good enough for most use cases because it also does not move the memory in case there is already enough space left. 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.

I think it's a very interesting design choice. I haven't read the code, so maybe you already thought of this, but one idea that comes to mind is that instead of reallocing new_size, you realloc f(new_size) where f is some function that rounds up to discrete steps. This should ensure good asymptotics as realloc can then realize that the requested allocation size is identical to the current one and nothing needs to be…

Yes!

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.

Re: Generic Containers in C: Vec

#40

Post by uecker »

swinglock wrote: post #36
uecker wrote: post #28

Earlier quoted context omitted.

If I have some time, I will do some benchmarking. 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.

Popular allocators will indeed grow your allocation in-place without moving when possible. This is essentially the same as if you'd tracked it yourself in your vector and grown it once in a while, though it will work with bytes instead of number of items. See for instance the size classes in jemalloc at https://jemalloc.net/jemalloc.3.html . If you ask for 1 byte, you actually have 8 bytes, so realloc within the same…

Exactly! Why would I want to add my own memory management logic on top of the memory management logic that already exist.

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...

Post reply on HN