[darcs-users] darcs patch: fpstring.c: switch a memchr for memrchr

[Gwern Branwen]

On 2008.04.25 13:26:11 -0700, Don Stewart <dons at galois.com> scribbled 0.3K characters:
> gwern0:
> > Fri Apr 25 16:01:53 EDT 2008  gwern0 at gmail.com
> >   * fpstring.c: switch a memchr for memrchr
> >   See <http://bugs.darcs.net/issue814>; memrchr speeds up is_funky quite a bit and thus helps whatsnew -s. It doesn't seem to break (any more) tests.
>
> memrchr isn't available on BSDs.
>
> -- Don

Hm. That's too bad. If the memchr stuff isn't portable or common, perhaps we could adopt Jaak's solution. He suggested simply replacing the double memchr loop with a regular loop ('produces really nice asm', he said):

hunk ./src/fpstring.c 57
-    /* We'll assume memchr(3) is faster than a simplistic loop that
-     * checks each char against the two sought values, and NUL is more
-     * likely than DOS's Ctrl-Z.
-     * We go forward through the string using memchr, then we reverse and
-     * iterate backwards through the string; using memrchr instead of memchr
-     * gives us better cache locality, which makes a difference on big files. */
-    return !!(memchr(s, 0, len) || memrchr(s, 26, len));
+  if (len != 0) {
+    do {
+      // We assume \0 (or NULL) is more likely than ^Z
+      if (*s == 0 || *s == 26)
+        return !!s;
+      ++ s;
+    }
+    while (-- len != 0);
+  }
+
+  return !!NULL;

Time-wise this seems a little worse:

gwern at localhost:2270~/foo>time darcs whatsnew -s [ 6:43PM]
A ./bigtempfile
darcs whatsnew -s  1.82s user 3.57s system 10% cpu 53.521 total
gwern at localhost:2272~/foo>time darcs whatsnew -s [ 6:45PM]
A ./bigtempfile
darcs whatsnew -s  1.67s user 3.13s system 7% cpu 1:08.30 total
gwern at localhost:2278~/foo>time darcs whatsnew -s [ 6:48PM]
A ./bigtempfile
darcs whatsnew -s  1.57s user 3.51s system 9% cpu 55.392 total
gwern at localhost:2283~/foo>time darcs whatsnew -s [ 6:50PM]
A ./bigtempfile
darcs whatsnew -s  1.64s user 3.27s system 7% cpu 1:02.59 total

Thoughts?

--
gwern
Lacrosse SAP SO13 SHF STARLAN Mafia Kh-11 MJ-12 Dodger House
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://lists.osuosl.org/pipermail/darcs-users/attachments/20080425/3f56e015/attachment-0001.pgp