Implicit optimization versus explicit optimization

Question

To explain what I mean, let me start with an example.

Consider a deque that supports O(logn) concatenation with another deque and O(n) addition of n elements at one end. This dequeimplements a general seq interface (or type-class, or what have you) that allows iterating over a collection.

An explicit optimization approach would be, having a concat method (or function) for deque objects and a separate pushSeq method for seq objects. Each method would be documented with the appropriate complexity.

An implicit optimization approach would be to have a single concat method that accepts a seq. An internal dynamic type test checks whether the supplied argument is actually a deque, and if so, calls an implementation method for concating deques. This is documented in the API.

Obviously you could have both of these. The point of implicit optimization is that you don't give the user explicit control over optimization. It just "happens", unless the user deliberately looks for it.

Right now I'm writing a library and I'm facing a very similar choice. I very much like the idea of a compact interface where things just "work". An implicit approach also gives me a lot more freedom. For example, maybe I can perform ten dynamic type tests to optimize the concat operation for different collections. Having ten different methods wouldn't make sense.

What's your take on this? Which approach is better, and why?

Answer 1

I don't optimize anything until I have identified a performance problem, measured and profiled the software and know where the problem is. I want your library to "just work". As it's a library, I expect it to be reasonably efficient most of the time for most use cases, but also do not expect it to be optimal for every case. If I find it is inefficient for a simple or typical use case, to kick off a performance concern, I will not be impressed - especially if it is trivial to fix - you, as the library vendor, should have (as you are doing now) thought of that.

Give me one method that works reasonably well most of the time, and if you feel the need, give some "advanced" API's that I can use when, and only if, needed. Make sure the advanced API's are clearly documented as such. e.g. "Use this API to optimize the speed/memory use/whatever...."

Answer 2

First off, I'm going to assume that you've verified that optimisation is actually needed. Much has been said on the perils of premature optimisation, so I'll just say that if you haven't already, then check that this code actually needs optimising (ie. it's responsible for a significant portion of the program's execution time, or, for libraries, it's significantly slower than the things it's going to be used alongside).

Having made sure that this optimisation is necessary, there are a few issues to consider. The first thing is to consider who will use it:

• Some users don't care about optimisation. Having multiple methods provides them with multiple options in a place where one option would be fine. You're making them think more than they might otherwise have to, which is to be avoided - a programmer's brain is their most important resource; you should not eat into it lightly.
• Some users may be less skilled or less experienced - they might not know about optimisation, or might not understand the difference between the methods. Presenting them with several options will confuse them, and they might use the wrong one, or just give up and go find another library.

To generalise the previous two points, if it's up to the user to optimise, then there will be some users who don't. This means you're limiting the performance of your library in a lot of its applications. If you can make your code faster, you'll probably want to make it faster for everyone who uses it.

It's also worth considering how the code will be used:

• Your different methods might end up having different names, depending on your language's restrictions on method naming and argument types. This means that users have to remember which method goes with which type. This is more complicated than just knowing that collections have a concat method.
• Hiding the optimisations away makes your library more useable - the user doesn't need to make any type checks themselves, or use different methods in different places. They can forget about performance and focus on functionality, using concat everywhere and knowing that the optimisations will be handled for them.

In general, I'd definitely advise making the optimisations implicit, tucked "under the hood". In most cases, a user should be required to understand as little as possible about the internal workings of your code in order to use it. They'll need to know what it does, but the details of how it does it shouldn't affect them.

The main argument I'd make in favour of letting the user access the internal methods is that they may be able to select the correct method themselves without needing the type checks you're making, simply by knowing from the structure of the logic what type the object will be at that point. If you want to leave this possibility open, then one approach I've seen work quite well is to have a layered namespace structure. This depends on what your language allows, and the nature of the methods in question (might not work with your situation) but in general, it works something like this:

• A standard namespace, MyLibrary, which contains all the top-level functions with their checks and implicit optimisations. The majority of your users will just use this, and leave your code to optimise things.
• A deeper namespace, MyLibrary.Core or something like that, which exposes some more of the internal methods. The standard namespace is mostly a wrapper to hide this deeper namespace from users who are happy to let your code handle the optimisations. Users who really want to squeeze a little extra performance can use this namespace to give them access to the internal methods, so they can handle the optimisation themselves.

Answer 3

Having a single method that can choose if/when to follow a pre-defined optimization is a better route to take. Just some advantages off the top of my head:

• Easier to write unit tests
• Will "Just Work" for anybody using it
• Can update/change the code handling that section without requiring anyone relying on the code to change anything
• Can add further optimizations or new types without affecting anything else
• Less likely people will use it "wrong" and come complaining to you
• Easier to learn how to use your library
• Leads to better code reuse. What if an optimization actually works for 3 types, not just 1? You don't need to rewrite much, if anything, and the users don't need to worry about which one to use

All that said, and as has been said above, don't do too much premature optimization. Wait until you know there's a problem, which unit testing and getting users will help you find.

Answer 4

From my perspective (admittedly biased by implementing general-purpose data structures for use in areas like raytracing and physics)...

Pros of implicit:

1. Can be used to avoid pathological misuse of your library (inappropriate algorithms/data structures).
2. Might make your library easier to use "reasonably well".
3. Allows users to deal with fewer functions/classes.

Cons of implicit:

1. You generally cannot really hide this information away from many people. They'll double their efforts to dig into your library and want to know its internal workings, only they're now investing more time counteracting the attempts to hide the performance characteristics. For such people hungry to understand performance characteristics of everything, the attempts to hide/make implicit starts to become an inconvenience rather than a convenience, since they'll now feel the need to understand more intricate details of when one algorithm is used over the other.
2. It will complicate testing of the library's correctness, as your input cases will have to cover the full range of cases against which you apply these optimizations.
3. You generally will not achieve optimal performance over the explicit version, as it's often too difficult to anticipate under which conditions one algorithm will perform better than the other (it's not as simple as choosing one with superior complexity; quadratic-complexity sorting outperforms linearithmic, for example, on small input sizes).

From my standpoint, it's generally better to err on the side of explicit. That's not to exclude implicit options outright, but trying to hide the performance characteristics of your library too much and automating the decision of what algorithms to use can start to actually turn into a performance bottleneck if it's not done perfectly well while simultaneously multiplying the complexity and testing of its implementation. If you favor more explicit, users who run into hotspots using your library will at least have alternate options to explore. Favoring implicit too much may deprive them of all options besides using another library while you find yourself simultaneously dealing with multiplied maintenance costs.

Uniqueness Edit?

Since I got criticized a bit for not contributing enough unique information in my answer with the confusion that it was redundant with the accepted one, I'll try to make it clear where this answer differs through some respectful disagreements with it (though I still like that answer anyway!):

If I find it is inefficient for a simple or typical use case, to kick off a performance concern, I will not be impressed - especially if it is trivial to fix - you, as the library vendor, should have (as you are doing now) thought of that.

I like this rationale but have to respectfully disagree in this particular case dealing with libraries offering very generalized data structures and algorithms. It's an issue of perspective though and responsibilities. In my opinion, if a user uses a sub-par data structure or algorithm for the task at hand, it's not the library implementer's job to make that efficient, it's the user's to choose a better algorithm or data structure. And the main reason I think that is not out of laziness on the library implementer's part but just due to some practical tendencies I observe around me, that if we held library implementer's to such standards, all library implementations might be considered faulty under such standards, since I can easily use a linear-time search in just about any generalized container library for something I could do in logarithmic time or better.

It might even be trivial to fix such bottlenecks in the library itself, but to do so would then penalize those who genuinely wanted a linear-time search and determined through their measurements that it was the right choice for their use case.

Give me one method that works reasonably well most of the time, and if you feel the need, give some "advanced" API's that I can use when, and only if, needed.

I love this idea and my interpretation of that is to favor implicit most of the time with a more advanced explicit API on top. The difficulty is just in feasibly implementing it well. We might all have different experiences working with different libraries for containers and algorithms, but most of the ones I encountered were just "advanced" to begin with. They did not and could not abstract away their performance characteristics to the point where you could just use them willy-nilly and expect something even reasonably efficient to result. And if such expertly-implemented libraries have been unable to manage this so effectively, then I think it tends to be too ambitious for the rest of us to try to make it so much easier/implicit (and I have personally tried and failed), and this is why I tend to vote for erring on the side of explicit or the more "advanced" API to start with.

It might just be a matter of priorities. I do agree that this would be absolutely ideal, and any dream library I'd want to use would share the design suggested above if it was implemented beautifully. It just seems so hard to do that, so I would suggest prioritizing the "advanced" explicit API first, and if you find some low-hanging fruit where you can easily provide a more implicit API, aim for that second.

Philosophical Side

I might have been guilty of reading too much into this question, but I interpreted it as one much more generalized beyond the immediate scope of what to do with this deque, and that's what interested me as someone who explored this idea of implicitness as far as I could take it. It is curious how "explicit/advanced" many of our standard libraries are with armies of people who have come to understand their innermost performance characteristics, and how we have to choose daily between all these data structures and algorithms to do our thing.

And I tried before to utilize every corner of C++ to make a library that hid away performance-related decisions from the user, and even without any runtime checks involved (using code generation with C++ templates). And I had something going there where you could sort things and it'd choose between insertion/quick/radix sort based on the inputs, you could search and it'd just do it in constant/logarithmic/linear time based on the data structure, etc. etc. But after taking a lot of pride in that work, and over the months, I found it too difficult to reason about its performance, and my colleagues even more so, and I even hit some bottlenecks as a result of naively assuming that certain algorithms would always be faster based on certain conditions. And it wasn't even that naive because I benchmarked those conditions, but what I found was that the thresholds for when one algorithm is superior to another also varies based on the data type being used and not just say, the number of elements.

In the end I abandoned that uber implicit library for one more explicit, found it so much simpler to maintain and reason about, and it's kind of through my personal failures that I vote on leaning towards that explicit side, as many other container/algorithm libraries do. Conceptually it always does feel like things could be so much more implicit, but I can at least say that it's harder to do really well than it sounds. So I definitely think implicit is the ideal and share all those same hopes and desires to see such a library, but perhaps to save you some of the same grief I had, I'd suggest to prioritize the explicit API first. You can always build implicit APIs on top of explicit APIs; you can't do the reverse.