On Wednesday, August 11, 2021 at 11:34:16 AM UTC+3, anti...@math.uni.wroc.pl wrote:
> DFS <nos...@dfs.com> wrote:
> >
> > Thanks. I created a static array[10_000_000] outside the function, and
> > it handled large results sets just fine. But another issue popped up,
> > using option 2, which concatenates words one by one into that static
> > array, then does one puts() at the end.
> >
> > Turns out it's VERY slow for large result sets.
> >
> > Option 1 Option 2
> > substring catt: 91 matches found 0.04s 0.038s
> > substring cat : 3710 matches found 0.20s 0.16s
> > substring ca : 22793 matches found 1.39s 2.25s
> > substring c : 128689 matches found 7.75s 57.91s
> > substring e : 252896 matches found 15.29s 216.58s
> >
> > Option 1 starts printing immediately, one line at a time. Option 2 sits
> > there constructing that long string for quite a while. Too long I
> > think. What might I be doing wrong?
> >
> > Note: the timing includes time to print to screen. Just finding the
> > word matches is 0.03s using either option.
> >
> >
> > =================================================================
> >
> > //option 1: one puts per line (suggested by bart)
> > int i = 0;
> > char buff[longword+3];
> > char line[tcols];
> > *line = '\0';
> > while(i < matchcnt) {
> > for(int j = 1;j<=maxcols;j++) {
> > sprintf(buff,"%-*s ",longword,matchwords[i++]);
> > strcat(line,buff);
> > }
> > puts(line);
> > *buff = '\0';
> > *line = '\0';
> > }
> >
> > =================================================================
> >
> > //option 2: one big string, one puts (per Lurndal)
> > static char line[10000000]; //declared outside the func
> >
> > int i = 0;
> > char buff[longword+3];
> > *line = '\0';
> > while(i < matchcnt) {
> > for(int j = 1;j<=maxcols;j++) {
> > sprintf(buff,"%-*s ",longword,matchwords[i++]);
> > strcat(line,buff);
> ^^^^^^^^^^^^^^^^^^
> > }
> > *buff = '\0';
> > strcat(line,"\n");
> > }
> > puts(line);
> >
> > =================================================================
> The 'strcat' in a loop is classic antipattern: it causes quadratic
> complexity to to repeated scanning for end of 'line'. Use something
> like
>
> char * cp = line;
> .....
> strcat(cp, buff);
> cp += strlen(buff);
> ....
>
>
> --
> Waldek Hebisch

strcat() should have been deprecated in 1989 with replacement that returns something potentially useful, e.g. pointer to
termination character of result string or length of result string. Or return nothing, which still would be an improvement.

But committees have their own logic.

Michael S <already5chosen@yahoo.com> writes:

> On Wednesday, August 11, 2021 at 1:23:55 PM UTC+3, Ben Bacarisse wrote:
>> anti...@math.uni.wroc.pl writes:
>>
>> > DFS <nos...@dfs.com> wrote:
>> <cut>
>> >> =================================================================
>> >>
>> >> //option 1: one puts per line (suggested by bart)
>> >> int i = 0;
>> >> char buff[longword+3];
>> >> char line[tcols];
>> >> *line = '\0';
>> >> while(i < matchcnt) {
>> >> for(int j = 1;j<=maxcols;j++) {
>> >> sprintf(buff,"%-*s ",longword,matchwords[i++]);
>> >> strcat(line,buff);
>> >> }
>> >> puts(line);
>> >> *buff = '\0';
>> >> *line = '\0';
>> >> }
>> >>
>> >> =================================================================
>> >>
>> >> //option 2: one big string, one puts (per Lurndal)
>> >> static char line[10000000]; //declared outside the func
>> >>
>> >> int i = 0;
>> >> char buff[longword+3];
>> >> *line = '\0';
>> >> while(i < matchcnt) {
>> >> for(int j = 1;j<=maxcols;j++) {
>> >> sprintf(buff,"%-*s ",longword,matchwords[i++]);
>> >> strcat(line,buff);
>> > ^^^^^^^^^^^^^^^^^^
>> >> }
>> >> *buff = '\0';
>> >> strcat(line,"\n");
>> >> }
>> >> puts(line);
>> >>
>> >> =================================================================
>> >
>> > The 'strcat' in a loop is classic antipattern: it causes quadratic
>> > complexity to to repeated scanning for end of 'line'. Use something
>> > like
>> >
>> > char * cp = line;
>> > .....
>> > strcat(cp, buff);
>> > cp += strlen(buff);
>> > ....
>> ... or get the length first and use memcpy. But my favourite is
>>
>> cp += snprintf(cp, "%s", whatever);
>>
>> --
>> Ben.
>
> Don't you mean sprintf() ?

Yes, thanks. Finger memory making me type letters.

> snprintf() requires one more parameter (size of the target buffer) and
> does *not* return the number of actually written characters when
> buffer is too small.

snprintf is, in fact, what one usually wants to avoid making assumptions
about available space (hence my urge to type it!) but the pattern
becomes more complex in portable code because you can't write this:

while (cp < ep) cp += snprintf(cp, ep - cp, "%s", whatever);

because the construction of the pointer (and the subsequent comparison)
are undefined. Once the pattern gets more complicated, other options
start to look simpler.

--
Ben.

DFS <nospam@dfs.com> writes:
>On 8/10/2021 6:22 PM, Bart wrote:
>> On 10/08/2021 23:08, DFS wrote:
>>> On 8/10/2021 2:41 PM, Scott Lurndal wrote:
>>
>>>> I was suggesting that the compiler could have just
>>>> stored a 160k string in RO storage and called puts
>>>> with a pointer to it.   There is no need to construct
>>>> it at runtime.
>>>>
>>>> The entire program would reduce to a single call
>>>> to puts with a compiler generated constant string.
>>>
>>> Gotcha.
>>>
>>> I just noticed something in my program.  Using option 2 above, the
>>> version compiled by tcc crashes when the value in line 3 is large
>>> (1027424).  The version compiled by gcc doesn't crash.
>>>
>>> Is that a stack overflow issue?
>>>
>>
>> Yes, you're using VLAs, (maybe in option 1 too if longword and tcols are
>> not compile-time constants).
>
>They're not. Longword is the longest word (1 to 31) in a result set,
>and tcols is the width of your terminal at the time you do the search.
>
>Here's the app: https://imgur.com/a/cQdvAeM
>
>
>
>> Typical stack size is a few MB. It seems the default stack size of tcc
>> is smaller than of gcc**. tcc crashes with this:
>>
>>     int n=2000000;
>>     char str[n];
>>     memset(str,0,n);
>>
>> but gcc doesn't, until you change n to 4000000. If I dump the two
>> executables, then the gcc one contains this:
>>
>>   Stack reserve:    2097152
>>   Stack commit:     4096
>>
>> tcc's has:
>>
>>   Stack reserve:    1048576
>>   Stack commit:     4096
>>
>> There are probably ways of increasing the stack size, but better not to
>> use VLAs for arrays of this size. (Use static arrays or allocate on the
>> heap.)
>
>
>Thanks. I created a static array[10_000_000] outside the function, and
>it handled large results sets just fine. But another issue popped up,
>using option 2, which concatenates words one by one into that static
>array, then does one puts() at the end.
>
>Turns out it's VERY slow for large result sets.

strcat is almost never the right interface to use. It needs
to scan the entire string to find the terminal nul-byte before
appending. As the string gets longer, each strcat takes longer
than the one before.

Just keep a pointer to the next element and increment the
pointer each time you add a new element.

Michael S <already5chosen@yahoo.com> writes:
>On Wednesday, August 11, 2021 at 11:34:16 AM UTC+3, anti...@math.uni.wroc.pl wrote:

>
>strcat() should have been deprecated in 1989 with replacement that returns something potentially useful, e.g. pointer to
>termination character of result string or length of result string. Or return nothing, which still would be an improvement.
>
>But committees have their own logic.

Having been a member of those committees for a decade,
I'll point out that deprecating or changing the semantics of strcat
would have broken vast amounts of existing, functioning
and useful code.

Secondly, as pointed out in the thread, the function snprintf
is a suitable substitute.

On Wednesday, August 11, 2021 at 4:55:41 PM UTC+3, Scott Lurndal wrote:
> Michael S <already...@yahoo.com> writes:
> >On Wednesday, August 11, 2021 at 11:34:16 AM UTC+3, anti...@math.uni.wroc.pl wrote:
>
> >
> >strcat() should have been deprecated in 1989 with replacement that returns something potentially useful, e.g. pointer to
> >termination character of result string or length of result string. Or return nothing, which still would be an improvement.
> >
> >But committees have their own logic.
> Having been a member of those committees for a decade,
> I'll point out that deprecating or changing the semantics of strcat

For me, deprecation does not mean *immediate* removal. For me, it mean that we threaten to remove a function in 15 years time and are actually removing it after 30 years. Or never. But in the mean time conforming compilers issue annoying diagnostics.

And, of course, nobody suggest changing semantic without changing name.

> would have broken vast amounts of existing, functioning
> and useful code.
>
> Secondly, as pointed out in the thread, the function snprintf
> is a suitable substitute.

No, sprintf() is more like strcpy(). And snprintf() differs even more.

On Wednesday, August 11, 2021 at 4:29:52 PM UTC+3, Ben Bacarisse wrote:
> Michael S <already...@yahoo.com> writes:
>
> > On Wednesday, August 11, 2021 at 1:23:55 PM UTC+3, Ben Bacarisse wrote:
> >> anti...@math.uni.wroc.pl writes:
> >>
> >> > DFS <nos...@dfs.com> wrote:
> >> <cut>
> >> >> =================================================================
> >> >>
> >> >> //option 1: one puts per line (suggested by bart)
> >> >> int i = 0;
> >> >> char buff[longword+3];
> >> >> char line[tcols];
> >> >> *line = '\0';
> >> >> while(i < matchcnt) {
> >> >> for(int j = 1;j<=maxcols;j++) {
> >> >> sprintf(buff,"%-*s ",longword,matchwords[i++]);
> >> >> strcat(line,buff);
> >> >> }
> >> >> puts(line);
> >> >> *buff = '\0';
> >> >> *line = '\0';
> >> >> }
> >> >>
> >> >> =================================================================
> >> >>
> >> >> //option 2: one big string, one puts (per Lurndal)
> >> >> static char line[10000000]; //declared outside the func
> >> >>
> >> >> int i = 0;
> >> >> char buff[longword+3];
> >> >> *line = '\0';
> >> >> while(i < matchcnt) {
> >> >> for(int j = 1;j<=maxcols;j++) {
> >> >> sprintf(buff,"%-*s ",longword,matchwords[i++]);
> >> >> strcat(line,buff);
> >> > ^^^^^^^^^^^^^^^^^^
> >> >> }
> >> >> *buff = '\0';
> >> >> strcat(line,"\n");
> >> >> }
> >> >> puts(line);
> >> >>
> >> >> =================================================================
> >> >
> >> > The 'strcat' in a loop is classic antipattern: it causes quadratic
> >> > complexity to to repeated scanning for end of 'line'. Use something
> >> > like
> >> >
> >> > char * cp = line;
> >> > .....
> >> > strcat(cp, buff);
> >> > cp += strlen(buff);
> >> > ....
> >> ... or get the length first and use memcpy. But my favourite is
> >>
> >> cp += snprintf(cp, "%s", whatever);
> >>
> >> --
> >> Ben.
> >
> > Don't you mean sprintf() ?
> Yes, thanks. Finger memory making me type letters.
> > snprintf() requires one more parameter (size of the target buffer) and
> > does *not* return the number of actually written characters when
> > buffer is too small.
> snprintf is, in fact, what one usually wants to avoid making assumptions
> about available space (hence my urge to type it!) but the pattern
> becomes more complex in portable code because you can't write this:
>
> while (cp < ep) cp += snprintf(cp, ep - cp, "%s", whatever);
>
> because the construction of the pointer (and the subsequent comparison)
> are undefined. Once the pattern gets more complicated, other options
> start to look simpler.
>
> --
> Ben.

The code below is what I have in majority of my embedded projects.
May be, not 100% portable, by I don't care even about 25% portability. If it works on 1-2-3-4 targets that I care about, I am satisfied.
The purpose of my_pritntf() is to prevent buffer overflows (when used in code patterns similar to one you illustrated above) rather than to always output something meaningful.
For systems in question, it tends to be used in "nice to have" parts like telnet and web interfaces that are mostly used during development. For core functionality I try to impose anti-Doug-McIlroy principles, i.e. avoid both text inputs and text outputs. Not 100% successfully, last years one client in one small project insisted on JASON-based main COMM protocol, but that's a rare exception.

#include <stdio.h>
#include <limits.h>
#include <stdarg.h>

#include "my_snprintf.h"

// my_snprintf - Write formatted output to sized buffer
// my_snprintf is similar to snprintf() with following modifications
// 1. Argument n is signed. For n <= 0 the function does nothing and returns 0
// 2. Return value is always a number of characters that have been into s,
// not counting the terminating null character.
// The rest of description applies to case of positive n.
// Unlike snprintf(), if an encoding error occurs, a 0 is returned and
// the terminating null character is written to s[0].
// Unlike snprintf(), if n had not been sufficiently large, a value of n-1
// is returned and the terminating null character is written to s[n-1].
int
my_snprintf(char * s, ptrdiff_t n, const char * format, ...)
{ if (n <= 0)
return 0;
if (n > INT_MAX)
n = INT_MAX;

va_list args;
va_start(args, format);
int ret = vsnprintf(s, n, format, args);
if (ret < 0)
{ // encoding error.
// since our code uses no UNICODE, it should never happen, but let's handle it nevertheless
s[0] = 0; // may be, unnecessary
return 0;
}

if (ret >= n) {
s[n-1] = 0; // most likely unnecessary
return n-1;
}

return ret;
}

On Wednesday, 11 August 2021 at 14:52:54 UTC+1, Scott Lurndal wrote:
>
> strcat is almost never the right interface to use. It needs
> to scan the entire string to find the terminal nul-byte before
> appending. As the string gets longer, each strcat takes longer
> than the one before.
>
> Just keep a pointer to the next element and increment the
> pointer each time you add a new element.
>
Most strings are short. Building up a url with strcat is not going to
stress a 3GHz machine. If the strings become huge then, yes, you
need to look at more efficient ways of concatenating them.

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>On Wednesday, 11 August 2021 at 14:52:54 UTC+1, Scott Lurndal wrote:
>>
>> strcat is almost never the right interface to use. It needs
>> to scan the entire string to find the terminal nul-byte before
>> appending. As the string gets longer, each strcat takes longer
>> than the one before.
>>
>> Just keep a pointer to the next element and increment the
>> pointer each time you add a new element.
>>
>Most strings are short. Building up a url with strcat is not going to
>stress a 3GHz machine. If the strings become huge then, yes, you
>need to look at more efficient ways of concatenating them.

Building it with snprintf() will be far more flexible and efficient.

Every cycle matters.

On 11/08/2021 16:06, Scott Lurndal wrote:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>> On Wednesday, 11 August 2021 at 14:52:54 UTC+1, Scott Lurndal wrote:
>>>
>>> strcat is almost never the right interface to use. It needs
>>> to scan the entire string to find the terminal nul-byte before
>>> appending. As the string gets longer, each strcat takes longer
>>> than the one before.
>>>
>>> Just keep a pointer to the next element and increment the
>>> pointer each time you add a new element.
>>>
>> Most strings are short. Building up a url with strcat is not going to
>> stress a 3GHz machine. If the strings become huge then, yes, you
>> need to look at more efficient ways of concatenating them.
>
> Building it with snprintf() will be far more flexible and efficient.
>
> Every cycle matters.
>

Start with this:

char str[100];
char* s;

Then a loop like this (all unoptimised code to stop it being optimised
out of existence):

for (int i=0; i<10000000; ++i) {
strcpy(str,"one ");
strcat(str,"two ");
strcat(str,"three ");
strcat(str,"four ");
strcat(str,"five");
}
puts(str);

took 1 second (on my Windows PC running tcc). If use sprintf():

for (int i=0; i<10000000; ++i) {
s=str;
s+=sprintf(s,"%s","one ");
s+=sprintf(s,"%s","two ");
s+=sprintf(s,"%s","three ");
s+=sprintf(s,"%s","four ");
sprintf(s,"%s","five");
}
puts(s);

then it takes 5.5 seconds. With snprintf() as you suggest, it takes 6.1
seconds. I thought you said every cycle matters?

These all write into the same string. If each iteration uses a newly
allocated 100-char string, then the strcat loop takes 2.2 seconds, and
both forms of sprintf take something over 7 seconds.

If I take the second loop above, and write the string directly (so not
using "%s"), then it makes no difference; it's not the formatting that
takes the extra time, not for %s anyway, it must be other overheads.

Bart <bc@freeuk.com> writes:
>On 11/08/2021 16:06, Scott Lurndal wrote:
>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>> On Wednesday, 11 August 2021 at 14:52:54 UTC+1, Scott Lurndal wrote:
>>>>
>>>> strcat is almost never the right interface to use. It needs
>>>> to scan the entire string to find the terminal nul-byte before
>>>> appending. As the string gets longer, each strcat takes longer
>>>> than the one before.
>>>>
>>>> Just keep a pointer to the next element and increment the
>>>> pointer each time you add a new element.
>>>>
>>> Most strings are short. Building up a url with strcat is not going to
>>> stress a 3GHz machine. If the strings become huge then, yes, you
>>> need to look at more efficient ways of concatenating them.
>>
>> Building it with snprintf() will be far more flexible and efficient.
>>
>> Every cycle matters.
>>
>
>
>Start with this:

No thanks. I've enough to do writing real working production code.

Bart <bc@freeuk.com> wrote:
> On 09/08/2021 09:29, Michael S wrote:
> > On Monday, August 9, 2021 at 3:03:15 AM UTC+3, DFS wrote:
> >> On 8/8/2021 6:30 PM, Michael S wrote:
> >>
> >>> Bart and DFS are unique people with unique capabilities. DFS more so,
> >> What are you babbling about?
> >
> > Your shared love to strange tools that wouldn't in top#5 list of choice of professional and likely not in top#10.
>
> You just don't get it.
>
> When I drive to the shops I like to use my hatchback, I don't need a
> 40-ton truck, or a 747, which are how big and cumbersome those
> professional tools appear to me. (And if younger I'd jump on my bike.)
>
> Who cares about the top 10 anyway? Where was the top 10 when I needed a
> tiny, fast HLL language for my 8-bit micros which actually ran ON those
> same micros? I've used my own languages ever since.
>
> And when I have to play with C, I prefer my own small C compiler; you
> know, that one with the faster printf than gcc/tdm.

I like small and fast programs. But here it looks like
you really want to mislead other folks. First, what
you are measuring is speed of Windows console. IIUC
correctly what you wrote in your case Windows console
is fast enough: if you read printed text time spent
in console will be negligible compared to time spent
reading. And if console were too slow simple way
to solve problem is to get faster console: AFAICS
other folks pointed out that Microsoft provides
faster console and consoles from third party
(Cygwin and Msys) are faster too.

Second, any semi-decent tool to measure exection
time will tell you that time spent in your program
is negligible and basically 100% of time is
spent in Windows console. But instead of telling
that Windows console has a quirk which make it
much slower with one way of driving it (which
happen to be used by your gcc/tdm package) you
spin it as "gcc is slower than tcc".

Third, every programmer must understand importance
of being precise: programmer job is tell computer
what to do and if programer is not precise
enough computer will reject the task or do wrong
thing. Other explaned you difference between
gcc and package that you get. This distinction
matters because it tells you where to report
problem. In your case, if you honestly do
not know which part is responsible, then it
is resonable to report problems to whoever is
behind TDM project. OTOH, if you think that
problem is in core gcc, then it is resonable
to report it to gcc folks (since your version
is quite old you may get answer "fixed in
newer release", but that is another topic).
If you identify specific library or tool it
makes sense to report problem to authors
of problematic components.

If report to gcc folks problem with Windows console,
do not expect nice answer: it is not part that
they supply.

Forth, you are jumping to conclusion: you do not
know why printf in your gcc/tdm package is doing
output in the specific way. It may be a bug.
But to do this requires some effort, so there
may be deeper reason. Namely, Windows console
is quirky, and "slow" way may be reasonable
way to get correct output in all cases. I mean,
there are bugs where simple fix is to force
"slow" mode of operation. If "slow" mode is
fast enough, then this may be resonable fix
(fast enoug correct program is much better than
much faster incorrect one). Note: I do not have
specific info, but AFAICS you too do not know why
this is done. Before knowing reasons claim like
"printf gcc/tdm in slower" are jumping to conclusion.

--
Waldek Hebisch

On 11/08/2021 17:14, Scott Lurndal wrote:
> Bart <bc@freeuk.com> writes:
>> On 11/08/2021 16:06, Scott Lurndal wrote:
>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>>> On Wednesday, 11 August 2021 at 14:52:54 UTC+1, Scott Lurndal wrote:
>>>>>
>>>>> strcat is almost never the right interface to use. It needs
>>>>> to scan the entire string to find the terminal nul-byte before
>>>>> appending. As the string gets longer, each strcat takes longer
>>>>> than the one before.
>>>>>
>>>>> Just keep a pointer to the next element and increment the
>>>>> pointer each time you add a new element.
>>>>>
>>>> Most strings are short. Building up a url with strcat is not going to
>>>> stress a 3GHz machine. If the strings become huge then, yes, you
>>>> need to look at more efficient ways of concatenating them.
>>>
>>> Building it with snprintf() will be far more flexible and efficient.
>>>
>>> Every cycle matters.
>>>
>>
>>
>> Start with this:
>
> No thanks. I've enough to do writing real working production code.
>

And giving bad, untested advice...

On Wednesday, 11 August 2021 at 16:06:38 UTC+1, Scott Lurndal wrote:
>
> Building it with snprintf() will be far more flexible and efficient.
>
> Every cycle matters.
>
People often talk about "bottlenecks" in code. However for a program
which launches, performs a calculation, returns a result, and terminates,
there are no bottlenecks. Every cycle is equal. However not every line of
code is equal. Typically some lines will be executed millions or even
billions of times, other lines only once.

But a lot of programs don't fit that model. They spend a lot of time idling,
waiting for input, and then occasionally present the user with a lag when a
long operation is attempted. Efficiency only matters in the laggy code,
there's no point in optimising code which executes in under just noticeable time.

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>On Wednesday, 11 August 2021 at 16:06:38 UTC+1, Scott Lurndal wrote:
>>
>> Building it with snprintf() will be far more flexible and efficient.
>>
>> Every cycle matters.
>>
>People often talk about "bottlenecks" in code. However for a program
>which launches, performs a calculation, returns a result, and terminates,
>there are no bottlenecks. Every cycle is equal. However not every line of
>code is equal. Typically some lines will be executed millions or even
>billions of times, other lines only once.
>
>But a lot of programs don't fit that model. They spend a lot of time idling,
>waiting for input, and then occasionally present the user with a lag when a
>long operation is attempted. Efficiency only matters in the laggy code,
>there's no point in optimising code which executes in under just noticeable time.

You are discounting the fact that prodiction code is generally not running
stand-alone bare-metal. In which case there will be other
processes/threads/guests waiting for the CPU, so every cycle matters.

On 8/11/2021 8:47 AM, Bart wrote:
>
> (all unoptimised code to stop it being optimised
> out of existence):
> ...
> then it takes 5.5 seconds. With snprintf() as you suggest, it takes 6.1
> seconds. I thought you said every cycle matters?
>

^^^ Timing "unoptimised" code and then talking about "cycles". This does
not make a single shred of sense.

--
Best regards,
Andrey Tarasevich

On 8/11/2021 4:34 AM, antispam@math.uni.wroc.pl wrote:

> The 'strcat' in a loop is classic antipattern: it causes quadratic
> complexity to to repeated scanning for end of 'line'. Use something
> like
>
> char * cp = line;
> .....
> strcat(cp, buff);
> cp += strlen(buff);
> ....
>

From other posts:

> Bacarisse: "my favourite is cp += snprintf(cp, "%s", whatever);"
> (he meant to say sprintf)

> Lurndal: "Building it with snprintf() will be far more flexible and
> efficient."

build string, in seconds
----------------------------- build +
antispam sprintf()/ print to
substring matches strcat as above snprintf() screen

catt 91 0.036 0.036 0.036 0.037
cat 3710 0.067 0.038 0.038 0.129
ca 22793 1.423 0.044 0.052 0.657
c 128689 53.591 0.084 0.139 4.437
e 252896 207.782 0.132 0.238 8.598

Much better! Thanks for the suggestions.

built on Win10, using Mingw-w64 GCC
http://mingw-w64.org/doku.php

which I got via
https://github.com/skeeto/w64devkit/releases/tag/v1.8.0

run in cmd.exe shell inside ConEmu

$ prog wordlist.txt option1234 (for dev and testing)

===========================================================================
//print matching words in columns of the same size, with no line
// wrapping in middle of word

//array large enough to output 370K words of length 31
static char line[12000000];

void showresults(char *matchwords[], int matchcnt, int stropt) {
//get longest word in results
int longword = 0;
for(int i=0;i<matchcnt;i++) {
int thislen = strlen(matchwords[i]);
if(thislen>longword) {longword=thislen; }
}
//get # of columns visible onscreen
int tcols = gettcols();
//get max number of columns to print on each line
//add 2 to longword to account for spaces
int maxcols = ((int)(tcols/(longword+2)));
//build one big string, do one puts
//fastest but requires huge array alloc
int i = 0;
char buff[longword+3];
*line = '\0';
char *cp = line;
while(i < matchcnt) {
for(int j = 1;j<=maxcols;j++) {

//add word to buffer
sprintf(buff,"%-*s ",longword,matchwords[i++]);

//add buffer to string

//strcat
if(stropt == 1) {
strcat(line,buff);
}

//antispam/strlen
else if(stropt == 2) {
strcat(cp, buff);
cp += strlen(buff);
}

//sprintf
else if(stropt == 3) {
cp += sprintf(cp, "%s", buff);
}

//snprintf
else if(stropt == 4) {
cp += snprintf(cp, sizeof buff, "%s", buff);
}

}

//reset buffer
*buff = '\0';

//add newline
if(stropt == 1) //strcat
strcat(line,"\n");
else
cp += sprintf(cp, "\n");

}
//print to screen
puts(line);

//show string builder option
char *stropts[] = {"strcat","antispam/strlen","sprintf","snprintf"};
printf("%s\n",stropts[stropt-1]);

}
===========================================================================

scott@slp53.sl.home (Scott Lurndal) writes:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>On Wednesday, 11 August 2021 at 14:52:54 UTC+1, Scott Lurndal wrote:
>>>
>>> strcat is almost never the right interface to use. It needs
>>> to scan the entire string to find the terminal nul-byte before
>>> appending. As the string gets longer, each strcat takes longer
>>> than the one before.
>>>
>>> Just keep a pointer to the next element and increment the
>>> pointer each time you add a new element.
>>>
>>Most strings are short. Building up a url with strcat is not going to
>>stress a 3GHz machine. If the strings become huge then, yes, you
>>need to look at more efficient ways of concatenating them.
>
> Building it with snprintf() will be far more flexible and efficient.
>
> Every cycle matters.

As Bart's measurements indicate, snprintf() is likely to have
substantial overhead, probably because it has to parse its format
string. I wouldn't assume snprintf() is going to be faster than
strcat() without measuring it for the specific data I'm working with.

The non-standard strlcat() returns the initial length of the destination
plus the length of the source, which can be used to find the end of the
copyied string without re-scanning. (It can be a little tricky to get
the compilation command right on some systems.)

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips
void Void(void) { Void(); } /* The recursive call of the void */

On 11/08/2021 19:01, Andrey Tarasevich wrote:
> On 8/11/2021 8:47 AM, Bart wrote:
>>
>> (all unoptimised code to stop it being optimised out of existence):
>> ...
>> then it takes 5.5 seconds. With snprintf() as you suggest, it takes
>> 6.1 seconds. I thought you said every cycle matters?
>>
>
> ^^^ Timing "unoptimised" code and then talking about "cycles". This does
> not make a single shred of sense.
>

The code we're talking about is functions in a binary library which
presumably are already optimised.

If I turn on optimisation for my simple loops, then all timings become
0.0 seconds; what on earth use is that?

Perhaps you'd like to provide a better test program then? One which
tests the efficacy of strcat vs snprintf, rather than a how smart a
compiler is in making short work of a pointless, repetitive loop.

In a real application, the strings may not be simple literals of a known
length, may not be so amenable to inlining, and may not be in a simple
loop like this and where results are discarded.

DFS <nospam@dfs.com> writes:
>On 8/11/2021 4:34 AM, antispam@math.uni.wroc.pl wrote:
>
>
>> The 'strcat' in a loop is classic antipattern: it causes quadratic
>> complexity to to repeated scanning for end of 'line'. Use something
>> like
>>
>> char * cp = line;
>> .....
>> strcat(cp, buff);
>> cp += strlen(buff);
>> ....
>>
>
> From other posts:
>
>> Bacarisse: "my favourite is cp += snprintf(cp, "%s", whatever);"
>> (he meant to say sprintf)
>
>> Lurndal: "Building it with snprintf() will be far more flexible and
>> efficient."
>
>
>
> build string, in seconds
> ----------------------------- build +
> antispam sprintf()/ print to
>substring matches strcat as above snprintf() screen
>
>catt 91 0.036 0.036 0.036 0.037
>cat 3710 0.067 0.038 0.038 0.129
>ca 22793 1.423 0.044 0.052 0.657
>c 128689 53.591 0.084 0.139 4.437
>e 252896 207.782 0.132 0.238 8.598
>
>
>Much better! Thanks for the suggestions.
>
>
>built on Win10, using Mingw-w64 GCC
>http://mingw-w64.org/doku.php
>
>which I got via
>https://github.com/skeeto/w64devkit/releases/tag/v1.8.0
>
>run in cmd.exe shell inside ConEmu
>
>$ prog wordlist.txt option1234 (for dev and testing)
>
>===========================================================================
>//print matching words in columns of the same size, with no line
>// wrapping in middle of word
>
>//array large enough to output 370K words of length 31
>static char line[12000000];
>
>void showresults(char *matchwords[], int matchcnt, int stropt) {
>

I was thinking more along the lines of this:
static char line[12000000];

/**
* Catenate the words from 'matchwords' into 'line', computing the
* word length of the longest single word along the way.
*
* @param matchwords A vector of character pointers, one for each word
* @param matchcnt The number of entries in the matchwords vector.
*/
void
showresults(char **matchwords, size_t matchcnt)
{ size_t longest_word = 0ul;
char *lp = line;
char *elp = &line[sizeof(line)];

for(size_t i = 0ul; i < matchcount; i++) {
char *cp = *matchwords++;
size_t len = 0ul;
while ((*cp != '\0') && (lp < elp)) {
len++;
*lp++ = *cp++;
}
longest_word = max(longest_word, len);
}

if (lp < elp) *lp++ = '\0';
else line[sizeof(line)-1] = '\0';

puts(line);
}

It will silently truncate the output string if 'line'
isn't large enough to collect all the words in 'matchwords'.

The implementation of max is left to the student.

On 11/08/2021 18:19, antispam@math.uni.wroc.pl wrote:
> Bart <bc@freeuk.com> wrote:

>> And when I have to play with C, I prefer my own small C compiler; you
>> know, that one with the faster printf than gcc/tdm.
>
> I like small and fast programs. But here it looks like
> you really want to mislead other folks.

I gave timings for bcc, tcc, gcc**, clang**, CL, DMC and lccwin.

There was a mixup over the ones marked ** which is explained below. But
some gcc/clang versions were much slower. lccwin was in between.

> First, what
> you are measuring is speed of Windows console. IIUC
> correctly what you wrote in your case Windows console
> is fast enough: if you read printed text time spent
> in console will be negligible compared to time spent
> reading. And if console were too slow simple way
> to solve problem is to get faster console: AFAICS
> other folks pointed out that Microsoft provides
> faster console and consoles from third party
> (Cygwin and Msys) are faster too.

That's not really relevant. All compilers were running the same program
under the same OS and with the same, bog-standard MS Command Prompt.

If one compiler exhibits much slower behaviour, then it's odd to suspect
the console first.

> Second, any semi-decent tool to measure exection
> time will tell you that time spent in your program
> is negligible and basically 100% of time is
> spent in Windows console. But instead of telling
> that Windows console has a quirk which make it
> much slower with one way of driving it (which
> happen to be used by your gcc/tdm package) you
> spin it as "gcc is slower than tcc".

DFS has observed the effect; I have observed it. Other who haven't
observed it haven't been using the same platform or the right compilers.

However I've just done another test, and it is only one specific gcc and
clang installation which has that problem, at least, of the ones I have.

So:

gcc/tdm 9.2.0 OK
clang/LLVM 11.0.0 OK
gcc/11.2.0 Slow, both of these from Winlib link
clang 12.0.1 Slow

The winlib gcc installs itself in such a way that it becomes the default
'gcc' version, and also confusingly provides clang.exe which then the
default 'clang'.

I'm now upgraded my gcc/tdm to 10.3.0, and that is slow too:

gcc/tdm 10.3.0 Slow (there is no clang)

So my comments about gcc/tdm having the problem, although made
erroneously, are actually correct.

> Third, every programmer must understand importance
> of being precise: programmer job is tell computer
> what to do and if programer is not precise
> enough computer will reject the task or do wrong
> thing. Other explaned you difference between
> gcc and package that you get. This distinction
> matters because it tells you where to report
> problem. In your case, if you honestly do
> not know which part is responsible, then it
> is resonable to report problems to whoever is
> behind TDM project.

If you look at my first post on the subject (8-8-21 15:41 BST) it was to
confirm what DFS had observed, and I suggested a workaround.

But everyone seems very keen to challenge what I'd said.

> OTOH, if you think that
> problem is in core gcc, then it is resonable
> to report it to gcc folks (since your version
> is quite old you may get answer "fixed in
> newer release", but that is another topic).
> If you identify specific library or tool it
> makes sense to report problem to authors
> of problematic components.

I really have no idea who's reponsible for what. And I don't care as
it's not my product so not my headache.

(It's also, now, exhibited on two separate builds: gcc/tdm 10.3.0, from
FSF Inc, and gcc 11.2.0 from chap called Brecht Sanders.)

> Forth, you are jumping to conclusion: you do not
> know why printf in your gcc/tdm package is doing
> output in the specific way.

No, I don't, but that's what it does.

On 11/08/2021 19:54, Scott Lurndal wrote:
> DFS <nospam@dfs.com> writes:
>> On 8/11/2021 4:34 AM, antispam@math.uni.wroc.pl wrote:
>>
>>
>>> The 'strcat' in a loop is classic antipattern: it causes quadratic
>>> complexity to to repeated scanning for end of 'line'. Use something
>>> like
>>>
>>> char * cp = line;
>>> .....
>>> strcat(cp, buff);
>>> cp += strlen(buff);
>>> ....
>>>
>>
>> From other posts:
>>
>>> Bacarisse: "my favourite is cp += snprintf(cp, "%s", whatever);"
>>> (he meant to say sprintf)
>>
>>> Lurndal: "Building it with snprintf() will be far more flexible and
>>> efficient."
>>
>>
>>
>> build string, in seconds
>> ----------------------------- build +
>> antispam sprintf()/ print to
>> substring matches strcat as above snprintf() screen
>>
>> catt 91 0.036 0.036 0.036 0.037
>> cat 3710 0.067 0.038 0.038 0.129
>> ca 22793 1.423 0.044 0.052 0.657
>> c 128689 53.591 0.084 0.139 4.437
>> e 252896 207.782 0.132 0.238 8.598
>>
>>
>> Much better! Thanks for the suggestions.
>>
>>
>> built on Win10, using Mingw-w64 GCC
>> http://mingw-w64.org/doku.php
>>
>> which I got via
>> https://github.com/skeeto/w64devkit/releases/tag/v1.8.0
>>
>> run in cmd.exe shell inside ConEmu
>>
>> $ prog wordlist.txt option1234 (for dev and testing)
>>
>> ===========================================================================
>> //print matching words in columns of the same size, with no line
>> // wrapping in middle of word
>>
>> //array large enough to output 370K words of length 31
>> static char line[12000000];
>>
>> void showresults(char *matchwords[], int matchcnt, int stropt) {
>>
>
> I was thinking more along the lines of this:
>
> static char line[12000000];
>
> /**
> * Catenate the words from 'matchwords' into 'line', computing the
> * word length of the longest single word along the way.
> *
> * @param matchwords A vector of character pointers, one for each word
> * @param matchcnt The number of entries in the matchwords vector.
> */
> void
> showresults(char **matchwords, size_t matchcnt)
> {
> size_t longest_word = 0ul;
> char *lp = line;
> char *elp = &line[sizeof(line)];
>
> for(size_t i = 0ul; i < matchcount; i++) {
> char *cp = *matchwords++;
> size_t len = 0ul;
> while ((*cp != '\0') && (lp < elp)) {
> len++;
> *lp++ = *cp++;
> }
> longest_word = max(longest_word, len);
> }
>
> if (lp < elp) *lp++ = '\0';
> else line[sizeof(line)-1] = '\0';
>
> puts(line);
> }
>
> It will silently truncate the output string if 'line'
> isn't large enough to collect all the words in 'matchwords'.
>
> The implementation of max is left to the student.
>

Oh, I see you managed to make time for this, then!

I hadn't even asked you to write any code, just to look at my results.

I can take it then that my observations were on the mark since you
aren't interested in refuting them.

On 8/11/2021 11:47 AM, Bart wrote:

> Start with this:
>
>     char str[100];
>     char* s;
>
> Then a loop like this (all unoptimised code to stop it being optimised
> out of existence):
>
>   for (int i=0; i<10000000; ++i) {
>       strcpy(str,"one ");
>       strcat(str,"two ");
>       strcat(str,"three ");
>       strcat(str,"four ");
>       strcat(str,"five");
>   }
>   puts(str);
>
>
> took 1 second (on my Windows PC running tcc). If use sprintf():
>
>   for (int i=0; i<10000000; ++i) {
>       s=str;
>       s+=sprintf(s,"%s","one ");
>       s+=sprintf(s,"%s","two ");
>       s+=sprintf(s,"%s","three ");
>       s+=sprintf(s,"%s","four ");
>          sprintf(s,"%s","five");
>   }
>   puts(s);

Did you mean to leave off the s+= in the last line?

> then it takes 5.5 seconds. With snprintf() as you suggest, it takes 6.1
> seconds. I thought you said every cycle matters?

FWIW: also on Windows

compiled with tcc
strcat : 0.7s
sprintf: 6.3s

compiled with Mingw-w64 GCC
strcat : 0.4s
sprintf: 4.4s

Bart <bc@freeuk.com> writes:
>On 11/08/2021 19:54, Scott Lurndal wrote:

>I can take it then that my observations were on the mark since you
>aren't interested in refuting them.
>

No, I'm just not interested in you and your silly obsessions.

Bart <bc@freeuk.com> wrote:
> On 11/08/2021 18:19, antispam@math.uni.wroc.pl wrote:
> > Bart <bc@freeuk.com> wrote:
>
> >> And when I have to play with C, I prefer my own small C compiler; you
> >> know, that one with the faster printf than gcc/tdm.
> >
> > I like small and fast programs. But here it looks like
> > you really want to mislead other folks.
>
> I gave timings for bcc, tcc, gcc**, clang**, CL, DMC and lccwin.
>
> There was a mixup over the ones marked ** which is explained below. But
> some gcc/clang versions were much slower. lccwin was in between.
>
>
> > First, what
> > you are measuring is speed of Windows console. IIUC
> > correctly what you wrote in your case Windows console
> > is fast enough: if you read printed text time spent
> > in console will be negligible compared to time spent
> > reading. And if console were too slow simple way
> > to solve problem is to get faster console: AFAICS
> > other folks pointed out that Microsoft provides
> > faster console and consoles from third party
> > (Cygwin and Msys) are faster too.
>
> That's not really relevant. All compilers were running the same program
> under the same OS and with the same, bog-standard MS Command Prompt.
>
> If one compiler exhibits much slower behaviour, then it's odd to suspect
> the console first.

Why odd. On my Linux machine running program that you
provided I get:

time ./b1
<lot of output>
1234567890 1234567890 1234567890 1234567890 1234567890
real 0m0.282s
user 0m0.012s
sys 0m0.000s

That says that program took 12ms CPU time to run, while real time
between start and finish is 282ms. It is odd to not notice that
most real time is spent _outside_ program. And the clear suspect
for causing bigger real time is console. AFAIK Windows has also
tools that allow you to see this.

And even if you have no tools it is rater easy to estimate time
spent in your program, and even 282ms that I see is much bigger
than any resonable estimate of runtime (and 3s that you reported
is really way off).

And simple way to isolate console effects is output to a file,
you know that this is much faster, so you really have no
excuse.

> > Second, any semi-decent tool to measure exection
> > time will tell you that time spent in your program
> > is negligible and basically 100% of time is
> > spent in Windows console. But instead of telling
> > that Windows console has a quirk which make it
> > much slower with one way of driving it (which
> > happen to be used by your gcc/tdm package) you
> > spin it as "gcc is slower than tcc".
>
> DFS has observed the effect; I have observed it. Other who haven't
> observed it haven't been using the same platform or the right compilers.

The point is what "the effect" is! If you mean execution
time of your program, then without any measurement I know
that it is negligile. If you measured, you will know to.
Or rather, you already know, but you prefer doing propaganda.

Put it differently: when you throw pathological program at
gcc and gcc takes long time to compile it, this is gcc problem.
When library bundled with your gcc install sends output to
window console that causes long execution time in console
that is gcc problem. When your compiler has trouble
with some code this is also gcc problem, without gcc
people would write simpler code that your compiler can
handle.

Note: I do not dispute your observations, but what they
mean.
> > Third, every programmer must understand importance
> > of being precise: programmer job is tell computer
> > what to do and if programer is not precise
> > enough computer will reject the task or do wrong
> > thing. Other explaned you difference between
> > gcc and package that you get. This distinction
> > matters because it tells you where to report
> > problem. In your case, if you honestly do
> > not know which part is responsible, then it
> > is resonable to report problems to whoever is
> > behind TDM project.
>
> If you look at my first post on the subject (8-8-21 15:41 BST) it was to
> confirm what DFS had observed, and I suggested a workaround.
>
> But everyone seems very keen to challenge what I'd said.

DFS can be excused as he apparently does not know what
happened. You know, but prefer misleading formulation.

> > OTOH, if you think that
> > problem is in core gcc, then it is resonable
> > to report it to gcc folks (since your version
> > is quite old you may get answer "fixed in
> > newer release", but that is another topic).
> > If you identify specific library or tool it
> > makes sense to report problem to authors
> > of problematic components.
>
> I really have no idea who's reponsible for what. And I don't care as
> it's not my product so not my headache.

If you do not care, then why so much fuss? Here you are responding
to DFS, but there were many threads started by you.

> (It's also, now, exhibited on two separate builds: gcc/tdm 10.3.0, from
> FSF Inc, and gcc 11.2.0 from chap called Brecht Sanders.)
>
> > Forth, you are jumping to conclusion: you do not
> > know why printf in your gcc/tdm package is doing
> > output in the specific way.
>
> No, I don't, but that's what it does.
>

--
Waldek Hebisch

On 11/08/2021 17:47, Bart wrote:
> On 11/08/2021 16:06, Scott Lurndal wrote:
>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>>> On Wednesday, 11 August 2021 at 14:52:54 UTC+1, Scott Lurndal wrote:
>>>>
>>>> strcat is almost never the right interface to use. It needs
>>>> to scan the entire string to find the terminal nul-byte before
>>>> appending. As the string gets longer, each strcat takes longer
>>>> than the one before.
>>>>
>>>> Just keep a pointer to the next element and increment the
>>>> pointer each time you add a new element.
>>>>
>>> Most strings are short. Building up a url with strcat is not going to
>>> stress a 3GHz machine. If the strings become huge then, yes, you
>>> need to look at more efficient ways of concatenating them.
>>
>> Building it with snprintf() will be far more flexible and efficient.
>>
>> Every cycle matters.
>>
>
>
> Start with this:
>
>     char str[100];
>     char* s;
>
> Then a loop like this (all unoptimised code to stop it being optimised
> out of existence):

As you well know, timing unoptimised code is an utterly pointless
exercise. You need to do something to make sure the operations are
carried out, such as judicious use of volatile, or using "global"
variables rather than local ones. Disabling optimisation is like
comparing the speed of cars while forcing them to remain in first gear.

>
>   for (int i=0; i<10000000; ++i) {
>       strcpy(str,"one ");
>       strcat(str,"two ");
>       strcat(str,"three ");
>       strcat(str,"four ");
>       strcat(str,"five");
>   }
>   puts(str);
>
>
> took 1 second (on my Windows PC running tcc). If use sprintf():
>
>   for (int i=0; i<10000000; ++i) {
>       s=str;
>       s+=sprintf(s,"%s","one ");
>       s+=sprintf(s,"%s","two ");
>       s+=sprintf(s,"%s","three ");
>       s+=sprintf(s,"%s","four ");
>          sprintf(s,"%s","five");
>   }
>   puts(s);
>
> then it takes 5.5 seconds. With snprintf() as you suggest, it takes 6.1
> seconds. I thought you said every cycle matters?
>

<https://godbolt.org/z/954eccfsM>

gcc (and I really mean gcc - no libraries are involved) generates
identical code in both cases, and so I would assume (without testing)
that the speed is the same.

> These all write into the same string. If each iteration uses a newly
> allocated 100-char string, then the strcat loop takes 2.2 seconds, and
> both forms of sprintf take something over 7 seconds.
>
> If I take the second loop above, and write the string directly (so not
> using "%s"), then it makes no difference; it's not the formatting that
> takes the extra time, not for %s anyway, it must be other overheads.