Groups > comp.lang.c > #126205 > unrolled thread

Count string in string with loop increase 2, why is this not faster?

Started by	Bart Smissaert <bart.smissaert@gmail.com>
First post	2018-02-03 00:00 -0800
Last post	2018-02-03 22:03 +0000
Articles	20 on this page of 98 — 10 participants

Back to article view | Back to comp.lang.c

Page 2 of 5 — ← Prev page 1 [2] 3 4 5 Next page →

#126249

From	Keith Thompson <kst-u@mib.org>
Date	2018-02-03 18:00 -0800
Message-ID	<lna7wp4iq9.fsf@kst-u.example.com>
In reply to	#126247

Richard Damon <Richard@Damon-Family.org> writes:
[...]
> You keep on describing these as ANSI strings, and that you see all these 
> zeros (which implies the UTF-16/UCS-2 encoding), but true ANSI strings 
> are stored a consecutive 8 bit chars (with somewhere a defined code page 
> for the string). It seems that somehow you have what you is maybe data 
> that all would fit in the Latin-1 code page (what you think of as ANSI), 
> but it is expressed as a 'wide string', but then it should have been 
> using pointers to WCHAR / wchar_t / uint16_t / char16_t, not to unsigned 
> char.
>
> Looking up VBA, it looks like you are dealing with a String, also called 
> at time a BSTR, which are passed as pointers to WCHAR which will be a 
> type like uint16_t etc. I don't know where the unsigned char* came from.

In the Windows world, the term "ANSI" is commonly misused to refer
to one of the Windows 8-bit encodings, such as Windows-1252.
Windows-1252 is similar to Latin-1 (ISO 8859-1), but defines
printable characters for some codes that are treated as control
characters in Latin-1.  Historically, I think it was submitted
for ANSI standardization but never approved.  Similarly, "Unicode"
is commonly misused to refer to a particular encoding of Unicode,
UTF-16 (usually the little-endian variant).

(UTF-8 is a much more popular encoding outside the Windows world.)

It's important to be clear about which encoding you're using, especially
when talking to people who might not be familiar with MS Windows.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#126257

From	Bart Smissaert <bart.smissaert@gmail.com>
Date	2018-02-04 01:53 -0800
Message-ID	<91c1bf4a-0096-4d2f-8495-639c96b86797@googlegroups.com>
In reply to	#126249

> It's important to be clear about which encoding you're using, especially
> when talking to people who might not be familiar with MS Windows.

As far as I know VBA handles strings in Unicode, encoded as UTF-16. Admittedly, I am no expert in this. So, this thread deals with Unicode strings, encoded as UTF-16. My application uses SQLite and all the strings stored in that are UTF-8. I know it doesn't have to be UTF-8, but in my case they are. When I get data out of SQLite and move it to VBA (Excel) or VB6 it will be converted from UTF-8 to UTF-16. The reverse will happen when moving data, say from an Excel sheet to SQLite.
Again though, this thread is about Unicode UTF-16 strings.
Hope this clarifies.

RBS

[toc] | [prev] | [next] | [standalone]

#126262

From	Richard Damon <Richard@Damon-Family.org>
Date	2018-02-04 13:23 -0500
Message-ID	<CcIdC.3336$Wm5.2703@fx14.iad>
In reply to	#126257

On 2/4/18 4:53 AM, Bart Smissaert wrote:
>> It's important to be clear about which encoding you're using, especially
>> when talking to people who might not be familiar with MS Windows.
> 
> As far as I know VBA handles strings in Unicode, encoded as UTF-16. Admittedly, I am no expert in this. So, this thread deals with Unicode strings, encoded as UTF-16. My application uses SQLite and all the strings stored in that are UTF-8. I know it doesn't have to be UTF-8, but in my case they are. When I get data out of SQLite and move it to VBA (Excel) or VB6 it will be converted from UTF-8 to UTF-16. The reverse will happen when moving data, say from an Excel sheet to SQLite.
> Again though, this thread is about Unicode UTF-16 strings.
> Hope this clarifies.
> 
> RBS
> 

Sometimes it is unclear if it deals with UTF-16 or UCS-2 strings (which 
would be limited to just the BMP). This goes back to the fact that 
Microsoft adopted using Unicode early, when it was thought that it could 
be a 16 bit character set, and fixed themselves using 16 bit characters 
to avoid variable length encodings.

One issue I was pointing out is that VBA Strings should be seen as 
arrays of WCHAR (roughly uint16_t) not arrays of unsigned char using two 
chars per code point, but your code seems to be doing that.

[toc] | [prev] | [next] | [standalone]

#126263

From	Bart Smissaert <bart.smissaert@gmail.com>
Date	2018-02-04 11:11 -0800
Message-ID	<f3d1ba1f-f853-4e1a-9174-e2bce8342c13@googlegroups.com>
In reply to	#126262

> One issue I was pointing out is that VBA Strings should be seen as 
arrays of WCHAR (roughly uint16_t)

OK, so how should I alter the C function:

int sqlite3_CountStringInStringA(const unsigned char *strSearch, const unsigned char *strFind, int nSearch, int nFind)
{
	int i = 0;
	int countstring = 0;

	if (nSearch == 0 || nFind == 0) {
		return 0;
	}

	for (i = 0; i <= nSearch - nFind; i += 2) {
		if (memcmp(strSearch + i, strFind, nFind) == 0) {
			countstring++;
			i = i + (nFind - 2);
		}
	}

	return countstring;
}

and how the C function declaration:

sqlite3_CountStringInStringA(const unsigned char *strSearch, const unsigned char *strFind, int nSearch, int nFind);


RBS

[toc] | [prev] | [next] | [standalone]

#126265

From	Richard Damon <Richard@Damon-Family.org>
Date	2018-02-04 14:48 -0500
Message-ID	<ssJdC.10452$RQ3.4320@fx02.iad>
In reply to	#126263

On 2/4/18 2:11 PM, Bart Smissaert wrote:
>> One issue I was pointing out is that VBA Strings should be seen as
> arrays of WCHAR (roughly uint16_t)
> 
> OK, so how should I alter the C function:
> 
> int sqlite3_CountStringInStringA(const unsigned char *strSearch, const unsigned char *strFind, int nSearch, int nFind)
> {
> 	int i = 0;
> 	int countstring = 0;
> 
> 	if (nSearch == 0 || nFind == 0) {
> 		return 0;
> 	}
> 
> 	for (i = 0; i <= nSearch - nFind; i += 2) {
> 		if (memcmp(strSearch + i, strFind, nFind) == 0) {
> 			countstring++;
> 			i = i + (nFind - 2);
> 		}
> 	}
> 
> 	return countstring;
> }
> 
> and how the C function declaration:
> 
> sqlite3_CountStringInStringA(const unsigned char *strSearch, const unsigned char *strFind, int nSearch, int nFind);
> 
> 
> RBS
> 

I would have expected the function to have been defined with a 
declaration like:

int sqlite3_CountStringInStringA(const WCHAR *strSearch, const  WCHAR 
*strFind, int nSearch, int nFind);

Now, using the prototype at the call site should generate an error as it 
appears it currently has a unsigned char[] as a data source (either its 
own array or received as a pointer), so you would need to change that 
and so on until you get to the original source.

My guess is that somewhere, some code did something to take a VBA string 
from some runtime, that should have been expresses as a WCHAR* (or some 
other define/typedef to something similar) and made it an unsigned char*

This all gets into code that you haven't shown, so I can't be sure where 
the source is of the strange type for the wide character string.

I also just noticed that your function name ends in A, and remember that 
one convention used in Windows (not sure if it is here), that functions 
often occurred in pairs, a xxxA, and a xxxW, where the A version dealt 
with 'normal' strings, with 8 bit characters, and the W version dealt 
with 'wide' strings, like you have been defining, but you are describing 
the data this function as getting is a wide string (the VBA string).

[toc] | [prev] | [next] | [standalone]

#126266

From	Bart Smissaert <bart.smissaert@gmail.com>
Date	2018-02-04 12:17 -0800
Message-ID	<fb43d0c4-bf8f-4d68-85fc-61fe90354de1@googlegroups.com>
In reply to	#126265

> int sqlite3_CountStringInStringA(const WCHAR *strSearch, const  WCHAR 
*strFind, int nSearch, int nFind);

I tried that but get errors in compiling in MSVS 2012:

Error	1	error C2143: syntax error : missing ')' before '*'	C:\SQLite\311\sqlite3.c	3199	1	SQLite3_StdCall

Line 3199 is:

SQLITE_API sqlite3_CountStringInStringA(const WCHAR *strSearch, const WCHAR *strFind, int nSearch, int nFind);

And I also get:

Error	7	error C2371: 'WCHAR' : redefinition; different basic types	C:\Program Files (x86)\Windows Kits\8.1\Include\um\winnt.h	394	1	SQLite3_StdCall

Note that I am compiling sqlite3.c from the latest Windows download.


RBS

[toc] | [prev] | [next] | [standalone]

#126269

From	bartc <bc@freeuk.com>
Date	2018-02-04 21:53 +0000
Message-ID	<uhLdC.698929$yM6.361778@fx26.am4>
In reply to	#126266

On 04/02/2018 20:17, Bart Smissaert wrote:
>> int sqlite3_CountStringInStringA(const WCHAR *strSearch, const  WCHAR
> *strFind, int nSearch, int nFind);
> 
> I tried that but get errors in compiling in MSVS 2012:
> 
> Error	1	error C2143: syntax error : missing ')' before '*'	C:\SQLite\311\sqlite3.c	3199	1	SQLite3_StdCall

I don't know what WCHAR is supposed to be. Try wchar_t instead.

If it still complains, try adding #include <wchar.h>

(But on my main compiler, wchar_t is just a typedef of 'short int'.)

-- 
bartc

[toc] | [prev] | [next] | [standalone]

#126271

From	Bart Smissaert <bart.smissaert@gmail.com>
Date	2018-02-04 14:35 -0800
Message-ID	<edcf6106-a8e3-4be7-b47f-e9c81b0bad26@googlegroups.com>
In reply to	#126269

Yes, thanks, that compiles and runs as well.
Now however the function give the wrong result, I suppose because it now deals with 2 byte values and not 1 byte values.

These are my 2 functions, first one looping in steps of 1 (used to be byte) and second one looping in steps of 2.

The result should be 2, but I get one for the first function and 0 for the second function.

int sqlite3_CountStringInString(const wchar_t *strSearch, const wchar_t *strFind, int nSearch, int nFind)
{
	int i = 0;
	int countstring = 0;

	if (nSearch == 0 || nFind == 0) {
		return 0;
	}

	for (i = 0; i <= nSearch - nFind; i++) {
		if (memcmp(strSearch + i, strFind, nFind) == 0) {
			countstring++;
			i = i + (nFind - 1);
		}
	}

	return countstring;
}

int sqlite3_CountStringInStringA(const  wchar_t *strSearch, const  wchar_t *strFind, int nSearch, int nFind)
{
	int i = 0;
	int countstring = 0;

	if (nSearch == 0 || nFind == 0) {
		return 0;
	}

	for (i = 0; i <= nSearch - nFind; i += 2) {
		if (memcmp(strSearch + i, strFind, nFind) == 0) {
			countstring++;
			i = i + (nFind - 2);
		}
	}

	return countstring;
}

Will see if I can fix this.

RBS

[toc] | [prev] | [next] | [standalone]

#126279

From	bartc <bc@freeuk.com>
Date	2018-02-04 23:32 +0000
Message-ID	<XJMdC.393317$oi6.108275@fx40.am4>
In reply to	#126271

On 04/02/2018 22:35, Bart Smissaert wrote:
> Yes, thanks, that compiles and runs as well.
> Now however the function give the wrong result, I suppose because it now deals with 2 byte values and not 1 byte values.
> 
> These are my 2 functions, first one looping in steps of 1 (used to be byte) and second one looping in steps of 2.

The first one can no longer loop in steps of 1 bytes, otherwise you will 
be accessing half of one 16-bit character, and half of the next.

> 
> The result should be 2, but I get one for the first function and 0 for the second function.
>
What are he test strings? So that we can recreate your test. I used 
these test strings:

  search: "one two three threethree four five";
  find:   "three"

and got the correct result of 3 from both your first function (or my 
version of it which looks little different), and from your second 
function with the indicated tweaks applied.

> int sqlite3_CountStringInString(const wchar_t *strSearch, const wchar_t *strFind, int nSearch, int nFind)
> {
> 	int i = 0;
> 	int countstring = 0;
> 
> 	if (nSearch == 0 || nFind == 0) {
> 		return 0;
> 	}
> 
> 	for (i = 0; i <= nSearch - nFind; i++) {
> 		if (memcmp(strSearch + i, strFind, nFind) == 0) {
> 			countstring++;
> 			i = i + (nFind - 1);
> 		}
> 	}
> 
> 	return countstring;
> }
> 
> int sqlite3_CountStringInStringA(const  wchar_t *strSearch, const  wchar_t *strFind, int nSearch, int nFind)
> {
> 	int i = 0;
> 	int countstring = 0;
> 
> 	if (nSearch == 0 || nFind == 0) {
> 		return 0;
> 	}
> 
> 	for (i = 0; i <= nSearch - nFind; i += 2) {

Use ++i here;

> 		if (memcmp(strSearch + i, strFind, nFind) == 0) {

Use nFind*2 here (convert characters to bytes. Or technically 
nFind*sizeof(wchar_t)).

> 			countstring++;
> 			i = i + (nFind - 2);

I used i=i+nFind-1. Note that we are now working in wide 16-bit 
characters, and nFind is the number of 16-bit characters.

-- 
bartc

[toc] | [prev] | [next] | [standalone]

#126293

From	Bart Smissaert <bart.smissaert@gmail.com>
Date	2018-02-05 06:26 -0800
Message-ID	<98843798-4d3e-41c5-87e9-870927fdc2ce@googlegroups.com>
In reply to	#126279

Thanks got that working now:

SQLITE_API int sqlite3_CountStringInString(const wchar_t *strSearch, const wchar_t *strFind, int nSearch, int nFind)
{
	int i = 0;
	int countstring = 0;

	if (nSearch == 0 || nFind == 0) {
		return 0;
	}

	for (i = 0; i <= nSearch - nFind; i++) {
		if (memcmp(strSearch + i, strFind, nFind * 2) == 0) {
			countstring++;
			i = i + (nFind - 1);
		}
	}

	return countstring;
}

SQLITE_API int sqlite3_CountStringInStringA(const  unsigned char *strSearch, const  unsigned char *strFind, int nSearch, int nFind)
{

	int i = 0;
	int countstring = 0;

	if (nSearch == 0 || nFind == 0) {
		return 0;
	}

	for (i = 0; i <= nSearch - nFind; i += 2) {
		if (memcmp(strSearch + i, strFind, nFind) == 0) {
			countstring++;
			i = i + (nFind - 2);
		}
	}
	return countstring;
}

There is less of a difference now between the version that skips every other byte and the version that doesn't and not sure it is worth it to have 2 versions.

Could you show me your version of the one that skips every other byte?

RBS

[toc] | [prev] | [next] | [standalone]

#126297

From	bartc <bc@freeuk.com>
Date	2018-02-05 16:59 +0000
Message-ID	<B30eC.488069$1x.140608@fx30.am4>
In reply to	#126293

On 05/02/2018 14:26, Bart Smissaert wrote:

> SQLITE_API int sqlite3_CountStringInString(const wchar_t *strSearch, const wchar_t *strFind, int nSearch, int nFind)

> SQLITE_API int sqlite3_CountStringInStringA(const  unsigned char *strSearch, const  unsigned char *strFind, int nSearch, int nFind)
> {
> 
> 	int i = 0;
> 	int countstring = 0;
> 
> 	if (nSearch == 0 || nFind == 0) {
> 		return 0;
> 	}
> 
> 	for (i = 0; i <= nSearch - nFind; i += 2) {
> 		if (memcmp(strSearch + i, strFind, nFind) == 0) {
> 			countstring++;
> 			i = i + (nFind - 2);
> 		}
> 	}
> 	return countstring;
> }
> 
> There is less of a difference now between the version that skips every other byte and the version that doesn't and not sure it is worth it to have 2 versions.
> 
> Could you show me your version of the one that skips every other byte?

Both my functions took wchar_t* parameters and both ended up doing the 
same thing.

I think once you decided to formally use wchar_t strings, you can't 
really mess about pretending they are char strings.

If some 16-bit characters have data in the high byte, then you can't as 
it will give the wrong results.

But even if all have zero in the high bytes, if using memcmp then you 
have to compare all 16 bits, and you have to step by one wchar_t at a time.

Otherwise looking for "abc" in "xabcdef", the first memcmp compares 
(a,0,b,0,c,0) with (x,0,a,0,b,0), but the second compares (a,0,b,0,c,0) 
with (0,a,0,b,0,c) which is a waste of time. Go straight to (a,0,b,0,c,0).

-- 
bartc

[toc] | [prev] | [next] | [standalone]

#126299

From	Bart Smissaert <bart.smissaert@gmail.com>
Date	2018-02-05 09:44 -0800
Message-ID	<c8ccaab5-0429-4a03-8cb2-a8c23c40bb29@googlegroups.com>
In reply to	#126297

So, are you saying forget about gaining some (little) time by skipping the even bytes? I think it is best to stick with only one, the function called SQLITE_API int sqlite3_CountStringInString.

RBS

[toc] | [prev] | [next] | [standalone]

#126300

From	bartc <bc@freeuk.com>
Date	2018-02-05 18:28 +0000
Message-ID	<gn1eC.1616836$OX.1427743@fx47.am4>
In reply to	#126299

On 05/02/2018 17:44, Bart Smissaert wrote:
> So, are you saying forget about gaining some (little) time by skipping the even bytes? I think it is best to stick with only one, the function called SQLITE_API int sqlite3_CountStringInString.

I think that the char-based version that skipped a byte at a time was 
slowing things down. The one that skipped two bytes is now equivalent to 
the function taking wchar_t strings that skip a char (= 2 bytes) at a time.

So using wchar_t originally would have been better.

I can't see any simple way of making this faster.

-- 
bartc

[toc] | [prev] | [next] | [standalone]

#126301

From	scott@slp53.sl.home (Scott Lurndal)
Date	2018-02-05 18:41 +0000
Message-ID	<Kz1eC.1462$nY2.602@fx28.iad>
In reply to	#126300

bartc <bc@freeuk.com> writes:
>On 05/02/2018 17:44, Bart Smissaert wrote:
>> So, are you saying forget about gaining some (little) time by skipping the even bytes? I think it is best to stick with only one, the function called SQLITE_API int sqlite3_CountStringInString.
>
>I think that the char-based version that skipped a byte at a time was 
>slowing things down. The one that skipped two bytes is now equivalent to 
>the function taking wchar_t strings that skip a char (= 2 bytes) at a time.
>
>So using wchar_t originally would have been better.
>
>I can't see any simple way of making this faster.

Use PCMPEQW to compare a vector of wchar_t's against a vector of the first
character of the search string and compare from there.   Or, if the search
string is less than 8 wchar_t (128 bits), use PCMPEQW with a sliding comparision
against the source string.

[toc] | [prev] | [next] | [standalone]

#126303

From	bartc <bc@freeuk.com>
Date	2018-02-05 20:08 +0000
Message-ID	<iR2eC.760204$pP1.434568@fx21.am4>
In reply to	#126301

On 05/02/2018 18:41, Scott Lurndal wrote:
> bartc <bc@freeuk.com> writes:
>> On 05/02/2018 17:44, Bart Smissaert wrote:
>>> So, are you saying forget about gaining some (little) time by skipping the even bytes? I think it is best to stick with only one, the function called SQLITE_API int sqlite3_CountStringInString.
>>
>> I think that the char-based version that skipped a byte at a time was
>> slowing things down. The one that skipped two bytes is now equivalent to
>> the function taking wchar_t strings that skip a char (= 2 bytes) at a time.
>>
>> So using wchar_t originally would have been better.
>>
>> I can't see any simple way of making this faster...
> 
> Use PCMPEQW to compare a vector of wchar_t's against a vector of the first
> character of the search string and compare from there.   Or, if the search
> string is less than 8 wchar_t (128 bits), use PCMPEQW with a sliding comparision
> against the source string.
> 

... in C.

Isn't this the job of memcmp?

But I've tried a couple of tests and managed 40-60% faster than gcc-O3 
using ordinary inline ASM. (And that's within the framework of my non-C 
language and poor compiler, comparing a 16-bit word at a time as I can't 
remember how to use string compare instructions.)

How did you fare with PCMPEQW?

-- 
bartc

[toc] | [prev] | [next] | [standalone]

#126304

From	scott@slp53.sl.home (Scott Lurndal)
Date	2018-02-05 21:27 +0000
Message-ID	<M_3eC.5140$vP3.694@fx15.iad>
In reply to	#126303

bartc <bc@freeuk.com> writes:
>On 05/02/2018 18:41, Scott Lurndal wrote:
>> bartc <bc@freeuk.com> writes:
>>> On 05/02/2018 17:44, Bart Smissaert wrote:
>>>> So, are you saying forget about gaining some (little) time by skipping the even bytes? I think it is best to stick with only one, the function called SQLITE_API int sqlite3_CountStringInString.
>>>
>>> I think that the char-based version that skipped a byte at a time was
>>> slowing things down. The one that skipped two bytes is now equivalent to
>>> the function taking wchar_t strings that skip a char (= 2 bytes) at a time.
>>>
>>> So using wchar_t originally would have been better.
>>>
>>> I can't see any simple way of making this faster...
>> 
>> Use PCMPEQW to compare a vector of wchar_t's against a vector of the first
>> character of the search string and compare from there.   Or, if the search
>> string is less than 8 wchar_t (128 bits), use PCMPEQW with a sliding comparision
>> against the source string.
>> 
>
>... in C.
>
>Isn't this the job of memcmp?
>
>But I've tried a couple of tests and managed 40-60% faster than gcc-O3 
>using ordinary inline ASM. (And that's within the framework of my non-C 
>language and poor compiler, comparing a 16-bit word at a time as I can't 
>remember how to use string compare instructions.)
>
>How did you fare with PCMPEQW?


http://www.alfredklomp.com/programming/sse-strings/

[toc] | [prev] | [next] | [standalone]

#126306

From	bartc <bc@freeuk.com>
Date	2018-02-05 22:04 +0000
Message-ID	<Vx4eC.534983$YE3.185238@fx06.am4>
In reply to	#126304

On 05/02/2018 21:27, Scott Lurndal wrote:
> bartc <bc@freeuk.com> writes:
>> On 05/02/2018 18:41, Scott Lurndal wrote:
>>> bartc <bc@freeuk.com> writes:
>>>> On 05/02/2018 17:44, Bart Smissaert wrote:
>>>>> So, are you saying forget about gaining some (little) time by skipping the even bytes? I think it is best to stick with only one, the function called SQLITE_API int sqlite3_CountStringInString.
>>>>
>>>> I think that the char-based version that skipped a byte at a time was
>>>> slowing things down. The one that skipped two bytes is now equivalent to
>>>> the function taking wchar_t strings that skip a char (= 2 bytes) at a time.
>>>>
>>>> So using wchar_t originally would have been better.
>>>>
>>>> I can't see any simple way of making this faster...
>>>
>>> Use PCMPEQW to compare a vector of wchar_t's against a vector of the first
>>> character of the search string and compare from there.   Or, if the search
>>> string is less than 8 wchar_t (128 bits), use PCMPEQW with a sliding comparision
>>> against the source string.
>>>
>>
>> ... in C.
>>
>> Isn't this the job of memcmp?
>>
>> But I've tried a couple of tests and managed 40-60% faster than gcc-O3
>> using ordinary inline ASM. (And that's within the framework of my non-C
>> language and poor compiler, comparing a 16-bit word at a time as I can't
>> remember how to use string compare instructions.)
>>
>> How did you fare with PCMPEQW?
> 
> 
> http://www.alfredklomp.com/programming/sse-strings/


Those are for 8-bit, zero terminated strings.

This problem uses 16-bit strings of known length, of which only one is 
zero-terminated, and both contain embedded zero bytes.

Do you have an actual solution for the OP's problem?

-- 
bartc

[toc] | [prev] | [next] | [standalone]

#126308

From	scott@slp53.sl.home (Scott Lurndal)
Date	2018-02-05 22:38 +0000
Message-ID	<j15eC.18818$s_2.335@fx42.iad>
In reply to	#126306

bartc <bc@freeuk.com> writes:
>On 05/02/2018 21:27, Scott Lurndal wrote:
>> bartc <bc@freeuk.com> writes:
>>> On 05/02/2018 18:41, Scott Lurndal wrote:
>>>> bartc <bc@freeuk.com> writes:
>>>>> On 05/02/2018 17:44, Bart Smissaert wrote:
>>>>>> So, are you saying forget about gaining some (little) time by skipping the even bytes? I think it is best to stick with only one, the function called SQLITE_API int sqlite3_CountStringInString.
>>>>>
>>>>> I think that the char-based version that skipped a byte at a time was
>>>>> slowing things down. The one that skipped two bytes is now equivalent to
>>>>> the function taking wchar_t strings that skip a char (= 2 bytes) at a time.
>>>>>
>>>>> So using wchar_t originally would have been better.
>>>>>
>>>>> I can't see any simple way of making this faster...
>>>>
>>>> Use PCMPEQW to compare a vector of wchar_t's against a vector of the first
>>>> character of the search string and compare from there.   Or, if the search
>>>> string is less than 8 wchar_t (128 bits), use PCMPEQW with a sliding comparision
>>>> against the source string.
>>>>
>>>
>>> ... in C.
>>>
>>> Isn't this the job of memcmp?
>>>
>>> But I've tried a couple of tests and managed 40-60% faster than gcc-O3
>>> using ordinary inline ASM. (And that's within the framework of my non-C
>>> language and poor compiler, comparing a 16-bit word at a time as I can't
>>> remember how to use string compare instructions.)
>>>
>>> How did you fare with PCMPEQW?
>> 
>> 
>> http://www.alfredklomp.com/programming/sse-strings/
>
>
>Those are for 8-bit, zero terminated strings.

That was an example.  Please feel free to do your own
work on adapting the example.  Note that all the SSE
string instructions support either 8-bit or 16-bit
elements (UTF-8 or UCS-16).

>Do you have an actual solution for the OP's problem?

Not for free, my time is valuable and I believe in people
doing their own work.  I'm happy to point out potential
paths for them to follow.

[toc] | [prev] | [next] | [standalone]

#126314

From	bartc <bc@freeuk.com>
Date	2018-02-06 01:34 +0000
Message-ID	<8C7eC.446657$1t7.45854@fx03.am4>
In reply to	#126308

On 05/02/2018 22:38, Scott Lurndal wrote:
> bartc <bc@freeuk.com> writes:

>>>> How did you fare with PCMPEQW?
>>>
>>>
>>> http://www.alfredklomp.com/programming/sse-strings/
>>
>>
>> Those are for 8-bit, zero terminated strings.
> 
> That was an example.  Please feel free to do your own
> work on adapting the example.

Me? It's the OP who needs the work and he's more familiar with VBA. 
(I've been using x86 asm for decades and still have a hard time with SSE 
instructions.)

I thought maybe that you'd done tests comparing optimised C against a 
routine using these instructions, and had an idea what benefits there 
might have been before other people wasted /their/ time.

But I've since had another go at the C, and came up with this variation. 
Where occurrences of the search string are sparse, this code, both 
compiled with gcc-O3, can be three times as fast as the original routine:

int test1(wchar_t *strSearch, wchar_t *strFind, int nSearch, int nFind)
{
     int n,c,nbytes;
     int countstring = 0;

     if (nSearch == 0 || nFind == 0 || nFind > nSearch) {
         return 0;
     }
     n=nSearch - nFind+1;
     nbytes = nFind * 2;
     c = *strFind;

     while (n > 0) {
         if (*strSearch == c && memcmp(strSearch, strFind, nbytes)==0) {
             ++countstring;
             strSearch += nFind;
             n -= nFind;
         } else {
             ++strSearch;
             --n;
         }
     }

     return countstring;
}

The key is searching first for a matching first pair of characters 
before bothering to call memcmp. (Which then compares nFind characters, 
including the first pair again, but that was easier to do than to avoid).

It might be worth making nFind==1 a special case, as that can be greatly 
simplified if it is likely to be common.

(I've added a 'nFind>nSearch' check, but that is not really necessary, 
as it will bail out in that case when it gets to the loop. Take it out 
if that condition is unlikely. However, the way gcc-O3 works is so 
unpredictable, that when I did try, it was immediately 20% slower!)

-- 
bartc

[toc] | [prev] | [next] | [standalone]

#126332

From	Bart Smissaert <bart.smissaert@gmail.com>
Date	2018-02-06 06:39 -0800
Message-ID	<f93a9bfe-a458-494b-a8fb-78165b6949d2@googlegroups.com>
In reply to	#126314

> int test1(wchar_t *strSearch

Thanks, I got that about 80% faster in my test with these strings:

strSearch = "This is just a test, testing for the difference between a one-step loop and a two_step loop, counting strings."

strFind = "test"

RBS

[toc] | [prev] | [next] | [standalone]

Page 2 of 5 — ← Prev page 1 [2] 3 4 5 Next page →

csiph-web

Count string in string with loop increase 2, why is this not faster?

Contents

#126249

#126257

#126262

#126263

#126265

#126266

#126269

#126271

#126279

#126293

#126297

#126299

#126300

#126301

#126303

#126304

#126306

#126308

#126314

#126332