Sign in to follow this  
Rydinare

Unity STL Performance Thread

Recommended Posts

A discussion regarding STL performance started here: http://www.gamedev.net/community/forums/topic.asp?topic_id=563033t After discussing with Sneftel, we agreed it would be more appropriate to create a new thread.
Quote:
Original post by thatguyfromthething Sure, it will be faster than what someone who is a novice programmer writes, but how many times have you seen people using stl drop down to a straight c array? If you need to do that more than one in a thousand times you suffer all the penalty of if you didn't use it at all, plus the penalty of huge learning curve and million problems and quirks.
If you're using an array that will always be the same size, you're correct that a vector is not the proper choice. Something like boost::array<> is a better choice to avoid the extra allocations. Is this a flaw in the STL or the developer who simply used the incorrect data structure? I vote the latter. Moreso, though, this points to pre-optimization. The point of code is not to be as fast as possible, simply fast enough. Therefore, if it's not a bottleneck in your code, why bother? A huge learning curve and a million problems and quirks is a blanket statement that I have not seen in practice. Can you elaborate on this a bit more?
Quote:
Original post by thatguyfromthething To write a good vector class as an example, it's really an exercise in memory management. That's too much for the average guy to tackle in a realistic timeframe, but the gains you can make are enormous even for vector class if you know what you are doing. Like if you might want your memory aligned properly by default or to have some SIMD get generated out (and no, this will never EVER happen automatically in your code).
I think you're speaking of specific cases. STL is not a golden hammer that solves all solutions. But, it's fair to say it solves most. Only after profiling had revealed the vector to be a bottleneck would it be a consideration to write my own.
Quote:
Original post by thatguyfromthething And that's just easily measurable speed you can improve, not the insidious problems caused by code size bloat when you have everything defined as multiple templates defined in terms of each other, which template on multiple items.
Why is this an insidious problem? A larger exe is not really a big deal in most cases.
Quote:
Original post by thatguyfromthething Not to mention where is the stl kdtree, hashtable, octree, bsp, cover tree, ball tree, rtree, btree, rtree, spatial index etc. etc. etc.? I mean, not even a hash table? Seriously? So how far can you go with game programming with just a vector and a map?
hash table is in the new STL standard and available under most compilers at this point or via STL port. It's unordered_map, unordered_set. There are tree and graph containers available (TCL, Boost, etc...). STL doesn't cover every possible collection, sure, but I don't see how that means that STL should be avoided.
Quote:
Original post by thatguyfromthething Also not mentioning crossplatform compatibility. Linux? Who cares? Has anyone ever made a cent supporting linux?
Yes.
Quote:
Original post by thatguyfromthething Mac support is nice I guess but then there's what? 5000 other platforms? Wouldn't you like to have code work on more than 1% of those platforms without additional tweaks? I have sat next to guys on multiple occasions who were trying to port stl over to other platforms, and for the time spent you may as well make your own - especially since there's not a hell of a lot in there anyway. Even if an implementation is lame you will be able to change it any time you want easily. I've gone through millions of lines of other people's code and hacked away but there's no way I could go into stlport source and figure out thing one of what's going on without searching around for hours.
Is there a specific platform you've had trouble with? I've used STL on Win32, Mac, various flavors of Linux, HP-UX, VxWorks and Nucleus OS. Of course, there's some platforms where STL may not be ideal, because of a weaker compiler, so you make adjustments for those cases. Those tend to be the minority of cases, not the majority.
Quote:
Original post by thatguyfromthething A template library written almost entirely in macros! The irony of that is astounding. That's exactly what templates are there to replace, and if you need or want to resort to macros chances are you are seriously abusing templates and have a poor design, which I strongly believe is the case.
If you're claiming that some implementations make use of macros, ok... true. I don't see your point. Templates aren't a drop-in replacement for macros. They're used to cover cases where macros were being abused and provide benefits that macros simply don't support. They don't cover all functionality covered in macros. The C++ standard does not require the use of macros in implementing the library either, so your statement simply doesn't hold water.
Quote:
Original post by thatguyfromthething So we get this kind of lame vector class, some math utilities that are far from optimal, a sort that is slow and has a ridiculously cumbersome interface using function points. Iostreams? Probably worst implementation idea in history. Except iterators, of course, which is the other big 'selling point' that is supposedly 'object oriented'.
The vector<> class is not lame by any means. That's just silly. If you're comparing ease of use against Java or C#, note that they had time to observe what was done and improve upon it.
Quote:
Original post by thatguyfromthething ... rant removed ... But, templates are the opposite of OOP. Instead of unifying your interface you are shattering it completely and making it impossible to tell what code is actually generated. WHAT GETS GENERATED? This is very hard to track down and is mostly left up to the people making the compiler, and for anything where you care about performance this is an issue. And if you care about more than one compiler, you get to track it down more than once, and you get things working great on one but not the other.
I disagree. I think the correct approach first identify that you have a performance problem using a profiler, then make adjustments to fix it. Why fix non-problems? If there's no performance problem, why does the generated code matter? That's the whole principle of abstraction.
Quote:
Original post by thatguyfromthething I have gotten surprised countless times at the stupid things compilers will do, especially with templates. Which is not to say not to use them at all because with C++ you are somewhat forced into it, but when you template on serveral items and do all the cute tricks you see in stl and boost, it is almost totally hopeless to ever track down what's really going on at a low level and you will see sudden performance drops for seemingly no reason. From the stupid comments I see all the time it's clear most people using stl and boost don't even know how templates really work or how the compiler works at all.
You can trace into STL and Boost. I agree it's more difficult than having the code entirely exposed, but it's certainly doable. The extra difficulty is offset by the fact that this is an infrequent task. If performance is dropping for seemingly no reason maybe you need to question what you're actually doing and if STL or Boost is the culprit.
Quote:
Original post by thatguyfromthething So obviously it's terrible if you really care about performance
Not obvious, no.
Quote:
Original post by thatguyfromthething and it doesn't have the data structures you would care about for making anything but some kind of business app without resorting to another API.
STL doesn't have a lot of the functionality in other libraries, I agree. Boost and other libraries fill in these gaps. While not ideal, it's hardly a lost situation and certainly not a reason to avoid STL altogether.
Quote:
Original post by thatguyfromthething And it's it's the antithesis of OOP because instead of simplifying interfaces and and types it exponentially grows them, and instead of decoupling interface and implementation it again exponentially increases the coupling effect between files.
I don't agree. Template meta-programming and OOP are two different paradigms. If you're thinking of templates as an OO construct, maybe that's why you're having so much difficulty. You use them together, but not interchangeably.
Quote:
Original post by thatguyfromthething So it's a terrible idea from either of the two important perspectives. If you are doing like a large business or database or general GUI app, you should care about the OOP aspect. If you are doing like a game or graphics tool then the performance aspect for most tasks and the OOP for things like events and GUI. If you don't care about either of these things, why are you using C++ and not perl or something?
The STL doesn't prohibit you from accomplishing either of these things. That's ridiculous. That's just blind hatred for the technology, no offense.
Quote:
Original post by thatguyfromthething So no, I am not spreading lies or misinformation. I used to think more like you, but years and years of struggling with C++ to make it behave properly have finally made me realize why this is such a poor approach.
It's good to be enlightened. I just question the basis behind it. When used properly, STL makes your life easier, not more difficult. I have worked on many applications, including high-performance servers and embedded. I haven't experienced the overwhelming breadth of the type of problems you describe. Isolated incidents, yes, those happen with every library. The big problem is that there was a time when what you're saying used to (mostly) hold water. The problem is it was well over 10 years ago. Nowadays, and in most cases, the advice you're giving is simply bad advice, no offense. I don't agree with the mentality of trying to micro-optimize every single section of code, even when 95% of that code isn't along the critical path.

Share this post


Link to post
Share on other sites
I've been in and out of the games industry for long enough that I've heard all the arguments that are being used about STL before.

I've heard them about using "proper" C++ -- by which people mean using virtual dispatching and inheritance.

Before that, they were talking about C++ vs C.

Before that it was C vs assembly language...

It's actually a pretty rare programmer whose hand-rolled last-year's technology can beat this year's compiler optimisations. I'm not saying it's not possible. It's certainly not possible without having a profiler and it's amazing how many people who haven't written line 1 of their software are spending their time thinking about how to optimise things. People who haven't ever written a game, haven't ever finished a bit of software are fretting that their game is SO special that it will put SUCH stress on machines that they need to START writing in assembly or without vdispatch or by building their own datastructs or deciding to code in low-level shader languages or whatever the hell this week's stupid argument is.

This is why the earth's hard disks are full of enormously optimised games that are only 1% complete and will never make it any further.

The original authors of UNIX were actually astoundingly lazy in that good way that really good devs are. That's why almost all the data structures are singly linked lists. They wrote them like that to start with and intended to optimise later when they needed to. And they never found a need to. On the other hand, they wrote an operating system whose basic design is still in use over 30 years later between three of them in a few months. There's a lesson there.

Of course, now that you can write a 'Breakout' or a 'Pacman' without absolutely *needing* to do it in cutting-edge bleeding eyes optimised assembly language because BBC Basic interpreted on a 1MHz microprocessor really won't cut it; what's the very, very first game everyone tries to write as their very first learning level project? World of flipping WarCraft, of course...

Share this post


Link to post
Share on other sites
It doesn't matter. To STL or not to STL in this context is a useless religious argument. I don't fight with you about which is better, needle nosed pliers or monkey wrenches.

The algorithms in the STL are authored a specific way that is often extensible: custom memory allocators, etc. It's important that you understand exactly how they are implemented. Once you know that you can decide if they are good for your task or not.

Sometimes you need to write clones with limited or specific functionality, sometimes they are perfect.

There is no correct side to the argument as stated: "is the STL good or bad". The only correct answer is "sometimes"

-me

Share this post


Link to post
Share on other sites
Quote:
Original post by Katie
The original authors of UNIX were actually astoundingly lazy in that good way that really good devs are. That's why almost all the data structures are singly linked lists.


I had nothing to do with UNIX, but I did do a fair amount of all kinds of coding in the 90s. I used linked lists for everything as well, in a variety of languages (which means 'both', C and Pascal).

Reason: There was no standard library, there was no code reuse, there was no versioning system, there was no storage (30MB disk with 2MB free), there was no internet, the BBS crawled along with 14.4bps, there was no wikis, no references, no codez sites, there was 'a book' on algorithms, and that was about it.

So when I needed a dynamic structure - I burst typed the link-list stanza (there was no copy paste either, there was no MDI).


And no, they were not dark ages, and there did indeed exist many alternatives, and people actually were doing real software - but point remains, in those days, I could write linked list blindly, not even thinking about it.

Compare this to RB trees, vectors, hash tables, etc, all of which depend on various internal details to be implemented robustly (resize factors, hash functions).

Also, in DOS times, vectors/arrays were not all that cool due to 64kb segment limit. And linked lists allocated memory accurately. Vector with 50% wasted space? Are you insane? 50 bytes wastes space could ruin one's day.



The reason I'm putting that out is because I didn't use linked lists because they were good - but because they were a 1lb. hammer. And while I had a full toolbox of power tools, I had to run everything on a single 1.5V battery, so I used the thing which didn't use power at all.

Today, someone might assume that linked lists must be magic because of all the reasons - they are not - they are dead simple, memory efficient and have constant performance characteristics. They are also likely the slowest of dynamic containers, but at least they are consistently slow.


Times have changed. It really was only 15 years ago when third-party libraries and compilers were a problem for many reasons. None of those reasons exist anymore.

Regarding STL: the reasons it "has performance problems" is due to the abstractions it defines. Those abstractions introduce specific performance characteristics. STL still compiles to assembly, and not some weird, 20% slower code.

Meanwhile, jobs ads are flooded looking for Ruby programmers, no previous experience needed, to develop cloud social applications, two week turnaround time.

The times have changed.

Share this post


Link to post
Share on other sites
Quote:
Original post by Palidine
It doesn't matter. To STL or not to STL in this context is a useless religious argument. I don't fight with you about which is better, needle nosed pliers or monkey wrenches.

The algorithms in the STL are authored a specific way that is often extensible: custom memory allocators, etc. It's important that you understand exactly how they are implemented. Once you know that you can decide if they are good for your task or not.

Sometimes you need to write clones with limited or specific functionality, sometimes they are perfect.

There is no correct side to the argument as stated: "is the STL good or bad". The only correct answer is "sometimes"

-me


Fair enough. The original author seemed to imply that the STL had no place in gaming or anything performance intensive, which was what I was replying to. My original point was for the majority of cases it's right choice, but certainly not all. There is no tool that is the right choice 100% of the time.

Share this post


Link to post
Share on other sites
I think a dev should show little humbleness in regards to new technology and paradigms. I've been there where asm was king, then inline asm in C++, then rolling your own data structures becouse STL was akward, etc.. You just gotta keep unlearning bad practices (which was considered good) while learning the new. Unlearning might be the bigger challenge.

Quote:
Original post by thatguyfromthething
... rant removed ...

But, templates are the opposite of OOP. Instead of unifying your interface you are shattering it completely and making it impossible to tell what code is actually generated. WHAT GETS GENERATED? This is very hard to track down and is mostly left up to the people making the compiler, and for anything where you care about performance this is an issue. And if you care about more than one compiler, you get to track it down more than once, and you get things working great on one but not the other.

It's not the opposite if OOP. Its generic programming in OO. It's more like duck typing with added benefit ot static type checking.

Why do you want to know what it generates? If profiler shows big perf drop there, just check it out from disassembly, if you're in low level stuff. Usually the unspecialized version does the job just fine, but you can always specialize it, to generate whatever you wish. And on larger scale, the compiler usually does a better job on optimization than any human.

Quote:
Original post by thatguyfromthething
I have gotten surprised countless times at the stupid things compilers will do, especially with templates. Which is not to say not to use them at all because with C++ you are somewhat forced into it, but when you template on serveral items and do all the cute tricks you see in stl and boost, it is almost totally hopeless to ever track down what's really going on at a low level and you will see sudden performance drops for seemingly no reason. From the stupid comments I see all the time it's clear most people using stl and boost don't even know how templates really work or how the compiler works at all.

Heh, that's a bit ironic. Yea compilers create suboptimal code time to time, shown by profiler. Like not inlining obvious function. But it's trivial to optimize it later, before the product ships. I haven't faced any difficulties to see low level code and to guide the compiler for better output.

Share this post


Link to post
Share on other sites
Quote:
Original post by Ftn
I think a dev should show little humbleness in regards to new technology and paradigms. I've been there where asm was king, then inline asm in C++, then rolling your own data structures becouse STL was akward, etc.. You just gotta keep unlearning bad practices (which was considered good) while learning the new. Unlearning might be the bigger challenge.


This. A thousand times this.

My biggest annoyance when it comes to programming are the 40 or 50 year olds who have 'been there, done that' and know the 'right' way to do something because 'it was true 20 years ago'. Never mind that times have changed, compilers have improved, cpu speed out paces memory speed and hundreds of other changes.

I've gone on a rant about this before; adapt or gtfo basically. Stop trying to hold back the state of the art.

(I should note that not all 40 and 50 year old coders are like this, the best ones do adapt and I'm glad about that. I also had a horrible shock when I went to write '30 year old' and realised 'crud, thats me in a few months.. errm' *chuckles* I pray I never get like that...)

Share this post


Link to post
Share on other sites
Quote:

It's actually a pretty rare programmer whose hand-rolled last-year's technology can beat this year's compiler optimisations.

I'd say this is a big misconception, too. People think that the compiler has some magic ability to go in and do wonders and that somehow with the stl that it's even better and these super advanced programmers (who mainly wrote this code 15+ years ago) have some secret mojo no one else does.

But the reality is the compiler is generally good at inlining, and good at return value optimization and good at rearranging order for pipeline execution. You might get a little better if you mess with compiler specific directives but to get simd generated out for example you need to do it yourself.

Quote:

It's certainly not possible without having a profiler

Profiler is another misconception, it's like saying you need a debugger to figure out bugs. It's just raw data, it catches things that amount to mistakes but it really tells you very little. Like the debugger, it is easy to misuse as a crutch that negates actual thought - it's not there to debug logic, but to catch simple mistakes and that's it.

Quote:

and it's amazing how many people who haven't written line 1 of their software are spending their time thinking about how to optimise things. People who haven't ever written a game, haven't ever finished a bit of software are fretting that their game is SO special that it will put SUCH stress on machines that they need to START writing in assembly or without

Well sure, it is always the case you can preoptimize things.

It's also easy to assume everyone on a site like this is a 15 year old game enthusiast or a college student but that's not necessarily the case and I'd bet there are also some of the best programmers in the world hanging around.

@Rydinare
This is sort of disjoint since I won't go through and edit everything for nine hours just to make a message board post.

But, just because you don't see something doesn't make it not so.

Most programs don't need to worry a lot about code size or performance, but most programs don't need to be written in C++. It's easy to get gigabytes of object files in C++, though.

The point of macros is metaprogramming, too. Templates were introduced as a replacement, because they work ok for little stuff but they are hard to deal with when making something large. I don't say anyone who uses macros is incompetent, but a template library programmed almost entirely in macros is pretty ironic and shows that it's probably not someone who should be listened to much. But, free has a big appeal.

Yes, other languages did learn from C++ mistakes. That's why they don't use C++ templates at all, but what does that have to do with anything? My point is not to bash on anybody, just to point out reality. The fact C++ has been left in the dust should say a lot about many of C++'s features.

I know templates are not OO, I'm the one who said it. Most people who talk about stl, design patterns, and OOP in C++ are pretty vague on what OOP is and how templates work. Or more likely, simply dead wrong. But, it's unsurprising because the way templates and C++ in general work is beyond mindboggling if you really look at it in detail.

People drop to c array because of performance, not size. I said nothing about resizing. You can also preallocate a vector, but that's not the real issue.

Sure you can trace through anything, but good luck with that using stlport or dinkumware, or probably any other big template library. But more important, what assembly gets generated? The point is not to look for mistakes but to find out why things slow down. This is possible but much harder with templates, almost impossible when you have complicated things going on (which almost anything in the stl qualifies as).

Who said I microoptimized anything? How would ten years passing have changed how stl works? Most of stlport was written 15+ years ago and has not changed a whit as far as I can tell in that time, whereas what qualifies as optimal code today has changed dramatically because hardware has changed dramatically. Sure computers can perform most tasks faster than ever, but again it comes to why are you using C++ if you don't care about performance? For some things you basically get paid in direct proportion to how much of x you can do, or even in exponential proportion. If Modo could handle 20 billion poly models would they be languishing in obscurity while zbrush has a dozen times the customers? Modo is certainly easier to use and it has all the same basic features, but bottom line is it's useless for most of what zbrush does so well simply due to not having the raw firepower.

How does stl solve almost anything? This came up as a discussion about data structures, if you remember. You (and I) are only talking about vectors because that's about all there is worth noting in stl. If that's all you need for data structures, you probably are mistaken to use C++ at all. I'd almost say the entire reason to use C++ at all compared to say Java is to be able to make specialized APIs. Of course if there is some API you need that's only in C++ then you are stuck with C++, but the real point is so that the people writing the API can have performance and flexibility and in turn use other low level APIs. Say you want to make something akin to Oracle or a game engine. Do you really think STL will cover your data structure needs? Well, it won't even scratch the surface. However if you are just some guy who uses Oracle or a game engine's built in stuff and make GUIs on top of it, by all means don't worry about data structures they use at all, because it's out of your hands anyway. If that's the case, drop C++ completely if you can and use C# or mono or python or Java to call on their API to do the actual work. But you can be pretty sure that somewhere in those programs there's a lot of work that went into various data structures.

If you want to convince yourself stl is a joke, just make a class with a vector of ints and a couple other primitive members, basically a typical object of some kind. Then make a vector of these classes, each with a dozen ints in the child vector. Add about a million to the vector, then sort it and see how long that takes to complete(for comparison, I can run the same code with my own implementation in about 150ms). Also note how awkward this is, syntactically speaking. Sure, you can blame the implementation, but the implementation is going to be different on each platform and yet tend to universally suck because. Also check the difference between what you get with a static array and a vector, I know that put a sad frown on my face.

[Edited by - phantom on February 25, 2010 3:42:16 AM]

Share this post


Link to post
Share on other sites
Quote:
If you want to convince yourself stl is a joke, just make a class with a vector of ints and a couple other primitive members, basically a typical object of some kind. Then make a vector of these classes, each with a dozen ints in the child vector. Add about a million to the vector, then sort it and see how long that takes to complete(for comparison, I can run the same code with my own implementation in about 150ms).

Funny thing is, that takes a few ms using the STL on my machine. So, what now?

Share this post


Link to post
Share on other sites
Quote:
Original post by thatguyfromthething
Quote:
It's certainly not possible without having a profiler
Profiler is another misconception, it's like saying you need a debugger to figure out bugs. It's just raw data, it catches things that amount to mistakes but it really tells you very little. Like the debugger, it is easy to misuse as a crutch that negates actual thought - it's not there to debug logic, but to catch simple mistakes and that's it.
Are you telling me you don't use a profiler when doing performance analysis? If not a profiler then what? How do you know "Implementation A" is faster or slower than "Implementation B" if you don't profile?

Share this post


Link to post
Share on other sites
Quote:
Original post by Codeka
Are you telling me you don't use a profiler when doing performance analysis? If not a profiler then what? How do you know "Implementation A" is faster or slower than "Implementation B" if you don't profile?


It depends where one is standing. It is also the crux of this "Foo is slow". Also the basis for engineering, and the reason why Linux will not become desktop OS and why Twitter made it big and all other absurdities that seem to permeate the computing world.

It is not code that matters, and it is not code that is slow.

Slowness is in the domain of users - they tell you something is slow. Profiler lets you pinpoint down certain limited causes as to why it is slow.

This is why vector is good enough most of the time. Since development time is limited, after solving all the other causes, the application will, at some point, become fast enough.

A common fallacy of benchmarking is benchmarking in isolation.

Here's a more practical example, I deal in visualizations from time to time. And there was this graph handling tool. I used all the best practices, memory layouts, algorithms, etc, until it was able to handle 100,000 nodes in real time. As Borat would say "Great Success!".

Except it wasn't. The biggest graph that any user would ever load would be no more than 500 nodes. Which could be handled by a linked list of nodes using an n^2 algorithm.

I made the wrong assumption about what "fast" means. And second fallacy: "future-proof". Sure, my version is "future-proof". Except that future versions which actually do handle large graphs of hundreds of millions of nodes run on cluster of CUDA machines.

This is just one example of why constant factor optimizations are dangerous. Sure, 200% percent may sound a lot, but unless it is achievable with minimal effort, there's likely a million% improvement in using a different approach altogether.

Especially with multi-core being old news, TBB and similar tools abundant, it has gotten almost impossible to allocate any budget into constant overhead.

Instead, improving development practices by automating performance tests and either accurately getting user expectations, as well as accurate budget estimates will go much further, even if at smaller increments.

So I agree with that - profiler, while indispensable tool - is not where one should focus attention. Users are, for any arbitrary definition of user. They tell you which profiler to use, and where to point it.

Share this post


Link to post
Share on other sites
Quote:
Original post by thatguyfromthething
Profiler is another misconception, it's like saying you need a debugger to figure out bugs. It's just raw data, it catches things that amount to mistakes but it really tells you very little. Like the debugger, it is easy to misuse as a crutch that negates actual thought - it's not there to debug logic, but to catch simple mistakes and that's it.


Well, there's a big difference. When you're debugging you already know you have a bug and the general area based on what isn't working. When you're profiling, you're often looking for that initial glimpse into where your bottlenecks are, because frankly, even though you may think you have an idea, oftentimes, you won't really know until you profile.

Can tools be too heavily relied upon? Of course. But, the fact is that your avoidance of using these tools is part of the reason why you may feel like you do. If you think a debugger and a profiler are two tools that tell you very little, I don't know what to say, other than I couldn't disagree more. I can't foresee creating a large software project without both in my arsenal, and that is with some very good software engineering practices to surround it.

Quote:
Original post by thatguyfromthething
Most programs don't need to worry a lot about code size or performance, but most programs don't need to be written in C++. It's easy to get gigabytes of object files in C++, though.


Well, it's simply about picking the best tool for the job. If the only thing C++ had going for it is performance, I don't think it would consistently be one of the top three or four most widely used programming languages. It's hard to fathom that 10% of all applications are truly performance critical.

Quote:
Original post by thatguyfromthething
The point of macros is metaprogramming, too. Templates were introduced as a replacement, because they work ok for little stuff but they are hard to deal with when making something large. I don't say anyone who uses macros is incompetent, but a template library programmed almost entirely in macros is pretty ironic and shows that it's probably not someone who should be listened to much. But, free has a big appeal.


A template library programmed almost entirely in macros? Well, I don't agree with that statement at all. That's a grandiose exaggeration.

Quote:
Original post by thatguyfromthething
Yes, other languages did learn from C++ mistakes. That's why they don't use C++ templates at all, but what does that have to do with anything? My point is not to bash on anybody, just to point out reality. The fact C++ has been left in the dust should say a lot about many of C++'s features.


Actually, other languages started out with no templates, then people were writing a lot of type-unsafe and dangerous code, so it revealed the need for generics. These languages later added support for generics and were often limited by their earlier choices. Most languages don't have a template or generic mechanism as powerful as C++ templates, but that often has to do with the history of those programming languages.

Anyway, you were saying STL is horrible; I was just curious what you were comparing it to that you might like better.

Quote:
Original post by thatguyfromthething
I know templates are not OO, I'm the one who said it. Most people who talk about stl, design patterns, and OOP in C++ are pretty vague on what OOP is and how templates work. Or more likely, simply dead wrong. But, it's unsurprising because the way templates and C++ in general work is beyond mindboggling if you really look at it in detail.


Well, I think beyond mindboggling is a bit of an overstatement. Template meta-programming can be ugly. The true power wasn't really envisioned when C++ templates were designed and it has evolved through creative exploit after exploit into a very powerful, but somewhat confusing paradigm. That being said, there is an effort to simplify it with C++ concepts, though we're years away from getting that.

Quote:
Original post by thatguyfromthething
People drop to c array because of performance, not size. I said nothing about resizing. You can also preallocate a vector, but that's not the real issue.


If you're saying a vector is still slower even after preallocating, I'll have to disagree. Memory allocations aside, an STL vector tends to operate as fast or faster, especially when looping, due to locality of reference.

Quote:
Original post by thatguyfromthething
Sure you can trace through anything, but good luck with that using stlport or dinkumware, or probably any other big template library. But more important, what assembly gets generated? The point is not to look for mistakes but to find out why things slow down. This is possible but much harder with templates, almost impossible when you have complicated things going on (which almost anything in the stl qualifies as).


I don't see why the assembly generated classifies as "more importantly". But if you need to know, you can certainly see the generated assembly. There is nothing preventing you from looking at it. As for complexity, I find the complexity of my application itself is much more critical than the complexity of the STL.

Quote:
Original post by thatguyfromthething
Who said I microoptimized anything? How would ten years passing have changed how stl works? Most of stlport was written 15+ years ago and has not changed a whit as far as I can tell in that time, whereas what qualifies as optimal code today has changed dramatically because hardware has changed dramatically. Sure computers can perform most tasks faster than ever, but again it comes to why are you using C++ if you don't care about performance? For some things you basically get paid in direct proportion to how much of x you can do, or even in exponential proportion. If Modo could handle 20 billion poly models would they be languishing in obscurity while zbrush has a dozen times the customers? Modo is certainly easier to use and it has all the same basic features, but bottom line is it's useless for most of what zbrush does so well simply due to not having the raw firepower.


Well, for one thing, many STL implementations were non-standard. In fact, the standard that we're referring to was C++98. Before that, the STL wasn't even exception-safe. I can't speak for STLport 15 years ago, because I've only needed STLport on two separate occasions, when there were performance reasons, because the STLport implementation was more performant. However, I'm quite confident that STLport has changed quite a bit in 15 years.

More to the point, Microsoft did not actually have a standards-compliant version of the STL until Visual Studio .Net 2003, IIRC. The VS6 one was terrible, buggy and leaky. This is why programmers with a heavy background in Windows tended to stick to MFC or ATL collections, rather than STL.

However, it's been a long time past, these issues are no longer true. Then, factor in that compilers have, in the past 5-7 years made tremendous leaps. Visual Studio 2008 optimizes considerably better than VS6 ever did. The inline keyword or lack there of is taken merely as a suggestion to modern compilers, where on many older compilers, it was blindly followed, even when it degraded performance. There's a lot that changed.

I still have vague memories of leaky strstream implementations, of old GCC environments where STL didn't work quite right, of a 1996 implementation of STL on an old version of VxWorks, where half the methods of vector weren't implemented, because it was pre-standard. Yes, these times existed. They are long past.

Quote:
Original post by thatguyfromthething
How does stl solve almost anything?


I never said the STL solves almost anything. Your comment was "STL is a joke".

Quote:
Original post by thatguyfromthething
This came up as a discussion about data structures, if you remember. You (and I) are only talking about vectors because that's about all there is worth noting in stl.


Not at all. We're talking about vectors because you brought up vectors. I'd be happy to apply any of the discussion to list, set, multiset, map, multimap, unordered_set, unordered_map, etc...

Quote:
Original post by thatguyfromthething
If that's all you need for data structures, you probably are mistaken to use C++ at all.


If you read my earlier post, you'll notice I also mentioned using Boost and other third party libraries. If you need a list, I'll give you a list.

Quote:
Original post by thatguyfromthething
I'd almost say the entire reason to use C++ at all compared to say Java is to be able to make specialized APIs. Of course if there is some API you need that's only in C++ then you are stuck with C++, but the real point is so that the people writing the API can have performance and flexibility and in turn use other low level APIs. Say you want to make something akin to Oracle or a game engine. Do you really think STL will cover your data structure needs? Well, it won't even scratch the surface. However if you are just some guy who uses Oracle or a game engine's built in stuff and make GUIs on top of it, by all means don't worry about data structures they use at all, because it's out of your hands anyway. If that's the case, drop C++ completely if you can and use C# or mono or python or Java to call on their API to do the actual work. But you can be pretty sure that somewhere in those programs there's a lot of work that went into various data structures.


Again, you're writing things that I never said. STL is far from covering all my data structure needs. But it's powerful and flexible enough to build new data structures ontop. STL absolutely isn't perfect (especially with the design of allocators), but it's definitely better than you've given it credit for.

Quote:

If you want to convince yourself stl is a joke, just make a class with a vector of ints and a couple other primitive members, basically a typical object of some kind. Then make a vector of these classes, each with a dozen ints in the child vector. Add about a million to the vector, then sort it and see how long that takes to complete(for comparison, I can run the same code with my own implementation in about 150ms). Also note how awkward this is, syntactically speaking. Sure, you can blame the implementation, but the implementation is going to be different on each platform and yet tend to universally suck because. Also check the difference between what you get with a static array and a vector, I know that put a sad frown on my face.


Ok, all you're saying is you don't like the sort implementation. STL certainly provides you the flexibility to create an algorithm with a different sort implementation. If you're saying blindly using STL sort is a bad idea, I agree. In fact, I find that 99% of the time if I need something sorted, a vector is the wrong container to start with. Regardless, if you have code that proves that your mechanism is 150ms and the STL version is ridiculously slow, then post it, and I'm sure we can analyze it and tell you what you're doing differently and how to use STL more efficiently.

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
Quote:
Original post by Codeka
Are you telling me you don't use a profiler when doing performance analysis? If not a profiler then what? How do you know "Implementation A" is faster or slower than "Implementation B" if you don't profile?
It depends where one is standing. It is also the crux of this "Foo is slow". Also the basis for engineering, and the reason why Linux will not become desktop OS and why Twitter made it big and all other absurdities that seem to permeate the computing world.
I agree with you, but when you're talking about using std::vector (etc) vs. rolling your own, you can't conclude that one is faster than the other without profiling the specific circumstances.

Share this post


Link to post
Share on other sites
Quote:
Original post by thatguyfromthething
People think that the compiler has some magic ability to go in and do wonders and that somehow with the stl that it's even better and these super advanced programmers (who mainly wrote this code 15+ years ago)
Point me to a current compiler that uses a code generator not improved upon in the last 15 years. Among other objections to your statement, many code generators for amd64 have only been written in the last 5 years.
Quote:
have some secret mojo no one else does.
They have domain-specific knowledge generally restricted to language designers, hardware engineers and the like, which most of the rest of us *don't* have. If you are up to date on the intricacies of modern cache architecture and instruction-level parallelism, good for you.
Quote:
Quote:
It's certainly not possible without having a profiler

Profiler is another misconception, it's like saying you need a debugger to figure out bugs. It's just raw data, it catches things that amount to mistakes but it really tells you very little. Like the debugger, it is easy to misuse as a crutch that negates actual thought - it's not there to debug logic, but to catch simple mistakes and that's it.
If you are honestly claiming that attempting to solve a problem without reference to the relevant data is a sensible idea, then you open yourself to ridicule. I give you the opportunity to clarify what you meant there...
Quote:
Quote:
and it's amazing how many people who haven't written line 1 of their software are spending their time thinking about how to optimise things.
Well sure, it is always the case you can preoptimize things.
And 99% of the time, you will be optimising the wrong thing. remember the rule: 10% of the code takes 90% of the execution time. A profiler allows you to identify the 10%, but you can't do that until you write at least a prototype of the code.

You can legitimately make algorithmic optimisations ahead of time, but even here you want make sure you are actually working on a bottleneck.
Quote:
It's also easy to assume everyone on a site like this is a 15 year old game enthusiast or a college student but that's not necessarily the case and I'd bet there are also some of the best programmers in the world hanging around.
Contrary to popular myth, the best programmer is not the programmer who writes the best code. Rather, the best programmer is the programmer who delivers software conforming to project specifications, on or before the project deadline.

With that in mind, any optimisation beyond the project requirements is wasted time, and time is money. Optimising the wrong part of the application (because you didn't run the profiler) is even worse, because not only have you wasted time and money, but you likely still have to optimise the right part of the program.
Quote:
Most programs don't need to worry a lot about code size or performance... most programs don't need to be written in C++.
This is the truest statement in this thread - Kudos.
Quote:
It's easy to get gigabytes of object files in C++, though.
Sure, in Debug mode. But then again, most hard drives are hundreds of gigabytes these days, and release mode is generally on the order of 100x smaller...
Quote:
People drop to c array because of performance, not size. I said nothing about resizing. You can also preallocate a vector, but that's not the real issue.
Are you claiming that a pre-allocated std::vector performs worse than a malloc'd array? If so, are you willing to put your money where your mouth is, and demonstrate reproducible benchmarks to prove this claim?
Quote:
How would ten years passing have changed how stl works? Most of stlport was written 15+ years ago and has not changed a whit as far as I can tell in that time
The underlying compilers have improved drastically in that time. The standard library doesn't do anything particularly unusual or tricky - quite the opposite, it is very straightforward and efficient C++. Compiler improvements translate to direct performance improvements in standard library elements.
Quote:
optimal code today has changed dramatically because hardware has changed dramatically.
Really? I would like you to supply a concrete reference for this.

In certain specific areas this is true, for instance the PS3 with its unusual Cell architecture. In most other areas, the only change in writing optimal code has been moving away from C++ (because C++ isn't a good fit for something like Google's cluster).
Quote:
But you can be pretty sure that somewhere in those programs there's a lot of work that went into various data structures.
A lot of work went into, and continues to be put into, both the standard library and boost. Are you claiming there wasn't?
Quote:
Add about a million to the vector, then sort it and see how long that takes to complete(for comparison, I can run the same code with my own implementation in about 150ms).
Again, reproducible benchmarks, or it didn't happen. If you are making a comparative performance claim, handwaving is not sufficient.

Share this post


Link to post
Share on other sites
Quote:

If you want to convince yourself stl is a joke, just make a class with a vector of ints and a couple other primitive members, basically a typical object of some kind. Then make a vector of these classes, each with a dozen ints in the child vector. Add about a million to the vector, then sort it and see how long that takes to complete(for comparison, I can run the same code with my own implementation in about 150ms).


Mmhmm. This smells.

I distinctly remember the assembly generated from optimized stl being identical to that of arrays. I needed the C++ refresher anyways, so I generated this little test based off of what I interpreted this mini-rant to mean.

MSVS2008, standard release build config:

foo.h

#include <string>
#define _SCL_SECURE 0
#include <vector>

class foo{
public:
int x;
int y;
std::string name;
std::vector<int> stuff;

foo();
bool operator<(const foo &rhs);
};






foo.cpp

#include "foo.h"

foo::foo(){
x=rand();
y=rand();
name = "";
int count = rand()%12;
for( int ix = 0; ix < count; ++ix){
stuff.push_back(rand());
}
}

bool foo::operator<(const foo &rhs){
if(stuff.size() < rhs.stuff.size()){
return(true);
}
if(stuff.size() > rhs.stuff.size()){
return(false);
}
for(int ix = 0; ix < stuff.size(); ++ix){
if(stuff[ix]<rhs.stuff[ix]){
return(true);
}
if(stuff[ix]>rhs.stuff[ix]){
return(false);
}
}
return(false);
}






main.cpp

#include "foo.h"
#include <vector>
#include <windows.h>
#include <algorithm>
#include <iostream>

int main(){
DWORD beginInit,endInit, beginSort, endSort, beginArrayInit, endArrayInit, beginArraySort, endArraySort;

beginInit = GetTickCount();
std::vector<foo> foos(10000);
endInit = GetTickCount();

beginSort = GetTickCount();
std::sort(foos.begin(),foos.end());
endSort = GetTickCount();

beginArrayInit = GetTickCount();
foo foos2[10000];
endArrayInit = GetTickCount();

beginArraySort = GetTickCount();
std::sort(&foos2[0],&foos2[9999]);
endArraySort = GetTickCount();

std::cout << "init: " << endInit-beginInit << std::endl;
std::cout << "sort: " << endSort-beginSort << std::endl;
std::cout << "array init: " << endArrayInit-beginArrayInit << std::endl;
std::cout << "array sort: " << endArraySort-beginArraySort << std::endl;
return(0);
}






(using 10000 entries since a million blows the stack. Arrays are awesome!)


init: 110
sort: 125
array init: 375
array sort: 828


Yeah, those arrays are super awesome.


I don't have access to your code to test of course, but I suspect that any benefits you might gain in 'add a bunch of data and sort' tests will be offset by losses in 'remove entries from middle' or 'random access something near the end' or any of the other common collection behaviors. The STL has withstood years of analysis by people far better than you or I, and nobody has made a better performing general purpose vector. Period.

If you think that you or someone else has, prove it. Post some code or quit spreading disinformation.

Share this post


Link to post
Share on other sites
Quote:
Original post by swiftcoder
Quote:
Add about a million to the vector, then sort it and see how long that takes to complete(for comparison, I can run the same code with my own implementation in about 150ms).
Again, reproducible benchmarks, or it didn't happen. If you are making a comparative performance claim, handwaving is not sufficient.
^^This.

Everyone in this thread knows that they are right, so quit talking and produce the code, then we can optimise it with and without STL.
We can objectively look at the results, see which one is faster, smaller source, smaller binary, etc...

Share this post


Link to post
Share on other sites
Quote:
Original post by thatguyfromthething
If you want to convince yourself stl is a joke, just make a class with a vector of ints and a couple other primitive members, basically a typical object of some kind. Then make a vector of these classes, each with a dozen ints in the child vector. Add about a million to the vector, then sort it and see how long that takes to complete(for comparison, I can run the same code with my own implementation in about 150ms). Also note how awkward this is, syntactically speaking. Sure, you can blame the implementation, but the implementation is going to be different on each platform and yet tend to universally suck because. Also check the difference between what you get with a static array and a vector, I know that put a sad frown on my face.


Then run the same thing on a compiler supporting r-value references and an appropriate standard library implementation and watch the *one* performance problem that vectors suffer from be completely squashed.

Share this post


Link to post
Share on other sites
Here's my attempt :)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <map>
#include <windows.h> // for QPC

struct typical_object_of_some_kind
{
std::vector<int> vector_of_ints;
std::string a_string;
std::string another_string;
};

bool operator < (typical_object_of_some_kind const &lhs, typical_object_of_some_kind const &rhs)
{
// we could do "a_string" first, but that would be cheating...

std::less<std::vector<int> > pred;
return pred(lhs.vector_of_ints, rhs.vector_of_ints);
}

//------------------------------------------------------------------------------
int main(int, char **)
{
srand(0);

std::vector<typical_object_of_some_kind> big_vector;
for(int i = 0; i < 1000000; i++)
{
typical_object_of_some_kind tofsk;

std::stringstream ss;
ss << "This is a long-ish string that we'll add to the first value: " << i;
tofsk.a_string = ss.str();

for(int j = 0; j < 20; j++)
{
tofsk.vector_of_ints.push_back(rand());
}

big_vector.push_back(tofsk);
}

LARGE_INTEGER freq, start, end;
::QueryPerformanceFrequency(&freq);
::QueryPerformanceCounter(&start);

std::cout << "about to sort..." << std::endl;
std::sort(big_vector.begin(), big_vector.end());

::QueryPerformanceCounter(&end);

std::cout << "sort complete in: " << (static_cast<double>(end.QuadPart) - start.QuadPart) / freq.QuadPart << "s" << std::endl;

// print out the first few, just to prove it actually *is* sorted...
int num = 0;
for(std::vector<typical_object_of_some_kind>::iterator it = big_vector.begin(); it != big_vector.end() && num < 100; ++it, num++)
{
std::stringstream ss;
for(std::vector<int>::iterator it2 = it->vector_of_ints.begin(); it2 != it->vector_of_ints.end(); ++it2)
{
ss << " " << *it2;
}
std::cout << ss.str() << std::endl;

num++;
}

return 0;
}



It's totally unoptimized and I just wrote it in my lunch break, so it's not that great. For 1,000,000 entries it sorts in about 6.5 seconds. If you take out the strings, it runs in about 2.7s. For 100,000 entries (with strings) it sorts in 530ms.

Not as fast as it could be, but how often do you need to sort 100,000-element arrays of ints anyway?

Share this post


Link to post
Share on other sites
Quote:
Original post by Telastyn

init: 110
sort: 125
array init: 375
array sort: 828


Yeah, those arrays are super awesome.


I don't have access to your code to test of course, but I suspect that any benefits you might gain in 'add a bunch of data and sort' tests will be offset by losses in 'remove entries from middle' or 'random access something near the end' or any of the other common collection behaviors. The STL has withstood years of analysis by people far better than you or I, and nobody has made a better performing general purpose vector. Period.

If you think that you or someone else has, prove it. Post some code or quit spreading disinformation.


He's trying to create a hypothetical example where the vector is going to do a lot of copying due to having to re-arrange lots of stuff. This is a pathological example of poor performance given the right circumstances and a sufficiently expensive-to-copy object. Regardless, the problem is non-existant with r-value references so there's no point in even discussing it IMO.

Even if you want to say "well I'm talking about *old* code on compilers that didn't have that support", it's still arguably an invalid comparison because you aren't comparing the same things. A C-array is not a dynamically sized array. If you want a real comparison to a C-array then replace "vector" with boost::array<> and let's talk.

Share this post


Link to post
Share on other sites
Quote:
The STL has withstood years of analysis by people far better than you or I, and nobody has made a better performing general purpose vector.


This is what it comes down to right here. *General purpose* containers. You can create a structure that performs better than the STL in your particular situation, provided you know what you're doing. But it always involves sacrificing generality. The STL is designed to work with all container types without assuming certain traits which break certain objects. For example, if it's okay to move an object around without invoking it's copy constructor/destructor then you can reallocate or shift a vector of these objects faster than the STL would. But then you've sacrificed generality and made your code more dangerous too. If the object is later modified to contain a pointer to it's own memory, you're in big trouble.
Fortunately the commercial compilers actually take notice of what types you store in the vector and they will perform shallow copies on objects which are known to be safe. e.g. a vector of other vectors.

So if you think the STL isn't a satisfactory solution to your problem, you might want to:

1) Profile your code to see if it really matters
2) Switch to a different container as you're probably just using the wrong one
3) Understand why the STL container is slower than a customised solution and which constraints your own method drops in order to outperform it.
4) Determine if the expected performance increase is worth the time you're about to invest
5) Write your own container, profile it, get frustrated when it's somehow slower than the STL, do some research, discover that your compiler's STL implementation is using optimisations you've never heard of, then incorporate those optimisations into your own code and hopefully receive a payoff for all your time spent!

Share this post


Link to post
Share on other sites
Quote:
Original post by cache_hit
He's trying to create a hypothetical example where the vector is going to do a lot of copying due to having to re-arrange lots of stuff. This is a pathological example of poor performance given the right circumstances and a sufficiently expensive-to-copy object. Regardless, the problem is non-existant with r-value references so there's no point in even discussing it IMO.
It's also non-existent if you simply decide not to copy the objects while sorting them. Just sort indices or pointers instead of the actual heavyweight objects...
Design choice is obviously more important than library choice here.

If you do the equivalent operations without the STL (i.e. copying a vector == malloc/free) I don't see how there's going to be any performance difference. In his example, he's solving it in a stupid way with the STL and a smart way without it -- this doesn't prove the STL is slow, it just proves that one design is stupid.

Obvious fallacy is obvious.

Share this post


Link to post
Share on other sites
Quote:
Original post by Hodgman
Quote:
Original post by cache_hit
He's trying to create a hypothetical example where the vector is going to do a lot of copying due to having to re-arrange lots of stuff. This is a pathological example of poor performance given the right circumstances and a sufficiently expensive-to-copy object. Regardless, the problem is non-existant with r-value references so there's no point in even discussing it IMO.
It's also non-existent if you simply decide not to copy the objects while sorting them. Just sort indices or pointers instead of the actual heavyweight objects...
Design choice is obviously more important than library choice here.

If you do the equivalent operations without the STL (i.e. copying a vector == malloc/free) I don't see how there's going to be any performance difference. In his example, he's solving it in a stupid way with the STL and a smart way without it -- this doesn't prove the STL is slow, it just proves that one design is stupid.

Obvious fallacy is obvious.


Oh i agree, but that was too obvious to even mention :). I mentioned && refs because it makes vector<> *hands down* superior. Try storing objects by value in a c-style array and then lets what your hand written sort function performs at compared to that of a move-enabled implementation.



On another note the subject of template code bloat is highly exaggerated. Yea it exists, but not nearly as much as you (and by you i mean the indefinite you) think. And news flash, if you need a list of ints and a list of floats, then guess what - the code has to exist somewhere. The difference is that the compiler can often use the same code for multiplw parameterizations, while you cant, unless you store everything as void* in which case theres no ppint even discussing it anymore

Share this post


Link to post
Share on other sites
Quote:

If you have code that proves that your mechanism is 150ms and the STL version is ridiculously slow, then post it, and I'm sure we can analyze it and tell you what you're doing differently and how to use STL more efficiently.

This a 1000 times over. When i first started using STL I didn't know about all the tricks. You can reserve, resize, set custom allocators, replace iobufs, use range-checked accessors, etc. Not every operation is "fast" by default, but it IS "amortized fast" for a general set of operations. I think too many people put some esoteric case into their program, and complain STL is TOO SLOW!
For instance they will have vector<int> and push_back() a million items without calling .reserve(), then complain that new[1000000] is faster. I know I've made the mistake of not reserving before.
Or they complain that std::list<int> is too slow, and replace it with new int[1000]... well you've changed data structures. Did you really want a list? or an array? maybe you actually need a tree? map? set?
Or they complain the find() is too slow. Well, it is a linear search. You COULD use lower_bound, upper_bound, equal_range and do a binary search.

Share this post


Link to post
Share on other sites
This type of benchmarks is notoriously pointless anyway.

First question to ask is why are we sorting this many things or this type. If this needs to be done frequently, first split the storage into hot and cold parts. Hot contain a simple pair of key and pointer to actual data. This pair should be POD.

Second question to ask is - can we benefit from different approach. Can we sort less, can we use multiple cores, can we change the complexity of the problem.

Finally, what does the user actually want to do? It is highly unlikely that they will actually want to sort million gizmos. They will probably want to get top 10 movies - which is completely different problem altogether.


As far as graphics algorithms go - there isn't much to say. Papers are written in academic manner, but they usually involve only very trivial constructs, all which can be implemented in elegant and highly compact manner using in-place and implicit data structures.

Typical example would be recursion stack problem with quicksort. I find it simply unworthy of even mentioning - quicksort and many other recursive algorithms can be trivially converted to explicit stack version. But this simply isn't worth discussing or worrying about, it's semantically equivalent to going from for to while loop.

There is a very tiny edge case to be made with regard to hard-coding (globals) and other implicit relations, but the benefits gained from them are simply no longer viable under today's deadlines and cost models.

Effects of architectures, such as cache, synchronous vs. asynchronous, dynamic vs. static, etc... apply to all languages and libraries, and are mostly a design decision which should be taken into account in planning state to design the overall style of implementation - this is what will determine the overall characteristics of application more than any individual choice of algorithm or optimizations. It is also the area which is notoriously to get right first time off, since due to hardware capacities today the peak behavior will not be obvious from prototypes. This is the area where expertise does pay off, but very few pay attention to it or even consider it.

This willful ignorance of experience is mostly a consequence of abysmally cheap labor costs, which makes it cheaper to rewrite five times rather than hiring a single expert at five times the price. Practice shows that this approach is economically superior as far as business bottom line goes.

Whether this is good, bad or ugly is somewhat beyond the point, just like complaining that rain is wet. Bring an umbrella - or learn why the business works this way, and try to find a way to convince them they should be doing it differently. Most won't care, most won't benefit, but those that do will likely be the people who understand the underlying problems themselves.

Share this post


Link to post
Share on other sites
Quote:
Original post by Hyrcan
Quote:
If you want to convince yourself stl is a joke, just make a class with a vector of ints and a couple other primitive members, basically a typical object of some kind. Then make a vector of these classes, each with a dozen ints in the child vector. Add about a million to the vector, then sort it and see how long that takes to complete(for comparison, I can run the same code with my own implementation in about 150ms).

Funny thing is, that takes a few ms using the STL on my machine. So, what now?

You sorted a vector with a million classes on a random key value in the class, each containing a vector with 12 items in it in a few milliseconds without taking some kind of shortcut? Not that I don't believe you, but, I don't believe you because I've recently benchmarked it pretty thoroughly in VC++ and all benchmarks I see point to other implementations being about the same or even worse.

The results I get is it takes about 135ms to sort 1 million ints in STL.
Which to me is a pretty good result, but how often do you have a static array of a million ints?

It takes about 450ms if you use a vector instead of an array. Which is kind of crappy, but not enough to slit your wrists, but since this is the real world case for any large data it does kind of suck. Especially when you have sorting as part of a much more complex algorithm. A case that comes up again and again and again.

If you move to the scenario I describe it will be executing til the day you die unless you replace std:swap and optimize the copy constructor (and doing that for hundreds of classes is not a fun prospect). Which to me is kind of ridiculous. The interface here is bad enough to suffer, but aside from benchmarks almost everything you want to sort is going to be something more complicated. Like a linear octree node, a vertex, that kind of thing.


Quote:
Original post by Codeka
Quote:
Original post by thatguyfromthething
Quote:
It's certainly not possible without having a profiler
Profiler is another misconception, it's like saying you need a debugger to figure out bugs. It's just raw data, it catches things that amount to mistakes but it really tells you very little. Like the debugger, it is easy to misuse as a crutch that negates actual thought - it's not there to debug logic, but to catch simple mistakes and that's it.
Are you telling me you don't use a profiler when doing performance analysis? If not a profiler then what? How do you know "Implementation A" is faster or slower than "Implementation B" if you don't profile?


You can't get very far just optimizing the obvious, whole program performance is almost always a bigger issue, especially the larger and more complex your program becomes.

Code that runs great in a simple test might cause problems in a large long running program and when people say stuff like "code size doesn't matter" or even that there's no reason to make your own data structures it tells me they have not dealt with these issues before. Especially if the say there's no reason to code them at all. If all you use is one thing and have never done it yourself how can you even think you know anything about it?

Maybe the confusion is in thinking containers = all data structures.

[Edited by - thatguyfromthething on February 26, 2010 5:35:30 PM]

Share this post


Link to post
Share on other sites
Guest
This topic is now closed to further replies.
Sign in to follow this