10

Recently, I made a new friend. His name is _expand, and we've had some nice conversations, and I've even hung out with him a few times. But when I started asking around, no one had ever heard of my _expand. I became suspicious. I called a few thoroughly non-metaphorical friends at microsoft, and a few friends elsewhere in the business. Nothing. No one had ever used it. I noodled around various search engines and source trees. Nothing except a cursory mention here and there. Certainly not enough information on performance and compatibility for me to introduce _expand into production code or more pertinently, generic libraries.

Worse, there's no equivalent function that I can find in any of the gnu libraries, so anything I hack up with my new friend isn't going to be portable in the least. Which is a shame, because it's really a fascinating and exciting capacity to have. Certainly, I could dig down into realloc, and pull apart how it functions, but the problem there is that much of the implementation is highly variable on *nixes. So I'd have to code version after version to try and get a portable _expand. Still, it seems ridiculous that nothing similar exists in the glib or the expanded gnu libs.

  1. Is there a similar function that I should know about for linux hacking? Mostly Answered
  2. Is there a standard hook that I could build a similar function on? Answered
  3. Does anyone know what kind of performance _expand offers?
  4. How does it interact with objects allocated on the LFH?

To clarify my interests, I'm trying to build a singly-linked accumulator that expands in an attempt to minimize fragmentation while allocating multiple-element blocks along the lines of the traditional deque implementation. By constraining the use-cases for element addition and deletion, I'm hoping to optimize time-to-delete for the whole structure, as well as element insertion and indexing. As a result, the "loud failure" of _expand lets me make the structure think intelligently about when and if it can resize inplace, and what that means about where it can put data.

Jake Kurzer
  • 1,532
  • 4
  • 16
  • 25
  • 8
    Nice literary stylings. Now kill them. For all our sakes. Quickly. – dmckee --- ex-moderator kitten Dec 06 '10 at 02:11
  • There's probably a reason why no one ever uses it. – Rafe Kettler Dec 06 '10 at 02:15
  • 4
    +1 for nice literary stylings. I like them. – Thilo Dec 06 '10 at 02:18
  • @Rafe: I even looked for reasons not to use it, for information on if it was contraindicated. Nothing. @dmckee: Suggested alternative wording? – Jake Kurzer Dec 06 '10 at 02:37
  • Realloc causes a copy operation and a move operation if it cannot expand, which is extremely-bad-ungood in a lot of situations. This makes it unsafe if you have anything pointing into the memory you just realloc'd, slow in cases where you have a high degree of fragmentation or if you're in the LFH and it cannot find a bigger bucket, and overall, it means it has a performance characteristic that tends to be strictly worse than other options on windows. – Jake Kurzer Dec 06 '10 at 02:46
  • 1
    On the other hand, as the documentation states if there is no memory available to expand _expand just fails, you are probably still better off preallocating all the space you need and then manage that allocated space yourself – Harald Scheirich Dec 07 '10 at 00:53
  • The "loud failure" of _expand is pretty much exactly what makes it desirable. Then you can handle the break in contiguity intelligently. The LFH makes pre-allocation an odd endeavor on windows, but unfortunately it's intentionally got no documentation. I do know that the LFH handles all objects 16kb or less, which is a rather odd value. – Jake Kurzer Dec 07 '10 at 01:18
  • 2
    It's been a while, so there's a good chance that you've already found `malloc_usable_size`. It's not standard, but it's widely implemented, and I believe it does exactly what you want. – Max Lybbert May 21 '12 at 05:26

1 Answers1

3

That C++ has been getting by with new and delete sans any equivalent of realloc shows how little attention these things get. Unsurprising _expand is largely ignored when it's not even consistently available at the OS level. If you want to roll your own, there's plenty of precedent for user-defined versions of malloc, and a quick look in /usr/include/malloc.h on my Linux box shows hooks explicitly for this...

/* Called once when malloc is initialized; redefining this variable in
   the application provides the preferred way to set up the hook
   pointers. */
extern void (*__malloc_initialize_hook) __MALLOC_PMT ((void));
/* Hooks for debugging and user-defined versions. */
extern void (*__free_hook) __MALLOC_PMT ((__malloc_ptr_t __ptr,
                                        __const __malloc_ptr_t));
extern __malloc_ptr_t (*__malloc_hook) __MALLOC_PMT ((size_t __size,
                                                    __const __malloc_ptr_t));
extern __malloc_ptr_t (*__realloc_hook) __MALLOC_PMT ((__malloc_ptr_t __ptr,
                                                     size_t __size,
                                                     __const __malloc_ptr_t));
extern __malloc_ptr_t (*__memalign_hook) __MALLOC_PMT ((size_t __alignment,
                                                       size_t __size,
                                                      __const __malloc_ptr_t));
extern void (*__after_morecore_hook) __MALLOC_PMT ((void));

Doesn't look like you'll be able to intercept the existing realloc implementation at that particular decision point though, or easily get insight into whether it will resize inplace, so you might have to reimplement everything (or adapt any of many existing heap implementations).

Tony Delroy
  • 102,968
  • 15
  • 177
  • 252
  • 1
    I'm quite happy with new and delete almost all the time, but this particular problem doesn't resolve neatly unless you have a way of introspecting the heap. Thank you so much for this, I don't know why I didn't think to check malloc.h and feel a bit of a ninny. Do you have any idea if these hooks are portable and standard? One would expect them to be, but I've been burned quite often enough. – Jake Kurzer Dec 06 '10 at 18:54
  • @Jake: Unfortunately, I think they're specific to GNU libC. If you need more portability, then you might look at malloc debug libraries such as electric fence and see how they intercept memory allocation routines. One approach that may or may not suit you is using LD_PRELOAD to stipulate a library that provides overrides for the memory allocation routines... it's very simple to do (one of my old answers discussed this - http://stackoverflow.com/questions/3410990/ld-preload-for-c-class-methods/3411412#3411412 + see my (only) question), but I'm not sure how to do something similar on Windows.... – Tony Delroy Dec 07 '10 at 00:39
  • GNU libC is probably enough for now, I think... Though I'd like to support some of the more esoteric mallocs. I think this is worth doing, but I'm a bit worried about being the one to do it. – Jake Kurzer Dec 07 '10 at 00:41
  • 1
    @Jake: just thinking - modern OSes (even some not-so-modern ones :-)) - allocate virtual memory first and only associate it with physical RAM as specific pages are faulted in, so you can typically afford to allocate an extremely generous container size right away, which lessens the need for _expand. Of course, 64-bit apps have much more virtual address space to play with. – Tony Delroy Dec 08 '10 at 04:17