3
\$\begingroup\$

If I have a long string:

// 10MB string
$string='';
for($run=0; $run<1000000; $run++)
$string.='012345689';

Then I perform many substr, cutting off small portions from the beginning.

for($run=0; $run<100000; $run++)
{
$temp=substr($string,0,10);
DoSomething($temp);
$string=substr($string,10);
}

It is VERY slow (20 seconds), which I tracked down to: substr($string,10) as the cause of the problem. Seems it is rebuilding the entire variable each time, which slowing the whole script down.

How can this be optimized, without incrementing the start offset of the first substr in the second code fragment?

EDIT: for those who are upset, the reason why I don't want to use an offset is because this would require keeping the entire string in memory the whole time. I'm trying to optimize both speed and memory.

\$\endgroup\$
14
  • \$\begingroup\$ Is the length of the substrings cut off at the beginning constant? \$\endgroup\$ – Eugen Rieck Dec 27 '11 at 13:01
  • \$\begingroup\$ There is no reason not to keep track of offsets, simply do $temp = substr( $string, $offset, 10 ); $offset += 10;.... instead of $string=substr($string,10); \$\endgroup\$ – Esailija Dec 27 '11 at 13:03
  • \$\begingroup\$ Can you use a list rather a single string? \$\endgroup\$ – Peter Lawrey Dec 27 '11 at 13:03
  • 2
    \$\begingroup\$ Is this a real world use case - Doing 100000 operations on 1MB of data? \$\endgroup\$ – Pekka Dec 27 '11 at 13:03
  • \$\begingroup\$ Yes, it is constant. I padded all the values out so that I wouldn't have to search. \$\endgroup\$ – Alasdair Dec 27 '11 at 13:04
4
\$\begingroup\$

Use

for($run=0; $run<100000; $run++)
{
$temp=substr($string,$run*10,10);
DoSomething($temp);
//$string=substr($string,10);
}

You trade RAM for performance: The original string will not become shorter, but you don't need the very expensive copying of the string again and again

\$\endgroup\$
10
  • \$\begingroup\$ I was hoping there might be a way to cut the string without having to copy it over and over again. That sounds plausible to me. If it can't be done in PHP, then OK, this is the answer. \$\endgroup\$ – Alasdair Dec 27 '11 at 13:13
  • \$\begingroup\$ Small additional improvement: Rename $run to $offset and don't do $run++ but $offset += 10, so instead of increment and multiplication it only has to do an addition ... additionally saves a temporary variable (result of $run*10) ... while the effect will be hardly measurable relative to substr and DoSomething ;-) \$\endgroup\$ – johannes Dec 27 '11 at 13:20
  • \$\begingroup\$ How is it trading ram for performance? Both, RAM usage and performance are significantly better in the braindead obvious offset solution. I just tested it and memory_get_peak_usage() is 1.95 times higher than when using offset. \$\endgroup\$ – Esailija Dec 27 '11 at 13:21
  • \$\begingroup\$ It's thinkable to create something which will chop the string without copy, but that's not what makes sense in PHP as it has some downsides like disabling coy-on-write. Also mind that choping stuff of would usually not result in memory actually returned to a usable pool unless the shorter string is copied to some other memory segment. \$\endgroup\$ – johannes Dec 27 '11 at 13:24
  • 1
    \$\begingroup\$ @johannes True but that metric is pretty useless. You will have to allocate 10mb vs 20mb for your script, which one you want? \$\endgroup\$ – Esailija Dec 27 '11 at 13:30
0
\$\begingroup\$

You can split string into array and then free memory by unsetting array elements when you don't need them anymore. Of cource PHP has big overhead for arrays, so you should split string into bigger parts then your read chunk size. Splitting a string by big chunks shouldn't be too slow. Example (badly tested, just a basic idea):

<?php
class ScumbagString {
    //Our main strings array
    private $string_array=array();

    //Basic settings
    private $chunk_size;
    private $array_element_size;

    //Array position variables
    private $insert_key;
    private $read_key;

    //Positions in array elements
    private $insert_element_space_left;
    private $read_offset;

    /**
     * 
     * @param Integer $chunk_size Size of a string you will read each time
     * @param Integer $chunks_concated Number of chunks in one array element
     * @param String $string String to add to internal array
    */
    public function __construct($chunk_size=10,$chunks_concated=1000,&$string='') {
        //Set default variables
        $this->insert_key=0;
        $this->read_key=0;

        $this->read_offset=0;

        $this->string_array[0]='';


        //Process passed variables
        $this->chunk_size=$chunk_size;
        $this->array_element_size=$chunk_size*$chunks_concated;
        $this->insert_element_space_left=$this->array_element_size;

        if($string) {
            $this->add($string);
        }
    }

    /**
     * Adds a string to the end of internal array
     * @param String $string String to add
     */
    public function add(&$string) {
        $str_length_left=strlen($string);
        $offset=0;
        while($str_length_left) {
            $substr_len=min($this->insert_element_space_left,$str_length_left);

            $this->string_array[$this->insert_key].=substr($string,$offset,$substr_len);
            $offset+=$substr_len;
            $str_length_left-=$substr_len;
            if($substr_len===$this->insert_element_space_left) {
                $this->insert_key++;
                $this->string_array[$this->insert_key]='';

                $this->insert_element_space_left=$this->array_element_size;
            }
            else {
                $this->insert_element_space_left-=$substr_len;
            }
        }


    }

    /**
     * Get a chunk from internal array.
     * @return Mixed Either a string of $chunk_size from the begining of array or FALSE if fails.
     */
    public function get() {
        //This is a special case
        if($this->read_key===$this->insert_key) {
            //Check if we have enough data written to read
            if($this->read_offset+$this->chunk_size>$this->array_element_size-$this->insert_element_space_left) {
                return FALSE;
            }
        }

        $return_str=substr($this->string_array[$this->read_key],$this->read_offset,$this->chunk_size);

        $this->read_offset+=$this->chunk_size;

        if($this->read_offset>=$this->array_element_size) {
            $this->read_offset=0;
            unset($this->string_array[$this->read_key]);
            $this->read_key+=1;
        }

        return $return_str;
    }
}
$sStr=new ScumbagString(10,5000);

$string='';
for($run=0; $run<1000000; $run++) {
    $string.='0123456789';
    //If it is possible - avoid using $string at all, just do 
    //$sStr->add('0123456789'); to lower peak memory usage
}

$sStr->add($string);

//Free string if you will not use it anymore
unset($string);

//In this cycle memory usage should slowly drop
//It will not drop by 10 each iteration, but it should drop
//by 10*5000 (+ array element overhead) each 5000's iteration.
for($run=0; $run<1000000; $run++)
{
    $temp=$sStr->get();
    DoSomething($temp);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy