News for hackers. Stuff that matters.
Re:Efficient string copying and concatenation in C by antirez on Thursday September 12, 2019 @12:39PM (#20953507)
I can't see how incrementally improving the approach of the C standard library is the right design decision here. They need to just include a standard, well designed dynamic strings library to C, that stores the length alongside with the (binary safe) string itself, and that's all. Every serious C program uses it, null terminated strings are a joke. However because of this huge background with null terminated strings in C, such library should make sure to always automatically terminate strings with a null term, so that people can trivially print them, call strlen() against them and so forth when needed and when there is no binary data inside.
Re:Efficient string copying and concatenation in C by Steven_Vellon on Thursday September 12, 2019 @01:19PM (#20953955)
A lot of C developers I know see value in keeping the C standard library small. I implemented my own `l_string` (length-string) struct and associated libraries for a class (we weren't allowed to use external libraries) and it was not prohibitively difficult. Something like this probably covers most use cases: https://github.com/antirez/sds
Re:Efficient string copying and concatenation in C by nneonneo on Thursday September 12, 2019 @08:33PM (#20957953)
Sadly, real C standard libraries are anything but small. glibc is pretty huge; statically linking a simple hello world program produces something like 750KB of output (libc.so itself is nearly 2MB in size). A quick peek at glibc's documentation shows just how much stuff there is: https://www.gnu.org/software/libc/manual/html_mono/libc.html.

Unfortunately, I wouldn't call all of it critically useful stuff. For example, "strfry" and "memfrob" are useless beyond toy applications as neither are remotely secure; "l64a" and "a64l" are useless (and possibly even dangerous) because they look like they implement base64 but with a different alphabet (and a much worse API); they have a hilariously large number of random number generators, _none_ of which produce high-quality random numbers for simulation or especially cryptography; etc. etc.

Neither MSVC nor macOS will let you truly statically link a binary (because the system interfaces aren't constant), so it's harder to directly compare, but on macOS "libSystem.dylib" depends on basically everything in /usr/lib/system which is about 5MB of code.

So yeah, I don't think I'd call many real libc libraries "small" by any stretch.

Re:Efficient string copying and concatenation in C by dottrap on Thursday September 12, 2019 @08:49PM (#20958042)
Here is a web page comparing the different C library implementations:

http://www.etalabs.net/compare_libcs.html

For the .a size:

musl: 426k

uClibc: 500k

dietlibc: 120k

If you statically link to these, your final binary will only pull what is actually needed and be smaller than this.

Re:Efficient string copying and concatenation in C by BubRoss on Friday September 13, 2019 @10:36AM (#20962540)
I know they are smaller, but why are they able to only pull in what you use when other libc implementations can't?
Re:Efficient string copying and concatenation in C by dottrap on Saturday September 14, 2019 @12:54AM (#20968986)
Any that allows static linking will get the same benefit.

For the three mentioned in the ancestor thread:

Apple doesn't ship a static libc, so developers must dynamically link.

glibc does allow static linking, but it is something they don't really go out of their way to promote and I recall some historic pains trying to get it to work right. Maybe that all works better today.

MSVC does allow static linking to msvcrt. MSVC is a little different than other platforms because they have permutations (and associated rules) you must be aware of: [debug | release], [static | dynamic], [single-threaded | multithreaded].

Re:Efficient string copying and concatenation in C by rurban on Friday September 13, 2019 @06:46AM (#20960884)
glibc is only so bloated because of locale und unicode support. Also 32bit wchar_t and intl errors.

Adding better string functions or CPU-specific optims is nothing compared to that.

musl is mostly so small because it only does the C locale and basic unicode towlower. Nothing like the monstruous glibc unicode tables or internationalized error messages.

Re:Efficient string copying and concatenation in C by antirez on Friday September 13, 2019 @04:54AM (#20960353)
I don't see value in keeping the C standard library small in this regard, since everybody is going anyway to implement this kind of code from scratch, it's like not having stdio.h for FILE* operations. However... the library you linked is surely a good pick according to me since I'm the author myself :-D
Re:Efficient string copying and concatenation in C by sdegutis on Thursday September 12, 2019 @03:07PM (#20955152)
I really love his trick of returning a pointer to the inside of his own allocated memory which is then compatible with C's stdlib string functions, while having his own string functions use pointer arithmetic to get the real struct back out and operate on that. Genius! This is the kind of thing that keeps drawing me to C every once in a while. C is almost like a puzzle, to figure out how you can accomplish what would be trivial in JavaScript, but with all these restrictions caused by an almost extreme simplicity. (Granted, C is not actually simple when you start hitting all the weird edge-cases and surprising UB, etc.)
Re:Efficient string copying and concatenation in C by stkdump on Thursday September 12, 2019 @03:31PM (#20955422)
I don't love this trick. To get this to work, they had to typedef the string type to char*, which means the API will also accept any normal string and probably crash at runtime. So to get this little convenience feature, type safety was sacrificed.
Re:Efficient string copying and concatenation in C by tmp0258 on Thursday September 12, 2019 @06:38PM (#20957216)
Seems to me that it would also prevent tools like the address sanitizer and valgrind from detecting some invalid memory accesses (corresponding to negative indexes). A "more conventional" string library [1] might be safer.

[1] for example: https://github.com/websnarf/bstrlib/blob/master/bstrlib.txt

Re:Efficient string copying and concatenation in C by einpoklum on Thursday September 12, 2019 @04:32PM (#20956125)
> A lot of C developers I know see value in keeping the C standard library small.

And what value what that be?

... if you're going to say "easier to fit a small implementation into the memory of some microcontroller" - not a sufficient argument. There's always some smaller system with not enough memory, and larger systems with more than enough.

Re:Efficient string copying and concatenation in C by kjeetgill on Thursday September 12, 2019 @04:43PM (#20956229)
This is C land. You're not going to make it far by making the case that bloat is acceptable.

People have a range of technical and aesthetic reasons for hating bloat and C attracts a lot of them.

Off the top of my head:

- Smaller memory footprints

- Easier reimplementation

- Lower attack surface

- Less room for breaking changes

- Less baggage for when we inevitably wish we could deprecate things

Re:Efficient string copying and concatenation in C by einpoklum on Thursday September 12, 2019 @07:17PM (#20957508)
> Smaller memory footprints

Nobody said you need to link the entire library.

Plus - with custom-made libraries, the memory footprint is no smaller.

> Easier reimplementation

Implementation begins with some part of the standard library, and gets completed gradually later on.

> Lower attack surface

Are you really arguing in favor of "everyone roll your own library" as a reduction of attack surface?

> Less room for breaking changes

C's standard library was already broken in various significant ways to begin with (e.g. gets() ...) .

Also, are you really worried about all those breaking changes between C99 and C11?

> Less baggage for when we inevitably wish we could deprecate things

Umm, you do realize things usually get deprecated when they've been replaced by something more relevant, right? In our case - new C library code.

Re:Efficient string copying and concatenation in C by AceJohnny2 on Thursday September 12, 2019 @04:52PM (#20956327)
> - Lower attack surface

wut?

Re:Efficient string copying and concatenation in C by Steven_Vellon on Thursday September 12, 2019 @04:54PM (#20956346)
String formatting libraries, and other things that work with buffers are frequent attack surfaces for buffer overflow attacks.

Granted, using C means developers often implement these operations themselves which introduces the possibility of creating more attack surfaces. But it's less likely that the standard library presents an attack surface when the standard library is tiny.

Re:Efficient string copying and concatenation in C by AceJohnny2 on Thursday September 12, 2019 @06:06PM (#20956969)
I mean, C's attack surface is like that of activated charcoal. I'm not sure that C's small standard library gives it a smaller attack surface, specifically because it means programmers who have better things to do are forced to reinvent the wheel, poorly [1]. But mostly, because C's lack of guardrails means it takes active effort on even trivial operations to be safe.

I've been working with it for nearly two decades, and every year I think more that C programs should be confined to a well-guarded quarantined area with hazard trefoils and a "beware of the leopard" sign.

[1] https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule

edit: people reimplementing their "safe" string library isn't something to brag about, but be ashamed of our entire industry for.

Re:Efficient string copying and concatenation in C by antirez on Thursday September 12, 2019 @06:00PM (#20956924)
Actually not having dynamic strings and buffers in the library is one of the main reasons people do pointer math and reallocations by hand introducing memory corruption bugs.
Re:Efficient string copying and concatenation in C by dottrap on Thursday September 12, 2019 @09:20PM (#20958225)
> And what value what that be?

A lot of embedded development still have very tight requirements. We're still talking about things discussed in tens or if generous, hundreds of kilobytes.

As a more mainstream example you might have heard of, the Arduino, I think the baseline Arduino has around 32KB available.

Also, in the embedded space, the compilers used are notorious for not having a complete standard library implementation. Lots of things are missing. Thus, developers who care about porting their code to different chips, are cautious about limiting what standard library functions they depend on.

Again, as a more mainstream example you might have heard of, look at Lua, which is implemented in 100% ANSI C. Because they care about Lua truly being portable to everywhere, they try to constrain their dependence on the standard library, and they supply some #ifdefs in luaconf.h to implement or workaround some standard library functions they know to be often missing.

And as a more mainstream example of an incomplete C standard library, look at Android. Bionic is the name of their C standard library. It is missing a lot of things. (And you have to use one of those #ifdefs in luaconf.h to compile Lua successfully on Android to workaround Bionic.)

Re:Efficient string copying and concatenation in C by kerkeslager on Thursday September 12, 2019 @06:51PM (#20957316)
There's some nuance to be had here. The important implications of a larger C standard library aren't technical, they're social--i.e. the implications of a larger standard library for teams using C are negative. Let's look at two other languages: C++ and Python.

C++ has a large standard library. This ends up being one of C++'s biggest downfalls: the various libraries don't play nicely with each other, have many different ways of doing the same or similar things, each have complex gotchas--and it's impossible to know them all, so you never really know C++. It's full of dark corners, and the result is bugs, and difficult debugging, and teams that try to enforce only using subsets of the language (and inevitably fail a little). This problem is only getting worse over time. The reason C++'s new features haven't just been backported back into the C standard is that people saw this coming and didn't want it happening. C is already a complex language, but it's still simple enough that you can actually reasonably read the entire C standard library (I have; QED).

A large standard library doesn't have to be this way. Python has a large standard library--this is the "batteries included" of Python. The reason Python can get away with this is that they can deprecate their mistakes. And they are: quite a few modules in the standard library will disappear with the Python 2 sunset. But this is not without downsides--everyone who has been working on a major Python project in the past few years has felt the pain at some point. And C is not Python: it's the backbone of a lot of other applications, so breaking changes are far more costly for C than for Python. C is "once supported, always supported", and for very good reason, so we can't afford to introduce mistakes to the standard.

So, if you don't want the problems of all the cruft in C++'s standard library, and you don't want the deprecations of Python's standard library, your only remaining choice, by process of elimination, is to have a very slim standard library, and make VERY conservative choices about what to add to it.

I think that we should add a new string library to C when strings are a solved problem. But contrary to what people are saying, strings aren't a solved problem. We shouldn't add a string library that doesn't solve internationalization, for example. And in fact, with that problem, the fox is in charge of the henhouse, making the problem worse: we've got people in the Unicode team adding fsking emoji to the standard. Unfortunately, I think we're going to have to wait until Unicode collapses under its own bad decisions and is replaced by a better standard, and that standard becomes mature, before committing to that proven solution. Otherwise we end up with ICU-related crap into the "once supported, always supported" C standard library.

Re:Efficient string copying and concatenation in C by einpoklum on Thursday September 12, 2019 @07:29PM (#20957588)
> C++ has a large standard library.

Is it that large? i.e. is it larger than, say, Java's ?

> it's impossible to know them all, so you never really know C++

This is semantic quibbling. You know a language more if you know its commonly-used libraries better - whether they're in the standard or not.

> the various libraries don't play nicely with each other

They may not be in perfect synch, but they play ok-ish-ly with each other - as far as I can tell.

However, not playing nice is much much more of a problem with non-standard libraries - in various languages. I'm sure C programmers have that experience with a vengeance... say, everybody using different implementations of basic data structures like queues and lists and hash tables and so on.

> It's full of dark corners

Yes, yes it is. And they're pretty scary... however, that's not really because of the library size. Also, those dark corners exist, unexplored, for C libraries; it is arguably better that they be mapped once and for all, at least some of them which are somewhat-frequently stumbled upon.

...

More generally - the issue you're describing seems to be more with the combination of "iron-clad backwards compatibility" and a larger standard library:

- C has the former, not the latter - Python has the latter, not the former

C++ has the former (upto minor points like the `auto` keyword), as well as the latter, but with warts.

The warts are there, that's true, but they're not so bad. And use of the standard library does pay off very nicely - often removing warts in your own code.

Re:Efficient string copying and concatenation in C by kerkeslager on Thursday September 12, 2019 @07:47PM (#20957687)
> Is it that large? i.e. is it larger than, say, Java's ?

Large, yes. Larger than Java's? I don't know.

It's larger than C's, that's for sure.

> This is semantic quibbling. You know a language more if you know its commonly-used libraries better - whether they're in the standard or not.

If it's in the standard library you better bet it gets used, even if only by your dependencies.

> I'm sure C programmers have that experience with a vengeance... say, everybody using different implementations of basic data structures like queues and lists and hash tables and so on.

Eh, it's not too bad in C. Libraries tend not to force you to use their data structures too much, and if they do, you just don't use that library. Some, you use their data structures because that's what you included the library to get. It's certainly a problem, but dependency management is easier than having dependencies you can't make go away.

> The warts are there, that's true, but they're not so bad. And use of the standard library does pay off very nicely - often removing warts in your own code.

So use C++, if you like it.

My post wasn't an attack on C++. C++ has its upsides. I only described the downsides of C++ because I was explaining what C is trying to avoid.

Re:Efficient string copying and concatenation in C by segfaultbuserr on Thursday September 12, 2019 @12:44PM (#20953565)
Here's a stupid but somewhat relevant case: Recently, I saw a surprisingly insidious variation of the "FizzBuzz" question in C. Like the usual FizzBuzz, but with a twist: You are required to return your answer as "char (star)" with a separator "\n", the memory should be allocated dynamically, assuming the user calls free(). A naive implementation that strcat() / realloc() the string and repeats it a thousand times, a better solution is to overestimate the required memory and malloc(). Adding a different constraint can make the question quickly become effectively "reimplement std::vector in C", and in real applications, something like this occurs daily, all C programmers have their own standard library, so I guess C++ is at least useful for its standard library...
Re:Efficient string copying and concatenation in C by ben7799 on Thursday September 12, 2019 @02:27PM (#20954699)
How is this a stupid interview question?

There are a lot of positions this would be a great indicator of whether or not the candidate could do the job.

If low level programming is involved the candidate better be able to handle this. Just cause you don't have to solve this problem every doesn't mean you're not going to need those skills for systems programming, writing drivers, embedded programming, etc..

I suspect this would have an extremely high weed out rate actually. A very large % of so called software engineers would fail this, certainly anyone who did all their learning in a dynamic language with automatic garbage collection and who had not branched out into lower level programming.

It's a dumb question if the job position is for a Javascript UI dev of course.. it's not a good question for all positions.

I would also say it's a travesty for any school to award anyone a bachelor's degree in computer science to someone who would fail this question. I've interviewed a large # of candidates with master's degrees who would fail this. Thankfully most of those candidates didn't have a bachelors in computer science + a masters in computer science from a highly ranked US institution.

Also someone who groks this problem and solves it is way less likely to write memory leaks into code in a garbage collected language.

Re:Efficient string copying and concatenation in C by segfaultbuserr on Thursday September 12, 2019 @02:49PM (#20954943)
I didn't really meant to criticize the question itself, just use it to make a point on C's stdlib that the OP was talking about.
Re:Efficient string copying and concatenation in C by kazinator on Thursday September 12, 2019 @03:48PM (#20955621)
It's good to measure all the pieces (if you can) or get an upper-bound estimate, allocate once, then move in.

http://www.kylheku.com/cgit/txr/tree/lib.c?id=txr-225#n3897

(The mysterious wini, wref and auto_str macros here allow a C character array on the stack to be a Lisp value with a type tag, recognized and ignored by the garbage collector.)

Re:Efficient string copying and concatenation in C by drng on Thursday September 12, 2019 @06:32PM (#20957175)
Am I missing something here? Assuming you're writing `char * fizzbuzz(unsigned n)`, can't you determine exactly how many bytes you need at the outset from `n` and just malloc once?
Re:Efficient string copying and concatenation in C by Steven_Vellon on Thursday September 12, 2019 @06:44PM (#20957256)
There are some variations of fizzbuzz that have you print out the number of iterations performed at that point on each line. The memory consumption could still be predetermined, but the math is a bit more complicated. Other variations have you reading integers from a stream (integers are not in any order), printing "Fizz" and "Buzz" when it's a multiple of 3 and 5 respectively, and that does not have a predetermined memory footprint.

While FizzBuzz has become notorious for weeding out total incompetence [1], there are some variations of the problem that are unexpectedly nuanced.

1. https://thedailywtf.com/articles/The-Fizz-Buzz-from-Outer-Sp...

Re:Efficient string copying and concatenation in C by simias on Thursday September 12, 2019 @12:51PM (#20953643)
I'm not really sure what's the point of this exercise instead of a regular FizzBuzz. Dealing with strings in C is tedious, error prone and results in very verbose code but it's not really difficult per-se. What is this testing for exactly?

If I had to do something like that in a real program I'd very much overalloc a few bytes (because why not? If those small allocations really become a problem in your app you probably want to use a custom allocation scheme anyway) and then just snprintf the result into it. I'd go even further and say that code that would micro-optimize this to save a couple of bytes at the cost of maintainability shouldn't pass a code review IMO.

Re:Efficient string copying and concatenation in C by segfaultbuserr on Thursday September 12, 2019 @12:57PM (#20953712)
Exactly.

It's why call it "stupid", "insidious", but "somewhat relevant", as the parent comment proposes a better stdlib in C to handle strings.

Re:Efficient string copying and concatenation in C by partialrecall on Thursday September 12, 2019 @01:49PM (#20954267)
For some jobs, tolerance to tedium is considered a skill.
Re:Efficient string copying and concatenation in C by jly on Thursday September 12, 2019 @05:01PM (#20956418)
FizzBuzz covers a lot of (very basic) ground but adding memory manipulation is valuable. I ask a few simple string manipulation interview questions for embedded C developers as a weeder and the point is that we want to see how candidates deal with pointers and low level memory. There are other good follow-ups and alternatives you can build off this. Engineers with years of experience fail these questions all the time. Dealing with 'tedious' things like this is daily part of some developer jobs.
Re:Efficient string copying and concatenation in C by Steven_Vellon on Thursday September 12, 2019 @03:57PM (#20955726)
Is it not possible to keep allocating contiguous memory? Just keep appending to the string and allocating more memory. Repeated calls to malloc are not guaranteed to be contiguous but I think you can do this with posix_memalign. Just keep growing the heap segment, and appending more character to it. I suppose it's not going to be contiguous in physical memory, but it should in virtual memory.
Re:Efficient string copying and concatenation in C by termie on Thursday September 12, 2019 @04:10PM (#20955906)
You can use realloc. It will try to use the existing contiguous span of memory, but if it cannot, it will malloc a new span and copy the previous bytes in and return a pointer to it.
Re:Efficient string copying and concatenation in C by Steven_Vellon on Thursday September 12, 2019 @04:22PM (#20956022)
In that case, you need to test if the memory is contiguous and copy to the new pointer if not. O(N^2) in the worst case, where every memory allocation returns a distinct start pointer.

What I was getting at is that in virtual memory the heap is always contiguous (even if it isn't in physical memory, but we only need it to be contiguous in virtual memory). So one can guarantee that the solution will never require copying data if the program exclusively uses the stack, and the resultant string is the only piece of data on the heap. You always add contiguous memory so your string can dynamically grow without ever copying to a new buffer. This probably requires allocating memory through the use of OS-specific syscalls to request new memory pages instead of malloc or realloc.

Re:Efficient string copying and concatenation in C by termie on Thursday September 12, 2019 @05:24PM (#20956628)
Yes, the kernel will map virtual to physical however it sees fit, no guarantees there (at least not in user-space via glibc). Realloc will always return a virtually contiguous slice or NULL if it can’t. And you’re right, obviously all those potential subordinate mallocs would be inefficient. :) In this contrived FizzBuzz example case, you could pretty easily do the math and just malloc it all in one go at the start of the function. Fizz and Buzz are the same size, you would just need to add up the iota lengths and the trailing \0. If you take an arg for N (1..N) then stack allocations are not going to work. You need to statically declare their size.
Re:Efficient string copying and concatenation in C by Steven_Vellon on Thursday September 12, 2019 @06:36PM (#20957200)
What I'm getting at, though, is that it's possible to implement it without any copies even if the memory consumption cannot be predetermined. Bypass malloc() and realloc() entirely and invoke brk() to increase the program's segment size. This grows the data segment contiguously (in virtual memory), so there will never be a need to copy the result string to a different buffer. In other words point the result pointer to the start of the heap, and never put anything else on the heap.
Re:Efficient string copying and concatenation in C by unkulunkulu on Thursday September 12, 2019 @05:04PM (#20956434)
O(N) is worst if you realloc exponentially with O(N) worst case possible extra unused space in the end
Re:Efficient string copying and concatenation in C by billziss on Thursday September 12, 2019 @01:00PM (#20953766)
While I often implement strings along the lines you suggest I disagree that this feature belongs in the standard library. For one thing how big (sizeof) should the length prefix be? 16-bits? 32-bits? 64-bits?

The beauty of the C string is that it is minimal and straightforward: if you have a pointer to it, you know where it ends. And it works with pretty much any OS out there.

(My personal variant of dynamic strings are refcounted, length prefixed and nul-terminated with the pointer pointing to the traditional C string.)

Re:Efficient string copying and concatenation in C by jcranmer on Thursday September 12, 2019 @01:24PM (#20954003)
> For one thing how big (sizeof) should the length prefix be? 16-bits? 32-bits? 64-bits?

size_t, or uintptr_t [1]. Maybe uint32_t, although given pointer alignment, smaller-than-pointer for size doesn't help all that much.

> The beauty of the C string is that it is minimal and straightforward: if you have a pointer to it, you know where it ends.

And if you screw up adding a null byte, client code will happily keep running through the rest of memory to find it. And if your string has embedded nulls, you're SOL anyways.

> And it works with pretty much any OS out there.

And for safety reasons, the OS generally has to assume a maximum length anyways, otherwise, you tend to have security vulnerabilities.

[1] size_t is not necessarily the same size as uintptr_t. An architecture with a 64-bit base pointer shared across several 32-bit indexes is an interesting idea that could use some more programming exploration.

Re:Efficient string copying and concatenation in C by kzrdude on Thursday September 12, 2019 @01:14PM (#20953907)
Using size_t as the common solution seems like the way to go.

    struct string { char *data; size_t size; size_t alloc_size; };
    struct string_view { char *data; size_t size; };
And we have the same design that C++ uses.
Re:Efficient string copying and concatenation in C by nneonneo on Thursday September 12, 2019 @02:42PM (#20954847)
C++ implementations sometimes optimize for storing short strings inside the string structure itself. One approach looks something like this on 64-bit machines:

    struct string {
        union {
            struct {
                char *ptr;
                size_t capacity;
            };
            char str[16];
        } data;
        size_t length;
    };
It looks complex, but it’s actually a really nice design because it requires no separate allocation for strings less than 16 bytes long, which is a common case, and the strings are relatively compact. And, it stores a capacity parameter which allows you to know when it’s safe to grow the string without allocating, making it possible to implement efficient repeated concatenation.
Re:Efficient string copying and concatenation in C by billziss on Thursday September 12, 2019 @01:31PM (#20954072)
I do not think I have ever seen a string that needs more than 64K, but then again I do not read whole files in memory in C. (I do in Python.) So this would be wasteful in many cases.

My personal variant uses 32-bits for length and 32-bits for refcount, which aligns well on most platforms, including 64-bit ones.

Something like:

    struct string_header
    {
        int32_t refcnt;
        int32_t length;
        // character content starts here
    };
Given a char pointer to get to the header you must do:

    ((struct string_header *)p)[-1]
Re:Efficient string copying and concatenation in C by papermachete on Thursday September 12, 2019 @03:21PM (#20955316)
>I

>I

>I

There is no 'I' in standard libraries :)

Re:Efficient string copying and concatenation in C by saagarjha on Thursday September 12, 2019 @01:42PM (#20954197)
How would you use the refcount?
Re:Efficient string copying and concatenation in C by billziss on Thursday September 12, 2019 @01:53PM (#20954311)
I use the refcount to avoid copying the string when passing it around. I just refcount it instead.

To clarify this is part of a larger library that includes other memory management machinery, such as autorelease pools, etc.

Re:Efficient string copying and concatenation in C by benj111 on Thursday September 12, 2019 @03:03PM (#20955110)
Why not go full Pascal strings, and go for 8 bit?

The good thing about 64 bit lengths is you never need to worry about overflowing the string. The bad thing is no one know what to do, or codes for the possibility of the string overflowing. 8 bits 'should' avoid people making that assumption.

Re:Efficient string copying and concatenation in C by Gibbon1 on Thursday September 12, 2019 @08:07PM (#20957792)
The was my thought earlier this morning.

Something anything is better than the total shit design we've been living with.

Re:Efficient string copying and concatenation in C by kreco on Friday September 13, 2019 @03:59AM (#20960100)
> For one thing how big (sizeof) should the length prefix be? 16-bits? 32-bits? 64-bits?

Exactly like what is returned by strlen... ?

Re:Efficient string copying and concatenation in C by chrisdew on Friday September 13, 2019 @04:22AM (#20960208)
Is your string library open sourced? Could you provide a link?
Re:Efficient string copying and concatenation in C by kazinator on Thursday September 12, 2019 @03:43PM (#20955571)
No matter what string manipulation method you use, you have to produce linear, null-terminated strings for passing into all sorts of existing API's, standard and not.
Re:Efficient string copying and concatenation in C by masklinn on Friday September 13, 2019 @02:21AM (#20959680)
That's really not an issue when done for you. std::string does it just fine.
Re:Efficient string copying and concatenation in C by B1FF_PSUVM on Thursday September 12, 2019 @03:17PM (#20955255)
> null terminated strings are a joke.

There was a quiet market war some forty years ago about that, and Pascal lost.

But yeah, now we can afford it, the downsides vastly exceed the vanishing cost.

Re:Efficient string copying and concatenation in C by stkdump on Thursday September 12, 2019 @03:23PM (#20955336)
I think the problem with Pascal's strings wasn't that they stored a length. The problem was that every string variable always occupied 256 bytes of RAM and no string could ever be bigger than 255 characters.
Re:Efficient string copying and concatenation in C by sllabres on Thursday September 12, 2019 @05:37PM (#20956748)
UCSD-, TP/BP-, Freepascal?
Re:Efficient string copying and concatenation in C by sllabres on Thursday September 12, 2019 @06:41PM (#20957234)
I was in the impression that TP strings grew dynamically (memory), but I just checked for TP and this seems to be wrong. Probably too much time has passed since then ;)
Re:Efficient string copying and concatenation in C by greiskul on Thursday September 12, 2019 @05:19PM (#20956580)
And looking at modern languages, I would say that C strings also lost, just latter, since none of them do strings that way anymore.
Re:Efficient string copying and concatenation in C by Gibbon1 on Thursday September 12, 2019 @08:42PM (#20957996)
A good reason for adding a modern string type to C would be for better interop between other languages and C.
Re:Efficient string copying and concatenation in C by nicoburns on Thursday September 12, 2019 @12:48PM (#20953594)
Agreed. I feel like such a library probably also ought to support slices/arrays in the same style. I get that the C community is conservative, but this seems like a pretty non-invasive change that would make C code much less bug prone, and faster to boot!
Re:Efficient string copying and concatenation in C by antirez on Thursday September 12, 2019 @12:51PM (#20953637)
Yep, ISO C should get an optional library, that embedded systems may want to skip, offering things like: dynamic strings, linked lists with iterator, an ordered dictionary data structure with iterator (API will be like a hash table basically), a PRNG that is not a joke. With just that it will feel like programming in a different language.
Re:Efficient string copying and concatenation in C by nneonneo on Thursday September 12, 2019 @08:15PM (#20957837)
Several flavours of BSD provide header-only libraries for linked lists and search trees as part of their libc in sys/queue.h and sys/tree.h, which are remarkably nice and easy to use. newlib libc provides these, and macOS used to provide them in /usr/include (now they're only in the kernel headers - but they're header-only and self-contained so they're easy to add to any project).

sys/queue.h provides four different linked list implementations: standard singly-linked lists, standard doubly-linked lists, a singly-linked list with a tail pointer (for fast tail insertion) and a doubly-linked list without a head pointer. All come complete with

sys/tree.h provides two types of balanced search trees: splay trees and red-black trees. Both provide ordered dictionaries

Both libraries make quite extensive use of macros, but they are quite reasonably implemented and documented via man-page. I've successfully used them a few times. Shame that, like other nice BSD innovations (e.g. strlcpy/strlcat) they haven't made it into other libcs.

Re:Efficient string copying and concatenation in C by saagarjha on Friday September 13, 2019 @12:27AM (#20959170)
> macOS used to provide them in /usr/include (now they're only in the kernel headers - but they're header-only and self-contained so they're easy to add to any project)

They've been moved to the Xcode Command Line Tools with the rest of the standard headers.

Re:Efficient string copying and concatenation in C by Sean1708 on Friday September 13, 2019 @09:37AM (#20962007)
> doubly-linked list without a head pointer

Off-topic, I know, but what's the benefit of this and how does it differ from a doubly-linked list without a tail pointer?

Re:Efficient string copying and concatenation in C by jcranmer on Thursday September 12, 2019 @01:28PM (#20954036)
ISO C already mandates that most of its library is optional for "freestanding" implementations. (float.h, iso646.h, limits.h, stdalign.h, stdarg.h, stdbool.h, stddef.h, stdint.h, and stdnoreturn.h are the only headers required even for freestanding implementations).
Re:Efficient string copying and concatenation in C by derefr on Thursday September 12, 2019 @04:05PM (#20955833)
What if we just created a standard [and related working group] that exists "downstream" of ISO C, where there is one release of the "C-with-batteries" per ISO C release (e.g. Cwb11 would descend from C11; Cwb18 from C18; etc.) that just adds these sort of "obvious" libc parts (or libcwb parts, I guess) that the C standards committees don't seem to want to bring into the "base" libc, without changing C itself otherwise?

Then compilers wanting to support the "with-batteries" superset standard could just allow their flag that looks like "-std=c90" to be extended like "-std=c90+batteries".

Re:Efficient string copying and concatenation in C by wruza on Thursday September 12, 2019 @08:36PM (#20957967)
It is called Objective-C and it was pretty popular recently. Strings, arrays, classes, jsonserialization, etc.

Or you can JUST use D.

Why people always skip enormous work already done decades ago and whine that they miss something and something in C?

Re:Efficient string copying and concatenation in C by derefr on Friday September 13, 2019 @12:42AM (#20959231)
If every C compiler and C runtime shipped with CoreFoundation, I'd agree with you. Some undertakings are too enormous for 100 different implementors to want to go through the trouble of making their own implementations of it!
Re:Efficient string copying and concatenation in C by dooglius on Thursday September 12, 2019 @04:37PM (#20956173)
Why would you need compiler support? It's not like C doesn't already support libraries.
Re:Efficient string copying and concatenation in C by derefr on Thursday September 12, 2019 @05:08PM (#20956485)
The whole point of libc—or any language runtime—is that it's "just there." In other words, insofar as a piece of code "is C", it can expect to have access to these libraries; and insofar as a compiler "is a C compiler", it will be expected to link your code to a runtime that includes these libraries.

What this means is that:

• people who are learning a language, can learn language features "through" examples that rely on the included batteries to demonstrate a point (for example, image support in DrRacket, or the HTTP client in Go), without needing to also learn everything involved in ecosystem package management first;

• people who want to write small, self-contained, yet portable utility programs (e.g. coreutils), can just rely on the language runtime and its presence on basically every OS, rather than declaring package dependencies (= not portable) or statically linking in their own libraries (= not small). The more stuff a language's runtime does, the more such programs become possible to write in said language.

• features in a shared runtime can rely on other things in a shared runtime; and the library ecosystem of a runtime can use the runtime's data-structures as a lingua franca to specify library APIs in terms of. JS libraries return promises because the JS runtime includes promises. Elixir libraries pass around DateTimes because the Elixir runtime specifies a DateTime type. Go libraries take and return slices, maps, and channels because those are things that exist in the runtime. If these runtimes didn't have these things—even if the languages had fancy macro systems that meant that pulling in the relevant library would enable exactly the same syntax—then library support for these would be fragmented, rather than expected. Exactly the way library support for prefix-length strings is in C.

Re:Efficient string copying and concatenation in C by NikkiA on Thursday September 12, 2019 @07:19PM (#20957533)
string literals without having to process a asciz string into a ptr+size string at runtime, would be nice. C++ has language support that could enable that regardless of a future string format, of course, but C doesn't.
Re:Efficient string copying and concatenation in C by nicoburns on Thursday September 12, 2019 @06:22PM (#20957099)
What's your take on the benefit of this over actually programming in a different C-like language (zig for instance)?
Re:Efficient string copying and concatenation in C by m463 on Thursday September 12, 2019 @05:25PM (#20956640)
serious question: why doesn't C improve much?

I understand there are benefits to small or no changes whatsoever.

I also understand there are a number of standards (1990, 95, 2011...)

Is it that all the people who would be interested in improving C just naturally migrate to C++ which is getting improvements?

Your example of better strings is good, but why not lists and hashes as language elements?

If not in the language directly, then ok in the library. But speaking of the library, why limit to just a few things, why not batteries fully included. shoot for knuth in the standard library!

Re:Efficient string copying and concatenation in C by johnisgood on Thursday September 12, 2019 @09:29PM (#20958286)
> Your example of better strings is good, but why not lists and hashes as language elements?

Probably because there are many ways to implement data structures, for very specific, and entirely different use cases. C gives you the minimum that allows you to build those according to your own specific needs. It would be very difficult or perhaps even impossible to come up with an implementation that suits everyone's specific cases. Perhaps we could do it by giving the users the option to pick, but then the language would be really huge, it would quickly become bloated. Think about how many ways one could implement a hash table! I like and use ohash extensively though, along with stuff from sys/queue.h. For hash tables, uthash seems to be popular, too.

> If not in the language directly, then ok in the library. But speaking of the library, why limit to just a few things, why not batteries fully included. shoot for knuth in the standard library!

There are many libraries out there. GLib comes to mind. There is also Gnulib, Klib, and God knows what else. I am sure there are a lot of libraries. I have written my own private library of common data structures, subroutines, and so on. You may want to take a look at: https://github.com/kozross/awesome-c

Re:Efficient string copying and concatenation in C by flukus on Thursday September 12, 2019 @08:22PM (#20957877)
In the case of strings it's because in practice it's just not that much of a problem. If your not in a highly constrained environment you'd just use one of several libraries like glib that have strings and other stuff you'd typically find in the standard libraries of other languages. These libraries have the freedom evolve faster, break backward compatibility, not have to worry about committee design and keeping everyone happy, limit themselves to certain classes of machines and do all sorts of things you can't in a standard library.

C has an anemic standard library but many libraries you can use as your standard, this keeps everyone happy. I'd expect the javascript/npm world to evolve this way in future.

Re:Efficient string copying and concatenation in C by crpatino on Thursday September 12, 2019 @08:35PM (#20957963)
It all depends on your definition of improvement...

C is a bit like a Formula One car. Regardless of the historic reasons that caused it to evolve the way it did, it ended up occupying a niche and being very well suited to it, while at the same time being ill suited for other, more general purpose, uses. Under that perspective, change is slow because the people most invested in it want to make improvement happen in a very narrow and precise direction. McLaren, after all, is not going to bat an eye if you complain about its latest model lacking a baby seat!!!

C++, on the other hand, started sort of like NASCAR racing. It wanted to make a racing car out of a mundane, everyday car, and it got very, very good at it. Unfortunatelly, because C++ is based in an everyday car, and because it is Designed-by-Committee (TM), it shows lots and lots of "improvements" that individually kind of make sense, but in the bulk lack any coherence. Nowadays, C++ may perform like the Batmobile (from "Batman Begins" movie) on a good day; but you never know when it is going to bite you in the ass and turn into the Homermobile from the 90's Simpson's TV show.

It is a mix of necessity and lack of insight that many of the people in my generation had to learn how to drive in fucking racing carts!!! But when it's all said and done it gives you a little perspective on how things work and helps you appreciate the differences.

Re:Efficient string copying and concatenation in C by mehrdadn on Thursday September 12, 2019 @12:41PM (#20953524)
Sounds an awful lot like C should just become C++ already...
Re:Efficient string copying and concatenation in C by antirez on Thursday September 12, 2019 @12:42PM (#20953538)
No need, C dynamic string libraries totally look like plain C.
Re:Efficient string copying and concatenation in C by doboyy on Friday September 13, 2019 @10:21PM (#20968522)
No doubt, but they are all non standard which is irritating for people who expect that out of the box.
Re:Efficient string copying and concatenation in C by doboyy on Friday September 13, 2019 @10:14PM (#20968496)
This is bait but whatever. Keeping some properties of C is very hard if you go this route. It also seems you'll end up playing lanaguage design whack-a-mole problems which manifests its self in C++ and co.
Re:Efficient string copying and concatenation in C by astrobe_ on Thursday September 12, 2019 @01:46PM (#20954236)
What they really want is to find a way to convince their boss to rewrite everything in Go.
Re:Efficient string copying and concatenation in C by flohofwoe on Thursday September 12, 2019 @12:54PM (#20953668)
std::string has its own share of problems, but at least it's useful for C programmers as a warning on how not to implement a string library (for instance: a string shouldn't be important enough to give it its own allocation, it shouldn't be mutable by default, there should be string manipulation functions which are actually useful in real world situations instead of being an academic exercise, and so on...).
Re:Efficient string copying and concatenation in C by saagarjha on Thursday September 12, 2019 @01:22PM (#20953985)
I’m not sure I understand your first and third complaints and the second one is why const exists.
Re:Efficient string copying and concatenation in C by emmelaich on Friday September 13, 2019 @01:41AM (#20959484)
> length alongside with the (binary safe) string itself,

What is the type of the length?

What is the type of the length+string?

What lengths is it limited to?

Do we need a 32 bit and 64 bit version? And 128+ bit version?

Can you provide an implementation? What is its best and worst case efficiency?

What is its expected efficiency for the typical string operations?

Re:Efficient string copying and concatenation in C by amelius on Thursday September 12, 2019 @06:36PM (#20957199)
One problem is that POSIX uses null-terminated strings everywhere.
Re:Efficient string copying and concatenation in C by colejohnson66 on Thursday September 12, 2019 @09:32PM (#20958309)
So can’t you bill terminate your length prefixed string and pass a pointer to the data to POSIX. From what I understand, that’s how C++’s std::string works with ::c_str()
Re:Efficient string copying and concatenation in C by saagarjha on Friday September 13, 2019 @12:29AM (#20959178)
Starting from C++11, yes.
Re:Efficient string copying and concatenation in C by kazinator on Friday September 13, 2019 @01:51PM (#20964504)
> null terminated strings are a joke

I think that the null-terminated representation of the raw string data is a fantastic design; the best of all conceivable alternatives.