Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:46416
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.210.192 as permitted sender)
DomainKey-Status: bad
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=gamma;
        h=date:from:to:cc:subject:message-id:mime-version:content-type
         :content-disposition:user-agent;
        b=x/SYKt+6StKqPBvnzFsD3T5SdNdxx1/eOFJh7mUuQxbOcOQryRzcsIP2RSyy52VD3W
         MXjvbRizJuDqyKCLsoIy4ud0DClm33Pdbxg2ND3wFgrhQTmL2p8zicNPMTfKr+knYc3l
         yPoVpT48VnhnTvDYGCv6oPbiubvvl38AekyVY=
Date: Mon, 14 Dec 2009 18:22:03 -0800
To: internals@lists.php.net
Cc: Richard.Smith@sun.com
Message-ID: <20091215022203.GA23217@lbasantk3.red.iplanet.com>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="zYM0uCDKw75PZbzx"
Content-Disposition: inline
User-Agent: Mutt/1.5.19 (2009-01-05)
Subject: safe_address optimization for 64 bit size_t for platforms other
	than x86_64.
From: basant.kukreja@gmail.com (Basant Kukreja)

--zYM0uCDKw75PZbzx
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

Hi,
   On non x86_64 platforms current implementation of safe_address uses doubles
for 64 bit php which is very expensive on some architectures e.g sparc.

safe_address function calculates nmemb * size + offset and it want to make
sure that it output doesn't overflow.  My colleague Richard Smith suggested a
platform independent mechanism to avoid double logic for most common cases
(>99%).  In this proposed optimization we can check if the inputs are
sufficiently large enough so that overflow is possible. If overflow is
possible, regular double logic will follow.

This new implementation performs very closely to the assembly version on Linux
x86_64 on micro-benchmark (attached at bottom).

On a ecommerce benchmark on Solaris sparc, new implementation reduced the time
spent in _ecalloc to 50%.

Patch against php 5.3 trunk is attached. Please provide your comments.

Regards,
Basant.

Microbenchmark testing on Linux x86_64 :
=======================================
Based on the above suggested implementation, I benchmarked 3 implementation of
safe_address on Linux x86_64 (fedora 11) using a micro benchmark. Here are the
results :

--------------------------------------
For a regular nmemb * size + offset when no overflow possible :
nmemb = 23456 size = 67890 offset = 12345
assembly version of safe_address time diff = 26 ticks 
doubles imlementation of safe_address time diff = 72 ticks 
proposed safe_address time diff = 30 ticks 
--------------------------------------

For bigger integer multiplication :

nmemb = 2589934591 size = 4294967295 offset = 5

assembly version of safe_address time diff = 26 ticks 
doubles imlementation of safe_address time diff = 75 ticks 
proposed safe_address time diff = 76 ticks 

--------------------------------------
Here is the micro benchmark link :
http://bitbucket.org/basantk/php53perfpatches/src/tip/safe_address_bench.c


--zYM0uCDKw75PZbzx
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="safe_address_64bitopt_php53.txt"

Index: Zend/zend_alloc.c
===================================================================
--- Zend/zend_alloc.c	(revision 291181)
+++ Zend/zend_alloc.c	(working copy)
@@ -2382,9 +2382,26 @@
 static inline size_t safe_address(size_t nmemb, size_t size, size_t offset)
 {
 	size_t res = nmemb * size + offset;
-	double _d  = (double)nmemb * (double)size + (double)offset;
-	double _delta = (double)res - _d;
+	double _d, _delta;
 
+#if SIZEOF_SIZE_T == 8
+	const int nmemb_bits = 30;
+	const int size_bits = 33;
+
+	/* Check that arguments are within defined ranges such that overflow can't
+	 * occur. The basic principle is that if nmemb*size < 2^63 and offset <
+	 * 2^63 then nmemb*size+offset < 2^64. For efficency, powers of 2 have been
+	 * used for each range. nmemb_bits + size_bits should not exceed 63. The
+	 * test below checks that each argument doesn't exceed its allotted range.
+	 */
+	if (EXPECTED(!(nmemb >> nmemb_bits | size >> size_bits 
+	                         | offset >> (nmemb_bits + size_bits))))
+		return res;
+#endif
+
+	_d  = (double)nmemb * (double)size + (double)offset;
+	_delta = (double)res - _d;
+
 	if (UNEXPECTED((_d + _delta ) != _d)) {
 		zend_error_noreturn(E_ERROR, "Possible integer overflow in memory allocation (%zu * %zu + %zu)", nmemb, size, offset);
 		return 0;

--zYM0uCDKw75PZbzx--