433799 - a simple optimization in String::equalsUTF8 () with a good performance impact

Status: RESOLVED FIXED

(Tamarin Graveyard :: Tracing Virtual Machine, defect)

Description

[Moh Haghighat]

User-Agent:       Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; .NET CLR 2.0.50727; .NET CLR 1.1.4322; .NET CLR 3.0.04506.648; .NET CLR 3.5.21022; MS-RTC LM 8)
Build Identifier: 

A simple optimization results in good improvement in TT. The function String::equalsUTF8 () in StringObject.cpp returns true iff the two strings are equal.

Here’s the current implementation:

bool String::equalsUTF8(const utf8_t* toCompare, uint32_t _lenbytes)
{
    if (_lenbytes != this->getLen()) 
        return false;
    return ::memcmp(this->getData(), toCompare, _lenbytes) == 0;
}

The code has a short cut to avoid the compare when the lengths are different.
I value profiled the equality of the parameters in the call to memcmp by a simple probe:
	_vprof (toCompare == this->getData());

Here’s the results on Sunspider:
..\..\core\StringObject.cpp:2200 0.688457 [0 : 1] 228854 332416
..\..\core\StringObject.cpp:2200 0.674459 [0 : 1] 779 1155
..\..\core\StringObject.cpp:2200 0.263423 [0 : 1] 145245 551376
..\..\core\StringObject.cpp:2200 0.849673 [0 : 1] 780 918
..\..\core\StringObject.cpp:2200 0.851366 [0 : 1] 779 915
..\..\core\StringObject.cpp:2200 0.851366 [0 : 1] 779 915
..\..\core\StringObject.cpp:2200 0.999777 [0 : 1] 600814 600948
..\..\core\StringObject.cpp:2200 0.8506    [0 : 1] 780 917
..\..\core\StringObject.cpp:2200 0.850273 [0 : 1] 778 915
..\..\core\StringObject.cpp:2200 0.304787 [0 : 1] 2623 8606
..\..\core\StringObject.cpp:2200 0.045018 [0 : 1] 754 16749
..\..\core\StringObject.cpp:2200 0.071435 [0 : 1] 788 11031
..\..\core\StringObject.cpp:2200 0.581109 [0 : 1] 17005 29263
..\..\core\StringObject.cpp:2200 0.850763 [0 : 1] 781 918
..\..\core\StringObject.cpp:2200 0.001674 [0 : 1] 779 465219
..\..\core\StringObject.cpp:2200 0.848913 [0 : 1] 781 920
..\..\core\StringObject.cpp:2200 0.557813 [0 : 1] 15954 28601
..\..\core\StringObject.cpp:2200 0.870457 [0 : 1] 934 1073

This shows that in a significantly large number of cases, we are comparing a utf8_t string object with itself. For example, in the case of of bitops-bitwise-and.abc (line7 above), 99.98% of the 600948 calls compare an object with itself.

Here’s the suggested change:

bool String::equalsUTF8(const utf8_t* toCompare, uint32_t _lenbytes)
{
	// This is only for intern strings which are never offset or prefix
	const utf8_t* thisData = this->getData();
	if (thisData == toCompare) return true;

	if (_lenbytes != this->getLen())
		return false;

	return ::memcmp(thisData, toCompare, _lenbytes) == 0;
}

The performance impact on a Core2 Duo is:

Test                                    TT   TT+patch    %speedup
unspider/access-binary-trees.as         484     422        12.81
sunspider/access-fannkuch.as            422     391         7.35
sunspider/access-nbody.as               610     594         2.62
sunspider/access-nsieve.as              172     156         9.30
sunspider/bitops-3bit-bits-in-byte.      47      46         2.13
sunspider/bitops-bits-in-byte.as        109      93        14.68
sunspider/bitops-bitwise-and.as         828     719        13.16
sunspider/bitops-nsieve-bits.as         172     156         9.30
sunspider/controlflow-recursive.as      109      93        14.68
sunspider/crypto-aes.as                 578     562         2.77
sunspider/crypto-md5.as                 671     640         4.62
sunspider/crypto-sha1.as                141     125        11.35
sunspider/math-cordic.as                172     140        18.60
sunspider/math-partial-sums.as          766     734         4.18
sunspider/math-spectral-norm.as         109     109         0.00
sunspider/s3d-cube.as                   547     531         2.93
sunspider/s3d-morph.as                  282     266         5.67
sunspider/s3d-raytrace.as               812     781         3.82
sunspider/string-fasta.as               562     500        


Reproducible: Always

Steps to Reproduce:
1. Run Tamarin-Tracing on Sunspider benchmarks2.
3.
Actual Results:  
Run Tamarin-Tracing on Sunspider benchmarks

Expected Results:  
The performance impact on a Core2 Duo is:

Test                                    TT   TT+patch    %speedup
unspider/access-binary-trees.as         484     422        12.81
sunspider/access-fannkuch.as            422     391         7.35
sunspider/access-nbody.as               610     594         2.62
sunspider/access-nsieve.as              172     156         9.30
sunspider/bitops-3bit-bits-in-byte.      47      46         2.13
sunspider/bitops-bits-in-byte.as        109      93        14.68
sunspider/bitops-bitwise-and.as         828     719        13.16
sunspider/bitops-nsieve-bits.as         172     156         9.30
sunspider/controlflow-recursive.as      109      93        14.68
sunspider/crypto-aes.as                 578     562         2.77
sunspider/crypto-md5.as                 671     640         4.62
sunspider/crypto-sha1.as                141     125        11.35
sunspider/math-cordic.as                172     140        18.60
sunspider/math-partial-sums.as          766     734         4.18
sunspider/math-spectral-norm.as         109     109         0.00
sunspider/s3d-cube.as                   547     531         2.93
sunspider/s3d-morph.as                  282     266         5.67
sunspider/s3d-raytrace.as               812     781         3.82
sunspider/string-fasta.as               562     500        


Here’s the suggested change:

bool String::equalsUTF8(const utf8_t* toCompare, uint32_t _lenbytes)
{
	// This is only for intern strings which are never offset or prefix
	const utf8_t* thisData = this->getData();
	if (thisData == toCompare) return true;

	if (_lenbytes != this->getLen())
		return false;

	return ::memcmp(thisData, toCompare, _lenbytes) == 0;
}

Comment 1

[Moh Haghighat]

Attachment: the suggested change

Comment 2

[Moh Haghighat]

The results of this experiments were obtained using runtests.py script. We just realized the script is unfair and submitted a report https://bugzilla.mozilla.org/show_bug.cgi?id=434118

Here are the new speedup results using the fixed script.

test                                                   avm    avm2     %sp
--------------------------------                     -----   -----     ---
Sunspider/access-binary-trees.as                     171.0   156.0     8.8
Sunspider/access-nbody.as                            218.0   203.0     6.9
Sunspider/bitops-bitwise-and.as                      281.0   265.0     5.7
Sunspider/bitops-nsieve-bits.as                       47.0    46.0     2.1
Sunspider/string-fasta.as                            187.0   172.0     8.0

Comment 3

[Steven Johnson]

I'll take this and slip the change in with an upcoming push, since it's small

Comment 4

[Steven Johnson]

I think this bug has been obsoleted and/or fixed in https://bugzilla.mozilla.org/show_bug.cgi?id=411163

Comment 5

[Dan Smith]

Marking resolved/fixed per comments of Steven Johnson.