Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A Story Of realloc (And Laziness)

blog.httrack.com

Post reply on HN
Print view View original

41–50 of 65 posts

Re: A Story Of realloc (And Laziness)

#41

Post by dbaupp »

yongjik wrote: post #35
plorkyeran wrote: post #13

Earlier quoted context omitted.

It always calls (the equivalent of) malloc + memcpy + free for each grow, so it can be anywhere from the exact same speed (when realloc does the same thing internally) to absurdly slower (in the given case of a large array that has to be paged in). The first case is by far the most common case, but it is something that sometimes matters.

It seems that even vector::shrink_to_fit is implemented that way. That is, when you call shrink_to_fit, it first copies all elements it has, swaps itself with the new copy, and deletes the original vector. (Probably because there's no portable way of returning only part of a contiguous memory region. Yikes.) http://stackoverflow.com/questions/2695552/how-to-shrink-to-...

I think the reason is the existence of move/copy constructors, i.e. it's invalid to just move a C++ object in memory (as a realloc would do), in general.

(shrink_to_fit does need to (attempt to) get a smaller allocation, otherwise or wouldn't be shrinking the vector.)

Re: A Story Of realloc (And Laziness)

#42

Post by asveikau »

fprawn wrote: post #32
fprawn wrote: post #10

Earlier quoted context omitted.

Memory allocation failures are virtually non-existent in modern desktop computers. Good practice is to not test return values from malloc, new, etc. Memory can be allocated beyond RAM size, so by the time a failure occurs your program really should crash and return its resources. Embedded systems have fewer resources and some will not have virtual memory and so the situation will be different. But unless you know bet…

I'll clarify this. I'm not saying you shouldn't ever check return values, that's obviously not the right thing to do. And of course there are exceptions to the general rule. If you're allocating a large chunk of memory and there's a reasonable expectation that it could fail, that should be reported, of course. In the general case, however, if allocating 100 bytes fails, reporting that error is also likely to fail. An…

> In the general case, however, if allocating 100 bytes fails, reporting that error is also likely to fail. An actual memory allocation failure on a modern computer running a modern OS is a very rare and very bad situation. It's rarely recoverable.

I call BS on this. First of all, it's not the 100 byte allocation that is likely to fail; chances are it's going to be bigger than 100 bytes and the 100 byte allocation will succeed. (Though that is not 100% either.) Second, the thing you're going to do in response to an allocation failure? You're going to unwind the stack, which will probably lead to some temporary buffers being freed. That already gets you more space to work with. (It's also untrue that you can't report errors without allocating memory but that's a whole other story...)

I suspected when I wrote in this thread that I'd see some handwavy nonsense about how it's impossible to cleanly recover from OOM, but the fact is I've witnessed it happening. I think some people would just rather tear down the entire process than have to think about handling errors, and they make up these falsities about how there's no way to do it in order to self justify... Although, when I think back to a time in which I shared your attitudes, I think the real problem was that I hadn't yet seen it being done well.

Re: A Story Of realloc (And Laziness)

#43

Post by whoopdedo »

nhaehnle wrote: post #36
picomancer wrote: post #34

This is really neat. Somehow I always assumed realloc() copied stuff instead of using the page table. But say you have 4K page table size. You malloc() in turn a 2K object, a 256K object, and another 2K object, ending up with 2K, 256K, 2K in memory. Then your 256K is not aligned on a page boundary. If you realloc() the 256K it has to move since it's surrounded by two objects. When you do that, you'll wind up with the…

The libc memory allocator does not simply hand out memory contiguously. In your example, the 256K block will end up being 4K aligned. In fact, that's what the article already explains: the large alloc will just end up being passed through to the kernel, which only deals at page granularity.

What the article revealed to me is that there is no guarantee a contiguous block of allocated virtual memory will be backed by contiguous physical memory. In hindsight, that should be obvious.

But what does this mean for locality? Will I be thrashing the cache if I use realloc frequently? Do I even have the promise that malloc will return unfragmented memory?

Re: A Story Of realloc (And Laziness)

#44

Post by bodyfour »

plorkyeran wrote: post #4
CJefferson wrote: post #2

I have also found people often unestimate realloc (but have never done the same level of investigation to find out just how clever it is!) On several occasions I have wanted to use mmap, mremap, and friends more often to do fancy things like copy-on-write memory. However, I always find this whole area depressingly poorly documented, and hard to do (because if you mess up a copy-on-write call, it just turns into a cop…

C++ really wants a realloc variant that extends an allocation if it can be extended without a copy, and leaves the allocation unchanged if it can't. The annoying thing is that there's no good reason why this can't exist beyond that the STL allocator interface happens not to have it.

jemalloc's non-standard interface gives you some of what you want, expectially xallocx() http://www.canonware.com/download/jemalloc/jemalloc-latest/d...

There have been C++ templates written that use jemalloc-specific calls; for instance see Folly from facebook. I haven't taken a close look, but I know they do some jemalloc-specific code: https://github.com/facebook/folly/tree/master/folly

The other allocated-related thing that C++ really wants (and could benefit C as well) is "sized deallocation". Most of the time you often know the exact size of the memory you allocated. If you could pass that to free() the allocator could save some work determining it. In the case of C++ the compiler can often do this on your behalf for many "delete" calls (at least in the cases where it knows the exact type). Google did an implementation of this idea and got good results. They submitted a proposal to the standards body but I don't know if there is any recent activity. I hope it does happen though: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n353...

Re: A Story Of realloc (And Laziness)

#45

Post by nhaehnle »

whoopdedo wrote: post #43
nhaehnle wrote: post #36

Earlier quoted context omitted.

The libc memory allocator does not simply hand out memory contiguously. In your example, the 256K block will end up being 4K aligned. In fact, that's what the article already explains: the large alloc will just end up being passed through to the kernel, which only deals at page granularity.

What the article revealed to me is that there is no guarantee a contiguous block of allocated virtual memory will be backed by contiguous physical memory. In hindsight, that should be obvious. But what does this mean for locality? Will I be thrashing the cache if I use realloc frequently? Do I even have the promise that malloc will return unfragmented memory?

Do I even have the promise that malloc will return unfragmented memory?

What do you mean by this? malloc returns memory that is contiguous in the virtual address space. It may not be contiguous in the physical address space, but that should be irrelevant for cache behavior.

Will I be thrashing the cache if I use realloc frequently?

I suppose. But if you use realloc, you should anyway ensure that you realloc geometrically growing chunks of memory (e.g., whenever you need a new buffer, you multiply its size by a constant factor like 1.2 instead of just adding an element at a time). As a result, realloc() should be infrequent enough that it normally doesn't matter.

Re: A Story Of realloc (And Laziness)

#46

Post by deathanatos »

htns wrote: post #33
yaur wrote: post #27

Earlier quoted context omitted.

Ugh. I would much rather know that the process died because of allocation failure than try to figure out why some code is trying to write to a random null pointer as these are two very different types of bugs.

I'm having a hard time picturing a situation where it would be tough to figure out. Typically you allocate memory to use it right after. errno will be set too. Of course, there is no reason to not do all your allocation through a wrapper function which does check and abort on failure. I think the point was that surviving malloc failures is a dubious approach - instead go all in, or if it's a long-running service, pro…

In one scenario, the process writes "Out of memory." or similar to stderr. In the other, it segfaults. Maybe.

I'll take the clear error message.

Re: A Story Of realloc (And Laziness)

#47

Post by plorkyeran »

bodyfour wrote: post #44
plorkyeran wrote: post #4

Earlier quoted context omitted.

C++ really wants a realloc variant that extends an allocation if it can be extended without a copy, and leaves the allocation unchanged if it can't. The annoying thing is that there's no good reason why this can't exist beyond that the STL allocator interface happens not to have it.

jemalloc's non-standard interface gives you some of what you want, expectially xallocx() http://www.canonware.com/download/jemalloc/jemalloc-latest/d... There have been C++ templates written that use jemalloc-specific calls; for instance see Folly from facebook. I haven't taken a close look, but I know they do some jemalloc-specific code: https://github.com/facebook/folly/tree/master/folly The other allocated-related…

Folly does take advantage of jemalloc to expand allocations in-place when possible, but afaik it doesn't do the more extreme optimization mentioned in the article where pages are moved to a different virtual address without actually paging into memory.

Sized deallocation made it into C++14.

Re: A Story Of realloc (And Laziness)

#48

Post by _kst_ »

asveikau wrote: post #5

This bothers me so much: buffer = realloc(buffer, capa); Yeah, 'cause when it fails we didn't need the old buffer anyway... Might as well leak it.

It depends on your recovery strategy. If your response to a `realloc()` failure is going to be to terminate the program, then you might as well assign the result back to the original pointer. If you're going to continue executing without allocating the extra memory, then yes, you need to assign the result to a separate pointer.

Re: A Story Of realloc (And Laziness)

#49

Post by bodyfour »

plorkyeran wrote: post #47
bodyfour wrote: post #44

Earlier quoted context omitted.

jemalloc's non-standard interface gives you some of what you want, expectially xallocx() http://www.canonware.com/download/jemalloc/jemalloc-latest/d... There have been C++ templates written that use jemalloc-specific calls; for instance see Folly from facebook. I haven't taken a close look, but I know they do some jemalloc-specific code: https://github.com/facebook/folly/tree/master/folly The other allocated-related…

Folly does take advantage of jemalloc to expand allocations in-place when possible, but afaik it doesn't do the more extreme optimization mentioned in the article where pages are moved to a different virtual address without actually paging into memory. Sized deallocation made it into C++14.

Since 2.1, jemalloc does support using mremap to do large realloc()'s, although it seems to be off by default. You need "./configure --enable-mremap" to get it.

That's good news about sized deallocation, I hadn't noticed that there is an updated "N3778" proposal which apparently was accepted. I still haven't seen the dlmalloc work to support that show up in the main svn branch.

Re: A Story Of realloc (And Laziness)

#50

Post by fprawn »

asveikau wrote: post #42
fprawn wrote: post #32

Earlier quoted context omitted.

I'll clarify this. I'm not saying you shouldn't ever check return values, that's obviously not the right thing to do. And of course there are exceptions to the general rule. If you're allocating a large chunk of memory and there's a reasonable expectation that it could fail, that should be reported, of course. In the general case, however, if allocating 100 bytes fails, reporting that error is also likely to fail. An…

> In the general case, however, if allocating 100 bytes fails, reporting that error is also likely to fail. An actual memory allocation failure on a modern computer running a modern OS is a very rare and very bad situation. It's rarely recoverable. I call BS on this. First of all, it's not the 100 byte allocation that is likely to fail; chances are it's going to be bigger than 100 bytes and the 100 byte allocation wi…

If you have time, can you expound on this? Is there, perhaps, an open source project that handles NULL returns from malloc in this way you could point me to?
Post reply on HN