Closed Bug 512740 Opened 10 years ago Closed 10 years ago

String code can be optimized.

Categories

(Tamarin Graveyard :: Virtual Machine, defect)

defect
Not set

Tracking

(Not tracked)

VERIFIED FIXED

People

(Reporter: stejohns, Assigned: stejohns)

References

Details

Attachments

(14 obsolete files)

Various useful optimizations for the new String code were found during profiling; this bug is intended to serve a catchall for reviewing them.
Attachment #396776 - Flags: superreview?(daumling)
Attachment #396776 - Flags: review?(edwsmith)
Allows us to use bit-shift rather the multiply/divide for doing offset adjustments. Also saves a bit in our bitflags.
Attachment #396793 - Flags: superreview?(daumling)
Attachment #396793 - Flags: review?(edwsmith)
Rewrite several hot comparison loops using template functions; besides cleaning up the code considerably, we actually get substantially better code generation from GCC for the indexOf and lastIndexOf cases.
Attachment #396812 - Flags: superreview?(daumling)
Attachment #396812 - Flags: review?(edwsmith)
Same as before, but had a signed/unsigned issue that broke hi-bit latin1 chars. Fixed that and added a little TypeTraits love to ensure that people can't pass non-unsigned-chars to the template functions.
Attachment #396812 - Attachment is obsolete: true
Attachment #396828 - Flags: superreview?(daumling)
Attachment #396828 - Flags: review?(edwsmith)
Attachment #396812 - Flags: superreview?(daumling)
Attachment #396812 - Flags: review?(edwsmith)
Attached patch Optimize StIndexableUTF8String (obsolete) — Splinter Review
If the UTF8 string is the same length as the source string, we don't need to do the complex index mapping (it's 7-bit ascii)... bail early. This is hot during PCRE usage and 7-bit patterns are fairly common.
Attachment #396840 - Flags: superreview?(daumling)
Attachment #396840 - Flags: review?(edwsmith)
Attached patch Optimize StUTF8String (obsolete) — Splinter Review
When source length == utf8 length, use memcpy rather than sluggish loop to copy chars. Also some other minor restructuring. This makes a surprisingly large difference for language/search test.
Attachment #396845 - Flags: superreview?(daumling)
Attachment #396845 - Flags: review?(edwsmith)
Attached patch Optimize StUTF8String, #2 (obsolete) — Splinter Review
Use the bit we saved in an earlier patch to cache the "is-7-bit" status of a string. For cases that use this heavily, it makes a dramatic difference. (To wit: the language/string/search.as test ran about 1100ms before any of these patches. With the previous patch it drops to ~300ms. With this patch it drops to ~40ms....)

(Also took the opportunity to restructure the String ctors so that all fields are properly ctor-inited now, so that I could be clear on what is set where...)
Attachment #396862 - Flags: superreview?(daumling)
Attachment #396862 - Flags: review?(edwsmith)
Attached patch More template functions (obsolete) — Splinter Review
Add templated versions of hashCode and indexOfCharCode, and have matchesLatin1 use the existing equalsImpl. 

Also fix bogus comment about equalsUTF8 and note that equalsUTF8 and hashCodeUTF8 could be optimized with 7BIT, but since they aren't currently used (!) I'm not bothering...
Attachment #396880 - Flags: superreview?(daumling)
Attachment #396880 - Flags: review?(edwsmith)
What it says.
Attachment #396891 - Flags: superreview?(daumling)
Attachment #396891 - Flags: review?(edwsmith)
Added MathUtils::toIntClamp to avoid unnecessary double->int conversions. Several String methods had to call toInt() but then check the result against length() to guard against Infinity... in the case of charCodeAt it moves the needle because the meat of the function is so small.
Attachment #396917 - Flags: superreview?(daumling)
Attachment #396917 - Flags: review?(edwsmith)
Attachment #396776 - Flags: superreview?(daumling) → superreview+
Attachment #396793 - Flags: superreview?(daumling) → superreview+
Comment on attachment 396828 [details] [diff] [review]
Rewrite hot loops using template functions, again

The original code used memcmp() for 8-bit compares - is a loop faster? And would it be faster to use *str1++ instead of str1[j]?
Attachment #396828 - Flags: superreview?(daumling) → superreview+
Comment on attachment 396840 [details] [diff] [review]
Optimize StIndexableUTF8String

Good catch!
Attachment #396840 - Flags: superreview?(daumling) → superreview+
Attachment #396845 - Flags: superreview?(daumling) → superreview+
Comment on attachment 396862 [details] [diff] [review]
Optimize StUTF8String, #2

Nit: rename TSTR_7BIT to TSTR_7BIT_FLAG to stay consistent
Attachment #396862 - Flags: superreview?(daumling) → superreview+
Attachment #396880 - Flags: superreview?(daumling) → superreview+
Attachment #396891 - Flags: superreview?(daumling) → superreview+
Attachment #396917 - Flags: superreview?(daumling) → superreview+
(In reply to comment #11)
> (From update of attachment 396828 [details] [diff] [review])
> The original code used memcmp() for 8-bit compares - is a loop faster? And
> would it be faster to use *str1++ instead of str1[j]?

You'd think so, on both counts, but from the profiling I did on GCC/x86-32, that was not the case.
Attached patch inline String::Compare (obsolete) — Splinter Review
String::Compare(Pointers, ...) is called from exactly one function, so inline the contents there to remove pointless call overhead.

Also remove the two completely-unused Compare() variants that take string literals.
Attachment #397084 - Flags: superreview?(daumling)
Attachment #397084 - Flags: review?(edwsmith)
Comment on attachment 397084 [details] [diff] [review]
inline String::Compare

I am sure that you checked all uses of the removed methods - did you also check FP code?
Attachment #397084 - Flags: superreview?(daumling) → superreview+
Attachment #396776 - Flags: review?(edwsmith) → review+
Attachment #396793 - Flags: review?(edwsmith) → review+
Attachment #396828 - Flags: review?(edwsmith) → review+
Attachment #396840 - Flags: review?(edwsmith) → review+
Attachment #396845 - Flags: review?(edwsmith) → review+
Attachment #396862 - Flags: review?(edwsmith) → review+
Attachment #396880 - Flags: review?(edwsmith) → review+
Attachment #396891 - Flags: review?(edwsmith) → review+
Attachment #396917 - Flags: review?(edwsmith) → review+
Attachment #397084 - Flags: review?(edwsmith) → review+
Restructuring generates substantially better / faster code, especially on ARM.
Attachment #398059 - Flags: superreview?(edwsmith)
Attachment #398059 - Flags: review?(daumling)
Comment on attachment 398059 [details] [diff] [review]
optimize indexOfImpl, lastIndexOfImpl

This is a truly amazing finding. Too bad that I don't know the internals of the ARM processor.
Attachment #398059 - Flags: review?(daumling) → review+
Unfortunately, the previous "optimizations" were just plain wrong. (This might be the reason for the measured speedup...) 

"Correct" patch posted here, but not asking for review yet until I have a chance to measure whether it actually makes any speed difference...
Attachment #398059 - Attachment is obsolete: true
Attachment #398059 - Flags: superreview?(edwsmith)
Attached patch indexOf, lastIndexOf once more (obsolete) — Splinter Review
Revised version that is both correct and faster (on MacTel32 and ARM).
Attachment #398196 - Flags: superreview?(edwsmith)
Attachment #398196 - Flags: review?(daumling)
Attachment #398190 - Attachment is obsolete: true
Comment on attachment 396776 [details] [diff] [review]
add isDependent() and isStatic() methods to save an instruction when checking type

pushed as part of changeset:   2419:7756063180de
Attachment #396776 - Attachment is obsolete: true
Comment on attachment 396793 [details] [diff] [review]
Change String width constant values to 0/1

pushed as part of changeset:   2419:7756063180de
Attachment #396793 - Attachment is obsolete: true
Attachment #396828 - Attachment is obsolete: true
Comment on attachment 396828 [details] [diff] [review]
Rewrite hot loops using template functions, again

pushed as part of changeset:   2419:7756063180de
Comment on attachment 396840 [details] [diff] [review]
Optimize StIndexableUTF8String

pushed as part of changeset:   2419:7756063180de
Attachment #396840 - Attachment is obsolete: true
Comment on attachment 396845 [details] [diff] [review]
Optimize StUTF8String

pushed as part of changeset:   2419:7756063180de
Attachment #396845 - Attachment is obsolete: true
Comment on attachment 396862 [details] [diff] [review]
Optimize StUTF8String, #2

pushed as part of changeset:   2419:7756063180de
Attachment #396862 - Attachment is obsolete: true
Comment on attachment 396880 [details] [diff] [review]
More template functions

pushed as part of changeset:   2419:7756063180de
Attachment #396880 - Attachment is obsolete: true
Comment on attachment 396891 [details] [diff] [review]
Add cachedChar optimizations to _charAt and _append

pushed as part of changeset:   2419:7756063180de
Attachment #396891 - Attachment is obsolete: true
Attachment #396917 - Attachment is obsolete: true
Comment on attachment 396917 [details] [diff] [review]
remove unnecessary int<->double conversion

pushed as part of changeset:   2419:7756063180de
Comment on attachment 397084 [details] [diff] [review]
inline String::Compare

pushed as part of changeset:   2419:7756063180de
Attachment #397084 - Attachment is obsolete: true
Attachment #398196 - Flags: review?(daumling) → review+
Depends on: 514400
Attachment #398196 - Flags: superreview?(edwsmith) → superreview+
Comment on attachment 398196 [details] [diff] [review]
indexOf, lastIndexOf once more

pushed as changeset:   2462:ee52b61359ba
Attachment #398196 - Attachment is obsolete: true
Steven, are we done here?
Yep. Closing.
Status: NEW → RESOLVED
Closed: 10 years ago
Resolution: --- → FIXED
Resolved fixed engineering / work item that has been pushed.  Setting status to verified.
Status: RESOLVED → VERIFIED
You need to log in before you can comment on or make changes to this bug.