Which is faster?

An speed comparison of two pieces of code.

  • (2 Pages)
  • +
  • 1
  • 2

16 Replies - 1687 Views - Last Post: 16 March 2009 - 09:11 PM Rate Topic: -----

#1 grimpirate   User is offline

  • Pirate King
  • member icon

Reputation: 149
  • View blog
  • Posts: 717
  • Joined: 03-August 06

Which is faster?

Posted 15 March 2009 - 02:49 PM

Alright so I've been thinking about the abs function recently. Obviously, the abs function works on both integers and floats, but in my own code I know I will ONLY be dealing with integers. So my question is which of these two procedures would be quicker given the integer, $number
$number = abs($number);
OR
if($number & 0x80000000) $number = ($number ^ 0xffffffff) + 1;
// alternative approach
if($number < 0) $number = ($number ^ 0xffffffff) + 1;
My guess is the second one will be much quicker, but I'm not sure how PHP does things at a low level.

This post has been edited by grimpirate: 15 March 2009 - 02:52 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Which is faster?

#2 AlienWebguy   User is offline

  • D.I.C Head

Reputation: 9
  • View blog
  • Posts: 84
  • Joined: 04-March 09

Re: Which is faster?

Posted 15 March 2009 - 02:57 PM

Wrap your function call in microtime()'s and see :)
Was This Post Helpful? 0
  • +
  • -

#3 AdamSpeight2008   User is offline

  • MrCupOfT
  • member icon

Reputation: 2298
  • View blog
  • Posts: 9,535
  • Joined: 29-May 08

Re: Which is faster?

Posted 15 March 2009 - 03:11 PM

Is this

Abs of n =Not(n) - 1

in PHP this?
(! $number) -1



or if True == 1
AbsOf n =  -((n && 2147483648) != 0) * n


This post has been edited by AdamSpeight2008: 15 March 2009 - 03:24 PM

Was This Post Helpful? 0
  • +
  • -

#4 grimpirate   User is offline

  • Pirate King
  • member icon

Reputation: 149
  • View blog
  • Posts: 717
  • Joined: 03-August 06

Re: Which is faster?

Posted 15 March 2009 - 03:43 PM

@AlienWebguy: I've already run microtime but I don't trust the results given that any number of exterior factors may affect the way microtime computes. For larger pieces of code I'd be happy to trust its values.

@AdamSpeight2008: I have no idea what you're even remotely alluding to with your notation as that's not PHP code. Please explain your questions/suggestions with complete sentences.

I'll assume I was asked what my procedure does. Basically, I test the high bit of a 32 bit number (if the high bit is set you know its a negative number). If its a negative number I compute the two's complement of said number (this yields the positive version of the number). The two's complement can be achieved by either NOT or an XOR operation with a mask of 0xffffffff (once upon a time when coding something in PHP the ! bitwise operator produced some sort of error so I no longer rely on it), and then adding 1 to the original number.

My logic is that using an if statement is much quicker than using a call to a function.
Was This Post Helpful? 0
  • +
  • -

#5 AdamSpeight2008   User is offline

  • MrCupOfT
  • member icon

Reputation: 2298
  • View blog
  • Posts: 9,535
  • Joined: 29-May 08

Re: Which is faster?

Posted 15 March 2009 - 04:04 PM

What I'm trying to do is use the result of the conditional as if it where an integer.
e.g.
False = 0
True = 1

If you do its possible to calculate the absolute directly
a =n * (1-(2*(( n & 2147483648) > 0) ) )

A little math, can save a lot coding.
Edit: Wrong AND

This post has been edited by AdamSpeight2008: 15 March 2009 - 04:16 PM

Was This Post Helpful? 0
  • +
  • -

#6 AdaHacker   User is offline

  • Resident Curmudgeon

Reputation: 463
  • View blog
  • Posts: 820
  • Joined: 17-June 08

Re: Which is faster?

Posted 15 March 2009 - 09:37 PM

View Postgrimpirate, on 15 Mar, 2009 - 04:43 PM, said:

@AlienWebguy: I've already run microtime but I don't trust the results given that any number of exterior factors may affect the way microtime computes. For larger pieces of code I'd be happy to trust its values.

Which is why you measure over a lot of iterations and do it several times. By measuring the total time for a large number of iterations, you take the relatively small inaccuracies in microtime out of the equation.

Just out of curiosity, I tried this out myself. I wrote up a quick script to calculate the absolute values of a pre-generated set of a million random integers between -1000 and 1000 using several methods. Here's the results. The numbers represent the time taken to complete all million calculations. These are approximate averages over several test runs.
Using asb() built-in - ~3.7 sec
Using grimpirate's method - ~1.5 sec
Using AdamSpeight2008's method - ~1.8 sec
Using my method - ~1.6 sec

I added my own method in there just because I wanted to see how a simpler version performed. The other 2 posted methods are rather long and, at a glance, it's not immediately obvious what they do. So my method was simply to apply the definition of absolute value:
if ($number < 0) $number = -$number;

So yes, for what it's worth, it seems that it is faster to skip the function call. Not that I can think of many situations where this would actually be a useful optimization, but at least it's an interesting piece of trivia.
Was This Post Helpful? 0
  • +
  • -

#7 grimpirate   User is offline

  • Pirate King
  • member icon

Reputation: 149
  • View blog
  • Posts: 717
  • Joined: 03-August 06

Re: Which is faster?

Posted 15 March 2009 - 11:22 PM

@AdaHacker: I'm working on a PNG creation library for PHP. Therefore, I need to optimize calculations to make them execute as quickly as possible. LOL, wow, abs is ridiculously slow by comparison.

@AdamSpeight2008: What I can discern from the following statement:
a=n * (1-(2*(( n & 2147483648) > 0) ) )
isthat you're isolating the 32nd bit, checking to see if its set, then multiplying by 2 in order to get 0 or 2, subtracting to get 1 or -1 and finally multiplying the number itself by either 1 or -1. However, I don't think php accepts integer values larger than (2^32) / 2 - 1 = 2147483647, as it doesn't understand unsigned integers I don't think, but I understand what you're doing. However, as a matter of optimization I would say that multiplications should always be avoided. So I could probably improve your code to somthing like the following
$a = $n * (1 - ((($n & 0x80000000) >> 30) << 1));
Left shifting by 1 is equivalent to multiplication by 2 and right shifting by 30 (not sure if that's quicker than comparison operator) would give you a 0 or 2 as you wanted previously. Given that this new procedure eliminates the if statement it may very well be quicker. Unfortunately, I can't think of a constructive way to eliminate the final multiplication by -1.

This post has been edited by grimpirate: 15 March 2009 - 11:30 PM

Was This Post Helpful? 0
  • +
  • -

#8 Valek   User is offline

  • The Real Skynet
  • member icon

Reputation: 544
  • View blog
  • Posts: 1,713
  • Joined: 08-November 08

Re: Which is faster?

Posted 15 March 2009 - 11:54 PM

abs() is running, at most, about 0.2 behind if($n & 0x80000000) $n = ($n ^ 0xffffffff) + 1; for me. I've done numerous tests.
Was This Post Helpful? 0
  • +
  • -

#9 grimpirate   User is offline

  • Pirate King
  • member icon

Reputation: 149
  • View blog
  • Posts: 717
  • Joined: 03-August 06

Re: Which is faster?

Posted 16 March 2009 - 01:07 AM

This is why it's impossible to trust the microtime function.

EDIT: Also, AdamSpeight2008 I managed to do what you were doing but using solely bitwise operations and adds as follows:
$number = (($number ^ (((((($number & 0x80000000) >> 31) & 1) ^ 0xffffffff) << 1) + 2)) + (((((($number & 1) + 1) << 31) >> 30) & 2) & ((($number & 0x80000000) >> 30) & 2)));

This post has been edited by grimpirate: 16 March 2009 - 01:27 AM

Was This Post Helpful? 0
  • +
  • -

#10 AdamSpeight2008   User is offline

  • MrCupOfT
  • member icon

Reputation: 2298
  • View blog
  • Posts: 9,535
  • Joined: 29-May 08

Re: Which is faster?

Posted 16 March 2009 - 09:07 AM

How fast is this one?
&number=  $number^($number>>31))-($number>>31)


Was This Post Helpful? 0
  • +
  • -

#11 Valek   User is offline

  • The Real Skynet
  • member icon

Reputation: 544
  • View blog
  • Posts: 1,713
  • Joined: 08-November 08

Re: Which is faster?

Posted 16 March 2009 - 11:52 AM

Not faster than grimpirate's. His is still at least 0.2 faster than the rest almost every time.
Was This Post Helpful? 0
  • +
  • -

#12 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7507
  • View blog
  • Posts: 15,558
  • Joined: 16-October 07

Re: Which is faster?

Posted 16 March 2009 - 12:34 PM

Sorry, torture testing an abs function seems a little silly. It's hard to imagine a difference a few operations will impact otherwise optimized code. :P

Still, the testing methodologies sounded interesting. Here's my harness, fyi.

<?php
function testFunction($func) {
	$st = microtime(true);
	for($i=-50000; $i<50000; $i++) {
		$n = $func($i);
	}
	return (microtime(true)-$st);
}

$fa = array(
	"abs" => create_function('$n', 'return abs($n);'),
	"func1" => create_function('$n', 'return ($n & 0x80000000) ? (($n ^ 0xffffffff) + 1) : $n;'),
	"func2" => create_function('$n', 'return ($n < 0) ? (($n ^ 0xffffffff) + 1) : $n;'),
	"func3" => create_function('$n', 'return ($n < 0) ? -$n : $n;')
	);

foreach ($fa as $label => $func) {
	$elapsed = testFunction($func);
	echo "$label = $elapsed\n";
}
?>



Of note, while results could vary considerably, func3 was always the fastest. B)
Was This Post Helpful? 0
  • +
  • -

#13 grimpirate   User is offline

  • Pirate King
  • member icon

Reputation: 149
  • View blog
  • Posts: 717
  • Joined: 03-August 06

Re: Which is faster?

Posted 16 March 2009 - 01:05 PM

Adam, much respect. That is a bold way of using the bitwise right shift of PHP to your advantage, as it performs an arithmetic shift instead of logical shift.

EDIT: I think that Adam's code should actually be faster than my own as he's using less bitwise procedures and there's no conditional if. At the very least when dealing with negative numbers. If the number is already positive then yes mine would be faster as it short circuits the need to perform any computations. A combination of the two may be quicker. Something like
if($mask = $number >> 31) $number = ($number ^ $mask) - $mask;


@baavgai: I'm not torture testing the abs function simply for my own benefit. I don't know if you read earlier but I'm working on another project that involves repetitive use of the abs function whereas most of the other operations are bit operations or add/subtract. In one region alone it could add up to using the abs function well over 600 times, so every microsecond counts.

As an aside, I know PHP has some sort of garbage collection mechanism and this is the primary reason I don't trust the results of microtime. The fact is those garbage collection routines could be insantiating randomly anywhere and we have no idea how. Perhaps attempting to do something in an assembly language methodology is inherently flawed in higher level language that doesn't allow for assembly language usage.

This post has been edited by grimpirate: 16 March 2009 - 01:28 PM

Was This Post Helpful? 0
  • +
  • -

#14 baavgai   User is offline

  • Dreaming Coder
  • member icon


Reputation: 7507
  • View blog
  • Posts: 15,558
  • Joined: 16-October 07

Re: Which is faster?

Posted 16 March 2009 - 02:19 PM

View Postgrimpirate, on 16 Mar, 2009 - 02:05 PM, said:

@baavgai: I'm not torture testing the abs function simply for my own benefit.


Understood. It just seemed an unlikely place for a bottleneck.

View Postgrimpirate, on 16 Mar, 2009 - 02:05 PM, said:

As an aside, I know PHP has some sort of garbage collection mechanism and this is the primary reason I don't trust the results of microtime.


Not sure. PHP generally doesn't need to survive a page refresh. Under the covers it seems to be mostly associative arrays. Garbage collection wouldn't be a big factor for normal PHP usage.

As far as computer timers go, old PCs were 18.2 ticks per second. While doubtless their current cousins are faster; a high resolution clock is strangely not a priority in computer hardware. As a result, regardless of you computer speed, your timer can only get so granular. I'd be interested to know the time frame, it anyone knows.

View Postgrimpirate, on 16 Mar, 2009 - 02:05 PM, said:

Perhaps attempting to do something in an assembly language methodology is inherently flawed in higher level language that doesn't allow for assembly language usage.


PHP is interpreted. It's entirely possible that bit functions are handled internally and never even seen by a hardware register. For what you're trying to do, I'm afraid PHP sounds like a poor choice. It's ability to take advantage of libraries is exceptional, though. C? ;)
Was This Post Helpful? 0
  • +
  • -

#15 grimpirate   User is offline

  • Pirate King
  • member icon

Reputation: 149
  • View blog
  • Posts: 717
  • Joined: 03-August 06

Re: Which is faster?

Posted 16 March 2009 - 03:41 PM

I hear ya baavgai. If anything I would do this in just straight assembly, then I could simply look up the number of clock cycles it takes for each instruction to execute and I would empirically know how long it takes. However, the whole purpose of this is to speed up procedures for a library in PHP that can create PNGs. I already know that gd can do this, but it isn't offered on a lot of free servers. So I'm trying to create something that would allow people to create images without gd being available. For instance, people could then create CAPTCHAs where the ability to do so before might not have been readily available. First things first though, gotta speed it up so it doesn't time out. After all, I only have 30 seconds of execution time available.

This post has been edited by grimpirate: 16 March 2009 - 03:44 PM

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2