HELP! Code taking a long time to run

[Ozyman]

Thanks in advance for any help.

I have created a collection of functions that I use to generate a menu on my website (prestopnik.com). My webhost uses PHP 4.0.6.

A couple of months ago I noticed that it was taking 5-15 seconds on average to load a page of my website, and most of that time the browser said "waiting for prestopnik.com". I talked to my web host, and they suggested it had to do with my php.

I've isolated the problem to my menuing functions (when I remove the menu, the problem goes away).

I'll attach the relevant code to the end of this post, but here is some basic documentation/pseudo-code:

My website is organized as a tree. Each page of the website is represented by one (or more) nodes in the tree. The root node is a dummy node. Currently there are about 95 nodes in this tree.

When you visit a page on my website, the menu is generated dynamically based on this process:

1) The menu data is loaded from a text file into a tree.

2) The tree is traveresed in order and at each node a 4 part test is applied to decide if that node should be displayed as part of the menu. If any of the four parts of the test is true, the node is printed, otherwise it is not.
The 4 part test:

a) Is this node the child of the root? (i.e. all top level nodes are printed)

b) Is this node a sibling of a node representing the current page?

c) Is this node a child of a node representing the current page?

d) Is this node in the path from the root to the node representing this page?

----end documentation/pseudocode----

I think that the slowest part of this is the 4th test, which I could probably do a bit more efficiently.

I have a few questions:

1) Do you have any recomendations for how I might speed my code up.

1b) I use a lot of recursion in this code. Is recursion particularly slow in PHP? How about creating arrays or joining them?

2) Should a decent webhost be able to run this php code faster than mine is. I have a pretty cheap ($8/month) webhost, and I'm wondering if I just don't get many cpu cycles for my website because I pay so little.

2b) Also if this is mostly the result of a cheap web host, what sort of questions could I ask my webhost or future webhosts that would ensure my website was running on a server with more cpu cycles to spare?

Again, thanks for any help that you can offer.

$GlobalSerial = 0;

class menu_tree_node
{
  var $serial;
  var $url;
  var $menu_name;
  //var $mouse_over;

  var $children_pages = array();  

  //var $index_terms = array();

  var $hidden;
	var $font_size;
	var $icon;

  function menu_tree_node()
    {
//      $this->mouse_over = "mouse over test";
      $this->hidden = false;
			$this->font_size = "medium";
			$this->icon = "none";
			$this->serial = $GLOBALS['GlobalSerial']++;
    }
}

function load_tree($file_name)
{
 $lines = file($file_name);

 for($i = 0; $i<count($lines); $i++)
   $lines[$i] = rtrim($lines[$i]);

 $root = new menu_tree_node();
 read_and_add_node($lines, $root);

 return $root;
} 

//$root needs to be passed by reference 
function read_and_add_node(&$lines, &$root)
{
 $root->url = $lines[0];
 $root->menu_name = $lines[1];

 if($lines[2] == "true") 
   $root->hidden = true;
 else
 	 $root->hidden = false;

 $root->font_size = $lines[3];
 $root->icon = $lines[4];
 $num_children = $lines[5];
 for($i = 0; $i < $num_children; $i++)  //$line[5] is a string, but converts to a  #
 {
		$root->children_pages[$i] = new menu_tree_node();
		$lines = array_slice($lines,6);
		read_and_add_node($lines, $root->children_pages[$i]);
	}
}

function print_full_tree($root)
{
 print_node($root);

 for($i = 0; $i < count($root->children_pages); $i++)
 {
 print_full_tree($root->children_pages[$i]);
 }
}

function get_parent_n($root, $node)
{
 if ($root == NULL)
 		return NULL;

 if (is_parent($root,$node))
 {
 		return $root;
 }

 for($i = 0; $i < count($root->children_pages); $i++)
 {
 	  $prNode = $root->children_pages[$i];
 	  //print (":$prNode->url");
    $tmpNode = get_parent_n($root->children_pages[$i], $node);
		if ($tmpNode != NULL)
		{
		 //print("found!! = $tmpNode->url");
			 return $tmpNode;
  	}
 }
 return NULL; 
}

function load_and_print_menu($file_name)
{
$root = load_tree($file_name);
print_menu($root,$root);
}

function print_menu($real_root, $root, $num_spaces=0)
{
  if($real_root == NULL)
	{
	echo("print_menu() passed $real_root = NULL ");
	return;
	}

  if ($root == NULL)
    return;

  $main_URL = "http://prestopnik.com/";
  $test_string = $GLOBALS["SERVER_NAME"] . $GLOBALS["PATH_INFO"];
  $thisURL = $GLOBALS["PATH_INFO"];

  for($i = 0; $i < count($root->children_pages); $i++)
    {
	   display_menu_node($real_root, $root->children_pages[$i],$num_spaces);
		 print_menu($real_root, $root->children_pages[$i],$num_spaces+3);		
		}
}

function getNodesFromURL($root, $url)
{
  $nodes = array();
	$tmpNodes = array();

 if($root->url == $url)
 {
$nodes[0] = new menu_tree_node();
	$nodes[0] = $root;
 }	

 for($i = 0; $i < count($root->children_pages); $i++)
   {
    $tmpNodes = getNodesFromURL($root->children_pages[$i], $url);
 		$nodes = array_merge($nodes,$tmpNodes);
	 }
	 return $nodes;
}

function display_menu_node($root, $node, $num_spaces)
{
 $thisURL = $GLOBALS["PATH_INFO"];
 $thisURL = substr($thisURL,1); //remove leading slash
 $thisNodes = getNodesFromURL($root, $thisURL);

 //print all pages that are children of the root
 if( is_parent($root,$node)) 	
   	{
	  print_node_link($node,$num_spaces);
		return;
 	  }
//thisNodes are the nodes that represent the page currently being viewed
//$node is the node that may be printed as part of the menu.
 for($i = 0; $i < count($thisNodes); $i++)
 {	 	 
 	 //print all siblings of this page
   if( is_sibling($root, $node, $thisNodes[$i]))
   {
	  print_node_link($node,$num_spaces);
		return;
	 }
	 //print all children of this page 
   if (is_child($thisNodes[$i],$node))
   {
	  print_node_link($node,$num_spaces);
		return;
 	 }
	 //print all nodes in the path from the root to this page
   if ( in_path($node,$root,$thisNodes[$i]))
   {
	  print_node_link($node,$num_spaces);
		return;
 	 }
 }
}

function is_parent($node_p, $node)
{
  for($i = 0; $i < count($node_p->children_pages); $i++)
		  if($node_p->children_pages[$i] == $node)
					return true;

return false;
}

function is_sibling($root, $node1, $node2)
{
 $parent1 = get_parent_n($root,$node1);
 $parent2 = get_parent_n($root,$node2);

 if($parent1 == $parent2)
   return true;
 else
	 return false;
}

function is_child($node_p, $node_c)
{
   for($i = 0; $i < count($node_p->children_pages); $i++)
	 				if ($node_p->children_pages[$i] == $node_c)
						 return true;

return false;
}


function is_ancestor($node, $node_a)
{
 return is_descendent($node_a, $node);
}

function is_descendent($node, $node_d)
{
 if($node == NULL)
 	return false;

 if($node_d == NULL)
  return false;	

 if ($node == $node_d)
 	return true;

 if(is_child($node,$node_d))
 		return true;		

 for($i = 0; $i < count($node->children_pages); $i++)
 				if( is_descendent($node->children_pages[$i], $node_d))
				   return true;

 return false;
}


//returns true if $node_bottom is a descendent of $node and a $node_top is an ancestor of $node) 
function in_path($node, $node_top, $node_bottom)
{
 return (is_descendent($node,$node_bottom) && is_ancestor($node,$node_top));
}

function print_node_link($node,$num_spaces)
{
  if( $node == NULL)
    return;

  $url = "http://" . $GLOBALS["SERVER_NAME"] . "/" . $node->url;

  if ($node->hidden == false)
    {
		  echo("<$node->font_size>");
      for($j=0; $j<$num_spaces; $j++)
	      echo("&nbsp;");

  print_unfinished_link($node->menu_name, $url);
  echo("</$node->font_size>");
		echo("</a>");

		if ($node->icon != "none")
			 echo ("<img src=\"http://prestopnik.com/$node->icon\">");		

		echo("<br>\n");
}
}

function print_unfinished_link($name, $url)
{
  $test_string = "http://" . $GLOBALS["SERVER_NAME"] . $GLOBALS["PATH_INFO"];
  if($url == $test_string)
    echo("$name");
  else
    {
		 $trimmed_name = ltrim($name);
		 $len1 = strlen($name);
		 $len2 = strlen($trimmed_name);
		 for($i=0; $i<($len1-$len2); $i++)
		   echo("&nbsp;");

 echo("<a href=\"$url\">$trimmed_name");
}
}

function get_this_parent($root)
{
//  $thisPage = $GLOBALS["SERVER_NAME"] . $GLOBALS["PATH_INFO"];
    $thisPage = $GLOBALS["PATH_INFO"];
    $thisPage = substr($thisPage,1); //remove leading slash
  return get_parent($root, $thisPage);
}

[Roger_Ramjet]

Ask to see phpinfo() to find out what the configuration is, if you know how to interpret that properly.

Look for someone hosting on Sun Cobalt or Cube servers. Purpose built and about as good as it gets. Definitely avoid NT boxes, Linux or any Unix flavour is a must.

Ask how many other sites you'll share the server with, and who they are. Quickest answer to Q2b is to find out what other site you'll share the server with and see how they run. Bear in mind that sharing a server with sites that get lots of trafic is really going to affect yours unless they have rigid bandwidth and cpu cycle rationing in place: if they do then it does not matter much what the other sites' traffic is like.

Expect to pay @ £200 pa for web space and MySQL at a decent host. The economics just don't work out any less. If they are charging much less then the server must be overloaded just to pay for itself.

[Ozyman]

Thank you.

As far as speeding up my code goes. I've come up with two possible solutions, that I'll mention at the end of this post.

Since I think I've solved the question of how to speed up my code, I'm more interested in other opinions about how to verify I have a decent web server, or find a good one.

A question for Roger Ramjet. What does @ £200 pa mean? I know £200 is about 387 USD, but what does the pa mean? Is that per annum (per year)?

Also, is there anything in particular I should look for on phpinfo(). I have this on a page for my server at prestopnik.com/info.php. I know that I can verify a PHP version and a system type (4.0.6 and SunOS src 5.7 Generic_106541-12 sun4u sparc SUNW,UltraSPARC-IIi-cEngine for my site). Is there anything else I should be looking at?

Thanks again for any responses.

more efficient coding solutions:

First possibilty, I could build a hash table of some sorts that captures the parent/children relationships in the tree. Then I wouldn't have to traverse the tree nearly as much, because for most checks I could just do a simple lookup in a hash table.

A second option, and I think this is the better one. I think I can do the whole thing in two traversals of the tree. In the first traversal, I can mark each node as to whether it needs to be displayed, and then display them in the second traversal. I'd do this by doing an in-order traversal of the tree, and returning a code based on whether I've found the node or not. I think I've got it figured out in my head, and I'm going to try and write it this weekend, if anyone is curious to see it let me know.

[Weedpacket]

This could be interesting to tinker on a code basis. If you could post a sample of the tree text file to test with, I've got a couple of ideas that may bear fruit - actually one of them was the two-pass approach: build the tree and then display it. (A quick-and-dirty code-level change is to use [man]in_array[/man] instead of walking a node's children by hand.)

Roger Ramjet's estimate re: economics is probably right; my thinking is that if the service provider hasn't made the effort to upgrade their PHP service in the last three years they're unlikely to have forked out the dosh to get in new hardware (which over the same time scale would work out to be about four times faster than what they would have bought for the same money). Going by the description from phpinfo, it looks like this is the machine. On things like cache, clock speed and memory access, my laptop's processor beats it (though of course it's only 32-bit).

Yes, pa is per annum.

[Ozyman]

If you could post a sample of the tree text file to test with

You can download the actual tree text file that I use for my website from
prestopnik.com/menu.dat .

Hopefully I'll get a chance to do that rewrite today, once I get it done I'll post the results here.

Thanks again for all the info.

[Ozyman]

ok, here's how I ended up solving it. In writing this, I ran into a bug that took me a while to catch. Turns out I needed to pass the $root paramater by reference to determine_print_values().

Finding that bug made me think that maybe if I had passed things around by reference in the first place that would at least have helped things some. oh well, this solution is better in the long run.

function load_and_print_menu($file_name)

{

$root = load_tree($file_name);

determine_print_values($root,true);

smart_print_menu($root,$root);


}


//no two nodes can have the same URL if one is descendent from the other
//if $set_children == true, then set all children print_value to 1
function determine_print_values(&$root, $set_children)
{
 $thisURL = $GLOBALS["PATH_INFO"];

 $thisURL = substr($thisURL,1); //remove leading slash

 if ($thisURL == $root->url)
 {

  for($k = 0; $k < count($root->children_pages); $k++)
	{
	  $root->children_pages[$k]->print_value = 1;
 	  //determine_print_values($root->children_pages[$k],false);
	} 		
	$root->print_value = 1;

 }
 else
  for($i = 0; $i < count($root->children_pages); $i++)
  {
	 if ($set_children)
	 {
		   $root->children_pages[$i]->print_value = 2;

 }

 determine_print_values($root->children_pages[$i], false);
 if($root->children_pages[$i]->print_value > 0)
 {


   $root->print_value = ($root->children_pages[$i]->print_value) + 1;

	 if ($root->children_pages[$i]->print_value == 1)
	     for($j = 0; $j < count($root->children_pages); $j++)
			 {
			 $root->children_pages[$j]->print_value = 2;

				 } 
 }	   
}
}

//traverse the list and print any node that has print_value > 0
function smart_print_menu($real_root, $root, $num_spaces=0)
{
  if($real_root == NULL)
	{
	echo("print_menu() passed $real_root = NULL ");
	return;
	}

  if ($root == NULL)
    return;

  $main_URL = "http://prestopnik.com/";
  $test_string = $GLOBALS["SERVER_NAME"] . $GLOBALS["PATH_INFO"];

   $thisURL = $GLOBALS["PATH_INFO"];


  if($root->print_value > 0)
   	 print_node_link($root,$num_spaces);

  for($i = 0; $i < count($root->children_pages); $i++)
  	 smart_print_menu($real_root, $root->children_pages[$i],$num_spaces+3);		
}