Bug #14637 trim trailing spaces processes data only byte wise

Description:
In the file strings/ctype-simple.c
are two functions which trim blank spaces from the end of a string.
my_hash_sort_simple() and my_lengthsp_8bit().

Both functions parse the string byte wise and are quite slow for longer strings.

suggested improvement see below

How to repeat:
na

Suggested fix:
Changing the function from parsing the string 8bit wise to work on 32bit wise
would make sense for architectures beeing able to work in unaligned 32bit words.

We would sacrifice a little performance for strings which have zero or only one blank space
but we would gain a very good improvement for strings with more blank spaces.

So instead doing something like this:
int my_hash( char *start, int len){
const char *end= start + len;
while (end > start && end[-1] == ' ')
          end--;
return end;
}

We could do:
int my_hash_32bit( char *start, int len){
const char *end= start + len;
const char *start2= start + (long)(len & 3);
while (end > (unsigned long*)start2 ){
  if( ((unsigned long*)end)[-1] != 0x20202020) break;
  end-=4;
}
while (end > (unsigned char*)start ){
  if( ((unsigned char*)end)[-1] != ' ') break;
  end--;
}
return end;
}

Below is a POWER/PC assembler version of the above function.
please note: the asm function does not test for strings for length=0.
I assume that this case will never appear in MySQL.
Would be good if someone could verify this!

The below asm function beats the current C function for nearly every case,
its only slower for the case of exactly one blank space.

// ##################################################
// find length of string without trailing blankspaces
//
// r3 = ptr to string
// r4 = length of string

asm(
".text                          \n"
".align  4                      \n"
".globl  trim_blankspace_32bit  \n"
"                               \n"
"trim_blankspace_32bit:         \n"
"   mr    r9,r3                 \n"
"   add   r3,r3,r4              \n"
"   lbz   r6,-1(r3)             \n"     // preload end of string
"   andi. r0,r4,3               \n"     //
"   add   r8,r9,r0              \n"
"   lis   r5,0x2020             \n"
"   ori   r5,r5,0x2020          \n"
"   cmpwi cr0,r6,0x20           \n"     // quick exit for 0 blank spaces
"   bnelr+ cr0                  \n"     //
".align  4                      \n"
".loop32bit:                    \n"
"   cmplw cr1,r3,r8             \n"
"   ble-  cr1,.test8bit         \n"
"   lwzu  r4,-4(r3)             \n"
"   cmpw  cr0,r4,r5             \n"
"   bne-  cr0,.start8bit        \n"

"   cmplw cr1,r3,r8             \n"
"   ble-  cr1,.test8bit         \n"
"   lwzu  r4,-4(r3)             \n"
"   cmpw  cr0,r4,r5             \n"
"   beq+  cr0,.loop32bit        \n"

".start8bit:                    \n"     // 32bit test did not match
"   addi  r3,r3,4               \n"     // retest the last 4 bytes
".test8bit:                     \n"
                                        // loop unrolled
"   cmplw  cr1,r3,r9            \n"     // max 3 bytes to test
"   blelr+ cr1                  \n"
"   lbz    r4,-1(r3)            \n"
"   cmpwi  cr0,r4,0x20          \n"
"   bnelr  cr0                  \n"
"   subi   r3,r3,1              \n"
"   cmplw  cr1,r3,r9            \n"
"   blelr+ cr1                  \n"
"   lbz    r4,-1(r3)            \n"
"   cmpwi  cr0,r4,0x20          \n"
"   bnelr  cr0                  \n"
"   subi   r3,r3,1              \n"
"   cmplw  cr1,r3,r9            \n"
"   blelr+ cr1                  \n"
"   lbz    r4,-1(r3)            \n"
"   cmpwi  cr0,r4,0x20          \n"
"   bnelr  cr0                  \n"
"   subi   r3,r3,1              \n"
"   blr                         \n"
);

Cheers
Gunnar

In today's 5.0-BK sources (ChangeSet@1.1957.1.18, 2005-11-03 20:29:21+02:00, jani@ua141d10.elisa.omakaista.fi) one may see the following:

void my_hash_sort_simple(CHARSET_INFO *cs,
                         const uchar *key, uint len,
                         ulong *nr1, ulong *nr2)
{
  register uchar *sort_order=cs->sort_order;
  const uchar *end= key + len;

  /*
    Remove end space. We have to do this to be able to compare
    'A ' and 'A' as identical
  */
  while (end > key && end[-1] == ' ')
    end--;
...

So, yes, it is byte after byte processing, and it may be optimized.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/41796

ChangeSet@1.2799, 2008-02-06 18:45:46+02:00, gkodinov@magare.gmz +5 -0
  Bug #14637: trim trailing spaces processes data only byte wise
   Use and int * where possible to scan for trailing space in a
   string instead of always iterating char-by-char.

sample benchmark file

Attachment: test.test (, text), 1.11 KiB.

Using the attached benchmark file on a 32 bit Intel Core 2 Duo CPU I've got 43485 ms run with the fix compared to 44373 without it.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/42219

ChangeSet@1.2799, 2008-02-13 16:53:24+02:00, gkodinov@magare.gmz +8 -0
  Bug #14637: trim trailing spaces processes data only byte wise
   Use and int * where possible to scan for trailing space in a
   string instead of always iterating char-by-char.
   Using the attached benchmark file on a 32 bit Intel Core 2 
   Duo CPU I've got 43485 ms run with the fix compared to 44373 
   without it.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/42418

ChangeSet@1.2799, 2008-02-16 11:08:10+02:00, gkodinov@magare.gmz +5 -0
  Bug #14637: trim trailing spaces processes data only byte wise
   Use and int * where possible to scan for trailing space in a
   string instead of always iterating char-by-char.
   Using the attached benchmark file on a 32 bit Intel Core 2 
   Duo CPU I've got 43485 ms run with the fix compared to 44373 
   without it.

Pushed into 6.0.5-alpha

Documented in the 6.0.5 changelog as follows:

        The performance of internal functions that trim multiple spaces from
        strings when comparing them has been improved.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/90112

Backported to 5.6.0 (next-mr-runtime)
(6.0-codebase revid: 2476.1362.1)

Pushed into 5.6.0-beta (revid:davi.arnaut@sun.com-20091119234808-xbjpkwaxjt5x5c0b) (version source revid:davi.arnaut@sun.com-20091119234808-xbjpkwaxjt5x5c0b) (merge vers: 5.6.0-beta) (pib:13)

Pushed into 6.0.14-alpha (revid:kostja@sun.com-20091120124947-yi6h2jbgw0kbciwm) (version source revid:kostja@sun.com-20091119222407-5a7cjlhw06trtxnf) (merge vers: 6.0.14-alpha) (pib:13)

Noted in 5.6.0 changelog.

Already fixed in earlier 6.0.x release.

Pushed into 5.5.3-m3 (revid:alik@sun.com-20100306103849-hha31z2enhh7jwt3) (version source revid:vvaintroub@mysql.com-20091120154107-6awpq04plug2xlri) (merge vers: 5.6.0-beta) (pib:16)

Moved 5.6.0 changelog entry to 5.5.3.