Þ   briarpig  » thorn  » demos  » list

     Although Wil usually avoids lists in contexts where scaling and speed matter, sometimes they can't be avoided. Also, sometimes a list is the simplist solution in a non-scaling context. Wil prefers a circular doubly-linked list with simple edge conditions: hard to get wrong and easy to review by eye.

     This column focuses on code for very basic doubly-linked lists. General discussion of context, design, and performance appear column right, following definitions of more list classes.

     Code for all iterators appears in the iter demo. Iterators all have names ending with p for pointer because þ iterators act like pointers. But a class is not an iterator when p appears in the middle of a class name — this usually means just pointer in the sense of void*. (But a few exceptions append a further qualification at the end of iterator names.)

     Extremely verbose template classes appear separately at the bottom of the right column, and in the iter demo. You can skip them if templates look horrific to you (which seems reasonable). Wil provides them mainly as raw material to derive more specific replacements for template code needing a refactor. Templates are only marginally tested since Wil uses them rarely.

     Most list class names contain either q for queue or l for list. Class names ending in e for element are members that go inside a list. Class names ending in p for pointer are iterators, but p in the middle usually just means an address pointer is part of element content. A class name containing a literal lowercase t for template is usually a template type.

• q - queue: primitive list
• l - list: higher level list
• e - element: list member
• p - pointer: iterator or address pointer
• r - reverse: a back-to-front iterator
• k - const: immutable; a const iterator
• 32 - 32-bit: has 32-bit length inside
• t - template: template version

     So yqe is the base queue element: a node with next and previous pointers to successor and predecessor elements. Base queue yq contains one yqe element as the head sentinel element, which is not content. In general, any class name of the form yqTe is a subclass of yqe containing T as content of the list element. For example, yqpe contains a void* pointer. You might be tempted to confuse this with yqp which is yq's forward iterator. The reverse iterator is named yrqp.

     In day job rewrites of yqe using friendly names, Wil uses link or ln most often as part of the class name. State for next and prev pointers to successor and predecessor links is held in members e_n and e_p. You should memorize the names of those members.

     Wil most often uses epop() and ezero() to remove a link element from its containing yq list and set the members to zero. In general, Wil doesn't zero elem links on queue removal, so you need to do it explicitly when you want to an invariant like "non-member means zero pointers, and vice versa." It's safer to zero when no longer used, but not required.

     When an operation resembles one in STL interfaces, Wil tries to use the same name, at least in a synonym method. But the idea is to borrow familiarity with STL names to reduce documentation; it's not to borrow STL definitions. Instead, you are expected to memorize the code in methods above, because they are defined to do exactly what appears in the inlines, which is one of the reasons all methods are inlines here.

     In queue elem class yqe the code is the documentation.

     The self referential empty constructor must do the same thing as ecycle() because yq's empty constructor requires it (cf »).

     The following yqe subclasses are typical uses appearing in other demos. For example, yqve is used by some heap subclasses to manage lists of memory blocks in run format.

     A basic idea behind yqe subclasses is that declaring new ones is trivial and sufficiently clear that little explanation is needed. Template subclass yqte is quite similar (used mainly by template lists).

     Template queue yqt using yqte elements is shown bottom right (cf »); associated iterators appear in the iter demo.

     Wil usually puts name deque for double ended queue in class names for yq when using longer code names. Letter q for queue implies a more primitve api, while l for list sometimes distinguishes a higher level api. (List yl32 automatically counts length.)

     The only yq state is sentinel element q_e whose members point at the first and last list members. When q_e points at itself, the queue is empty. Construction self-cycles q_e become empty. List linkage is always terminated by the address of q_e.

     The empty constructor makes the sentinel q_e point at itself. Zero pointers in q_e is never valid.

     Method qclear() makes the list empty again. But note this frees no space used by former members of the list. You need to reclaim space for elements however your usage requires.

     The STL style interation api shown above appears in the iter demo. (It's very straight forward.) You aren't required to use this iteration api; you can simply call methods below directly. An STL style api is only useful when updating old code using STL, when you want to avoid significant logic change.

     The following methods have no direct STL analog, except for qsize() returning list length. The implementation of each (further below) gives more explanation. The qpop_front() and qpop_back() are similar to STL methods; but they combine getting with popping in one method, when STL doesn't.

     Note how the return value of type yqe* implies a downcast will be required in normal use with these methods, to convert from base class yqe to the actual subclass you used.

     Method qlencmp() is more efficient than qsize() when you want to compare actual size to a specific value: qlencmp() only iterates over as many members as it takes to answer the question. For example, if a list contains ten thousand members, and you want to know if length is over two, qlencmp() need only look at three members to answer definitively. So when minLen is a small constant, qlencmp() is always constant time.

     When the queue is empty, the first member is the sentinel element, and qempty() returns true:

     To iterate forwards over yq, just use qfront() and qafter() like this bit of sample code:

     To iterate backwards over yq, just do the same thing using qback() and qbefore(). Nil is returned when the queue is empty, or when no more elements follow the current one.

     Pushing a new element on the queue front is shown next. The same code works whether or not the queue is empty. The ascii diagram aims to help you review the code for correctness. (Letter h for head in the figure refers to the q_e sentinel.)

     Method qmove_to_front() assumes argument old is in the queue, removes it, then pushes it back on the front.

     The following methods are just like those above, but targeting the back of the queue instead of the front.

     Now let's look at non-inline methods defined in yq.cpp:

     Note neither qpop_front() nor qpop_back() zeroes pointers in removed elems. Use yqe::ezero() if you need them zero.

     Method qat(i) returns the member at index i, else nil:

     Method qfind(e) returns the zero-based index of element e, else negative when not found:

     Queue size is calculated by walking all list elements:

     Comparing size to input length n requires seeing no more than n+1 elements:

     Method qswap() exchanges all content in two queues. This sort of action is sometimes quite helpful when element ownership in two queues can be exchanged without any net change in, for example, refcounting of elements. (This code is untested.)

     Wil's concern about list speed is mostly constrained to C++ contexts. Wil doesn't worry about the same things when coding in Lisp. But this is mainly because Wil plans to do performance intensive code in C++; a little extra cost in Lisp or Smalltalk matters not if gigantic data structures in high frequency use are in C and C++.

     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.

     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.

     Lists below extend yq by adding a list length, but yq32 does so only by adding a 32-bit q_n length member, without giving you any help maintaining the length beyond providing increment and decrement operators. Sometimes this might be just what you need.

     In contrast, list yl32 maintains the new q_n length member for you, as a side effect of using other methods. To ensure you cannot manipulate the raw yq directly, yl32 has-a private yq as a member variable, instead of inheriting publically from yq the way yq32 does.

     In more complex þ classes using lists, Wil uses a plain yq when length is seldom useful, but prefers yl32 instead when he either needs a length or wants one for stats or printed representations.

     All yl32 methods are inlines calling yq's api to change list members, adding only the maintenance of length q_n. Any yq method re-exposed by yl32 has a name replacing the leading q with l.

     Length q_n is only lowered by inline _ldown() below. Its main purpose is complaining on underflow. Since _ldown() is only called when an element is removed, the length must be nonzero. But if zero, the length must be garbled, so it's recomputed by walking the list.

     When the list hits empty — as evidenced by popping nil instead of an element — _lnone() checks for a nonzero length and then forces length to zero for good measure.

     All methods popping a member element call _less() which either calls _ldown() or _lnone() since one must be suitable. (Wil assumes lightly nested inline methods are just as efficient as no use of inlines at all, so the purpose of _less() is maximum clarity in pop methods.)

     The public api closely follows that of yq while maintaining the new q_n length field. Note clearing a list just makes the list empty; it doesn't free any of the elements, or even unlink them from one another. So presumably you have those bases covered another way. Just remember yl32 doesn't handle space ownership — you do.

     When you remove an element from the list using erase, you must call lerase() rather than calling yqe::eerase() on the element directly — as you would with plain yq lists — or otherwise length q_n won't be maintained. (This is a hole in the yl32 api created by yqe.)

     All pop methods above obviously have identical effect to yq methods, but _less() peeks at the nil or non-nil value in passing to either decrement length or force length to zero.

     The push methods are too trivial for comment as you can see. However, note these are the last methods changing queue length — methods below have no net change on length.

     Construction makes an empty list; destruction does nothing — if you need element resource cleanup, do it yourself (presumably by emptying the list early in some larger object's destructor).

     The begin and end methods below provide an STL style interation api that's described in the iter demo instead of here.

     All other methods below are just thin inline shells atop yq methods because length doesn't change.

     Since length is maintained in q_n, we can get length direct without walking the list. However, if you did want to call the yq methods, those are exposed too. (For example, maybe you want to assert lsize() is equal to lqsize() — who knows.)

     Though lswap() doesn't change net combined length of both lists, it does exchange the length of each with the other in addition to swapping queues. (This one's not quite as thin.)

     "Do you use yl32 or it's equivalent in day jobs?" Stu asked.

     "No," Wil replied. "Usually just clones of yqe and yq. Less novelty is usually better when folks are already queasy over not using STL."

     "Why do they let you use your own code?" Stu wondered.

     "Because where I do, the fastest thing with least overhead is needed," Wil explained. "Usually lists with intrinsic links are called for, without any allocation from a heap to add elements."

     Wil wasn't finished. "I also use multiple inheritance of yqe in objects I need to add to multiple lists. Let me show you how that works."

     Occasionally objects need to be member elements in multiple queues, so Wil inherits yqe multiple times via intermediary classes inheriting yqe once apiece only. Before more explanation, an example might help. Let's look at inheriting twice only, though three times is often common in caches of some sorts, like file i/o page caches.

     Suppose you have a Node type that sometimes must be seen as a Foo in a list of Foos, and sometimes must be seen as Bar in a list of Bars. Wil handles that case like this:

     Pushing a Node into a yq list of Bar elements looks like this:

     Popping a Node from a yq list of Bar elements looks like this:

     This works because casting to and from Bar* each time says which path in the inheritance graph to use. And that's the reason to use intermediary subclasses when inheriting from yqe more than once: to name each path in the graph with a different type.

     Of course the pushFoo() and popFoo() methods look exactly the same but with Foo substituted for Bar everywhere.

     In Wil's suite of list classes, one ugly part is incremental addition of features: a little at a time in small feature upgrades. For example, the base list doesn't count members as superfluous cost to any user who doesn't need a list size. When it comes to primitive data structures, Wil prefers more classes with carefully separated feature accumulation, because this minimizes coupling of what you want and what's forced on you by packaging. The downside of this? Wil has too many class names.

     Doubly-linked circular lists have become less useful in recent years as the penalty for cache line misses has gone up. A list operation touching both next and previous list members — and the target member — ends up touching at least three different cache lines in memory, on average, for a very large number of list members with no expected locality of adjacent list members. For example, this is what's expected with LRU (least recently used) lists of objects, which can approximate random member order in a list. In a server under memory pressure, touching many cache lines is expensive compared to any solution touching fewer.

     In some cases, such as LRU lists, this is unavoidable. If a list usage often pops a member at any position then re-pushes at one end or another, then using a doubly-linked circular list doesn't have a better alternative touching fewer cache lines. You'll just have to to it; so there's no use in worrying over how many cache lines you touch.

     But other uses of doubly-linked circular lists might not have this requirement. You might get by with a singly linked list and still have all constant time operations. In this case you pay a penalty in extra cache lines touched when using lists on this page. In a performance bottleneck you might not be able to afford this choice. However, lists on this page are rather simple, so it's quite easy to use them until you have a reason not to do so anymore. That's how Wil plays it.

     Wil used to employ doubly-linked circular lists in hashmap buckets to chain collisions in open hash style (meaning a bucket it open to further additions). But that costs too much in cache lines touched now. Closed hashing with probing to resolve collisions now rules the day, typically touching only one cache line per table probe. (See the tombstones page for a look at good closed hashing style.)

     However, in subclasses of heap apis managing pages and books, Wil still uses linked lists in hashmap buckets, primarily because this is just simpler than alternatives and because page and book allocation is not a main cause of memory pressure for cache lines. (At least not so far.) And until toy language implementations have nothing better to do than improve marginal performance issues, Wil pursues simplicity.

     Lists are easy. They're so easy, many folks think the most important thing is to use a standard list: rolling your own and re-inventing the wheel is a huge hit on style points. Wil agrees using a standard tool is fine when results are not critical.

     But when you're on the hook to make a system scale without risks, Wil thinks you're crazy to use any code you haven't personally vetted and isolated so it's under your control. If you put lists in central components affecting success of your system, it's madness not to have them under your thumb: you could not rule out hidden factors causing odd system behavior. (Axiomatically, all complex systems have odd behavior which you must diagnose.)

     So in some cases you must write your own lists, or adopt someone else's which you review as carefully as writing them from scratch. This is how you create an option to ensure you know exactly what's happening, all the time. A common api allowing fast swapping between your lists and standard replacements is great; substitution is good experimental technique.

     A motto "trust no one" works when it's your skin at stake. Trust standard replacements when you can test whether they act identical to your own tools. Standard tools typically aim for universal use, but "one-size-fits-all" is rarely a perfect fit. Generic memory use can expose you to risks, or deny efficient options; critical infrastructure often needs static allocation.

     Wil's been using the variant of doubly-linked circular lists shown earlier for almost twenty years. It's been rewritten in C and C++ several different times; however, nothing besides the names have changed. The model for code roughly imitates how VAX queue instructions do circular lists: using a sentinel node as a list head, where the sentinel points at itself fore and aft when the list is empty. This manner of list avoids special cases in adding and removing list members, avoiding branches and taking fewer instructions — efficient but for touching many cache lines.

     The majority of code associated with template yqt<T> is actually in the iterators, which appear in the future iter demo. The following code hasn't been tested. This is just a draft Wil wrote for thinking purposes.

     All template methods are inlines, as normal with templates.

     Unlike all other list classes on this page, yqt<T> does manage ownership of space for elements added as members, to more closely resemble the STL api of std::list<T>. The allocator is a heap using an api described in the (future) heap demo.