Page 1 of 1
Bottleneck resolution challenge! :)
Posted: Mon Feb 25, 2008 11:09 pm
by Chris Corbyn
Code: Select all
<?php
$str = '';
for ($i = 0; $i < 10000; $i++) {
$str .= 'A';
}
$start = microtime(true);
for ($i = 0; $i < 1000; $i++) {
$qp = '';
$bytes = unpack('C*', $str);
foreach ($bytes as $val) {
$qp .= sprintf('=%02X', $val);
}
}
echo '1000 of a 10KB string encodings took ' . (round(microtime(true) - $start, 4)) . ' seconds' . "\n";
Who can make this demonstration of a slow script faster for me?

It's a very blind example of what QP encoding does (turns octets into =N where N is the byte value in hexadecimal, uppercase). The only catch is that in the real world most ascii bytes must be left unencoded and the places where line wraps occur are really strict. This is why I need to deal with one byte at a time.
The thing I'm looking for optimization on is:
a) Splitting the string into an array of bytes (or any other way you can see to get all the byte values out)
b) Turning those byte values into the =N form.
IMPORTANT: The algorithm MUST deal with individual bytes at a time
As an example of just how slow this is, encoding that 10KB string of A's 1000 times on my Macbook takes
16 seconds. There's plenty of room for improvement if someone can pick better functions than unpack() and sprintf(). Maybe even just a different unpack() format will help ("C" is character data which is what I'm dealing with).
Re: Bottleneck resolution challenge! :)
Posted: Tue Feb 26, 2008 2:11 am
by Mordred
God, I do this all day at my dayjob and now here too? Is there no rest?!

Letssee..
OMG, you put such code in a bottleneck? The only thing worse would be to throw the bottle and wait for the ocean to bring it to the client
Seriously, the most trivial implementation is the best (KISS, remember?)
Your code: 1000 of a 10KB string encodings took
20.6245 seconds
My code: 1000 of a 10KB string encodings took
5.0864 seconds
Code: Select all
<?php
$str = '';
for ($i = 0; $i < 10000; $i++) {
$str .= 'A';
}
//make this a constant
$map = Array();
for ($i = 0; $i < 256; ++$i) {
$map[chr($i)] = sprintf('=%02X', $i);
}
$start = microtime(true);
$len = strlen($str);
for ($i = 0; $i < 1000; ++$i) {
$qp = '';
for ($j=0; $j < $len; ++$j)
$qp .= $map[$str[$j]];
}
echo '1000 of a 10KB string encodings took ' . (round(microtime(true) - $start, 4)) . ' seconds' . "\n";
echo $qp;
?>
And do mind how you write them loops, preincrements are better (for languages with sucky compilers like PHP). Compare ++$j above with $j++:
++$j: 1000 of a 10KB string encodings took
5.0864 seconds
$j++: 1000 of a 10KB string encodings took
5.6792 seconds
Re: Bottleneck resolution challenge! :)
Posted: Tue Feb 26, 2008 7:35 am
by Chris Corbyn
Do you know, I never thought of pre-computing all 256 byte values! You're a genius!
Even if I was encoding 1KB of data, the cost of pre-computing those 256 possible bytes values would be neglible (and in fact in the real algorithm it will be 128 + a few extra bytes).
EDIT | Do you mind if I ask what your day job is?
Re: Bottleneck resolution challenge! :)
Posted: Tue Feb 26, 2008 8:13 am
by Chris Corbyn
I gained 35% speed increase from simply pre-encoding 256 bytes of QP octets as a private static (damn PHP for not allow "final static"). The reason it's not 400% like your increase is down to another issue I'm aware of (I'm unpacking strings in several separate encapsulated classes; using byte arrays rather than strings may help).
Re: Bottleneck resolution challenge! :)
Posted: Tue Feb 26, 2008 8:19 am
by Mordred
Chris Corbyn wrote:Do you know, I never thought of pre-computing all 256 byte values! You're a genius!
Even if I was encoding 1KB of data, the cost of pre-computing those 256 possible bytes values would be neglible (and in fact in the real algorithm it will be 128 + a few extra bytes).
Nononono. Don't precompute them, read my comment - make it a constant!
$map = Array('\0' => '=00', ...);
(yeah, okay, "precompute" it with a script to generate the PHP code of course)
Chris Corbyn wrote:EDIT | Do you mind if I ask what your day job is?
You surely know some people that code PHP sites or intraweb apps or whatever during the day, and in their free time they code computer games for fun? I'm the exact opposite

PHP/WebAppSec is my 'hobby', I'm actually a game programmer.
I'm unpacking strings in several separate encapsulated classes
Hmm, you can freely access a string as an array, why do you insist on the unpacking? If you're sure you must have it, see if using str_split() instead would be faster.
Edit: I forgot: mind your loops. for loops with ++$i will be faster than foreach. foreach also
copies the array (since you're not using references) which in a tight loop will hurt as well.
Re: Bottleneck resolution challenge! :)
Posted: Tue Feb 26, 2008 4:12 pm
by Chris Corbyn
Mordred wrote:I'm unpacking strings in several separate encapsulated classes
Hmm, you can freely access a string as an array, why do you insist on the unpacking? If you're sure you must have it, see if using str_split() instead would be faster.
Edit: I forgot: mind your loops. for loops with ++$i will be faster than foreach. foreach also
copies the array (since you're not using references) which in a tight loop will hurt as well.
I have the array pre-generated yes (i.e. I wrote a script which displayed the array then copied and pasted into my class)
The packing and unpacking is a bit wasteful; however the unpacking is probably necessary. I need to access individual *bytes* from separate *characters* within a string. In other words I need to know where the character boundaries are and what bytes those characters contain. Really I should unpack and then repeatedly work with that byte array rather than packing it back into a character and letting other bits of the code turn it back into a byte array.
The reason I've gone down this route is to avoid a mass rewrite when PHP6 gets closer since:
$string{3}
Is in theory "the character at offset 3" not "the byte at offset 3". At least the manual uses the wording "character" as opposed to byte. I could stop worrying about future versions of PHP I guess, but I'd rather not have to maintain two versions again
