558270 - unroll Duff proper

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Luke Wagner [:luke]]

Attachment: patch

It just occurred to me that the the loop in Duff could be unrolled further so that, once the loop gets revved up, it only does addition every X iterations, where X is the unroll factor (currently 8).  (So, not really Duff's device, just classic loop unrolling.)

A quick micro-bench shows a 38% speedup when the text is long (150 chars), the pattern is short (2), and the match is at the end.  To wit, compared to jsc (opt shell build from January I had lying around) we are: 1.58x faster without -j, 2.16x faster with -j, and 3.34x faster with the patch and -j.

Comment 1

[Luke Wagner [:luke]]

Attachment: perf test

Measured with -j:
                                      Trunk  Patch
Match early:                          31     28
Match at end, with false positives:   99     80
Match at end:                         71     46

It looks like my 38% figure was conservative (measured without -j).

Comment 2

[Luke Wagner [:luke]]

Attachment: perf test (wrong file last time)

Comment 3

[Robert Sayre]

awesome

Comment 4

[Luke Wagner [:luke]]

No observed speedup on SS/V8.  But still, for patlen >= 2 (and out of the BMH range (<11 or >255)), this seems like a big win for long text strings.

Comment 5

[Luke Wagner [:luke]]

http://hg.mozilla.org/tracemonkey/rev/b414c98f9030

Comment 6

[Chris Leary [:cdleary] (not checking bugmail)]

(In reply to comment #3)
> awesome

I think you mean, "Ooh, yeah!"

But then again, "Duff man says a lot of things!"