tags:

views:

226

answers:

5

Two, maybe trivial questions:

1. Why can not I beat the STD functions?

Really. I spent the last three days implementing something faster than std::sort, just for the sake of doing it. It is supposed to be an introsort, and I suspect it uses the single pivot version quicksort inside. Epic fail. Mine was at least twice as slow.

In my utter bitterness I even copy-pasted other - top notch - programmers code. No avail. I benchmarked my other algorithms too... My binary search, and upper_bound, lower_bound versions are so stripped down it couldn't really be made with less instructions. Still, they are about twice as slow.

I ask, why, why, why? And this leads me to my next question...

2. Where can I find the source code of the STL library functions?

Of course, I want to look at their sources! Is it even possible to write more efficient code than those, or am I at an abstraction level with my "simple" main.cpp where I can not reach optimisations utilized by the STL library?

I mean for example... Let's take the maps... wich are simple associative containers. The documentation says it is implemented with a red-black tree. Now... would it worth it to try implement my own red-black tree, or they took this joy :-) away from me and I should just throw every data I get my hands on into the map container?

I hope this does make sense. If not, please forgive me.


+3  A: 

They are probably optimized to a great extent. Such implementations consider memory page faults, cache misses etc.

Getting the source of those implementations depends on the compiler they are shipped with. I think most compilers (even Microsoft) will allow you to see them.

I think the most important things to know are the architecture you are compiling to and the operating system (if any) your program will be running on. Understanding these things will allow you to precisely target the hardware.

There are also countless optimization techniques. This is a good summary. Also, global optimization is whole science, so there are certainly many things to learn.

There are some clever things on this site, too. Sok sikert!

Tamás Szelei
Hi, sztomi! I am from Hungary too :-).I use GCC and all I can find is header files with declarations, but no sources anywhere :-(.How could I achieve the same performance? What skills should I pick up? I can not imagine how one could do such sophisticated things in simple codes with few lines I mentioned (thinking about binary search, no introsort).
Mike Shinola
@Mike: You'd be surprised. I just improved the performance of GCC's `std::rotate` this past November. The code had never been changed in decades. (But now it's fast, of course :v) .) Sorting functions, though, I think are more glamorous and tend to be updated with any new research.
Potatoswatter
Woa! Sounds good. Did you submitted your changes or something? Anyway, I just found some real GCC code... dohh... full of __variable _name_this___and_that :-). How could you bear with that?
Mike Shinola
@Mike: The GCC standard library restricts itself to using names reserved for the implementation, which means everything (except interfaces) begins with a double underscore or underscore+capital letter. Otherwise, the user could legally `#define` something and accidentally modify a variable name. (Ironically, many people look at the library code and decide it's l33t to have macros with such names, which defeats the whole purpose.) I think it's best to write the code with normal variable names and add the underscores before submitting.
Potatoswatter
@ Potatoswatter: "Ironically, many people look at the library code and decide it's l33t to have macros with such names, which defeats the whole purpose." Laughed hard at that part ;-)
Mike Shinola
+2  A: 

Looking at the disassembled version of your code versus their code and comparing them may give you some insights into why their is faster than yours.

It seems like a fool's errand to reimplement from scratch standard library functionality for the sake of making faster versions. You'd be far better served trying to modify their version to achieve your goals, although even then you really need to understand the underlying platform to be able to judge the value of the changes that you're making.

I would guess that were you to post your sort routine that it would be torn apart in minutes and you would gain an understanding of why your version is so substantially slower than the standard library version.

dash-tom-bang
YOU try and modify Microsoft's stdlib. The code is incomprehensible.
iconiK
Thank you for the assembly hint, I will go after that! Also... It's not just about making faster code, it probably won't make a difference, but knowing its doable...
Mike Shinola
I have spent a great deal of time inside of the standard container code that ships with MSVC. It's a different coding standard from mine but it's very consistent and pretty easy to understand once you get the conventions. (And if it's the algorithms that you don't understand, optimizing it is probably out of your league.)
dash-tom-bang
+1  A: 

Two answers, probably generally-applicable:

  • You will probably not be able to implement more efficient versions of algorithms that many other smart people have spent much more time optimizing. By virtue of time and testing alone, the STD algorithms will be pretty good.

  • For identical algorithms, optimization is something which is "very hard" with all the current hardware and configuration variations. To give an example, the primary factor for algorithm performance on a particular platform might be which levels of cache its most frequently used routines can be stored in, which is not generally something you can optimize by hand. Hence, the compiler is generally much more of a factor for actual algorithm performance than any particular code you can write.

But yeah... if you're really serious about optimization, get down into the assembly and compare. My advice, though, would be to focus on other things, unless it's your job to optimize your implementation or something. Just my 2c.

Nick
"My advice, though, would be to focus on other things"... that is exactly my conclusion, and I will. And no, unfortunately nobody pays me for straining over a damn sort algo. :-D
Mike Shinola
+2  A: 

Most IDEs have a command to open a named header file using the compiler's search paths. I use this pretty often and tend to keep the code for algorithm open.

For me, the code you're looking for is in

/usr/include/c++/4.2.1/bits/stl_algo.h
/usr/include/c++/4.2.1/bits/stl_tree.h

Note that a lot of people have done their theses on sorting and tree-balancing (fields I would think are picked to the bone, I would not attempt research there), and many of them are probably more determined than you to make GCC's standard library faster.

That said, there's always the possibility of exploiting patterns specific to your code (some subranges are already sorted, frequently used specific small sequence sizes, etc).

Potatoswatter
Thanks for the IDE tipp. Of curse, my knowledge is insignificant compared to those people, but still... Its a hard pill to swallow. I succeded to get 4-6 times faster at 100 million integers than std::sort but only with classification sorts, with O(N) space complexity. I will try to rewrite one of these to be in-place, thus reducing the extra memory needed. Will see if I come up with something worthy. If somebody can point me to aformentioned sources codes, (s)he is more than welcome.
Mike Shinola
@Mike Shinola - Why do you keep asking for pointers to the source? Potatoswatter just told you where it was for GCC on Linux. What compiler and environment are you using? You can download many STL implementations right now, but chances are you already have the source on your system.
Brian Neal
@Brian Neal - I meant the source codes of inplace implementations of classification sources, not the STL library sources which I asked originally. Sorry if I did not articulate my intention properly, I was tired and it was midnight here.
Mike Shinola
@Mike: "inplace implementations of classification sources"? Can you give an example what you're looking for? Everything remotely related to trees and sorting is in header files right on your machine.
Potatoswatter
@Potatoswatter: edit: *"classifications sorts", sorry. I am looking for an implementation of radix sort wich has much smaller space complexity than the usual O(N). I have read some reports about them in the past few days, but my current job does not leave enough time for me at the moment to give it a try - neither my skills are enough to translate academically phrased pseudocode into raw code in such a short time what I have on my hands. Nevertheless, I will definitely crack it in some time. The unfortunate thing is my holiday is over and I cant allow myself to spend hours on algorithms.
Mike Shinola
+8  A: 

The short answer is "if it was possible to write faster code which did the same thing, then the standard library would have done it already".

The standard library is designed by clever people, and the reason it was made part of C++ is that other clever people recognized it as being clever. And since then, 15 years have passed in which other clever people tried to take these specifications and write the absolutely most efficient code to implement it that they could.

That's a lot of cleverness you're trying to compete with. ;)

So there is no magic in the STL, they don't cheat, or use tricks unavailable to you. It is just very carefully designed to maximize performance.

The thing about C++ is that it's not a fast language as such. If you're not careful, it is easy to introduce all sorts of inefficiencies: virtual function calls, cache misses, excessive memory allocations, unnecessary copying of objects, all of this can cripple the performance of C++ code if you're not careful.

With care, you can write code that's about as efficient as the STL. It's not that special. But in general, the only way you're going to get faster code is to change the requirements. The standard library is required to be general, to work as well as possible across all use cases. If your requirement is more specific, it is sometimes possible to write specialized code that favors those specific cases. But then the tradeoff is that the code either will not work, or will be inefficient, in other cases.

A final point is that a key part of the reason why the STL is so clever, and why it was adopted into the standard, is that it it is pretty much zero-overhead. The standard libraries in many languages are "fast enough", but not as fast as hand-rolled code. They have a sorting algorithm, but it's not quite as fast as if you wrote it yourself in-place. It might use a few casts to and from a common "object" base class, or maybe use boxing on value types. The STL is designed so that pretty much everything can be inlined by the compiler, yielding code equivalent to if you'd hand-rolled it yourself. It uses templates to specialize for the type you're using, so there's no overhead of converting to a type understood by the container or algorithm.

That's why it's hard to compete with. It is a ridiculously efficient libary, and it had to be. With the mentality of your average C or C++ programmer, especially 10-15 years ago, no one would ever use a std::vector if it was 5% slower than a raw array. No one would use iterators and std algorithms if they weren't as fast as just writing the loop yourself.

So the STL pioneered a lot of clever C++ tricks in order to become just as efficient as hand-rolled C code.

jalf
+1 for "if it was possible to write faster code which did the same thing, then the standard library would have done it already"
FredOverflow
"If you're not careful, it is easy to introduce all sorts of inefficiencies :..., cache misses..."Could you elaborate on that? Im going to google for it tonight but if you have any good sources to learn from, I am all ears (or eyes, in this case).
Mike Shinola
To be honest, I wasn't sure whether to include that one, because it's not unique to C++, it's a property of the hardware. The thing is basically that the CPU cache uses locality to determine which bits of memory to keep in cache: spatial locality (if you just used the data at address X, you'll probably soon need the data at X+1) and temporal locality (if you just needed a chunk of data, you'll probably need it again soon). So if your code involves jumping around between random chunks of data, the cache won't hold the correct data so it constantly has to load that data from main memory instead
jalf
Two common ways this can become a problem is if you have a 2D array, traversing it column-wise instead of row-wise means that every new element is on a new row, and so it is far removed in memory from the previous entry you accessed, and will result in a cache miss. If you traverse a row at a time, you only access contiguous addresses, and so the cache is able to predict which data is needed, and have it ready for you.
jalf
The other example is a linked list vs an array. The list allocates new memory for each node, and that memory might be *anywhere*. The vector is one contiguous chunk of memory, so spatial locality is guaranteed. every part of the vector is near the rest of the vector, and the cache likes that
jalf
@jalf: Tank you for your contribution! The 2D array part is especially enlightening, never tought about that yet! I think I have to learn to think like a machine then and utilizing the underlying hardware properly. Also, if I remember well there is a register keyword in C which is kind of like a hint to cache the data since you intend to use it frequently. Does it worth something at all? From what I have read: it depends. I would rather use less explicit methods though, since the compiler either listens to my register keyword or not.
Mike Shinola
@jalf: So if you, or anyone has any tutorial, book, resource what could help me to catch the drift, I would really appreciate it.
Mike Shinola
@Mike: The register keyword is useless. Most compilers just ignore it. A modern compiler performs extensive analysis for carrying out register allocation. The keyword dates back to a time when that was too expensive to do, and so it was necessary for the programmer to tell the compiler which objects to place in registers.
jalf
As for books, I'm not sure. I've learned a lot from this one: http://www.amazon.com/Computer-Architecture-Quantitative-Approach-3rd/dp/1558605967, but to be honest, this hardware-level knowledge isn't often necessary. It's typically better to focus on code level improvements. As in the STL case, make sure you don't waste time accidentally creating copies of objects, or initializing before assigning, when you could just do a copy construction instead, and so on
jalf
@jalf: The book looks interesting, I will definitely order it. Thanks for the heads-up. I really appreciate all your help. Thank you again.
Mike Shinola