Have Your Efficiency, and Flexibility Too

Metaprogramming Techniques For No-Compromise Code

by Nick Sabalausky

Full source code for this article is available on GitHub, or can be downloaded here.

View this article on a Single Page or Multiple Pages

Table of Contents:

1. Have Your Efficiency, and Flexibility Too
2. First Attempt: Send Efficiency and Flexibility to Dr. Oop's Couples Therapy
3. Respecting the Classics: Old-School Handcrafting
4. Success at Dr. Metaprogramming's Clinic
5. It Walks Like a Duck and Quacks Like a Duck...Kill It!
6. Metaprogramming Plus: The Flexibility Enhancements
   • Method #1: Compile-Time Function Execution
   • Method #2: Compiling at Runtime
   • Method #3: Convert a Runtime Value to Compile-Time
   • Method #4: Dynamic Fallback
7. The Last Remaining Elephant In The Room: Runtime Conversion
   • Conversion Downsides And Possible Fixes
     • Hold It, Gizmo! Quit Squirming Around!
     • Hey Data, Get Back Here!
8. Curtain Call

Just look how the efficiency and flexibility knuckleheads bicker in even the simplest situations. This example is written in the D programming language, but it's the same sad old story in any language:

From ex1_original.d:

Ok, so I guess the fighting between efficiency and flexibility isn't so obvious at a glance. They're making some ordinary-looking Gizmos and nothing seems immediately wrong. There's no fists flying, no colorful primetime-banned language, no headlocks or piledrivers. But you have to look closer: it's passive-aggression. And experts say that's psychologically-damaging, right?

Normally, code like that would be fine, so what's the problem? Well, we don't just have two or three Gizmos collecting dust until a rare special occasion when we decide to pull one out to use it. Oh, no. Gizmos are the main component in the real product: the UltraGiz. The UltraGiz is made of thousands of Gizmos of all different types, and it really gives those Gizmos a big workout. Plus, each port-zapping is fairly quick. The real expense comes from how many port-zaps occur.

So even a small improvement to the Gizmo's size and speed will add up to a big improvement in the UltraGiz. And since many different types of Gizmos are needed, we know we need both efficiency and flexibility.

What flexibility is needed? For one, some Gizmos need to spin, and some don't. But every Gizmo is paying the price for that flexibility: There's always that spinCount variable, even for ones that don't spin. And they all have to take the time to check the isSpinnable variable. Heck, each Gizmo even has to use storage space just to know whether it's spinnable or not. They're not just stamped on the side with "spinny" or "no spinny".

And then there's the output ports. Every time any Gizmo is called upon to do its stuff, it has to check how many ports there are, zap the first one, increment some internal value, check if its done, zap the next one, etc. That's necessary for a few of the Gizmos, but most Gizmos only have one or two ports. Why can't they just zap their one or two ports and be done with it? Most Gizmos have no need for that extra overhead.

Ultimately, the problem boils down to all that flexibility coming from runtime variables. Since the flexibility happens at runtime, the compiler can't usually optimize away the speed issues. And since all the Gizmos are the same type, struct Gizmo, the compiler can't optimize the space issues either.

Let's see how the Gizmos currently perform. I'll use this test program to simulate an UltraGiz and time it:

From ex1_original.d:

On my 1.7 Ghz Celeron (Yes, I know that's old, please don't flame me!), compiling with DMD in release mode with optimizations and inlining on, my result is 21 seconds. My system's task manager tells me it used 10.4 MB of RAM. Hmm, even on my old hardware, that could really be better.

Flexibility is really starting to push his co-star's buttons. Efficiency is even getting ready to take a swing at Flexibility. Uh, oh! At this point, many people just decide to prioritize either efficiency or flexibility. Often, this comes with reasons like "Hardware just keeps getting faster" or "This is built for speed, those who need flexibility can use a slower alternative." I've never liked to compromise, and I think we can do better. So let's see if we can diffuse this odd couple's situation before it turns into an all-out brawl (and they consequently loose their lucrative time-slot due to prime-time decency standards).

From ex2_objectOriented.d:

Oh dear God, what have we done?! Blech!

Ok, calm down...Deep breaths now...Stay with me...Breathe...Breathe...Maybe it's not as bad as it seems. Maybe it'll be worth it. After all, it's technically flexible. Not pretty, but flexible. Maybe the efficiency will be good enough to make it a worthwhile compromise. Let's see...

The code to test this version is almost the same as before so I won't show it here. But you can view it in ex2_objectOriented.d if you'd like.

On my system, this takes 40 seconds and 11.3 MB. That's nearly twice the time and 10% more memory as before. Hmm, uhh...nope, no good. Well, that was a bust.

So what went wrong? The problem is, object orientation involves some overhead. Polymorphism requires each instance of any Gizmo type to store some extra hidden data, which not only increases memory usage but also allows fewer Gizmos to fit into the cache. Polymorphism also means an extra indirection when calling a member function. This extra indirection can only sometimes be optimized away. Each Gizmo needs to be individually allocated (although it's possible to get around that in certain languages, including D, but it's still yet another thing to do). The by-reference nature of objects means the Gizmo arrays only contain pointers. Not only does that mean greater memory usage, but it can also decrease data locality (how "close together" related data is in memory) which leads to more cache misses. Using composition for the spin capability also decreased data locality, increased indirection, and increased memory usage. All things considered, we wound up doing the exact opposite of what we tried to do: Our attempts to decrease time and memory increased them instead, and also gave us less maintainable code.

In many cases, the overhead of object orientation isn't really a big problem, so object orientation can be a very useful tool (although perhaps not so much in this case). But in highly performance-sensitive sections, the overhead can definitely add up and cause trouble.

So for all the successes Dr. Oop has had, efficiency and flexibility are just too strongly opposed. Flexibility is left unhappy with the complexity required, and poor efficiency nearly had a heart attack! This time, Dr. Oop's solution just isn't quite what the patients has been hoping for. Oops, indeed.

Programmers familiar with templated classes might be annoyed at this point that I've rejected the object oriented approach without considering the use of template classes. Those familiar with D are likely screaming at me, "Mixins! Mixins!" And then there's C++'s preprocessor, too. Well, frankly, I agree. Such things can certainly improve an object oriented design. But those are all forms of metaprogramming, which I haven't gotten to just yet. Besides, the main point I want to get across is this: Object orientation isn't a general substitute for metaprogramming and does have limitations in how well it can marry efficiency with flexibility.

From ex3_handcrafted.d:

It certainly matches the old man's speech patterns, but just look at the careful attention to detail and workmanship! Two handmade single-port Gizmos, one spinny and one not. Two handmade double-port Gizmos. And even a couple general-purpose multi-port jobs. Let's take 'er for a...ahem...a spin...

On my system, that clocks in at 10.5 seconds and 9.4 MB. Hey, not bad! That's definitely an improvement over the original. It's twice as fast, and uses about 10% less memory.

The old guy's a bit eccentric, and his methods may be a bit out of date, but he really knows his stuff. Too bad the approach is too meticulous and error-prone to be useful for the rest of us mere mortals. Or for those of us working on modern large-scale high-complexity software.

I should point out that since the Gizmos are now separate types, with no common base type, they can no longer be stored all in one array. But that's not a big problem, we can just keep a separate array for each type. No big deal. And if we wanted, we could create a struct GizmoGroup that kept arrays of all the different gizmo types in a convenient little package. The town elder didn't actually make such a struct, but in any case, here's the updated UltraGiz:

From ex3_handcrafted.d:

In reality, specially handcrafting only-slightly-different versions is such a meticulous, repetitive maintenance nightmare that you'd normally only make one or two specially-tweaked versions, and leave the rest of the cases up to a general-purpose version. And even that can be a pain. So as happy as efficiency may be, flexibility is storming out of the room. We're getting close, but haven't succeeded yet. What we need is a better twist on this handcrafting approach...

From ex4_metaprogramming.d:

Dr. Metaprogramming points out, "As an added bonus, trying to make a portless Gizmo is now caught at compile-time instead of runtime."

Efficiency whines, "Look at all those ifs!" The doc explains that those aren't real ifs, they're static if. They only run at compile-time.

Efficiency responds, "Oh, ok. So you're really making many different types, right? Isn't there an overhead for that, like with polymorphism?" The doc says it does make many different types, but there's no runtime polymorphism (just compile-time) and no overhead. Efficiency smiles.

Seeing Efficiency happy makes Flexibility concerned. Flexibility balks, "We occasionally require some logic to determine a Gizmo's number of ports and spinnability, so I doubt we can do this." The doc assures him that D can run many ordinary functions at compile-time. And in other languages, code can just be generated as a separate step before compiling, or a preprocessor can be used. He adds that even if runtime logic really is needed, there are ways to do that, too. He'll demonstrate all of this shortly. Flexibility smiles.

The code to test this is still very similar to all the other versions. But since this is the first metaprogramming version, I'll show the new Gizmo-testing code here:

From ex4_metaprogramming.d:

One of the important things to note here is that the function useGizmo() is templated to accept any type. This is necessary since there are multiple Gizmo types instead of just one, and also because the Gizmos are structs instead of classes and therefore don't have a common base type. So effectively, there is now a separate useGizmo() function for each Gizmo type (although a smart linker might combine identical versions of useGizmo() behind-the-scenes). In the next section, I'll get back to the matter of this function being templated, but for now, just take note of it.

Also, note that the arrays gizmosA, gizmosB, etc. were replaced by a templated array. This is just like the separate arrays from ex3_handcrafted.d, but it gives us a better way to refer to them. For example, we now say gizmos!(2, false) instead of gizmosC. This may seem to be of questionable benefit, especially since we could have just named it gizmos2NoSpinny. But it will come in handy in the later metaprogramming versions since it lets us use arbitrary compile-time values to specify the two parameters. That gives us more metaprogramming power. But that will come later.

This version gives me 10.1 seconds and 9.2 MB. That's just as sleek and slim as the handcrafted version and...wait no...huh? It's slightly better? Granted, it's not by much, but what's going on?

It may seem strange that generic code could be more efficient than a specially handcrafted non-generic version. But at least part of what's happening is that with metaprogramming, the compiler is essentially doing your handcrafting automatically as needed.

Remember, in the real handcrafted version, the town elder only handcrafted one-port and two-port versions. For everything else, he had to fallback to the original strategy of dealing with a variable number of ports at runtime. With the metaprogramming version, on the other hand, the compiler automatically "handcrafted" a special five-port version when we asked for five ports. If we had also asked for three-port and seven-port versions, it would have automatically "handcrafted" those as well. It's possible to create and maintain all those special version manually, but it would be highly impractical.

If you really do want a single type for general multi-port Gizmos, just like the town elder's handcrafted version, that's certainly possible with metaprogramming, too. In fact, we'll get to that later.

Of course, I don't mean to imply that handcrafted optimization is obsolete. There are always optimizations a compiler won't be able to do. But when your optimization involves creating alternate versions of the same thing, metaprogramming makes it quick and easy to apply the same technique on as many different versions as you want without hindering maintainability.

I've alluded to a number of flexibility enhancements that can be made to this metaprogramming version. I'll explain these as promised, but there's one other enhancement I'd like to cover first:

From snippet_notAGizmo.d:

The templated useGizmo() function will happily accept that. Hmm, accepting a type based on its members rather than its declared name, what does that remind you of...? Yup, duck typing.

Granted, it's not exactly the same as the usual duck typing popularized by dynamic languages. It's more like a compile-time variation of it. But it still has the same basic effect: If something looks like a Gizmo, it will be treated as a Gizmo whether it was intended to be or not. Whether or not that's acceptable is a matter for The Great Duck Debate, but for those who dislike duck typing, it's possible to kill the duck with metaprogramming and constraints. This is almost identical to ex4_metaprogramming.d, but with a few changes and additions that I've highlighted:

From ex5_meta_deadDuck1.d:

Those experienced with the D programming language may notice this is very similar to the way D's ranges are created and used, but with the added twist that a type must actually declare itself to be compatible with a certain interface.

Now, if you try to pass a boat dock to useGizmo(), it won't work because the boat dock hasn't been declared to implement the IGizmo interface. Instead, you'll just get a compiler error saying there's no useGizmo() overload that can accept a boat dock. As an extra bonus, if you change Gizmo and accidentally break it's IGizmo interface (for instance, by deleting the doStuff() function), you'll get a better error message than before. Best of all, these changes have no impact on speed or memory since it all happens at compile-time.

Under the latest version of DMD at the time of this writing (DMD v2.053), if you break Gizmo's IGizmo interface, this is the error message you'll get:

So it plainly tells you what type failed to implement what interface. In a language like D that supports compile-time reflection, it's also possible to design the IGizmo interface so the error message will state which part of the interface wasn't implemented. But the specifics of that are beyond the scope of this article (That's author-speak for "I ain't gonna write it.")

This is great, but announcing and verifying these dead-duck interfaces can be better generalized. Changes from ex5_meta_deadDuck1.d are highlighted:

From ex5_meta_deadDuck2.d:

If you ever want to create another type that also counts as an IGizmo, all you have to do is add the declaration line:

From snippet_anotherGizmo.d:

Now isIGizmo will accept any AnotherGizmo, too. And just like a real class-based interface, if you forget to implement part of IGizmo, the compiler will tell you.

There are many further improvements that can be made to declareInterface(). For instance, although it's currently using a string mixin, it could be improved by taking advantage of D's template mixin feature. It could also be made to detect the name of your type so you only have to specify "IGizmo", and not "AnotherGizmo". But this at least demonstrates the basic principle.

For the sake of simplicity, the rest of the examples in this article will forgo the anti-duck typing techniques covered in this section.

Of course, none of this is needed if you're only using classes, which can truly inherit from one another. In that case, you can just use real inheritance-based interfaces. But if you want to avoid the overhead of classes, you can use these metaprogramming tricks to achieve much of the same flexibility.

All that needs to be done is assign the return value of a function to a compile-time value. The compiler will execute the function itself (if it can) instead of waiting until runtime. Simple. Changes from ex4_metaprogramming.d are highlighted:

From ex6_meta_flex1_ctfe.d:

From ex6_meta_flex2_frontend.d, the frontend program:

And the main program, with changes from ex4_metaprogramming.d highlighted:

From ex6_meta_flex2_compilingAtRuntime.d, the main program:

From example_runtimeToCompileTime.d:

Of course, given the repetition in there, metaprogramming can be used to automatically generate the code to handle large numbers of possible values. Or even the entire range of certain types, such as enum, bool, byte or maybe even a 16-bit value. A 32-bit value would be unrealistic on modern hardware, though. And arbitrary strings would be out of the question unless you limited them to a predetermined set of strings, or to a couple bytes in length (or more if you limited the allowable characters). But even with these limitations, this can still be a useful technique.

In any case, the fact remains: With certain restrictions, it is possible to convert a runtime value into a compile-time value. Here's how it can be applied to our Gizmo example (as usual, changes from ex4_metaprogramming.d are highlighted):

From ex6_meta_flex3_runtimeToCompileTime1.d:

That will work, but there's two potential problems with it.

The first problem is that it involves extra runtime code. That could cut into, or possibly even eliminate, the efficiency savings from metaprogramming. However, the extra runtime code is only run once when setting up the Gizmos, not while the Gizmos are actually being used. So as long as the Gizmo usage is enough to overshadow the extra overhead, it should still be worth it.

The second problem is that the addGizmos() function is an incredibly repetitive mess of copy-pasted code. It's a total violation of DRY: Don't Repeat Yourself. Maintaining that function would be very error-prone. Fortunately, that's easily fixed with a preprocessor, macros, or in D's case, string mixins:

From ex6_meta_flex3_runtimeToCompileTime2.d:

If you wish, you can see the generated code by simply outputting the result of dispatch:

From snippet_outputGeneratedCode.d:

To do this, we'll use the same metaprogramming Gizmo we've been using for all the other methods in this section. But we'll also add a DynamicGizmo which is identical to the original Gizmo in ex1_original.d, just with a different name. Then, the UltraGiz will look like this (as usual, changes from ex4_metaprogramming.d are highlighted):

From ex6_meta_flex4_dynamicFallback1.d:

The original Gizmo with the runtime options, ie DynamicGizmo, is used where necessary, while the more common cases are optimized with metaprogramming techniques. Not a bad compromise.

As you can see in the full code listing for ex6_meta_flex4_dynamicFallback1.d, I opted to make a completely separate definition for the dynamic version of Gizmo; that is, the DynamicGizmo. It would have also been possible to use a single definition for both the metaprogramming Gizmo and the DynamicGizmo. To do that, you'd just need to add another compile-time parameter, say bool dynamicGizmo, to go along with numPorts and isSpinnable. Doing so would probably be a good idea if only part of your struct is affected by the change from runtime options to compile-time options. But with Gizmo, the metaprogramming version converted practically everything to compile-time options, so in this case it was a little cleaner to just leave DynamicGizmo defined separately.

One other notable change I made was to the gizmos template (Ie, the arrays that had been named gizmosA, gizmosB, etc. in the earlier handcrafted version.) In all the other metaprogramming versions, gizmos had been templated on number of ports and spinnability. That worked fine, but now we have DynamicGizmo which doesn't really fit into that. So now gizmos is templated on the Gizmo's type so the dynamic Gizmos can be accessed with gizmos!(DynamicGizmo). Unfortunately, that also means the nice simple:

Becomes the ugly:

So I created an overload of the gizmos template which maps the nice simple old syntax to the new one.

As an extra benefit, templating gizmos on type makes it easy to clean up all those repetitive foreach statements in UltraGiz.run():

From ex6_meta_flex4_dynamicFallback2.d:

I've highlighted the changes from the original metaprogramming version, ex4_metaprogramming.d:

From ex7_meta_runtimeConversion.d:

From example_anyGizmo.d:

As you see in main() above, before you use an AnyGizmo, you first check the type via currentType and then use the appropriate member of gizmoUnion. This does have a few gotchas, though:

First, you have the runtime cost of checking the type before using the Gizmo. But this may be minimal, since you won't usually need to check the type on every single member access, only when it might have changed.

Second, since a union must be the size of its largest member, you won't get as much space savings when using an AnyGizmo. But, if the mere existence of one of your optional features requires extra time-consuming processing, you can at least save time because any Gizmos that forgo that feature won't incur the extra cost. Plus, this issue will only affect an AnyGizmo, not any other Gizmos you may have in use.

The final gotcha is that this makes converting a Gizmo more costly since the newly converted Gizmo needs to be copied back to the memory location of the original Gizmo. But if the Gizmo only needs to be converted occasionally, this shouldn't be a problem. If it is a problem, though, it may be possible to do the conversion in-place in memory.