How to save memory when using the hierarchical structure of an object

Question

I have a simple thing thing that can have children of the same type.

This object has a toHTML method that does something like:

$html = '<div>' . $this->name . '</div>'; $html .= '<ul>'; foreach($this->children as $child) $html .= '<li>' . $child->toHTML() . '</li>'; $html .= '</ul>'; return $html; 

The problem is that when the object is complex, for example, a lot of children with children with children, etc., memory use increases.

If I just print_r multidimensional array that powers this object, I get 1 MB of memory usage, but after I convert the array to my object and do print $root->toHtml() , it takes 10 MB !!

How can i fix this?

======================================

Made a simple class similar to my real code (but smaller):

 class obj{ protected $name; protected $children = array(); public function __construct($name){ $this->name = $name; } public static function build($name, $array = array()){ $obj = new self($name); if(is_array($array)){ foreach($array as $k => $v) $obj->addChild(self::build($k, $v)); } return $obj; } public function addChild(self $child){ $this->children[] = $child; } public function toHTML(){ $html = '<div>' . $this->name . '</div>'; $html .= '<ul>'; foreach($this->children as $child) $html .= '<li>' . $child->toHTML() . '</li>'; $html .= '</ul>'; return $html; } } 

And tests:

 $big = array_fill(0, 500, true); $big[5] = array_fill(0, 200, $big); print_r($big); // memory_get_peak_usage() shows 0.61 MB $root = obj::build('root', $big); // memory_get_peak_usage() shows 18.5 MB wtf lol print $root->toHTML(); // memory_get_peak_usage() shows 24.6 MB 

Answer 1

Introduction

Since you are outputting HTML output, there is no need to save it indirectly, consuming memory.

Here is a simple class that:

• Creates a menu from a multidimensional array
• Effective memory uses Iterator
• You can write to Socket , Stream , File , array , Iterator , etc.

Example

 $it = new ListBuilder(new RecursiveArrayIterator($big)); // Use Echo $m = memory_get_peak_usage(); $it->display(); printf("%0.5fMB\n", (memory_get_peak_usage() - $m) / (1024 * 1024)); 

Output

 0.03674MB 

Other output interfaces

 $big = array_fill(0, 500, true); $big[5] = array_fill(0, 200, $big); 

Simple Compare

 // Use Echo $m = memory_get_peak_usage(); $it->display(); $responce['echo'] = sprintf("%0.5fMB\n", (memory_get_peak_usage() - $m) / (1024 * 1024)); // Output to Stream or File eg ( Socket or HTML file) $m = memory_get_peak_usage(); $it->display(fopen("php://output", "w")); $responce['stream'] = sprintf("%0.5fMB\n", (memory_get_peak_usage() - $m) / (1024 * 1024)); // Output to ArrayIterator $m = memory_get_peak_usage(); $it->display($array = new ArrayIterator()); $responce['iterator'] = sprintf("%0.5fMB\n", (memory_get_peak_usage() - $m) / (1024 * 1024)); // Output to Array $m = memory_get_peak_usage(); $it->display($array = []); $responce['array'] = sprintf("%0.5fMB\n", (memory_get_peak_usage() - $m) / (1024 * 1024)); echo "\n\nResults \n"; echo json_encode($responce, 128); 

Output

 Results { "echo": "0.03684MB\n", "stream": "0.00081MB\n", "iterator": "32.04364MB\n", "array": "0.00253MB\n" } 

Used class

 class ListBuilder extends RecursiveIteratorIterator { protected $pad = "\t"; protected $o; public function beginChildren() { $this->output("%s<ul>\n", $this->getPad()); } public function endChildren() { $this->output("%s</ul>\n", $this->getPad()); } public function current() { $this->output("%s<li>%s</li>\n", $this->getPad(1), parent::current()); return parent::current(); } public function getPad($n = 0) { return str_repeat($this->pad, $this->getDepth() + $n); } function output() { $args = func_get_args(); $format = array_shift($args); $var = vsprintf($format, $args); switch (true) { case $this->o instanceof ArrayIterator : $this->o->append($var); break; case is_array($this->o) || $this->o instanceof ArrayObject : $this->o[] = $var; break; case is_resource($this->o) && (get_resource_type($this->o) === "file" || get_resource_type($this->o) === "stream") : fwrite($this->o, $var); break; default : echo $var; break; } } function display($output = null) { $this->o = $output; $this->output("%s<ul>\n", $this->getPad()); foreach($this as $v) { } $this->output("%s</ul>\n", $this->getPad()); } } 

Conclusion

As you can see, an iterator loop is fast, but storing values ​​in an iterator or object may not be as efficient.

Answer 2

The problem is that you are buffering all the data in memory that you do not actually need, because you are simply outputting the data, not processing it.

Instead of buffering everything in memory, if all you want to do is output it, you should simply output it to where it will be:

 public function toHTMLOutput($outputStream){ fwrite($outputStream, '<div>' . $this->name . '</div>'; fwrite($outputStream, '<ul>'); foreach($this->children as $child){ fwrite($outputStream, '<li>'); $child->toHTMLOutput($outputStream); fwrite($outputStream, '</li>');} } fwrite($outputStream, '</ul>'); } $stdout = fopen('php://stdout', 'w'); print $root->toHTMLOutput($stdout); 

or if you want to save the output to a file

 $stdout = fopen('htmloutput.html', 'w'); print $root->toHTMLOutput($stdout); 

Obviously, I only implemented it for the toHTML() function, but the same principle should be used for the build function, which can lead to the fact that you generally skip the separate HTTML function.

Answer 3

The total number of elements in your array is just over 100,000.

Each element of your array is just one byte (logical), so for more than 100,000 elements, it takes 100,000 bytes ~ 0.1 MB

Each of your objects is ~ 100 bytes, this is 100 * 100000 = 100000000 bytes ~ 10 MB

But you have ~ 18 MB, so where is it 8 of?

If you run this code

 <?php $c = 0; //we use this to count object isntances class obj{ protected $name; protected $children = array(); public static $c=0; public function __construct($name){ global $c; $c++; $this->name = $name; } public static function build($name, $array = array()){ global $c; $b = memory_get_usage(); $obj = new self($name); $diff = memory_get_usage()-$b; echo $c . ' diff ' . $diff . '<br />'; //display change in allocated size if(is_array($array)){ foreach($array as $k => $v) $obj->addChild(self::build($k, $v)); } return $obj; } public function addChild(self $child){ $this->children[] = $child; } public function toHTML(){ $html = '<div>' . $this->name . '</div>'; $html .= '<ul>'; foreach($this->children as $child) $html .= '<li>' . $child->toHTML() . '</li>'; $html .= '</ul>'; return $html; } } $big = array_fill(0, 500, true); $big[5] = array_fill(0, 200, $big); $root = obj::build('root', $big); 

You will notice that the change is permanent with the exception for objects created as 1024th, 2048th, 4096th ...

I don’t have a link to any article or manual page about this, but I assume that php holds links to each created object in an array with an initial size of 1024. When you make this array full, its size will be doubled to make space for new objects .

If you differ from, for example, the 2048th object, subtract the size of the object (the constant value that you have on the other lines) and divide by 2048, you will always get a 32-standard pointer size in C.

So, for 100,000 objects, this array has grown to the size of 131072 elements. 131072 * 32 = 4194304B = 4 MB

This calculation is approximate, but I think it answers your question, which takes up so much memory.

To answer the question of how to save memory, avoid using objects for a large data set.

Obviously, objects are nice and simple, but primitive data types are faster and smaller.

Perhaps you can make it work with a single object containing an array of data. It is difficult to propose an alternative without additional information about these objects and what methods / interface they require.

Answer 4

One thing that can catch you is that you can get close to the exit of your stack due to recursion. In this case, it might make sense to create a rendering function that processes the tree as a whole for rendering instead of relying on recursion to do the rendering for you. For information on this, see Tail Call Recursion and Tail Call Optimization.

To adhere to the current code structure and avoid many resource problems that you are likely to encounter with the simplest solution, it may just pass the html string as a link:

 class obj{ protected $name; protected $children = array(); public function __construct($name){ $this->name = $name; } public static function build($name, $array = array()){ $obj = new self($name); if(is_array($array)){ foreach($array as $k => $v) $obj->addChild(self::build($k, $v)); } return $obj; } public function addChild(self $child){ $this->children[] = $child; } public function toHTML(&$html = ""){ $html .= '<div>' . $this->name . '</div>'; $html .= '<ul>'; foreach($this->children as $child){ $html .= '<li>'; $html .= $child->toHTML($html); $html .= '</li>'; } $html .= '</ul>'; } } 

This will not allow you to move a bunch of duplicates of the partial tree until recursive calls are resolved.

Regarding the actual assembly of the tree, I think that most of the memory usage is just the price of a game with big data, your options are either rendering, and not creating a hierarchical model for rendering (just output output instead of building a tree) or use which Some caching strategies for caching copies of the tree of objects or copies of the rendered html depending on how the data is used on your site. If you control incoming data, you can add invalid corresponding cache keys to this workflow in order to keep the cache obsolete.