Output a String from a Subroutine

[Little Richie]

Alright guys, round two!
First, thanks again for all the help on the int to ASCII problem.

I'm now having an issue returning a string (that string actually) from a function. I know it can be done with malloc, but something tells me there is a better, or more direct, way. If there really isn't another way to do it, that would be good to know also.

[Thesh]

What are you trying to accomplish by avoiding malloc? I'm assuming this is C. If you are going to return an arbitrary length string, then the function that generates the string has to allocate the memory for it. If you don't want to allocate memory, the caller has to pass a pointer to a pre-allocated block of memory and the length of that block of memory.

[Little Richie]

What are you trying to accomplish by avoiding malloc?

It's not that I am trying to avoid malloc, I just want to know if there are other, or even better, ways to do it. My point here (and in all of the coding threads I have been or will be a part of) isn't to "make it work" but to understand a bunch of ways to do the same thing, and get different opinions on the best way in certain situations.

[Jplus]

Well you could also allocate the memory with calloc or a nonstandard allocator, but I guess that's not really "different". In the end you're always going to allocate memory. The only real variation I can think of is to let your procedure take an additional char* as an argument, assume that a large enough buffer has already been allocated to that pointer by the calling environment and write to that instead. But that wouldn't be a good idea.

If you were programming in C++ you could return a std::string instead (which would be the preferred solution). That would still involve allocation behind the curtains, but you wouldn't be the one to fuss about it anymore. Of course since your mentor seems to have the opinion that you should learn the bare bones first, this isn't an option in your case.

[PM 2Ring]

The only real variation I can think of is to let your procedure take an additional char* as an argument, assume that a large enough buffer has already been allocated to that pointer by the calling environment and write to that instead. But that wouldn't be a good idea.

In general, it's not a good idea, unless you can guarantee that the buffer is big enough, which is why Thesh suggested that the buffer length should also be passed to the routine that fills the buffer. But in this case, where we're just converting an unsigned long int to a string, we don't need to be that paranoid. IMHO.

Getting the routine to do its own allocating makes it less efficient but more useful. If it's going to be used in a simple loop where we convert one integer at a time and print the resulting string (or write it to a file), then the simplest strategy is to get it to use a pre-allocated buffer or an array on the caller's stack; it's wasteful to malloc a fresh buffer each time through the loop. But if we want to convert a bunch of ints & manipulate the resulting strings (eg sort them in various ways), then it might be handy to have the converting routine malloc those strings for us. OTOH, if we know how many strings in total we're going to need in advance I'd be tempted to malloc one big block to write all the strings to, although I admit that approach is a little more complicated, since you have to keep track of what you're doing to prevent buffer over-run.

Edit:
Another option is for the converting routine to maintain its own static buffer. That strategy is almost universally despised, but I figured I ought to mention it.

[Yakk]

A pretty standard pattern is a function that takes a pointer to a buffer and a size of the buffer, and it returns how many bytes it wants to use/did use.

You'd use it like this:

Code: Select all

size_t get_string( char* buf, size_t buf_size );

char stack_buf[1024];
char* answer = 0;
char* allocated_buf = 0;

size_t wanted = get_string( stack_buf, sizeof(stack_buf)/sizeof(stack_buf[0])) );
if (wanted > sizeof(stack_buf)/sizeof(stack_buf[0])) )
{
  allocated_buf = malloc( wanted );
  size_t wanted2 = get_string( allocated_buf, wanted );
  Assert(wanted2 == wanted);
  answer = allocated_buf;
} else {
  answer = stack_buf;
}


where we have a fixed-sized "stack" or "automatic" buffer that is used if large enough, and otherwise we malloc memory.

There are a few reasons to go through hoops like this instead of just returning a malloc'd memory buffer. Among them is the possibility that we might not be using the same heap, and the possibility that our caller would prefer to not have to worry about malloc if they don't have to.

Other approaches might include passing in an allocator or reallocator to the function that is producing the string:

Code: Select all

typedef char*(*string_reallocator)(void*, char*, size_t);
char* get_buff( string_reallocator realloc, void* );

char* my_simple_realloc( void* unused, char* old, size_t new_size )
{
  return realloc( old, new_size )
}


where you could have a version that uses a stack buffer so long as it is big enough, then switches over to using a heap buffer. This might be marginally more efficient.

...

In C++, you'd return a class that handles its own memory. Or you'd have a class passed in by reference, and fill it.

[Little Richie]

Well, I wrote up the code and sent it off to my mentor.
He says that although it works, and that malloc is an OK way to do it, it's not a great way to do it.

He goes on to say:
----
There are better ways. I can't ever recall in my 40+ years of programming ever using malloc a single time. IMHO it is never a good idea. That said, there are applications when it is a good way to go, but I've never worked on such systems. Most people don't, these are very specialized applications... So, if you're ever thinking of using malloc, ask yourself if there isn't a better way... Most of the time (and by most I mean 99.999% of the time) there are better ways than using malloc. In the rare event malloc is a good idea, the way it should be used is not the way most folks use it.

So, back to our problem at hand... There are a few ways to solve the problem. But first let's examine what we shouldn't do and why...
One way to do it is like this:

Code: Select all

  char * function( unsigned int )
  {
     char string[15] = 0;
     char * pointer = string;
     do some work, placing result in string[]...
     return( pointer );
  }

Can you tell me:
1. Is this a good way to do it?
2. Explain your answer to #1.
----

At this point, I have no idea. How else can I solve this problem?

[korona]

If your mentor never used malloc he never had to code a serious program. End of story. Any program that manages a variable amount of objects has to use malloc.
The code you posted has undefined behavior as the memory pointed to by the variable "string" belongs to your function and is not valid anymore after your function returns. That is definitely not the way to do it and it doesn't work.

EDIT: You want an arbitrary sized chunk of memory. malloc gives you just that. Local variables are stored on the stack and are only valid during the execution of the function they belong to. The only other option would be to use a global accessible chunk of memory but that is a really bad option as 1.) it would still have a fixed size 2.) that would be a very bad design because you'd need a global variable just for the return value of a function.

Dynamically allocating memory was considered slow 25 years ago but memory allocators have become better in the mean time and there is no reason to avoid malloc unless it is in a very tight loop that is run thousands of times per second.

[EvanED]

If your mentor never used malloc he never had to code a serious program. End of story. Any program that manages a variable amount of objects has to use malloc.
The code you posted has undefined behavior as the memory pointed to by the variable "string" belongs to your function and is not valid anymore after your function returns.

Now now, it only has undefined behavior if he dereferences from the pointer that gets returned.

I say that only to emphasize the point that korona is right: that won't work.

There are essentially three ways to do this.

The first is with malloc:

Code: Select all

char * int_to_string(int n) {
    int number_of_characters_needed = 1 + snprintf(NULL, 0, "%d", n);
    char * buf = malloc(number_of_characters_needed);
    sprintf(buf, "%d", n);
    return buf;
}

The second is by having the caller pass a string and writing to that:

Code: Select all

int int_to_string(int n, char * out, size_t size) {
    return 1 + snprintf(out, size, "%d", n);
}

Both of these are perfectly fine. I prefer the latter (except for the "need" to write a not-retarded version of the standard strncpy function) because of the heap issues other people have mentioned, but that's a relatively weak reason. The latter does pretty much mandate a more complicated API, because in many cases (e.g. int_to_string) in order to be correct you have to pass the size of the buffer into the function, which adds a parameter, and then the caller needs some way of knowing what size they should allocate, which means you need that extra return value behavior. That just pushes the logic that's in the first version (mallocing) into the caller. So the result is more flexible but also more complicated.

The third possibility is to use a function-static buffer:

Code: Select all

char* int_to_string(int n) {
    static char buffer[20] = {'\0'};
    snprintf(buffer, 20, "%d", n);
    return buffer;
}

This looks a lot like yours, but notice the static in there. That causes that variable to stick around between calls. (It's like a global, except that there's no way to name it so you can't access it from outside of say_cheese except via its return value.)

This way sucks. Don't do it. The problem is if the value may change between calls, then it will change for everyone:

Code: Select all

char * one = int_to_string(1);
char * two = int_to_string(2);
printf("%s = %d!\n", one, 1);

This is the sort of "spooky action at a distance" that makes globals a bad idea, and it also means that you basically can't use that function in a concurrent program. This way also caps the length. For instance, that version of int_to_string won't work correctly if the conversion needs more than 20 characters. And I don't know of any way in C to get around that problem.

[PM 2Ring]

If your mentor never used malloc he never had to code a serious program. End of story. Any program that manages a variable amount of objects has to use malloc.

Agreed. I seriously suggest that Little Richie should start looking for a better mentor. I doubt anyone here would like to work with a C programmer who doesn't believe in using malloc.

The code you posted has undefined behavior as the memory pointed to by the variable "string" belongs to your function and is not valid anymore after your function returns. That is definitely not the way to do it and it doesn't work.

I suspect that the posted code is an example of how not to do it, and it's Little Richie's task to explain why it's bad.

I'm a bit puzzled about the use of the variable named "pointer". Why not just return "string", since it will get converted into a pointer to the first element? Assuming, of course, that we make the storage class of "string" static.

I don't understand the point of calculating the string length in this particular application. We know the maximum string length, since we're just converting an unsigned int to string. The code required to determine the actual string length wastes more bytes than it saves, and also wastes time.

Here's the link to the original thread:
Unsigned int to ascii in C

[phlip]

I don't understand the point of calculating the string length in this particular application. We know the maximum string length, since we're just converting an unsigned int to string. The code required to determine the actual string length wastes more bytes than it saves, and also wastes time.

Perhaps in this case... but we're trying to answer the general question of returning strings from functions in C, as a learning thing. Obviously in the specific case where the maximum potential length of the string is known in advance, there are some simplifications you can make...

Also, re the instructor's "avoid malloc" comments: it might be worth double-checking whether they meant "avoid dynamic allocation" (which is terminally dumb, and a sign you should find a new mentor), or just "avoid calling malloc directly, use some kind of pre-built wrapper" (which is still kinda dumb, but not quite so extreme)...
I had a heated discussion with someone once, who was claiming that you should never use "delete" in C++... I thought they meant that you should never free anything, but it turned out they meant you should always use smart-pointers, and only ever call "delete" directly if you're in the process of making a smart-pointer class (and even then you should check whether you're reinventing the wheel). I've also seen wrappers around "new" which directly return a smart-pointer, and recommendations to always use those, and not "new" directly. Of course, such a stance makes slightly more sense in C++, which has things like smart pointers, as opposed to C, which doesn't.

[EvanED]

I don't understand the point of calculating the string length in this particular application. We know the maximum string length, since we're just converting an unsigned int to string.

No you don't.

Otherwise you wind up with code that assumes that an int is 16 bytes and 5 digits is sufficient, and then causes segfaults and security vulnerabilities when compiled with today's compilers. Or you assume that an int is 32-bits and 10 digits is sufficient, and then causes segfaults and security vulnerabilities when compiled on a system that uses an ILP64 model, like Crays.

How many digits is sufficient for a 64-bit int? Do you know off the top of your head? I don't.

And the 16-to-32-bit transition and ILP64 are both things that have actually happened; that's not even getting into the fact that you could theoretically have a 128-bit int or a 2048-bit int by the standard.

[phlip]

Code: Select all

char buffer[(sizeof(int)*CHAR_BIT+2)/3+2]; // sufficient to hold any int value, including sign and null terminator

This will overestimate slightly (due to rounding down log₂(10) to 3, and also by supposing that all the sizeof(int)*CHAR_BIT bits are value-bits, and yet also allowing for a sign-bit), but it will always be big enough, for whatever integer type you specify.

[edit] Though, for clarity, I'm in no way suggesting that doing this is a good idea...

[EvanED]

Nice... seems like you could even be able to make the bound tighter by putting in a floating point and casting at the end.

I gave a small amount of thought to how you would determine that statically when I was typing the original post, and the only thing that came to mind was C++ metaprogramming.

Of course, now that I think about it more, for the case where you just malloc() up some memory to write to, you could even compute it dynamically and get a tight bound. So I guess I was overthinking things a little.

[PM 2Ring]

I don't understand the point of calculating the string length in this particular application. We know the maximum string length, since we're just converting an unsigned int to string.

No you don't.

Otherwise you wind up with code that assumes that an int is 16 bytes and 5 digits is sufficient, and then causes segfaults and security vulnerabilities when compiled with today's compilers. Or you assume that an int is 32-bits and 10 digits is sufficient, and then causes segfaults and security vulnerabilities when compiled on a system that uses an ILP64 model, like Crays.

How many digits is sufficient for a 64-bit int? Do you know off the top of your head? I don't.

And those environments are both things that have actually happened; that's not even getting into the fact that you could theoretically have a 128-bit int or a 2048-bit int by the standard.

Fair point. But why not handle that sort of thing with a bunch of #if stuff? At least, the common cases can be handled automatically, and really weird cases can chuck a compile-time error. It seems more efficient to me to test stuff like that at compile time rather than at run time. Even if (for example) you have a 64 bit environment that will happily run an executable that was compiled to run in 32 bit environment, the 32 bit exe will only "see " the int size it was compiled for. Won't it?

(FWIW, back in the days of Fidonet I used to do that sort of thing all the time, since I used an Amiga, and there was a lot of C code going around that was written specifically for 16 bit MS-DOS. If I was lucky, other people would've fixed the original 16 bit code to work properly on 32 bit Windows, but even then I'd often have to fix stuff that wouldn't work properly on big-endian machines. And don't get me started on non-flat memory models. )


EDIT:

[edit] Though, for clarity, I'm in no way suggesting that doing this is a good idea...

Why not, phlip?

[EvanED]

Fair point. But why not handle that sort of thing with a bunch of #if stuff? At least, the common cases can be handled automatically, and really weird cases can chuck a compile-time error.

If it threw a compile-time error that would be acceptable to me, but I don't think it can be completely general. In particular, you wouldn't be able to handle systems where the int type you're interested in converting is larger than the minimum size mandated by the standard for long long. (Or, if you want strict C89, larger than the minimum size mandated by the standard for long. That rules out working on ILP64 systems.)

So if you were on a system with 128-bit long longs and wanted to write long_long_to_string you wouldn't be able to do it using that.

Even if (for example) you have a 64 bit environment that will happily run an executable that was compiled to run in 32 bit environment, the 32 bit exe will only "see " the int size it was compiled for. Won't it?

Yes, that's correct.

(Theoretically I guess you could see an architecture shift where the registers are increased in size but keep the same name (unlike x86's evolution). That could screw with things.)

Edit: One more point... I would strongly argue that only the first version would need to be revised, even in my example. That one you could change to not call snprintf twice, which would actually be a win, and instead use the incantation that phlip posted to get the number of characters needed. However, for the others -- and in particular, for the second -- I strongly feel that you should continue to use snprintf in the absence of very very concrete evidence that changing it will help -- and even then, the size should still be passed. Even if you want to say that the caller of int_to_string should always allocate the right amount, adding the explicit size parameter allows you to assert that fact. E.g.

Code: Select all

void int_to_string(int n, char * out, int size) {
    int needed = 1 + snprintf(size, out, "%d", n);
    assert(size >= needed);
}

or even

Code: Select all

void int_to_string(int n, char * out, int size) {
    int needed = 1 + sprintf(out, "%d", n);
    assert(size >= needed);
}

if you're really cavalier. Otherwise, there's nowhere you can add that assertion: int_to_string can't know the size unless its told, and the caller can't know what gets written to it. (What if int_to_string is buggy and writes too much?)

I very strongly feel that arrays and their sizes should always be available together so that you can add checks like that.

[csanders]

You could also do something like:

Code: Select all

typedef struct {
    char string [20];
} string_return_type;

string_return_type int_to_string (int i)
{
    string_return_type r;
    sprintf (r.string, "%d", i);
    return r;
}

Stuffing it into a struct can get a fixed size string copied back to the caller's stack without any malloc. (Of course, replace that size of 20 with whatever more correct formula there is for maximum string lengths.)

[Sc4Freak]

You could also do something like:

Code: Select all

typedef struct {
    char string [20];
} string_return_type;

string_return_type int_to_string (int i)
{
    string_return_type r;
    sprintf (r.string, "%d", i);
    return r;
}

Stuffing it into a struct can get a fixed size string copied back to the caller's stack without any malloc. (Of course, replace that size of 20 with whatever more correct formula there is for maximum string lengths.)

Otherwise known as the C Programmer's Disease.

[PM 2Ring]

Otherwise known as the C Programmer's Disease.

Wrapping an array in a struct merely so that you can return it is not really in the spirit of C, IMHO. But if you really want to do that sort of thing to return a string you might as well add an extra field to the struct to return the string length, with a string length of zero acting as a defacto error code. I guess you could use negative string lengths for additional error codes, if you were that way inclined.

[csanders]

Oh, I certainly don't think that's the right way to return a string. If it were my code, I'd just use malloc and return a pointer. However, the original question was asking how to do it without a malloc.

I think after the instructor's suggestion to avoid malloc that it's time to find a new instructor. It's like learning from a carpenter who tells you never to use a screwdriver. "I've built plenty of houses with just a hammer, that's all you should need." Memory allocation is a very important tool in the toolbox, and one you need to learn how to use.

[Little Richie]

I think after the instructor's suggestion to avoid malloc that it's time to find a new instructor. It's like learning from a carpenter who tells you never to use a screwdriver. "I've built plenty of houses with just a hammer, that's all you should need." Memory allocation is a very important tool in the toolbox, and one you need to learn how to use.

I talked to him about your concerns and his explanation was quite simple, and I think worth the read.

"

Here is the issue... It is a matter of real-world programming vs. theoretical-world programming.
In the real-world of programming, the vast majority of the time the programmer knows IN-ADVANCE what the constraints of the problem are.

In the theoretical-world of programming, the programmer knows nothing about the environment they are working in.

Simply because things are possible in programming, doesn't mean it is a good thing to do, especially when efficiency is an issue. By efficiency here I mean things like execution speed and memory space. One might argue that with today's huge memories, space isn't really much of a consideration, but that's the way the world was back in the 1950s when littering wasn't considered a bad thing. I can recall my mother telling me to simply throw garbage out of the car window when we were on a trip. No one cared, there was plenty of space out there and how much space does a candy wrapper or a piece of kleenex take up? Well, when everyone does it and when there are a bunch of people it does matter. So, in my world, if all programmers do their best, it is a better world to live in.

So, back to the problem at hand. It is a very rare problem where the programmer doesn't know in advance the scope (size) of the problem. So, in your example, how often is it really a possibility that the string needs to grow infinitely? And, think about the cost associated with using a device like malloc in such a situation. If the goal is to be able to store the most possible data does malloc make sense? No. Why? Because there is a heavy memory overhead associated with malloc, especially when the size of the items being allocated are small.

Now, because no machine is infinite, no data structure can grow infinitely. Because 99.9999% of the time, the programmer knows in advance what the largest amount of data will be, he can simply plan for that ahead of time and deal with the program at design time as opposed to run-time.

C++ has many inherent issues with efficiency (which is why I avoid it). The theory of such programming languages is that they make things "simpler" for the programmer by disconnecting him from the real-world by generalizing things (or abstracting things) to the point where he no longer knows what is going on inside the computer. There are heavy penalties associated with these generalizations. As a result, applications today are huge lumbering things that respond slowly and consume huge computer resources. How many times have you pressed a button or clicked on an icon and nothing has happened? Do you simply wait a while to see if something is going to happen? Do you click pr press again? Did the computer "see" the event? Is the button broken?

I grew up in a world where when you pressed a button something happened NOW. The only delays were the speed of electricity in a wire. And in mechanical systems where things don't move that quickly we would get immediate feedback that something was happening because there was a sound associated with the button press.

I guess today folks simply are used to having their requests delayed or ignored. I am of the belief that humans are in charge and the machines are our slaves and they should respond to us (not vise-a-versa).

So, good, efficient programming is a desirable thing. Abstraction leads to inefficiency by it's very nature. I know that you know about hardware electronics, what if people built hardware the way people built software? How would that be? The hardware engineer needs to know in advance how much voltage and current will need to pass through a resistor at the time he is designing his circuit. If you think of a resistor as a function, in today's "abstract" world the resistor would have to be designed in advance to handle whatever was thrown at it. This would mean that all resistors would need to be as big as possible, or worse yet, they would need to allocate some resistive material at the time they ware called upon to do their work. I know this is an absurd example, but just because it is possible to generalize things is software doesn't mean it should be done.

Of course, programming in the way I propose looks like it would take longer, it really doesn't. ALso, if you think about the amount of real-time you'll save for your users and multiply that out, doesn't it make sense to have the programmer spend a bit of extra time up front to make things simpler and faster for the public each and every time they run the application?

If I were given the task to create a data structure that required me to to "insert a node", I would ask many questions before I wrote a single line of code. Things like:

1. Exactly how is this going to be used.
2. What is the maximum number of nodes I'll ever see?
3. What is the size of each node?
4. What is the most important consideration?
a. Speed of execution?
b. Speed of programming?
c. Memory utilization?
d. Program maintainability.
e. Other?

Let's say you were working on a huge system where you were told to implement this insert_inorder function. Now let's say there are hundreds of programmers that have called your routine. Now, let's say that on one of the cases, speed is very important, and in all of the other cases, no one cares. Now let's say there are thousands of places in the code where your function is called and you are faces with speeding this thing up. Where do you begin? You could try to optimize the routine but experience tells us that the best way to optimize anything is to KNOW as much in advance as possible. How do you solve such a problem.

On the other hand, if a special purpose routine were implemented for this specific situation, with advanced knowledge as to how it was to be used, and the stresses that would be placed upon it, all of the trade-offs could be done at the time it was written and this crisis I mentioned above most likely would never take place.

I could go on and on, but hopefully you get my point. I don't want to live in a world where every resistor is protected by a fuse because hardware engineers stop designing things up-front. Of course, in that world wouldn't you want to have a circuit-breaker in there to protect the fuse? Where does it end?

I'm interested to know what you think about all of this. Personally, it makes sense to me, even if malloc's overhead is less now than it was in the past.
I also take what he says with the knowledge that he is from a different time, and spends most of his time thinking about low level code. Personally, I will most likely end up using malloc, but having the root knowledge of how to do something is always useful. Logic and principals are what I am trying to learn from him, not necessarily his philosophy on the code itself. He asks me questions and gives me problems to solve, I look for all the ways to do them, and learn all of them, I take into account what he prefers, but it's the overall idea I am looking for.


Edit: Remove Old Edit.

[PM 2Ring]

I agree with the principle of not using malloc when it's not necessary, and as I mentioned earlier in this thread it's not necessary in this particular application where we know the maximum string length at compile time. But there are plenty of real-world cases where we can only know a program's memory requirements at run-time. One common example is image processing. In some cases, image transformations can be performed one pixel at a time or one row at a time, but it is often necessary to read a whole image into memory in order to process it, or at least to process it efficiently. Considering the possible range of sizes that images come in, it would be extremely wasteful to use a fixed size array that's large enough to deal with the biggest possible image that the program could be used on.

FWIW, I started learning C in 1980. The first machine I used C on had 64 kilobytes of RAM. By that stage, I was a competent programmer in BASIC, PL/I, IBM 360 assembler and FORTRAN. The machines I used back then didn't have a lot of RAM; the IBM mainframe that I ran PL/I and assembler on had 64k of core storage, implemented with actual ferromagnetic cores. So I know how to be frugal with memory. But I also know how to utilize the memory endowments of modern environments when it's appropriate to do so, and dynamically allocating memory for things like trees, or hash tables of cached results from calculations, can often lead to much faster performance than a memory-miser approach.

[Jplus]

I would like to highlight some parts of your mentor's "explanation".

Here is the issue... It is a matter of real-world programming vs. theoretical-world programming.
In the real-world of programming, the vast majority of the time the programmer knows IN-ADVANCE what the constraints of the problem are.

In the theoretical-world of programming, the programmer knows nothing about the environment they are working in.

[...]

Basically he's saying in a long-winded way that (1) you want your code to be as general as possible and (2) general code should pose as few requirements on the execution environment as possible, so (3) your code should be efficient. I fullheartedly agree to that and besides, efficiency is a virtue in itself.

[...] If the goal is to be able to store the most possible data does malloc make sense? No. Why? Because there is a heavy memory overhead associated with malloc, especially when the size of the items being allocated are small.

This seems rather misleading though. What does he mean by "heavy memory overhead"? You should know that processes in modern operating systems are granted some number of memory pages that they can use, and that they can ask for more memory pages when they run out of space. Modern allocators are optimized to squeeze as much as they can out of the memory pages that are already available to your program before asking for more. Of course the allocators have to store some additional data to keep track of what is in use and what isn't, but you wouldn't have to be afraid that they'd double the amount of memory required or anything. For really small items you can use special purpose allocators that pool the items into arrays, if necessary.

Now, this is not to say there are no problems with memory allocations. For one, memory allocation may add heavy time overhead. Context switches are required to add more pages, which can take a lot of time by itself, and if your memory gets severely fragmented allocators may have to do a lot of searching in order to find a gap of the right size. Another problem is that the responsibility to manage the allocated memory is on the programmer (if not wrapped in some kind of convenient handle like a C++ std::string), which turns out to be something that humans are not really good at.

So you may want to avoid free store allocation because of time efficiency, but not because of space efficiency (see below). The management pitfalls are a good reason to avoid manual allocation, but since you should especially work on your weaknesses, it's a good idea to exercise such responsibilities before you walk into them while doing serious, real-world work.

Now, because no machine is infinite, no data structure can grow infinitely. Because 99.9999% of the time, the programmer knows in advance what the largest amount of data will be, he can simply plan for that ahead of time and deal with the program at design time as opposed to run-time.

This is wrong, and I can tell you why with a simple counterexample: the phpBB post form. Forum members may post message anywhere from a single character (see Random bitstream!) to lengthy works like this one. Of course, you can arbitrarily assume that users will never post a message of more than 20k characters (this post is 10234 characters). So your mentor is suggesting to determine that size at design time and use a fixed size array.

Obviously, that means you'll be wasting a lot of space most of the time! Not to mention the problem that will occur when somebody, some day, posts a message of slightly more characters than the assumed upper limit. It's a tradeoff without acceptable compromise: the safer your upper limit, the more space you'll waste, and the less space you waste, the more often posts will get truncated or even cause your program to segfault or be exploited by buffer overflow attacks (depending on how well you're aware of your own mistake).

There is only one right way to deal with such dynamic requirements: determine the space needed at runtime and allocate on the free store appropriately. Ironically, that's both the safest and the most space-efficient way to go about it.

C++ has many inherent issues with efficiency (which is why I avoid it). The theory of such programming languages is that they make things "simpler" for the programmer by disconnecting him from the real-world by generalizing things (or abstracting things) to the point where he no longer knows what is going on inside the computer. [...]

Your mentor obviously knows very little about C++ -- or about C, for that matter. High-level languages with modern, advanced compilers or interpreters, which definitely includes C, never reliably reflect what's going on in your machine. The only way to find that out is to inspect the assembly code that the compiler generates. One compiler may generate vastly different assembly from another, and of course different machine architectures require different assembly code. That's the entire point of all high-level languages: you're abstracting away from your machine so you can write portable code.

Now, some high-level languages allow you to delve more into technical details than others, but that's still in a way that abstracts away from the machine's internal mechanics. And for what it's worth, C++ is pretty much equivalent to C in this respect. All basic operations in C++ have exactly the same efficiency profile as in C, including manual allocation (C++'s operator new and C's malloc are usually implemented with the same allocator). The main difference is that C++ offers more techniques to improve the modularity of your code, especially classes and templates. While those additions make the language more complex and therefore add compile-time overhead, they have no adverse effect on the run-time efficiency at all (in fact, it turns out that templates sometimes benefit efficiency).

Now it's true that many things are easy to do in C++ while you'd often avoid them in C because it would be too involved. Often they're implemented and ready to use, such as dynamic binding and linked lists. But you don't have to use them (I almost never use either of those myself), and if you do use them they take no more overhead than if you'd implement the equivalent in C. Rather, the convenient, well-crafted and utterly optimized implementations that are offered in C++ will generally be more efficient and safer than anything you could build yourself under realistic time constraints, whether you do it in C or C++. The most obvious example is the std::vector.

If you're still not convinced, have a look at these two comparisons at the Computer Language Benchmarks Game.

[...]

[...] Abstraction leads to inefficiency by it's very nature. [...]

This is only marginally true. Statically typed, compiled, GC-free languages such as C, C++, Fortran and ATS produce very efficient assembly code. Only if you're highly skilled at assembly programming and you're thorougly knowledgeable about the target architecture you'll be able to improve such code, and even then the speedup will be insignificant most of the time.

Of course, programming in the way I propose looks like it would take longer, it really doesn't.

It does, and very much so: it causes you to avoid all kind of existing, very useful tools and you'll have to reinvent the wheel many times. You can do it as an exercise once in a while, but don't waste too much time on it, especially since it doesn't train you to do anything useful.

ALso, if you think about the amount of real-time you'll save for your users and multiply that out, [...]

Such practices will only cost your users, both because it takes you longer to release your software and because you write sub-optimal solutions.

If I were given the task to create a data structure that required me to to "insert a node", [...]

In real-world situations you shouldn't be given such a task, because such datastructures are already available. And if you ever, ever find a need to implement some new kind of datastructure, please do it in C++ so you can just wrap your class in a template and never need to duplicate your code or use ugly preprocessor trickses to make it work for new value types.

Let's say you were working on a huge system where you were told to implement this insert_inorder function. Now let's say there are hundreds of programmers that have called your routine. Now, let's say that on one of the cases, speed is very important, and in all of the other cases, no one cares. Now let's say there are thousands of places in the code where your function is called and you are faces with speeding this thing up. Where do you begin? You could try to optimize the routine but experience tells us that the best way to optimize anything is to KNOW as much in advance as possible. How do you solve such a problem.

On the other hand, if a special purpose routine were implemented for this specific situation, with advanced knowledge as to how it was to be used, and the stresses that would be placed upon it, all of the trade-offs could be done at the time it was written and this crisis I mentioned above most likely would never take place.

Here your mentor seems to be contradicting himself. Does he want you to write code that is as general as possible, so it will be efficient enough in all situations for which it is intended, or does he want you to write new code every time your old code turns out not to be efficient enough? Curious.

To summarize, I'm afraid you should take your mentor with several grains of salt. If you like his puzzles you can stick with him for the time being, but be aware that lots of other interesting and insightful puzzles are available on the interwebs.

[gametaku]

[...] If the goal is to be able to store the most possible data does malloc make sense? No. Why? Because there is a heavy memory overhead associated with malloc, especially when the size of the items being allocated are small.

This seems rather misleading though. What does he mean by "heavy memory overhead"? You should know that processes in modern operating systems are granted some number of memory pages that they can use, and that they can ask for more memory pages when they run out of space. Modern allocators are optimized to squeeze as much as they can out of the memory pages that are already available to your program before asking for more. Of course the allocators have to store some additional data to keep track of what is in use and what isn't, but you wouldn't have to be afraid that they'd double the amount of memory required or anything. For really small items you can use special purpose allocators that pool the items into arrays, if necessary.

Now, this is not to say there are no problems with memory allocations. For one, memory allocation may add heavy time overhead. Context switches are required to add more pages, which can take a lot of time by itself, and if your memory gets severely fragmented allocators may have to do a lot of searching in order to find a gap of the right size. Another problem is that the responsibility to manage the allocated memory is on the programmer (if not wrapped in some kind of convenient handle like a C++ std::string), which turns out to be something that humans are not really good at.


So you may want to avoid free store allocation because of time efficiency, but not because of space efficiency (see below). The management pitfalls are a good reason to avoid manual allocation, but since you should especially work on your weaknesses, it's a good idea to exercise such responsibilities before you walk into them while doing serious, real-world work.

Which is why in C++ you should use std::unique_ptr and std::shared_ptr, and minimizing the scope of variables to what's required by the program.

C++ has many inherent issues with efficiency (which is why I avoid it). The theory of such programming languages is that they make things "simpler" for the programmer by disconnecting him from the real-world by generalizing things (or abstracting things) to the point where he no longer knows what is going on inside the computer. [...]

Your mentor obviously knows very little about C++ -- or about C, for that matter. High-level languages with modern, advanced compilers or interpreters, which definitely includes C, never reliably reflect what's going on in your machine. The only way to find that out is to inspect the assembly code that the compiler generates. One compiler may generate vastly different assembly from another, and of course different machine architectures require different assembly code. That's the entire point of all high-level languages: you're abstracting away from your machine so you can write portable code.

Technically not even inspecting the assembly that is generated, or manual coded will reliably reflect what's going on in the machine as instructions can be executed out of order, executed simultaneously using instruction pipelines, and there are other trickses.

[Yakk]

Your teacher possibly needs to read this:
http://www.computer.org/cms/Computer.or ... ucture.pdf

Basically, C++ doesn't take away the ability to write ridiculously efficient code. It makes it easier. It also makes it easier to write inefficient code.

But the fact that the standard quicksort that ships with C is about 2.5x slower than the standard quicksort that ships with C++, and the C++ version is safer and less bug prone, is an example of why throwing away C++ is a bad idea.

In addition, there are reasons to write inefficient code -- it is often programmer-time efficient, and there are more software development tasks than programmers to do them in general.

As an aside, I spent a few months designing hardware. You don't specify the location and specifications of transistors, you let the compiler handle that. There are far too many gates to hand craft the specifications of each one.

If you are working on throw-away code -- code that won't be reused 5-20 years down the line -- or on toy problems, or in embedded systems, or in a situation where you have discovered a performance bottleneck, his approach makes sense. But most development isn't in those situations. And it isn't as if the C era of coding was a paradise -- buffer overflows, possibly the most common security error out there, where rife (and remain rife when you write code in a C style).

[korona]

You usually do not know the size of your data structures in advance. Actually I cannot imagine any many non-trivial applications that do not have to malloc.
The web browser you're using to view the page probably does a dynamic memory allocation on every html tag it parses, on every javascript command that is parsed and on every mouse move event it processes.
Your operating system kernel does a malloc each time a file is opened, each time a pipe is created, a socket is created or a thread or process is started. How can all this information be known in advance?

I'm currently working on a high performance program. Yesterday I replaced a dynamically allocated buffer that was reallocated a few hundred thousand times per second by a pre-allocated one (still allocated by malloc and not statically allocated as the size varies from 5000 to 9 million entries depending on the problem instance). It gave me a speedup of 2% (not of the whole program, just of that procedure). Modern memory allocators are fast. Sure you should not allocate thousands of 1 byte buffers but as long as you do not call malloc in a loop that gets executed millions of times per second it does not make a difference.

EDIT: I think I don't have to empathize that allocating 8 GB because my problem instances vary from 100 kb to 8 GB is stupid. Not to mention that the people running the program would complain that the program consumes that much memory. In many cases we're not even allowed to use 8 GB per instance as there other instances solved in parallel on the same computing node.

For many problems malloc actually helps to save memory as you do not over-allocate any buffers when you know their exact size.

Btw. it is actually hard to beat gcc by using assembler (unless you're doing something special, e.g. SSE programming). As the complexity of processors increases it gets harder to write optimal code for them by hand. In modern processors the execution speed of instructions depends strongly on the their order. Executing integer and floating point instructions alternatively is faster than doing that sequentially as they will be executed in parallel.

[Little Richie]

Overall, it seems that you all agree with his general ideas, but don't like how extreme he is about them.

[...]or in embedded systems, or in a situation where you have discovered a performance bottleneck, his approach makes sense.

This is where a good chunk of his coding experience comes from, so his ideas make sense in context.

For many problems malloc actually helps to save memory as you do not over-allocate any buffers when you know ither exact size.

I see that, and I do understand when it could be useful.

In addition, there are reasons to write inefficient code -- it is often programmer-time efficient, and there are more software development tasks than programmers to do them in general.

Sure, there are reasons, but I don't want to learn to be inefficient. I'd rather know both ways to solve a problem, and leave it up to me when to be inefficient.

Modern allocators are optimized to squeeze as much as they can out of the memory pages that are already available to your program before asking for more. Of course the allocators have to store some additional data to keep track of what is in use and what isn't, but you wouldn't have to be afraid that they'd double the amount of memory required or anything. For really small items you can use special purpose allocators that pool the items into arrays, if necessary.

Of course. I'm not under the impression that I'm going to be wasting an enormous amount of memory or time by using malloc. I guess he believes that as long as I know what's going on, I can make the best decision when it comes to real coding. From what you all have said, even if it's marginal, it would be naive to believe that there is no hit taken when using malloc.

This is wrong, and I can tell you why with a simple counterexample: the phpBB post form.

That's a really good point.

I'd like to stress that, at this point, I see the pros and cons of both, and have a general feel for the fora's take on the issue. I really do enjoy seeing all of theses sides of the same problem, and getting multiple reasons and views on why something is "bad" or "good." Thanks!

[EvanED]

In addition, there are reasons to write inefficient code -- it is often programmer-time efficient, and there are more software development tasks than programmers to do them in general.

Sure, there are reasons, but I don't want to learn to be inefficient. I'd rather know both ways to solve a problem, and leave it up to me when to be inefficient.

You probably have the right idea, but I'd suggest flipping your viewpoint around a bit. Instead of saying "leave it up to me when to be inefficient", look at it as "leave it up to me when to put in the extra effort to be really efficient."

The reason for this is that, by the 80/20 rule of thumb (80% of the execution time is spent in 20% of the code), "when to be inefficient" really ought to be "a significant majority of the time." Once you find out where that inefficiency is hurting you, you can work on it.

It's entirely possible that you'll get faster code by doing this, because you'll be able to spend more time figuring out to do with the code that does matter instead of "wasting" effort speeding up things that aren't contributing much execution time to begin with. (cf. Amdahl's law.)

[Yakk]

A good programmer can make any program faster given time. (Rarely this can be only done by waiting for Moore's law to lift all boats). So when you use less effort to write less efficient code, you are banking programmer time. When you work out what part of your program that actually needs more speed, you now have more time to work on it. Spend effort where it does the most good. And learning how to write defensive code makes development easier. Instead of hand crafting a buffer for a problem, use a reasonably efficient automatic buffer that just works. Learning how to use that autobuffer, how to write code that just works even if code elsewhere misbehaves, not making each function perfectly crafted for just one use but flexible enough to be tested and then used elsewhere - these all make your coding faster. But they take time to learn.

[Jplus]

General point to take home: the manual buffer approach that your mentor advocates can be an optimization in some corner cases, but it can also be a total disaster (and that's more likely). Applying such a trick anywhere before you know for sure it will help you would be a classical example of premature optimization. If you plan to treat manual buffers as a "normal option" alongside dynamically allocated buffers you'll inevitably develop a bad habit. Remember the manual buffer trick only as a trick, and instead make it your default approach to use dynamically allocated buffers.

I wouldn't say I agree to your mentor's general ideas at all. I think efficiency is a good thing, but your mentor doesn't even seem to consistently advocate efficiency.

Some pointers on premature optimization.

[Thesh]

Also, keep in mind that your function call stack is limited in size (usually very limited). Excessive use of arrays on the stack can cause serious problems down the line that can only be fixed by rebuilding the application to use a larger stack size. Also, with fixed arrays, you usually have to over allocate, and if this is on the stack you can potentially see a performance hit due to less ideal usage of the processor cache. Not to say you should never allocate arrays on the stack, just avoid large arrays and excessive overallocation.

[Yakk]

Except, on 64 bit systems, there is little reason why we don't have multiple-gigabyte sized stacks. It isn't as if the virtual memory they aren't actually using has a large cost.

Stack size should only be limited (more than heap size) in the brief eras where physical memory starts approaching virtual memory sizes, and in the lagging period where lazy ass/conservative programmers are used to "small" stacks and don't want to make them larger. And "rebuilding a program to make it larger" just means you screwed up when you built it the first time.

[korona]

Well there is not really a reason to have a gigabyte sized stack. The cache thrashing caused by pushing multiple megabytes of data on the stack is more costly than using malloc. Especially when it causes the CPU to mispredict a branch.
If you really have to get the last bit of performance out of that method store the return value on a separate stack or in a pre-allocated (but dynamically allocated) buffer.

[Yakk]

Hmm? The cache treats the stack and the heap identically. Tossing multiple megabytes onto the heap will cause the cache to "trash" just as much?

Less, if you maintain locality of memory reference, because prefetches will end up helping...

[WarDaft]

If you absolutely must return variable sized strings and don't want to dynamically allocate, you can have X different fixed size string holding structs (sizes of powers of two for example) and return the string as a linked list logarithmic in the size of the string with amortized constant time access and logarithmic sized overhead.

[Yakk]

As an aside, a neat thing coming in C++0x is the existence of emplace based functions. I suspect that emplace based return will be coming in the next version of the C++ standard, where the return value isn't passed by pointer, but instead passed on the stack, directly modified by the called function, then used by the caller. Or at least permitting that optimization.

So if you do char foo[1024] = bar();, bar() ends up with a local return value that it can modify (which is foo). If you instead do this:
char foo[1024] = {0};
// foo is used here
int baz;
foo = bar();
the return value that bar modifies is instead a temporary, and the move constructor is called when it is assigned to foo[]. (With the compiler being allowed to reorder the stack so that it is actually passed to bar, but that is an option for the compiler).

It is a continuation of the increased efficiency that the move constructor provides -- emplace transfer of objects, instead of move based transfer of objects.

---

And things like the above are the kind of things that are really hard to deal with when you code in a C style, unless you go and write upteen bajillion versions of your function. Being able to move semantics into the language, and giving the compiler access to your type information, means that it can do optimizations that it could not do without that knowledge -- and these optimizations can be heavily context dependent. So instead of having 7 different versions to write and maintain, you write it once, and the compiler knows how to optimize your code for the 7 different cases.

std::sort is an example of this. Unlike the C qsort function, it keeps type information around. Instead of taking the comparison function as a function pointer, it takes it as a functor (an arbitrary C++ object, possibly including a function, that has an operator() that accepts pairs of elements from your list, and returns true or false). This makes it easy for the compiler to inline that function. The type information means that it automatically knows how to sort doubles.

And because it is a robust and central sorting algorithm, a ridiculous amount of work went into optimization: when it switches to insertion sort, how it picks the pivot, etc. So while you can custom-code a quick sort that matches the performance of std::sort, you both don't have to, and very few people have spent months working on the sorting algorithm optimizations that are baked into std::sort. qsort can have those optimizations, but it is stuck living in a land of function pointers and void*, which causes huge indirection costs, and explains the 2.5x slowdown that C's qsort has over std::sort (results will vary by implementation) sorting basic types (like integers and doubles).

[Jplus]

Yakk, you seem to be describing normal RVO. Which has become even more accessible with rvalue references in C++11, but still, it's been around for quite a while.

I totally agree about the part on C++ allowing for high efficiency tuning that is hard or totally impossible in C though. Did you, by any chance, read the little quicksort discussion that I recently had with Breakfast in the "It doesn't work" thread?

Edit: link to the start of the quicksort discussion (there is more on the next page).

[Yakk]

rvalue references doesn't do emplace return values -- it is operator move, not operator emplace construct. But ya, now that I think of it, (N)RVO is what I was talking about, and if not, close enough.

Sigh. I sort of don't like relying on the compiler to magically optimize without saying "by the way, this can be optimal". It seems overly brittle: with something like emplace insert or operator move, it happens (and if it doesn't, because it isn't possible, you get a compiler error). When you have an optimization like (N)RVO, doing something you don't realize is important might break the compilers ability to optimize it, and silently your code gets (possibly significantly) slower.

I mean, "return the value from more than one spot breaks (N)RVO" -- what shit is this?

[EvanED]

I sort of don't like relying on the compiler to magically optimize without saying "by the way, this can be optimal". It seems overly brittle: with something like emplace insert or operator move, it happens (and if it doesn't, because it isn't possible, you get a compiler error). When you have an optimization like (N)RVO, doing something you don't realize is important might break the compilers ability to optimize it, and silently your code gets (possibly significantly) slower.

For a while I've thought it would be pretty cool if you could add assertions to the code that certain optimizations are performed, e.g. that NRVO is performed at a particular point, or that a function call is actually inlined, etc.

What I have no clue about though is how to actually make this usable.

[Jplus]

We've now officially moved the discussion entirely off-topic, but whatever.

I think we (programmers in general) should have more faith in compilers, they do really good jobs at optimizing. Just compare the result of compiling without any optimization-related flags to something with -O3 -DNDEBUG (or /Ox /DNDEBUG). The difference can be overwhelming (not to mention other optimizing flags that sometimes make a difference), even when you've already written very efficient code. Most of the time a compiler will be aware of all optimizations that you can think of as well as many more.

Inlining is a good example. The inline keyword is nowadays mostly ignored by compilers, because the compiler knows much better than the programmer when to do it and when not to do it. If you have some shortish, non-recursive function that you want to slap an "inline" on, you can trust that the compiler will do it even if you don't. And if it doesn't, it's probably for a good reason. Actually, it might do it on some calls but not on others.

Some compilers (or all?) offer a flag so you can let it warn you when it gently denies your inlining request. If it really bothers you. But as the years pass by the inline keyword will probably be forgotten (heck, isn't it even deprecated in C++11?), just like the register keyword.

Now, it's true that RVO doesn't always kick in when you want it. But that's just RVO; it's really not so simple to apply when it depends on runtime information what object should hold the return value. If that bothers you, you can rewrite your function such that it always returns the same object. It might take some swaps, but that's again something your compiler can optimize so it might still improve your code overall.

Forcing the compiler to fail when it cannot apply some particular optimization that you're obsessed with doesn't seem like a good idea to me. I think it will only help to make your code less portable. The compiler is your friend!