Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:96716
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain gmail.com designates 209.85.213.174 as permitted sender)
MIME-Version: 1.0
Sender: morrison.levi@gmail.com
In-Reply-To: <20161103112101.C28155FAB4@mx.zeyos.com>
References: <20161103112101.C28155FAB4@mx.zeyos.com>
Date: Thu, 3 Nov 2016 06:23:23 -0600
Message-ID: <CAFMT4NokR1sLfDMOOuE-e=6FSHs6XX54x3hj2_CN4K7G0TE68g@mail.gmail.com>
To: Benjamin Coutu <ben.coutu@zeyos.com>
Cc: PHP Internals <internals@lists.php.net>, Dmitry Stogov <dmitry@zend.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Subject: Re: [PHP-DEV] Algorithmic efficiency of zend_memrchr
From: levim@php.net (Levi Morrison)

On Thu, Nov 3, 2016 at 5:21 AM, Benjamin Coutu <ben.coutu@zeyos.com> wrote:
> Hello everyone,
>
> I think there are a few improvements that we could make to some fundament=
al algorithms.
> I'd like to point out one particular for now, to see if there is any inte=
rest in these kind of low level code optimizations from the community.
>
> Please consider the following code snippet extracted from
>
> https://github.com/php/php-src/blob/49412756df244d94a217853395d15e96cb60e=
18f/Zend/zend_operators.h#L193
>
> static zend_always_inline const void *zend_memrchr(const void *s, int c, =
size_t n)
> {
>   const unsigned char *e;
>   if (n <=3D 0) {
>     return NULL;
>   }
>
>   for (e =3D (const unsigned char *)s + n - 1; e >=3D (const unsigned cha=
r *)s; e--) {
>     if (*e =3D=3D (const unsigned char)c) {
>       return (const void *)e;
>     }
>   }
>   return NULL;
> }
>
> The issue with this is that on each loop we have to do two comparison tes=
ts, one against the length boundary and one to check for the actual occurre=
nce of the search character.
>
> We can avoid checking the length boundary if we use a sentinel by setting=
 the last possible element to the character we are searching for, whereby w=
e guarantee that we will find it and no longer need the test inside the loo=
p. After the search we reset that character and then recheck the last itera=
tion step to see if we have aborted the loop because of reaching the end (f=
alse positive) or because of an actual positive.
>
> A patch could look like this:
>
> static zend_always_inline const void *zend_memrchr(const void *s, int c, =
size_t n)
> {
>   const unsigned char *b;
>   const unsigned char *e;
>   const unsigned char t;
>
>   if (n > 0) {
>     /* Initialize boundary pointers */
>     b =3D (const unsigned char *)s;
>     e =3D b + n - 1;
>
>     /* Set sentinel */
>     t =3D *b;
>     *b =3D (const unsigned char)c;
>
>     /* Search */
>     while (*e !=3D (const unsigned char)c) {
>       --e;
>     }
>
>     /* Restore sentinel */
>     *b =3D t;
>
>     /* Recheck */
>     if (e !=3D b || t =3D=3D (const unsigned char)c) {
>       return (const void *)e;
>     }
>   }
>
>   return NULL;
> }
>
> For the above example we could go one step further and test an entire lon=
gword at a time with alignment on longword boundaries, just like some moder=
n C library implementations do. Which begs the question: Is there a reason =
we are not using standard memrchr here?
>
> This kind of approach might be applicable to other string handling functi=
ons as well. Should I look into this further?
>
> Cheers,
>
> Benjamin Coutu
>
> --
>
> Bejamin Coutu
> ben.coutu@zeyos.com
>
> ZeyOS, Inc.
> http://www.zeyos.com
>
>
> --
> PHP Internals - PHP Runtime Development Mailing List
> To unsubscribe, visit: http://www.php.net/unsub.php

An obvious issue with this is that not all strings are writable. The
signature of the function also specifies it is a pointer to a const so
you shouldn't be able to do this anyway.