Program Performance

[KiSSFRo]

Hi,

I have a program that does the following: given a directory as it's only argument, it goes to that directory and looks for directories inside that contain 2 special types of very large files. If it finds these files, it goes through each file line by line looking to see if they contain certain strings. As mentioned, these two files are very big and contain a lot of information, and I recently ran this program on a certain directory and it took 35 minutes to complete. I've optimized the algorithms as much as I can using binary search to compare each line for each value that I'm looking for (don't want to implement a hash table for this particular program). My question is this, would it be faster for me to use the 'grep' command to look for the information im looking for, rather than opening each file and going line by line, or would it even make a difference?

KiSSz

[KevinADC]

what do you mean by "using binary search"?

[KiSSFRo]

I have a list of items that I'm searching for in the big files and they are stored in an array and they are sorted. A binary search is when you first look at the middle value to compare with the value you're looking for, then if it's less you go to middle value of the left half of the array, if it's greater you go to the middle value of the right half of the array and you keep doing this till you find the value. With each comparison you eliminate half the values so it's much faster than searching from the beginning of the array to the end.

[eWish]

I would suggest that do a Benchmark using each method (binary search and grep). Then compare the times and see which one is quicker.

--Kevin

[KevinADC]

I have a list of items that I'm searching for in the big files and they are stored in an array and they are sorted. A binary search is when you first look at the middle value to compare with the value you're looking for, then if it's less you go to middle value of the left half of the array, if it's greater you go to the middle value of the right half of the array and you keep doing this till you find the value. With each comparison you eliminate half the values so it's much faster than searching from the beginning of the array to the end.

Is the sorted list the search items you look for in the file? From what I know, a binary search is for finding the items in the sorted list, not using the sorted list to find items in a file. But maybe you have some unusual circumstance that makes your search method a good choice.

[KiSSFRo]

Is the sorted list the search items you look for in the file? From what I know, a binary search is for finding the items in the sorted list, not using the sorted list to find items in a file. But maybe you have some unusual circumstance that makes your search method a good choice.

I come across a line in the file, then I go search my sorted list of elements to see if it matches one of them.

KiSsZ

[KevinADC]

I come across a line in the file, then I go search my sorted list of elements to see if it matches one of them.

KiSsZ

ahhh... I see. Unless you post your code for evaluation I would say you are doing the best you can.

[KiSSFRo]

I'm going to paste my code and I was wondering if any of you guys can see where I can be more efficient. I know a lot of it is sloppy because I'm a Perl beginner and I went quickly through this. Any feedback would be much appreciated. Here is my code:

#!/usr/bin/perl -w
use Cwd;
use Time::Local;

main();

sub partition
{
	my $x = $testNames[$_[0]];
 	my $i = $_[0] - 1;
	my $j = $_[1] + 1;

	do
	{
		do      
		{
			$j--;
		}
		while ($x lt $testNames[$j]);

		do  
		{
			$i++;
		} 
		while ($x gt $testNames[$i]);
	
		if ($i < $j)
		{ 
			$temp1 = $testNames[$i];   
			$testNames[$i] = $testNames[$j];
			$testNames[$j] = $temp1;
			
			$temp2 = $passFailBoolean[$i];
			$passFailBoolean[$i] = $passFailBoolean[$j];
			$passFailBoolean[$j] = $temp2;

			$temp3 = $elapsedTime[$i];
			$elapsedTime[$i] = $elapsedTime[$j];
			$elapsedTime[$j] = $temp3;

			$temp4 = $directorySizes[$i];
			$directorySizes[$i] = $directorySizes[$j];
			$directorySizes[$j] = $temp4;
		}
	}
	while ($i < $j);     
	return $j;           
}

sub quicksort
{
	my $middle;
	my $first = $_[0];
	my $last = $_[1];
	if ($first < $last)
    	{
		$middle = partition($first, $last);
		quicksort($first, $middle);   
		quicksort($middle + 1, $last);    
	}
}

sub calculateElapsedTime
{
	my @parameters = @_;

	my %months = 
	(
		"Jan" => 0,
		"Feb" => 1,
		"Mar" => 2,
		"Apr" => 3,
		"May" => 4,
		"Jun" => 5,
		"Jul" => 6,
		"Aug" => 7,
		"Sep" => 8,
		"Oct" => 9,
		"Nov" => 10,
		"Dec" => 11
	);

	my @time;
	foreach $parameter (@parameters)
	{
		my @words = split(/\s+/, $parameter);
		my @numbers = split(/:/, $words[7]);
		push(@time, timelocal($numbers[2], $numbers[1], $numbers[0], $words[6], $months{$words[5]}, $words[9])); 
	}
	
	return ($time[1] - $time[0]);
}

sub binarySearch
{
	@parameters = @_;
	my $low = 0;
	my $high = @passFailNames - 1;
	my $middle;
	
	while ($low <= $high)
	{
		$middle = $low + $high;
		if ($parameters[0] eq $passFailNames[$middle])
		{
			$tempIndex = $middle;
			return 1;
		}
		elsif ($parameters[0] lt $passFailNames[$middle])
		{
			$high = $middle - 1;
		}
		else
		{
			$low = $middle + 1;
		}
	}

	return 0;
}

sub main 
{
	@passFailNames = 
	(
		"CSI Errors : 0",
		"CSIBFM_TX_ISM Errors : 0",
		"CSI_CREDIT_TRK Errors : 0",
		"CSI_FLITTRK Errors : 0",
		"CSI_ISM Errors : 0",
		"GFX Checker Errors : 0",
		"GFX Checkers not done : 0",
		"HSB_SD0 Errors : 0",
		"HSB_SD1 Errors : 0",
		"HT_SB_ISOCH_TRK Errors : 0",
		"HT_SB_PRIM_TRK Errors : 0",
		"HT_SB_SEC_TRK Errors : 0",
		"MCHCORE Errors : 0",
		"SAGP Errors : 0",	
		"Test Completed : Yes",
		"cpu1_bfm Errors : 0",
		"flex_config Errors : 0",
		"ioorb_isr_trk Errors : 0",	
		"sig_trk_idwb Errors : 0",
		"system_cfg_addr Errors : 0",
		"system_noncfg_addr Errors : 0"
	);

	if ($ARGV[0])
	{
		$dir1 = $ARGV[0];
	}
	else
	{
		$dir1 = getcwd;
	}

	opendir(DIR1, $dir1) or die "[!] Can't open directory: $dir1";
	$passes = 0;
	while ($file1 = readdir(DIR1)) 
	{
		if (-d "$dir1/$file1")
		{
			my $passFailTotal = 0;
			my $passFailBool = "false";
			my $runSimFlag = "FALSE";
			my $transcriptFlag = "FALSE";
			opendir(DIR2, "$dir1/$file1") or die "[!] Can't open directory: $dir1/$file1";
			while ($file2 = readdir(DIR2))
			{
				my $misrErrorTotal = 0;
		 		if (($file2 eq "runsim.log") or ($file2 eq "runsim.log.gz"))
				{
					$runSimFlag = "TRUE";
					my $gunzipFlag = "false";
					if ($file2 eq "runsim.log.gz")
					{
						system("gunzip $dir1/$file1/runsim.log.gz");
						$file2 = "runsim.log";
						$gunzipFlag = "true";
					}

					my $startedFlag = "FALSE";
					my $endedFlag = "FALSE";
					@temp = split(/\s+/, `du $dir1/$file1`);
					push(@directorySizes, $temp[@temp - 2]);
					push(@testNames, $file1);
					open(FH1, "$dir1/$file1/$file2") or die "Can't open file: $dir1/$file1/$file2";
					while ($line1 = <FH1>)
					{
						if ($startedFlag eq "FALSE" and $line1 =~ m/Simulation started at:/)
						{
							push(@startTimes, $line1);
							$startedFlag = "TRUE";
						}
						elsif ($endedFlag eq "FALSE" and $line1 =~ m/Simulation ended at:/)
						{
							push(@endTimes, $line1);
							$endedFlag = "TRUE";			
						}
						elsif ($passFailTotal < 21)
						{
							my @passFailValues = (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0);
							$line1 =~ s/^\s+//;
    							$line1 =~ s/\s+$//;
							if (binarySearch($line1, $tempIndex) == 1)
							{
								if ($passFailValues[$tempIndex] == 0)
								{	
									$passFailValues[$tempIndex] = 1;
									$passFailTotal = $passFailTotal + 1;
								}
							}	
						}

							
					}
					close(FH1);
					if ($endedFlag eq "FALSE" or $startedFlag eq "FALSE")
					{
						push(@startTimes, "-");
						push(@endTimes, "-");
						$noStartEndTimeTotal++;
					}

					if ($passFailTotal == @passFailNames)
					{
						push(@passFailBoolean, "Pass");
						$passes++;
					}
					else
					{
						push(@passFailBoolean, "Fail");
					}
					
					if ($gunzipFlag eq "true")
					{
						system("gzip $dir1/$file1/runsim.log");
					}
				}
		 		elsif (($file2 eq "transcript.log") or ($file2 eq "transcript.log.gz"))
				{
					$transcriptFlag = "TRUE";
					my $gunzipFlag = "false";
					
					if ($file2 eq "transcript.log.gz")
					{
						system("gunzip $dir1/$file1/transcript.log.gz");
						$file2 = "transcript.log";
						$gunzipFlag = "true";
					}
					open(FH1, "$dir1/$file1/$file2") or die "Can't open file: $dir1/$file1/$file2";
					my $tclFlag1 = 0, $tclFlag2 = 0;
					while ($line1 = <FH1>)
					{

						if ($tclFlag1 == 0 and ($line1 =~ m/# TclNOTE:      [0-9]+ ps: Translated address from 0x0004E008 to 0x4027004d data is 0x00000003/))
						{
							$tclFlag1 = 1;
						}
						elsif ($tclFlag2 == 0 and ($line1 =~ m/# TclNOTE:      [0-9]+ ps: Translated address from 0x0004E008 to 0x4027004d data is 0x00000002/))	
						{
							$tclFlag2 = 1;
						}
						elsif ($tclFlag1 == 1 and $tclFlag2 == 1 and ($line1 =~ m/Error: ERROR!! X in data: misr_data_qual/))
						{
							$misrErrorTotal++;
						}
							
					}
					if ($gunzipFlag eq "true")
					{
						system("gzip $dir1/$file1/transcript.log");
					}
				}

				if ($runSimFlag eq "TRUE" and $runSimFlag ne "FALSE")
				{
					push(@misrErrors, $misrErrorTotal); 
				}
				elsif($runSimFlag eq "TRUE" and $runSimFlag ne "TRUE")
				{
					last;
				}
			
			}
			closedir(DIR2);
		}
	}


	if (@testNames > 0)
	{
		for ($i = 0; $i < @startTimes; $i++)
		{
			if ($startTimes[$i] ne "-" and $endTimes[$i] ne "-")
			{
				$simulationTime = calculateElapsedTime($startTimes[$i], $endTimes[$i]);
				$timeTotal += $simulationTime;
				$localHour = int ($simulationTime / 3600);
				$simulationTime -= (3600 * $localHour);
				$localMinute = int($simulationTime / 60);
				$simulationTime -= (60 * $localMinute);
				$localSecond = sprintf("%.2f", $simulationTime);
				$simulationTime = "$localHour:$localMinute:$localSecond";
				push(@elapsedTime, $simulationTime);
			}
			else
			{
				push(@elapsedTime, "-");
			}
		} 

		for ($j = 0; $j < @directorySizes; $j++)
		{
			$sizeTotal += $directorySizes[$j];
		}

		$sizeAverage = sprintf("%.2f", $sizeTotal / @directorySizes);
		$totalSimulations = @testNames;
		$fails = $totalSimulations - $passes;
		$timeAverage = $timeTotal / (@startTimes - $noStartEndTimeTotal);
		$hour = int ($timeAverage / 3600);
		$timeAverage -= (3600 * $hour);
		$minute = int($timeAverage / 60);
		$timeAverage -= (60 * $minute);
		$second = sprintf("%.2f", $timeAverage);
		open (OUTPUTFILE, '>output.txt');
		print OUTPUTFILE "@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n";
		print OUTPUTFILE "@       Netbatch_Util Output       @\n";
		print OUTPUTFILE "@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\n\n";
		print OUTPUTFILE "Regression Directory: $dir1\n";	
		print OUTPUTFILE "Total Simulations: $totalSimulations\n";
		print OUTPUTFILE "Total Passes: $passes\n";
		print OUTPUTFILE "Total Fails: $fails\n";
		print OUTPUTFILE "Average Simulation Time: $hour:$minute:$second\n";
		print OUTPUTFILE "Average Directory Size: $sizeAverage\n\n";
		print OUTPUTFILE "@@@@@@@@@@@@@@@\n";
		print OUTPUTFILE "@    Fails    @\n";
		print OUTPUTFILE "@@@@@@@@@@@@@@@\n\n";

		quicksort(0, @testNames-1);
		for ($r = 0; $r < @testNames; $r++)
		{
			if ($passFailBoolean[$r] eq "Fail")
			{
				print OUTPUTFILE "$testNames[$r]\n";
			}
		}

		print OUTPUTFILE "\n@@@@@@@@@@@@@@@\n";
		print OUTPUTFILE "@  All Tests  @\n";
		print OUTPUTFILE "@@@@@@@@@@@@@@@\n\n";

		for ($l = 0; $l < @testNames; $l++)
		{
			print OUTPUTFILE "Name: $testNames[$l]\n";
			print OUTPUTFILE "Status: $passFailBoolean[$l]\n";
			print OUTPUTFILE "Time: $elapsedTime[$l]\n";
			print OUTPUTFILE "Size: $directorySizes[$l]\n";
			print OUTPUTFILE "Misr Errors: $misrErrors[$l]\n\n";
		}
	}
	else
	{
		open (OUTPUTFILE, '>output.txt');
		print OUTPUTFILE "@@@@@@@@@@@@@@@@@@@@@@@@\n";
		print OUTPUTFILE "@ Netbatch_Util Output @\n";
		print OUTPUTFILE "@@@@@@@@@@@@@@@@@@@@@@@@\n\n";
		print OUTPUTFILE "@ Regression Directory: $dir1\n";	
		print OUTPUTFILE "@ Total Simulations: $totalSimulations\n\n";
	}		
	close (OUTPUTFILE); 	
	closedir(DIR1);
	exit 0;
}

[KevinADC]

Nothing bad is jumping out. Looks OK to me. Hard to say if it could be improved without being to run the code, but I don't want to run it.

in general:

do {
 ...
} while()

can be replaced with a simpler loop:

while() {
 ...
}

It might also be a little more efficient, although its not going to be dramatic.

[KiSSFRo]

Thanks Kevin. I guess what initially lead me to think that I could improve the efficiency is whenever Im at the console and I do a grep it finds the information so quickly, even for big files. I guess if ran through the Perl interpreter this would be a lot slower?

[KevinADC]

Thanks Kevin. I guess what initially lead me to think that I could improve the efficiency is whenever Im at the console and I do a grep it finds the information so quickly, even for big files. I guess if ran through the Perl interpreter this would be a lot slower?

I'm not sure. Perls only disadvantage that I am aware of is the time it takes to compile the code versus running a shell command that doesn't have to be compiled. But that can't account for a dramatic difference, especially not for a small script like you have.

Hopefully someone on Devshed will have more insight. You can also try www.perlmonks.com