0

i am trying to design a chord system..

the problem is my system works fine if the size is like 10-20 lines of addPeer, removePeer etc..

but when i test it with a like 5000 lines of command file.

the first few hundreds was pretty fast, but as the program load more and more lines, it start to get slow..

As the requirement of the program is to test my program design, i cannot use threading.

I heard pointer is a good way to get things done faster, but how do i use pointer for my case.

This is my class headers..

class chord 
{
public:
chord();
~chord();

struct fingerTable {
int index;
int key;
};

struct node {
int nodeid;
vector<fingerTable> fTable;
vector<string> data;
};

void addPeer(int);

vector<node> cNode;
vector<fingerTable> fTable;

/* SOME more functions ..*/
};

This is my addPeer Function

void chord::addPeer(int id)
{
//id = node ID
int fIndex,nextNode;
node newNode;
vector<fingerTable> ft1;
vector<string> data1;
//increment indexCounter
//indexCounter++;

newNode.nodeid = id;
//insert a blank fingerTable first.
newNode.fTable = ft1;
//insert a blank data first.
newNode.data = data1;

//push back node to vector chord Index Node
cNode.push_back(newNode);
//indexCounter++;
//perform finger table computation

//sort it base on its NodeID
sort(cNode.begin(),cNode.end(),sortByNodeID);

for(int i=0;i<cNode.size();i++)
{
if(cNode[i].nodeid==id)
{
fIndex=i;
}
}//end for loop to loop finding index of node

if(fIndex!=cNode.size()-1)
{
//if not last element
nextNode=fIndex+1;
}
else
{
nextNode=0;
}

//now we get the message vector of the next node and do a datashift on it.
data1 = cNode[nextNode].data;
//clear its data away so we can empty it and re-arrange it.
cNode[nextNode].data.clear();
//performing data shift function
dataShift(data1,fIndex-1);

if(id!=0)
{
cout << "PEER " << id << " inserted."<< endl;
}

}//end addPeer

My question is, which part can i improvise on for this function addPeer to make the whole program execute the lines faster. as it get really slow when execute a few hundreds line.

user2017011
  • 93
  • 1
  • 1
  • 9
  • 1
    Well, you are doing linear work on every `addPeer`, so of course it will be slow (total time: quadratic). Have you thought about why you need to do all that work when adding a peer? – nneonneo Feb 16 '13 at 17:53
  • because when i add a peer, the next node are affected thus i need re-arrange its data to check if there any changes to the data should belong to which node. but i will take a good look at my codes again. thanks for the feedback. – user2017011 Feb 16 '13 at 18:00
  • You need to benchmark first to find out what is actually slow. If it is **not** the algorithm: Input/Output often is a likely candidate. So is forgetting to compile with optimizations turned on. The next thing is to minimize allocations by using `vector::reserve` when you know the size in advance. – pmr Feb 16 '13 at 18:09
  • @pmr, can i like unset the variable per run, so variable wont keep increment e.g the 2 temp vector – user2017011 Feb 16 '13 at 18:13
  • @user2017011 Benchmark first. Always. Never optimize when you don't know where the slow part is. Intuition about bottlenecks is often wrong. – pmr Feb 16 '13 at 18:15
  • @pmr, i did some testing. if i comment away cNode.push_back(newNode); then it run very fast. probably the part on vector having issue. – user2017011 Feb 16 '13 at 18:19
  • @user2017011 Than you should think about `vector::reserve`. Also, your testing could be horribly off: Maybe not doing any work at that point reduces the amount of necessary work at a later point which skews your results. Just get a profiler. Really. – pmr Feb 16 '13 at 18:34
  • Given you're calling `std::sort()` on every insertion, you're demonstrating that order is important, which suggests that `std::vector` may not be the container for this job. See http://stackoverflow.com/a/471461/78845 for more details. – johnsyweb Feb 17 '13 at 22:20

2 Answers2

1

This is slowing down because you are constantly sorting. You should prob. be using a sorted structure like std::map<int,node> .

Thomas
  • 4,980
  • 2
  • 15
  • 30
0

Change your container.

By using std::vector, your algorithm is spending most of its time copying chords to the wrong location.

If you want your chords to be sorted, consider using std::set instead of std::vector.

Drew Dormann
  • 59,987
  • 13
  • 123
  • 180
  • Thanks thats a good feedback. i think i really need to change my container, is there any more thing i could do to make it faster. – user2017011 Feb 16 '13 at 17:59
  • Is it still too slow? The answer will **always** be "Yes, there is something you could do to make it faster". – Drew Dormann Feb 16 '13 at 18:06