Speed differences in using arrays/linked lists in stacks/queues/etc..

[AFB]

I know the OOP version would be slower, but by how much?

 

[Argo]

As a programmer you should not concern yourself with such issues. Unless every CPU cycle is critical speed difference will be negligible.

 

[DaveSimmons]

Unless you're John Carmack hand-tuning 3D engine code to work acceptably on lousy gf4mx cards, you should normally only be concerned with the O() time of the algorithm, e.g. know not to use bubble sort or linear search.

Even that isn't always true. Linear search makes perfect sense for small values of n since the code is cleaner and easier to maintain and speed usually does not matter searching 100 items.

 

[kamper]

I agree. The biggest challenge in sofware development isn't getting the program to run fast enough, it's getting it free from mistakes and errors with minimal development time. Even if speed is a concern, it's probably better to focus on higher level things like algorithmic complexity rather than things that are absolutely separate from the business logic.

Of course it doesn't hurt to know a little about low-level optimizations and it can be fun If you're comparing C to, say, java I'd bet there's not a whole lot of difference when using arrays. I read an article a while ago (can't remember where) that argued that java can be faster is some situations because the runtime environment can dynamically optimize for things like processor cache size.

I assume that in an oo language you're implementing linked lists with regular objects so that'd probably be quite a bit slower since you're dealing with object construction/destruction and all the back-end stuff that comes with it (classloading, for example). Of course I have no authority on how much of a difference it would make.

You're not looking at reimplementing stacks and queues in java are you?

 

[AFB]

Originally posted by: kamper
You're not looking at reimplementing stacks and queues in java are you?

Why?


The only problem I have noticed with array based stacks/queues it that they aren't expandable beyond the initial size. Anyway, I am a why/how person so I sometimes just want to know how it works

 

[kamper]

How else do you propose to implement a stack if not with an array? (well besides a linked list...) Vectors are array based and Stacks are Vector based. They just manage array resizing behind the scenes. There's a great example of where algorithm design can affect performance. A Vector has to be able to choose an optimal resizing plan for a variety of different usage patters which the writers couldn't possible know of before hand. I could see reimplementing a the idea of a Vector if you had a very specific, time-critical usage pattern if you could make some good situation-specific optimizations.

 

[AFB]

Originally posted by: kamper
How else do you propose to implement a stack if not with an array? (well besides a linked list...) Vectors are array based and Stacks are Vector based. They just manage array resizing behind the scenes. There's a great example of where algorithm design can affect performance. A Vector has to be able to choose an optimal resizing plan for a variety of different usage patters which the writers couldn't possible know of before hand. I could see reimplementing a the idea of a Vector if you had a very specific, time-critical usage pattern if you could make some good situation-specific optimizations.

Every once and a great while, you need to know how something is impemented. Often when I need a queue for a specific thing, I use a linked list and specify the object allowed to be enqueued. Then you don't need to cast . Anyway, you won't need to do this with templates

 

[Armitage]

Originally posted by: DaveSimmons
Unless you're John Carmack hand-tuning 3D engine code to work acceptably on lousy gf4mx cards, you should normally only be concerned with the O() time of the algorithm, e.g. know not to use bubble sort or linear search.

Even that isn't always true. Linear search makes perfect sense for small values of n since the code is cleaner and easier to maintain and speed usually does not matter searching 100 items.

What kind of programming do you guys do that performance is such a non-issue? I tend to be fairly obsessed with performance, but then, it's not unusual for stuff I'm working on to run a week or two on our cluster.

 

[AFB]

Originally posted by: Armitage

Originally posted by: DaveSimmons
Unless you're John Carmack hand-tuning 3D engine code to work acceptably on lousy gf4mx cards, you should normally only be concerned with the O() time of the algorithm, e.g. know not to use bubble sort or linear search.

Even that isn't always true. Linear search makes perfect sense for small values of n since the code is cleaner and easier to maintain and speed usually does not matter searching 100 items.

What kind of programming do you guys do that performance is such a non-issue? I tend to be fairly obsessed with performance, but then, it's not unusual for stuff I'm working on to run a week or two on our cluster.

Say you had to order the items in a drop down list. Performance isn't going to mean much

 

[Armitage]

Originally posted by: amdfanboy

Originally posted by: Armitage

Originally posted by: DaveSimmons
Unless you're John Carmack hand-tuning 3D engine code to work acceptably on lousy gf4mx cards, you should normally only be concerned with the O() time of the algorithm, e.g. know not to use bubble sort or linear search.

Even that isn't always true. Linear search makes perfect sense for small values of n since the code is cleaner and easier to maintain and speed usually does not matter searching 100 items.

What kind of programming do you guys do that performance is such a non-issue? I tend to be fairly obsessed with performance, but then, it's not unusual for stuff I'm working on to run a week or two on our cluster.

Say you had to order the items in a drop down list. Performance isn't going to mean much

Well yea. If that's all I did in programming though, I think I'd rather dig ditches

 

[DaveSimmons]

Originally posted by: Armitage
What kind of programming do you guys do that performance is such a non-issue? I tend to be fairly obsessed with performance, but then, it's not unusual for stuff I'm working on to run a week or two on our cluster.

At this job: commerical Windows application software in VC++/MFC.

Our main application lets the user create assessment content and publish to e-learning servers (WebCT, Blackboard, eCollege) using SOAP and wininet. Our second, new application allows creating content then dynamically generating Macromedia Flash learning objects, then (if desired) uploading them to the same servers.

At my previous job I wrote statistical analysis software in VC++/MFC and conversion filters (dBase, excel, SPSS) to bring in data from other statistical apps.

For most end-user applications there are only tiny sections of the code that require optimization, such as the filter for importing large SPSS data files (80 MB of data was large in 1996 on a pentium 133 with 32 MB RAM )

 

[kamper]

Pretty much any desktop app that's not crunching numbers won't really care about speed. I work with web-apps myself. Sure, performance is an issue, but not in the sense that we worry about low-level optimizations. We worry about algorithms in the rare case that any thing complicated comes along but mostly about the mechanics of transactions and the amount of load we put on the database as opposed to the application server.
An example optimization:
large, complicated dynamic sql = bad
stored procedure = good
Granted, now that I think about it, that's purely outside the realm of business logic and completely about lowlevel optimization. Hmmm

Armitage, although I like my job, I'd have to say I'm a little jealous of yours. How do you get involved in stuff like that and what language(s) do you write in?

 

[kamper]

Originally posted by: Armitage

Originally posted by: DaveSimmons
Unless you're John Carmack hand-tuning 3D engine code to work acceptably on lousy gf4mx cards, you should normally only be concerned with the O() time of the algorithm, e.g. know not to use bubble sort or linear search.

Even that isn't always true. Linear search makes perfect sense for small values of n since the code is cleaner and easier to maintain and speed usually does not matter searching 100 items.

What kind of programming do you guys do that performance is such a non-issue? I tend to be fairly obsessed with performance, but then, it's not unusual for stuff I'm working on to run a week or two on our cluster.

I'd say that most developers fight not with hardware limitations, but with software limitations. The computer will run our programs fast enough if we can just get them to do what we want. Sure, Carmack worries about how efficient his lighting engine is, but first he had to figure out how to even create the algorithms for all the effects.
Until we create the compiler that will turn a plain english non-functional requirements document into a fully functional application with no human intervention I think this will continue to be the larger struggle.

 

[Armitage]

Originally posted by: DaveSimmons

Originally posted by: Armitage
What kind of programming do you guys do that performance is such a non-issue? I tend to be fairly obsessed with performance, but then, it's not unusual for stuff I'm working on to run a week or two on our cluster.

At this job: commerical Windows application software in VC++/MFC.

Our main application lets the user create assessment content and publish to e-learning servers (WebCT, Blackboard, eCollege) using SOAP and wininet. Our second, new application allows creating content then dynamically generating Macromedia Flash learning objects, then (if desired) uploading them to the same servers.

At my previous job I wrote statistical analysis software in VC++/MFC and conversion filters (dBase, excel, SPSS) to bring in data from other statistical apps.

For most end-user applications there are only tiny sections of the code that require optimization, such as the filter for importing large SPSS data files (80 MB of data was large in 1996 on a pentium 133 with 32 MB RAM )

I mostly work on modeling & simulations for astrodynamics R&D. Sensor scheduling/tasking, constellation and mission design, collision avoidance. Lots of number crunching.

 

[Armitage]

Originally posted by: kamper
Pretty much any desktop app that's not crunching numbers won't really care about speed. I work with web-apps myself. Sure, performance is an issue, but not in the sense that we worry about low-level optimizations. We worry about algorithms in the rare case that any thing complicated comes along but mostly about the mechanics of transactions and the amount of load we put on the database as opposed to the application server.
An example optimization:
large, complicated dynamic sql = bad
stored procedure = good
Granted, now that I think about it, that's purely outside the realm of business logic and completely about lowlevel optimization. Hmmm

Armitage, although I like my job, I'd have to say I'm a little jealous of yours. How do you get involved in stuff like that and what language(s) do you write in?

See above. Mostly use C++, along with legacy (or contributed) Fortran. I'm an aerospace engineer by education & job title, but have picked up alot of CompSci simply as a tool for the job.

 

[DaveSimmons]

Originally posted by: Armitage
I mostly work on modeling & simulations for astrodynamics R&D. Sensor scheduling/tasking, constellation and mission design, collision avoidance. Lots of number crunching.

Sounds like fun

The last time I worked on software needing that level of optimization was 6502 assembly programming for the Commodore 64 before college. Getting a steady 30 FPS for a game on a 1.x MHz CPU required effort

 

[Barnaby W. Füi]

hm, interesting. any ideas why the following two examples have such huge performance differences?

 

[Barnaby W. Füi]

haha, wow, and using the stl slowed it down even more

 

[AFB]

Interesting.

 

[Armitage]

Lol ... my first sig quote
My guess is that it's simply "abstraction penalty", but it's to late to think any harder on that tonight. In my experience, you gotta be damn careful using the STL. It's convenient, but it can really bite your ass on performance. Especially lists. Even if you think a list should be the better container, try a vector anyway. You might be suprised.

 

[Barnaby W. Füi]

You're famous.

Yeah, I assumed the same. Those templates can really expand to a lot of crap. I just picked lists randomly, no preference/prejudice really.