Live data from Hacker News

Generic Containers in C: Vec

uecker.codeberg.page

81–90 of 91 posts

Re: Generic Containers in C: Vec

#81
post #80
post #9

Earlier quoted context omitted.

Correct, complex types must be typedef'd. At least, until c2y integrates _Record as per N3332: https://thephd.dev/_vendor/future_cxx/papers/C%20-%20_Record...

I am not terribly excited about this proposal. It is overly complex.

I agree, but the current specification is complex too: two identical "tagged" structs are compatible, two identical "untagged" structs are not. And before C23 it was even worse, depending on whether the two structs were defined in the same file or not.

We're applying a patch over a patch over a patch... no surprise the end result looks like a patchwork!

Re: Generic Containers in C: Vec

#82
post #80

Earlier quoted context omitted.

I am not terribly excited about this proposal. It is overly complex.

I agree, but the current specification is complex too: two identical "tagged" structs are compatible, two identical "untagged" structs are not. And before C23 it was even worse, depending on whether the two structs were defined in the same file or not. We're applying a patch over a patch over a patch... no surprise the end result looks like a patchwork!

Sure, but _Record would add even more complexity. The tag rules I had changed in C23 were a step to remove complexity, so a step towards cleaning it up. I wasn't able to fix the untagged case, because WG14 had concerns, but I think these can be addressed, making another step. It is always much harder to undo complexity than to add it.

Re: Generic Containers in C: Vec

#83

Earlier quoted context omitted.

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…

The name has to be ugly, new names in C are always taken from the set of reserved identifiers: those starting with an underscore & a capital letter, or with two underscores. Since they didn't reserve any "normal" names, all new keywords will be stuff like `_Keyword` or `__keyword`, unless they break backwards compatibility. And they really hate breaking backwards compatibility, so that's quite unlikely.

The problem is not the _G, the problem is the "generic". It is a completely wrong name for what it does.

Re: Generic Containers in C: Vec

#84

Earlier quoted context omitted.

The name has to be ugly, new names in C are always taken from the set of reserved identifiers: those starting with an underscore & a capital letter, or with two underscores. Since they didn't reserve any "normal" names, all new keywords will be stuff like `_Keyword` or `__keyword`, unless they break backwards compatibility. And they really hate breaking backwards compatibility, so that's quite unlikely.

The problem is not the _G, the problem is the "generic". It is a completely wrong name for what it does.

This is an old tradition in ISO C. unsigned actually means modulo and const actually means immutable.

Re: Generic Containers in C: Vec

#85
post #69
post #58

Earlier quoted context omitted.

If the templates are monomorphized, each instantiation of a templated function will have a different address. To acquire the address of any given instantiation we need a symbol in the object file.

What isn't clear to me why one would ever want monomorphization in the first place.

Not ever wanting monomorphization seems like a bit of a strong claim to me. Why do you take that position?

Re: Generic Containers in C: Vec

#86
post #40

Earlier quoted context omitted.

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…

As you said in the article, the reason is performance and that stands even if a realloc implementation is not poor.

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?

Re: Generic Containers in C: Vec

#87
post #40

Earlier quoted context omitted.

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…

As you said in the article, the reason is performance and that stands even if a realloc implementation is not poor. 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 ca…

When I implemented this, I did some minimal benchmarking. Realloc was easily fast enough to cover all my use cases. I am not Facebook who need to optimize the single last byte of their string type. For the fast case, there is the alternative API which allows one to keep track of the capacity, without having the cost of storing it in the type.

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

Re: Generic Containers in C: Vec

#88
post #69

Earlier quoted context omitted.

What isn't clear to me why one would ever want monomorphization in the first place.

Not ever wanting monomorphization seems like a bit of a strong claim to me. Why do you take that position?

I was asking the question why one would ever want it.

Re: Generic Containers in C: Vec

#89

Earlier quoted context omitted.

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

Why should reference counting be a last resort?

... in C++. Because, at least in C++, it is a bad, slow and inconvenient GC. If you want or need generalized GC there are significantly better languages for that.

Re: Generic Containers in C: Vec

#90
post #88

Earlier quoted context omitted.

Not ever wanting monomorphization seems like a bit of a strong claim to me. Why do you take that position?

I was asking the question why one would ever want it.

Right. I had interpreted you asking that question as you having taken that position and soliciting responses for a discussion. Seems that was an improper reading.
Post reply on HN