The Rationale of the HadronZoo Collection Class Templates

The HadronZoo C++ Class Library includes two groups of basic collection class templates: Unordered and ordered. In an unordered collection, objects are in the order they were added. In an ordered collection, objects are ordered by value or by some other criteria, as directed by the calling program. The HadronZoo collection class templates are as follows:-

Note that the template arguments are either named 'OBJ' or 'KEY'. Both can be any legal data type or pre-defined class but by convention, the argument which determines the order of the collection is named KEY. The name OBJ is used in all other cases.

Mainly on the anticipation of small collection size, the unordered collections are constructed as completely self-contained entities. The ordered collections which are often large, are all based on _hz_tmpl_ISAM, an internal ISAM class specifically designed to support large collections. This class is defined in hzIsamT.h and implemented in hzIsamT.cpp

Low Memory Overhead

All of the above templates have direct counterparts in the Standard Template Library (STL), so why did HadronZoo develop its own variants? The main reason was space efficiency. The intention for the ordered collections at least, was for them to store millions of objects for runtime duration in omnipresent server programs. The STL implementations had overheads that in the target environment if not the general case, could be improved upon.

The ordered collections currently have 8 elements per data node and 24 pointers per index node. In the forthcoming version, both data and index nodes will contain a variable number of 'buckets'. The idea behind this is to increase both node size and effective node occupancy, thereby further lowering overheads.

Smart Pointer/Copy Restrictions

Another reason for developing the HadronZoo collection class templates, was to restrict copying. HadronZoo considers memory resident hard copies of anything other than small, fixed sized entities such as integers, to be highly undesirable. In particular, there appears to be no grounds whatsoever for hard copying memory resident collections. Indeed, no grounds even for soft copying such entities. It should suffice to pass a reference to a collection. Accordingly, HadronZoo collection class templates suppress copying by having their copy constructors and assignment operators as private and undefined.

The only exception to this is hzList which can be soft-copied. This exception was allowed because hzList is still used by some classes to hold multiple values or sub-class objects. Such host classes would be uncollectable if the hzList did not allow copying, since the process of adding to or inserting objects into a collection involves assignment.

Collections in a Multi-threaded Environment

For multi-threaded programs to work properly if at all, every program resource that is accessed by more than one thread and written to by at least one, must be protected by a lock. For such programs to work efficiently, the total time spent within locks must be kept to a minimum. There are two ways to acheive this: Firstly, do as little as possible within the lock itself, preferrably nothing other than read from or write to, the protected resource. Nothing that can be done outside the lock, should ever be done within it. Secondly, if at all possible, arrange matters so that contention naturally becomes less likely.

The ordered collections are a good illustration of how contention can become less likely. Threads other than the main program thread, generally have one of two distinct objectives. Either to perform a separate background task such as generate periodic reports, OR to be one of an army of threads, all doing the same thing in order to bring more processing power to bear. In the former case, the thread will access the collection only occasionally and is unlikely to be a major source of contention. In the latter case, the threads will always be trying to read from and write to the collection simultaneously. What such threads are less likely to want to do however, is modify the exact same part of the collection.

Illustration of course, is not the same thing as implementation. With the current version we are still stuck with whole collection locking. This renders background tasks threadsafe but is useless for bringing more processing power to bear. Every collection operation involves a lookup which is of necessity, thousands of machine instructions taking of the order of 1 to 2 microseconds. This is far too long to be done within a lock and with the anticiaped level of contention, could easily cause a multi-threaded program run much slower than an equivelent single-threaded program.

Locking individual nodes in the _hz_tmpl_ISAM class is the easy part. It is achieved by building a new version of the target node in isolation, then setting a pointer to switch the new node in. With this method, threads can read nodes without seeking a lock but must seek a lock if writing. With collections however, there are two possible types of contention. Not only may multiple thread seek to write to the collection at the same time, but they may be seeking to add the exact same entity. To prevent this we are adding an extra step to the process. Threads seeking to write to the collection will first write to a 'register of intent'. If the exact same intent is already registered by another thread, the collection operation returns success without actually doing anything. This will appear in the next version.