Talk:C dynamic memory allocation/Archive 1

Archive 1Archive 2


Hybrid allocator

In all actuality, I've solved the heap problem for glibc on Linux, in theory; but I can't bring myself to write a "Hybrid allocator" section with an explaination. I'm currently trying to get the glibc people to adopt the design and code it, but they haven't responded to me yet.

The reason why I won't write the section is because I'm a source of bias. Until I get the thing accepted, my only reasoning for putting it on there could be that I'm trying to draw attention to the idea; however, it may be useful to draw attention to it, as others may benefit from the concept. So, if anyone wants me to write a section on it, I will, by request only.

requests+++

Added title to comment --h2g2bob (talk) 17:15, 2 May 2009 (UTC)

Pointers vs. arrays

Pointers and arrays are not the same in C; malloc returns a pointer to an allocated region of memory, it does not return an array (or a pointer to the beginning of an array, or anything else). The article confused this in a few places. See here and here for more information. Neilc 18:12, 27 Mar 2005 (UTC)

Pointers are not the same as declared arrays, but a pointer can be used in place of an array name. I don't know about recent compilers, but back in the 80's, the compiler took any array notation and converted it to pointer notation. wrp103 (Bill Pringle) - Talk 14:23, 29 Mar 2005 (UTC)
I don't disagree that in some situations pointer notation and array notation are equivalent in C -- that is pretty elementary. That doesn't change the fact they are two distinct concepts, however. Furthermore, it is not true that the compiler will generate identical addressing code for an array and a pointer -- there is an extra level of indirection involved in accessing a pointer. For example, this program will dump core:
/* File 1 */
#include <stdio.h>
extern char *declared_as_ptr;

int main(void)
{
	printf("ptr = %s\n", declared_as_ptr);
	return 0;
}

/* File 2 */
char declared_as_ptr[] = "xxx";
The pages I linked to originally have more information on this. Neilc 15:49, 29 Mar 2005 (UTC)

Terminating Zero

A terminating zero is unnecessary if you know the string length -- in the case of the example, 11.

It may be unnecessary, but it is convention in C (it may even be in the standard) that strings are zero terminated. To think of strings in C as being null terminated (as they should be) is more compatible to and aids the reader's understanding than attempting to be overly pedantic at this point. Dysprosia 30 June 2005 06:55 (UTC)

Casting malloc

Although I agree that the discussion is irrelevent to this article, just as a point of interest it is true that most sources now discourage from casting the result of malloc, and from casting void * in general. Doing so is a hang over from Ye Olden Days which is now unnecessary, doesn't serve any good purpose, and can conceal compiler warnings. NicM 20:14, 19 March 2006 (UTC).

I agree that casting from void * is unnecessary, but I'm not sure there's a consensus on whether it is good style, and I definitely don't think that it is "strongly discouraged". It can actually produce some useful compiler warnings; for example:
T *foo = malloc(sizeof T);

If we change the type of foo but don't update the call to malloc, the code will be buggy. One way to fix this is to use malloc(sizeof *foo), although I know a lot of people who find that construct unintuitive. Another way is to use an explicit cast:

T *foo = (T *) malloc(sizeof T);

which ensures that the programmer needs to update the RHS of the assignment if the type of the LHS changes. Now, I can't say I personally find this all that convincing (I would use sizeof *var myself), but that's the argument I've heard for casting away from void pointers in the Postgres source, for example. Neilc

I think that sounds like a fairly horrible reason to use casts. And it still hides the case where stdlib.h is omitted. As you mention, the most reliable way to solve the malloc part of the type-changes-but-programmer-didn't-check-initialisation problem is to use (sizeof *p). NicM 08:43, 20 March 2006 (UTC).
In any case, a few trivial Google searches show that the vast majority of people do discourage casting malloc. Some people do cast it for various reasons, but they do seem to be a minority. Not terribly scientific, but there you go. NicM 08:53, 20 March 2006 (UTC).
Casting malloc is required in C++ (where void* doesn't have an implicit conversion to every other pointer type) (see [[1]]). So code that should compile as either C or C++ must cast the return value of malloc. I am sure I read somewhere that GCC follows this (that its code should be able to compile as C++ as well as the usual C), and the few examples of its code I've seen do cast malloc, but I did not find an actual reference after extensive searching... —Isaac Dupree(talk) 15:03, 24 June 2006 (UTC)
The example states that the program is C, not C++, so casting isn't required. wrp103 (Bill Pringle) 20:00, 24 June 2006 (UTC)
It shouldn't really matter -- a note (at least) about C++ requiring the cast should be present. 80.198.74.58 01:05, 12 July 2007 (UTC)
It is a reason used in some real-life C code (though by no means most of it, apparently) to choose to cast malloc, so it seems that it should at least be mentioned as a reason for casting malloc -- that is all. —Isaac Dupree(talk) 20:06, 24 June 2006 (UTC)
This is not a forum for trying to "figure out" whether or not casting malloc() is a good idea or not. Wikipedia is an encyclopedia, not a multi-author textbook. The distinction is that opinions, practice and advocacy are reported, not espoused. Regardless of whether or not one can make a case for it being good practice, you can't simply claim it here on Wikipedia because you figured it out here in the discussion page. If there is any contention about the issue (and I assure you there is; the C++ language makes it illegal to leave off the cast) you have to find some credible entity who agrees or advocates the opinion and report that. Even finding consensus here is irrelevant. The language supports either method, so advocating one method over another is advocacy. The correct answer is to cite the source for such advocacy, not to use Wikipedia as a platform for advocacy.
The user 71.254.20.100 deleted my request for a citation, leaving the comment that the citation is after the semi-colon and that I should lighten up. What is after the semi-colon is not a citation. Its an attempt at explaining why such an opinion is justified. That's just plain advocacy. Its ok so long as its a cited, sourced thing and Wikipedia essentially takes the position: "There is a prevailing opinion X held by organization Y which is explained by reason Z". If you instead express it as "X is true because of Z" then implicitly Wikipedia becomes an advocating agency for opinion X.
The standard remedy for this common error here on Wikipedia is to express a request for citation. This informs the reader that this kind of mistake is being made, as well as offering an obvious solution to the problem (just find someone who advocates the opinion.) Qed (talk) 19:01, 27 September 2010 (UTC)
My feeling is the paragraph should go entirely. No compiler in current use is going to let that go without a warning and I'm sure that there are going to be plenty of references on both sides of the fence. Unless the conflict itself is notable for its heat (major public figures dissing each other on major public forums). - Richfife (talk) 21:45, 27 September 2010 (UTC)
I second that. Among other reasons: the fact that a C compiler would assume the existence of an erroneous function instead of issuing an `undefined' error is itself broken behaviour. Reinderientalk/contribs 20:57, 28 September 2010 (UTC)
It's actually not wrong; the early C specs allow for undeclared functions (they're supposed to assume that they return an int). In this case the compiler isn't broken, the spec is. Modern compilers invariably flag that with a serious warning, but I don't think any of them call it an error. No modern (in the last 25 years) compiler is going to let it slide without a warning. If someone's using an older compiler at this late date, they know the risks. - Richfife (talk) 21:08, 28 September 2010 (UTC)

Time for me to "be bold" and make edits according to this discussion. Reinderientalk/contribs 00:02, 3 October 2010 (UTC)

Its much better now. Do you think that the rest of the page still contains "original research"? Or can we get rid of that warning at the top? Qed (talk) 06:53, 15 October 2010 (UTC)

correct spelling?

I admit my experience with anything other than Windows is relatively slim so far, but I thought the term was mAlloc. Wrong?

Liastnir 03:37, 10 April 2006 (UTC)

C is case sensitive. It's malloc. Dysprosia 03:39, 10 April 2006 (UTC)

Dynamically sized stack allocation is possible

'alloca', commonly available even if not standardised by the C standard, has allowed it for a long time, and C99 specifies that automatic(on-stack) arrays may have their lengths specified by an expression computed at runtime (although actual support for this is relatively low; GCC's support for this is "broken"). So only the lifetime management issue (or a need/desire for extreme portability) is(are) what makes malloc(heap-allocation, that is) necessary in C. Also, recursive function calls can even be used to effectively create a stack-based variable-size linked list, portably. Dynamic amounts of stack memory completely make sense. Of course, historical reasons play a part in what is used the most today, and quite possibly in the original historical reasons for malloc (I don't myself know). I'm not sure how I'd rework the rationale section though, but anyone may feel free to do it (of course!) if they have any idea how to go about it (or are simply feeling more motivated at the moment...). —Isaac Dupree(talk) 22:29, 24 June 2006 (UTC)

Although it is commonly available, alloca is non-standard, machine dependent and spottily implemented. It is often buggy and unsafe, most implementations cannot determine when the allocation exceeds the space available on the stack. The man pages on most OS discourage its use. C99 automatic arrays will be nice, but as you say, GCC doesn't support them properly yet. NicM 09:07, 4 December 2006 (UTC).

The GCC support for variable length arrays is broken? I've been using it. Also, I heard that GCC supported it even before C99. Maybe C99 has an additional requiremente that GCC does not fulfill yet. Does anybody know? Jorge Peixoto

The webpage Variable Length - Using the GNU Compiler Collection (GCC), which I have just found by googling this search terms, supports my idea that GCC supports variable length arrays quite well, but not exactly like C99 demands. Jorge Peixoto 22:52, 20 February 2007 (UTC)

Oh, I have just realized that variable length arrays are supported in GCC by default: one doesn't have to flip a switch like -std=gnu99 or whatever. They wouldn't enable it by default if it was really broken. Jorge Peixoto 23:00, 20 February 2007 (UTC)

They support VLAs, but they are not C99 compliant.[2] Which is a bit useless if you want to target C99. Although apparently it generally accepts C99, it just accepts other stuff too it probably shouldn't. NicM 23:57, 26 February 2007 (UTC).

Steel Memory Allocator

I'm working on the Steel Memory Allocator, a design I came up with based on everything in the universe just about. The page for it is:

http://steel-malloc.sourceforge.net/

Is this worth adding to 'External links'? I'm basically documenting the entire design of my allocator before I start (site due to be finished 2006 Sep 15) so there's a lot of interesting information; although it's not really much relevant to anything.  ;)

At least whoever writes Steel Memory Allocator once it's done will have a lot to go on, since I can't write it myself. —Preceding unsigned comment added by Bluefoxicy (talkcontribs) 05:38, 14 September 2006

[personal attack removed] —The preceding unsigned comment was added by 69.216.120.229 (talkcontribs) 19:14, 3 December 2006 (UTC).

A new user, User:Davedice contribs, added a link to an article that was apparently created by him. Here is the link:

Could some folks look at this article and decide if this is link is appropriate? Since I'm the person who reverted it, I would prefer not to decide on my own. wrp103 (Bill Pringle) 23:56, 26 February 2007 (UTC)

It looks like a legit paper to me, but it doesn't seem to add a lot to the article since the allocator it covers isn't mentioned. NicM 00:02, 27 February 2007 (UTC).

Alignment

Not sure if the page is about ANSI C only. But perhaps memory alignment should be mentioned, and functions like memalign(), valloc(), and such? —The preceding unsigned comment was added by Jwagnerhki (talkcontribs) 20:40, 3 March 2007 (UTC).

free(NULL)

free(NULL) is undefined, not safe. —Preceding unsigned comment added by 89.132.149.210 (talk) 08:38, 17 June 2008 (UTC)

Check your "facts", it is perfectly safe. ISO/IEC 9899:1999(E) §7.2.30.2 The free function, clause 2 clearly states: "If ptr is a null pointer, no action occurs." 84.163.233.11 (talk) 22:08, 4 July 2008 (UTC)


confusion of NULL versus null pointer

Comment moved from my talk page in response to this edit of mine:

Check the C standard. The return values of malloc() etc. are null pointers, not NULL. NULL is a null pointer constant, which is not necessarily a pointer at all (C99 7.17:3 and and 6.3.2.3:3). —Preceding unsigned comment added by 84.163.235.85 (talk) 09:58, 1 October 2008 (UTC)

I have now checked the C99 standard, and indeed it says in section 7.20.3.3:

"The malloc function returns either a null pointer or a pointer to the allocated space."

and likewise for calloc and realloc. On the basis of this, I have reverted the above edit.

As referenced in the above comment, the C99 standard differentiates between a "null pointer" and "null pointer constant" (6.3.2.3) as follows:

"An integer constant expression with the value 0, or such expression cast to type void *, is called a null pointer constant. If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function."

and it states that the macro NULL is defined as a null pointer constant.

Yet despite this, manual pages (e.g. for glibc) typically state that malloc "returns NULL" rather than "returns a null pointer". This was the basis for my earlier edit. On thinking about it, it seems that the ambiguity is resolved as follows -- please comment if you have anything to add to it.

The implentation of NULL may be as (void *) 0 but according to the standard it may instead be an integer type with value 0. In all cases NULL is a null pointer constant, but if NULL is defined as a void *, rather than (say) int, then it will also happen to be a null pointer. In Linux glibc, NULL is implemented as follows (in <linux/stddef.h>):

#if defined(__cplusplus)
#define NULL 0
#else
#define NULL ((void *)0)
#endif

So (in the case of plain C), NULL is in fact a (void *) 0. Given that the return value of a failed malloc call is a null pointer of type void *, hence equal to (void *) 0, it is fair for the manpage here to say that malloc "returns NULL", although this is a less general statement. (That said, despite this distinction, in most practical cases you will test for a null pointer returned by comparing it with NULL.) — Alan 12:59, 1 October 2008 (UTC)

Allocation size limits

sizeof(size_t)−1 is not same as SIZE_MAX sizeof(size_t) returns size of data type (usualy unsigned int = 4B) not maximum value that can hold variable of that type —Preceding unsigned comment added by 213.220.206.78 (talk) 10:44, 26 December 2008 (UTC)

moved from top of page -h2g2bob:

"sizeof(size_t)−1" is wrong, it will give "3", not "0xFFFFFFFF" on IA-32. —Preceding unsigned comment added by 92.113.180.34 (talk) 02:41, 2 January 2009 (UTC)

Was fixed in january. --h2g2bob (talk) 17:05, 2 May 2009 (UTC)

glibc malloc history

it's based on: libg++-1.2X malloc -> dlmalloc-2.7.0 -> ptmalloc2-20011215 -> glibc-malloc-2.3 —Preceding unsigned comment added by Xose.vazquez (talkcontribs) 22:29, 7 May 2009 (UTC)

RfC: Is behavior of printf after free really undefined?

In the section of this page, Use after free, it is claimed that after a pointer has been passed to free, that:

Even attempting to print the variable with printf is undefined behavior (assuming malloc did not return a null pointer); for example:
printf("%p", (void *) ptr); /* Undefined behavior */

Is the behavior really undefined? Assuming that we discount that the value of the pointer we get back from malloc is undefined, the call to free() is pass by value. The value of ptr will not change as a result of passing it to free. The printf() should print the value of the pointer as it was before the call to free (ie. this is the defined behavior).

The only doubt to this is that, perhaps the original poster was focusing on the %p format placeholder. The wikipedia article on printf states that the placeholder specifies:

Print a void * (pointer to void) in an implementation-defined format.

This specification is a little generic (implementation-defined format). If an implementation were to attempt to "pretty-print" the value pointed to by ptr, then the assertion of undefined behavior would be reasonable.

I suggest that this is not what is meant by "implementation-defined format", and that the scope is restricted to an arbitrary formatting of the value of the pointer itself (not de-referenced). Even if my suggestion is wrong, I assert that in this example, it is only the use of the %p placeholder which presents the problem. So the claim that

Even attempting to print the variable with printf is undefined behavior (assuming malloc did not return a null pointer);

is not correct, because other forms of printf would be defined to print the value of the pointer as it was before the call to free. Example:

printf("%x", ptr); /* Hex value of ptr */ 148.182.52.148 (talk) 04:28, 27 October 2009 (UTC)

I agree. printf is a bad example because free should not change the address of the pointer. A better example of an error would be the one given on page 167 of the 2nd edition of Kernighan and Ritchie. Their example of an error is trying to free all the elements in a linked list with this code:
for (p = head; p!=NULL; p = p->next) /*wrong */
free(p);
This is clearly incorrect because after p is freed there is no assurance that p->next will still point to the next element in the list. K & R also gives the correct solution to the problem:
for (p = head; p!=NULL; p = q) { /*right */
q = p->next;
free(p);
}
Unless somneone objects I would recommend replacing the printf example with the example from K & R, which could easily be cited for a source. Rusty Cashman (talk) 05:25, 3 November 2009 (UTC)
I of course meant to say free should not change the address pointed to by the ponter not the address of the pointer itself (though that should be true as well). Rusty Cashman (talk) 06:35, 3 November 2009 (UTC)
Did anyone bother to check the C standard? If you had, you would see that use of any pointer after free is undefined. Compilers are free to do whatever they want with them. OrangeDog (τε) 19:46, 5 November 2009 (UTC)
I think that it's better to use Rusty's example and treat the printf example as unknown, unless OrangeDog can cite the C standard or a precise reference like Harbison and Steele. It seems like a subtle question and I would not bet money on either side being right. Rusty's example illustrates where the common practical danger is, and that's what's more important to describe in the article. But, I would not write code like the printf example in a real program. For example, if the pointer is in a register and the compiler understands the semantics of free, it might re-use the register after the call to free, clobbering the pointer. Only careful examination of the standard can say whether that is allowed. 69.228.171.150 (talk) 04:59, 14 November 2009 (UTC)

The problem with switching to the linked list example is that it will no longer illustrate the same point. Section 6.2.4 of the C standard (Storage durations of objects) says explicitly that reference to an object outside of its lifetime is undefined behaviour. There is no question that any access through a freed pointer is undefined; the question is whether use of the pointer itself is undefined behaviour. I think that it is undefined, but the argument is not a simple one.

The same section says that a pointer to an object becomes indeterminate when the object's lifetime ends. An indeterminate value is a technical term defined in 3.17.12. It is either a valid value of the type in question or it is a trap representation. It is perfectly true that the free function can't alter the value of the pointer it is passed, but it can alter the meaning of that pointer in such a way that it becomes a trap representation. For example, on some exotic hardware the free function might alter some hardware registers so that any reference to the pointer at all would result in a trap.

The standard states that this is undefined behaviour explicitly in two places, but neither is in normative text. One is 6.5.2.5 example 17and the other is Appendix J which lists undefined behaviour. Both of these state that use (not just use in indirection) of an indeterminate pointer is undefined behaviour.

I would suggest that the current example be kept. Ben Bacarisse (talk) 23:37, 6 February 2010 (UTC)

Tcmalloc

This section needs attention. "The best threaded malloc ever" is non-encyclopedic. I don't know much about it, so I'll leave this task to someone else. —Preceding unsigned comment added by Jdstroy (talkcontribs) 05:35, 7 February 2010 (UTC)

Well, it's better now, but still not up to par. I'm not sure what to do about this. It's clearly a hot-shit, up and coming technology but there really aren't any good references for it that I can find. - Richfife (talk) 19:32, 15 February 2010 (UTC)

nemalloc

nedmalloc is stated as "essentially dlmalloc wrapped by a per-thread lookaside cache to improve execution concurrency", which is unfortunate since this particular software is a rather bad example and the claim "to improve execution concurrency" is a false claim. The claim on the project's website "more than 125 times faster than the standard Win32 memory allocator" is just ridiculous. The author of that software needs to do a reality check.

I have just benchmarked the latest unstable version (the stable one would not even build). The results are identical to the results I had about a year ago with an older version.

Benchmarks were performed using MinGW gcc 4.4 and 4.5 under Windows XP 32 bit on a Core2 quad, with every possible compiler optimization enabled and tuned for the architecture. For being able to build the unstable version with MinGW (producing a good number of warnings), one has to manually add a few #defines. Also, the standard and low-frag heap allocator benchmarks are disabled by default.

The benchmark is more than disillusioning, even more so as the benchmark program is very much contrieved to test specifically the advantageous case (many allocations/deallocations with ultra-high contention and a relatively small total set) which nedalloc was built for, and neither the standard, nor the low-frag allocator are specifically tuned for Core2.

With one thread, both the standard allocator and the low-frag allocator outperform nedalloc by 25-35%. With 2 concurrent threads, the standard allocator is beginnign to spend a considerable amount of system time spinning, but is still about 10% faster than nedalloc. With 4 concurrent threads, nedalloc beats the standard allocator, but is still about 16-18% slower than the low-frag allocator. With 8 concurrent threads (on a 4-core no-HT machine), the standard allocator has deteriorated at about 50% of its single-threaded performance (which is surprisingly good for a generic locking implementation!), while nedalloc is again able to gain a little, but the low-frag allocator still outperforms nedalloc by 11%. —Preceding unsigned comment added by 92.202.27.95 (talk) 14:40, 28 July 2010 (UTC)