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.
> Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something.
Until then, the choice is pretty much between C and C++, and the latter provides a much saner and safer alternative, than a language that keeps pretending to be portable macro assembler.
Requires manual work from people willing to put into the effort, lesser development experience reading documents written for other languages, no out of the box plugins for IDEs, or graphical debuggers support, e.g. CUDA as one such example.
I switched from C++ to C because C++ is too complex and dealing with this complexity was stealing my time. I would not call this a "political reason".
Dealing with security issues is one of my occupations, when having a DevOps role in project delivery, and I rather use that time elsewhere.
void foo(std::vector<int> &x) { x[4] = 1; }
int main() { std::vector<int> x{ 0, 1, 3, }; foo(x); std::cout << x[4]; }
Additionally, until C++26, the way the standard is written, the legalese doesn't forbid the implementation to do bounds checking.
Now can you please enlighten us how to do the same with C arrays and strings, with bounds checking enabled, and why in 50 years WG14 has completely ignored the problem, including Dennis Ritchie proposal for fat pointers, until the government and industry pressure, and even now, I am quite curious if C2y will really bring any actual improvement.
I dunno how it rates it now, but if this link: https://www.reddit.com/r/programming/comments/1m3dg0l/making... gets used for future training, future LLMs might make good suggestions for cleaning it up.
Is mutability not part of the point of having a string buffer? Wouldn't the corresponding immutable type just be a string?
In my experience, the only functions a mutable string buffer needs to provide are "append string (or to-string-able)" and "undo that append" (which mostly comes up in list-like contexts, e.g. to remove a final comma); for everything else you can convert to an immutable string first.
(theoretically there might be a "split and clobber" function like `strtok`, but in my experience it isn't that useful once your APIs actually take a buffer class).
Considering the functions from this implementation, they can be divided as follows:
Lifetime methods:
init
free
clear
print
index_of
match_all
split
append
prepend (inefficient!)
remove
replace
There are also a lot of common operations not provided here. And the ones that are provided fail to work with `StringBuffer` input.
new_capacity *= 2;
https://stackoverflow.com/questions/1100311/what-is-the-idea...
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.
At the small end, on the real machine tiny allocations are inefficient, so rather than 1, 2, 3, 5, 8, 12, 27, 41 turns out we should probably start with 16 or even 64 bytes.
Then at the large end the "clever" reuse is a nonsense because of virtual memory, so that 1598, 2397, 3596 doesn't work out as cleanly as 1024, 2048, 4096
Folly has a growable array type which talks a big game on this 1.5 factor, but as I indicated above they quietly disable this "optimisation" for both small and large sizes in the code itself.
Of course YMMV, it is entirely possible that some particular application gets a noticeable speedup from a hand rolled 1.8x growth factor, or from starting at size 18 or whatever.
Clearly we don't just want a blanket constant, but the growth factor should be a function of the current length - decreasing as the size of the array grows.
For space optimization an ideal growth factor is 1+1/√(length). In the above example, where we have 2 Gi array, we would grow it only by 64ki elements. Obviously this results in many more allocations, and would only use this technique where we're optimizing for space rather than time.
We don't want to be messing around with square roots, and ideally, we want arrays to always be a multiple of some power of 2, so the trick is to approximate the square root:
inline int64_t approx_sqrt(int64_t length) {
return 1 << (64 - __builtin_clzll(length)) / 2;
// if C23, use stdc_first_leading_one_ull() from <stdbit.h>
}
inline int64_t new_length(int64_t length) {
if (length == 0) return 1;
return length + approx_sqrt(length);
}
old length: 2^16 -> new length: 0x00010100 (growth: 2^8)
old length: 2^17 -> new length: 0x00020200 (growth: 2^9)
old length: 2^18 -> new length: 0x00040200 (growth: 2^9)
old length: 2^19 -> new length: 0x00080400 (growth: 2^10)
old length: 2^20 -> new length: 0x00100400 (growth: 2^10)
old length: 2^21 -> new length: 0x00200800 (growth: 2^11)
old length: 2^22 -> new length: 0x00400800 (growth: 2^11)
old length: 2^23 -> new length: 0x00801000 (growth: 2^12)
old length: 2^24 -> new length: 0x01001000 (growth: 2^12)
old length: 2^25 -> new length: 0x02002000 (growth: 2^13)
old length: 2^26 -> new length: 0x04002000 (growth: 2^13)
old length: 2^27 -> new length: 0x08004000 (growth: 2^14)
old length: 2^28 -> new length: 0x10004000 (growth: 2^14)
old length: 2^29 -> new length: 0x20008000 (growth: 2^15)
old length: 2^30 -> new length: 0x40008000 (growth: 2^15)
old length: 2^31 -> new length: 0x80010000 (growth: 2^16)
[1]:https://cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf
> return length + approx_sqrt(length);
They don't seem the same. Should one take the root or its reciprocal?
length * (1 + 1/√(length)) = length + length/√(length) = length + √(length)
Maybe I could've worded it a bit better.
More detail is in the RAOTS paper. It organizes the data blocks into so called logical "superblocks" (which have no material representation). Each superblock is ~n data blocks each of length n. In practice it's not exactly this because when we have an odd number of bits, say 5, we have to split it either 2:3 or 3:2 (for the log2 of num_blocks:block_size). The paper choses the former (same as above), but we could potentially also do it the other way where you have more blocks of smaller average size, but it would be a bit more awkward to index into the data blocks themselves since you'd have have to test for odd/even - which we don't do above because of the /2 integer division, and it would make the index block larger which we'd want to avoid because we have to reallocate it.
So in the approach taken, avg_block_size > √(length) and num_blocks < √(length), but avg_block_size * num_blocks == length still holds, and avg_block_size ≈ √(length) ≈ num_blocks.
If we're reallocating rather than using an index block, replace `num_blocks` with number of times we have to call the allocator.
Hereby I propose an addition to C:
namespace something { }
class someclass { }
someclass_fn1(someclass\* asfirstparameter, ...)
cl\* c;
c->fn1(a,b)
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();
// 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();
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)
However while we're looking at any library, GTK for example, those structs are made like that. But you're right - this only looks simple, as there are many pitfalls we could hit when implementing it.
There are many alternatives or newer languages which I think is the answer to your proposal.
You mentioned Go, which is absolutely reasonable.
However, like all languages, Go has its pros and cons as well. I am sure someone has tried to push for a new feature that may be OOP-like and it gets rejected. You can say that for any language.
We also have Rust, Odin, Zig, C3, etc -- all have their own sprinkles and flavours on how to do things. These are "better C" or "better C++" depending on how you view it.
Personally I prefer Odin. It (kinda) has namespaces but there are no classes... and functions/procedures are still created outside the struct. To me, out of the many languages, Odin keeps it C but with many improvements and I am happy with that.
Each to their own.
while (new_capacity < required) {
new_capacity *= 2;
}
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.
void StringBuffer_replace(StringBuffer *buf,
const char *original,
const char *update,
size_t from);
void StringBuffer_replace(StringBuffer *buf,
const StringBuffer *original,
const StringBuffer *update,
size_t from);
ranger_danger•6mo ago
fsckboy•6mo ago
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•6mo ago
I think that would break its "Compatible with normal C string functions" feature.
fsckboy•6mo ago
ranger_danger•6mo ago
fsckboy•6mo ago
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 )
ranger_danger•6mo ago
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
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?
fsckboy•6mo ago
I explained how returning the address of the string buffer instead of the address of the struct would give you a C compatible string that you could pass to other C library functions. If those functions are "readonly" wrt the string, everything is copasetic.
if those string functions update/write the c-string (which is in the buffer) the strlen in the header will now be wrong. That has nothing to do with my suggestion, and it's already "broken" in that way you point out. My "string free bytes field" suggestion will also be broken by an operation like that, so my suggestion does not make this data structure worse than it already is wrt compatibility with C library functions.
However that strlen and free bytes problem can be managed (no worse than C standard strings themselves) and strlen and/or free bytes are useful features that make some other things easier so overall it's a win.
ranger_danger•6mo ago
> i did see a place to shave a byte in the sds data struct. The null terminator is a wasted field
I'm still not sure what byte in the struct you're talking about removing... because I don't see an actual null terminator field.
fsckboy•6mo ago
the strlen field can be moved to where the word "null term" appears, except with a changed semantic of "bytes remaining" so it will go to zero at the right time. now you have a single entity "bytes remaining" instead of two entities, "strlen" and "null" giving a small storage saving (there is an additional null terminator most of the time, right at the end of the string; but this doesn't take up any storage because that storage is not used for anything else)
over and out.
ranger_danger•6mo ago
Yes but it does not appear anywhere in the struct that I can see... I would love to be proven wrong though.
fsckboy•6mo ago
dernett•6mo ago
fsckboy•6mo ago