Reviewing merge request #70: optimize QString:: toLower()/toUpper()/toCaseFolded()

see commit messages for details.
NOTE that the qunicodetables needs to be re-generated after applying some of these patches.

here are some numbers:

* toUpper() before:
RESULT : tst_QString::toUpper():"600A":
0.00551 msecs per iteration (total: 276, iterations: 50000)
RESULT : tst_QString::toUpper():"600a":
0.00617 msecs per iteration (total: 309, iterations: 50000)
RESULT : tst_QString::toUpper():"300A+300a":
0.00634 msecs per iteration (total: 317, iterations: 50000)
RESULT : tst_QString::toUpper():"300a+300A":
0.00617 msecs per iteration (total: 309, iterations: 50000)
RESULT : tst_QString::toUpper():"300<10400>":
0.00627 msecs per iteration (total: 314, iterations: 50000)
RESULT : tst_QString::toUpper():"300<10428>":
0.00717 msecs per iteration (total: 359, iterations: 50000)
RESULT : tst_QString::toUpper():"150<10400>+150<10428>":
0.00708 msecs per iteration (total: 354, iterations: 50000)
RESULT : tst_QString::toUpper():"150<10428>+150<10400>":
0.00732 msecs per iteration (total: 366, iterations: 50000)
RESULT : tst_QString::toUpper():"300A+150<10400>":
0.00587 msecs per iteration (total: 294, iterations: 50000)
RESULT : tst_QString::toUpper():"300A+150<10428>":
0.00677 msecs per iteration (total: 339, iterations: 50000)
RESULT : tst_QString::toUpper():"300a+150<10400>":
0.00691 msecs per iteration (total: 346, iterations: 50000)
RESULT : tst_QString::toUpper():"300a+150<10428>":
0.00670 msecs per iteration (total: 335, iterations: 50000)
RESULT : tst_QString::toUpper():"600<FB03> (ligature)":
0.0168 msecs per iteration (total: 845, iterations: 50000)

* toUpper() after:
RESULT : tst_QString::toUpper():"600A":
0.00521 msecs per iteration (total: 261, iterations: 50000)
RESULT : tst_QString::toUpper():"600a":
0.00602 msecs per iteration (total: 301, iterations: 50000)
RESULT : tst_QString::toUpper():"300A+300a":
0.00613 msecs per iteration (total: 307, iterations: 50000)
RESULT : tst_QString::toUpper():"300a+300A":
0.00602 msecs per iteration (total: 301, iterations: 50000)
RESULT : tst_QString::toUpper():"300<10400>":
0.00325 msecs per iteration (total: 163, iterations: 50000)
RESULT : tst_QString::toUpper():"300<10428>":
0.00408 msecs per iteration (total: 204, iterations: 50000)
RESULT : tst_QString::toUpper():"150<10400>+150<10428>":
0.00406 msecs per iteration (total: 203, iterations: 50000)
RESULT : tst_QString::toUpper():"150<10428>+150<10400>":
0.00398 msecs per iteration (total: 199, iterations: 50000)
RESULT : tst_QString::toUpper():"300A+150<10400>":
0.00417 msecs per iteration (total: 209, iterations: 50000)
RESULT : tst_QString::toUpper():"300A+150<10428>":
0.00506 msecs per iteration (total: 253, iterations: 50000)
RESULT : tst_QString::toUpper():"300a+150<10400>":
0.00508 msecs per iteration (total: 254, iterations: 50000)
RESULT : tst_QString::toUpper():"300a+150<10428>":
0.00504 msecs per iteration (total: 252, iterations: 50000)
RESULT : tst_QString::toUpper():"600<FB03> (ligature)":
0.0163 msecs per iteration (total: 816, iterations: 50000)

------------------------------

* toCaseFolded() before:
RESULT : tst_QString::toCaseFolded():"600A":
0.00653 msecs per iteration (total: 327, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"600a":
0.00542 msecs per iteration (total: 271, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"300A+300a":
0.00647 msecs per iteration (total: 324, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"300a+300A":
0.00638 msecs per iteration (total: 319, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"300<10400>":
0.00677 msecs per iteration (total: 339, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"300<10428>":
0.00587 msecs per iteration (total: 294, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"150<10400>+150<10428>":
0.00672 msecs per iteration (total: 336, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"150<10428>+150<10400>":
0.00683 msecs per iteration (total: 342, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"300A+150<10400>":
0.00651 msecs per iteration (total: 326, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"300A+150<10428>":
0.00662 msecs per iteration (total: 331, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"300a+150<10400>":
0.00672 msecs per iteration (total: 336, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"300a+150<10428>":
0.00564 msecs per iteration (total: 282, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"600<FB03> (ligature)":
0.00574 msecs per iteration (total: 287, iterations: 50000)

* toCaseFolded() after:
RESULT : tst_QString::toCaseFolded():"600A":
0.00578 msecs per iteration (total: 289, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"600a":
0.00493 msecs per iteration (total: 247, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"300A+300a":
0.00578 msecs per iteration (total: 289, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"300a+300A":
0.00583 msecs per iteration (total: 292, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"300<10400>":
0.00412 msecs per iteration (total: 206, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"300<10428>":
0.00327 msecs per iteration (total: 164, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"150<10400>+150<10428>":
0.00415 msecs per iteration (total: 208, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"150<10428>+150<10400>":
0.00408 msecs per iteration (total: 204, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"300A+150<10400>":
0.00491 msecs per iteration (total: 246, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"300A+150<10428>":
0.00493 msecs per iteration (total: 247, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"300a+150<10400>":
0.00498 msecs per iteration (total: 249, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"300a+150<10428>":
0.00408 msecs per iteration (total: 204, iterations: 50000)
RESULT : tst_QString::toCaseFolded():"600<FB03> (ligature)":
0.00489 msecs per iteration (total: 245, iterations: 50000)

Commits that would be merged:

Version 2
  • Version 1
  • Version 2
  • 36eb5fb
  • f29b81f

    • add tests and benchmarks for QString::toLower()/toUpper()/toCaseFolded()

  • 4ef7d71

    • optimize handling of surrogate pairs in toLower()/toUpper()

  • bd3682d

    • optimize QString::toCaseFolded()

  • 4478c42

    • optimize QString::toLower()/toUpper() for special cases, step 1

  • 70fea3e

    • optimize QString::toLower()/toUpper() for special cases, step 2

Showing 36eb5fb-f29b81f

Comments

Pushed new version 1

avatar Konstantin Ritt | 2011-10-17 16:30:50 UTC 

+                 --p;

What if the string start with a LowSurrogate (invalid, but possible for string coming from the user)? in that case, p would be before the string, and the size in the memcpy would overflow.
Before, there was a test (line 4926) but you removed it.

avatar Olivier Goffart | 2011-10-18 09:37:24 UTC on src/corelib/tools/qstring.cpp 

+                 --p;

prop->lowerCaseDiff always equals to 0 for surrogate parts. IIRC, it’s checked in the tables generator

avatar Konstantin Ritt | 2011-10-18 13:24:20 UTC on src/corelib/tools/qstring.cpp 

+             if (i+j < specialCaseMap.size() - 1)

missing spaces

avatar Oswald Buddenhagen | 2011-10-18 14:53:29 UTC on util/unicode/main.cpp

you may want to add a comment with an exact reference why your variant is ok. because the next guy looking at the code will ask the same question as olivier …

avatar Oswald Buddenhagen | 2011-10-18 14:54:45 UTC

→ State changed from New to Updated

done

avatar Konstantin Ritt | 2011-10-18 16:11:44 UTC

Pushed new version 2

avatar Konstantin Ritt | 2011-10-18 16:11:50 UTC

Looks good to me.

avatar Olivier Goffart | 2011-10-18 16:46:28 UTC 

+        if (QChar::isHighSurrogate(*p) && QChar::isLowSurrogate(p[1])) {

whitespace is messed up here. fixing myself.

avatar Oswald Buddenhagen | 2011-10-18 17:22:15 UTC on src/corelib/tools/qstring.cpp

→ State changed from Updated to Revise and resubmit 

FAIL!  : tst_QString::toUpper() Compared values are not the same
   Actual (QString(1, QChar(0xdf)).toUpper()): S  
   Expected (QString("SS")): SS  
   Loc: [tst_qstring.cpp(1593)]  
FAIL!  : tst_QString::toLower() Compared values are not the same  
   Actual (QString(1, QChar(0x130)).toLower()): ?  
   Expected (QString(QString(1, QChar(0x69)) + QChar(0x307))): i?  
   Loc: [tst_qstring.cpp(1652)]

avatar Oswald Buddenhagen | 2011-10-19 12:30:26 UTC

→ State changed from Revise and resubmit to Closed

Thank you for your contribution. With the launch of the Qt Project
under Open Governance [1], you can now contribute your changes via Gerrit [2].
At the same time, contributions via Gitorious can no longer be merged.

We would still like to see your patch on the new platform, and wish for you to become
a member of the Qt Project. Please read [3] and in particular [4] to familiarize yourself
with the new tools. You will still find a read-only mirror of all Qt repositories on
Gitorious.

With a much wider set of possible reviewers, we are also looking forward to better
response times to contributions. Looking forward to your patch!

The Nokia Qt team

[1] http://labs.qt.nokia.com/2011/10/21/the-qt-project-is-live/
[2] http://codereview.qt-project.org
[3] http://www.qt-project.org
[4] http://developer.qt.nokia.com/wiki/Gerrit_Introduction

avatar The Qt Project | 2011-10-21 14:22:14 UTC

Add a new comment:

Login or create an account to post a comment

How to apply this merge request to your repository