My online STV election system has thrown some challenges my way this week with the issue of memory eating.

PHP, unlike many languages doesn't have a true garbage collector, I know many can argue that PHP5 does add some additional ways to collect reference cycles but overall, unless you implement what you want to achieve in the most efficient way, you will be doomed when your memory consumption quickly soars.

The STV application implements a variety of methods to determine a winner including; Approval, Borda, Condorcet (using a Schwartz Sequential Dropping with a Beatpath Matrix for ties), Instant Runoff, Meek and Plurality. It is important that each of the methods share a common interface and abstract layered implementation so that I can easily add methods later in development (as was the case with SSD). However, elections tend to have thousands if not hundreds of thousands of ballots, take this simple example:

# Our test constant
define('BALLOT_TEST', 10000);
define('CANDIDATE_TEST', 10);
# Define ballots, where we will store them
$ballots = array();
# Create a test loop
for($i = 0; $i < BALLOT_TEST; $i++) {
     $ballots[] = range(0, rand(CANDIDATE_TEST / 2, CANDIDATE_TEST));

The example above simply creates an array of all ballots (for every one, I'm assuming we have expressed a preference for at least 1/2 of the candidates, such that the ballots may vary in size. At the start of development, it was a simple solution however the memory needed as my testing went along was quite simply ridiculous.

Logically, we need a way to handle our ballots in a much more efficient way, take this simple example:

# Define structures
$uniqueBallots = array();
$uniqueBallotsCounts = array();
$uniqueBallotsLookup = array();
# Create a test loop
for($i = 0; $i < BALLOT_TEST; $i++) {
    # Create a random ballot
    $ballot = range(0, rand(CANDIDATE_TEST / 2, CANDIDATE_TEST));
    # Generate a string (some custom method implemented)
    $string = \Election::toString($ballot);
    # Check unique?
    if(!empty($uniqueBallotsLookup[$string])) {
        $uniqueIndex = $uniqueBallotsLookup[$string];
    } else {
        $uniqueBallots[] = $ballot;
        $uniqueIndex = count($uniqueBallots) - 1;
        $uniqueBallotsCount[$uniqueIndex] = 1;
        $uniqueBallotsLookup[$string] = $uniqueIndex;

The trade-off between the two code examples isn't too demanding in terms of processing. It means I need to keep track of more variables and further down the line I need to remember how everything was formatted and what is stored where, but it saves memory usage of over 120% (from random tests I ran).

Freeing a reference in PHP

References are ideal if you're going to pass data back-and-forth, most variables are passed by reference without you even having to add or change your code, instead the PHP interpreter handles them as references by default:

 * Some example function (returns reference with a reference input)
 * @param $reference - Reference to a variable
 * @access private
private function &referenceResponse(&$reference) {
    $array = array(
        'test' => true,
        'reference' => $reference
    return $array;
$var = 1;
# Returns a pointer (reference)
$result =& $this->referenceResponse($var);
# Do some processing
# ....
# Free up, but how?
# Nope, that just removed our the reference between $result and $array
$result = NULL;

If you've got a lot of cycled pointers, as I often end up with, the easiest way to clean and force your memory to be free'd up is by setting it to NULL, that will set the original value to NULL instead of just the reference variable.

Tackling slow scripts

If your script is slow (I personally mean anything over 1 second to load as I'm keen on efficient coding to the best as PHP can, anyway) then it is important you debug what's causing your code to run slowly and check where your memory increases:

# Timer at the start
$startTime = microtime(true);
$startMemory = memory_get_usage();
# Whatever your code does
for($x = 0; $x < 5000000; $x++) {
    $test = new Test;
    echo 'Memory: '.(memory_get_usage() - $startMemory).'<br />';
# End of script
$endTime = microtime(true);
$endMemory = memory_get_usage();
# Output
echo 'Loaded in: '.($endTime - $startTime).' seconds.<br />';
echo 'Memory usage: '.($endMemory - $startMemory).'<br />';
echo 'Peak usage: '.memory_get_peak_usage();

Have you got any PHP benchmarks for your code? Let me know your comments by mentioning #ALJTMedia on Twitter or leave a comment on our Facebook or Google+ page.

Other Resources

Ignite your brand, utilise user-generated content no matter where you or your audience are ›