You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@subversion.apache.org by st...@apache.org on 2011/01/01 17:18:56 UTC
svn commit: r1054250 - /subversion/trunk/subversion/libsvn_subr/eol.c
Author: stefan2
Date: Sat Jan 1 16:18:55 2011
New Revision: 1054250
URL: http://svn.apache.org/viewvc?rev=1054250&view=rev
Log:
About 3x speed up of svn_eol__find_eol_start() on 64 bit machines
(20 .. 40% on 32 bits). This function is a significant contributor
to our diff algorithm.
* subversion/libsvn_subr/eol.c
(svn_eol__find_eol_start): use some masking magic to process
the data in larger chunks
Modified:
subversion/trunk/subversion/libsvn_subr/eol.c
Modified: subversion/trunk/subversion/libsvn_subr/eol.c
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_subr/eol.c?rev=1054250&r1=1054249&r2=1054250&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_subr/eol.c (original)
+++ subversion/trunk/subversion/libsvn_subr/eol.c Sat Jan 1 16:18:55 2011
@@ -29,14 +29,68 @@
#include "svn_io.h"
#include "private/svn_eol_private.h"
+/* Machine-word-sized masks used in svn_eol__find_eol_start.
+ */
+#if APR_SIZEOF_VOIDP == 8
+# define LOWER_7BITS_SET 0x7f7f7f7f7f7f7f7f
+# define BIT_7_SET 0x8080808080808080
+# define R_MASK 0x0a0a0a0a0a0a0a0a
+# define N_MASK 0x0d0d0d0d0d0d0d0d
+#else
+# define LOWER_7BITS_SET 0x7f7f7f7f
+# define BIT_7_SET 0x80808080
+# define R_MASK 0x0a0a0a0a
+# define N_MASK 0x0d0d0d0d
+#endif
+
char *
svn_eol__find_eol_start(char *buf, apr_size_t len)
{
+#if !SVN_UNALIGNED_ACCESS_IS_OK
+
+ /* On some systems, we need to make sure that buf is properly aligned
+ * for chunky data access. This overhead is still justified because
+ * only lines tend to be tens of chars long.
+ */
+ for (; (len > 0) && ((apr_uintptr_t)buf) & (sizeof(apr_uintptr_t)-1)
+ ; ++buf, --len)
+ {
+ if (*buf == '\n' || *buf == '\r')
+ return buf;
+ }
+
+#endif
+
+ /* Scan the input one machine word at a time. */
+ for (; len > sizeof(apr_uintptr_t)
+ ; buf += sizeof(apr_uintptr_t), len -= sizeof(apr_uintptr_t))
+ {
+ /* This is a variant of the well-known strlen test: */
+ apr_uintptr_t chunk = *(const apr_uintptr_t *)buf;
+
+ /* A byte in R_TEST is \0, iff it was \r in *BUF.
+ * Similarly, N_TEST is an indicator for \n. */
+ apr_uintptr_t r_test = chunk ^ R_MASK;
+ apr_uintptr_t n_test = chunk ^ N_MASK;
+
+ /* A byte in R_TEST can by < 0x80, iff it has been \0 before
+ * (i.e. \r in *BUF). Dito for N_TEST. */
+ r_test |= (r_test & LOWER_7BITS_SET) + LOWER_7BITS_SET;
+ n_test |= (n_test & LOWER_7BITS_SET) + LOWER_7BITS_SET;
+
+ /* Check whether at least one of the words contains a byte <0x80
+ * (if one is detected, there was a \r or \n in CHUNK). */
+ if ((r_test & n_test & BIT_7_SET) != BIT_7_SET)
+ break;
+ }
+
+ /* The remaining odd bytes will be examined the naive way: */
for (; len > 0; ++buf, --len)
{
if (*buf == '\n' || *buf == '\r')
return buf;
}
+
return NULL;
}
Re: svn commit: r1054250 - /subversion/trunk/subversion/libsvn_subr/eol.c
Posted by Stefan Fuhrmann <eq...@web.de>.
On 01.01.2011 18:14, Hyrum K Wright wrote:
> On Sat, Jan 1, 2011 at 11:18 AM,<st...@apache.org> wrote:
>> Author: stefan2
>> Date: Sat Jan 1 16:18:55 2011
>> New Revision: 1054250
>>
>> URL: http://svn.apache.org/viewvc?rev=1054250&view=rev
>> Log:
>> About 3x speed up of svn_eol__find_eol_start() on 64 bit machines
>> (20 .. 40% on 32 bits). This function is a significant contributor
>> to our diff algorithm.
>>
>> * subversion/libsvn_subr/eol.c
>> (svn_eol__find_eol_start): use some masking magic to process
>> the data in larger chunks
>>
>> Modified:
>> subversion/trunk/subversion/libsvn_subr/eol.c
>>
>> Modified: subversion/trunk/subversion/libsvn_subr/eol.c
>> URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_subr/eol.c?rev=1054250&r1=1054249&r2=1054250&view=diff
>> ==============================================================================
>> --- subversion/trunk/subversion/libsvn_subr/eol.c (original)
>> +++ subversion/trunk/subversion/libsvn_subr/eol.c Sat Jan 1 16:18:55 2011
>> @@ -29,14 +29,68 @@
>> #include "svn_io.h"
>> #include "private/svn_eol_private.h"
>>
>> +/* Machine-word-sized masks used in svn_eol__find_eol_start.
>> + */
>> +#if APR_SIZEOF_VOIDP == 8
>> +# define LOWER_7BITS_SET 0x7f7f7f7f7f7f7f7f
>> +# define BIT_7_SET 0x8080808080808080
>> +# define R_MASK 0x0a0a0a0a0a0a0a0a
>> +# define N_MASK 0x0d0d0d0d0d0d0d0d
>> +#else
>> +# define LOWER_7BITS_SET 0x7f7f7f7f
>> +# define BIT_7_SET 0x80808080
>> +# define R_MASK 0x0a0a0a0a
>> +# define N_MASK 0x0d0d0d0d
>> +#endif
>> +
>> char *
>> svn_eol__find_eol_start(char *buf, apr_size_t len)
>> {
>> +#if !SVN_UNALIGNED_ACCESS_IS_OK
>> +
>> + /* On some systems, we need to make sure that buf is properly aligned
>> + * for chunky data access. This overhead is still justified because
>> + * only lines tend to be tens of chars long.
>> + */
>> + for (; (len> 0)&& ((apr_uintptr_t)buf)& (sizeof(apr_uintptr_t)-1)
>> + ; ++buf, --len)
>> + {
>> + if (*buf == '\n' || *buf == '\r')
>> + return buf;
>> + }
>> +
>> +#endif
>> +
>> + /* Scan the input one machine word at a time. */
>> + for (; len> sizeof(apr_uintptr_t)
>> + ; buf += sizeof(apr_uintptr_t), len -= sizeof(apr_uintptr_t))
>> + {
>> + /* This is a variant of the well-known strlen test: */
>> + apr_uintptr_t chunk = *(const apr_uintptr_t *)buf;
> This type isn't in APR 0.9.x, which is causing build failures on at
> least two of the build slaves.
>
Oops - sorry! This makes it absolute clear
what the @since clauses in our headers
are worth.
Should be fixed by r1054264.
-- Stefan^2.
>> +
>> + /* A byte in R_TEST is \0, iff it was \r in *BUF.
>> + * Similarly, N_TEST is an indicator for \n. */
>> + apr_uintptr_t r_test = chunk ^ R_MASK;
>> + apr_uintptr_t n_test = chunk ^ N_MASK;
>> +
>> + /* A byte in R_TEST can by< 0x80, iff it has been \0 before
>> + * (i.e. \r in *BUF). Dito for N_TEST. */
>> + r_test |= (r_test& LOWER_7BITS_SET) + LOWER_7BITS_SET;
>> + n_test |= (n_test& LOWER_7BITS_SET) + LOWER_7BITS_SET;
>> +
>> + /* Check whether at least one of the words contains a byte<0x80
>> + * (if one is detected, there was a \r or \n in CHUNK). */
>> + if ((r_test& n_test& BIT_7_SET) != BIT_7_SET)
>> + break;
>> + }
>> +
>> + /* The remaining odd bytes will be examined the naive way: */
>> for (; len> 0; ++buf, --len)
>> {
>> if (*buf == '\n' || *buf == '\r')
>> return buf;
>> }
>> +
>> return NULL;
>> }
>>
>>
>>
>>
Re: svn commit: r1054250 - /subversion/trunk/subversion/libsvn_subr/eol.c
Posted by Hyrum K Wright <hy...@hyrumwright.org>.
On Sat, Jan 1, 2011 at 11:18 AM, <st...@apache.org> wrote:
> Author: stefan2
> Date: Sat Jan 1 16:18:55 2011
> New Revision: 1054250
>
> URL: http://svn.apache.org/viewvc?rev=1054250&view=rev
> Log:
> About 3x speed up of svn_eol__find_eol_start() on 64 bit machines
> (20 .. 40% on 32 bits). This function is a significant contributor
> to our diff algorithm.
>
> * subversion/libsvn_subr/eol.c
> (svn_eol__find_eol_start): use some masking magic to process
> the data in larger chunks
>
> Modified:
> subversion/trunk/subversion/libsvn_subr/eol.c
>
> Modified: subversion/trunk/subversion/libsvn_subr/eol.c
> URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_subr/eol.c?rev=1054250&r1=1054249&r2=1054250&view=diff
> ==============================================================================
> --- subversion/trunk/subversion/libsvn_subr/eol.c (original)
> +++ subversion/trunk/subversion/libsvn_subr/eol.c Sat Jan 1 16:18:55 2011
> @@ -29,14 +29,68 @@
> #include "svn_io.h"
> #include "private/svn_eol_private.h"
>
> +/* Machine-word-sized masks used in svn_eol__find_eol_start.
> + */
> +#if APR_SIZEOF_VOIDP == 8
> +# define LOWER_7BITS_SET 0x7f7f7f7f7f7f7f7f
> +# define BIT_7_SET 0x8080808080808080
> +# define R_MASK 0x0a0a0a0a0a0a0a0a
> +# define N_MASK 0x0d0d0d0d0d0d0d0d
> +#else
> +# define LOWER_7BITS_SET 0x7f7f7f7f
> +# define BIT_7_SET 0x80808080
> +# define R_MASK 0x0a0a0a0a
> +# define N_MASK 0x0d0d0d0d
> +#endif
> +
> char *
> svn_eol__find_eol_start(char *buf, apr_size_t len)
> {
> +#if !SVN_UNALIGNED_ACCESS_IS_OK
> +
> + /* On some systems, we need to make sure that buf is properly aligned
> + * for chunky data access. This overhead is still justified because
> + * only lines tend to be tens of chars long.
> + */
> + for (; (len > 0) && ((apr_uintptr_t)buf) & (sizeof(apr_uintptr_t)-1)
> + ; ++buf, --len)
> + {
> + if (*buf == '\n' || *buf == '\r')
> + return buf;
> + }
> +
> +#endif
> +
> + /* Scan the input one machine word at a time. */
> + for (; len > sizeof(apr_uintptr_t)
> + ; buf += sizeof(apr_uintptr_t), len -= sizeof(apr_uintptr_t))
> + {
> + /* This is a variant of the well-known strlen test: */
> + apr_uintptr_t chunk = *(const apr_uintptr_t *)buf;
This type isn't in APR 0.9.x, which is causing build failures on at
least two of the build slaves.
> +
> + /* A byte in R_TEST is \0, iff it was \r in *BUF.
> + * Similarly, N_TEST is an indicator for \n. */
> + apr_uintptr_t r_test = chunk ^ R_MASK;
> + apr_uintptr_t n_test = chunk ^ N_MASK;
> +
> + /* A byte in R_TEST can by < 0x80, iff it has been \0 before
> + * (i.e. \r in *BUF). Dito for N_TEST. */
> + r_test |= (r_test & LOWER_7BITS_SET) + LOWER_7BITS_SET;
> + n_test |= (n_test & LOWER_7BITS_SET) + LOWER_7BITS_SET;
> +
> + /* Check whether at least one of the words contains a byte <0x80
> + * (if one is detected, there was a \r or \n in CHUNK). */
> + if ((r_test & n_test & BIT_7_SET) != BIT_7_SET)
> + break;
> + }
> +
> + /* The remaining odd bytes will be examined the naive way: */
> for (; len > 0; ++buf, --len)
> {
> if (*buf == '\n' || *buf == '\r')
> return buf;
> }
> +
> return NULL;
> }
>
>
>
>
Re: svn commit: r1054250 - /subversion/trunk/subversion/libsvn_subr/eol.c
Posted by Hyrum K Wright <hy...@hyrumwright.org>.
On Sat, Jan 1, 2011 at 11:18 AM, <st...@apache.org> wrote:
> Author: stefan2
> Date: Sat Jan 1 16:18:55 2011
> New Revision: 1054250
>
> URL: http://svn.apache.org/viewvc?rev=1054250&view=rev
> Log:
> About 3x speed up of svn_eol__find_eol_start() on 64 bit machines
> (20 .. 40% on 32 bits). This function is a significant contributor
> to our diff algorithm.
>
> * subversion/libsvn_subr/eol.c
> (svn_eol__find_eol_start): use some masking magic to process
> the data in larger chunks
>
> Modified:
> subversion/trunk/subversion/libsvn_subr/eol.c
>
> Modified: subversion/trunk/subversion/libsvn_subr/eol.c
> URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_subr/eol.c?rev=1054250&r1=1054249&r2=1054250&view=diff
> ==============================================================================
> --- subversion/trunk/subversion/libsvn_subr/eol.c (original)
> +++ subversion/trunk/subversion/libsvn_subr/eol.c Sat Jan 1 16:18:55 2011
> @@ -29,14 +29,68 @@
> #include "svn_io.h"
> #include "private/svn_eol_private.h"
>
> +/* Machine-word-sized masks used in svn_eol__find_eol_start.
> + */
> +#if APR_SIZEOF_VOIDP == 8
> +# define LOWER_7BITS_SET 0x7f7f7f7f7f7f7f7f
> +# define BIT_7_SET 0x8080808080808080
> +# define R_MASK 0x0a0a0a0a0a0a0a0a
> +# define N_MASK 0x0d0d0d0d0d0d0d0d
> +#else
> +# define LOWER_7BITS_SET 0x7f7f7f7f
> +# define BIT_7_SET 0x80808080
> +# define R_MASK 0x0a0a0a0a
> +# define N_MASK 0x0d0d0d0d
> +#endif
> +
> char *
> svn_eol__find_eol_start(char *buf, apr_size_t len)
> {
> +#if !SVN_UNALIGNED_ACCESS_IS_OK
> +
> + /* On some systems, we need to make sure that buf is properly aligned
> + * for chunky data access. This overhead is still justified because
> + * only lines tend to be tens of chars long.
> + */
> + for (; (len > 0) && ((apr_uintptr_t)buf) & (sizeof(apr_uintptr_t)-1)
> + ; ++buf, --len)
> + {
> + if (*buf == '\n' || *buf == '\r')
> + return buf;
> + }
> +
> +#endif
> +
> + /* Scan the input one machine word at a time. */
> + for (; len > sizeof(apr_uintptr_t)
> + ; buf += sizeof(apr_uintptr_t), len -= sizeof(apr_uintptr_t))
> + {
> + /* This is a variant of the well-known strlen test: */
> + apr_uintptr_t chunk = *(const apr_uintptr_t *)buf;
This type isn't in APR 0.9.x, which is causing build failures on at
least two of the build slaves.
> +
> + /* A byte in R_TEST is \0, iff it was \r in *BUF.
> + * Similarly, N_TEST is an indicator for \n. */
> + apr_uintptr_t r_test = chunk ^ R_MASK;
> + apr_uintptr_t n_test = chunk ^ N_MASK;
> +
> + /* A byte in R_TEST can by < 0x80, iff it has been \0 before
> + * (i.e. \r in *BUF). Dito for N_TEST. */
> + r_test |= (r_test & LOWER_7BITS_SET) + LOWER_7BITS_SET;
> + n_test |= (n_test & LOWER_7BITS_SET) + LOWER_7BITS_SET;
> +
> + /* Check whether at least one of the words contains a byte <0x80
> + * (if one is detected, there was a \r or \n in CHUNK). */
> + if ((r_test & n_test & BIT_7_SET) != BIT_7_SET)
> + break;
> + }
> +
> + /* The remaining odd bytes will be examined the naive way: */
> for (; len > 0; ++buf, --len)
> {
> if (*buf == '\n' || *buf == '\r')
> return buf;
> }
> +
> return NULL;
> }
>
>
>
>