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 3 of 5 — ← Prev page 1 2 [3] 4 5 Next page →

#126339

From	bartc <bc@freeuk.com>
Date	2018-02-06 18:07 +0000
Message-ID	<s9meC.917167$ch5.593863@fx18.am4>
In reply to	#126332

On 06/02/2018 14:39, Bart Smissaert wrote:
>> 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"

I got more dramatic differences, when testing those strings 10M times.

With gcc/O3 64-bits, fast and slow timings were 2.5 and 7.1 seconds 
(180% faster).

With gcc/O3 32-bits, they were 2.8 and 13 seconds (360% faster).

With O0 (no optimisation) the differences were narrow, I think between 
80% and 200% faster.

-- 
bartc

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

#126341

From	Bart Smissaert <bart.smissaert@gmail.com>
Date	2018-02-06 12:34 -0800
Message-ID	<2297ba4e-8d2f-4516-9907-b767f2836897@googlegroups.com>
In reply to	#126339

No idea why your differences are so much larger. I am compiling (std_call as I am accessing the C dll from VBA via a .tlb) in MSVS 2012. Not sure it makes a difference, but my code is in the large SQLite3 amalgation 3.22.0.

I had a go at trying to make a fast function for if strFind is a single character, but this is the best I have come up with and not much faster than your latest test1:

SQLITE_API int sqlite3_CountCharInString(const wchar_t *strSearch, int count, const wchar_t *strChar)
{
	int i;
	int total;
	total = 0;

	for (i = 0; i<count; i++)
	{
		if (*strSearch == *strChar) total++;
		strSearch++;
	}
	return total;
}

RBS

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

#126346

From	bartc <bc@freeuk.com>
Date	2018-02-06 21:12 +0000
Message-ID	<aToeC.470372$oD1.406285@fx44.am4>
In reply to	#126341

On 06/02/2018 20:34, Bart Smissaert wrote:
> No idea why your differences are so much larger. I am compiling (std_call as I am accessing the C dll from VBA via a .tlb) in MSVS 2012. Not sure it makes a difference, but my code is in the large SQLite3 amalgation 3.22.0.
> 
> I had a go at trying to make a fast function for if strFind is a single character, but this is the best I have come up with and not much faster than your latest test1:
> 
> SQLITE_API int sqlite3_CountCharInString(const wchar_t *strSearch, int count, const wchar_t *strChar)
> {
> 	int i;
> 	int total;
> 	total = 0;
> 
> 	for (i = 0; i<count; i++)
> 	{
> 		if (*strSearch == *strChar) total++;
> 		strSearch++;
> 	}
> 	return total;
> }
> 
> RBS
> 

This is very odd.

My routine took 2.8 seconds to find the 12 occurrences of "t" in your 
test string (repeated 10 milion times).

Then I tried the specialised routine below, which is simpler than yours, 
doesn't need the string length (assuming it's zero-terminated with a 
16-bit zero), and passes the find character directly.

It took 1.2 seconds for the same task (either called directly, or from 
inside the general routine).

Then I thought I'd try yours. And yours took 0.4 seconds!

So I've no idea what's going on.

I then decided to leave gcc and tried a non-optimising compiler, TCC. 
There, the regular routine took 4.3 seconds; my testonechar() 3.4 
seconds, and yours was 4.5 seconds.

Using gcc again with optimisation off, the results were similar to TCC, 
but narrower.

So it might be better to disregard the results from gcc-O3, as that 
might be taking advantage of some inferences it can make from the small 
test program, which will not be the case in a real program.

It looks like my one-character routine is somewhat faster than the 
regular one; yours /might/ be faster. But in all it probably isn't 
worthwhile to have a dedicated function.

(Do you get your MSVC to optimise the code?)

--------------------------------
int testonechar(wchar_t *strSearch, wchar_t cFind)
{
     int c;
     int countstring = 0;

     while (c  = *strSearch++) if (c==cFind) ++countstring;

     return countstring;
}

-- 
bartc

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

#126348

From	Bart Smissaert <bart.smissaert@gmail.com>
Date	2018-02-06 13:42 -0800
Message-ID	<3653e794-521e-4d53-b6e8-a7579d5be99f@googlegroups.com>
In reply to	#126346

> But in all it probably isn't worthwhile to have a dedicated function

Yes, that is what I found sofar and didn't expect that.

If I understand it well you are using the actual value of cFind in your testonechar function, rather than a pointer. I found that using the pointer
is slightly faster.

> Do you get your MSVC to optimise the code?

Yes, but I have a feeling it could be optimized more:

Optimization:                    Optimize Speed (/O2)
Inline Function Expansion:       Default
Enable Intrinsic Functions:      No
Favor Speed Or Size:             Neither
Omit Frame Pointers:             No(Oy-)
Enable Fibre-Safe Optimizations: No
Whole Program Optimization:      No


RBS

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

#126351

From	Bart Smissaert <bart.smissaert@gmail.com>
Date	2018-02-06 16:43 -0800
Message-ID	<64044642-4874-4fcb-94ae-e8271c184faa@googlegroups.com>
In reply to	#126346

For some reason your function gets quite slow (some 4-5x) when you pick a character where the second byte is not zero, eg Char(128).
I tried to pass the pointer of the character instead, but couldn't get that to work, to do with the intermediate variable c and getting overflow.

RBS

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

#126352

From	bartc <bc@freeuk.com>
Date	2018-02-07 01:10 +0000
Message-ID	<pmseC.673377$QL6.442615@fx20.am4>
In reply to	#126351

On 07/02/2018 00:43, Bart Smissaert wrote:
> For some reason your function gets quite slow (some 4-5x) when you pick a character where the second byte is not zero, eg Char(128).

That one should still have the second byte zero unless wchar_t is 
signed. But on Windows it appears to be unsigned. Try this code:

  double x;
  wchar_t c;

  c=128;
  x=c;

  printf("%f\n",x);

It should display 128.0000.

Anyway I tried a value 30000 for the 1-character find string, and 
injected 30000 as the 6th character of the search string, and couldn't 
see a difference. What strings did you use?

This search is really just working with 16-bit integers; that they 
represent ASCII or UCS2 characters is irrelevant.

(BTW, if using my testonechar() routine, did you ensure the wchar buffer 
is terminated by one word of zeros? If not then it might explain why 
it's taking longer, as it will search memory until it encounters two 
zero bytes.)

-- 
bartc

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

#126353

From	Keith Thompson <kst-u@mib.org>
Date	2018-02-06 18:47 -0800
Message-ID	<ln8tc51poo.fsf@kst-u.example.com>
In reply to	#126352

bartc <bc@freeuk.com> writes:
> On 07/02/2018 00:43, Bart Smissaert wrote:
>> For some reason your function gets quite slow (some 4-5x) when you
>> pick a character where the second byte is not zero, eg Char(128).
>
> That one should still have the second byte zero unless wchar_t is 
> signed. But on Windows it appears to be unsigned. Try this code:
>
>   double x;
>   wchar_t c;
>
>   c=128;
>   x=c;
>
>   printf("%f\n",x);
>
> It should display 128.0000.

The only way that could display a value other than 128.000000
is if wchar_t is signed and only 8 bits.  (In that case it would
most likely print -128.000000.)

If you want to see the characteristics of wchar_t on your system,
try this:

#include <stdio.h>
#include <stddef.h>
#include <limits.h>
#include <stdint.h>
int main(void) {              
    printf("wchar_t is %zu bits, %s\n",
           CHAR_BIT * sizeof (wchar_t),
           (wchar_t)-1 < (wchar_t)0 ? "signed" : "unsigned");
    printf("WCHAR_MIN = %ld\n", (long)WCHAR_MIN);
    printf("WCHAR_MAX = %ld\n", (long)WCHAR_MAX);
}

-- 
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]

#126356

From	David Brown <david.brown@hesbynett.no>
Date	2018-02-07 15:13 +0100
Message-ID	<p5f1id$lpe$1@dont-email.me>
In reply to	#126353

On 07/02/18 14:56, bartc wrote:
> On 07/02/2018 12:02, Ben Bacarisse wrote:
>> bartc <bc@freeuk.com> writes:
> 
>>> The same method works but you have to use:
>>>
>>>    c = 32768;
>>
>> Not on my system.  You are assuming that wchar_t is two bytes, and if
>> wchar_t is two bytes and signed, that the implementation does what you
>> expect with an overflowing signed integer conversion.
>>
>> Both of these may be reasonable in the context, but it is so easy to
>> test if an integer type is signed in C that making these assumptions
>> seems unnecessary: (T)-1 will be positive if T if an unsigned integer
>> type.
> 
> Given an arbitrary integer expression of arbitrary type, and you want to
> know if C regards its value as negative, then assigning or casting to
> floating point and printing the result is a simple, direct way of doing it.
> 

That is true - but it does not affect what Ben wrote.  In general (i.e.,
not in any specific system), wchar_t may be signed or unsigned, it does
not have to be any bigger than a char, and does not have to have the
same signedness as char.  Obviously an 8-bit wchar_t would not be
particularly useful on a host that can support wider character sets, so
16-bit and 32-bit wchar_t are common.  (8-bit wchar_t may be used in
smaller embedded systems - while I work with such systems, I have never
had need of a wchar_t and haven't looked at sizes.)

So if wchar_t is signed and is 16-bit or less, then "c = 32768" is
implementation defined.  It is certainly common to give the same effect
as "c = -32768" when using signed 16-bit types, but it is not required.
 And if wchar_t is 8-bit, it is likely (but not required) to be 0.

Anyway, if you want a simple and direct way to tell if "x" is negative,
why not write:

	if (x < 0) printf("x is negative\n");

?

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

#126380

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2018-02-07 14:48 +0000
Message-ID	<87lgg4hn3i.fsf@bsb.me.uk>
In reply to	#126356

David Brown <david.brown@hesbynett.no> writes:

> On 07/02/18 14:56, bartc wrote:
<snip>
>> Given an arbitrary integer expression of arbitrary type, and you want to
>> know if C regards its value as negative, then assigning or casting to
>> floating point and printing the result is a simple, direct way of doing it.
>
> That is true

Except for the fact that for some values the conversion will be undefined.

<snip>
-- 
Ben.

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

#126388

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2018-02-07 17:13 +0000
Message-ID	<87r2pwg1tw.fsf@bsb.me.uk>
In reply to	#126380

David Brown <david.brown@hesbynett.no> writes:

> On 07/02/18 15:48, Ben Bacarisse wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>> 
>>> On 07/02/18 14:56, bartc wrote:
>> <snip>
>>>> Given an arbitrary integer expression of arbitrary type, and you want to
>>>> know if C regards its value as negative, then assigning or casting to
>>>> floating point and printing the result is a simple, direct way of doing it.
>>>
>>> That is true
>> 
>> Except for the fact that for some values the conversion will be undefined.
>
> Will it?  Which values?  If the integer type has trap values, then the
> conversion will be undefined.  I suppose in theory you could have an
> integer type that has a wider range of values than a floating point
> type, but I think it is unlikely!

Yes, that is very unlikely[1] and not what I was thinking of.  I was
thinking that non-exact conversions were undefined so as to permit a
floating-point exception, but no, the nearest FP number must be chosen
(though it's implementation-defined if it's the next highest or the next
lowest).

[1] Unless short float makes it into C, but I can't wait that long to
    reply just so I can be right!
-- 
Ben.

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

#126395

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2018-02-07 17:27 +0000
Message-ID	<87lgg4g16n.fsf@bsb.me.uk>
In reply to	#126380

David Brown <david.brown@hesbynett.no> writes:

> On 07/02/18 15:48, Ben Bacarisse wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>> 
>>> On 07/02/18 14:56, bartc wrote:
>> <snip>
>>>> Given an arbitrary integer expression of arbitrary type, and you want to
>>>> know if C regards its value as negative, then assigning or casting to
>>>> floating point and printing the result is a simple, direct way of doing it.
>>>
>>> That is true
>> 
>> Except for the fact that for some values the conversion will be undefined.
>> 
>
> Will it?  Which values?

In fact, all it needs is a 128-bit integer type, and a literal reading
of "cast to floating point", but that is still unlikely (and not what I
was thinking of).

-- 
Ben.

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

#126415

From	David Brown <david.brown@hesbynett.no>
Date	2018-02-07 17:01 +0100
Message-ID	<p5f7sq$4vg$1@dont-email.me>
In reply to	#126380

On 07/02/18 15:48, Ben Bacarisse wrote:
> David Brown <david.brown@hesbynett.no> writes:
> 
>> On 07/02/18 14:56, bartc wrote:
> <snip>
>>> Given an arbitrary integer expression of arbitrary type, and you want to
>>> know if C regards its value as negative, then assigning or casting to
>>> floating point and printing the result is a simple, direct way of doing it.
>>
>> That is true
> 
> Except for the fact that for some values the conversion will be undefined.
> 

Will it?  Which values?  If the integer type has trap values, then the
conversion will be undefined.  I suppose in theory you could have an
integer type that has a wider range of values than a floating point
type, but I think it is unlikely!

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

#126364

From	Bart Smissaert <bart.smissaert@gmail.com>
Date	2018-02-07 02:00 -0800
Message-ID	<6ea33c13-f89b-4075-8de7-d6756ebb9218@googlegroups.com>
In reply to	#126353

I think there are some misunderstanding here. I said Char(128), but I should have said Chr(128). This is VBA or VB6 Chr. This returns the character based on the ASCII value. If I do in VBA this:

Sub xxx()

Dim str As String
Dim arrBytes() As Byte

str = Chr(128)
arrBytes = str

Debug.Print arrBytes(0) & "," & arrBytes(1)

End Sub

Then I get this output:

172,32

So, second byte is not zero.

So, how should C see this as 128?
If I have Chr(128) as the character to find then what should I pass to the C function? I thought this should be an integer value made up of 172 as first byte and 32 as second byte. This does indeed work and gives me the right count, but as said is quite slow.

RBS

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

#126368

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2018-02-07 12:02 +0000
Message-ID	<87372dhus1.fsf@bsb.me.uk>
In reply to	#126353

bartc <bc@freeuk.com> writes:

> On 07/02/2018 02:47, Keith Thompson wrote:
>> bartc <bc@freeuk.com> writes:
>>> On 07/02/2018 00:43, Bart Smissaert wrote:
>>>> For some reason your function gets quite slow (some 4-5x) when you
>>>> pick a character where the second byte is not zero, eg Char(128).
>>>
>>> That one should still have the second byte zero unless wchar_t is
>>> signed. But on Windows it appears to be unsigned. Try this code:
>>>
>>>    double x;
>>>    wchar_t c;
>>>
>>>    c=128;
>>>    x=c;
>>>
>>>    printf("%f\n",x);
>>>
>>> It should display 128.0000.
>>
>> The only way that could display a value other than 128.000000
>> is if wchar_t is signed and only 8 bits.  (In that case it would
>> most likely print -128.000000.)
>
> Yeah, that was some confusion on my part.
>
>> If you want to see the characteristics of wchar_t on your system,
>> try this:
>
> The same method works but you have to use:
>
>   c = 32768;

Not on my system.  You are assuming that wchar_t is two bytes, and if
wchar_t is two bytes and signed, that the implementation does what you
expect with an overflowing signed integer conversion.

Both of these may be reasonable in the context, but it is so easy to
test if an integer type is signed in C that making these assumptions
seems unnecessary: (T)-1 will be positive if T if an unsigned integer
type.

-- 
Ben.

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

#126379

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2018-02-07 14:46 +0000
Message-ID	<87r2pwhn7q.fsf@bsb.me.uk>
In reply to	#126368

bartc <bc@freeuk.com> writes:

> On 07/02/2018 12:02, Ben Bacarisse wrote:
>> bartc <bc@freeuk.com> writes:
>
>>> The same method works but you have to use:
>>>
>>>    c = 32768;
>>
>> Not on my system.  You are assuming that wchar_t is two bytes, and if
>> wchar_t is two bytes and signed, that the implementation does what you
>> expect with an overflowing signed integer conversion.
>>
>> Both of these may be reasonable in the context, but it is so easy to
>> test if an integer type is signed in C that making these assumptions
>> seems unnecessary: (T)-1 will be positive if T if an unsigned integer
>> type.
>
> Given an arbitrary integer expression of arbitrary type, and you want
> to know if C regards its value as negative, then assigning or casting
> to floating point and printing the result is a simple, direct way of
> doing it.

We weren't talking about that.  If that is what you want to do, why
would you add the conversion to a floating point type?  Even if you like
extra conversions, it will be undefined for some integer values.

The issue was to detect if an integer /type/ is signed or unsigned.
That can be done without guessing a magic value and hoping the
conversion is defined the way you want.

The simple way is to test (T)-1.  You don't like that (which is fine --
I'm never going to be reading your C code) but people searching for this
topic in the future should be able to find the right to do it.

-- 
Ben.

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

#126408

From	bartc <bc@freeuk.com>
Date	2018-02-07 13:56 +0000
Message-ID	<9ADeC.1713694$OX.256926@fx47.am4>
In reply to	#126368

On 07/02/2018 12:02, Ben Bacarisse wrote:
> bartc <bc@freeuk.com> writes:

>> The same method works but you have to use:
>>
>>    c = 32768;
> 
> Not on my system.  You are assuming that wchar_t is two bytes, and if
> wchar_t is two bytes and signed, that the implementation does what you
> expect with an overflowing signed integer conversion.
> 
> Both of these may be reasonable in the context, but it is so easy to
> test if an integer type is signed in C that making these assumptions
> seems unnecessary: (T)-1 will be positive if T if an unsigned integer
> type.

Given an arbitrary integer expression of arbitrary type, and you want to 
know if C regards its value as negative, then assigning or casting to 
floating point and printing the result is a simple, direct way of doing it.

-- 
bartc

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

#126396

From	bartc <bc@freeuk.com>
Date	2018-02-07 11:17 +0000
Message-ID	<UeBeC.603044$9X4.108846@fx02.am4>
In reply to	#126353

On 07/02/2018 02:47, Keith Thompson wrote:
> bartc <bc@freeuk.com> writes:
>> On 07/02/2018 00:43, Bart Smissaert wrote:
>>> For some reason your function gets quite slow (some 4-5x) when you
>>> pick a character where the second byte is not zero, eg Char(128).
>>
>> That one should still have the second byte zero unless wchar_t is
>> signed. But on Windows it appears to be unsigned. Try this code:
>>
>>    double x;
>>    wchar_t c;
>>
>>    c=128;
>>    x=c;
>>
>>    printf("%f\n",x);
>>
>> It should display 128.0000.
> 
> The only way that could display a value other than 128.000000
> is if wchar_t is signed and only 8 bits.  (In that case it would
> most likely print -128.000000.)

Yeah, that was some confusion on my part.

> If you want to see the characteristics of wchar_t on your system,
> try this:

The same method works but you have to use:

   c = 32768;

instead. This method is easy to understand; your isn't. It also works 
with any expression of unknown result type and signage.


-- 
bartc

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

#126367

From	Bart Smissaert <bart.smissaert@gmail.com>
Date	2018-02-06 23:59 -0800
Message-ID	<b0ddefa8-9e8b-40c1-90ca-2975a6187238@googlegroups.com>
In reply to	#126352

> did you ensure the wchar buffer is terminated by one word of zeros?

Aah, of course, VBA and VB6 strings are not null terminated, they have the length prepended at the start of the string! Off now, but will have a look at this later.

RBS

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

#126384

From	Bart Smissaert <bart.smissaert@gmail.com>
Date	2018-02-07 05:10 -0800
Message-ID	<77f89bc9-7fc4-4ba4-bc23-7b0e9ac3f57b@googlegroups.com>
In reply to	#126367

I added the length as function argument, but that didn't alter the speed (about 5x slower), but using the char pointer instead of the char integer value solved the slowness:

SQLITE_API int sqlite3_testonechar(wchar_t *strSearch, int nLength, wchar_t *cFind)
{

	int countstring = 0;

	while (nLength--) if (*strSearch++ == *cFind) ++countstring;

	//while (c = *strSearch++) if (c == cFind) ++countstring;

	return countstring;
}

It is however no faster than my first attempt:

SQLITE_API int sqlite3_CountCharInString(const wchar_t *strSearch, int nCount, const wchar_t *strChar)
{
	int i;
	int total;
	total = 0;

	for (i = 0; i < nCount; i++)
	{
		if (*strSearch == *strChar) total++;
		strSearch++;
	}
	return total;
}

They are about equally fast.


RBS

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

#126392

From	bartc <bc@freeuk.com>
Date	2018-02-07 11:01 +0000
Message-ID	<Z%AeC.603013$9X4.404573@fx02.am4>
In reply to	#126367

On 07/02/2018 07:59, Bart Smissaert wrote:
>> did you ensure the wchar buffer is terminated by one word of zeros?
> 
> Aah, of course, VBA and VB6 strings are not null terminated, they have the length prepended at the start of the string! Off now, but will have a look at this later.

OK, in that case just tweak the routine to accept a length, as that is 
already available anyway. The loop becomes something like this:

     while (length--) if (*strSearch++ == cFind) ++countstring;

I'd thought that these were C wchar_t strings with a terminator.

-- 
bartc

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

Page 3 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

#126339

#126341

#126346

#126348

#126351

#126352

#126353

#126356

#126380

#126388

#126395

#126415

#126364

#126368

#126379

#126408

#126396

#126367

#126384

#126392