1018893 - Latin1 strings: support indexOf and friends

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jan de Mooij [:jandem]]

indexOf/lastIndexOf/contains/startsWith/endsWith are all pretty similar and straight-forward to convert.

Comment 1

[Jan de Mooij [:jandem]]

Attachment: Part 1 - lastIndexOf

Moves the algorithm itself into a new templatized function. I also added some asserts and cleaned up the code a bit.

Note that using separate TextChar and PatChar "types" instead of jschar for both actually makes the algorithm a bit more readable.

Comment 2

[Jan de Mooij [:jandem]]

Attachment: Part 2 - indexOf and contains

Comment 3

[Luke Wagner [:luke]]

Comment on attachment 8432442 [details] [diff] [review]
Part 1 - lastIndexOf

Great, and nice tidying.

Comment 4

[Luke Wagner [:luke]]

Comment on attachment 8432460 [details] [diff] [review]
Part 2 - indexOf and contains

Review of attachment 8432460 [details] [diff] [review]:
-----------------------------------------------------------------

srsly, templates ftw

::: js/src/jsstr.cpp
@@ +1010,5 @@
>  static const int      sBMHBadPattern  = -2;  /* return value if pat is not ISO-Latin-1 */
>  
> +template <typename TextChar, typename PatChar>
> +static int
> +BoyerMooreHorspool(const TextChar *text, uint32_t textlen, const PatChar *pat, uint32_t patlen)

textLen and patLen?

@@ +1015,4 @@
>  {
>      uint8_t skip[sBMHCharSetSize];
>  
>      JS_ASSERT(0 < patlen && patlen <= sBMHPatLenMax);

Since you're tidying up, I'd move this assertion to the top and move 'skip' to the the line before the for loop.

@@ +1020,4 @@
>      for (uint32_t i = 0; i < sBMHCharSetSize; i++)
> +        skip[i] = uint8_t(patlen);
> +
> +    uint32_t patlast = patlen - 1;

patLast?

@@ +1121,2 @@
>  static MOZ_ALWAYS_INLINE int
> +StringMatch(const TextChar *text, uint32_t textlen, const PatChar *pat, uint32_t patlen)

textLen, patLen?

@@ +1167,2 @@
>       *
>       * FIXME: Linux memcmp performance is sad and the manual loop is faster.

It'd be nice to retest this or just remove the hack and see if anything regresses.

@@ +1169,5 @@
>       */
>      return
>  #if !defined(__linux__)
> +        (patlen > 128 && IsSame<TextChar, PatChar>::value)
> +            ? UnrolledMatch<MemCmp<TextChar, PatChar>>(text, textlen, pat, patlen)

I'd try server to see if we can depend on C++11 >> (instead of > >).

Comment 5

[Jan de Mooij [:jandem]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/3fe6b7f69763
https://hg.mozilla.org/integration/mozilla-inbound/rev/dcfd3a026c6f

(In reply to Luke Wagner [:luke] from comment #4)
> srsly, templates ftw

Yes! Really nice.

> textLen and patLen?

I did a search-and-replace in jsstr.cpp (and checked the result).

> Since you're tidying up, I'd move this assertion to the top and move 'skip'
> to the the line before the for loop.

Done.

> patLast?

Done.

> It'd be nice to retest this or just remove the hack and see if anything
> regresses.

I'll file a follow-up bug.

> I'd try server to see if we can depend on C++11 >> (instead of > >).

I remember reading a bugzilla comment saying this is okay to use this now, and some grepping shows a lot of places in dom/.

Comment 6

[Jan de Mooij [:jandem]]

Attachment: Part 3 - startsWith and endsWith

Comment 7

[Jan de Mooij [:jandem]]

Oh this patch also adds a latin1 jit-test directory and moves the basic/latin1-* tests there. The review interface doesn't show that, looks like.

Comment 8

[Luke Wagner [:luke]]

Comment on attachment 8432711 [details] [diff] [review]
Part 3 - startsWith and endsWith

Review of attachment 8432711 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/jsstr.cpp
@@ +1571,5 @@
> +    return true;
> +}
> +
> +static bool
> +IsSubstring(JSLinearString *text, JSLinearString *pat, size_t start)

Perhaps IsSubstringAt hor HasSubstringAt?  IsSubstring sounds like something that would behave more like indexOf.

Comment 9

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/3fe6b7f69763
https://hg.mozilla.org/mozilla-central/rev/dcfd3a026c6f

Comment 10

[Jan de Mooij [:jandem]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/ff1d94fe525c

(In reply to Luke Wagner [:luke] from comment #8)
> Perhaps IsSubstringAt hor HasSubstringAt?  IsSubstring sounds like something
> that would behave more like indexOf.

Ah, nice, I couldn't think of a good name. I changed it to HasSubstringAt.

Comment 11

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/ff1d94fe525c