Re: Algorithm Optimizations - string search

Hello, I was again in bed for few days:/// Hope this time I have fully recovered:/ Anyways the patch for today is for auxiliary php_charmask function used by trim, str_word_count and addcslashes. It is basically just bunch of if-statements. But it can sped up by reordering them. Original needs 4+3 tests executed in case of single char, and 4 in case of range. Optimized needs only 1 test for single char + 3 for range. Maybe not a big improvement, but it is way faster for chars, and about the same speed for ranges. Here are some evaluation results (the results for MOD1): http://212.85.117.53/gsoc/index.php?option=com_content&view=article&id=62:phpmask-possible-reimplementation&catid=36:patches&Itemid=56 The diff is below. Cheers Michal Index: ext/standard/string.c =================================================================== RCS file: /repository/php-src/ext/standard/string.c,v retrieving revision 1.445.2.14.2.69.2.29 diff -u -d -r1.445.2.14.2.69.2.29 string.c --- ext/standard/string.c 3 Jul 2008 14:00:20 -0000 1.445.2.14.2.69.2.29 +++ ext/standard/string.c 8 Jul 2008 20:27:50 -0000 @@ -663,36 +663,38 @@ memset(mask, 0, 256); for (end = input+len; input < end; input++) { c=*input; - if ((input+3 < end) && input[1] == '.' && input[2] == '.' - && input[3] >= c) { - memset(mask+c, 1, input[3] - c + 1); - input+=3; - } else if ((input+1 < end) && input[0] == '.' && input[1] == '.') { - /* Error, try to be as helpful as possible: - (a range ending/starting with '.' won't be captured here) */ - if (end-len >= input) { /* there was no 'left' char */ - php_error_docref(NULL TSRMLS_CC, E_WARNING, "Invalid '..'-range, no character to the left of '..'"); - result = FAILURE; - continue; - } - if (input+2 >= end) { /* there is no 'right' char */ - php_error_docref(NULL TSRMLS_CC, E_WARNING, "Invalid '..'-range, no character to the right of '..'"); + if (input[1] != '.') { + mask[c] = 1; + } else { + if ((input+3 < end) && input[2] == '.' && input[3] >= c) { + memset(mask+c, 1, input[3] - c + 1); + input+=3; + } else if ((input+1 < end) && input[0] == '.' && input[1] == '.') { + if (end-len >= input) { /* there was no 'left' char */ + php_error_docref(NULL TSRMLS_CC, E_WARNING, "Invalid '..'-range, no character to the left of '..'"); + result = FAILURE; + continue; + } + if (input+2 >= end) { /* there is no 'right' char */ + php_error_docref(NULL TSRMLS_CC, E_WARNING, "Invalid '..'-range, no character to the right of '..'"); + result = FAILURE; + continue; + } + if (input[-1] > input[2]) { /* wrong order */ + php_error_docref(NULL TSRMLS_CC, E_WARNING, "Invalid '..'-range, '..'-range needs to be incrementing"); + result = FAILURE; + continue; + } + /* FIXME: better error (a..b..c is the only left possibility?) */ + php_error_docref(NULL TSRMLS_CC, E_WARNING, "Invalid '..'-range"); result = FAILURE; continue; + } else { + mask[c] = 1; } - if (input[-1] > input[2]) { /* wrong order */ - php_error_docref(NULL TSRMLS_CC, E_WARNING, "Invalid '..'-range, '..'-range needs to be incrementing"); - result = FAILURE; - continue; - } - /* FIXME: better error (a..b..c is the only left possibility?) */ - php_error_docref(NULL TSRMLS_CC, E_WARNING, "Invalid '..'-range"); - result = FAILURE; - continue; - } else { - mask[c]=1; } - } + } + return result; } /* }}} */