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 author=Skywing link=board=30;threadid=4193;start=0#msg34933 date=1071239883]
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]

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 author=Telos link=board=30;threadid=4193;start=0#msg34943 date=1071249942]
I think the biggest hit to performance was switching from an array to a linked list [~3000 items].[/quote]

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 author=Adron link=board=30;threadid=4193;start=0#msg34974 date=1071261636]
Why did you switch from using an array to using a linked list? What's wrong with the vector class?
[/quote]

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 author=iago link=board=30;threadid=4193;start=0#msg35019 date=1071278603]
[quote author=Adron link=board=30;threadid=4193;start=0#msg34974 date=1071261636]
Why did you switch from using an array to using a linked list? What's wrong with the vector class?
[/quote]

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]
Definitely not true at all.

ok, never = avoided

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

[quote author=iago link=board=30;threadid=4193;start=0#msg35024 date=1071280922]
ok, never = avoided
[/quote]

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

[quote author=iago link=board=30;threadid=4193;start=0#msg35024 date=1071280922]
ok, never = avoided
[/quote]
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.[/quote]
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.

[quote author=iago link=board=30;threadid=4193;start=0#msg35096 date=1071323090]
[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.[/quote]
I don't quite undertstand how trees and lists are different here?
[/quote]

To insert an item into a singly linked list, you only need to change one pointer to "commit the transaction". The list never has to be left in an inconsistent state between two instructions.

This means that you don't need to use special synchronization functions to control access to the list when you are adding or removing items. Someone else can safely access the list simultaneously with your modifying it.

This applies to the common operations of inserting object at an end or removing object from an end i.e. to managing a queue, which is very commonly done from more than one thread. A typical example would be requests arriving to some driver or module and getting queued for processing.

Ah, that makes sense, but that hardly ever comes up (in my experience, and probably most people here).

But the rest of my post stands :)

[quote author=iago link=board=30;threadid=4193;start=15#msg35109 date=1071328405]
But the rest of my post stands :)
[/quote]

This strange post stands?!

[quote author=iago link=board=30;threadid=4193;start=0#msg35096 date=1071323090]
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]

You'll grant that an array frequently is better? I'll grant than an array frequently is worse too! :)

You won't grant that trees are frequently better than lists? I'll say that trees frequently are better than lists, and lists frequently are better than trees.


[quote author=iago link=board=30;threadid=4193;start=0#msg35096 date=1071323090]
But the bottom line, that I should have said originally, is that trees are better than ordered linked lists, but necessarely better than arrays
[/quote]

Trees are necessarely better than arrays? I most definitely don't agree. Take for example strings - often stored as arrays of characters. Do you propose that strings now be stored as trees? I doubt you do, and so I think that you should reconsider your post.

edit: Particularly reconsider the contradicting parts...

Sorry, that was a misprint. I meant not necessarely. oops :)