4 Replies - 1450 Views - Last Post: 30 June 2010 - 02:36 PM Rate Topic: -----

#1 Nizbel99  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 6
  • View blog
  • Posts: 117
  • Joined: 19-May 09

C++ Efficiency Question

Posted 30 June 2010 - 12:15 PM

Hello,

I'm implementing something in C++ (arbatrary large numbers for those who remember my last post), where speed and efficientcy is really important. I've been thinking about several implementation ideas, and the bulk of the decision comes down to either using an array, a linked list, or a vector. But no matter which one I use, it seems that some problems arise.

I need to be able to resize the data structure I'm using incase said number gets to pick for the current amount of space, while being able to perform operations (such as multiplication, division, addition, GCD, etc...) efficiently. If I use arrays, I can't resize them using new/delete, and I don't want to have to use malloc/re-alloc/free mixed with the rest of my C++ code. If I use linked lists of a vector, I'm worried that this may not be too efficient because of the scattered pieces in memory, increased number of page faults, and what not...

I've looked at a variety of algorithms for arbatrary larger numbers and I understand them relatively well, so that's not an issue, but rather just the way I would be storing that data. I was just wondering what everyone's input/suggestion on this was, considering that efficientcy plays a big role on this :)

Thanks for your time,

Zach

This post has been edited by Nizbel99: 30 June 2010 - 12:18 PM


Is This A Good Question/Topic? 0
  • +

Replies To: C++ Efficiency Question

#2 Banfa  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 83
  • View blog
  • Posts: 109
  • Joined: 07-June 10

Re: C++ Efficiency Question

Posted 30 June 2010 - 12:39 PM

OK well to start with you seem to think that a vector is implemented as a linked list. Its not, in fact the C++ standard guarantees that the memory in a vector will have exactly the same foot print as a vector, 1 contiguous block. If a vector is resized to make it bigger it will have to reallocate and copy exactly as you would have to do with an array.

The advantage is that it is all handled for you. Under optimisation you should find that there is little difference in efficiency between an array and a vector.

You should not be considering arrays at all, the question should be whether to use a vector (C++ array) or a list (an actual linked list). Generally the recommendation is that your default container should be a vector and you should only use one of the other containers if you have a reason that you can write down.

Another consideration is that for a small number of contained items, certainly anything less than a few hundred the inefficiencies inherent from using a contiguous block of data like a vector are nearly negligible against using something like a list.

Finally a vector does support the random access iterator which a list does not allowing for efficient access directly to any member.

So my recommendation for now would be go ahead and implement using a vector, if you are careful you can probably make it so that you can easily change the container. Then if you are not getting the desired performance profile to find the bottle neck and only then if the bottle neck is the container try a different container type.
Was This Post Helpful? 3
  • +
  • -

#3 Nizbel99  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 6
  • View blog
  • Posts: 117
  • Joined: 19-May 09

Re: C++ Efficiency Question

Posted 30 June 2010 - 12:47 PM

Sorry, I must of not been clear. I know that a vector is not implemented as a linked list. And by the second linked list reference, I meant a C++ list object. Sorry for being un-clear.

As for the rest, I wasn't sure as to how much the small inefficiencies would matter. That's why I was asking :) - If the difference is really really really small, then I'll go with a vector. The idea was to store part of the number in a vector of integers (for some range R), and then for fractional numbers, have two of these vectors, one for the numerator and then one for the denominator. Plus, I know that I'll be doing alot of basic operations with these numbers, so I just wanted to make sure that I wouldn't get small inefficiencies that could of been prevented by just asking =)

Thank you for your help and taking the time to clarify =)

Zach

PS: Even though this is for learning experiences only, I still want to try to make this project as efficient as I can =) - Also, my goal was to make an implementation of numbers large enough to be used for thing like RSA, which is another reason I asked about efficientcy.

This post has been edited by Nizbel99: 30 June 2010 - 12:51 PM

Was This Post Helpful? 0
  • +
  • -

#4 Salem_c  Icon User is offline

  • void main'ers are DOOMED
  • member icon

Reputation: 1689
  • View blog
  • Posts: 3,209
  • Joined: 30-May 10

Re: C++ Efficiency Question

Posted 30 June 2010 - 01:07 PM

As Banfa says, get something debugged and working with vector first. You're not going to get "lucky" and stumble into the most optimal solution just by thinking about it.

However, working code and a clean design is a good place to start from when tuning the system.

Then profile it to see where the real hot spots are.

Armed with working code with a known performance characteristic, you can then do measured changes to bits of the code:
- Does it still work?
- Is it quicker?
- Does the code still retain its clarity from <vector>?

If it fails 1, then delete the change and try again (or fix the bugs).
If it fails 2, ditto.
3 is more subjective: If you get 10% with a simple tweak, you'd probably keep it. Some ungodly mess of code for a small fraction you might consider otherwise.

With each iteration, you'll learn something new.
Was This Post Helpful? 1
  • +
  • -

#5 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: C++ Efficiency Question

Posted 30 June 2010 - 02:36 PM

I would say ditch and idea of using a list -- For the algorithms that you will want a contiguous bock of memory will be better (far fewer cache misses etc).

Secondly, once you get things working you MAY wish to implement your own custom allocator. This can greatly improve the performance for the vector class when the size of your numbers changes often. The default way that most implementations of the vector allocator works is that to increase the size it allocates twice the currently allocated space. So for example if you have a vector of 2, and suddenly do a "push_back()", the allocator will grab room for 4, when it next grows it will grab room for 8 etc... this is fine for a default, but when you are doing something like multiplication you know that the result will be a predetermined size, so you can just have the allocator grab what you need all at once. -- again note that you should first program the algorithm with just the vector type, THEN if you find that it is not working for you, you can implement a custom allocator. If that still does not work well enough -- then get a profiler and find out where your bottlenecks are.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1