Þ   briarpig  » thorn  » demos  » heap

     Instead of standard heap apis — new() or malloc() — Wil sometimes needs a heap abstraction he can subclass and replace at need. Wil's default yH heap implementation uses malloc() and free(), but subclasses can do as they please.

     Wil also sometimes replaces global operator new() and operator delete() in all code using them. This is useful for debugging and analysis. Also, in anti-C++ shops pursuing C and/or forbidding C++ standard libraries, Wil can still write code in C++ by replacing heap operators with calls to malloc() and free() (or whatever a given environment prefers). So this page also shows how to replace new() and delete() if you can recompile all sources involved; but it's awkward with third party libraries.

     Wil's main heap for dynamic languages only incidentally uses heap yH's simple base api. To control where memory is allocated for garbage collection — and to prevent fragmentation, Wil uses a complex subclass of yH introduced in (future) page and book demos, allocating space in page and super-page granularity. The page/book heap in leaf class yPBH actually uses root class yH as a raw allocator whose blocks are suballocated by yPBH.

     The main api of yH is only three methods hmalloc(), hcalloc(), and hfree() which simply call the similarly named standard C library methods in the default method implementations. Subclasses must aim for the same contract: hcalloc() zeroes allocated memory and hfree() deallocates anything allocated by either hmalloc() or hcalloc(). Anything else is extra.

     Non-virtual hcopy() utility methods call virtual hmalloc() to get memory for copying yv runs (cf «). Each subclass might or might not be threadsafe. Any instance of yH is threadsafe in so far as it has no state, and the standard C heap is itself threadsafe.

     Although yH has an abstract api, the class itself is concrete: you can instantiate yH itself and it allocates memory using malloc() and free(). Singleton instance yH::g_1H is provided so you need not instantiate any other instance of yH; one is enough:

     The destructor does nothing since yH has no state. And the three main virtual methods are trivial wrappers:

     Method hnil() only logs unexpected nil slots:

     The remaining hcopy() methods provide gratuitous convenience support for copying contiguous octet sequences in yv iovec format from the run demo. The main idea of hcopy() is to ease writing some kinds of sample code that copies iovec buffers, when careful memory allocation is less important than getting immediate, clear results. Done early in one place, this reduces clutter later.

     Each memory block allocated by hcopy() has one extra byte of space to hold a nul byte; but this extra byte is not reflected in the v_n length of the yv instance returned, because the extra nul is not part of the copied content. (It's there only for debugging, to make examination under a debugger like gdb a better experience given a friendly C string termination for display purposes.)

     Both versions of hcopy() aim for constructive behavior when a nil pointer is encountered: in this case, the yv returned also has a nil v_p pointer but sums the input v_n lengths.

     The following yH subclass shows a random assortment of effects you might choose to use in heap subclasses. The name yxHH is somewhat arbitrary since Wil wrote it as a throw-away example for this demo (and for use in other demos where effects of heap allocation can be shown by printing yxHH).

     Because yxHH has state, Wil added a yx instance from the mutex demo to show how you might make a heap threadsafe, even though Wil won't write any samples using yxHH with more than one thread.

     Member h_stats sees average and std deviation for allocated block sizes, illustrating yrsum from the stat demo.

     An explanation of nested class Hq and inline quote() appear in the quote demo. And the api for printing is shown in the out demo. (But you needn't read those first.)

     As you read the code, try to remember Wil included random features that might look interesting, without following a theme or exercising restraint to increase simplicity. The code is just a big pile of stuff intended to provoke ideas, to suggest similar effects you might pursue in other contexts.

     If yxHH_SUM_BLOCK_PREFIX is defined, every block allocated starts with an extra eight byte prefix containing the block size and a magic signature. The point of this compiler switch is to show you can add or omit features depending on build options you need for debugging.

     This part of the api shows yH subclassing. Note a parent heap for the constructor is optional; when not provided, malloc() and free() are used instead.

     The following global singleton instance of yxHH is used by sample code in the right column for ymu_malloc() and ymu_free() (cf »).

     Struct Hprefix is only used as an eight byte prefix of every block allocated if yxHH_SUM_BLOCK_PREFIX is defined.

     Api shown below is the usual sort of boilerplate used for printing as shown in out and quote demos.

     Here's where the singleton is instantiated:

     Constructing yxHH mainly involves initializing h_mutex and h_stats. The destructor logs if outstanding blocks exist.

     All the printing methods here just call Hcite(). You can see examples of output in the right column (cf »).

     See bottom column right for hmalloc(), hcalloc(), and hfree() implementations (cf »).

     Further use of yxHH will appear in the (future) iter demo to reveal effects of list mutation on allocation heaps.

     thorn: todo, names, fd, iovec, assert, log, run, hex, crc, buf, in, out, quote, escape, compare, file, deck, cow, arc, blob, tree, slice, rand, time, stat, hash, heap « Þ, node, primes, page, book, pile, stack, atomic, lock, mutex, thread, map, meter, list, iter, ctype

     (mu: toy, peg, imm, tag, box, symbol, token, number, bigint, class, method, reader, writer, eval, env, vm, gc, world, pcode, compiler, asm, lathe, lisp, smalltalk, design, weight, jar, card, harp, debug, profile)

     Some demos are stubs: todo is a demo guide. See toy for mu updates on language pages; names introduces naming schemes.

     Some folks are aware you can override operator new() and operator delete(), but don't realize to what extremes this can be taken. You can also replace standard versions provided by the standard C++ library, by declaring inline replacements before the operators are first used.

     However, there are so many gotchas it's hard to list them all — and frankly it's tedious to explain each one. For example, suppose you use a third party library that's already compiled; if the api allocates objects you must delete, or vice versa, then you're obligated (awkwardly) to honor the library's original contract: that you'll share a standard definition of heap operators. This can be hard to work around. (You must preseve the ability to reach the original new() and delete() for that library.)

     Ignoring complex problems like that, Wil usually has a header file named something like ynew.h which is included first before any other header file in each of his header files and source files. This header contains declarations you see below. Whether you can succeed in using variants without reference to exceptions like std::bad_alloc and std::nothrow_t depends on whether you include any system header including a standard C++ new.h header. Once a standard header declares operators one way, you can't declare a new signature without a conflict.

     If you write an embedded system using no standard C++ headers at all, you can easily use the simpler versions of new() and delete() inlines below with no mention of exceptions. Otherwise you must leave switch YNEW_STD_BAD_ALLOC defined to agree with the usual fare.

     All variants of new() and delete() and below are defined in terms of these two methods mimicking malloc() and free():

     You can instead use malloc() and free(), which also works fine. But instead we'll use ymu_malloc() and ymu_free() to show some games you can play. In order to maximize applicability to the yH api shown on this page, we'll define those in terms of a yH subclass even though this isn't necessary. So dependency on yH is just an option, done gratuitously in ymu_malloc() and ymu_free() as illustration.

     Okay, here are inlines with exception types in signatures:

     Since there are fewer versions without exception types, the following list of inlines is much shorter:

     Note you can use the same method for vector and non-vector versions of operators, just as shown above using ymu_malloc() and ymu_free() everywhere regardless of whether an array is allocated or not. Or instead, you could choose to preserve the distinction, and use different method for vectors. For example, if you need vector specific statistics, you can preserve that information.

     Finally, here's the code for ymu_malloc() and ymu_free(). But note comments just afterward explaining this kludge.

     The guts of ymu_malloc() and ymu_free() could just as easily be malloc() and free() — or for that matter, direct calls could be used instead. So what's up with heap yxHH shown above?

     Class yxHH is an example subclass of yH shown bottom column left (cf «), and it's a collection of random debugging tactics you might use when implementing a heap subclass. The yxHH name is somewhat random because it's a throw-away example as far as Wil is concerned, written specifically for this demo. However, Wil added the ability to print yxHH so you can see usage statistics including count, average, and standard deviation (for all allocations) plus the N currently allocated blocks with a sum of block sizes.

     The following sample code shows how the effect of inlines for operator new() and operator delete() can be seen as state changes in yxHH when printed. (In these examples, each allocated block begins with an eight byte prefix, so all the sizes are eight bytes more than you might otherwise expect.)

     The printed output appears below. Each yxHH tag was written by yxHH::Hdump() (cf «). Note the last line shows total outstanding space allocation returns to zero after both arrays are deleted.

     Wil actually wrote the yxHH heap first to show the effects of using template queue yqt in the list demo, along with the element erasure using template iterators in the (future) iter demo.

     The following kitchen sink implementations of hmalloc(), hcalloc(), and hfree() are somewhat explained by the left column introduction to yxHH (cf «). They appear here to balance the left and right columns. (Otherwise a long dialog would be necessary, and it's late already.)

     Of course hcalloc() looks like hmalloc() with small edits:

     If block sizes are tracked, hfree() asserts the tag in the block's prefix is right, and the size of that block is subtracted from the outstanding sum of all blocks allocated.

     All this code is available only under the BriarPig mu-babel license described fully on the rights page. You do not have permission to reprint this page in any way. No feeds or repackaging is allowed. You can link this page if you want folks to read it.