Patchwork [6,of,6] parsers: use a lookup table to convert hex to binary

login
register
mail settings
Submitter Siddharth Agarwal
Date Sept. 7, 2013, 8:40 p.m.
Message ID <6638dd23999d66a95ce2.1378586440@dev1091.prn1.facebook.com>
Download mbox | patch
Permalink /patch/2410/
State Accepted
Commit d69e06724b96a985f29fd493a5dfe356a75af387
Headers show

Comments

Siddharth Agarwal - Sept. 7, 2013, 8:40 p.m.
# HG changeset patch
# User Siddharth Agarwal <sid0@fb.com>
# Date 1378540764 25200
#      Sat Sep 07 00:59:24 2013 -0700
# Node ID 6638dd23999d66a95ce28816f035a1d051963290
# Parent  8c45bfd4369fc7075fb2a2aca7cea6f492bd7782
parsers: use a lookup table to convert hex to binary

This is a hotspot for parse_manifest. With this patch, for a 20 MB, 200,000
file manifest, parse_manifest goes down from 0.153 seconds to 0.116.
Siddharth Agarwal - Sept. 7, 2013, 9:30 p.m.
On 09/07/2013 01:40 PM, Siddharth Agarwal wrote:
> # HG changeset patch
> # User Siddharth Agarwal <sid0@fb.com>
> # Date 1378540764 25200
> #      Sat Sep 07 00:59:24 2013 -0700
> # Node ID 6638dd23999d66a95ce28816f035a1d051963290
> # Parent  8c45bfd4369fc7075fb2a2aca7cea6f492bd7782
> parsers: use a lookup table to convert hex to binary
>
> This is a hotspot for parse_manifest. With this patch, for a 20 MB, 200,000
> file manifest, parse_manifest goes down from 0.153 seconds to 0.116.

Idan asked me to test out an unrolled switch. I tried a couple of 
variations and the best I got was 0.20 seconds, so it's worse than even 
the current code.

I saw similar results with both gcc 4.1.2 (ancient, I know) and gcc 
4.4.6 on a Linux system with 2x Intel Xeon CPU X5650 @ 2.67GHz.
Augie Fackler - Sept. 9, 2013, 3:15 a.m.
On Sat, Sep 07, 2013 at 01:40:40PM -0700, Siddharth Agarwal wrote:
> # HG changeset patch
> # User Siddharth Agarwal <sid0@fb.com>
> # Date 1378540764 25200
> #      Sat Sep 07 00:59:24 2013 -0700
> # Node ID 6638dd23999d66a95ce28816f035a1d051963290
> # Parent  8c45bfd4369fc7075fb2a2aca7cea6f492bd7782
> parsers: use a lookup table to convert hex to binary

Series looks reasonable, but it's important enough I want someone else
to glance at it.

>
> This is a hotspot for parse_manifest. With this patch, for a 20 MB, 200,000
> file manifest, parse_manifest goes down from 0.153 seconds to 0.116.
>
> diff --git a/mercurial/parsers.c b/mercurial/parsers.c
> --- a/mercurial/parsers.c
> +++ b/mercurial/parsers.c
> @@ -14,16 +14,32 @@
>
>  #include "util.h"
>
> +static int8_t hextable[256] = {
> + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> +      0,  1,  2,  3,  4,  5,  6,  7,  8,  9, -1, -1, -1, -1, -1, -1, /* 0-9 */
> + -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* A-F */
> + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> + -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* a-f */
> + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
> + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
> +};
> +
>  static inline int hexdigit(const char *p, Py_ssize_t off)
>  {
> - char c = p[off];
> + int8_t val = hextable[(unsigned char)p[off]];
>
> - if (c >= '0' && c <= '9')
> - return c - '0';
> - if (c >= 'a' && c <= 'f')
> - return c - 'a' + 10;
> - if (c >= 'A' && c <= 'F')
> - return c - 'A' + 10;
> + if (val >= 0) {
> + return val;
> + }
>
>       PyErr_SetString(PyExc_ValueError, "input contains non-hex character");
>       return 0;
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@selenic.com
> http://selenic.com/mailman/listinfo/mercurial-devel
tonfa - Sept. 10, 2013, 7:42 p.m.
On Mon, Sep 9, 2013 at 5:15 AM, Augie Fackler <raf@durin42.com> wrote:

> On Sat, Sep 07, 2013 at 01:40:40PM -0700, Siddharth Agarwal wrote:
> > # HG changeset patch
> > # User Siddharth Agarwal <sid0@fb.com>
> > # Date 1378540764 25200
> > #      Sat Sep 07 00:59:24 2013 -0700
> > # Node ID 6638dd23999d66a95ce28816f035a1d051963290
> > # Parent  8c45bfd4369fc7075fb2a2aca7cea6f492bd7782
> > parsers: use a lookup table to convert hex to binary
>
> Series looks reasonable, but it's important enough I want someone else
> to glance at it.
>

Serie looks good to me.
Though I'm not a huge fan of the temporary assumption on cache preloading
in #3.
Siddharth Agarwal - Sept. 10, 2013, 7:51 p.m.
On 09/10/2013 12:42 PM, Benoit Boissinot wrote:
> Serie looks good to me.
> Though I'm not a huge fan of the temporary assumption on cache 
> preloading in #3.

I tried combining patches 3 and 4 into one, but I found that there was 
just too much going on. As it is, patch 4 is confusing enough.
tonfa - Sept. 10, 2013, 7:53 p.m.
On Tue, Sep 10, 2013 at 9:51 PM, Siddharth Agarwal <sid0@fb.com> wrote:

> On 09/10/2013 12:42 PM, Benoit Boissinot wrote:
>
>> Serie looks good to me.
>> Though I'm not a huge fan of the temporary assumption on cache preloading
>> in #3.
>>
>
> I tried combining patches 3 and 4 into one, but I found that there was
> just too much going on. As it is, patch 4 is confusing enough.
>

That was my conclusion as well, couldn't see how to improve it.

Patch

diff --git a/mercurial/parsers.c b/mercurial/parsers.c
--- a/mercurial/parsers.c
+++ b/mercurial/parsers.c
@@ -14,16 +14,32 @@ 
 
 #include "util.h"
 
+static int8_t hextable[256] = {
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, -1, -1, -1, -1, -1, -1, /* 0-9 */
+	-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* A-F */
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* a-f */
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
+	-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
+};
+
 static inline int hexdigit(const char *p, Py_ssize_t off)
 {
-	char c = p[off];
+	int8_t val = hextable[(unsigned char)p[off]];
 
-	if (c >= '0' && c <= '9')
-		return c - '0';
-	if (c >= 'a' && c <= 'f')
-		return c - 'a' + 10;
-	if (c >= 'A' && c <= 'F')
-		return c - 'A' + 10;
+	if (val >= 0) {
+		return val;
+	}
 
 	PyErr_SetString(PyExc_ValueError, "input contains non-hex character");
 	return 0;