When managing memory in large systems that scale, Wil must sometimes plan how much memory is used for what, and how to organize effects of granularity and fragmentation as memory is allocated and freed. One tactic is large re-usable buffers like a page but much larger in size. Wil uses the term book to name such super-page objects, which are typically 64K or 128K in size.
Most code comments in the left column are cloned from the page demo, which was written first. In many places the api is identical except for replacing page terms with book terms. If you memorized the page demo: the right column is new.
yPBH heap «
The actual heap for book allocation is shown in the (future) pile demo. It subclasses the basic yH heap interface:
Class yBn is defined further below on this page (cf »).
The hBn() and hcBn() methods each pass a yht<yBn> handle argument, receiving a first ref to a returned yBn book node whose nbook() inline method returns the yB book.
The yB api shown next mainly defines a physical format as size in bytes, plus a bunch of convenience methods using that book of bytes. The yBn book node api further below (cf ») shows details for the node api; a book remains allocated as long as its yBn node is still in at least one handle.
A book is basically a super-page: like an operating system's virtual memory page, but much bigger. The size of a book can vary from build to build — depending on the constant defined for size — but reasonable sizes are in the range of 64K to 128K. Larger books might only make sense in very memory intensive apps.
Several factors influence choice of book size. Ideally a book is large enough to amortize many small operations in memory (like allocating boxed gc objects) per transition between books where discontinuity occurs. But we also want books to be small enough that allocating many of them at one time is not an onerous task for the host environment.
A current yPBH heap allocates 128 books at a time, so if a book is 64K in size, the granularity of host environment allocation is 8MB at a time. This is small potatoes these days. You should avoid making yB so much larger than 64K that allocating 128 at a time causes pain. The goal? Big enough books, but not too big.
An important feature of books is alignment: each book starts at an address that's a multiple of book size in bytes.
struct yB «
The api for yB books is quite simple. The state is just a contiguous sequence of aligned bytes.
Note a book might actually be another size: kBsz might instead be 128K or even 256K. Code comments and docs typically say 64K, as if it could not change, but the actual size of a book is whatever kBsz says. Usually it's 64K — or 0x10000 in hex, so book-aligned addresses are zero in the low four hex digits.
Constants above are used in bit masks: klow=0xffff selects bits of an address inside a book, and kmask=0xffff0000 selects the book that contains an address, in 32-bits.
Array B_u8[] is the array of bytes inside a book. This is the only state inside a book: the address of B_u8 is the same as the address of yB. By convention each book address is book-aligned, so not just any yB instance is valid: only those allocated at an address that's a multiple of kBsz.
Nothing stops you from delcaring a yB anywhere you like, say at a non-aligned address. But any book allocated by yPBH will be aligned, and many yB users assert Bgood() below is true.
When Bgood() is false, you can log this using Bbad():
Method p2B converts any p pointer to the yB book containing that address. This is just a matter of zeroing low bits:
Method Bzero() safely clears a book to zero:
Or Bmemset() can set all bytes to some other value:
Method Bhash() returns a hash of a book's address with fewer hashmap collisions expected, using a pseudo random number generator from the rand demo:
Most yB methods are inlines, because dealing with a fix-sized format with alignment isn't complex.
yB.cpp «
Non-inline book methods appear below. Method Bbad() logs when a book does not look good; printing a backtrace here also would help:
Memory management of pbooksages is done by refcounted yBn book nodes below. Under þ, books are allocated by yPBH heaps.
class yBn «
Each þ yB book allocated by yPBH is refcounted using a node subclass named yBn, whose name naturally means thorn Book node. Each yB has a one-to-one correspondence with exactly one yBn node, and the source yPBH heap allocates both.
When refs hit zero as the last handle loses the final ref to a book node, both book and node are deallocated, returning the book to a free list in the yPBH heap.
Currently sizeof(yBn)=40 so memory management overhead for a book is forty bytes — far less than 1% — plus any additional bytes used to track the handle, which could run twenty more bytes. This overhead is quite tiny, especially when a book is later suballocated with high efficiency, avoiding further per-block overhead for objects allocated from a book.
The yht handle template is described at length in the node demo, and here we see yBnh is a synonym for yht<yBn> whose name means thorn Book node handle.
When the last handle with a ref to the same yBn book node loses that reference (so count of refs go to zero) the yBn node is freed, returning the yB book to a heap free pool.
Class yBn is publically a node so you can put it into a handle to increment the refcount; but it's privately a yqe queue element so it's managing heap can keep it in one list or another behind the scenes. Each heap knows the exact status of every book.
The first two new state members n_H and n_B track the heap and actual book for the node. The heap is needed so the node can be sent back to the heap when freed (or to alloc new nodes when an old one is cloned).
The n_n next node member shown below allows the node's heap to store every node in a hashmap bucket's singly linked list. (Once added to this hashmap bucket, a book node is never removed until the heap is destroyed.)
The next n_16 field of 16-bits is where a descriptive ID is stored, that's passed when the book is allocated.
One byte magic signature n_ty says this node's type had better always be 'B' for book. This can be asserted when casting yn* to yBn*: it's a dynamic type tag.
The last one byte n_fuh member indicates whether a book node is free, used, or set aside for internal heap use; the raw value is only used in unconstructed nodes. (How can nodes not yet be constructed? Space allocated, but not yet used.)
None of the state members above are public, and neither are any of the constructors below. So how can you construct a yBn book node instance? You can't. Only yPBH heaps can construct a book node — so yPBH is a factory for yBn book nodes. You can see the api to alloc a new yBn instance at the top of this page (cf «).
The getters shown below are all public. Some of them must return constant values when a book node is allocated. (But yPBH works with book nodes in other states, when they are not currently allocated.) Wil hopes the meaning of these getters is sufficiently obvious, because they won't be explained.
The following size() and c_str() methods try to look at a book as a C string, but you should note the following dire warning: if you call c_str(), be advised no terminating null byte appears unless you put one inside the book yourself.
Method nbook() returns the node's book — this is the main method in the entire api. When given a book node, you should mainly be concerned with the book. Well, here it is:
The following getters and conversion operators return the book as a run, buf, or iovec. You can easily do this yourself; but by using these methods, you might avoid mistakes.
Bmemset() lets you call a book method on the node.
As always, yn node destructors are not public: you can only destroy a node by releasing all refs, by clearing all handles that ref a given node. You can't do it by fiat.
See the node demo for virtual method descriptions. Or you can follow the links to comments below on implementation.
Method B2iovec() is a static, subclass specific imitation of virtual n2iovec(), when you know the type.
As always, only handles in the node demo can invoke the on-zero-refs handler. Note virtual nzeroUses() was not overriden because the default do-nothing implementation works.
yBn.cpp «
Non-inline book node methods appear below. Most of them are very lightweight, and a couple aren't even implemented yet because Wil hasn't needed them; copy-on-write with books is still pending, but it's (of course) trivial as always.
Method nout() writes the entire book.
Virtual n2iovec() converts to iovec the same way B2iovec() and asiovec() inlines do.
Cloning is easy using yPBH::hBn() and copy. (They'd be done already now if challege was present.)
The destructor might never be called — yPBH pools nodes, never freeing pages and books until the heap is destroyed.
Checking goodness and badness is typical boilerplate in search of unexpected violations of C++ runtime guarantees.
On zero refs, a node frees itself using a private heap api. The mnemonic for x here in the name refers to the idea of max lifetime limit for a node, or maybe x-ing (crossing) out a node.
Method Bnbad() must log problem descriptions.
"At the bottom of the right column, why did you print the yPBH too?" Stu asked. "It made the column too long and now you have to write this dialog."
"Just to provide more context," Wil replied. "You can see pages and books used by yBqm inside dumped yPBH output."
"Oh you're right," Stu noticed. "Why not just remove some of the printed attributes to shorten lines?"
"Most are at least a little informative," Wil justified. "There's more to correlate this way. Kinda verbose though."
"Heh, I'll say," Stu sighed. "Let me ask about a couple. What's h=7d11e3ae. Page or book hash?"
"Yeah, I think it's the crc of the page or book address," Wil agreed. "But the address itself makes a fine hash much of the time given a prime number of buckets."
"You said 128 books were allocated at once currently," Stu recalled. "But I only see books at indexes zero to 125. That's only 126 — what happened to the other two?"
"Two are immediately used internally without adding them to the map since they'll never been allocated publically," Wil explained. "I can map those two later if it helps."
"What are those two books for?" Stu puzzled. "Is one for the page hashmap? At address vec=2010000?"
"Yes, that's one of the missing books," Wil confirmed. "The other book is diced up into useful subspace right off the bat. Half of it becomes the hashmap of books at address 2008000 in the output shown. That book is the end-piece."
"You knew I was going to ask what an end-piece book is, right?" Stu prodded, laughing. "Go on: explain."
"Well, yPBH doesn't assume space allocated from yH has any alignment," Wil explained. "So it just asks for many books and discards one to force aligment."
"But it's not really discarded," Stu countered.
"That's right," Wil agreed. "All parts of the buffalo are used. A book removed to force alignment, if necessary, is then subdivided into pages, and nodes for pages and books."
"What if you have book alignment already?" Stu asked.
"Then I still dice one book into pages and nodes anyway," Wil elaborated, "to avoid irritating bootstrap problems."
"Is this a preview of a future pile demo?" Stu guessed. "And why do you call yPBH a pile?"
"Yeah, some of this material is redundant with parts of the pile demo," Wil confirmed. "But central issues can't be said enough times. I call yPBH a pile because it's a synonym for heap — and I can refer to a pile of pages and books."
"Why not just say page/book heap every time," Stu wondered. "Is that too clunky?"
"Because I know folks will really say 'P, B, H heap' all the time instead," Wil predicted. "Life is too short to give small things four syllable names. You can thank me now."
"I suppose it will grow on me," Stu pondered. "Do you coin names in your day job all the time too?"
"Yeah," Wil nodded. "And usually folks hate short names at first. The negative feedback is often quite sharp."
"But what?" Stu prompted. "You're implying they get over it? What changes their minds?"
"Technical discussions suddenly become crisp using terse names," Wil explained. "Suddenly long phrases become one syllable, and questions for clarification about what someone just said go way down. Talking is more clear."
"Uh, huh," Stu was dubious. "So you say. Folks actually get enthusiastic? What works best?"
"One syllable names that sound like nothing else work best," Wil asserted. "Especially when they replace a name that was several words."
"Hmm," Stu considered. "Well I'd love to stay and shoot the breeze, but I have to book. See ya."
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. Neither feeds nor repackaging is allowed. You can link this page if you want folks to read it.
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.
Parts of this book demo strongly resemble the page demo because a yB book is similar to a yP page, just bigger. And a yBn book node bears the same relation to yB that a yPn page node bears to yP. So code for book nodes and maps will closely parallel code for page nodes and maps.
However, pages don't have the same sort of role in garbage collection as books. The next section explains.
The design of 64K (or 128K) books in þ is specifically geared to support a form of garbage collection Wil designed around 2000, give or take a year, which manages large areas of space with higher granularity than classical garbage collection systems. Instead of finding a link to old public descriptions from several years ago, consider the following short summary and recapitulation of basic ideas.
A classical form of copying collection often describes available memory as consisting of two large, equal-sized partitions — let's call them hemispheres or hemis for short — where at any given time one hemi is in use and the other hemi is held in reserve. When gc (garbage collection) is required, one hemi is copied to the other; then they switch.
The bad part of this classical design is obvious: half of memory is wasted. The hemi held in reserve isn't useful for anything except ensuring the used hemi can be copied when space is exhausted.
Even worse, there's a problem in deciding how big memory should be. If you have two large hemis, how do you gracefully make these memory partitions bigger? Growing the basic memory footprint in a hemi model is very awkward at best. Wil wondered why folks didn't solve this problem using an obvious simplification.
Instead of using a couple hemis, or some small number of them, why not define each partition as a collection of smaller pieces? (Call each piece a book since books on this page are designed to fill exactly this gc role Wil dreamed up.) Then several issues get easier to address. Want to make the size of memory bigger? Just allocate more books. Ready to collect garbage? How many books do you need to keep in reserve for gc? Only as many as you might collect at one time. If you partition the address space into disjoint book set partitions, each partition can act as a lightweight process garbage collected independently.
Wil's plan to use books for gc aimed to reduce the size of dead space held in reserve for gc, because only enough reserve to copy the largest lightweight process is needed. If you craft your app partitions with care, this can be far less than half all your available memory.
Better yet, the fewer books in a lightweight process, the faster it can be garbage collected. A single lightweight "process" consisting of a few megs of books can be collected in a few milliseconds — the time is mainly how long it takes to touch that much memory.
The hashmap of books shown in the next section aims to represent the address space of a lightweight "process" using garbage collection in a set of books. One of the things it must do very quickly is answer the question, "Is this pointer inside this 'process' address space?" In other words, the map must very quickly say whether a pointer is contained by a book in the map. Even the cost of hashing a book address might cost too much. So the map must use a prime number of buckets.
Wil plans to implement a classic Cheney style stop-and-copy gc in the first toy language implementation. And part of this algorithm requires telling whether an object must be copied or not. A classical description of Cheney uses an address range check to see whether an object lives inside the source hemi being copied. But when Wil uses books to compose gc address spaces, the range check must take the form of a hashmap key lookup: is this pointer's book inside source books being copied?
Among other things, this design allows layered gc address spaces. One address space of books can hold long-lived objects — perhaps immutable objects never collected. A mutable address space can refer to objects in the immutable space, and this will cost nothing in gc to discriminate because it will already be necessary to check every object for membership in a source set of books being copied. For sandboxing applications, it will be easy to copy-on-write starter address spaces cloned into a smaller footprint sandbox, which can simply be thrown away when a sandboxed request is done.
In other words, the use of books in garbage collection is critical for the kinds of optimizations Wil plans to use, and they seem exciting, if a little off the beaten path.
Part of the class below will strongly resemble maps in the page demo's right column. Some of the interfaces used are defined in the page demo. For example, the yPq page queue class is used to hold references to page nodes, so the pages can be used to build data structures while yPq handles memory management (cf «).
However, unlike the page demo maps, the map below allocates the book members inside: it's a factory for book instances which automatically owns and tracks the set of books in a hashmap. The idea is to provide a growable dynamic address space with book granularity. (To garbage collect, Wil can make a new yBqm map to copy old books, then destroy the previous instance to release old books processed.)
Class yBqme is the book queue map element used to add hashmap members to yBqm below. The key (book pointer) is stored in me_B, and me_e is just a link to the next elem in the same hashmap bucket, where each bucket is a singly linked list.
Note yBqme is a subclass of yqnhe which has a handle that refs a node. Each yBqme elem instance holds a ref to a book's node; this is how the queue in yBqm manages owership of every book inside.
class yBqm «
The name of class yBqm means thorn Book queue (and) map, but it's really just a map of books. The q for queue means yBqm is both a queue of books and a map of books. The queue is list of handles that ref book nodes; the map indexes these books by address.
Each element in a map bucket is a yBqme element, defined immediately above. (In the page demo, comparable map elements were nested classes.)
The number of buckets is kslots: the largest prime number less than 1024, because one 4096 byte page can hold at most 1024 yBqme* bucket pointers, assuming each pointer is 32-bits. Here you see assumptions about both page size and pointer size.
The last state member m_epp above is the array of buckets, whose name means element pointer pointer since the hashmap is an array of element pointers; m_epp points to the start of a yP page — the first one allocated from heap m_H by the m_Pq list of pages.
Iovec m_vH is the remains of the last page allocated for the purpose of providing space for yBqme element allocations. The name of m_vH means (u8) vector heap, because this yv run is treated as a fix-sized heap for suballocation. When exhausted, m_vH is replenished simply by allocating another page from m_Pq.
When first allocated, new yBqme elems allocated from m_vH go straight into the m_epp hashmap after construction when new members are added. Each new elem is also added to list of elements m_le, which is a list of book members held in handles.
The current number of map members is the length of m_le, which is a list of all books add to the map.
Follow links above to code and explanatory comments.
Method mnewB() allocates a new book from heap m_H, adding its node to the queue and the book address to the map.
Method mfindB() returns the book containing p if and only if that book is a member of the map.
The destructor and mclear() both release all books and empty the map, which remains usable after mclear() is called, which returns the map to the same empty state existing just after construction.
The number of books now in the map is msize().
Api details for printing boilerplate above and below are shown in out and quote demos; sample use appears in other demos.
yBqm.cpp «
Non-inline methods for yBqm appear below.
The constructor needs a heap from which to allocate books and pages. But nothing is allocated until a book is requested via mnewB().
The destructor releases all resources.
Clearing the map destroys two separate lists. The list of books in m_le is popped, clearing each elem inside, which releases all the books. Note instances of yBqme are not deallocated because they were allocated from pages stored in the other list, m_Pq, holding all pages allocated.
If not already previously initialized, _minit() allocs the first zero page for a m_epp hashmap consisting of all empty buckets.
When a new member is added, _mnew() allocs a yBqme element to hold the new book node, trying to alloc sizeof(yBqme) bytes from the last page put in m_vH using yv::vtake(), which is essentially just allocation by pointer bumping. Failing that, a new page is allocated from m_Pq, which holds the page node in a handle for later release.
Finally, provided an elem was allocated, _mnew() calls placement operator new() which returns the pointer passed and calls the constructor on this space. This use of placement operator new() is just the C++ way to call a constructor by name on heap space.
Allocating a new book with mnewB() is straight forward. First _mnew() allocates a new yBqme with a handle that can ref a new book node once allocated. If this succeeds, a book is allocated from the heap.
If both those succeed, the new elem is appended to list of elements m_le and pushed on the top of the map bucket to which the book address hashes. The hash of a book here is the book's own address. For an explanation why this might be expected to work very well, see the hash demo — particularly the final identity hash section, which suggests very few collisions for naked book addresses are expected.
Method mfindB() looks for the book in the map as cheaply as possible, using the same hash employed by mnewB(). Expected elapsed time in mfindB() must be very small because it will be called many times during garbage collection. The code in mfindB() will be used in the center of a tight loop, so cost must be minimized.
Output from this sample code appears in the next section. This merely creates stack instances of yPBH and yBqm, allocates two pages from the latter, and prints each before and after.
Each output link in code above takes you to a corresponding stdout section below.
The following edited output appears on stdout — long lines were broken to fit this column. The extra line break is shown as one ¬ character. Note this understandably looks much more cluttered than a single-line original.
One hundred lines were removed from the final heap dump output as annotated in red. (You won't miss them.)
demos « Þ
+ 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