17 ms·
Making a StringBuffer in C, and questioning my sanity
- ranger_danger 1y agoYou might be interested in https://github.com/antirez/sds https://github.com/antirez/sds
- fsckboy 1y agoneat, i like it, has some of the same ideas i've used in my string packages but i did see a place to shave a byte in the sds data struct. The null terminator is a wasted field, that byte (or int) should be used to store the amount of free space left in the buffer (as a proxy for strlen). When there is no space left in the buffer, the free space value will be.... a very convenient 0 heheh hey, OP said he wants to be a better C programmer!
- ranger_danger 1y ago> The null terminator is a wasted field I think that would break its "Compatible with normal C string functions" feature.
- fsckboy 1y agonooooo you don't understand. when the buffer is not full, the string will be zero terminated "in buffer" (which is how it works as is anyway). when the buffer is full, the "free count" at the end will do double duty, both as a zero count and a zero terminater
- ranger_danger 1y agoBut calling "normal C string functions" don't know about the "free count" byte, right? So it wouldn't be updated... unless I'm misunderstanding something.
- fsckboy 1y agonormal c string functions don't know about any of this package's improvements, I'm not sure you understand what the package does. +--------+-------------------------------+-----------+ | Header | Binary safe C alike string... | Null term | +--------+-------------------------------+-----------+ | `-> Pointer returned to the user. his trick is to create a struct with fields in the header for extra information about the string, and then a string buffer also in the struct. but on instantiation, instead of returning the address of the struct/header, he returns the address of the string, so it could be passed to strlen and return the right answer, or open and open the right file, all compatible-like. but if you call "methods" on the package, they know that there is a header with struct fields below the string buffer and it can obtain those, and update them if need be. He doesn't document that in more detail in the initial part of the spec/readme, but an obvious thing to add in the header would be a strlen, so you'd know where to append without counting through the string. But without doing something like that, there is no reason to have a header. Normal string functions can "handle" these strings, but they can't update the header information. I'm just extending that concept to the byte at the end also. this type of thing falls into what the soulless ginger freaks call UB and want to eliminate. (soulless ginger freaks? a combination of "rust colored" and https://www.youtube.com/watch?v=EY39fkmqKBM https://www.youtube.com/watch?v=EY39fkmqKBM )
- ranger_danger 1y ago> instead of returning the address of the struct Yes I'm pretty sure I understand this part. > an obvious thing to add in the header would be a strlen The length is already in the header from what I can tell: https://github.com/antirez/sds/blob/master/sds.h#L64 https://github.com/antirez/sds/blob/master/sds.h#L64 But my point was that if something like your "free count" byte existed at the end, I would think it couldn't be relied upon because functions such as s*printf that might truncate, don't know about that field, and you don't want later "methods" to rely on a field that hasn't been updated and then run off the end. And from what I can tell from the link above, there isn't actually a "free count" defined anywhere in the struct, the buffer appears to be at the end of the struct, with no extra fields after it. Maybe I'm misunderstanding something?
- improgrammer007 1y agoI would rather focus on solving the main problem than reinvent the wheel. Just use C++ if perf is critical which gives you all these things for free. In this day and age the reasons for using C as your main language should be almost zero.
- o11c 1y agoHm, this implementation seems allergic to passing types by value, which eliminates half of the allocations. It also makes the mistake of being mutable-first, and provides some fundamentally-inefficient operations. The main mistake that this makes in common with most string implementations make is to only provide a single type, rather than a series of mostly-compatible types that can be used generically in common contexts, but which differ in ways that sometimes matter. Ownership, lifetime, representation, etc.
- remexre 1y agoHow would you recommend doing that sort of "subtyping"? _Generic and macros?
- o11c 1y agoYup. It's a lot saner in C++, but people who refuse to use C++ for political reasons can do it the ugly way using C11 or GNU C.
- improgrammer007 1y agoThey even downvote people who suggest C++ :-). Doing this in C is such a colossal waste of time and energy, not to mention the bugs it'll introduce. Sigh!
- zahlman 1y agoTrolling about the choice of implementation language from a throwaway account is worth downvotes, yes. Doing a given task in a given language, simply for the sake of having it done in that language, is a legitimate endeavour, and having someone document (from personal experience) why it's difficult in that language is real content worth discussion. Choosing a better language is very much not a goal here. > Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something.
- vlovich123 1y ago
- WalterBright 1y agonew_capacity *= 2; A better value is to increase size by 1.5: https://stackoverflow.com/questions/1100311/what-is-the-ideal-growth-rate-for-a-dynamically-allocated-array https://stackoverflow.com/questions/1100311/what-is-the-idea...
- emmelaich 1y agoI remember reading (decades ago) an extensive article in Software Practice and Experience reaching the same conclusion.
- manwe150 1y agoOr like Python shows there, 1.25+k which can be better (faster growth and less memory wasted) than both
- burnt-resistor 1y ago1.25 of what? Do you mean 2.25*k == 9*k/4.
- tialaramex 1y agoThey say 1.25+k, in this context k will be some constant, suppose it's 16 bytes Thus you might see a curve like 13, 32, 56, 86 - this curve is aggressive to start but then much gentler. Because it's so gentle it gets the re-use upside for medium sized allocations but it incurs a lot more copying, I can imagine in Python that might be a good trade.
- burnt-resistor 1y agoYep. And probably use tcmalloc or jemalloc (deprecated?) too. Most OS sbrk/libc malloc implementations are better than they used to be, but certain profiled programs can increased performance by tuning one of the nonstandard allocators. YMMV. Test, profile, and experiment.
- tialaramex 1y ago
- gblargg 1y agoIt's odd how it has error reporting in some areas (alloc, split can return NULL if allocation fails), but not others (append, prepend have a void return type but might require allocation internally).
- burnt-resistor 1y agoIt can be refactored into creating a buffer primitive of void* buf, size_t capacity, size_t refcount. Then, the string can implement using CoW logic on a buffer and size_t length. Read-only references to substrings become cheap and copying is done whenever there's a modification or realloc can't grow the underlying buffer.
- p0w3n3d 1y agoBy the way, I have no power here, but you people are ubiquitous, at least one of you is in C committee. Hereby I propose an addition to C: namespace something { } Which is preprocessing to something_ before every function class someclass { } Which is preprocessing all the functions inside to someclass_fn1(someclass\* asfirstparameter, ...) And of course the final syntax sugar cl\* c; c->fn1(a,b) I mean this would make C much easier, as we already code object oriented in it, but the amount of preprocessing, unreadability that needs to be done in headers is simply brain exhausting
- masfoobar 1y ago???? Unfortunately, you will need to cover more ground with this proposal than what you have presented. It sounds simple but what you are suggesting is very complicated. Of course, to the OOP minds out there, they think their suggestion is a be-all-to-end-all, when in reality there are many ways to solve a problem. I understand what you are trying to do. I am not suggesting it is wrong but C is not an OOP language. I dont see why we should PRETEND that it has OOP-class features when its all you advocating is smoke and mirrors. Sure, C can do "OOP" but I must remind all that these techniques have been in C for years, before the OOP name was popularised and evolved into the form it is now. You are just forcing C programmers to program in such a way OOPLOVERS like when it is not required - and that is the modern OOP than has been forced on everything since the early-to-mid 90's. You are just HIDING whats really going on This proposal you are suggesting -- I am going to call this Typescript-C. The problem is that this namespace/class overlay makes much ASSUMPTIONS what the programmer wants. Lets dig into this further. Here is how (I believe) you see it implemented :- // In my TypeScript-C. namespace Foo { class Bar { int baz; void init() { this->baz = 10; } void free() { // whatever } int process(int withval) { return withval + this->baz; } } } // calling example :- Foo.Bar sample; sample->init(); printf("%d\n", sample->process(100)); sample->free(); This would translate to :- // Translated C... typedef struct Foo_Bar { int baz; } void Foo_Bar_init(Foo_Bar *self) { self->baz = 10; } void Foo_Bar_free(Foo_Bar *self) { // whatever } int Foo_bar_process(Foo_Bar \*self, int withval) { return withval + self->baz; } // calling example :- Foo_Bar sample; Foo_Bar_init(&sample); printf("%d\n", Foo_Bar_process(&sample, 100)); Foo_Bar_free(); My argument is, for starters, how is writing all this namespace and class wrapper actually better than the final code? Anyone that starts using C with namespaces and classes are going to assume we have inheritence, overrides, etc. Why? If anyone is THAT bad they cannot write proper C code, then I suggest they move to C++, Java, C#, Dlang.. or whatever. Its just adding extra fluff -- and C guys like to SEE what is going on. (Thats why it takes ages to truly grasp C++ internals)
- kazinator 1y agoThere is a way for this not to terminate: while (new_capacity < required) { new_capacity *= 2; } 1. All variables are unsigned (due to being size_t). So we don't worry about overflow UB. 2. new_capacity * 2 always produces an even number, whether truncating or not. 3. Supppose required is SIZE_MAX, the highest value of size_t; note that this is an odd number. 4. Therefore new_capacity * 2 is always < required; loop does not terminate.
- teo_zero 1y agoWhat I don't like is that some functions take as arguments a mix of StringBuffer's and regular C strings. This is confusing. For example why this: void StringBuffer_replace(StringBuffer *buf, const char *original, const char *update, size_t from); instead of this: void StringBuffer_replace(StringBuffer *buf, const StringBuffer *original, const StringBuffer *update, size_t from);