node_jump.cpp

#include<iostream>
#include <cstdlib>  
#include <ctime>
#include <chrono>    
using namespace std;

#define NETWORK_SIZE 100000

struct Node{

    uint id;
    // The size of the struct is small enough so it can fit to stack
    // I want to avoid vec use due to allocations overhead. (-1) - means no receiver defined. 
    // But it will require extra "if". 
    int receivers[3];
    int got_msg;
    int hop;
    
    Node() : id(0), receivers{-1, -1, -1}, got_msg(0), hop(0) {}

};


void gen_rnd(int fan, Node* node){
    for (int i = 0; i < fan; ++i) {
        int rnd;
        do {
            rnd = rand() % NETWORK_SIZE;
        } while (rnd == node->id);
        node->receivers[i] = rnd;
    }
}


void fill_array(Node nodes[], int fanout, int size){

        for (int i = 0; i < size; ++i) {
            nodes[i].id = i;
            gen_rnd(fanout, &nodes[i]);

    }

}


void start_msg(
    Node nodes[],
     int fanout,
      int mother_node,
        int size,
         float *dublicates_amount,
          float *total_messages_amount,
        int *used_nodes_total,
    float *total_hopes_amount){
    
    //===============Init==============
    float used_nodes_buff[10000];

    for (int i = 0; i<size; ++i){
         used_nodes_buff[i] = -1.0;
     }

    // immidiately define mother node as 1 because it has the message initially
    used_nodes_buff[mother_node] = 1.0;
    // mark the Node struct as 
    nodes[mother_node].got_msg = 1;
    
    int current_node = mother_node;
    

     //=====================================

    // the stack border  
    int idx_buf_offset = 1; 
    //the Stack buffer exists only for the nodes which are allowed to send the message 
    //and Node.got_msg = 1
    int idx_buf[10000];
        for (int i = 0; i<size; ++i){
         idx_buf[i] = -1;
     }
    //The first idx in the stack is the mother id put it there streight
    idx_buf[0] = mother_node;
    // This step will increase by 1 every iteration and it will go through the indexes of nodes untill it will meet "-1"
    // What means there are no nodes who can send any messages left and we stop the process.
    // Starting from 1 because 0 is buisy with mother
    int step_in_stack = 1;


    while (true){

        
        for (int i = 0; i < fanout; ++i){

           int idx = nodes[current_node].receivers[i];
           
           // This logic is for counting dublicates
           if (used_nodes_buff[idx]== -1.0){
              used_nodes_buff[idx] = 0.0;  
           }
           // 
           nodes[idx].got_msg += 1;
           // increase dublicates only if it alredy got one message.
           if (nodes[idx].got_msg > 1){
                used_nodes_buff[idx] += 1.0;
           }
            
           //Next block is for adding the index of the node which can send  messages
           // It can not be added there if it is not allowed to send message

           // If we did not yet get a message or got it 1 time==>
           if (nodes[idx].got_msg <= 1)
           {    
            
                // we put it in the queue that we need to send the message
                idx_buf[idx_buf_offset] = idx;
                // and we move the offset to the next memory block
                idx_buf_offset++;

                nodes[idx].hop = nodes[current_node].hop + 1;
                
           }  
            
        }

        // after we wrote all the receivers to the stack
        // we step to the next id in the stack
        
        //and then we get the next index from the "sender buffer" and assign it as a current node
        if (step_in_stack >= idx_buf_offset || idx_buf[step_in_stack] == -1) {
            break;
        }   

        current_node = idx_buf[step_in_stack];
        
        step_in_stack++;
        
        
        
   }

   //Statisitic variables
   float dublicates = 0.0;
   float total_messages = 0.0;
   
   
   for(int i = 0; i < size; ++i){

        if(used_nodes_buff[i]!= -1.0){
            (*used_nodes_total)++;
            dublicates += used_nodes_buff[i];
            *total_hopes_amount += nodes[i].hop;
        }
   }



   for (int i = 0; i< size; ++i){

    total_messages += nodes[i].got_msg;

   }

   *dublicates_amount += dublicates;
   *total_messages_amount += total_messages;



}   

int main(){

    srand(time(0));

    Node nodes[NETWORK_SIZE];

    int fanout;

    cout<< "Enter a fanout number"<< endl;


    cin >> fanout;

    int size = sizeof(nodes) / sizeof(nodes[0]);

    float dublicates_amount = 0.0;
    float total_messages_amount = 0.0;
    int used_nodes_total = 0;
    float total_hopes_amount = 0;
    int iter_times = 100;    
    int mother_node = rand() % NETWORK_SIZE;


    auto bench_start = chrono::high_resolution_clock::now();

        for(int i = 0; i < iter_times; ++i){

            fill_array(nodes, fanout, size);

            // Wipe old data from Node.got_msg
            for (int j = 0; j < size; ++j) {
                nodes[j].got_msg = 0;
            }
            start_msg(nodes, fanout, mother_node, size, &dublicates_amount, &total_messages_amount, &used_nodes_total, &total_hopes_amount);

        }    

    auto bench_end = chrono::high_resolution_clock::now();
    chrono::duration<double, std::milli> duration = bench_end - bench_start;
    
    float avg_hops = total_hopes_amount/used_nodes_total;    
    float avg_dub = dublicates_amount/iter_times;    
    float avg_tot = total_messages_amount/iter_times;    
    float avg_used = (float)used_nodes_total / iter_times; 


    cout<<"Dublicates avg amount: "<<avg_dub<< endl;
    cout<<"Messaes avg amount: "<<avg_tot<< endl;
    cout<<"Percentage dub/total:  "<< (avg_dub/avg_tot*100.00)<< endl;
    cout<<" Avg percent of Used: "<< avg_used/float(NETWORK_SIZE)*100.0 << endl;
    cout<<" Avg Hopes Amount: "<< avg_hops << endl;
    cout << "Execution time: " << duration.count() << " ms" << endl;


    return 0;

}