Valhalla Legends Archive

A few days ago I wrote a CPU intensive program in C that basically performs a lot of calculations and returns a result.  It uses "extern" a lot in order to share variables between source files and a lot of global variables.  I decided to rewrite it in C++ putting what I could into classes and encapsulating all of the data that needed to be shared.  The point of this is that I had a massive decrease in performance in the C++ version.  What took maybe 5-10 minutes to complete would have taken hours.

Was my implementation just that bad or is there a steep performance loss for certain applications?  If the latter when is C preferred to C++?

I think your implementation was bad.  If used properly, C++ isn't slow (provided you are using a modern compiler, anyway - I've heard that some not-so-recent versions of GCC produce pretty sucky code for C++ programs).

Quote from: Skywing on December 12, 2003, 08:38 AM
I think your implementation was bad.  If used properly, C++ isn't slow (provided you are using a modern compiler, anyway - I've heard that some not-so-recent versions of GCC produce pretty sucky code for C++ programs).

The 2.95.X branch on my Linux system tended to like to make everything virtual (or so it seemed from the assembly output), which hurt performance some.  However, I don't see how even that could've slowed the resulting program by the amounts Telos describes.

I'd be interested to see the two versions, preferably as links to other downloads if they're exceptionally large.  If I have some free time, I'll try to do some critiques on how to bring the C++ version back up to speed.

In that event I will try recoding it more effectively before I have anyone spend time examining it.  I think the biggest hit to performance was switching from an array to a linked list [~3000 items].

Quote from: Telos on December 12, 2003, 11:25 AM
I think the biggest hit to performance was switching from an array to a linked list [~3000 items].

Depending on what you do with the data stored in there, that could definitely hurt a lot!  Arrays support random access, but lists don't, so you'll incur worst case O(n) accessing a list element, but worst case O(1) accessing an array element.  To avoid reallocations, you might consider loading it into a list, then transferring to an array once you know the size (if the size can't be known in advance).  This will have some performance hit, but potentially still be a boost over having linear time access to all the elements for every operation.

It's not a case of C vs. C++ if you did things like switch from using an array to a linked list during the transition. Some features of C++ are inherently slower, yes, but it's usually negligible.

Why did you switch from using an array to using a linked list? What's wrong with the vector class?

Quote from: Adron on December 12, 2003, 02:40 PM
Why did you switch from using an array to using a linked list? What's wrong with the vector class?

That's what I was going to to say.  He switched to C++, but is still using a slow C-type thing.

I've been told that Linked Lists are never used in the real world because they're so damn slow.  Binary Trees are where it's at!

Quote from: iago on December 12, 2003, 07:23 PM

Quote from: Adron on December 12, 2003, 02:40 PM
Why did you switch from using an array to using a linked list? What's wrong with the vector class?

That's what I was going to to say.  He switched to C++, but is still using a slow C-type thing.

I've been told that Linked Lists are never used in the real world because they're so damn slow.  Binary Trees are where it's at!

Definitely not true at all.

ok, never = avoided

If you're gonna sort/order stuff, they're your friend.

Quote from: iago on December 12, 2003, 08:02 PM
ok, never = avoided

Dude, that's just crap. Who said that?

Quote from: iago on December 12, 2003, 08:02 PM
ok, never = avoided

I don't think so.  There are many situations where a linked list operates better than a tree.  For instance, insertions and removals can be performed in constant time given a pointer - if you're using an "advanced tree" (like you've already advocated), you'll have to do stuff like rebalancing elements after such operations.

It's easily to atomically link or unlink an element from a singly-linked list without using synchronization primatives.  This is particularly important in kernel mode programmming.

Additionally, you'll have a difficult time justifying the overhead of a tree in cases where there is no meaningful comparison between elements.

I realized afterwards that, yes, there are places for lists.  If you're doing something like a stack or queue, where you're always removing from the top or back and never traversing, it's a good idea. Also, if there's no way to compare the elements, trees are useless.

And I was comparing linked lists to trees, not to arrays.  I'll grant that an array is frequently better than trees or lists, just not that trees are better than lists.

Quote
It's easily to atomically link or unlink an element from a singly-linked list without using synchronization primatives.  This is particularly important in kernel mode programmming.

I don't quite undertstand how trees and lists are different here?


But the bottom line, that I should have said originally, is that trees are better than ordered linked lists, but [edit]not[/edit]necessarely better than arrays

I didn't understand your last post iago.

An array is frequently worse than a tree or list.

The way I see it, out of those three:

Arrays are best if you want random access to elements, and don't need to add or remove items often.

Trees are best if you want to add or remove objects often and access objects by a key or sort the items.

Lists are best if you want to add or remove objects often but don't need them to be sorted by a key.


Apart from that, there's double and single linked lists - double linked require more storage but can be traversed both ways. If you don't need to traverse the list both ways, a single linked list will save resources - both storage in each item, and synchronization resources.

There's also hash tables which are great for many purposes including rather fast insertion/removal and very fast lookup. They require more resources and more code though.