Whether or not virtual memory is a factor in some app or system, Wil often uses page buffers as one granularity of heap allocation, for several reasons:
- aligned with virtual memory page costs
- uniform memory re-use cuts fragmentation
- cheap page containment tests for pointers
- better scaling under VM page pressure
Under þ, pages are allocated by the yPBH heap api shown in the pile demo. The page allocation api strongly resembles the api for yB book allocation. The two yPBH methods involved — hPn() and hcPn() — both allocate nodes and are shown below.
yPBH heap «
The actual heap for page allocation is shown in the (future) pile demo. It subclasses the basic yH heap interface:
Class yPn is defined further below on this page (cf »).
The hPn() and hcPn() methods each pass a yht<yPn> handle argument, receiving a first ref to a returned yPn page node whose npage() inline method returns the yP page.
The yP api shown next mainly defines a physical format as size in bytes, plus a bunch of convenience methods using that page of bytes. The yPn page node api further below (cf ») shows details for the node api; the page remains allocated as long as its yPn node is still in at least one handle. A yPq page queue api shown later on this page (cf ») is a good place to hold page nodes. Hashmaps shown in the right column use yPq to own pages used in maps.
In most operating systems with virtual memory, a page is the unit size of paging (yes: sounds tautological) content between memory and secondary storage. Typically pages are 4K in size, but some systems use 8K, etc. In fact, you can't easily presume anything about page size in totally portable code. But material below pretends pages are always 4K in size.
An important feature of pages is alignment: each page starts at an address that's a multiple of page size in bytes.
struct yP «
The api for yP pages is quite simple. The state is just a contiguous sequence of aligned bytes.
Note a page might actually be another size: kPsz might instead be 8192 on systems using 8K pages. Code comments and docs typically say 4K, as if it could not change, but the actual size of a page is whatever kPsz says. Usually it's 4K — or 0x1000 in hex, so page-aligned addresses are zero in the low three hex digits.
Constants above are used in bit masks: klow=0xfff selects bits of an address inside a page, and kmask=0xfffff000 selects the page that contains an address, in 32-bits.
Array P_u8[] is the array of bytes inside a page. This is the only state inside a page: the address of P_u8 is the same as the address of yP. By convention each page address is page-aligned, so not just any yP instance is valid: only those allocated at an address that's a multiple of kPsz.
Nothing stops you from delcaring a yP anywhere you like, say at a non-aligned address. But any page allocated by yPBH will be aligned, and many yP users assert Pgood() below is true.
When Pgood() is false, you can log this using Pbad():
Method p2P converts any p pointer to the yP page containing that address. This is just a matter of zeroing low bits:
Method Pzero() safely clears a page to zero:
Or Pmemset() can set all bytes to some other value:
Method Phash() returns a hash of a page's address with fewer hashmap collisions expected, using a pseudo random number generator from the rand demo:
Most yP methods are inlines, because dealing with a fix-sized format with alignment isn't complex.
yP.cpp «
Non-inline page methods appear below. Method Pcopy() copies a source page to this page:
Method Pbad() logs when a page does not look good; printing a backtrace here also would help:
Memory management of pages is done by refcounted yPn page nodes below. Under þ, pages are allocated by yPBH heaps.
class yPn «
Each þ yP page allocated by yPBH is refcounted using a node subclass named yPn, whose name naturally means thorn Page node. Each yP has a one-to-one correspondence with exactly one yPn node, and the source yPBH heap allocates both.
When refs hit zero as the last handle loses the final ref to a page node, both page and node are deallocated, returning the page to a free list in the yPBH heap.
Currently sizeof(yPn)=40 so memory management overhead for a page is forty bytes — near one percent — plus any additional bytes used to track the handle, which could run twenty more bytes. This overhead is quite moderate, especially when a page is later suballocated with high efficiency, avoiding further per-block overhead for objects allocated from a page.
The yht handle template is described at length in the node demo, and here we see yPnh is a synonym for yht<yPn> whose name means thorn Page node handle.
When the last handle with a ref to the same yPn page node loses that reference (so count of refs go to zero) the yPn node is freed, returning the yP page to a heap free pool.
Class yPn 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 page.
The first two new state members n_H and n_P track the heap and actual page 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 page 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 page is allocated.
One byte magic signature n_ty says this node's type had better always be 'P' for page. This can be asserted when casting yn* to yPn*: it's a dynamic type tag.
The last one byte n_fuh member indicates whether a page 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 are public, and neither are any of the constructors below. So how can you construct a yPn page node instance? You can't. Only yPBH heaps can construct a page node — so yPBH is a factory for yPn page nodes. You can see the api to alloc a new yPn instance at the top of this page (cf «).
The getters shown below are all public. Some of them must return constant values when a page node is allocated. (But yPBH works with page 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 page 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 page yourself.
Method npage() returns the node's page — this is the main method in the entire api. When given a page node, you should mainly be concerned with the page. Well, here it is:
The following getters and conversion operators return the page as a run, buf, or iovec. You can easily do this yourself; but by using these methods, you might avoid mistakes.
Pmemset() lets you call a page 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 P2iovec() 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.
yPn.cpp «
Non-inline page 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 pages is still pending, but it's — you guessed it — trivial as always).
Method nout() writes the entire page.
Virtual n2iovec() converts to iovec the same way P2iovec() and asiovec() inlines do.
Cloning is easy using yPBH::hPn() and yP::Pcopy(). (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 Pnbad() must log problem descriptions.
The next section shows how yPn page nodes can be owned by lists based on primitive yq queues from the list demo.
The name of class yPq means thorn Page queue. It uses primitive queues based on yq in the list demo to manage a set of yPn page nodes. So far its main purpose in practical use has been simple page node ownership for allocated pages.
In effect, you just call qnewP() to say "give me a new yP page" which gets allocated from a yPBH heap. Then you use the yP page however you please, safe in knowledge this new page remains allocated by means of its node held by a yPnh handle within yPq. When a yPq list is destroyed, all pages are released at once. As a result, yPq acts a bit like a RAII guard for as many pages as you want to allocate for some purpose.
Page-based hashmaps shown column right use yPq for exactly this purpose, allocating pages from yPq, then using them without paying any attention to memory management because yPq handles that. This coding style gets leverage through composition, using other objects for narrow effects.
This version of yPq is slightly too primitive to be most efficient in touching memory, because it allocs list elements one at a time, instead of many at once at once in a bigger block. Using a page for this purpose seemed too high of overhead for short page lists. A simple variation of yPq was almost added to this demo to show better memory style, but it was omitted for brevity. (But a new 1K kilo object added to yPBH's api would work for this purpose.)
class yPq «
This queue of pages is mainly a shallow api to manage the two first state member variables, q_H and q_le shown below:
Queue heap q_H is the source of all pages allocated, and q_le is the list of elements holding a yPn page node for each page allocated. Elements in q_le are type yqnhe shown in the node demo (cf «). Since list elems are not exposed publically, generic node handle element yqnhe was used instead of a handle elem specfic to yPn page nodes.
Method qnewP() adds a new page to the list and returns it, while qclear() empties the list completely, freeing every page previously allocated. Obviously you can only safely call qclear() when you will not use pages allocated earlier again.
Method qsize() returns list length: a page count.
The constructor needs a source heap and the destructor releases all pages by calling qclear().
Api just above and below is typical printing api boilerplate similar in style to all other printing methods in þ — please see out and quote demos for detail.
yPq.cpp «
Non-inline yPq methods appear below. Some of this might make more sense after you read list and iter demos.
The list starts out empty: zero pages inside.
Destruction releases all pages in the list.
Above is Wil's original comment on yPq's use of individually allocated list elements. It summarizes a weird effect you would see if yPq allocated a page and then put a list handle element inside that page holding the ref to the page's node. Sometimes that sort of thing is perfectly reasonable, even if it makes you feel slightly queasy. Wil decided to do the simple thing instead, appearing in the version shown below.
Above you see one yqnhe list elem allocated first, then a yPn page node to go inside. Here the elem is made to ref the new node by assigning it to handle e_hn in the elem. (Follow the link to see a definition.) This causes one extra ref to be added by e_hn, followed by one released ref in first when method qnewP() exits. It would be more efficient to use inline e_hn.hswap(first) to exchange the ref in first with the nil pointer in e_hn, without a more costly net zero change caused by going up and then down again.
But even better, e_hn can just be passed to hPn() in the first place to receive a first reference. Temp handle first isn't even needed since e_hn is both around already, and exactly where we want the ref to land. Is this clear to you?
Wil almost changed the code now to remove first and pass e_hn directly to hPn(), but it seemed more educational to leave it like this and include the full explanation so you can think about optimization. Not all equivalent code is equally fast.
Note code in qclear() must exactly match memory management in qnewP() shown above, but in reverse. Because each list elem was allocating in the q_H heap, it must be used to free every elem popped from the list.
The ~yqnhe() destructor called here explicitly would have done the same thing as qnheclear() which does it early: releasing the node from the e_nh handle in the elem. Each page is released, so it goes back to the heap, since presumably there are no other refs to nodes in this q_le list.
Here's another gratuitous use of queue iterator api from the iter demo. Operators used above link to the code.
Several years ago Wil wrote part of a buffering system for a server, and was told "don't worry, paging will never happen" because there would always be enough physical memory.
"Are you sure?" Wil asked. "Because I'd be a lot more careful about alignment and locality if paging might occur." Wil was kinda hoping he'd be allowed to align buffers anyway, but buffer allocation was given as a task to a junior engineer. (Wil avoids meddling.)
A couple years later the product was tested by a customer who used far less physical memory than logical address space — so paging was heavy: the server suffered and did interesting things.
In absence of careful new request throttling, it seemed the server strongly preferred to give priority to new requests rather than finish processing old requests. As a result, the address space footprint kept growing — aggravating the paging even further.
When told about it, Wil noted the observed behavior made sense: new requests were chewing up virgin address space with higher locality in new buffers allocated contiguously, thus giving new request content high memory locality despite no page alignment.
In contrast, older requests used buffers allocated earlier in time, popped from free lists, and totally lacking in page alignment. The lack of alignment meant any given page had high probability — on average — of splitting a buffer across pages so each buffer shared a page with another buffer, which would easily be part of another request.
As a result, any request using old buffers was in page contention with other requests since buffers in free lists had random order, or rather the order in which buffers were freed. But new requests allocating buffers in virgin address space had zero contention with other requests, so they won races in ways making the old request queue get bigger.
What's the moral of this story? If folks like your product, it will get used in more contexts until finally it gets deployed under resource pressure. Whether you design for paging or not, it will get used under virtual memory paging pressure eventually. So you might as well accomodate obvious pain points early: align now.
Thus yP pages allocated by yPBH heaps are aligned.
"Can I see a clue to map iterator coding in the right column?" Stu asked. "Remove methods look suggestive."
"Well, the interesting problem of map element removal is outlined in the mremove() methods," Wil granted.
"Let me guess," Stu considered. "An iterator must point to a reference to the current map item in the iteration, so it's possible to unlink it from the current bucket. Am I close?"
"Yes," Wil agreed. "That's how iterating one bucket works. And the iterator can tell if the current element has been removed or not by whether it's already been unlinked."
"So all that's left is iterating over all the buckets," Stu said. "I don't know why you say this is hard."
Wil was chagrined. "When did I say it was hard? Don't I go out of my way to say everything is easy?"
"It gives me the opposite impression," Stu admitted, squinting thoughtfully. "What's wrong with me?"
"You've been hanging out with liars," Wil explained. "Now you suspect everything is crafty misdirection."
"That's just what you want me to believe," Stu accused with a pointing finger while smiling at his joke.
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.
The next two sections below show sample code for page-based hashmaps. The first is ypm for pointer map, which is really a set of pointers because only the keys are represented. And the second is yppm for pointer pair map, which maps a pointer key to a pointer value. Both of them are designed for modest population sizes of no more than several thousands.
A Lisp pretty printer for toy language support (coming soon) first used these hashmaps to track addresses of container objects already seen and already printed, in order to detect circular references (caused by self-embedding) and to detect structure repetition, both of which can be replaced by a citation instead of literal tree representation.
However, Wil eventually realized a more complex map supporting a subtle form of copy-on-write was needed in pretty printing for this purpose, to permit two passes over a data structure — one for sizing one for actually printing — without complex self interference. The fancy copy-on-write map will be shown later in the map demo, because it'll be much longer than code shown below. (The tricky parts of the cow map are somewhat entertaining, and not as trivial as the stuff below despite using simple effects.)
Maps shown below are characteristic of many hashmaps in þ based on fix-sized buffers using pages or books (64K super pages). So the code organization is almost boilerplate for a hashmap that does not resize. (If you add too many members, buckets just get deeper and take linear scans to search.)
The hashmap style shown below is called open hashing because buckets are open to further element additions. Wil sometimes calls this style open/chaining to emphasize collision resolution is via chaining in a bucket list. Wil prefers open/chaining hashmaps when allocating a large static max capacity closed/probing hashmap is not easy to arrange. Lists in an open/chaining hashmap touch more cache lines, but afford a lot of flexibility and gracefully handles overfilling beyond expected size.
(Wil has written at least a hundred different hashmap implementations over the years, to suit complex needs in different languages and varying resource constraints and threading contexts. So writing another one always seems no big deal, which of course leads to more of them. Perhaps after you read a few, they'll all start to look the same. It's hard not to write a few for symbol tables and compilers when writing a programming language.)
The hash method used is very rudimentary, and probably ought to be replaced with Chongo's (Landon Curt Noll's) FNV hash, named after himself and the original two authors, Glenn Fowler and Phong Vo. A hash based on Fowler Noll Vo should be faster than crc32 and might have better collision resistance.
This page will updated later when the hash is replaced. Hmm, looks like a hash demo will appear then to show another embodiment of fnv in a þ api.
The hashmap shown below represents a set of pointers added as members. All storage is allocated by yPq and consists entirely of yP pages. The hashmap's array is a single page, and each entry added to the map is suballocated from another page divvied up into map elems of type ypm::Mpe, where nested class name Mpe means map pointer element. Another hashmap shown further down in this page has very similar structure, but maps pointer key to pointer value. This map effectively maps a pointer to itself or to nil.
class ypm «
Class name ypm means thorn pointer map. Here the pointer type is void*, but the map is easily used for any scalar type whose size is not more than sizeof(void*), so Wil also uses ypm to represent integer sets of type ptrdiff_t. (Actually sizeof(ptrdiff_t) can be more than sizeof(void*) — just not the reverse. But this still doesn't stop Wil from pretending they're the same size.)
Note the minimum footprint of ypm to hold even one pointer member is two pages, or 8K. So only use this ypm when it's not too costly: to hold larger sets or when transiently used. (A more versatile ypm version can start with blocks less than a page.)
The following nested class is the element type:
Nested class Mpe is the map pointer element used to add hashmap members. The key (map member) pointer is stored in e_p, and e_n is just a link to the next elem in the same hashmap bucket, where each bucket is a singly linked list.
The number of buckets is kslots: the largest prime number less than 1024, because one 4096 byte page can hold at most 1024 Mpe* 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 Mpe 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 Mpe elems allocated from m_vH go straight into the m_epp hashmap after construction when new members are added. But any element removed from the hashmap is put into the m_efree element free linked list.
The current number of map members is m_n — this is the map size. Pointer m_nilval is the value returned by the map on any failed search for a pointer member: it defaults to zero, but can be set to any other value if a map might contain zero as a valid member.
Follow links above to code and explanatory comments.
When a removed element is freed, _mpush() pushes it on the top of the free list, which allocates in lifo stack order.
A free element is allocated by _mpop() when the free list is not empty. Obviously m_efree must be initialized to nil.
The number of bytes used by the map is mvol() if we don't count bytes in the remaining m_vH page yet to be allocated.
Insert and delete are done by madd() and mremove(). Re-adding the same pointer is idempotent — once added, adding it again does nothing: it's still a member. The return of mremove() is m_nilval if key p was not a member.
You query map membership with mfind().
The constructor needs an allocating heap and a preferred nil value. Clearing a map removes all members and releases all pages allocated, returning a map to an empty state as if just constructed.
Current member count is msize(). Destroying a map releases all pages allocated.
Api details for printing boilerplate above and below are shown in out and quote demos; sample use appears in other demos.
ypm.cpp «
Non-inline page methods appear below.
The constructor makes an empty map. The first page for m_epp is delayed until a member is added.
Destruction empties the map and releases all pages.
Clearing a map to empty does very little besides free all the pages by clearing the m_Pq list and zeroing m_epp to show lazy init is needed again, just like after construction.
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 Mpe map pointer element to hold the new pointer member. First it tries to pop the free list, then it tries to alloc sizeof(Mpe) 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.
When adding a new member, first lazy init is performed by _minit() if needed. Then the bucket to which the pointer hashes is searched — if found, nothing is done. Otherwise a new elem is allocated (either popped from the free list or constructed in new space) and pushed on the top of the bucket list picked by the search.
Finding an old member looks just like madd() except lazy init is not mandatory, and nothing new is added. If the target pointer is not found, mfind() returns the distinguished nil value passed to the constructor, which defaults to zero.
Removing an old pointer member also looks like madd() and mfind() except instead of letting pp point to the bucket list head, it follows the list traversal down, always pointing at the next element to be examined. If the pointer is found, it's element is unlinked just by updating pp, and then the element is pushed in the free list.
The only slightly interesting part of printing is hashmap scan shown below in _mdump_epp().
The map buckets are printed above with annotation showing the bucket index in the m_epp array so distribution can be seen. When a bucket contains only one elem, the handle inside is printed by itself. Otherwise a list of length over one is printed inside a tag grouping bucket collisions.
The hashmap shown below is extremely similar to ypm shown in the last section, which you ought to study first because fewer comments will be given below.
Once again, all storage is allocated by yPq and consists entirely of yP pages. The hashmap's array is a single page, and each entry added to the map is suballocated from another page divvied up into map elems of type ypm::Mkve, where nested class name Mkve means map key value element. Each member is a pair (key, val) of pointers.
class yppm «
Class name yppm means thorn pointer pair map (or more literally: pointer pointer map). As before in ypm, the pointer type is void*, but the map is easily used for any scalar type whose size is not more than sizeof(void*).
Nested class Mkve is the key/value pair element used to add map members. The key pointer is e_key, the value is e_key, and once again e_n is just a link to the next elem in the same hashmap bucket, where each bucket is a singly linked list.
Just as in ypm shown earlier, the definition assumes a page is 4K in size and that pointers are 32-bit, so a page can contain at most 1024 pointers. The map has kslots buckets because 1021 is the biggest prime under 1024 — primes are good hashmap sizes.
All state members have the same meaning as those in ypm shown earlier, except the elem type is Mkve:
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 Mkve 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 Mkve elems allocated from m_vH go straight into the m_epp hashmap after construction when new members are added. But any element removed from the hashmap is put into the m_efree element free linked list.
The current number of map members is m_n — this is the map size. Pointer m_nilval is the value returned by the map on any failed search for a pointer member: it defaults to zero, but can be set to any other value if a map might contain zero as a valid member.
Freed elems are pushed on the free list by _mpush().
Old free elems are allocated when _mpop() pops the free list.
As in yom, and delete are done by madd() and mremove(). But now adding the same key twice is not idempotent because the value can change. If madd() updates an old pair, the old value is returned; otherwise the distinguished nil value is returned.
The constructor needs an allocating heap and distiguished nil value defaulting to zero. Clearing a heap makes it empty as if just constructed.
A count of current map members is returned by msize(). Destruction empties the map and releases all pages.
Printing boilerplate above and below are shown in out and quote demos; sample use appears in other demos.
yppm.cpp «
Non-inline page methods appear below.
The constructor makes an empty map. The first page for m_epp is delayed until a member is added.
Clearing a map to empty does little besides free all pages by clearing the m_Pq list and zeroing m_epp to show lazy init is needed again, as after construction.
If not done already, _minit() allocs a first zero page for a m_epp map consisting of all empty buckets.
When a new member is added, _mnew() allocs a Mkve map pointer element to hold the new pointer member. First it tries to pop the free list, then it tries to alloc sizeof(Mkve) 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.
All remaining yppm methods are nearly identical to ypm methods shown in the last section, except all the elems are Mkve pairs instead of Mpe single pointer keys.
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