Dynamic Arrays in C
Вставка
- Опубліковано 9 чер 2024
- Sorry about the nose-whistle. I'll have to wear one of those nose holder-opener-things next time I record.
➤ Substack: bytesbeneath.com/p/dynamic-ar...
➤ X: x.com/falconerd_
➤ GitHub: github.com/Falconerd
➤ Discord: / discord
Tools used for video:
Slides/Animations:
animotion.pages.dev
Editing:
github.com/WyattBlue/auto-editor
Shotcut
Audacity
Canva
There is a slight oversight here relating to data alignment.
If the data type requires a larger alignment than that of the platforms' pointer, then the data in the array will be misaligned. This could result in either a performance penalty or an exception.
I'm not much of a C programmer, so I'm unsure of a completely portable solution but as of C11 you can use _Alignof to figure out how much patting to add to the header.
It would also be good to allow a user to manually specify sticter alignments, incase they want to do something like declare an array of a certain type but plan to apply vector operations to it which require stricter alignment.
You're right, that's actually a pretty big oversight! Thanks for the comment - I'll have to update the written version.
Looking forward to checking out your final solution
I'm just on my lunch break, so I can't test this out, but I'm thinking for x64, we just add an extra 8 bytes of padding to make the whole header 32 bytes. That way, the array will always be aligned even for SIMD unless I'm mistaken
Well on x86-64 specifically I think a static padding approach would require 64 bytes given that types like __m512 exist.
Most intel CPUs dont currently support AVX-512 but I believe AMD has since zen 4.
Today I learned that “unordered remove” is a thing that I feel i should’ve known a long time ago.
i beg you to make a beginner-intermediate C tutorial, you are really good at explaining things.
I hope not, because there are so many C tutorials and some of them are really good, but I think there are a lack of C videos on a intermediate level for C learners like me. :o)
I really like videos, that are not using disturbing background music and no 'clever' action movie editing, but just starts like this great video although I must admit, that I use C99. :o)
Macros - so far I know, they should be a 'nightmare' to debug? The only macros I use are __file__ and __line__
I assume a C++ compiler must be gigantic compared to a C compiler...
Coming fresh off of reading the K&R book on C, This is a very informative and entertaining video. Great stuff
I use to implement the vector by 1st method in uni. I will try to implement the 2nd method as it seems nicer to me. Thanks for teaching new stuff. Hopping for more videos on complex data structures such as hash tables and balanced binary search tree in future (in C obviously 🙂).
Wow C is such a versatile language, I see why other languages are built on it
C makes it feel like moving structs around in memory would just be a matter of (uint8_t*) casting and moving the bytes, sadly this isn't always the case for most architectures.
I don't have a use case for this as I only use high level languages at work but this is so interesting. Subscribed.
The second version doesn't handle reallocation. If the client has a pointer to the array data (that comes after the header) and reallocation is needed (assuming that functionality exists), then the client must be told to update his variable to the new array data. Therefore, version 2 is a great solution for *fixed length* arrays - for instance immutable string types. Passing out "a header" is necessary when the referenced array data can be reallocated - then the client doesn't need to know when reallocations happen.
The full implementation is available at the link in the description and does handle reallocation
@@DylanFalconer Ah, I see - array_ensure_capacity will re-assign to the array macro parameter, which is possible if the parameter is an L-value
Does this handle alignment of T? What will happen if alignof(T) is bigger than alignof(Array_Header)?
i saw a similar approach done elsewhere along with the explanation on what happens under the hood (struct fields are just offsets from struct location). as far as i remember it should be ok to do this
Nice catch! This array_init should take in alignment and align to _Alignof(T) or _Alignof(Array_Header) whichever is larger. Could simply be written into the macro with _Alignof(T) > _Alignof(Array_Header) ? _Alignof(T) : _Alignof(Array_Header) and the functions allocator should take in an alignment, with the stdlib allocator there is aligned_alloc.
@@attilatorok5767 It's not just the allocator that needs this math. Every accessor needs it too since the amount of padding present in the header will depend on the type being stored.
just suscribed, well explained, thank you.
I normal do a DynamicArray_t struct to store the size of the type the count of items and other metadata with the pointer this allows the functions like get index and so on.
also the header and pointer will be in the same memory section in this case.
What are you using to make such videos. i.e. what software is that were you click around to minimize / maximize topics/headings.
Implemented one of this before with excessive use of macros to replicate templating. So, I can easily implement an 8t, 16t, 32t and 64t dynamic array
I think it is a bit dishonest to compare the compile time of a full solution as implemented by std::vector to a halfbaked example that isnt even fully functional yet. What is the compile time of your full solution compared to the std::vector version? I wouldn't be surprised if it still beats out vector, but it will no longer have the same margin of victory. Otherwise, of course the source with more code takes more time to compile. They weren't comparable.
Another question is how does the compile time scale as you use it in more and more files? Is it linear? Constant time? Quadratic? I would expect the C code to scale fairly well and the C++ code to potentially have a more dramatic effect on link times, but that precompiled headers or modules would potentially remove most of that. Though if your C code were header only to encourage the compiler to inline more aggressively, that advantage would go away.
Runtime performance should be a wash as your benchmark showed. Your version has potential cache miss for any size operations, but most of the time one is getting the size because they intend to iterate. There is more potential for optimization in std::vector because the types are all fully known, but I have some doubts that much could be done for this simple case. But the potential to inline and/or vectorize the code might favor C++ in the right situation.
I was comparing std::vector to the full solution I use in my code, not a half-baked one that isn't functional yet. You can see the lines of code in the video. Thanks for your comment!
@@DylanFalconerThat's good to hear, but it is very unclear from the video. At about 1:20 you show three lines of C that doesn't even attempt to do anything dynamic and didn't use any sort of linrary-like code. Then around 1:40 you are showing three lines of C++ using a vector, so a complete dynamic array implementation would be included in the full source listing. Then at about 2:10 you go straight to benchmarking.
At the surface level, it looks like you are unfairly stacking the deck against C++ by using a very apples to oranges comparison, so you can see why I thought the benchmark reflected the code you showed that did absolutely zero dynamic array stuff and not the code you hadn't even talked about yet.
is there any command that i can use to show the profiles of two programs at 2:56
Sick video! I learned a lot
Nice video. Unfortunately this trick does not take data alignment into consideration, which can lead to UB or performance overhead. Flexible array member would be one way to fix that.
A few months ago I played around with implementing a generic and type-safe vector in C and gotta say, it was not that much fun. Well i mean, it was fun for the learning, but the hacks you gotta do with the preprocessor ... is quite something.
That being said, implementing a simple non-generic and type safe vector in plain C is really sweat. Just like you showed in the video.
Honestly i like the tools C++ offers you, specially in the realm of generic programming. Templates can be quite powerful if you learn to not overuse it.
I suppose my point is that every language has its advantages, specially the system's one. I enjoy doing my things in C++, but also enjoy to play around with simple C from time to time.
@@apenaswellignton except nothing is ever simple C, doing trivial things requires walls of C code that more often than not is so unreadable that not even splitting a basic problem into 50 functions will make it any more clear, and all because midwits think that error that happens once in a blue moon should be checked everywhere and all the time, taking up like 75% of all code with nothing but if statements checking if function call failed.
Whereas in C++ you only need to check at lowest level and throw exception on error and it will bubble up when it happens, except I've never seen an error ever happen in my entire life. I quite literally NEVER had write(2) or something like that fail. And guess what, if C++ exception isn't ever thrown, cost of exception is 0, now instead of checking on every level of call stack, you only check once, when basic write(2) fails, performance won't be a problem either, because chances are, if it was a write to external disk, it fucking died, no amount of performance will revive it.
Files that are expected to exist also should have exception thrown over return value, return value should be reserved for files that may or may not exist, especially if there's a lot of them, then exceptions can incur a heavy cost and it's worth going out of your way with if else in some limited scope over exceptions.
In C you don't even have a basic choice like this, it's if else if else if else all the way down and a waste of everyone's time.
@@shinobuoshino5066 those if statements are pretty useful when you do encounter an unusual error though!
@@AkimboOfficial ah yes, gotta clutter up 75% of my code with pointless if elses in case once in a blue moon error that never happens will happen.
@@shinobuoshino5066Ignoring edge cases is they key to writing good and safe software. After all, there's no problem if it's working on your machine
If you need a dynamic array just to have a growing string, then you don't need any structs and allocators and anything complex, you can just use regular old char* and write a function that will reallocate each time you add something to that string: `#define APPEND(Str, Fmt, ...) asprintf(&Str, "%s" Fmt, Str, __VA_ARGS__);`
I like the brackets too. Subbed
Is there a way to reserve a bunch of memory, and have labels that point to various places in the reserved memory?
Example: label_a might point to the first slot in the reserved memory, label_a[7] points to the eightth slot in that reserved section of memory, but maybe label_b points to the sixth slot in reserved memory.
yes? That's what pointers are. You can make an array and index it
Looks like same learning pet project I done for myself - dynamic arrays for 2d game objects. Every C++ user must do it once 😊
Amazing video Sir!
Agree with the other comment: please make a beginner-intemediate C tutorial.
Or if you don't have the time to make a full series, then I would be very happy with these kinds of videos ~ C lang tips and tricks
Cheers!
Thanks. Besides all debate happening in comment section, I learned something today. That's good 😊.
In my college we had directional lists. We defined structure with a pointer to another structure of the same type and a bunch of variables. Wanna append the list? Just use the malloc function.
linked lists are way too slow to replace basic arrays like this
The thing is with object oriented code I don't think comparing line count is a valid way to determine what compile time should be.
General Kenobi
Is there a name for the color scheme you're using in this video? I find it very easy on my eyes and wish I can use it for code.
I personally find the idea of dismissing C++ solely because of compilation times completely insane.
Yes, compilation times matter, to an extent... but so do a lot of other factors, like language and standard library features, safety, ease of use...
There a legitimate reasons why you'd want to use C over C++. There are also a lot of reasons why you'd want to use C++.
The first and most obvious I can think of was actually mentionned: C++ has templates to handle type agnostic interfaces, C does not.
But also: C++ allows you to handle resource ownership with classes, using RAII, move semantics etc. C does not, it is up to the user to handle
copies, moves, destruction. This is much more error prone, and that's one of the reasons we still often go for C++, regardless of compilation times.
You find it insane because it is insane. The person who made this video clearly has no idea about business. Increased compile times will lose some amount of money to time, but you have the opportunity cost of using a much more primitive language. Which is not always worth it. I would argue that compile times could never possibly be a business reason to pick C over C++. Terrible video.
@@teranyan I wouldn't go as far as to say the video is terrible, to be fair, I find the idea interesting and useful for those who legitimately want C for a reason or another. I just wanted to point out this specific reason should absolutely not be it.
I liked the thumbnail.
Vectors were the primary reason I started using c++ instead of c I don't like the idea of hard coded limits all over the place, I will be giving this method a try I actually did assume that the optimisation of vectors would be hard to match
Amazing stuff! I have a question: what tool are you using to create this style of presentation?
Looks like you could do this easily with Google slides or PowerPoint
Thank you 🤠 I have updated the description with the tools used
Regarding the first example, I'd personally I'd use a zero size array rather than a void pointer then malloc/realloc sizeof(struct) + total size of array
Thanks for sharing! Love your C videos!
I just use alloca and malloc and keep track of the buffers using ID’s if need be.
Great stuff. I look forward to checking out your channel. Thanks. Subscribed. Cheers
Thanks for subbing
i made something like this years ago. C is actually a potentially great language if it had standard library support to make it great.
i used it mostly as a safe dynamic string type. the allocator would store the capacity and size in the header right before the null terminated string data.
Compile time is why i haven't tried to compile Linux from scratch
Hi Dylan, I am just relearning C, can you write out the implementation for the array_append function at 4:08? thank you
Hi Aaron, I have a full implementation available if you click the Substack link in the description. Cheers
Why not using or comparing with the CDS library ?
is this the same as go lang version of dynamic array which they called a slice
I believe a slice is more like a "view" into an array. So, the array is fixed size, but the slice notation allows you to "slice" it up. It's a pointer and a length. It also has some convenience functions which, I think, can reallocate the underlying array's memory
I honestly don't understand why comparing C/C++ to things like Java or other managed languages. You have to understand that C++ and to a lesser extent C are lower level languages and they do not manage memory nor does the compiler and we like it that way. I don't want the compiler thinking for me. There is a myriad of reasons why too. The nice thing about C and C++ is you can use libraries that do manage memory for you or not; you don't have that option with managed languages std::vector is a library and not the language. SO MANY PEOPLE conflate things like std::map, std::vector, etc... as C++. C++ is simply the 'if', 'for', 'switch', 'class', 'template', etc... statements. I work both in desktop, rich GUI, environment as well as in embedded. The only thing that is common between those two worlds with regard to C/C++ is the C and C++ language - not the language support libraries. #define is also a pre-compiler language statement too. You don't need #define as you show in your video and many argue you shouldn't either. Scott Meyers, as one, who recommends to prefer the compiler over the pre-compiler. Finally, the whole dynamic memory topic - you should know you can, through operator overloading, make a C++ object appear or behave just like a managed language. The main take away for anyone reading this is C/C++ is vastly more powerful because it allows one to write code as close to the metal and do more yourself or as abstract as you want.
Nice.
Thanks!
The Trick is insanely useful. I like to allocate arenas upfront and grow my arrays into them. Using The Trick you can make a system for linking arenas together and getting an "infinite" arena where you can get however many dynamic arrays you want. Very lazy, very fast, very convenient.
This is a vector
Indeed
Except a very shitty one.
I still dont get how memory allocation works in C 😔
I like this video. But I feel that zig answers pretty much all your problems. It integrates with existing c code. It has a good standard library (with growable arrays). It has custom allocator support built into the language.
Its build time isn't quite as snappy as c. But it is still about half that of c++.
The more Marcros you add in c the higher the compile time as well
@@KManAbout is the impact of macros that large? I haven't checked myself. I would guess that parsing is the bulk of the compilation time.
@nikolajolanderrasmussen9128 it can get large. Just depends on the macros you have. There's overhead to everything. You can also look at compile times in some other languages that are really fast and they will usually be within 10% of similar c system with macros while offering something more robust
Hm. I guess one could write this with C++ templates and have quite similar results. Difference in append is because you probably do NOT initialize your objects on creation. Which might be an issue: your objects are UB on creation. Thus, to be fair you should call some init fun when append.
Imagine you have dyn array of dyn arrays. How would you manage that?
I guess this is too painful in C. In C++ it is vector. Also it could be с container1. Depending on properties you want to achieve.
BTW, you forgot about alignment. Maybe you were lucky with your example, but if metadata size (which you store on heap, as I understand) doesn't match object size there might be slowdown on access.
I made a (I'd say quite secure) dynamic vector that supports arbitrary array types, so a vec is possible and easily manageable.
actually, a simpler version of vec, just for the sake of vector nesting, is a vec since dynamic strings (depending on the implementation) are also arrays :D
@@phitc4242 are you talking C or C++?
@@danielmilyutin9914 C...
I wonder what are the tradeoffs between keeping your allocator in the datastructure vs passing them as arguments.
You'd have to pass the allocator as arguments to append, in addition to when you init and free the array. Because of this, I think it would make it fairly onerous to use if you had to always pass an allocator.
Yeah, passing the wrong allocator may or may not be an issue, depending on the allocator used. However, it's also annoying to explicitly pass every time you want to append as that's a common operation
@DylanFalconer pass it to the array via array.init, then every time you append the array will use the allocator pointer you passed on init.
Original C solution is not the same as C++ solution (so you can not compare their speed) as it doesn't use heap memory (it uses Stack memory instead which might be not so safe, but you don't need to release it). Also your second C solution (which is working the same fast as C++) is correctly represented C++ solution, BUT you also need to provide a macro for releasing array, you can not release it using free() function because you use your header which is hidden from user.
Summary C and C++ provides the same speed, but in C you have to use a function for releasing array memory. So use C++ if possible, but sometimes you don't have option for using it, then use C (e.g. for Embedded programming it's often prohibited to use C++ to avoid implementation its runtime).
I don't know what the pattern is called, but it is not uncommon; apparently computer networks use this to avoid sending more that one packet.
You may also work with the type as if it was just a pointer, which means it fits in a register. You can then use a macro to add the size of the header to the original pointer, and then get the element from there.
As pointed out by the pinned comment, the size is not item_size * capacity + sizeof (Array_Header). You forgot the padding. The Array_Header size might not be a multiple of the alignment of the element type.
If using GNU's C dialect, you can declare your structure to have a zero sized array at the end, which will add the necessary padding to the structure. In C99, you could use an empty array at the end of the structure, but it does not include padding, making it redundant.
And if your problem is that you like operator overloading:
1. That's a C++ feature. Trying to hack it into C is a bad idea.
2. you could make a function array_data_ptr(array*), but the lack of generics means it would be used like ((int*) array_data_ptr(array))[index]. Not pretty.
For the less knowledgeable, the C++ example at 1:40 is incomplete. You can't vector::at with a random index. It has to be in range of the length, not the capacity. Otherwise the elements would not be contiguous.
Opinion stuff:
I've been viewing a lot of material on C and I'm just left thinking: why are we still using it?
Like did not anybody think of replacements before Zig and Rust???????
C flatout makes your programs worse, no contest.
void* is a horrible, HORRIBLE abstraction for general use. It's a pointer, not a value, meaning a value has to be stored somewhere that is not the array, deferring the objects lifetime management to something else. Some people store the objects on the heap, for some reason.
No namespacing means that people do their namespacing, and when using namespaced stuff you can't remove the namespace, leading to overly verbose names. C could have just implemented them with emiting names with _, which is a valid character in everything I've ever seen.
Wait, C actually has namespacing, but only for structs, enums and unions, with their respective keywords for some reason, leading to the rampant use of typedef.
Macros are... just... copy... pasting... stuff???? might as well use automake. The C preprocessor is just a program unrelated to the compiler.
This also leads to buffer overflows are too easy to trigger.
Just pass a string without a null
Null terminated strings were good in the 1970 for the PDP-11, and nothing else after that.
string length is given in linear time. Nothing more to say, that's just bad.
Assemblers nowadays can store a normal ASCII string and give you it's length at assembly time for you to store in the binary's data section.
I don't even know why we call them strings, it's a character buffer without length and no invariance checking.
Recently I had to help a poor soul whose problem was that the buffer he was reading to didn't store the null character. I recognised in 1 second (you would too), and my solution fixed the problem immediately.
Oh, and strings can't include the null character, which actually has some uses.
There's literally no way to define compile time constants (yet, C23 has constexpr). #define is not a solution, the preprocessor sucks, and forces the compiler to analyze the replaced values everywhere, leading to larger compilation times.
The inline keyword exists, I guess. And no, it does not inline functions. Go figure.
static inline is a valid combination too, when all it does is just static, completely ignoring inline.
static is not the default.
The default is extern, and you can prepend it to anything, but why would you? It's the default. It really only matters for global variables, which are discouraged, from other C files.
Header files (which are copy-pasted recursively by the preprocessor) suck, no wonder languages that are not derived from C have never implemented them.
Oh, and they increase compilation times by a considerable amount, as demonstrated by C++20 modules and, oh yeah, every other language ever.
They are also read everytime they are included.
I literally can't count the amount of times I've seen a linked list where a dynamic array would be more appropriate (because modern processors, memory efficiency, etc...), just because C does not provide data structures in it's standard library because it CAN'T due to the lack of generic types. No, _Generic is not a replacement, it literally matches on a static amount of types. True generics allow the compiler to emit code that is tailor made for that type.
The lack of (monomorphised) generics promotes the use of void* (type-erased generics) without the safety of the type, or the safety of a garbage collector to manage the pointed-to-values, or the speed of implementations that use values rather that pointers.
Error handling is a joke. Errors are propagated by a single sentinel return value, and then you have to go out of your way to check errno, a seamingly unrelated variable.
I would rather use inline assembly than syscall wrapper functions, as the wrapper functions only return a single sentinel value and set errno, making me checking another, unrelated thing, where syscalls return both values and errors, meaning when I check if a returned value is valid, I also check what error it is.
Apparently no one knows about unions, even less how to make tagged ones.
No data hiding means that anyone can just overwrite the values on your struct or union, and then you can say goodbye to your invariance.
No RAII patterns nor defer means that error handling, which is already verbose enough, is even more verbose. You either repeat code, which is discouraged, or store your return value and using labels, which are discouraged.
I truly believe that if your first programming language is C, it will make you a worse programmer for longer than if you used anything else.
BTW, At 4:28 your array_append call should pass a void*, but it got passed an int.
Hey nice video! I have a slightly different and in my opinion (of course) preferable solution that sits in between your approach #1 and #2.
From my point of view there are 2 main problems with the implementation #2 you settled on:
1) To initialize this array (even 0 sized) it is necessary to allocate (which is not ideal since a lot of the time we have zero sized arrays). Alternatively you can have every function (ie array_length) check if the array is NULL. This of course has some slowdown but more importantly these checks have a tendency to spread (We know that we will have to check every time so to precent that we check once then save the length and use the saved one - this is aditional complexity)
2) It is not clear if the array is a dynamic array or just a pointer. This makes returning dynamic arrays slightly annoying because you always have to specify if its dynamic or not. (Its not uncomon to return static pointers when working with stateful systems).
So we would like the two following things:
1) the type needs to be static ie array of int is different from array of float on C type level
2) the dynamic array should be its own type
I do the following:
For each type define a new struct with the same members as you impl #1 except the items pointer has the desired type (I have a macro DEFINE_ARRAY_TYPE(int) for this).
Then I have each function on the array look like this:
_array_resize(void* array, int item_size, int to_size);
and a macro
#define array_resize(array, to_size)\
_array_resize(array, sizeof *array->items, to_size)
The rest of the functions have similar structure. This means to acess the size you simply do array->size. To dereference ith element you do array->items[i] etc. You can even declare these array types localy (you can in C declar struct inside a function) and use it just there.
I have detailed this approach on the Handmade discord but I wont send link here cause youtube would probably remove this whole comment.
Hey, that's actually pretty cool. I will implement it and play around with it. Thanks for sharing 🤠
do you have a gist with the implementation?
@@kiryls1207 maybe something looking a bit like this very barebones example (due to yt formatting some underscores were replaced by start/end italics):
#define DERIVE_DYN_ARRAY(T) \
typedef struct Dyn_Array_ ## T { \
size_t max_idx; \
T (*data)[]; \
} Dyn_Array_ ## T; \
\
bool Dyn_Array_ ## T ## __set(size_t i, T x, Dyn_Array_ ## T *restrict xs) { \
if(i > xs->max_idx \
&& !(xs->data = realloc(xs->data, (i + 1) * sizeof(T)) && (max_idx = i))) \
return false; \
else { \
xs->data[i] = x; \
return true; \
} \
} /* and so on and so forth */
it does increase code size though, which is where you could use more generic functions and maybe thin inline wrappers
@@yjlom oh thank you, i thought about some code generator, my only problem would be that macros, especially on the generators side, are really hard to debug when something goes out of your hand. i guess an arena could solve some of the problems but it doesn't come free. so yeah, unless it's a really known problem or you should really ponder if it's a good idea to use these kind of macros
Of course you can do it C, we've always known that so nothing new there. The real question is What happened to the compile time? C++ uses the STL for std::vector which is defined using template, you could try implementing your own version in C++ without template and see how compile time is affected.
that "trick" is also how many malloc implementations store metadata about the allocation
It's basically a pascal string for arrays.
It's how all heap allocators work.
That is not kinda stupid, init a value in a index that is too big for the array size actually allow the programmer this ability of writing to a memory that is not his, you can use it to kinda hack your program or do a lot of cool and weird things. C supposed to be super flexible for those purposed, thats why it so hard to be a good programmer in it
Why not just use realloc()?
Great video! Even though it does not cover some important things. Placing the header into the same block of memory plus using macros are really great ideas. 🙂
I have even been experimenting with my own dynamic_list thing in C. The basics of it where already done with allocation and auto growth, but I clearly wrote more functions in my header file than what I completed implementations for. I did not use macros though, but it still just has the simple void pointer code.
Most important for me was writing code that does exponential growth. And that's what I am missing in this video.
Most programming languages as far as I have seen use exponential growth for their dynamic buffer types. Which means doubling the buffer size when it it is full, which is relatively efficient when you have no option to predict needed max capacity in a program. The overhead of copying does not need to be fully paid again is the idea.
C is a simple language. Although I have always considered C++ fascinating at times when I worked with it, it's also a super complex programming language without enough safety at the same time.
My current point of view on this is to either go for C because it's simple and therefore easier to understand and debug, or to go for complex but also super memory and thread safe at the same time, Rust. I really like Rust.
There is a reason why the Linux project never adapted C++ and stayed at C, while they are now embracing Rust instead.
How to free it?
Cast the pointer back to Array_Header *, decrement (to point back to the start of the allocated block of memory), and free using the allocator's free() function
@odomobo is correct. Depending on your allocation style, you may not have to worry about it anyway. I'll make more content about memory allocators
@@DylanFalconer Yeah please do
Did you mean linked list :)
Arrays in other languages: ☺️☘️🌞
Arrays in C: 💀⚰️🤦♂️🤦♀️🚨 😀🔫
To be honest when you programm microcontrollers you dont reallyneed fancy overhead that c++ offers you. If you need dynamic arrays in C i.e. "normal arrays" in other language,you could write library like in 30 minutes and use it for the rest of your life.
Nah. It's really easy and logical, once you understand it.
If just compile times are your reason to use C rather than C++ for writing large complex projects, then that's kind of lame.
For hot reloading code, just don't use templates or use them sparingly.
And nobody is forced to just use standard C++ library. If you care about performance then you would write your own libraries catered to your specialized use case or use external one.
The thing is, C has very primitive support for library authors, just functions, structs and macros.
Whereas in C++ you have all the features that you would want and then some, which enables you to write very efficient zero cost abstractions.
Anything generic in C would require function pointers or macros.
And you can't make "code path decisions" at compile time like C++s if constexpr and function overloading.
Not to mention there is no constant expressions in C while in C++ now you can allocate memory at compile time and use the entirety of cmath enabling you to do arbitrary computations at compile time, all free of UB.
I do agree, but you might want to check out C23 (includes constexpr)
A short list:
* exposing yourself to type errors and memory leaks, to save 0.9 seconds per compile. Lose hours to save a minute or two.
* you can't share the array pointer because it gets reassigned, even passing the pointer into a function by value is dangerous.
* malloc allocates on the heap, not the stack
* data alignment, but easily fixed
* you can use both C and C++, it's the same compiler, just pick the zero-overhead abstractions that work for you.
* C++ templates can do what you're doing with macros, but with type safety, and operator overloading, a[x]
template
struct array {
T *data;
// ...
inline T& operator [](size_t i) {
return data[i];
}
};
I'm not a big fan of the proposed implementation either, due to the ease of misuse (no type distinction between ptr, array, and dyn array, dyn array append causes all pointer invalidation, not just element pointers), that said, your argument is really a strawman:
* exposing yourself to type errors and memory leaks, to save 0.9 seconds per compile. Lose hours to save a minute or two.
C++ compilation time, especially when using things like the STL, aren't just adding a few seconds here and there. I've worked on C++ projects that took over 45 minutes to build with minimal optimizations enabled. It's the same problem that LTO has, on any larger project, it's simply too slow to be usable, we saw build times over 24 hours, on high-end builders with 256GB of RAM, which it exhausted.
For larger productions, using C++, to get some of the type safety, but without its STL, makes a lot more sense than just using C, but at the same time, C++'s compilation speed is not about saving small amounts of time.
@@Aidiakapi that isn't a strawman, I was responding to what he said. As for previous projects you've worked on, you know that's a red herring, without specifics of how it was structured, etc. Your LTO anecdote makes it sound like a monolith... what problem were you expecting to solve with that anyway?
Points are kinda valid but zero cost abstractions aren't real, all abstractions have costs (including the abstraction developed in this video), especially when it comes to C++ wich has such an utterly terrible standard library amplified by feature creep.
C++ templates are a quite bad implementation of polymorphism too, and they absolutely explode your compile times not by just 0.9 seconds but tens of minutes in large codebases, so I will personally pass.
I am not saying you should use C, again your points against C are mostly valid, I am just saying that C++ "solutions" are really terrible and it is understandable why people opt to not go into that. Ideally we would use a more modern language like zig, odin or Rust, but then for other reasons that is often not possible.
@@marcossidoruk8033 zero-cost abstraction is a runtime performance term, you're arguing semantics dude.
But sure, let's talk about compilation times. The naive approach has you instantiating every template in every file you use them in, and then people wonder why their compilation is slow. You only need to instantiate a template once, and then extern it. Precompiled headers have been around forever, and of course you can implement a component using any C++ feature without exposing it in its interface. This is all neglecting the fact that if you have even the most rudimentary build tools, you're not rebuilding everything all the time anyway.
There's this common argument against C++ that it's bad because it has a library or feature, despite it being completely optional. That leads to people writing unsafe code with macros to make up for the lack of that feature in C. If you don't want to use std::vector - you don't have to, same goes for exceptions, virtual functions, etc. Meanwhile, C23 is finally getting constexpr, a feature C++11 introduced ages ago. And you can still write C code alongside C++ anyway. I find the whole C versus C++ thing ridiculous.
Other languages are other languages. I wrote my comment to be relevant to Dylan's video.
So, basically, you brought Ada arrays into C? Well, not quite. You don't have any type enforcement on the index.
too advanced for me lmao
I like it! The video itself is lacking in some parts, but it's not a bad implementation.
There are other reasons besides compile times when choosing C. Sometimes it's just the project you're stuck with, sometimes you need a greater level of control, sometimes you just can't be assed to prepend the "extern C" to every library function you use.
For me personally, I'll stick with a variation of solution 1 (with special macros for every typed array), but thats only because I'm an old fart and I come to expect certain functionality from squared brackets. C has it's way of doing things, and that's not bad. Just a quirk of the language.
It's not like "generics", - most closest approach to them is using macros with type provisioning without storing type size dynamically inside header and still there is a problem with fields optimization: in c++ if allocator set to default in stl container then it wouldn't be dynamically represent in container object
And trick with storing header as array element working only with maxaligned elements' allocation (malloc does it, of course (and it's lame)), 'couse header could have different alignment comparing to its elements and also each time using this type array there will be copying heap memory block of array with header to cache and this is not cool
i use this in gnu c
int addrecord(char ***inputarray, int *inputarraycounter, const char *fmt, ...)
{
char *str = NULL;
int len = 0;
if(fmt)
{
va_list ap;
va_start(ap, fmt);
len = vasprintf(&str, fmt, ap);
va_end(ap);
if(len == -1)
{
return -1;
}
}
(*(inputarray)) = realloc((*(inputarray)), sizeof(char *) * ++(*(inputarraycounter)));
(*(inputarray))[(*(inputarraycounter)) - 1] = str;
return len;
}
Compile times add up but coffee breaks with your colleagues add up more. Personally, I have a hatred for micro time management. 99% of the time you have save 100x as much time by not chit-chatting with your colleagues.
I agree, but I don't have colleagues, so I've gotta optimise my own workflow. It's only partially about time, though that's what I said in the video. It's more about fiction. Waiting just 3 seconds can pull me out of a flow state, and then I'll be on Discord or something.
try compiling a c program with tcc... compile times are as fast as 10x of that of gcc. even clang is faster than gcc... ;D
linked lists * cougth *
linked lists are really slow
@@lavatasche2806 it depends, if you use only the start and the end, like in a queue or in stack it is actually faster
@@lavatasche2806 it depends, when you only use start or end of the linked list it isnt slow, adding stuff to the start of end of a linked list sometimes can even be faster than to an array list. So linked lists are faster than vectors/array list for queues and stacks
I think microsft's BSTR type does this.
coding tribalism is so cringe 😬
Yes I like store bought pasta, but I also like being able to make my own - fresh - from base ingredients. In the world of development you may have an opsie-woopsie, or perhaps even a f#!€y-wucky but you learn something along the way and can grow as a programmer.
Edit: to be clear I love this video and despite other people’s criticism I think it’s an excellent piece of work. If someone wants to criticize anything they should at least try and explain why 😅
Thank you and to everyone who pointed out the alignment issue. I'm going to update the written version today with what I think is a sensible solution
I don't like the 2d option. I ve tried it a bunch of time, but yeah no. I rarely use dynamic array, so I don't think about it too much
This is literally just zig lol
I was thinking this was going to just be about VLA's, but this is cool too. This is how STB works too, and once you fix the alignment problem you'll be well on your way. I just wish that the extensions that Jacob Navia added to LCC would get added to the standard. I've been wanting C to have operator overloading for decades now. Oh well, this is one of those issues that I've always had with C and why I've been working on my own language. C is the best programming language there is, but it really does need overloads. Even Python does better here, and Python sucks.
I love strtok func so much. Why doing something in 5 characters when you can do it in 20 lines? Quit modernity! Embrace tradition. Tradition is what makes the industry go forward!
This is horrifying. If you’re trying to hotswap code, you doing things wrong.
By facilitating guess and check programming, you’re opening yourself to an absolute nightmare if others end up working on it.
I absolutely agree that compile time is important, but if your workflow is improved by waiting 30 seconds instead of 60 seconds, you’re doing countless things wrong.
Other than that, I do really like this design pattern for projects limited to C for whatever reason.
8:08 I personally would do this: void *ptr = NULL; instead of: void *ptr = 0;
though I think it does the same, I just feel like the former is more readable, at least to me.
also I would give some error if the allocated memory is NULL (the if (h) check).
Other than those nit picks, I really like this solution.
fun fact, This way of doing it is really similar of how it is done in Jai (a programming language primarily for making games that is currently in beta)
Though it stores the equivalent of this:
struct Resizable_Array {
int64_t count;
void *data;
uint64_t allocated;
Allocator allocator;
};
And a lot of it things is baked into the compiler, but the functions to interact with it is in the standard library (which is just a bunch of source files so you can see and modify it).
soon we will be able to do nullptr
Assigning 0 to pointer is undefined behavior because there's no guarantee that NULL is 0, C programmers can't even get these basic things right while my knowledge of C exists only because of me wrapping shitty C API's in real languages that don't give me brain damage.
@@shinobuoshino5066Assigning a pointer to 0 is well defined and will result in the pointer being assigned to null. Note that that means the pointer may not have the bit pattern for 0 after the assignment if nullptr is different.
What you might be thinking of is memseting a structure to zero and expecting the pointers to be null. In that case, the pointers will be 0 and not null on platforms that use a different value for null.
Fortunately this is almost all academic as most platforms can ensure that the address 0 and null are the same, even if the pointer does address address 0, via the magic of virtual memory. And I suspect that on platforms where this isn't possible, you are hard coding memory addresses anyway and not dealing with dynamic memory much at all.
You are confused. Undefined behavior is where the result of a set of operations may not be consistent, or where the language does not define the outcome of the operator. Accessing C arrays out of bounds in not undefined, it is just stack corruption. The fact that the stack size may accommodate the access does not make it undefined, it is just plain old corruption, illegal, wrong, faulty. It is an important distinction, as true undefined behaviour does exist, normally as a result of architecture specific details clashing with code generation. Faulty code seeming to work at runtime is not undefined, it is just unfortunate, and implementation specific - it may well crash instantly on some O/S Arch combination but run seeming without issues on others. This is why stack checkers exist, -fsanitize=address on gcc is good example and (I suspect, not tried it) would detect your example fault.
The best way to have a dynamic array in C is not have one.
just use array bigger than what you need.
Sounds stupid but it is the kind of enviroment C was made for.
you had harsh memory and processing limits, so you set sizes for boundaries for your data and you tried to make it reasonable enough so the program could be useful and still work.
If you truly needed bottomless pit of data, then that was a memory menagement issue, thats what heap and File pointers were made for.
congrats
you re-implemented a worse std::vector. This is the kind of shit why c++ exists. If compilation speeds are what hold you back, think hard about _why_ that is.
1:00 Yeah you just lost about all of your credibility here with that noob take about UB being "stupid". Undefined Behavior isn't an accident, it's a core language feature responsible for allowing compiled C and C++ code to be as fast as it is.
It shouldn't be an UB when an "Out of bound access" happens. When I see such code like show in this video, I see new CVEs poping up.
@@juergenm6107 Writing code that violates your data structure invariants is a cause of major bugs in _every_ language. Enforcing bounds checks on every access is both unnecessarily slow and makes the language less useful for some of its core use-cases in systems programming where "do what I say" unchecked memory accesses are both useful and critically necessary.
I agree, it was a silly take when UB is what makes the compile speed fast in the first place. What I should have said is I'd prefer if everything was explicit by default and then you could turn checks off for faster compilation.
@@DylanFalconer Hey if you want checked accesses for debugging, that's absolutely available -- it's called valgrind.
No. You can certainly justify array OOB access being undefined, but other forms of UB are silly even _with_ the potential optimizations, like the strict aliasing rule or the union live member rule (can't reinterpret the bytes of one object in a union as another -- that's UB, except specifically for type punning in C but not C++).
Both of those rules are pure anathema to low-level programming and are best left ignored by compiler writers in most cases given that ~any useful non-trivial networking or kernel programming will violate one or both rules very quickly. Particularly with the strict aliasing rule, it should have been left to the programmer to specify if pointers don't alias, and only the programmer, via restrict.
Not to mention, unlike rules like out-of-bounds access, they are very arbitrary to begin with. There's no obvious reason why a reinterpret cast from one pointer to another shouldn't just work, and I can't even think of a real example where the live object rule for unions would be useful for anything except guaranteeing unforeseen bugs you didn't intend.
So funny, the irony. What a mess and not even type safe (void*) or memory safe (better not forget to deallocate) and then he says "obviously I prefer C", lol. And that for something as simple as a dynamic array, better hope nobody wants a hash set/table, binary tree, graph, etc. Obviously you should use a modern language if you want to do serious high-level programming. A modern language abstracts away the uninteresting time-consuming details so you can focus on the what you want to program instead of having to play with low-level pointers, macros, allocators.
Some people just prefer low level language, so that you can literally see what's going on in the low level side. The disadvantage of C++ is that it abstract a lot of the low level side, but you still need to figure it out what's going on at low level to make sure you don't make some errors.
Funny you said that because I implemented absl flat hash map and flat hash set in C. It doesn't take much to get use to C way of managing memory. If you can't handle that (skill issue) then there is always other languages for you to choose like JavaScript
Edit: absl flat hash map and set is more pointer arithmetic so to be clear, I also implemented the normal hash map and set (just that I had a skill issue when I wrote it so it is only slightly faster than C++ hash map)
Edit 2: grammar
Edit 3: forgot I didn't specify why playing with low level pointer, allocator is good (and also fun). You are not relying on a black box to spit out your data structure object. If you have a memory fragmentation problem in C++, you might as well give up since knowing how a data structure work does not mean you understand its implementation.
Edit 4: malloc realloc free and some POSIX allocator isn't even low level
I would use a higher level language if they weren't all so slow :(
@@DylanFalconerthen, would you use Rust?
Not managing my own memory or not having pointers feels so icky. I like being able to do things with my memory like not allocating (which is sooo slow) as much as possible
This is a pointless topic. The C language was used to design operating systems in the 1970s. It enforced structured data structures and pointer manipulation. Even if it allowed you to dynamically allocate memory to the operating system, that's not what it was. If you want to keep your investment in C language syntax, you should try to learn C++
Pure waffle 😂
@@cheesepie4ever Your metaphor is inappropriate, add dynamic array to C language just like add refrigerator function to your bed.
Sounds like you are jealous of C
learn rust ffs