php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Bug #18829 array_pop, array_shift, array_push... functions very slow with large arrays
Submitted: 2002-08-09 07:22 UTC Modified: 2002-10-28 14:05 UTC
Votes:5
Avg. Score:4.0 ± 0.9
Reproduced:3 of 3 (100.0%)
Same Version:2 (66.7%)
Same OS:2 (66.7%)
From: jean-charles dot rogez at devoteam dot com Assigned: rodif_bl (profile)
Status: Wont fix Package: Arrays related
PHP Version: 4.2.2 OS: Linux RedHat 7.1
Private report: No CVE-ID: None
Have you experienced this issue?
Rate the importance of this bug to you:

 [2002-08-09 07:22 UTC] jean-charles dot rogez at devoteam dot com
The following program takes a very long time to execute.

On the same machine (P4 1.5GHz), under the same conditions, with N=50, PHP needs 87m30s !?!! The same program written in PERL 5.6 needs only 2.415s and in python 2.1.2 3.273s ! array_pop and array_push functions seems to be extremelly slow with large arrays. This problem has been detected on PHP 4.0.6 and is still present in 4.2.2.
4.2.2 was compiled with the default settings (configure without arguments).

<?php

function test_lists() {
  global $size;

# create a list of integers (Li1) from 1 to SIZE
  $Li1 = array();
  $Li1 = array_pad($Li1, $size, 0);

# copy the list to Li2 (not by individual items)
  $Li2 = $Li1;
  $Li3 = array();

# remove each individual item from left side of Li2 and
# append to right side of Li3 (preserving order)
  while ($Li2) {
    $Li3[] = array_shift($Li2);
  }
# Li2 must now be empty
# remove each individual item from right side of Li3 and
# append to right side of Li2 (reversing list)
  while ($Li3) {
    $Li2[] = array_pop($Li3);
  }
# Li3 must now be empty
# reverse Li1 in place
  $Li1 = array_reverse($Li1);
# check that first item is now SIZE
  if ($Li1[0] != $SIZE) return(0);
# compare Li1 and Li2 for equality
  $len1 = count($Li1);
  $len2 = count($Li2);
  $lists_equal = ($len1 == $len2);
  if (! $lists_equal) return(0);
  for ($i=0; $i<$len1; $i++) {
    if ($Li1[$i] != $Li2[$i]) {
      $lists_equal = 0;
      break;
    }
  }
  if (! $lists_equal) return(0);
# return the length of the list
  return($len1);
}

$size = 10000;
$ITER = $argv[1];
if ($ITER < 1) $ITER = 1;
$result = 0;
?>

Patches

Add a Patch

Pull Requests

Add a Pull Request

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2002-08-09 07:29 UTC] jean-charles dot rogez at devoteam dot com
Oops ! I forgot the end of the script
Add

while ($ITER-- > 0) {
  $result = test_lists();
}
print "$result\n";
?>

In the previous comment, N meant ITER. (ITER = 50)
 [2002-08-09 09:03 UTC] rodif_bl@php.net
This bug has been fixed in CVS. You can grab a snapshot of the
CVS version at http://snaps.php.net/. In case this was a documentation 
problem, the fix will show up soon at http://www.php.net/manual/.
In case this was a PHP.net website problem, the change will show
up on the PHP.net site and on the mirror sites.
Thank you for the report, and for helping us make PHP better.

I recently fixed the speed for array_shift and array_pop. I\'ll look at array_push see if there is anything good there. Try current CVS and tell me if the speed increased for you.
 [2002-08-09 12:59 UTC] rodif_bl@php.net
I ran current cvs and it was alot faster but still not fast enough.

with your example with 50 itterations

4m55.514s

1 itteration was about 
5 seconds

this is running on 1.2 p3



 [2002-08-10 05:39 UTC] edink@php.net
I did some testing on your function and it seems that array_shift is to blame. If I avoid using that function, the execution time drop down to few seconds. To cut down the problem:

  $size = 5000;
  $Li1 = array();
  $Li1 = array_pad($Li1, $size, 0);
  $Li2 = array();

  while ($Li1) {
    $Li2[] = array_shift($Li1);
  }

This takes 1.8 s on my P3 933 MHz. If I increase $size to 10000 it takes 16 s.

The rest of array functions seem to be working fine.
 [2002-08-12 04:25 UTC] jean-charles dot rogez at devoteam dot com
Same results than you. The script takes approximately 4 minutes on my P4 1.5Ghz with the latest CVS (before it was 87m...). After correction of the array_shift function, PHP should be in the same time than Perl or Python.
 [2002-08-12 09:18 UTC] rodif_bl@php.net
The problem wasn't just array_shift it was array_shift and array_pop. array_shift is whats causing the slowness now but way its implemented now I really don't think it can get much faster. Basically when you shift of the top of the array it needs to re-index the entire array meaning if you have 10,000 records it needs to loop thru all 10,000 changing the index. If the function didn't need to do this it wouldn't take nearly as long. Does it work this way in perl or python.

$a = array(1,2);
array_shift($a);
echo $a[0];
 [2002-08-13 04:11 UTC] jean-charles dot rogez at devoteam dot com
In perl :

@a = (1, 2, 3);
shift(@a);
print "$a[0], $a[1]";

Result : 2, 3

This is correct.

I don't know how the shift function is implemented in perl, but i think arrays are not reindexed like in PHP, else it shouldn't be so fast.
 [2002-08-13 20:45 UTC] kalowsky@php.net
Assigning to Brad, as he seems to be working on it... a bit.
 [2002-10-28 14:05 UTC] sterling@php.net
PHP is not perl, since arrays are bastards (the unwed child of a hash and array) there is really not a more efficient way to handle this, without breaking things badly...
 [2012-06-20 16:45 UTC] tszming at gmail dot com
Maybe some optimization can be done if we know a variable is an array but not a 
hash? 

I believe JavaScript also share similar issue and they got optimized finally, e.g: 
https://bugzilla.mozilla.org/show_bug.cgi?id=394448
 
PHP Copyright © 2001-2017 The PHP Group
All rights reserved.
Last updated: Sun Nov 19 01:31:42 2017 UTC