11 ms·
Generic dynamic array in 60 lines of C
- downvotetruth 4y agodata (startptr), endptr & capacity?! Memory might be cheap enough to waste, but more derefs do not help timings.
- exitb 4y agoCapacity may not be equal to size.
- JonChesterfield 4y agoThree pointers (or two and a size, or one and two sizes) is pretty standard for dynamic arrays. It lets you allocate more than one element a time when repeatedly appending one element. No checking malloc or realloc though. The anonymous struct is dubious too, though maybe being unable to pass these things to functions is a feature.
- nice_byte 4y agofunctions can work with just pointer / size / stride. think of it as stl iterators, there's no real point to be passing the container itself around. however, you can still do that, if you really want. just `typedef DYN_ARR_OF(widget) widget_array;` and now you have a name-able type, and can even have dynamic-arrays-of-dynamic-arrays (`DYN_ARR_OF(widget_array)`).
- WalterBright 4y agoHeavy use of macros to do metaprogramming is a strong sign it's time to move to a more powerful language.
- alar44 4y agoYeah that's a great opinion and all but generally C is used because it HAS to be used these days. No one is going to use this code for building a web application or will be tossing it into legacy code.
- jalino23 4y agoI don't have this luxury if I want to learn about ffmpeg libraries, its all written in c, almost all media and hardware accelerator libraries are written in c, you go to another language they just bind to c. its soo frustrating but I've no choice but to stick with c.
- ammar2 4y agohuh? What's wrong with using the higher level languages if they take care of binding to the C parts for you. (I know these are far an in-between for ffmpeg, too many leaky abstractions.)
- flohofwoe 4y agoUsually increased build system complexity, outdated manually maintained bindings, etc etc... - in some languages (like Zig) this is really trivial, in other languages it can be much harder.
- jalino23 4y agotry to find ffmpeg in go or rust that is < 5 years old and complete. how about intel libva,
- jpollock 4y agoMost languages have the ability to call C functions. Use the language that helps you write your code and convert to call the third party API. For example, a C++ Vector provides a generic container and the code can still call C functions with the underlying array. This is in the "Doctor it hurts if I do X" bucket. https://stackoverflow.com/questions/2923272/how-to-convert-vector-to-array https://stackoverflow.com/questions/2923272/how-to-convert-v...
- flohofwoe 4y agoMixing high level C++ stdlib classes with low level C APIs is often not exactly trivial, for instance most C++ containers expect that their items are RAII compatibel, and the resulting memory corruption errors will be harder to debug than plain old C code because the shit hits the fan deep inside some completely unreadable C++ stdlib implementation code.
- cperciva 4y agoC + a set of macros is a more powerful programming language.
- JUNGLEISMASSIVE 4y ago[dead]
- Night_Thastus 4y agoAlso a far worse language though. Macros have their place, but trying to do anything complex with them just turns into a total nightmare. They're hard to reason about, walk through, or modify. If heavy macro usage is found, it's definitely time to reconsider the approach.
- cperciva 4y agoIt really depends on how macros are used. If you're just using them to implement "high level language features", it's not a problem; sure, you might have trouble figuring out what STAILQ_INSERT_TAIL does internally, but you're going to have just as much trouble figuring out what the Lisp or Perl or Python "add this item to the end of that list" operations do internally. Macros can be a nightmare, but when they're used properly they're not.
- WalterBright 4y ago> when they're used properly they're not Yeah, they are. Source: Decades of C programming
- cperciva 4y agoYou're not the only person with decades of experience.
- WalterBright 4y agoWe all suffer from this, so it's not personal, but one is too often blind to the shortcomings of one's own code.
- flohofwoe 4y agoOn one hand that's obviously true, on the other hand it's just 60 lines of code, which is easier to check and audit than (for instance) a typical std::vector implementation - I don't know what the equivalent is in D, please forgive my ignorance :)
- tines 4y agoA typical std::vector implementation supports a lot more things, so it's not an apples-to-apples comparison. It's like saying that a horse-drawn carriage is a lot easier to repair than a motor vehicle. It's true, but doesn't really say much.
- eimrine 4y agoLisp?
- wheelerof4te 4y agoC is powerful enough.
- Gibbon1 4y agoIf were me I'd use inline functions instead of macro's
- nice_byte 4y agoyes, i know growth by a factor of 2 has issues under certain usage patterns. those are less likely to be problematic when there is more stuff going on than just growing the buffer - you can use the "hole" for other allocations.
- rkeene2 4y agoHard to tease out what you're saying here, but maybe a Hashed Array Table (HAT) is what you're referring to ? I have a slightly extended version here [0][1] [0] https://rkeene.org/viewer/tmp/hat.c.htm https://rkeene.org/viewer/tmp/hat.c.htm [1] https://rkeene.org/viewer/tmp/hat.png.htm https://rkeene.org/viewer/tmp/hat.png.htm
- quibono 4y agoI think GP meant that his implementation doubles the capacity of the array on resize as opposed to increasing by 1.5 or some other factor.
- _0w8t 4y agoThe code has integer overflow even on 64 bit CPU due to using uint32 for capacity.
- wzdd 4y agoThis seems pretty sensical to me except that it achieves its small size by sacrificing error checking and handling, even in the (aiui) non-exceptional case of realloc() returning NULL. This is of course classic C program behaviour so perhaps that's fine ;-)
- saagarjha 4y agoWhy use macros instead of inline functions?
- vore 4y agoInline functions can't be made type safe (or at least, as type safe as C gets) over generic arrays.
- flohofwoe 4y agoBecause the API needs to work for random item types. C doesn't have templates (and for stuff like this C11's _Generic isn't helpful because that just maps specialized function names to generic function names, but doesn't help with the generic implementation code).
- kzrdude 4y agoNot an entirely uncommon idea. I've written one. There's also a well-known one here, in klib: https://github.com/attractivechaos/klib/blob/master/kvec.h https://github.com/attractivechaos/klib/blob/master/kvec.h
- globalreset 4y agoWho didn't. Almost any C program dealing with strings and collections has to have their own implementation or import one. Part of the reason why C developers "feel" productive, but can't produce anything of meaningful complexity.
- rootw0rm 4y agoI think sqlite is fairly complex
- kzrdude 4y agoYou hurt me with the truth. Anyway, I think this HN posting has this "crazy" flavor of using macros to simulate generics, and that's the specific kind of implementation that I meant, which klib also does.
- deleted 4y ago[deleted]
- nice_byte 4y agotil the Linux kernel has no meaningful complexity
- kevin_thibedeau 4y agoStill waiting for a revolutionary OS written in $virtuous_lang to save us from the scourge of unsafe Linux. They've had since Ada-83 to get something off the ground. Guess they aren't so productive either.
- matheusmoreira 4y agoHave you ever heard of Linux?
- orbital223 4y agoDYN_ARR_RESET should probably be called DYN_ARR_INIT instead, as calling it more than once will leak memory. The handling of endptr in DYN_ARR_RESIZE seems to be incorrect. If I have an array with 2 elements and capacity of 3 and I DYN_ARR_RESIZE it to 5, I now have an array with 5 elements, 3 of which are garbage values.
- aslilac 4y ago~~Isn't the handling of `endptr` incorrect in `DYN_ARR_RESET` as well? `a.endptr = a.data;` feels very incorrect to me.~~ Nevermind, I see how it's supposed to work now. To your point, `RESIZE` is definitely incorrect. It should be checking the length before calling `realloc`.
- parasti 4y agoThats just idiomatic C. Set the "pointer to end" to be equal to the "pointer to start".
- nice_byte 4y agothat's the intended behavior. this somewhat mirrors what happens with a std::vector when you call resize() except of course c doesn't have default ctors. the point of resize is to make exactly "size" elements of the dynamic array addressable.
- matheusmoreira 4y agoThe values are garbage because they haven't been initialized yet. Other code may write to those locations.
- patrick451 4y ago> The handling of endptr in DYN_ARR_RESIZE seems to be incorrect. If I have an array with 2 elements and capacity of 3 and I DYN_ARR_RESIZE it to 5, I now have an array with 5 elements, 3 of which are garbage values. Why do you say this is wrong? That's exactly what I would expect.
- 4y ago
- kiryk 4y agoI like that the comments mention another two implementations of a similar idea and all are a bit different. Here's one I've written a few years ago: https://github.com/kiryk/mlisp/blob/master/vector.c https://github.com/kiryk/mlisp/blob/master/vector.c You may find it dirty, but it can be wrapped using macros, and used both on LHS and RHS like in "string(v, i) = ch" (the macros BTW) https://github.com/kiryk/mlisp/blob/71d028738d2f9607fa7ce8c1a59e33255460e03e/lisp.h#L3-L5 https://github.com/kiryk/mlisp/blob/71d028738d2f9607fa7ce8c1... (and a usecase) https://github.com/kiryk/mlisp/blob/71d028738d2f9607fa7ce8c1a59e33255460e03e/main.c#L29 https://github.com/kiryk/mlisp/blob/71d028738d2f9607fa7ce8c1...
- marcodiego 4y agoI think this author should learn about the "do {} while(0)" trick.
- HarHarVeryFunny 4y agoWhat's the benefit of do {...} while (0) vs just {...} ?
- tines 4y agoThe latter makes the macro usable without requiring a semicolon, which some people don't like; the former will cause a syntax error if the semicolon is missing, so they feel that it regulates syntax a bit better.
- nice_byte 4y agoWorks if you want to e.g. skip braces if if..else... statements. Some would say putting braces in always is good style, but I like skipping them myself so won't defend it :)
- yakubin 4y agoI agree it’s good style, but surrounding code using bad style is still poor excuse for writing macros which break.
- yakubin 4y agodo {…} while (0) is a statement, so it can be put between “if (…)” and “; else”, while just {…} would result in a syntax error due to a hanging else.
- HarHarVeryFunny 4y agoOK, but I guess what's really being relied on there is that it's syntactically still a single statement when you follow it with ';', whereas {...}; is two statements (which is what breaks the if-else). I just discovered that gcc also supports non-standard "statement expressions" of the form ({...}) which would serve the same purpose at the cost of portability.
- latenightcoding 4y agothis one does RAII in C and it's most likely faster: https://bit.ly/3ICOplU https://bit.ly/3ICOplU
- beej71 4y agoEven this one appears to leak memory on failed `realloc()`.
- olliej 4y agoI dislike this - having the “array” be a struct containing the pointer and size fields makes it easy to “copy” the array such that you get dangling pointers. Similarly there’s no way to track lifetime or ownership of the array. There are long term ABI benefits to these data structures just being opaque pointers outside of the implementing libraries
- nice_byte 4y agono reason for it to ever cross abi boundary.
- klyrs 4y agoDON'T USE THIS As fpoling points out, capacity is a 32-bit unsigned. That can overflow. There is no safety in append: if capacity is zero no new space will be made, if capacity overflows the realloc will not have enough space -- in either case, you end up writing past the end. Allocating a [capacity] zero array and appending to it is extremely common. That you'll write past the end in that case shows that the author has barely even used this. The code is unacceptably bad and unsafe. I don't usually do this, but I'm going to flag this post. I encourage everybody to do the same. Apologies to the author. Golf is fun. This is uncool. edit: changed size to [capacity]
- nice_byte 4y agoI have been using this for years. Capacity is not size. A zero size array will have non zero capacity. All c code is unsafe.
- klyrs 4y agoWhere do you check that capacity is nonzero? When capacity is zero, what happens on this line? a.capacity <<= 1u; "all c code is unsafe" is not an excuse to permit bloody obvious, undocumented memory overruns. I write a lot of c. Avoiding the unsafe bits, avoiding UB, is the skill required to write good c. "C code is unsafe" is a Rustacean marketing slogan. Don't believe it, but definitely don't practice it.
- nice_byte 4y agojust don't initialize it with 0 capacity :-)
- skullt 4y agoWhy not just fix it? It's a trivial fix and has the added benefit that a zero-initialized DYN_ARR_OF(x) struct would be in a valid state, which is always nice. A struct with several dynamic arrays can then much simpler to initialize, for example.
- 4y ago
- posharma 4y agoSeriously, in this day and age, why are we still stuck with C? There are battle tested container libraries in C++ for e.g.
- not_the_fda 4y agoYep, once you find yourself writing containers that are found in C++ its time to switch to it. I've seen too many C developers re-write C++ containers in C because they are afraid of C++, its madness.
- GuB-42 4y agoC++ is annoying because of name mangling and things like static initialization calling constructors. The result is that you can easily link C code to almost any language, including C++, with almost any linker. But for C++, you usually have to use the linker that comes with the C++ compiler that compiled your library. You can write code in C++ that is as compatible as C, but you have to go out of your way to achieve that, extern "C" is only the beginning. As a result, when the overhead of using C instead of a more complete language is not too great, I prefer to write my libraries in ANSI-C, for maximum compatibility.
- rurban 4y agoIndeed, C++ is madness. Unsafe iterators, insane template language compared to cpp
- jxy 4y agoWhat does it actually gain by using macros instead of proper functions? The only generic macro that can't be written in function is the one use `type`, but saving the type size in the struct is enough for this kind of code.
- andrewmcwatters 4y agoI don't like the use of macros for things like this. Macros in general should rarely or sparingly be used. I'm also not certain one should use "end pointers." Conventionally, it seems more advisable to use `size_t capacity`, `size_t length`, and `void *data`. Great use of Cunningham's Law, though! I appreciate C posts on Hacker News.
- nice_byte 4y agothe alternative in c is something like glib's array container which hides types. I dislike that more.
- andrewmcwatters 4y agoYes, but GLib arrays are also lossy. They require you to externally manage capacity or to know with perfect foresight exactly what your capacity will be for the lifetime of the memory allocation. I don't think those are impossible scenarios, but the cost of one additional pointer in terms of size leaves you with a lot more functionality. Saving one pointer in size and not having capacity makes GLib arrays nearly useless, which I find confusing. You could simply pass a pointer and a size around instead. Which is what most people actually do when they don't need resizable data layouts. If you're working with C, I think you have to just accept that void pointers happen. Working around losing compile-time type data requires you to create runtime structures, which I don't find acceptable.
- User23 4y agoAmusingly, Ward Cunningham denies inventing Cunningham's law and I feel compelled to correct that potential misunderstanding.
- andrewmcwatters 4y agoHow meta...
- deleted 4y ago[deleted]
- sitkack 4y agoThis isn't C, this is preprocessor. Tomato tomato, who cares if it is 60 lines or 600. https://doc.rust-lang.org/src/alloc/vec/mod.rs.html#400 https://doc.rust-lang.org/src/alloc/vec/mod.rs.html#400 https://docs.rs/containers/latest/src/containers/collections/raw_vec.rs.html https://docs.rs/containers/latest/src/containers/collections...
- lolcatuser 4y agohttps://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf Section 6.10 (Page 145): Preprocessing Directives Hey, would you look at that! The preprocessor is a mandatory part of the language!
- nathants 4y agoawesome! i do the same thing for arrays[1] and maps[2]. stuff like this is great when you are trying to find the performance ceiling of some workload in c/cpp. literally nothing to hide. 1. https://github.com/nathants/bsv/blob/master/util/array.h https://github.com/nathants/bsv/blob/master/util/array.h 2. https://github.com/nathants/bsv/blob/master/util/map.h https://github.com/nathants/bsv/blob/master/util/map.h
- halayli 4y agoa.capacity <<= 1u; decltype(a.data) tmp = (decltype(a.data)) realloc(a.data, sizeof(a.data[0]) * a.capacity); assert(tmp != NULL); That's not ideal. Imagine you are at 32GB capacity, the next realloc will ask for 64GB which is pretty excessive.
- euclaise 4y agoMy understanding is that this is the typical behavior of dynamic arrays
- rurban 4y agoOnly for bad dynamic array implementations. Good ones might resize by the golden ratio, and enlarge by blocksize if larger
- eqvinox 4y agoThis isn't suitable for arrays that large regardless of the resizing multiplier. realloc() generally allocates a new block of memory of the new size, copies the entire content over, and then frees the old block. Only sometimes you get to be lucky and have enough spare room after the existing data in the virtual address map to not need that copy. By the point this copying becomes relevant, a continuous dynamic array like this becomes fundamentally the wrong data structure.
- RcouF1uZ4gsC 4y agoAny sufficiently complicated C program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of C++.
- hgs3 4y agoThe biggest problem with this is that you cannot assign, pass, or return an "instance" of the array struct itself. That's because it's declared as an unnamed struct and in C two unnamed structs are not type compatible even if they have identical fields. C23 did improve struct compatibility [1] but unfortunately not for unnamed structs. [1] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3003.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3003.pdf
- thdespou 4y agoMacros are evil. I will stick to zig at the moment.
- shaggie76 4y agoCounterpoint to people suggesting size_t for capacity: we recently changed our in-house std::vector replacement from { T* first, last, end; } to { T* first; u32 size, capacity; }. Not only did this shave 8 bytes off of each instance but in many cases it saved more because they became 16 bytes which reduced alignment padding in other objects that use SIMD types that require 16-byte alignment. This saved 40 MB of memory for us in https://warframe.fandom.com/wiki/Orb_Vallis https://warframe.fandom.com/wiki/Orb_Vallis which, given the poverty our mobile minspec, was a terrific savings. Your needs may vary, but it's 2023 we're still cramming 4GB of poop into a 2GB bag.
- andrewmcwatters 4y agoIn game development, you'll want to do things like this often, but general purpose programming shouldn't adopt this practice. It's literally what the type is for.
- up2isomorphism 4y agoThe post demonstrated one thing: don’t share your code. Not to say I think this particular implementation is my favorite, but why anybody should expect a free online code snippet should be bulletproof is beyond me, it is a damn gist, a demo.