Memory saving trick

[btherl]

I just discovered a cute way to save memory in php. One of my favorite data structures is an inverted array where the interesting values are the keys, and the array values are meaningless. For example:

 

array(
  0 => "bunny",
  1 => "paboom",
  2 => "mummy",
);

 

becomes

 

array(
  "bunny" => true,
  "paboom" => true,
  "mummy" => true,
);

 

The idea is that I can check for array values in constant time now. The loss of the indices is not important because the data was not ordered to begin with, even though it was represented as an ordered array. Basically it's a hash table.

 

The only problem here is that I'm storing a copy of true for every single array entery. What can we do about that?

 

$start_mem = memory_get_usage();
$arr2 = array();
$bool = true;
for ($i = 0; $i < 10000; $i++) {
  $arr2[$i] =& $bool;
}
$end_mem = memory_get_usage();
print "Used " . ($end_mem - $start_mem) . " bytes for 10000 references to \$bool with integer keys\n";

$start_mem = memory_get_usage();
$arr = array();
for ($i = 0; $i < 10000; $i++) {
  $arr[$i] = true;
}
$end_mem = memory_get_usage();
print "Used " . ($end_mem - $start_mem) . " bytes for 10000 copies of true with integer keys\n";

 

Used 465776 bytes for 10000 references to $bool with integer keys

Used 625600 bytes for 10000 copies of true with integer keys

 

There you have it. Instead of storing a copy of true for every array element, I simply use one copy of true and create many references to it. The memory savings are around 25%

 

I'm interested in hearing about any other data structures in use by php programmers out there.

[btherl]

Whoops, there is a serious problem with this in php4.  Reference counts are 16 bit, so it's easy to overflow.  This is fixed in php5 however.  The 32 bit reference count there means you can reference the bool until your memory runs out without running into the reference count limit.

[shunting]

The cool think about this trick is that it shows a way to represent sets, where the members of the set are all keys, because (1) keys are guaranteed to be unique, and (2) when arrays are compared the order of the keys is not significant, and all the values are guaranteed to be identical!

$first = array('a'=>true,'b'=>true,'c'=>true,'d'=>true);
$second = array('d'=>true,'c'=>true,'b'=>true,'a'=>true);

if ($first == $second) {
  echo 'SETS ARE EQUAL';
} else {
  echo 'set are not equal';
}

And the memory trick is just the icing on the cake (at least in PHP5).