in reply to Program Hangs

Your algorithm is fundamentally flawed. Assume for a moment that the input file consisted of the following:

1
S AGT
3
S AGT
5
R AGT
7

[download]

Your algorithm would proceed as follows:

  1. The outer loop scans until it reads record 2;
  2. The inner loop then scans on until it reads record 6;
  3. Then you reset the pointer to the start of record 3; and exit to the outer loop;
  4. The outer loop scans on to record 4;
  5. The inner loop scans on to record 6;
  6. Then you reset the pointer to the start of record 5; and exit to the outer loop;
  7. The outer loop scans on to EOF.

Note that the above has matched both S records with the same R record.

Now imagine that your 100MB file has (say) 1000 S-records near the top of the file, and a single R-record 10 million lines further on. Then each of those 100 S-records would get matched against that single R-record; but you would have to re-read the 10 million intervening records over and over to do so.

1e3 * 10e6 == a very long time. It might well look like it had hung.

If the S-record/R-record pairs should appear sequentially:

...
S AGT
...
R AGT
...
S AGT
...
R AGT
...

[download]

Then you should not be resetting the pointer after you've found the matching R-record.

If however, the S-record/R-record pairs can be interleaved:

...
S AGT #1
...
S AGT #2
...
R AGT #1
...
R AGT #2
...

[download]

Then you would have to be maintaining two pointers: one telling you where to start looking for the next S-record; and one telling you where to start looking for the next R-record. Whilst this could be made to work, there are other, simpler approaches to this latter problem.

For example: a simple, single loop down the file looking for both types of record. When an S-record is found, you push it onto an array; when an R-record is found, you shift off the least recently found S-record from the array and do your calculations. 

my @Srecs;
while( <FILE> ) {
    if( /^S AGT/ ) {
        push @Srecs, $_;
    }
    elsif( /^R AGT/ ) {
        die "R-record with no corresponding S-record" unless @Srec;
        my @sRecBits = split ' ', shift @Srecs;
        my @rRecBits = split ' ', $_;
        ## Calculate stuff
    }
}
if( @Srecs) {
    printf "There were %d unmatched S-records\n"; scalar @Srec;
} 
## Other stuff

[download]

This single pass algorithm is far more efficient, less error prone and detects mismatches.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

Replies are listed 'Best First'.
Re^2: Program Hangs
by anbarasans85 (Initiate) on Feb 10, 2011 at 17:52 UTC
    Hi All,

    The program is working fine. I modified it using PERL hash. It is fast and I am happy.

    This is a very late reply but I thought i can share what I did.

    The logic is:
    1. Look for AGT events. Then make a hash key by combining event 's' or 'r' with packet id. ( hash_key = s<pktid> or r<pktid>) and store the corresponding time as hash value)
    2. The above runs through all lines of the trace file and build hashtable.
    3. then calculate delay for every packet_id. 

    while(<DATA>)
{
    @x=split(' ');
    if($x[3] eq 'AGT')
    {
        $hash_key = $x[0].$x[5];
        $hash_value = $x[1];
        $hash_table{"$hash_key"} = $hash_value;

        if($x[5] gt $last_packet_id)
        {
            $last_packet_id = $x[5];
        }
    }
}

$simulation_time = $x[1];

for($packet_id = 0;$packet_id<=$last_packet_id;$packet_id++)
{
    $hash_key = "s".$packet_id;
        $enqueue_time = $hash_table{"$hash_key"};
        $total_enqueue_count++;
    $hash_key = "r".$packet_id;
    if(exists($hash_table{$hash_key}))
    {
        $receive_time = $hash_table{"$hash_key"};
    }
    else
    {
                $total_drop_count++;
        next;
    }
    $total_receive_count++;
    $delay = $receive_time - $enqueue_time;
    $sum_of_delay = $sum_of_delay + $delay;

#    $delay = $delay * 1000;
#       print("\nDelay:$delay");

}

    [download]

    Thanks a lot for your help.

[reply]
[d/l]
Re^2: Program Hangs
by anbarasans85 (Initiate) on Dec 06, 2010 at 23:57 UTC
    Hello BrowserUk and all,

    Thanks for your comments. As you said, the program is not hung. It is searching for a corresponding 'r' receive event for a 's' send event. Since it does not find any corresponding 'r'(or may find it well below) it looks like the program is hung.

    Yes I am aware that the program is inefficient. In spite of that I wanted this particular program to work. Then use some efficient method like the method pointed by BrowserUk or use some PERL hash.

    The scenario for the simulation is very simple and I thought this simulation scenario will not produce packet loss event but it did. Since there was loss of packets it resulted in 'r' events missing. This assumption about "no loss" caused the confusion about program hang.

    Any how thanks for your help. I will post my program here when I implement some good algorithm for this delay calculation.

[reply]

In Section Seekers of Perl Wisdom