Hidden treasure in the D standard library

Posted on 28th August 2014 by Gary Willoughby

I’ve been using D for a number of years and I am constantly surprised by the hidden treasure I find in the standard library. I guess the reason for my surprise is that i’ve never exhaustively read the entire library documentation, I only skim it for what’s needed at any given time. I’ve promised myself I will read it thoroughly one day but until then i’ll enjoy these little discoveries. This article highlights a few of these hidden treasures which I hope you’ll enjoy learning about and will be useful for your future D projects.

std.functional

This module implements functions that manipulate other functions. I guess this is where D implements library functions to accommodate some aspects of functional programming. It’s a bit thin on the ground in there but what is there seems to be very useful.

memoize

Memoization is an optimization technique used primarily to speed up computer programs by caching the results of expensive function calls and returning the cached result when the same inputs occur again. This template, available in the standard library does just that.

The following is a simple program to display numbers of the Fibonacci sequence by using a recursive function. This is not the most optimised way of calculating this sequence but for the purposes of a memoization demonstration it will do.

If I run this on my computer it finishes in about 13 seconds, which is not great. That’s because it’s recalculating values every time it’s run. Using the memoize template we can cache the values instead of recalculating them again. This caching assumes that for any given valid arguments the function will return the exact same result. Here is the memoized version.

Internally in fib the recursive calls are now being made to the memoized version mfib. When the memoized version is called, it first checks its cache and if a value exists for that particular combination of arguments the cached value is returned avoiding any recalculation. This can save an enormous amount of computation time but with the overhead of maintaining a simple cache. If I run this new program using the memoized function, the execution time is dramatically shortened to only a fraction of a second.

The memoization cache is implemented as a simple associative array keyed on the types and values of the passed arguments. The cache element size can be limited by passing a second argument to the memoize template. View documentation.

std.parallelism

This module implements high-level primitives for SMP parallelism. These include parallel foreach, parallel reduce, parallel eager map, pipelining and future/promise parallelism. This module is recommended when the same operation is to be executed in parallel on different data, or when a function is to be executed in a background thread and its result returned to a well-defined main thread.

parallel

This is actually a convenience function that forwards to taskPool.parallel (which resides in the same module), the purpose of which is to create a parallel foreach loop. Parallelizing a foreach loop means that potentially each iteration can be run asynchronously across different threads. In reality, the parallel function allows you more fine grained control by adjusting how many range elements are allocated to separate threads in the form of tasks. These tasks contain a consecutive section of the iterated range and passes it to a thread for processing. Here’s an example of something that would benefit from being calculated in parallel.

Again we’re using our hideously inefficient fibonacci sequence generator to populate elements of an array. When run this program takes about 13 seconds to complete on my computer and it only uses one thread (on one CPU core).

To parallelize the loop we simply use the parallel function, like this.

Notice the second argument to parallel? that’s the number of work units (i.e. consecutive elements to pass to each thread for processing). I’ve set it to 1 to indicate I want each element to be run independently in its own thread. Smaller work units provide better load balancing, but larger work units avoid the overhead of communicating with other threads. The less time a single iteration of the loop takes, the larger work unit should be. For very expensive loop bodies, the unit size should be 1.

Now that the above loop is parallelized and each element is processed in it’s own thread, the execution time is slashed to 5 seconds. The program now uses multiple threads (and all four CPU cores) on my computer. View documentation.

std.random

This module implements facilities for random number generation.

dice

This function provides a way of generating random numbers using weighting. Take a look at this example.

Here the random number generated by dice will be in the range defined by 0 and the maximum index of the passed weight i.e. it will be between 0 and 2 as there are only three weighted elements. The weights themselves (element values) act as percentages, causing the different indexes to be returned with more or less frequency than others. In this particular example, 0 will be returned seventy percent of the time, 1 twenty percent and 2 ten percent of the time.

I’ve yet to think of a use case for this little function but it seems like it could be really useful and deserves a little light shedding on it. View documentation.

std.typecons

This module implements a variety of type constructors, i.e., templates that allow construction of new, useful general-purpose types.

Flag

This template defines a simple, self-documenting yes/no flag. This makes it easy for APIs to define functions accepting flags without resorting to boolean values (which are opaque in calls) and without needing to define a separate enumerated type. There is nothing worse when working on code to open up a file and see code like this.

What exactly do the three boolean arguments mean? They mean you have to look at the definition of this method to understand their meaning, doh! D introduced flags to avoid this nuisance by documenting the meaning of the flag at the call site. Here’s how they work.

Notice that the second parameter of the foo function is a flag. The flag’s string defines its meaning much like a variable. Usually a parameter like this would be defined as a boolean value but using flags we can make it easier to understand. As a bonus, the flag can be tested in the same way as you would a boolean value. One further treat is that because the Flag syntax is a little too verbose for the call site there are a couple of helper structs to make the call look a little more presentable. Using these, the above function could be called like this.

Don’t you agree this is much nicer than having to guess what boolean arguments mean? View documentation.

Proxy

This is an extremely handy mixin template for injecting code into a class or struct to make it behave like another type. Doing this manually is quite time consuming and involves a lot of operator overloading, whereas Proxy is a simple one liner that enables lots of automatic functionality.

Here’s an example where I make the struct Foo behave as an integral type.

Notice that all the operators in the above example just work? Here’s another slightly more complicated example using an inner string array.

In this example i’m accessing the inner array via concatenation, iteration, indexing and using it as a function parameter. Using this mixin is great for quickly creating user defined collections. Proxy overloads all the necessary operators making sure the outer type can be used wherever the inner type would be expected. The only functionality that isn’t supported is implicit conversions to the inner type, which is by design. View documentation.

RefCounted

This struct is a wrapper for creating reference counted objects. The wrapped type is automatically allocated using malloc and the struct keeps track of all references to it. When the reference count reaches zero (meaning all references to it are destroyed) it is freed using free. Here’s an example.

Creating reference counted objects is desirable if you are trying to keep reliance on the garbage collector to a minimum and you want make sure objects are destroyed as soon as they have no more references to them. This makes sure you can easily define when objects are deallocated.

There are a few words of warning here though. It doesn’t work with classes and it’s currently considered unsafe and should be used with care. i.e. No references to the payload should be escaped outside the object or you’re defeating the object (pardon the pun) of using it. With that said I still think it’s pretty cool and valuable. View documentation.

scoped

This is another nice addition for those who like to control what goes where in memory. Unlike RefCounted which can’t be used with classes, scope exists purely to cater for them. The idea behind this template is to avoid the reliance on the new keyword and the automatic allocation of classes on the garbage collected heap. Instead it instantiates a class in the current scope and on the stack. Here’s an example.

Here foo is allocated on the stack and used just like any other instantiated object. The effect of the scoped template is that the object will immediately be destroyed upon leaving the scope it was created in. This provides what is know as deterministic destruction for class based objects and as a result allows idioms such as RAII to be implemented.

As with RefCounted there are a few caveats. It only works with classes and it is also deemed unsafe, i.e. it is the responsibility of the user to not escape a reference to the object outside the scope. View documentation.

Conclusion

D provides an absolute wealth of fantastic features and advanced ideas in the standard library. Featured above are only a few of the treasures to be found. Two of the most amazing modules; std.algorithm and std.range aren’t even mentioned here. Click the links above and read more about each one and see for yourself the appeal and productivity of a modern system programming language such as D.

---