So, on Facebook, one of my long term nuclear engineering friends gave an example of a straightforward ‘find a minimum element’ loop in a C++ float array, and its equivalent in std::vector using std::min_element, noting that the two had a performance difference of around 15% on his particular test examples (which admittedly I did not see), and then snarked something along the lines of “I’m beginning to think all this talk of optimizing sorting times and stuff like that I hear from my computer friends is just a smokescreen. 😉“.
I probably should have been a little less snarky in my responses. I pointed out that
- Linear array processing with an index is something processors are built for
- Linear array processing with an index is something compilers are highly geared towards optimizing, and if you start abstracting on something that simple, the compiler may have difficulty doing the same kinds of optimizations. A more complex example like actual sorting may close the gap.
- 15% is hardly a problem unless you’re in the tightest possible loops deep in the 5% of your program that needs optimization, at which point why would you be using the STL?
- The performance of the STL in this context isn’t going to be worse than a constant time factor than raw array processing anyway, which is something you’d learn by studying optimization and complexity of algorithms.
- Readability, maintainability, and flexibility count for a lot in large programs (in the 95% that doesn’t require optimization), and that’s where using flexible containers and abstract algorithms actually matter.
- Maintaining readability becomes more important and way easier to justify when you’re not doing something trivial like looking up the minimum element of a container.
- This is a good opportunity to find out why you might take a performance hit in the STL, and even how to avoid the hits while still using it.
Okay. I was a bit of a pedantic dick about a snark, but at least I can turn this into something useful.
I could probably turn this into a whole series of essays on STL performance analysis in a somewhat modern compiler, but I think I’ll leave that for another day, as, frankly, I’m sure that’s a huge can of worms. It turns out my friend’s original intent, at any rate, was seeing what he could learn about more modern C++, promptly wrote a simple but practical example, and then raised an eyebrow that it wasn’t as performant as a manually written tight array processing loop.
Here’s my chance, then, to give an example, albeit a highly cooked example, of a taste of some modern C++ up to and including C++14.
In the code below, I’ll be calling one example set the “C++98” version for the older C++98 spec. It will avoid the STL almost entirely (even though C++98 supports the STL just fine), uses mostly custom objects and hand-written containers, and uses no modern language features. It is meant to be a minimalist program written by someone who understands classes, inheritance, and maybe templates, but not using the STL to act as container logic.
I’ll be calling the other batch the “C++14” version. While the STL has been around for quite some time, well before C++11 for example, I’m going to be mixing in C++11 and C++14 extensions, and I’m not writing a half dozen incrementally more modern versions of the same program.
So let’s jump right into it. Enter the Sensor class we’ll be largely operating on, in C++98 style:
Just a link to a great little video.
Multicore is already here and getting more important.
Even if one works most frequently in imperative/OO languages, as I will likely have to in a practical job for most of the rest of my coding career, failure to acknowledge the benefits of coding in a functional style, if not a functional language, is foolhardy. It’s here to stay, implicitly or explicitly, in any language that hasn’t completely stalled development. LINQ in C#. Improvements to Java collections and C++ STL. Lambdas everywhere. Scala and Clojure taking over the JVM and re-using Java classes. F# using the .NET runtime. Haskell compiling to native code.
And yet, the imperative and OO crowd don’t need to abandon all their design philosophies entirely. Its not about eliminating state. It’s about tightly controlling it.
Really really easy watch. No prior knowledge about any particular language required.
As part of solving a puzzle that’s going around, I had a need to figure out all the ways I could fit into a fit, say, a sequence of bricks of various lengths b0, b1… bn onto a wall of length n, where there had to be at least one unit of blank area between them (for, say, mortar, in this example, or report back that no such arrangements existed, if the bricks could not be made to fit. The order of the bricks must be preserved. Bricks and mortar spots are unit aligned, and there are no fractional units involved.
Its a tidy little sub-puzzle in its own right, and much shorter, so I think I’ll make it my challenge for those very few readers I have. Mostly just to amuse myself. Solve it in whatever language you like.
- length of wall n
- list describing sequence of brick sizes
- list of sequences each of which is…
- …a list of ranges which describe the start and end of each brick
Just a short blog post to link to this other beautiful blog post about C#’s LINQ.
It’s from 2006, and I’m not exactly a C# guru, though I’ve used it a fair bit inside Unity3d over the last few years.
However, it does a fine job at making good practical use cases for LINQ and why FP even in just this limited scope should matter to everybody in practical programming where there are generations, transforms, and aggregations of collections of data — which is very nearly every nontrivial program at some level.
It is a very easy read. It introduces necessary concepts slowly, with good examples. It talks to C# programmers specifically, and also OOP programmers (Java, C++, etc, yadda yadda) more broadly, rather than talking to people who have been writing FP for years.
I’ve grown very fond of FP languages over the years as I think that’s where the most interesting language exploration has been being done lately, but I’m not the slightest bit surprised or frankly perturbed by people having to or choosing to use more ‘traditional’ and established languages for doing the kinds of projects you might find me involved in… game programming, scientific programming, graphics and images, and to a lesser degree UI.
But its really good to see powerful techniques cross over between languages and get explained so well in terms of the people already using these more ‘comfortable’ imperative and OOP languages.
A friend of mine in the course of their work had to solve a space optimization problem she would have preferred to solve in O(n log n) time instead of O(n^2), and after some brief but fun discussion she epiphanied a bead on how to solve her particular scenario, and went on with life.
However, as these things frequently go, this managed to nerd-snipe me, because what started as a fairly straightforward bit of smug turned into a day long (and long overdue) bit of coding-for-elegance-and-performance in at least two different languages. This involves optimization of a lookup table and a sequence of indices into that table.
( regarding this post: http://java.dzone.com/articles/java-enums-you-have-grace )
This is a neat feature in Java. Being able to have an auto-numbered list of identifiers which also carry auxiliary (constant) information associated with the identifier could be handy for a number of uses, not the least of which is the state machine implementation that forms one of the article’s examples.
I mentioned in my last post, where I took my first stab at a little Swift program, that I might post that program with all the type annotations intact.
The point was to potentially illustrate, at least in that program, that the addition of the extra unessential type information didn’t actually improve the readability or comprehension of the program.
(Note that, if I wasn’t convinced by this language, and Haskell, using really strong typing and type inference, I would totally be against leaving type information out, so take this post with that in mind).
The original can be found at the bottom of this post:
The fully annotated version is at the bottom of this post.