The Joel on Software Discussion Group (CLOSED)

A place to discuss Joel on Software. Now closed.

This community works best when people use their real names. Please register for a free account.

Other Groups:
Joel on Software
Business of Software
Design of Software (CLOSED)
.NET Questions (CLOSED)
TechInterview.org
CityDesk
FogBugz
Fog Creek Copilot


The Old Forum


Your hosts:
Albert D. Kallal
Li-Fan Chen
Stephen Jones

"The Compiler should optimize that"

Last week I was interviewing a candidate for a programming position and I asked him a question about how to sort a particular type of dataset. He outlined on the whiteboard a bubblesort.

I asked if there might be any performance problems with that method of sorting.

He said, "There can be, but the compiler should optimize that."

I asked "The compiler will optimize what exactly?"

"That, the method."

"The sort algorithm you're using? The compiler will improve it?"

"Optimize it, yes. Any good compiler should do that."
Scott
Friday, November 24, 2006
 
 
Hopefully, you said canidate was a "no hire".
Bill Rushmore Send private email
Friday, November 24, 2006
 
 
Yes, but I am having difficulty finding competent people. Forget superstars, let's talk finding someone who isn't convinced they are a superstar yet just knows enough to be dangerous.

I did explain as best I could to the candidate what the issues were that I was concerned about, so that it would be an educational experience for him as well. I don't know if it helped, he's probably off posting on slashdot right now about his interview and that I didn't understand how advanced modern compilers are in his opinion.

The reason I brought this up is that I hear this comment a lot whenever I get into a discussion about performance issues. This meme is that optimization is not needed. There is this idea that compilers will optimize anything that can, theoretically, be optimized. That compilers do some sort of amazing analysis on code and can refactor and make optimizations that are basically miraculous to be able to automate.

The reality is of course that compiler optimizations are mostly simple things. They certainly won't analyze your code to discover your algorithms, evaluate your dataset to determine the most appropriate algorithm, then rewrite the code to use the new algorithm. But a lot of developers seem to think that that's what they'll do.

My speculation is that these guys don't know much about optimization or data structures or algorithms beyond a few pre-cooked APIs that come with their pet toolkit. So they do the testosterone thing when asked about performance issues by posturing and claiming that smart programmers don't optimize because compilers do that for you.
Scott
Friday, November 24, 2006
 
 
You should have asked him a follow-up question:

"Exactly what change would the optimiser have made? - Please show all steps"

His response might have been:

BubbleSort()
QubbleSort()
QubblkSort()
QubbckSort()
QuibckSort()
QuickSort()
pmuhC
Friday, November 24, 2006
 
 
I'd be disappointed that the candidate didn't just use the standard library's sort() method.
A Lackey
Friday, November 24, 2006
 
 
This interviewee is shit, no two opinions on this. :)

But on optimizations: It's a race between programmers trying to waste more and more cpu cycles, and the hardware industry trying to improve cpu cycles per second.

As long as the hardware industry is winning, one could simply state that certain kinds of optimization are simply not worth the time effort, because it's cheaper to let the user wait or throw in faster machines.
Optimized Offender
Friday, November 24, 2006
 
 
"Yes, but I am having difficulty finding competent people."

Aren't we all.  As much as people bitch about the state of management of software personal, there be might a reason for it all.  In my searches I've yet to find a single competent programmer who will do more work than damage. 

"My speculation is that these guys don't know much about optimization or data structures or algorithms beyond a few pre-cooked APIs that come with their pet toolkit."

I haven't interviewed in a long time -- even for my last job I didn't interview I just got the job.  But I feel I'd probably fail a lot of these interview questions.  I did, for university, write all kinds of algorthims but if someone asked me to write a quicksort I'd probably just look at them funny.
Almost H. Anonymous Send private email
Friday, November 24, 2006
 
 
pmuhC, that is funny. I would have liked that response.

Lackey, the response 'use the standard library function' to every sort situation is the exact same sort of response that tells me the candidate has very shallow understanding as when they claim the compiler will optimize bad code into good and inappropriate algorithms into appropriate ones.

AHA, "who will do more work than damage". Yes, that's a big issue. This person had held programming jobs and knew how to program to a spec in C, but I need someone who also can think and design and problem solve for themselves, and that involves being more knowledgeable not about APIs and methodologies, but about fundamentals.
Scott
Friday, November 24, 2006
 
 
I think that much of this is the result of current teaching techniques in computer science. When I was in college in the mid-ninties it was common to be told that you should not worry about efficiency (spatial or temporal) because either a) modern machines had more than enough memory/speed to handle whatever damn-fool way you chose to do something, or b) the compiler will take care of optimization for you. While this was, technically, true for most of the problems we faced in class, it was galling to be told these things without caveat or proviso, as if they would be true for all problems under all conditions.

At least once in college I ran into a homework problem that patently violated these assertions: in the organization of programming languages course we were given a project using a functional language (ML) to write a simple interpreter. About halfway through the project the servers on which we all did our work started crashing. It turned out that the student's programs were eating up huge amounts of virtual memory and causing the systems to kernel panic when they ran out of virtual storage.

Another problem is that you never get a very good understanding of how compilers actually work: you get pretty good coverage of lexical analysis and parsing, and adequate coverage of peephole optimizations and register allocation, but the deeper mysteries of optimization are not covered all that well. Even if you've taken the compiler design course at a good school you probably still don't understand optimization all that well.

Couple these two problems (an pedagogical insistance to ignore efficiency and a weakness in compiler design courses) with students who are not very inquisitive (maybe not as much of a problem today as it was during the dot-com boom) and you get folks with a degree in CS who still have some pretty odd ideas about what goes on inside the machine. These folks aren't just code monkeys who would be entirely out of their depth unless provided with their accustomed IDE and development framework, they are, in fact, educated computer scientists who simply haven't exceeded the limits of their narrow (by necessity of time and materials) education.

Not that I'm saying you should hire these bozos: if you are doing something really challenging, you need someone who took the time to learn more than what was in the book or the lecture. Unfortunately, these folks may be few and far between, and you may need to shell out one or two standard deviations above the median salary to convince them to work for you. These folks may also not be easy to contact: they may not be looking for work, either because they are self-employed entrepeneurs or because their current employers work VERY hard to keep them. Joel had an essay a year or so back about how to hire such folks, and it wasn't encouraging.

Here is the entry from January of 2005:

http://www.joelonsoftware.com/items/2005/01/27.html
Jeff Dutky Send private email
Friday, November 24, 2006
 
 
Actually he's right

Any good compiler ___should___ do that.

It's just that no compiler yet invented does do that.

One day compilers, or whatever they're called by then, will do that.  They will be able to understand the program's goals in a similar way to human programmers do, and be able to generate their own new code and algorithms to achieve the program's goals.

So I say give him a 2nd interview, in about 250 years time...

P.S.
Does this mean he's invented a wholly new kind of premature optimization?
Sunil Tanna
Friday, November 24, 2006
 
 
And on side note, why in the C library isn't there a 2-function pointer version of sort (call it sort2 or something) - one where both the swap and comparison are call-backs.  That'd be handy.
Sunil Tanna
Friday, November 24, 2006
 
 
"As long as the hardware industry is winning, one could simply state that certain kinds of optimization are simply not worth the time effort, because it's cheaper to let the user wait or throw in faster machines."

The difference between an O(n^2) sort and an O(n log n) sort is _huge_. It is worth the time effort.
masharpe
Friday, November 24, 2006
 
 
> Aren't we all.

When is the last time you wrote a sort? Possibly never. I think expecting the compiler to optimize a method is bad answer, but it could be stress related. It's hard for me to think that someone remembering between bubble sorts and the other variants is relevant. Surely there is something more job related you could ask?
son of parnas
Friday, November 24, 2006
 
 
Jeff, that's a good analysis. This candidate I'm sure can do good work somewhere, maybe a lot of places. Just not here with what we do since one of our big advantages is performance.

This is just one of the myths about performance, that compilers and faster hardware will fix performance automatically and if not, the compiler is broken or your customers need to buy faster workstations.

Another myth is that high performance code is hard to understand, non-portable, unmaintainable, etc. These are all excuses used to not have to deal with performance issues.

Getting the last squeeze out does make more complex code, but the first few orders of magnitude all comes from knowing your Knuth and/or being a competent mathematician who is not afraid to make mathematical discoveries and/or just trying it out lots of different ways and profiling.

Those first few orders of magnitude can all be abstracted.

When you get to the final stretch and you are unrolling your loops and programming to the vector processor, yeah, damn straight if it doesn't make the code complicated and harder to maintain, but most of these methods are patterns that you know and recognize when working in high performance code, so for those who know it, it's not more complex or unmaintainable at all, and more than C++ is unmaintainable compared to Logo.
Scott
Friday, November 24, 2006
 
 
While, I may sound disturbing, but I detest interviewers who ask textbook questions and get textbook answers. Now for the rest of my post, please consider "you" to be a third person :D , or better, consider that I'm speaking to  another listener who's interested in getting the meat.


***********************************

If you really want superstars, be an interviewer for superstars. Why not ask them about what they've done before in previous jobs and how they've done it. I'm pretty sure they wont avoid that question on the basis of some pending patents.
You don't have to ask superstars about how library functions are implemented. They care less about that, than their code that runs on it. It was implemented as a library function for a particular reason.
Now unless they're going to reinvent the library function as a part of their, specifically for the sake of performance issues, they're are never going to be bothered about that in the interview.

I know you'll respond with the fact that this person didn't get bubble sort and code optimization right. But what are the chances that a person with even that amount of minimal CS knowledge will attend your recruitment drive.


Seriously, which of these do you consider to be true ?
* Superstars know where they want to work, and might not turn up at all. Do they ever ever turn up ?

* The wannabe stars but good enough programmers, will want  to be groomed and a commitment from your company to seriously consider retaining them in the long term. They might already know that your answer is in the negative and hence not turn up. Do they turn up, but eventually reject your offers ?

* The market - pure wannabes on the monetary side will always be there in plenty. Do you keep meeting them 90% of the time ?

If you answers are true for all of these, its time to raise this with the senior most manager you can get to talk with.
Why?
* Your best engineers will already know that you've got a hard time finding people, compared to the rest of the market. They'll soon start thinking of leaving if you've got nothing planned for them.
* Your good but certainly not the best developers, will know the market is good for making a switch. They'll switch, since you haven't made concrete plans for them yet (you start planning at the top).
* You retain the garden variety programmers since they wont find another place to switch to. All others places are eventually like yours, in that they no longer accept garden variety programmers.

In short, raise the bar. Offer more, snag more.

***********************************
. Send private email
Friday, November 24, 2006
 
 
>> I'd be disappointed that the candidate didn't just use the standard library's sort() method.

Actually, unless you're using CPython, standard library sort functions tend to suck.  If performance is important, replacing a standard library sort function with something domain specific can give you a big boost.
SomeBody Send private email
Friday, November 24, 2006
 
 
You're assuming a lot. I tend to not like assumptions as that's where things get screwed up.

We're offering up to $200k total compensation for the position, but we're also flexible in how that's done. 8 weeks vacation is standard. And I don't need a superstar, just someone who is decent. I don't even have a list of technologies anyone has to know. Technologies and APIs you can learn or pick up. Just looking for someone intellectually curious with an interest in the problem domain, and actual ability to contribute more than they detract.

But let me reiterate - this thread is not about hiring people at all. I actually don't care about that today as I have other stuff that's more important to deal with. I am only talking about this phenomenon of belief in compilers as able to optimize something just because in their minds it may sometimes be optimizable.

S. Tanna says in 250 years this will all be optimized. He is assuming that CPU speeds haven't stalled out, and that this problem of automatically refactoring algorithms themselves into new algorithms isn't NP complete, which I'm pretty sure it is and will remain so.
Scott
Friday, November 24, 2006
 
 
That response was to '.'. I agree with SomeBody's response, which was part of the point I was making. When you take an algorithms class, usually you start with sort and go through performances of the various popular sorts with various datasets. The poor students come out of that week in class with the idea 'quicksort is best, always use quicksort'. Unfortunately, that was not the idea the class was trying to impart.
Scott
Friday, November 24, 2006
 
 
Seems like you're advertising in the wrong places, or you're simply getting those folks with x years of experience ,where  O(x) = 1. Frankly, if you're advertisement sounds like you want someone who has a fair bit of experience and is willing to switch domains, make it look so. Or you might end up meeting these folks who read notes on the flight to your town.
Or hire someone who's fresh but willing to learn and eventually get the work done. Grooming is anyway not investor friendly or manager friendly.

PS: Where are you located ?
. Send private email
Friday, November 24, 2006
 
 
In my work, I often get asked to look at poorly-performing systems, and discover the most outrageously inefficent coding. Almost as often, I find developers wasting time tuning pieces of code that have no impact on overall system performance. There's a huge pool of developers out there toiling away with no clue about performance. Which is fine when they're turning out simple CRUD applications and low-volume web sites. And when not, well, it keeps me busy...
Mike S Send private email
Friday, November 24, 2006
 
 
Again, I reiterate, this is not about hiring.

Let me change the initial story to be fictional instead.

Hey everybody, I was at a bar last week and this biker guy wearing a filthy leather jacket, a long beard, and silvered mirror glasses said that bubblesort is good enough because any decent compiler can optimize that! Can you believe it! What is with folks nowadays, I tell you!
Scott
Friday, November 24, 2006
 
 
Scott, I actually agree with you on the original point - i.e. that he should have known this.  In my experience, superstars may not be greatly interested in how library functions are implemented, but they do understand how computers point.

I was being flippant about the 250 years, but if you want to take it seriously... I'll bet you $10 that compilers will be able to do this within the next 250 years.  You pay me, if and when a compiler does it, but if it's not been achieved by then, I'll pay you $10 in 250 years time.
Sunil Tanna
Friday, November 24, 2006
 
 
OK, Sunil I will take that bet. We will meet on November 24, 2256. Let's say in front of the League of Interplanetary Justice, next to the blue reflecting pond.
Scott
Friday, November 24, 2006
 
 
Here is a little code for disassembling (RELEASE-ed, of course):

    std::vector <int> v;
    v.push_back (7863);

Might be fun!
:-)

And everyone blames compilers!
You have to blame developers.
ALWAYS!
asmguru62 Send private email
Friday, November 24, 2006
 
 
Would that be the League of Interplanetary Justice the Alpha or Gamma quadrant?

It's people like that who give outsourcing a good name. Does anybody have a clue how computers work anymore? To think that a compiler will optimize a poorly written sort seems ludicrous. I've found a lot of the same things as Mike S as far as people writing poor algorithms for important pieces of code and over-optimizing unimportant parts. I'm no compiler guru or hardware nut, but come on people.

And I've seen this thing on CRUD sites as well as in other types of applications. I would say in some instances poorly performing algorithms are even a bigger issue with CRUD sites because they are usually written in high level scripting languages. In a lot of cases you are already fighting an uphill battle because of the performance penalty you pay for scripting languages and the fact that many of them are still written as CGI's and you pay a lot of overhead for database connections and the like. To put a poorly performing algoritm on top of that is like running 1/2 a mile uphill with an extra 100lbs on your back.

My favorite piece of optimization I wrote, ever, I think was replacing a VBS custom sort method somebody wrote. It used 3 arrays and a collection and had issues sorting anything more than about 1,000 items. It would time out. The comments in the code talked about how to use this class when you needed "fast sorting". I was able to replace this WONDERFUL sort with an 'ORDER BY' clause in the SQL statement used to get the data and lo and behold, it could properly sort 10's of thousands of records and return the results in mere seconds.

Things like this reenforce my belief that some people should not be allowed near a keyboard.

I'm gonna go cry now.
Bart Park
Friday, November 24, 2006
 
 
Damn!

I just spent two weeks optimizing my triangle sorter...now you tell me I was wasting my time! NOT!


PS: I made it nearly three times faster.
Jimmy Jones
Friday, November 24, 2006
 
 
I'll tell a story. Everybody else has stories about the stupid other idiots they've met, but this one's about me.

I was working on a project as part of a grad school internship -- I wasn't in a CS program, and my training in sorting theory and practice was rather minimal. I need to perform a simple calculation on each member of a very (very) large dataset, and I needed to work on the values in order.

Without really thinking, I took my data, passed it to the standard library's sort function, and ... waited. About two hours later, my supervisor wandered back to see what was going on, heard the hard drive working itself to death, and laughed himself hoarse.

Clever readers already know what happened: Quicksort's great, until you run out of memory, and spend all your time swapping instead of sorting. If I'd stuck with that, it'd probably still be sorting today.

Supervisor pointed me in the direction of a merge sort, and a few minutes later, I had myself some working software.

Moral: This theory stuff continues to be important in real life.
Mark Jeffcoat Send private email
Friday, November 24, 2006
 
 
asmguru62, you are very clever.

#include <vector>
int main()
{
  std::vector <int> v;
  v.push_back (7863);
    
  return 0;
}

With full optimization on, and using the first couple compilers I tried this on, the body of main() turns into thousands of assembly language statements.

That's a very very good point you are making and is something most STL advocates just don't get.
Scott
Friday, November 24, 2006
 
 
> I am only talking about this phenomenon of belief
> in compilers as able to optimize something just
> because in their minds it may sometimes be optimizable.

Well, he probably read some discussions about how you don't have to worry about this or that detail because a good compiler will handle that particular thing for you.

There are several areas where this is certainly true.

But then he extrapolated that idea into an area where it doesn't apply at all (the compiler optimizing your actual algorithm).
Michael G
Friday, November 24, 2006
 
 
> With full optimization on, and using the first couple compilers I tried this on, the body of main() turns into thousands of assembly language statements.

There is a lot of code emitted, but ...

* Using MSVC with unusually full optimizations (i.e. including /Oy "omit frame pointers")

* And with adding a "v.reserve(1);" statement before the insert

* And with adding "#define _SECURE_SCL 0" and "#define _HAS_ITERATOR_DEBUGGING 0" statements

... then stepping through the insert statement shows that it runs through [only] 23 assembly language statements.

> That's a very very good point you are making and is something most STL advocates just don't get.

You might prefer a different data structure (which doesn't do range-checking on each call, for example) in a critical inner loop, but for general-purpose use it isn't bad IMO (i.e. I have other things to worry about ;-).
Christopher Wells Send private email
Friday, November 24, 2006
 
 
> This theory stuff continues to be important in real life.

A curiously your solution for solving it still works in real life too. Notice it's slow, do some research, fix it.
son of parnas
Friday, November 24, 2006
 
 
I agree with son of parmas. I haven't had to write a sort routine in years. Especially one that needed to be optimized to run as fast as possible. If I needed to do that tomorrow I would hit the web for two minutes and find information about what the tradeoffs are and which way would be best for my scenario. I sure as heck wouldn't try to pull it out of my ass based on teachings that I had over 20 years ago! Anyone who didn't spend a little time researching would be a candidate for a no hire in my mind. And let's not forget that pure performance is not always the most important factor. Maintainability is awfully important.

With that said the original candidate is still a no hire. Not because he/she couldn't pull a specific type of sort out of their butt. They are a no hire because their understanding of how a compiler works is fundamentally flawed.
anon
Friday, November 24, 2006
 
 
"There's a huge pool of developers out there toiling away with no clue about performance."

This is where a physicist, for example, can beat them, using the experience from writing even crude numerical programs for own use. The experience is that no matter what you *think* is performance-critical in your program, you still need to use some profiler and measure the time of execution for your routines on some typical datasets (define typical).
Roman Werpachowski Send private email
Friday, November 24, 2006
 
 
This is silly. You people are so binary it isn't even funny. Performance is a spectrum and not a simple true-false equation. No one is arguing that we should completely ignore performance. And anyone arguing that getting the best possible performance all the time is critical just doesn't understand that software is a business.

Get a grip and quit arguing over things that don't matter. Having the fastest possible sort doesn't always matter. Having one that's "good enough" and moving on is often much more important.
anon
Friday, November 24, 2006
 
 
The point I think of the original post, isn't to optimize the code in the interview, but that it revealed, in an amusing way, that the intervieweee didn't know basic computer science.
Sunil Tanna
Friday, November 24, 2006
 
 
Yes, it's a bit about that. When I asked "Would there be any performance problems with the sort method you're using?" a fair answer would be "Well, the bubble sort's the worst sort I can think of actually, but I couldn't remember how to do that other sort that's better for this problem set."

But it's more the reactionary or fake responses where the person has been reading slashdot and JoS and whatever and has picked up tidbits here and there but doesn't really understand much. They have the trick questions memorized but they don't have a lot of design or analysis skill.

The problem is that lots and lots of people have learned that in any discussion about optimization, rather than think about or understand the issues, you can fake being educated the same way that Eliza can fake being sentient by triggering off of keywords.

For example, if you hear the word 'performance' you randomly choose one of the following responses:

1. "Of course the compiler should optimize that."

2. "Rather than reinventing the wheel, any competent programmer such as myself would simply use the standard library function to solve that problem. To do otherwise is to waste the client's money."

3. "The most efficient way to handle these cases is to research them on the internet, and then choose the most appropriate solution."

Please notice that not one of these responses tells you anything at all about the candidate's capabilities, and often it is worth it to issue a couple followup questions which usually reveal that they are using these responses in order to fake being knowledgeable. We saw several cases of this happening even in this thread! :-) But seriously, you see this on slashdot and the internet all the time. People learn these generic 'appropriate responses' and spew them out, and it sounds all wonderful and insightful, but a little probing reveals it's all a facade.
Scott
Friday, November 24, 2006
 
 
> Actually, unless you're using CPython, standard library
> sort functions tend to suck.  If performance is
> important, replacing a standard library sort function
> with something domain specific can give you a big boost.

But, the thing is, the standard library sort function is likely to be "good enough" for most any case. And, when it isn't, you have to do research to find the right technique for your data.

And, in most cases, you'll not know if it is "good enough" until you do your performance testing.

So, the right answer is sort(), until it is demonstrated to be ineffective.
A Lackey
Friday, November 24, 2006
 
 
OK, so the vector solution produces thousands of lines of assembly.  Is there an alternative to compare to ?
x
Friday, November 24, 2006
 
 
X - yep a C style array
Sunil Tanna
Friday, November 24, 2006
 
 
>> So, the right answer is sort(), until it is demonstrated to be ineffective.

Well, I'll agree that "use the standard library sort" would've been a better interview answer than "use bubble sort".  However, once the interviewer tells the candidate that performance is important, that goes out the window.  It's just wrong to say you shouldn't worry about performance because "the compiler will optimize it" or "the standard library function will be good enough." 

I've seen this as a real world problem.  In one case, a developer was given the task of writing a specific component with the requirement that performance is important.  She came back with an implementation that used C's qsort to sort a large array of numbers.  Come on.  Developers should know better than that.  It would've been trivial to spend a few hours (tops) writing a faster sort but she went with qsort because of the myths that quicksort and standard library functions are the way to go.
SomeBody Send private email
Friday, November 24, 2006
 
 
Exactly!

I have heard and read several times lately that C arrays are obsolete and vectors are ALWAYS preferred as the 'modern replacement'. These assertions make me uncomfortable. Any questioning whether these claims are always true inevitably results in a lecture about how the incredible optimization done by the brilliant 200+ IQ minds that write all STL libraries means that it will always be every bit as fast as a C array and take the same amount of space, but so much safer and more expandable.
Scott
Friday, November 24, 2006
 
 
(that response was to S. Tanna)
Scott
Friday, November 24, 2006
 
 
> and more expandable.


Well, you know that they definitely are more expandable, because, ... um, ...  well, they expand.

And C arrays don't expand. This has the property of making C arrays somewhat less expandable than something that expands.

So I'm afraid that there isn't much comparison in the expansion department.


There are certainly plenty of cases where a C array is the right tool for the job. If you have a smallish number of things and you know that the number of things is fixed and _can't expand_, then it is perfect.


One of the really coolest things about the STL is that you can apply its algorithms to C arrays as well, there is a lot of compatability with C arrays.
Michael G
Saturday, November 25, 2006
 
 
1) You guys might want to have a look at the tr1::array template.  It's halfway between a C-style array and STL-style vector.  Also, I think part of the problem with the vector example given is that there's only one push_back() call -- not enough to amortize the cost of the heap allocation.  If you've reserved space in the vector enough ahead of time how many assembly instruction are actually executed by the push_back?  My guess is not many.  A more fair comparison would be against heap allocating space for an array with new, assigning that to a pointer, dereferencing that to put the number in the first slot, and the deleting the array.  I'd guess that if you checked the hardware performance counters for instructions executed, the results would be pretty close.  I'm not saying that the vector is without cost, but consider what you're getting for it.

2) Most STL sort() implementations now use the introsort algorithm.  Its worst case is O(n log n) and it's generally faster still than quicksort.  I'd be careful about blithely assuming that I could beat it without a lot of effort.  In some cases you might be able to with a bucket or radix sort, though.
Boojum
Saturday, November 25, 2006
 
 
> Well, I'll agree that "use the standard library
> sort" would've been a better interview answer
> than "use bubble sort".  However, once the
> interviewer tells the candidate that performance
> is important, that goes out the window.

Whoa, out the window?!?  I'm sure you're joking here, right?

Using the fully debugged standard sort that has well known and guaranteed algorithmic performance is a great answer.

Jumping to the immediate conclusion that the proper way to approach it is to completely reinvent the wheel and write your own sort is just awful... Danger Will Robinson!!!

There is a vast chasm between bubble sort and using the std (C++/STL) sort.

Unless there are unusual special considerations (like you're sorting something that can be bucketized or you have specific constraints such as needing to contain memory use or access), the most likely result of writing your own sort will be that you have to spend a bunch of time fixing bugs.
Michael G
Saturday, November 25, 2006
 
 
"but, the thing is, the standard library sort function is likely to be "good enough" for most any case. And, when it isn't, you have to do research to find the right technique for your data.

And, in most cases, you'll not know if it is "good enough" until you do your performance testing."

It really depends on exactly what line of work you are in. I've known folks who did kernel and server development and they had several of the standard sorting algorithms (among others) at their fingertips. They also knew the time/space complexities, and the input data peculiarities that made each of the methods relevant. In their line of work if you had to "research" something as standard and well worked out as sorting, you'd never have time to solve the really tricky problems. They used this stuff every day so it wasn't a matter of having to dredge up obscure lore from their data structures and algorithms classes.
Charles E. Grant
Saturday, November 25, 2006
 
 
"Actually he's right

Any good compiler ___should___ do that."

How?  The compiler is going to need more data.

Some sorts are stable.  Given two keys of the same value, a stable sort will keep them in the order.  Sometimes, this is needed.

A bubble sort is a stable sort.  A quick sort is not.

If the compiler automatically changes a bubble sort to a quick sort, it can introduce error.  That is not the sort of optimisation we need.

Sincerely,

Gene Wirchenko
Gene Wirchenko Send private email
Saturday, November 25, 2006
 
 
Wow, a lot of folks just don't get it.

"I'd be careful about blithely assuming that I could beat it without a lot of effort."

How could you even begin to make any assumptions it is best without some information about the state, format, quantity and disposition of the unsorted data?

This is exactly what I am talking about. Even after bringing up all this we have all the fakes and posers in here to tell us that their sort is always best, or that vectors are always better than arrays because they are expandable.

Sigh.
Scott
Saturday, November 25, 2006
 
 
Its bad to see taht candidate doesnt appreciate the difference between what can a compiler do and what it cann't ? In most of the case you actually dont have to do it urslef., but you should be able to see the difference
dhoom Send private email
Saturday, November 25, 2006
 
 
Yes, I agree. I'm not expecting someone to code any fancy sorts from scratch in an interview. When they do, sure, it's a very good sign. But when they can't talk about why you'd want to use one sort over another in different circumstances, or what the advantages and disadvantages of at least some sorts might be, that's not so good.
Scott
Saturday, November 25, 2006
 
 
> or that vectors are always better than arrays
> because they are expandable.

Wow, who said that?

You were complaining about people making unwarranted claims about vectors being "safer and more expandable" than C arrays.

Well, there is absolutely no doubt that a vector is indeed more expandable than a C array.

Do you have some confusion about this? I mean if you need to use an expandable array for something, would you actually choose to use a C array for it over a vector?
Michael G
Saturday, November 25, 2006
 
 
> Even after bringing up all this we have all
> the fakes and posers in here to tell us that
> their sort is always best

Yeah, darn those fakers Stepanov and Bjarne Stroustrup.

What a bunch of posers.

How could they think that a standard library sort would be anything but garbage. Obviously you have to write a new one by hand that is perfectly tuned for each individual situation. Anything else is just unthinkable.

And I've heard that even having the word "vector" in your comments is enough to bloat your program and cause 20 unexplained memory allocations and random crashes. You probably should avoid even talking about it.

LOL
Michael G
Saturday, November 25, 2006
 
 
Scott: "Any questioning whether these claims are always true inevitably results in a lecture about how the incredible optimization done by the brilliant 200+ IQ minds that write all STL libraries means that it will always be every bit as fast as a C array and take the same amount of space, but so much safer and more expandable."

This is humane nature. People usually prefer to minimize risk. Using a std::vector instead of an array minimizes risk at the expense of speed, that's why in a generic situation, a generic developer will prefer std::vector over a C array.
Roman Werpachowski Send private email
Saturday, November 25, 2006
 
 
s/humane/human
Roman Werpachowski Send private email
Saturday, November 25, 2006
 
 
"And I've heard that even having the word "vector" in your comments is enough to bloat your program and cause 20 unexplained memory allocations and random crashes. You probably should avoid even talking about it."

It will probably make your program go slower than using C arrays. Just made a quick test with filling arrays and C arrays beat std::vector by a factor of three, in my case. Just one datapoint.
Roman Werpachowski Send private email
Saturday, November 25, 2006
 
 
Boojum,

"2) Most STL sort() implementations now use the introsort algorithm.  Its worst case is O(n log n) and it's generally faster still than quicksort."

Introsort IS a Quicksort, switching to a Heapsort when a quadratic breakout is detected (usually done by the recursion depth).
Secure
Saturday, November 25, 2006
 
 
"It will probably make your program go slower than using C arrays. Just made a quick test with filling arrays and C arrays beat std::vector by a factor of three, in my case. Just one datapoint."


I bet the two pieces of code aren't exactly equivalent.
Jimmy Jones
Saturday, November 25, 2006
 
 
> How?  The compiler is going to need more data.

> Some sorts are stable.  Given two keys of the same value, a stable sort will keep them in the order.  Sometimes, this is needed.


Because the compiler, in 250 years time, will figure out the intent of the program, and whether a bubble sort can safely be replaced with a quick sort, in this particular case????

Maybe you missed the invisible flippant tags in my earlier post, or the fact that I pointed them out in a later post???
Sunil Tanna
Saturday, November 25, 2006
 
 
They're functionally equivalent.

The C array version:

const int N = 900000;

int main()
{
    int i, v[N];

    for (i = 0; i < N; i++) {
        v[i] = i;
    }
}


The std::vector using at():

#include <vector>

const int N = 900000;

int main()
{
    std::vector<int> v(N);

    for (int i = 0; i < N; i++) {
        v.at(i) = i;
    }
}


The std::vector using push_back():

#include <vector>

const int N = 900000;

int main()
{
    std::vector<int> v;

    for (int i = 0; i < N; i++) {
        v.push_back(i);
    }
}

All were compiled with g++ with -O2 optimization switch set. Both std::vector version were slower than the C array version.

I am 100% sure that these are very lousy tests but they do indicate a tendency.
Roman Werpachowski Send private email
Saturday, November 25, 2006
 
 
Maybe the compiler should be smart enough to fix your bugs as well...?

In fact, I think the compiler should probably be smart enough to write the code for you. All you give it is a bunch of half-formed pseudo-code and it does the rest.
Jimmy Jones
Saturday, November 25, 2006
 
 
I assume that I'm the worst programmer in the long line of programmers that starts with the CPU folks, goes through the compiler team, on down to me.

I assume that most of those people are working as close to the hardware as necessary and that the right closeness is determined through copious amounts of brains and experience.

I assume that the really important stuff has been in use long enough by enough people that it's virtually impossible for even a genius to find any improvements.

Strictly for fun and learning, I've implemented things like quicksort, bubblesort, binary search and have a basic understanding of some of the issues and trade-offs. But there's no way I'm ever going to beat the sort that is part of the library even if I know for sure that the library implementation is sub-optimal for a given situation. I might go looking for a different implementation that is optimal for a particular situation, but I'll never actually go write one myself. That would be as silly as me writing my own encryption--there is so much to go wrong and so much that has been done right that it simply makes no sense.

If you are looking for somebody to work further up the line (i.e. CPUs, compilers, etc.) then I'm not your guy. If you aren't doing that kind of work, then they guy who thinks he can (or really can) beat the system is probably  just an albatross around your neck.

And lest anyone think that I have unreasonable expectations regarding the ability a compiler to optimise something, here are the words I live by when I'm developing software and I suspect they apply to compiler optimisations, too:

The first rule of any technology used in a business is that automation applied to an efficient operation will magnify the efficiency. The second is that automation applied to an inefficient operation will magnify the inefficiency. (Bill Gates)
Ron Porter Send private email
Saturday, November 25, 2006
 
 
You are aware that .at() does range checking every time it is called?  try using [] access to the vector and see how it compares ... or try wrapping your c array accesses in range checks.
danielsn
Saturday, November 25, 2006
 
 
Ron.

I don't think you have written enough performance critical code if you assume the standard libraries are always better than what you can do.

Even an average programmer, can beat the standard libraries in most cases.  At least in C/C++ they can.

The reason:  The standard libraries are very flexible, and include a lot of checks.  STL vector is a good example, because it can do expanding arrays, has checks in it, etc.  Omit the flexibility and checks, and you can beat it.

Now, the most skillful part is (and even this can be done by average programmers using a profiler), of course, identifying the bottlenecks and knowing when to beat it.
Sunil Tanna
Saturday, November 25, 2006
 
 
I'm with you on that Tanna, it doesn't take an expert to beat the standard libraries. Especially with the STL, you might argue in the old days that if you wrote a custom class for every specialized thing, you'd have code bloat. But it can't be more bloated than including new code in every file that uses a function that should be generic, like an expanding macro header system does.

Now there will be along all the folks with their specialized instances of how if you 'weren't so ignorant and knew how to use the library it would be exactly the same', but first, as Roman pointed out above, that's not true, and second, there are lots of cases where even if it did make identical code, you are still forcing things into the STL design rather than finding the best solution.

For example, last month someone here pointed out that he has a expandible array class that kicks the ass of the STL. I have several of these classes myself. A LOT of cases where you have an array that needs to be expandible, you never shrink the array, and never insert things into the middle, etc. It's trivial to squash STL performance rather easily.

The folks who claim that you can't write a debugged quicksort or whatever so its a waste of time to ever do it miss Ron's good point that implementing this stuff and knowing its performance is something you should know how to do if you want to be a professional, just as a mathematician should know how to multiply and divide my hand even if he normally uses a calculator for this. Also they miss the point that not all programmers write crappy bug ridden code all day long and that those of us who don't shouldn't be restricted to using safe vanilla libraries like those who do.
Scott
Saturday, November 25, 2006
 
 
> I am 100% sure that these are very lousy tests but
> they do indicate a tendency.

It is true that it can be relatively easy in C++ for some things to be less performant than C if you don't pay any attention to what you are doing.

Is the moral of the story not to use C++? Well, no that is not the moral. The moral of this story is to pay some attention to what you are doing and do the basic things that avoid such problems.

For instance in your case you can get a huge performance boost in your push_back example by just adding a single line of code:

v.reserve(N);

The other example that uses v.at() will get a big boost if you just use the same v[i] syntax as you did for the array. Why would you use the .at() syntax instead of the more natural [] array syntax anyway? You really had to go out of your way here to reduce the performance intentionally.

You can even change the .at example to be like this:

    std::vector<int> v(N);
    int* pdata = &v[0];

    for (int i = 0; i < N; i++) {
        pdata[i] = i;

That uses a pointer to fill the vector. The actual fill portion of the code will be completely 100% absolutely identical code as using a C array, the only difference is the memory allocation during the creation of the vector.


The C array example is not very proper either, because you couldn't use that in a real program since it consumes a huge amount of stack space. In an actual program you would need to allocate that much memory off the heap instead.


Why would you do a performance test and not do even the most minimal performance best practices?
Michael G
Saturday, November 25, 2006
 
 
Holy fuck. Making those sorts of assumptions about the inner implementation of the vector is extremely poor practice.
Scott
Saturday, November 25, 2006
 
 
> STL vector is a good example, because it can
> do expanding arrays, has checks in it, etc.

Where did you get this idea from, the part about the checks certainly isn't correct.

In typical usage of a vector, the only single thing that is checked is if you run out of memory during an expansion.

Nothing else is checked unless you use a specialized .at() function which is not typically used. You are not forced to use .at(), you can use the simple and more natural array notation [] instead which is _not_ checked.

What types of checks did you think would happen if you used a vector? It is surprising that there is still this level of misunderstanding and phobia out there.
Michael G
Saturday, November 25, 2006
 
 
> Holy fuck. Making those sorts of assumptions about
> the inner implementation of the vector is extremely
> poor practice.

Uh no it isn't, that code is totally guaranteed to work according to the C++ standard. Vector memory is guaranteed to be allocated in one contiguous chunk just like an array.

This is so you can use it to interoperate with other stuff that wants to just work on arrays of memory.

There is plenty of stuff in STL that is set up like this, SPECIFICALLY SO THAT IT HAS GREAT PERFORMANCE THAT YOU CAN TAKE ADVANTAGE OF!
Michael G
Saturday, November 25, 2006
 
 
"I am 100% sure that these are very lousy tests but they do indicate a tendency."

It is indeed a lousy test; a better test would use a dynamic array in the C version.
...
Saturday, November 25, 2006
 
 
Michael G, give it up. It's clear you don't know what you are talking about.

Grabbing the address of an internal private member of a class for 'performance' reasons or to 'prove' it's the same as an array is BAD BAD BAD practice.

So, there you are off with your raw pointer, zooming through the array, when another user of the contained adds an element to the end. Whups! Now your pointer is pointing into dead space.
Scott
Saturday, November 25, 2006
 
 
You're right in that I haven't written much performance-critical code. So far, I've been more successful by taking different approaches than by beating the library. That said, I do know that I can beat the library if I have to, and have done so as part of my tinkering. But please don't ask me to sketch out a sort algoritm for memory :)

I've done enough exercises to know that if I'm running up against a peformance issue, it's because of the nature of the library, the nature of the problem, or the nature of my approach. Guess which one I'm betting on!

I guess the real point of what I was trying to say is that, for most of us, trying to the beat library should probably be left as an exercise or a last resort.
Ron Porter Send private email
Saturday, November 25, 2006
 
 
Michael, there's a pretty easy way to prove you're wrong on the general point.

If the STL vector really were just as efficient as the C-style array, how come the same functionality implemented in both is:  STL vector = thousands of assembly instructions,  C-style array = couple of dozen (at most) assembly instructions.


And you know what, even if there where the a compiler/library where it was just as efficient, the more general principle remains.... general purpose flexible code is nearly always less efficient than code than is designed that is designed for a specific purpose.

Here's a real world example that happened for me in an imaging application, when I using a flexible library (a well-known one) originally coded by somebody who is probably a better programmer than me.

Inside the library was code to draw pixels, using an X,Y coordinate.  It was fantastic.  Worked on any color depth or bitmap type.

Also inside the library was code to draw lines using bresenham's algorithm.  It was the best implementation of bresenham that you have ever seen.  Each pixel on the line was drawn using the pixel drawing function.

Also inside the library were functions to draw rectangles (by using the line drawing functions to join the 4 corners), and clear the whole bitmap (by setting each pixel on the bitmap using the pixel set function).

I wrote my initial code using them.  It was too slow by a couple of order of magnitudes.

Can you guess what I did?

I wrote my own less flexible versions of the functions, and I achieved the performance I needed.

In my code, I assumed 32bit bitmap, which was all my app needed to deal with.

I wrote a Fast_setpixel which was not as good/flexible as the original, but was faster.

I wrote a Horizontal Line, and Vertical Line functions.  Horizontal Line was just a memset.  Vertical Line could step thru pixels in memory, adding (4*scanline) to each offset.

Diagonal lines were still Bresenham, but using my fast but inflexible pixel routine.

Drawing rectangles?  Memset the horizontal top.  Memset the horizontal bottom.  Draw the verticals by stepping through memory in steps of 4*scanline, and setting the pixel pointed to, and that pixel+4*rectangle_width

Clear a bitmap - memset the whole thing

My code was less flexible than the library.... but throwing away flexibility usually allows you to improve performance.
Sunil Tanna
Saturday, November 25, 2006
 
 
<Off-Topic Question>

You say the library was really good. But wouldn't a really well designed library have let you substitute your specialized low-level functions for its general ones and still use its higher-level logic? There's no reason for you to reimplement Bresenham's algorithm when all you want to do is use the current one with a different setpixel function.

</Off-Topic Question>
Noah Lavine Send private email
Saturday, November 25, 2006
 
 
"The other example that uses v.at() will get a big boost if you just use the same v[i] syntax as you did for the array."

But then I don't have the supposed advantage of range checking by std::vector. Which even more underlines my point that you do have a speed-security tradeoff. The point of my examples was not criticize STL, I am a fan of such things from the system administrator's POV: I'd rather have my server perform 5% slower than have it have a buffer overflow exploited "for fun and profit". The point was to show that you

a) can't just follow blindly the standard libraries (c'mon, don't tell me that v[i] syntax for std::vector)
b) you can' have your cake and eat it, or have both maximum security and maximum speed.

Besides, I did now compare the C array with std::vector using the [] access. The STL vector still takes 60% more time to fill. As Sunnil wrote, the generated assembly code resembles nothing of the clean and short loop generated by simply using C arrays. So even using v[] with std::vector<int> v(N) doesn't give you the performance of the ordinary C arrays, malloc'ed or not malloc'ed. So I ask you: if we aim for performance, what's the point of using std::vector, if it is slower than C arrays even in its "performance mode"?

"It is indeed a lousy test; a better test would use a dynamic array in the C version."

"The C array example is not very proper either, because you couldn't use that in a real program since it consumes a huge amount of stack space. In an actual program you would need to allocate that much memory off the heap instead."

I know and I wouldn't use this code in any real software. However, in terms of performance there is no difference. malloc allocates the memory in one piece, so the time it takes to fill the array does not depend on whether it is static or dynamic.
Roman Werpachowski Send private email
Saturday, November 25, 2006
 
 
Point a) should have, in parens: "(c'mon, don't tell me that v[i] syntax for std::vector is the standard way of using std::vector)".

And yes, I know that you have the advantages of std::vector being a class with a destructor.
Roman Werpachowski Send private email
Saturday, November 25, 2006
 
 
> Michael G, give it up. It's clear you don't
> know what you are talking about.

Scott, I'm afraid that you're showing exactly the opposite of this.


> Grabbing the address of an internal private member
> of a class for 'performance' reasons or to 'prove'
> it's the same as an array is BAD BAD BAD practice.

This is not illegally grabbing some private member, it is using the public interface of the vector and grabbing the address of the first item in it.

This is totally legal C++, in fact vector is designed to allow such access and it is explicitly stated that this is allowed in the standard.


> So, there you are off with your raw pointer,
> zooming through the array, when another user of
> the contained adds an element to the end. Whups!
> Now your pointer is pointing into dead space.

Oh my god - you mean that if you took the couple of lines of code that I wrote for one function and slap them into somewhere totally different it might not work?

Oh no! How can the be possible?

Here is a clue - different pieces of code need to fit with different conditions when they are used. There are a zillion circumstances where you can't just take a chunk of code and slap it somewhere else without thinking.

Why do you think this is some extraordinary thing?

When you grab the pointer to the vector you should only use it when you know the vector will not be freed or reallocated.

THIS IS ABSOLUTELY THE SAME WITH ANY KIND OF DYNAMICALLY ALLOCATED MEMORY!!!
Michael G
Saturday, November 25, 2006
 
 
> Point a) should have, in parens: "(c'mon, don't
> tell me that v[i] syntax for std::vector is the
> standard way of using std::vector)".

Of course it is the standard way, that's why it uses the most familiar syntax.

Why would you think differently?

You don't typically use vector to get range checking, you typically use it to handle dynamic memory allocation and cleanup for you.
Michael G
Saturday, November 25, 2006
 
 
> You say the library was really good. But wouldn't a really well designed library have let you substitute your specialized low-level functions for its general ones and still use its higher-level logic?


Well it didn't. 

But then I didn't design the library, so I don't have to make excuses for it :-)

I neverd measured that the effect of having an extra layer of indirection on the function calls (because that wasn't how the code was to start with), so I didn't know if the extra overhead (in terms of speed) would have been noticeable or negligible.  I suspect, given the number of times some of these functions were called, it would probably have been noticeable.... I inlined some functions too, and this did make noticeable differences.


BTW, don't underestimate the sales advantage of a speed advantage over competitors when selling s/w.  It can be worth big $, so this isn't all academic.
Sunil Tanna
Saturday, November 25, 2006
 
 
> Michael, there's a pretty easy way to prove you're
> wrong on the general point.
>
> If the STL vector really were just as efficient as
> the C-style array, how come the same functionality
> implemented in both is:  STL vector = thousands of
> assembly instructions, C-style array = couple of
> dozen (at most) assembly instructions.

Sigh...

Let's compare the loops of the above examples (compiled with VC7.1):

C-Style array:

    for (i = 0; i < N; i++) {
0040100A  xor        eax,eax
        v[i] = i;
0040100C  mov        dword ptr [esp+eax*4],eax
0040100F  inc        eax 
00401010  cmp        eax,186A0h
00401015  jl          main+0Ch (40100Ch)


std::vector inner loop with typical [] syntax:

    for (int i = 0; i < N; i++) {
0040166D  mov        ecx,dword ptr [esp+8]
00401671  xor        eax,eax
        v[i] = i;
00401673  mov        dword ptr [ecx+eax*4],eax
00401676  add        eax,1
00401679  cmp        eax,186A0h
0040167E  jl          main+23h (401673h)


Wow, look at the difference!

If you're comparing the setup, that's comparing apples to oranges, std::vector is allocating memory from the heap and the C array is allocating memory from the stack which is cleaner but can only be used for very limited amounts.

If you need a relatively short, fixed sized array then sure, definitely use a C array, it is the right tool for that job. It is more efficient, primarily because grabbing a small chunk of stack memory is more efficient than doing the more complex heap allocation.

If you need a larger array, or need something that resizes, then use a vector for general purpose use.

Once you have your data stored in your vector, it is very efficient to access it, as the above disassembly proves.
Michael G
Saturday, November 25, 2006
 
 
> My code was less flexible than the library.... but
> throwing away flexibility usually allows you to improve
> performance.

Sure, it is worthwhile to apply special attention to code that is handling millions of items or large quantities of data. Especially through profiling you can identify bottlenecks and do custom things to solve the bottlenecks.

But this does not apply to every single bit of code in your application - every single bit of code (in fact the majority of your code) is not handling massive amounts of data or is in a critical inner loop.

For the majority of your code, the general-purpose tools work great.

The big bonus with STL is that even though it is general purpose, it was designed with excellent performance in mind as well (especially algorithmic performance) which helps to reduce the number of times that you have to do special-purpose code.

The thing I find ridiculous (but all too common apparently) is this concept that STL is terrible and has to be completely avoided because it will generate a bunch of performance problems everywhere.
Michael G
Saturday, November 25, 2006
 
 
> As Sunnil wrote, the generated assembly code
> resembles nothing of the clean and short loop
> generated by simply using C arrays.

Wrong. Look at the assembly for the loop that I posted above - they completely resemble each other right down to the exact same number of instructions generated in the inner loop.

You must be doing something wrong to be getting such different results.


> I know and I wouldn't use this code in any real
> software. However, in terms of performance there is
> no difference. malloc allocates the memory in one
> piece, so the time it takes to fill the array does
> not depend on whether it is static or dynamic.

How are you measuring the time elapsed for the filling? The code you provided is not taking any measurements before or after the loop.

If you are measuring the entire program run time, then you are also measuring the cost of doing the setup including the dynamic memory allocation. It definitely takes more time to do a dynamic allocation than a stack allocation, the code for doing a dynamic allocation is far more complex.
Michael G
Saturday, November 25, 2006
 
 
Well Michael, you are gradually converting to our side of the fence while claiming that's what you meant all along, and trying to obfuscate that fact by claiming we said things we didn't say. I guess that's called reframing the debate now? Or is there some other term for it, I try not to get involved in the latest political weasel tactics.

Your remaining argument that you can't allocate a lot on the stack is incorrect - I've allocated 1GB and up on the stack with no problems. Heap-stack collisions simply don't happen on modern systems anymore.

Your argument that you can disregard setup time and code is simply disingenuous.

And your claims that its safe and recommended (WTF) to take a pointer to an class's internal structures and operate directly on them is simply ignorant.
Scott
Saturday, November 25, 2006
 
 
> Your remaining argument that you can't allocate
> a lot on the stack is incorrect - I've allocated
> 1GB and up on the stack with no problems.

Surely you're joking here. Are you on some kind of completely special purpose hardware or something?


> Your argument that you can disregard setup
> time and code is simply disingenuous.

Not at all - in a test to find out how quickly something can be filled up, it is important to test the filling up time and not something other than the filling up time.

This like your previous argument that a vector is not more resizeable than a C array.

When testing fill-in time, you should measure fill-in time and not something else.


> And your claims that its safe and recommended (WTF)
> to take a pointer to an class's internal structures
> and operate directly on them is simply ignorant.

You seem to be having some problem understanding this part.

I am not taking a pointer to the class's internal structure, the class holds an object and I am taking the address of that object. That's all, there is no poking around in the vector's internal implementation or anything.

What part of "guaranteed by the C++ standard" is confusing to you here?
Michael G
Saturday, November 25, 2006
 
 
"Wrong. Look at the assembly for the loop that I posted above - they completely resemble each other right down to the exact same number of instructions generated in the inner loop."

I looked at the inner loops generated by my compiler too, and they are almost identical (the additional code in the STL version happens before/after the loop, so let's count it as STL overhead). You can see now that a small difference in a simple loop gives significant difference in performance ;-)

"If you are measuring the entire program run time, then you are also measuring the cost of doing the setup including the dynamic memory allocation. It definitely takes more time to do a dynamic allocation than a stack allocation, the code for doing a dynamic allocation is far more complex."

The C array code (total code, I didn't bother to put time measurements in the code, but I'll do it later) is still faster than STL after I tell it to allocate the memory dynamically.
Roman Werpachowski Send private email
Saturday, November 25, 2006
 
 
"What part of "guaranteed by the C++ standard" is confusing to you here?"

"Guaranteed" as in "guaranteed not to change" or merely "guaranteed to exist"?
Roman Werpachowski Send private email
Saturday, November 25, 2006
 
 
"The C array code (total code, I didn't bother to put time measurements in the code, but I'll do it later)"

OK: so the filling time is equal. But the overhead is significant (ca 0,5s) , and I declared the vector only once!

So if one would have to deal with thousands of arrays, the overhead might be a problem, even if simple operations through [] will run just as fast.
Roman Werpachowski Send private email
Saturday, November 25, 2006
 
 
> "Guaranteed" as in "guaranteed not to change"
> or merely "guaranteed to exist"?

Both. As much as anything else is guaranteed anyway.
Michael G
Saturday, November 25, 2006
 
 
***
And your claims that its safe and recommended (WTF) to take a pointer to an class's internal structures and operate directly on them is simply ignorant.
***

I'm with Micheal G on this one.

The std::vector is designed to be completely backwards compatible with a C array. There's nothing wrong with that.

If you need a very fast sort, you can simply pass a vector, or an iterator to the magic sort function, which can then take advantage of assumptions such as consecutive memory. This allows for a clean interface and low-level fast code at the same time. Contrary to the pure C alternative.

The entire C++ language and the STL is designed with efficiency in mind, and people have gone to great length to make sure programmers have the flexibility to do whatever it takes to get the job done, without having to abandon the STL altogether.

Take std::map for instance. The std::map iterator doesn't invalidate when you insert a new element into the map, but an std::vector does. So the whole argument about other code that "might break" because the vector may resize (and thereby invalidate the pointer) shows a fundamental lack of STL experience. Iterators to vectors invalidate, just like real pointers do.

The STL may be ugly, the STL may be unpredictable, but it *is* fast. The only way to get code that is significantly faster than the STL is by dropping constraints the STL algorithms adhere to. They are general purpose algorithms after all. If the general STL overhead, tiny as it is, is too expensive for you, you shouldn't be coding in C++ in the first place, but in C instead.
Barney
Saturday, November 25, 2006
 
 
> So if one would have to deal with thousands of
> arrays, the overhead might be a problem, even
> if simple operations through [] will run just
> as fast

A large number of heap allocations tends to become one of the major bottlenecks, regardless of whether the STL vector is doing them or whether you're doing them manually with malloc().

So in the situation you describe, switching from std::vector to manual allocation is extremely unlikely to solve the problem, you have to redesign the data structures to do fewer allocations overall, such as making things look at small regions within larger chunks.
Michael G
Saturday, November 25, 2006
 
 
Yes, you're right. Malloc fragmentation would be a major problem indeed.
Roman Werpachowski Send private email
Saturday, November 25, 2006
 
 
"This like your previous argument that a vector is not more resizeable than a C array."

We are finally coming back to the original point of this thread. Bullshit artists. Like you, Michael. People who don't understand even the basics, but who know how to spew bullshit. I'm so sick of interviewing these fools who can't program their way out of a paper bag and yet who are masters of spreading shit. You guys are the ones that take down projects, that make them late, that make the good people leave while you surround yourself with more bullshit artists spewing nonsense. You have nothing constructive to add because you don't understand the issues, so you just start saying a bunch of crap that isn't true in an attempt to misdirect attention from your own ignorance.

Thanks for bringing us back on topic.

> What part of "guaranteed by the C++ standard" is confusing to you here?

You must be talking about that 'other' C++ standard.
Scott
Saturday, November 25, 2006
 
 
Scott, your freakout about taking the address of the first item in a vector sadly proves that you are ignorant about many issues about using the STL.

It seems like you have some sort of phobia about it.

This is doing you nothing but harm, you should get over it, that could be a major step in improving your skills to the next level, it really seems to be that you are a bit stuck in a rut right now. That certainly happens to a lot of people.

Just sticking your head in the sand and calling other people names is not an effective way at improving your skills.
Michael G
Saturday, November 25, 2006
 
 
I've been looking at my C++ references (including the most recent draft version: http://www.open-std.org/jtc1/sc22/wg21/docs/projects#14882) and I can't find any guarantees regarding consecutive allocation of vector memory.

I've read about vectors being consecutive in many places, and I've even based code on this assumption, but now it seems it may be a myth after all.
Barney
Saturday, November 25, 2006
 
 
On the other hand, the C++ faq seems to confirm that the contents *are* consecutive:

http://www.parashift.com/c++-faq-lite/containers.html#faq-34.3

Well... if the faq authors have double-checked their sources, that is.
Barney
Saturday, November 25, 2006
 
 
Quote from the C++ standard:

<< Begin quote >>
23.2.4 Class template vector [lib.vector]

1
A vector is a kind of sequence that supports random access iterators. In addition, it supports (amortized) constant time
insert and erase operations at the end; insert and erase in the middle take linear time. Storage management is handled
automatically, though hints can be given to improve efficiency. The elements of a vector are stored contiguously,
meaning that if v is a vector<T, Allocator> where T is some type other than bool, then it obeys the identity &v[n]
== &v[0] + n for all 0 <= n < v.size()."

<< End quote >>
Barney
Saturday, November 25, 2006
 
 
> I've been looking at my C++ references

Here is a link with some details and references:

http://groups.google.com/group/comp.lang.c++/browse_thread/thread/8eadc19db7f52fd8/60dde8b03783d350?lnk=st&q=vector+contiguous&rnum=1&hl=en#60dde8b03783d350

One quote:

    A vector's storage is guaranteed to be contiguous. From ISO 14882, 2nd ed., 23.2.4 [lib.vector]:

"The elements of a vector are stored contiguously, meaning that if v is a vector<T, Allocator> where T is some type
other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size()."


Note that this is in the updated version of the standard.
Michael G
Saturday, November 25, 2006
 
 
It's also mentioned in Sutter and Alexandrescu's "C++ Coding Standards", pg. 153:
 
"vector's storage is always continuous, so accessing the address of its first element returns a pointer to its contents.  Use &*v.begin(), &v[0], or &v.front() to get a pointer to v's first element. ... When you pass pointers into a vector v's data, C code can both read from and write to v's elements but must stay within size's bounds."
Boojum
Saturday, November 25, 2006
 
 
Michael, you are exactly the same as the guy I interviewed in my first post to this thread. I see right through you.

A lot of companies wonder why someone sounds good in an interview and then when they hire the guy he is a total dud that can't write code and does nothing but cause troubles on the team, backstabbing other members, creating political turmoil, and jockeying for a project management position by taking credit for the work of others without ever having demonstrated any capability.

Guys like you are good at what you do - politics.

And it's hard to discern what's what in an interview, and nearly impossible to tell on the internet when someone can take their time to respond, do some quick googling, call their friends, and do other things that would reveal what is up during an interview.

But you've said enough to tip your hand and I see your game, I know you are a fake. You are very good at faking it, but I have seen so many of your kind that I can tell.

In addition to your tipping your hand, you've tried to dominate the discussion not through providing solid technical information that you yourself are knowledgeable about, but you have instead tried to:

- reframe the debate
- backpedal
- use straw man arguments

This stuff is just divisive politics in lieu of actual technical capability. And it's why Microsoft can't deliver solid software anymore - 3/4 of their developers now are guys just like you.
Scott
Saturday, November 25, 2006
 
 
By the way, using a raw array:

static const int N = 1000000;
int main( int argc, char **argv )
{
    int v[ N ];
    for ( int i = 0; i < N; ++i )
        v[ i ] = i;
}

and the standard library's tr1::array class:

#include <tr1/array>
static const int N = 1000000;
int main( int argc, char **argv )
{
    std::tr1::array< int, N > v;
    for ( int i = 0; i < N; ++i )
        v[ i ] = i;
}

compile to identical binaries on my machines when full optimizations are turned on.
Boojum
Saturday, November 25, 2006
 
 
> Michael, you are exactly the same as the guy I
> interviewed in my first post to this thread.
> I see right through you.

LOL!!!

Yup, just review my posts to find them chock full of all kinds of fake stuff like disassembly and quotes from the C++ standard.

Damn, referring to the C++ standard, what a poser, doesn't he know anything about C++ at all?  LOL!!!

With the additional quotes and information from other people, you still don't believe that you're wrong to freak out about getting a pointer into the vector?  Wow, talk about denial.

Your escalating ad hominem attacks aren't doing you any favors convincing people, you're just appearing increasingly desperate to avoid the technical details you were wrong on.

There's something you should learn from this - don't make a big stink about something you haven't studied and aren't comfortable with, you're just likely to stick your foot in your mouth.
Michael G
Saturday, November 25, 2006
 
 
Michael, I see through you. Development is more than google and pasting.
Scott
Saturday, November 25, 2006
 
 
You started off with a valid point, Scott. There are many misinformed programmers. Unfortunately, the points that Michael has made are pretty basic facts about STL programming. They're not things that someone who has used the library would need to google for.
Seth
Saturday, November 25, 2006
 
 
Scott, there posters other than MichaelG in this thread, even if you pretend that they don't exist, and they agree with Michael, not with you.  They also present sound technical arguments, unlike you...
Chris Nahr Send private email
Sunday, November 26, 2006
 
 
Wow! Some religious wars...

I checked if vector is linear or not.
Turns out that it is linear, so you can get the pointer to any element and access other elements by just moving the pointer.

Here is my code, if someone is interested.

===
#include <Windows.h>
#include <vector>

// -------------------------------------------------------------------------
#define N 0x10000

// -------------------------------------------------------------------------
int WINAPI WinMain (HINSTANCE, HINSTANCE, LPSTR, int)
{
    std::vector <int> a (N);
    int* aOriginal = new int [N];

    if (! aOriginal)
    {
        return -1;
    }

    // Fill the vector and allocated copy

    srand (GetTickCount ());
    for (int i=0; i<N; i++)
    {
        a [i] = rand ();
        aOriginal [i] = a [i];
    }

    int* pElement = & (a [0]); // Linear pointer
    int* a2 = new int [N]; // New copy to move values into

    if (a2)
    {
        // Move the values, using linear pointer

        for (int k=0; k<N; k++)
        {
            a2 [k] = pElement [k];
        }

        // Now, check if any values are not in place

        if (memcmp (a2, aOriginal, sizeof (int) * N) == 0)
        {
            _asm int 3 // vector IS linear! (It stops here)
        }
        else
        {
            _asm int 3 // vector IS NOT linear!
        }

        delete [] a2;
    }

    delete [] aOriginal;
    return 0;
}
===
asmguru62 Send private email
Sunday, November 26, 2006
 
 
Uhm... you only checked whether your IMPLEMENTATION is linear. All implementations pretty much are, we knew that. The question was whether the C++ standard mandates it is, or not. That gives reasonable guarantees w.r.t. portability.

It turns out that it had always been Stroustrup's intention to have arrays backwards compatible with C arrays, but he didn't mention it explicitely in the Standard. In recent versions of the standard it is set in stone.
Barney
Sunday, November 26, 2006
 
 
Of course, I forgot to mention the compiler: C++ from VS 2005.
asmguru62 Send private email
Sunday, November 26, 2006
 
 
It doesn't really matter what a single implementation does in the grand scheme of things. If the Standard sais it's wrong, it's wrong - regardless of Visual Studio.

In this case the Standard sais it's OK, so it's OK, regardless of MS's STL implementation (which is of dubious quality, but that's another topic).

This isn't really a religious war either, as you mentioned earlier.

With VIM/Emacs, it's a matter of preference - would you rather have modes or ctrl-shortcuts. But this discussion isn't about opinion or preference, it's about facts that can be checked.

The thing is, this discussion is getting kind of difficult because a certain somebody seems immune to logical arguments, including direct quotes from the C++ standard itself.
Barney
Sunday, November 26, 2006
 
 
> Bjarne Stroustrup says it takes constant time to access a vector element and that implies contiguous storage but I just wanted to double-check.

Ignoring the updated standard <grin>, there's another way to implement constant access time: implement it like ...

template<class T>
class alt_vector
{
  const SlabSize = 1000;
  typedef vector<T*> Vector;
  Vector m_vector;
  int m_lastSlabSize;
  T& operator[](size_t index)
  {
    T* slab = m_vector[index / SlabSize];
    return slab[index % SlabSize];
  }
  void push_back(T t)
  {
    //see if there's room in the last slab
    if (m_lastSlabSize < SlabSize)
    {
      //there's room in the last slab
      T* slab = m_vector[index / SlabSize];
      slab[m_lastSlabSize++] = t;
    }
    else
    {
      //need to allocate a new slab
      T* slab = new T[SlabSize];
      m_lastSlabSize = 0;
      slab[m_lastSlabSize++] = t;
      m_vector.push_back(slab);
    }
  }
}

... the advantage of this being that push() is far more efficient:

* Only one push in 1000 requires a new heap alloc
* The new heap alloc does occur, it needs to copy 1000 times less data from its old strage into its new one.
Christopher Wells Send private email
Sunday, November 26, 2006
 
 
The slab solution is nice, but it will be inefficient when the size of the slab is tiny compared to the size of the array. Because the slab size is a constant, your program has the same big-oh characteristics when you take slabs of size 1. Obviously, now you do an alloc for every element you push to the array, which is very bad indeed.

The array now grows by a constant factor, which means an array of size N will have N / sizeof(slab) new calls. This is hugely inefficient when you want to allocate large amounts of data.

The slabs themselves have to grow in order to prevent this from happening. What you get is probably a bit like a rope-structure, I think. (Not quite sure about that.)

Also, if you have slabs then it's unclear how you should deal with boundary cases. E.g. repeatedly add and remove an element on a slab boundary - will that result in allocation trashing? If not, then there's a bunch of corner cases to take care of. And how about copy constructors, do you want a copy to allocate the slabs one-by-one, then copy the internal values?

Rolling your own container is way too much work for a small improvement in performance, if you ask me.
Barney
Sunday, November 26, 2006
 
 
> The slab solution is nice

Thank you. :-)

> Rolling your own container is way too much work for a small improvement in performance, if you ask me.

You're right. I only did it once, for a big improvement, for a specific use case:

* Millions of elements to begin with
* Want an average O(1) time to insert new elements
* Want O(1) time to index elements
* Know approximately (to within an order of magnitude or two) the likely maximum number of elements (so I could do "m_vector.reserve(MaxExpectedElements/SlabSize);")
* No need to implement a copy constructor or an assignment operator
* No need to implement removing elements
Christopher Wells Send private email
Sunday, November 26, 2006
 
 
The std::deque container is implemented in a similar slab-like fashion.

The general idea is the same, but it is implemented slightly differently because it will also add slabs to the front as well.

There are times when it can be better to use a deque than a vector because of the way it expands in chunks like this - during expansion it doesn't have to copy all of the previously existing stuff in the container to the new array like vector needs to. So for stuff that is expensive to copy this can be good.

Also for dealing with really large sequences, it can be easier on the memory manager to only need to grab small chunks instead of having to get one really huge chunk.

Meanwhile it preserves constant time index-based access like a vector (with somewhat more overhead though).
Michael G
Sunday, November 26, 2006
 
 
+1 Michael G

And here's a quotation for our friend Scott to think about:

"There's nothing so tragic as the murder of a beautiful theory by a gang of brutal facts."

Well, I'd better get back to work now.  I'm writing a list forum server program that optimizes out all stupid, unresearched flames.
Anon for this one
Sunday, November 26, 2006
 
 
Scott,
Perhaps you as the interviewer have failed to picture the complexity and size of the problems your company has to solve?

Perhaps you should have asked the candidate whether he knows any other, faster, sorting algorithms which are better suited for much larger datasets instead of asking "if there might be any performance problems with that method of sorting". Would you ask him the same if he outlined a radix sort instead of bubble sort?

Anyway, knowing dozen different sort algorithms off the top of one's head IMO should not be the hiring condition.

Anyone can look up those algorithms on the Internet and happily copy/paste them into the project. Actually that is what most programmers will do given the chance. Point is to find someone who can at least understand the code he just copied and use it properly.
Igor
Tuesday, November 28, 2006
 
 
No that's not the point. This is proprietary software. If someone cuts and pastes code off the internet, they are dismissed immediately.
Scott
Tuesday, November 28, 2006
 
 
"Anyone can look up those algorithms on the Internet and happily copy/paste them into the project. Actually that is what most programmers will do given the chance. Point is to find someone who can at least understand the code he just copied and use it properly."

I would think being able to explain the possible performance issues of the sort you just coded would fall under "understanding the code". I think Scott's question addressed that point in a very direct fashion. Assuming the OP is based even loosely on reality the interviewee would likely have just copied and pasted the first "working" sort found without any understanding of what they were doing.

From what I can tell the knowledge of a dozen, or even one, sorting algorithms was not the problem. The problem was thinking that the compiler would magically optimize the bad algorithm away. Without knowing the technical name of the sort the candidate should have at least taken a few minutes to look at the algorithm and maybe try some small input sets to figure out where a problem might be. Maybe try a couple simple cases like a list in entered  in sorted order, a list entered in reverse order, then, hey, wait, a list in reverse order takes A LOT of work to sort. Hmmm.... If the candidate thought the compiler would magically optimize the sort he wrote, what makes you think that he would know what kind of sort he coded and if there were better alternatives?

Boy did this thread take one hell of a turn. Regardless of the knits about deques vs. vectors vs. C arrays, I don't see how anybody who considers themselves even a mediocre developer could possibly find any fault with Scott dismissing the candidate. That's fundamental stuff. Any kid out of school should have been able to nail that without any trouble and any senior developer, even if he forgot all the names and performance characteristics of the various sorts, should have been able to analyze what he wrote in a few minutes and find some problem areas if asked.
Bart Park
Tuesday, November 28, 2006
 
 
Bart, thank you for your thoughtful post. Yes, that all is true. One big motivation for my post though was the observation of how interviewing is made more difficult nowadays because of people who have rather sophisticated mechanisms for faking knowledge.

As we all know, many developers, especially those working at big outfits, spend most of the day surfing the internet and/or goofing off. Perhaps this replaces time formerly spent in useless status meetings. A lot of these workers do so because they are not really sure how to proceed with the work that is their responsibility. So they goof off, and then work politics to place blame for failure on other workers and circumstances, while taking credit for anything that other developers do manage to accomplish. How these guys make it and get hired is by faking technical competence. Learning how to fake competence is much easier than learning how to be a good developer and the pay is the same! Actually the pay is better since the fakes always try to work their way into management positions, where their lack of knowledge will likely never be discovered. This is how prototypical PHBs are born and is a manifestation of the Dilbert Principle, that incompetent workers are promoted.

The scam is very easy to work. You just read Slashdot, and JoS and CodingHorror, and memorize "commonly known facts," which are repeated endlessly by the denizens of these fora. Examples of tactics, as I've said, are that any questions about performance should be responded to with a haughty self-righteous attitude and statement that the compiler will deal with performance issues, or that one should just use a standard library because the people who wrote that are 'smarter than you' and 'can not be improved upon'.

Because of the success of this tactic, many of these self-righteous incompetents come with sterling letters of recommendations and truly impressive resumés, with long lists of accomplishments of miracles and situations where they saved the companies they worked for.

Interviewing nowadays is now not so much a problem of eliminating those who aren't a good fit, but is now an issue of seeing through the various charades and dog and pony shows.

You have to be able to look for small mistakes and then issue follow up questions that trap them. Any one can make a mistake, but its the follow up questions where you find out if they are following a script they memorized off the net or not.
Scott
Tuesday, November 28, 2006
 
 
Feeling a little bitter today Scott?  It must be hard being the best coder on the planet.
danielsn
Tuesday, November 28, 2006
 
 
How about sharing a link to your job posting Scott?  It'd be interesting to see how you describe the position.  It's as tough and important to write an effective job posting as it is to write a good resume.

Mike R.
Mike Rossetti Send private email
Wednesday, November 29, 2006
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz