Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

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

Alternative libraries for C, that are efficient

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

Contents

  Alternative libraries for C, that are efficient John Reye <jononanon@googlemail.com> - 2012-04-12 09:01 -0700
    Re: Alternative libraries for C, that are efficient John Reye <jononanon@googlemail.com> - 2012-04-12 09:05 -0700
      Re: Alternative libraries for C, that are efficient ImpalerCore <jadill33@gmail.com> - 2012-04-12 09:38 -0700
        Re: Alternative libraries for C, that are efficient John Reye <jononanon@googlemail.com> - 2012-04-12 11:32 -0700
          Re: Alternative libraries for C, that are efficient James Kuyper <jameskuyper@verizon.net> - 2012-04-12 14:41 -0400
            Re: Alternative libraries for C, that are efficient Willem <willem@toad.stack.nl> - 2012-04-12 18:51 +0000
              Re: Alternative libraries for C, that are efficient nick_keighley_nospam@hotmail.com - 2012-04-13 03:46 -0700
                Re: Alternative libraries for C, that are efficient Willem <willem@toad.stack.nl> - 2012-04-13 14:51 +0000
              Re: Alternative libraries for C, that are efficient Kenneth Brody <kenbrody@spamcop.net> - 2012-04-13 12:38 -0400
                Re: Alternative libraries for C, that are efficient Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-04-15 19:47 +0300
    Re: Alternative libraries for C, that are efficient tom st denis <tom@iahu.ca> - 2012-04-12 09:09 -0700
      Re: Alternative libraries for C, that are efficient John Reye <jononanon@googlemail.com> - 2012-04-12 11:13 -0700
        Re: Alternative libraries for C, that are efficient tom st denis <tom@iahu.ca> - 2012-04-12 18:20 -0700
    Re: Alternative libraries for C, that are efficient Jens Gustedt <jens.gustedt@loria.fr> - 2012-04-12 18:13 +0200
      Re: Alternative libraries for C, that are efficient James Kuyper <jameskuyper@verizon.net> - 2012-04-12 12:47 -0400
      Re: Alternative libraries for C, that are efficient John Reye <jononanon@googlemail.com> - 2012-04-12 11:22 -0700
        Re: Alternative libraries for C, that are efficient Jens Gustedt <jens.gustedt@loria.fr> - 2012-04-13 22:37 +0200
          Re: Alternative libraries for C, that are efficient Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-04-15 20:15 +0300
            Re: Alternative libraries for C, that are efficient Jens Gustedt <jens.gustedt@loria.fr> - 2012-04-15 23:30 +0200
    Re: Alternative libraries for C, that are efficient Ben Pfaff <blp@cs.stanford.edu> - 2012-04-12 09:20 -0700
    Re: Alternative libraries for C, that are efficient Noob <root@127.0.0.1> - 2012-04-12 18:34 +0200
      Re: Alternative libraries for C, that are efficient Kaz Kylheku <kaz@kylheku.com> - 2012-04-12 18:00 +0000
        Re: Alternative libraries for C, that are efficient nick_keighley_nospam@hotmail.com - 2012-04-13 03:50 -0700
      Re: Alternative libraries for C, that are efficient John Reye <jononanon@googlemail.com> - 2012-04-12 11:24 -0700
        Re: Alternative libraries for C, that are efficient Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-04-12 13:08 -0700
    Re: Alternative libraries for C, that are efficient James Kuyper <jameskuyper@verizon.net> - 2012-04-12 12:50 -0400
      Re: Alternative libraries for C, that are efficient John Reye <jononanon@googlemail.com> - 2012-04-12 11:30 -0700
        Re: Alternative libraries for C, that are efficient James Kuyper <jameskuyper@verizon.net> - 2012-04-12 15:55 -0400
    Re: Alternative libraries for C, that are efficient Barry Schwarz <schwarzb@dqel.com> - 2012-04-12 11:41 -0700
      Re: Alternative libraries for C, that are efficient Willem <willem@toad.stack.nl> - 2012-04-12 19:08 +0000
    Re: Alternative libraries for C, that are efficient "BartC" <bc@freeuk.com> - 2012-04-12 21:07 +0100
      Re: Alternative libraries for C, that are efficient James Kuyper <jameskuyper@verizon.net> - 2012-04-12 20:35 -0400
        Re: Alternative libraries for C, that are efficient "BartC" <bc@freeuk.com> - 2012-04-13 11:38 +0100
          Re: Alternative libraries for C, that are efficient James Kuyper <jameskuyper@verizon.net> - 2012-04-13 09:52 -0400
            Re: Alternative libraries for C, that are efficient "BartC" <bc@freeuk.com> - 2012-04-13 17:56 +0100
        Re: Alternative libraries for C, that are efficient Kenneth Brody <kenbrody@spamcop.net> - 2012-04-13 12:56 -0400
          Re: Alternative libraries for C, that are efficient James Kuyper <jameskuyper@verizon.net> - 2012-04-13 14:48 -0400
            Re: Alternative libraries for C, that are efficient Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-04-14 07:22 -0700
    Re: Alternative libraries for C, that are efficient Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-04-12 21:23 -0400
      Re: Alternative libraries for C, that are efficient Quentin Pope <qp19433@hotmail.NOSPAM.com> - 2012-04-13 16:52 +0000
    Re: Alternative libraries for C, that are efficient Jens Gustedt <jens.gustedt@loria.fr> - 2012-04-13 23:24 +0200

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

#19574

John Reye wrote:

> recently I learned that various "standard C library" functions have
> deficiencies in terms of high performance.

"Premature optimization is the root of all evil"

https://en.wikipedia.org/wiki/Program_optimization#When_to_optimize

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

#19577

On 2012-04-12, Noob <root@127.0.0.1> wrote:
> John Reye wrote:
>
>> recently I learned that various "standard C library" functions have
>> deficiencies in terms of high performance.
>
> "Premature optimization is the root of all evil"

If you're designing a programming language, and working with an interpreted
implementation for the time being, is it a case of premature optimization to be
concerned with that the language features will be suitable for compilation?

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

#19610

On Thursday, April 12, 2012 7:00:19 PM UTC+1, Kaz Kylheku wrote:
> On 2012-04-12, Noob <root@127.0.0.1> wrote:
> > John Reye wrote:

<snip>

> > "Premature optimization is the root of all evil"
> 
> If you're designing a programming language, and working with an interpreted
> implementation for the time being, is it a case of premature optimization to be
> concerned with that the language features will be suitable for compilation?

The Extreme Programmers would say so. Their form of Future Blindness precludes thinking of anything beyond passing the current test case. Doing so is Big Design Up Front (BDUF).

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

#19581

On Apr 12, 6:34 pm, Noob <r...@127.0.0.1> wrote:
> John Reye wrote:
> > recently I learned that various "standard C library" functions have
> > deficiencies in terms of high performance.
>
> "Premature optimization is the root of all evil"
>
> https://en.wikipedia.org/wiki/Program_optimization#When_to_optimize

Well implemented interfaces, will "almost automatically" make you
write good code.
But badly designed interfaces, will make you call strlen and all kinds
of other functions that you wouldn't have to call, if the functions-
interfaces had been designed in a better manner.

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

#19590

בתאריך יום חמישי, 12 באפריל 2012 19:24:30 UTC+1, מאת John Reye:
> 
> Well implemented interfaces, will "almost automatically" make you
> write good code.
> But badly designed interfaces, will make you call strlen and all kinds
> of other functions that you wouldn't have to call, if the functions-
> interfaces had been designed in a better manner.
>
There's often a tension between perfomance and ease of use, however.

For instance my options parser allows the programmer to take in a string, typically a file name, from the command line. Command line arguments are modifiable, so the OS has almost certainly copied the data from the console input into a temporary buffer. Then the options parser takes a local copy of the command line arguments. Then it makes another copy when the caller requests the program. So we end up, probably in main, with a char pointer we could have had with a simple ptr = argv[index]; However I made the judgement that it's easier that way. Then you don't have to document that argv must not be modified, or that if the programmer requests two copies of the file name (unlikely) that they are aliases. And how much is all this shuffling about of data in memory likley to impact performance?
 
-- 
The options parser and much more, on my website
http://www.malcolmmclean.site11.com/www

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

#19576

On 04/12/2012 12:01 PM, John Reye wrote:
> Hi,
> 
> recently I learned that various "standard C library" functions have
> deficiencies in terms of high performance.

The only thing you've learned from recent threads in this forum is that
some C standard library functions are specified by the standard to have
less than ideal interfaces. That's not exactly an earth-shattering piece
of news - it's true of almost every library. If you've learned of
significant (or even insignificant but measurable) performance problems
with these functions, you learned of it in some other context.

It's meaningless to talk about the performance of *the* C standard
library. There's no single C standard library - just a standard which
documents what the library does and how to use it, and many different
implementations of that library. Performance is meaningful only when you
specify a particular implementation of that library. Which particular
implementation have you seen bad performance figures for? What were
those figures?

...
> Are these deficiencies _only_ string-related?

No - there are lots of other kinds of minor problems with the C standard
library.

> Is there no good library which I can use for optimal computing?

I think that you can safely assume that no library you've ever heard of,
and no library that you ever will hear of, is perfectly optimal. There's
lots of good sub-optimal libraries out there, including various
implementations of the C standard library.

> Because if I use the "standard C library" I'll end up _not_ using many
> of it's routines.

Most people use only a small portion of the C standard library; there's
nothing unusual about that. I think that what you mean is something
different - you plan on refusing to use many C standard library
functions that could be useful, because you consider them less than optimal.

> Surely there must be a good library somewhere, or do all C programmers
> really carry their own routines with them?

I almost never write my own routines for any purpose for which a C
standard library routine can be made to serve, even if the library
routine is a less-than perfect fit to my desires. The main exception is
that I will often manually inline code that is roughly equivalent to
some of the standard str*() and mem*() functions, especially strtok().
For the other str*() and mem*() functions, I'll usually inline the code
only if I need a pointer to the end of the memory that was processed,
something that the standard library functions don't provide. The
in-lining is generally trivial for most of those functions.

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

#19582

On Apr 12, 6:50 pm, James Kuyper <jameskuy...@verizon.net> wrote:
> The only thing you've learned from recent threads in this forum is that
> some C standard library functions are specified by the standard to have
> less than ideal interfaces.
Yes that's it. Plus: these badly designed interfaces, can may force
you to do things (e.g. strlen), that you would not have to do
otherwise.


> It's meaningless to talk about the performance of *the* C standard
> library. There's no single C standard library
I meant the badly designed interface.

>
> > Are these deficiencies _only_ string-related?
>
> No - there are lots of other kinds of minor problems with the C standard
> library.
>
> > Is there no good library which I can use for optimal computing?
>
> I think that you can safely assume that no library you've ever heard of,
> and no library that you ever will hear of, is perfectly optimal.
What about a library that has better interfaces.
You can always change the internals, but if the function interfaces
are bad, you've got a deficiency from the start. ;)


> you plan on refusing to use many C standard library
> functions that could be useful, because you consider them less than optimal.
I'd only refuse it, if I thought the interface was bad.

And I'm trying to find my own style.
For what do I want to use the standard C lib; for what my own
routines.


> I almost never write my own routines for any purpose for which a C
> standard library routine can be made to serve, even if the library
> routine is a less-than perfect fit to my desires. The main exception is
> that I will often manually inline code that is roughly equivalent to
> some of the standard str*() and mem*() functions, especially strtok().
> For the other str*() and mem*() functions, I'll usually inline the code
> only if I need a pointer to the end of the memory that was processed,
> something that the standard library functions don't provide. The
> in-lining is generally trivial for most of those functions.

Could you perhaps give a brief example of what you mean with inlining,
here.
Thanks.

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

#19588

On 04/12/2012 02:30 PM, John Reye wrote:
> On Apr 12, 6:50 pm, James Kuyper <jameskuy...@verizon.net> wrote:
[>> John Reye wrote:]
>>> Is there no good library which I can use for optimal computing?
>>
>> I think that you can safely assume that no library you've ever heard of,
>> and no library that you ever will hear of, is perfectly optimal.
> What about a library that has better interfaces.

I guarantee you that the library with better interfaces will still be
sub-optimal.

>> I almost never write my own routines for any purpose for which a C
>> standard library routine can be made to serve, even if the library
>> routine is a less-than perfect fit to my desires. The main exception is
>> that I will often manually inline code that is roughly equivalent to
>> some of the standard str*() and mem*() functions, especially strtok().
>> For the other str*() and mem*() functions, I'll usually inline the code
>> only if I need a pointer to the end of the memory that was processed,
>> something that the standard library functions don't provide. The
>> in-lining is generally trivial for most of those functions.
> 
> Could you perhaps give a brief example of what you mean with inlining,
> here.

Here's an example of code to concatenate some strings:

	outstring[0] = '\0';
	for(str=0; str < num_strings; str++)
	    strcat(outstring, in_strings[str]);

My inline equivalent would be as follows:

	char *p = outstring;
	for(str=0; str < num_strings; str++)
	{
	    const char *q = instrings[str];
	    while(*p++ = *q++);
	    p--; // move back to terminating null character
	}

It's slightly more wordy, but keeps track of the current end of the
string, avoiding the time wasted by strcat() searching for the end of
the string. It's a minor issue, and I wouldn't bother with it if it were
significantly more difficult to do. Most of the str*() and mem*()
functions are easy to inline.

Here's some code in a utility library that I inherited responsibility
for several years ago. If caused problems when called inside a strtok()
loop in the calling routine:

    if((p=strtok(local_string, ","))!=NULL){
      do{
        /* Byte_sum = MFAIL if datatype_to_DFNT fails.
           Get HDF_num_type for p */
        if((HDF_num_type=datatype_to_DFNT(p))==MFAIL)byte_sum=MFAIL;

        /* If not MFAIL, increment byte_sum by the number of
           bytes returned from DFKNTsize */
        else byte_sum=byte_sum+(long int)DFKNTsize(HDF_num_type);

        }while((p=strtok(NULL,","))!=NULL && byte_sum!=MFAIL);
    }

To resolve this problem, a subordinate re-wrote the code, following my
advice, as follows:

    while (local_string != NULL && byte_sum != MFAIL) {
        next_string = strchr(local_string, ',');
        if (next_string)
           *next_string++ = '\0';
        HDF_num_type = datatype_to_DFNT(local_string);
        if (HDF_num_type==MFAIL)
           byte_sum = MFAIL;
        else
           byte_sum += (long int)DFKNTsize(HDF_num_type);
        local_string = next_string;
    }

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

#19584

On Thu, 12 Apr 2012 09:01:40 -0700 (PDT), John Reye
<jononanon@googlemail.com> wrote:

>Hi,
>
>recently I learned that various "standard C library" functions have
>deficiencies in terms of high performance.

Have you actually measured the performance impact of calling strlen
after each fgets?

>Examples include the return values of fgets(), strcpy(), strcat()
>(thanks Eric Sosman for mentioning the last 2)
>
>Example:            char * strcat ( char * destination, const char *
>source );
>Return Value:     destination is returned.
>
>How useless is that! I already know the distination, in the first
>place.

Useless is in the eye of the beholder.

    char buffer[100] = "The input is ";
    puts(strcat(buffer, flag ? "valid" : "invalid");

or

   strcat(strcpy(new_large_buffer, 
                       original_text_in_small_buffer),
             additional_text);

>Why not return a pointer to the end of the concatenated string, or the
>size of the string. This would cost the library no extra performance
>cost whatsoever!

Was that true 25+ years ago when the language was being designed?

>Are these deficiencies _only_ string-related?
>Is there no good library which I can use for optimal computing?

Any library where fgets returns something other the destination
pointer would be non-portable in the extreme.  Some might be tempted
to say it is not even C.

The approach taken by some compiler writers when they need to tweak a
standard function (such as add an extra parameter to make it safer) is
to create a new function with a similar name that is reserved for the
implementation (such as prepending an _ or appending a _s).  Then the
user has the choice of using the standard function or the system
specific extension.

>Because if I use the "standard C library" I'll end up _not_ using many
>of it's routines.

So you would rather loop through fgetc yourself?  You might want to
take one of your programs which is suffering from this fgets
deficiency and replace the calls to fgets and strlen with the fgetc
loop and determine the real benefit.

Or are you planning to rewrite all the standard functions you don't
like?  For how many different systems will you do this?  And in what
newsgroup will you discuss any problems you run into using these
functions.

>Where is a library, that is done right??

Not for any C system.

>Would this library only be a string-handling library, or buffer-
>handling library? Or are there other parts of the "standard C library"
>that are also deficient.

Only you can tell what is deficient.

>Surely there must be a good library somewhere, or do all C programmers
>really carry their own routines with them?

Most suffer these horrendous performance problems in silence by using
the standard library.  Others have been known to write their own
wrapper functions to encapsulate the standard functions.  But this is
usually done to add functionality (such as common error checking)
rather than deal with undocumented performance issues.


-- 
Remove del for email

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

#19587

Barry Schwarz wrote:
) On Thu, 12 Apr 2012 09:01:40 -0700 (PDT), John Reye
)<jononanon@googlemail.com> wrote:
)
)>Hi,
)>
)>recently I learned that various "standard C library" functions have
)>deficiencies in terms of high performance.
)
) Have you actually measured the performance impact of calling strlen
) after each fgets?
)
)>Examples include the return values of fgets(), strcpy(), strcat()
)>(thanks Eric Sosman for mentioning the last 2)
)>
)>Example:            char * strcat ( char * destination, const char *
)>source );
)>Return Value:     destination is returned.
)>
)>How useless is that! I already know the distination, in the first
)>place.
)
) Useless is in the eye of the beholder.
)
)     char buffer[100] = "The input is ";
)     puts(strcat(buffer, flag ? "valid" : "invalid");

Not much difference there:

  char buffer[100] = "The input is ";
  strcat(buffer, flag ? "valid" : "invalid");
  puts(buffer);

You only have to type the variable name twice.
That's a very minor inconvenience.  So it's marginally useful.
Returning a pointer to the nul terminator would be a lot more useful.

) or
)
)    strcat(strcpy(new_large_buffer, 
)                        original_text_in_small_buffer),
)              additional_text);

If strcpy and strcat returned a pointer to the nul character at the end of
the string, that would still work, *and* it would be a lot more efficient.

I've seen code where they build a giant string by repeatedly strcat()ing
a few words on the end.  That's needless O(n^2) performance right there.

)>Why not return a pointer to the end of the concatenated string, or the
)>size of the string. This would cost the library no extra performance
)>cost whatsoever!
)
) Was that true 25+ years ago when the language was being designed?

Yes.  Duh.  It's *NO* performance loss.  Not negligible, but zero.  Nil.
The library just copied a number of characters to somewhere else.
And it added a trailing zero to boot.  So it knows where that zero went.

)>Are these deficiencies _only_ string-related?
)>Is there no good library which I can use for optimal computing?
)
) Any library where fgets returns something other the destination
) pointer would be non-portable in the extreme.  Some might be tempted
) to say it is not even C.
)
) The approach taken by some compiler writers when they need to tweak a
) standard function (such as add an extra parameter to make it safer) is
) to create a new function with a similar name that is reserved for the
) implementation (such as prepending an _ or appending a _s).  Then the
) user has the choice of using the standard function or the system
) specific extension.

I think gnu libc has a few of those.  It would have been an easy fix
to accept those extra functions into the C standard interface, and then
everybody would have been happy.

)>Surely there must be a good library somewhere, or do all C programmers
)>really carry their own routines with them?
)
) Most suffer these horrendous performance problems in silence by using
) the standard library.  Others have been known to write their own
) wrapper functions to encapsulate the standard functions.  But this is
) usually done to add functionality (such as common error checking)
) rather than deal with undocumented performance issues.

The best approach I've seen is to have the build script check for
platform-specific extensions (such as strlcpy and strlcat), and if
those don't exist, include wrappers which emulate their behaviour.


I believe that these functions return the original pointer because
the language designers had some half-assed idea about viewing strings
as some kind of opaque type that you could manipulate through functions.
(I.E. conceptually, strcat takes two strings and returns one string,
 if you conveniently forget that the first string is changed, and also
 needs to have enough memory backing it to hold the whole string.)


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

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

#19589

"John Reye" <jononanon@googlemail.com> wrote in message 
news:d965f1e6-f918-4c5b-88f8-b5c09644faef@f5g2000vby.googlegroups.com...
> Hi,
>
> recently I learned that various "standard C library" functions have
> deficiencies in terms of high performance.
> Examples include the return values of fgets(), strcpy(), strcat()
> (thanks Eric Sosman for mentioning the last 2)
>
> Example:            char * strcat ( char * destination, const char *
> source );
> Return Value:     destination is returned.
>
> How useless is that! I already know the distination, in the first
> place.
> Why not return a pointer to the end of the concatenated string, or the
> size of the string. This would cost the library no extra performance
> cost whatsoever!
>
>
> Are these deficiencies _only_ string-related?

It seems that way. But no-one is bothered about it, because writing 
alternative versions (thin wrappers around standard functions) is trivial:

int strcat_l(char *s,char *t,int slen,int tlen){
 if (slen<0) slen=strlen(s);
 if (tlen<0) tlen=strlen(t);
 memcpy(s+slen,t,tlen+1);
 return slen+tlen;
}

int strcpy_l(char *s,char *t,int tlen){
if (tlen<0) tlen=strlen(t);
memcpy(s,t,tlen+1);
return tlen;
}

Etc.

(In this style that I sometimes use, you can optionally supply a string 
length if you know it, otherwise -1 is passed. It's not hard to make them 
faster than the standard functions. (Except when the lengths aren't known; 
then it would probably be better for these to just call the standard 
versions, instead of messing with strlen(). But I tend to use this form for 
other kinds of string processing where a standard version doesn't exist.))

-- 
Bartc

 

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

#19595

On 04/12/2012 04:07 PM, BartC wrote:
> "John Reye" <jononanon@googlemail.com> wrote in message 
> news:d965f1e6-f918-4c5b-88f8-b5c09644faef@f5g2000vby.googlegroups.com...
...
>> Example:            char * strcat ( char * destination, const char *
>> source );
>> Return Value:     destination is returned.
>>
>> How useless is that! I already know the distination, in the first
>> place.
>> Why not return a pointer to the end of the concatenated string, or the
>> size of the string. This would cost the library no extra performance
>> cost whatsoever!
>>
>>
>> Are these deficiencies _only_ string-related?
> 
> It seems that way. But no-one is bothered about it, because writing 
> alternative versions (thin wrappers around standard functions) is trivial:
,,,
> int strcpy_l(char *s,char *t,int tlen){
> if (tlen<0) tlen=strlen(t);
> memcpy(s,t,tlen+1);
> return tlen;
> }

Your wrapper version passes through the input array twice: once for
strlen() and once for memcpy(). That's precisely the deficiency he wants
to avoid. A minor change to the implementation of strcpy() would allow
it to return the desired pointer at no extra cost - the cost for your
wrapper is fairly high.
-- 
James Kuyper

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

#19608

"James Kuyper" <jameskuyper@verizon.net> wrote in message 
news:jm7sc1$18n$1@dont-email.me...
> On 04/12/2012 04:07 PM, BartC wrote:
>> "John Reye" <jononanon@googlemail.com> wrote in message
>> news:d965f1e6-f918-4c5b-88f8-b5c09644faef@f5g2000vby.googlegroups.com...
> ...
>>> Example:            char * strcat ( char * destination, const char *
>>> source );
>>> Return Value:     destination is returned.
>>>
>>> How useless is that! I already know the distination, in the first
>>> place.
>>> Why not return a pointer to the end of the concatenated string, or the
>>> size of the string. This would cost the library no extra performance
>>> cost whatsoever!
>>>
>>>
>>> Are these deficiencies _only_ string-related?
>>
>> It seems that way. But no-one is bothered about it, because writing
>> alternative versions (thin wrappers around standard functions) is 
>> trivial:
> ,,,
>> int strcpy_l(char *s,char *t,int tlen){
>> if (tlen<0) tlen=strlen(t);
>> memcpy(s,t,tlen+1);
>> return tlen;
>> }
>
> Your wrapper version passes through the input array twice: once for
> strlen() and once for memcpy().

Yes, I mentioned my versions work better when the caller knows the lengths.

 That's precisely the deficiency he wants
> to avoid. A minor change to the implementation of strcpy() would allow
> it to return the desired pointer at no extra cost - the cost for your
> wrapper is fairly high.

My point was that wrappers like this can be trivial to write: that 
length-based strcpy_l() function took only a minute or two. And instantly it 
can already be faster than the standard function.

Being able to deal also with cases where the lengths are not known, is an 
extra feature provided for convenience; it can be a bit slower, but it also 
*returns* the length of the string, so it might save the caller having to 
call strlen!

The wrapper functions can have other interfaces too.


-- 
Bartc 

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

#19614

On 04/13/2012 06:38 AM, BartC wrote:
> 
> 
> "James Kuyper" <jameskuyper@verizon.net> wrote in message 
> news:jm7sc1$18n$1@dont-email.me...
>> On 04/12/2012 04:07 PM, BartC wrote:
>>> "John Reye" <jononanon@googlemail.com> wrote in message
>>> news:d965f1e6-f918-4c5b-88f8-b5c09644faef@f5g2000vby.googlegroups.com...
>> ...
>>>> Example:            char * strcat ( char * destination, const char *
>>>> source );
>>>> Return Value:     destination is returned.
>>>>
>>>> How useless is that! I already know the distination, in the first
>>>> place.
>>>> Why not return a pointer to the end of the concatenated string, or the
>>>> size of the string. This would cost the library no extra performance
>>>> cost whatsoever!
>>>>
>>>>
>>>> Are these deficiencies _only_ string-related?
>>>
>>> It seems that way. But no-one is bothered about it, because writing
>>> alternative versions (thin wrappers around standard functions) is 
>>> trivial:
>> ,,,
>>> int strcpy_l(char *s,char *t,int tlen){
>>> if (tlen<0) tlen=strlen(t);
>>> memcpy(s,t,tlen+1);
>>> return tlen;
>>> }
>>
>> Your wrapper version passes through the input array twice: once for
>> strlen() and once for memcpy().
> 
> Yes, I mentioned my versions work better when the caller knows the lengths.

Which I consider a very minor advantage; if the length is known, just
call memcpy() directly. If it's not known, your version is slower than
strcpy(), and no faster than strcpy() followed by strlen().

>  That's precisely the deficiency he wants
>> to avoid. A minor change to the implementation of strcpy() would allow
>> it to return the desired pointer at no extra cost - the cost for your
>> wrapper is fairly high.
> 
> My point was that wrappers like this can be trivial to write: that 
> length-based strcpy_l() function took only a minute or two. And instantly it 
> can already be faster than the standard function.

With only a little extra work, you can write your own strcpy_l() that
doesn't call standard library functions, passes through the array only
once, and is likely (with a decent compiler) to compile into code with
speed comparable to that of strcpy() itself, but with the added
advantage of returning a value which contains more useful information
than that returned by strcpy(). I wouldn't bother writing such a
routine, because it's trivial to inline the code manually; but it would
have been slightly more convenient if strcpy() had been defined to work
that way in the first place. It's not a sufficiently big issue to
justify John Reye's overreaction, but it is a real one.

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

#19621

"James Kuyper" <jameskuyper@verizon.net> wrote in message
news:4F882FAF.4050609@verizon.net...
> On 04/13/2012 06:38 AM, BartC wrote:

>>>> int strcpy_l(char *s,char *t,int tlen){
>>>> if (tlen<0) tlen=strlen(t);
>>>> memcpy(s,t,tlen+1);
>>>> return tlen;
>>>> }
>>>
>>> Your wrapper version passes through the input array twice: once for
>>> strlen() and once for memcpy().
>>
>> Yes, I mentioned my versions work better when the caller knows the
>> lengths.
>
> Which I consider a very minor advantage; if the length is known, just
> call memcpy() directly. If it's not known, your version is slower than
> strcpy(), and no faster than strcpy() followed by strlen().

Then you lose all the abstraction that strcpy() etc provide; you have to
remember to copy the extra char in the case of strcpy().

And my main  example was strcat(); the strcpy() was needed to initialise the
destination in each iteration of the test loop. You don't really want to
start inlining functions such as strcat() because the code will obscure 
whatever it is you're really trying to do.

Don't forget these _l functions also return the length of the resulting
string. I altered the two test loops (one using _l functions, one using
standard functions) so that the length of the resulting string was needed.
(In the _l loop, I also used the result of strcpy_l() as one of the length
parameters to strcat_l().)

That way I managed to outperform four x86 C compilers at their highest
optimisation settings, *even without knowing* the lengths of the two strings
at the start of each iteration! (OK, on a very specific test on two strings
of 64 and 80 chars.)

I did another test using a strcmp_l(); this can return an instant result
when lengths are unequal, instead of having to scan the actual strings. OK,
you will argue this could also be done inline, but you don't really want to
do that; it's the compiler's job to inline, not yours.

-- 
Bartc
 

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

#19620

On 4/12/2012 8:35 PM, James Kuyper wrote:
> On 04/12/2012 04:07 PM, BartC wrote:
>> "John Reye"<jononanon@googlemail.com>  wrote in message
[...]
>>> Are these deficiencies _only_ string-related?
>>
>> It seems that way. But no-one is bothered about it, because writing
>> alternative versions (thin wrappers around standard functions) is trivial:
> ,,,
>> int strcpy_l(char *s,char *t,int tlen){
>> if (tlen<0) tlen=strlen(t);
>> memcpy(s,t,tlen+1);
>> return tlen;
>> }
>
> Your wrapper version passes through the input array twice: once for
> strlen() and once for memcpy(). That's precisely the deficiency he wants
> to avoid. A minor change to the implementation of strcpy() would allow
> it to return the desired pointer at no extra cost - the cost for your
> wrapper is fairly high.

Well, "fairly high" is relative.  What is the code going to do with the 
copy?  Perhaps that is orders of magnitude longer than the call to strlen().

Note, too, that it may be more efficient to call strlen() and then memcpy() 
than it is to copy byte-by-byte as you look for the nul-terminator.  (As I 
recall, the x86 series of CPU has a single opcode which basically does 
strlen, and memcpy can copy 4 [or even 8] bytes at a time for everything 
other than the endpoints.)

-- 
Kenneth Brody

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

#19622

On 04/13/2012 12:56 PM, Kenneth Brody wrote:
> On 4/12/2012 8:35 PM, James Kuyper wrote:
>> On 04/12/2012 04:07 PM, BartC wrote:
>>> "John Reye"<jononanon@googlemail.com>  wrote in message
> [...]
>>>> Are these deficiencies _only_ string-related?
>>>
>>> It seems that way. But no-one is bothered about it, because writing
>>> alternative versions (thin wrappers around standard functions) is trivial:
>> ,,,
>>> int strcpy_l(char *s,char *t,int tlen){
>>> if (tlen<0) tlen=strlen(t);
>>> memcpy(s,t,tlen+1);
>>> return tlen;
>>> }
>>
>> Your wrapper version passes through the input array twice: once for
>> strlen() and once for memcpy(). That's precisely the deficiency he wants
>> to avoid. A minor change to the implementation of strcpy() would allow
>> it to return the desired pointer at no extra cost - the cost for your
>> wrapper is fairly high.
> 
> Well, "fairly high" is relative.  What is the code going to do with the 
> copy?  Perhaps that is orders of magnitude longer than the call to strlen().

Agreed - I don't like wasting anything, but the amount of waste involved
here is not sufficient to justify John Reye's description of these
routines as "useless".

> Note, too, that it may be more efficient to call strlen() and then memcpy() 
> than it is to copy byte-by-byte as you look for the nul-terminator.  (As I 
> recall, the x86 series of CPU has a single opcode which basically does 
> strlen, and memcpy can copy 4 [or even 8] bytes at a time for everything 
> other than the endpoints.)

That's too platform-specific an issue for my tastes; some other platform
might have a single opcode for copying while looking for a null
terminator. As long as I write clean simple code that does precisely
what needs to be done, and no more than what needs to be done, I feel
I've done my part of the job; choosing the right op-codes to implement
it is the compiler's part.

If a two-pass implementation turns out to be faster than the one-pass
solution I wrote, I can hope that a sufficiently sophisticated compiler
will convert my one-pass C code into machine code equivalent to a
two-pass implementation. I'm not going to lose any sleep over the
possibility that it won't. If I need more speed, and can afford to loose
portability, I'll use assembly language rather than trying to figure out
how to trick a particular C compiler into generating the assembly
language I want it to generate.

John would probably be more interested in such issues than I am.

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

#19652

בתאריך יום שישי, 13 באפריל 2012 19:48:30 UTC+1, מאת James Kuyper:
> 
> If a two-pass implementation turns out to be faster than the one-pass
> solution I wrote, I can hope that a sufficiently sophisticated compiler
> will convert my one-pass C code into machine code equivalent to a
> two-pass implementation. I'm not going to lose any sleep over the
> possibility that it won't. If I need more speed, and can afford to loose
> portability, I'll use assembly language rather than trying to figure out
> how to trick a particular C compiler into generating the assembly
> language I want it to generate.
> 
You look at the bottlneck, which is unlikely to be the string concatenation, but might be. You know that.
But it's better to remove the bottleneck in C rather than assembly if you can. That way it's more likely that a maintainer can read your code. And ypu can port it much more easily. On the machine you port to the optimal two-pass solution might well be pessimal, but in ten years it might be a 20Ghz job available for five dollars, so no-one will care.

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

#19598

On 4/12/2012 12:01 PM, John Reye wrote:
> Hi,
>
> recently I learned that various "standard C library" functions have
> deficiencies in terms of high performance.

     Recently I learned that you have a bee in your bonnet.

     No, hold it, calm down, rewind: I'm not saying it's your
fault the bee is there; it may have flown in of its own accord.
But your best bet it to shake it out of your hat and settle down
before your blood pressure gets any higher.

     Despite its infelicities, I see little in the C library design
that forces implementations or callers to perform poorly.  Certainly,
there are some interfaces that could, if revised, admit of higher-
erforming implementations.  For example, malloc() is a fairly "narrow"
interface, and one can imagine a super_malloc() to which one could
pass information about the expected lifetime of the allocation, its
affinity or disaffinity to other allocations, whether it's more likely
to be used by the GPU or the DMA chip, and so on.  But one can also see
that such a super_malloc() could be rather messy to use:

	char *ptr = malloc(42);

vs.

	super_malloc_options opt = { 0 };
	opt.request_size = 42;
	opt.growth_allowance = 42 * 6;
	opt.lifetime_hint = SUPER_MALLOC_LIFETIME_BRIEF;
	opt.cache_choice = SUPER_MALLOC_CACHE_AVOID(&blivet);
	#if __STDC_VERSION__ > 201306L
	    opt.address_randomization =
	    #ifdef __WINDOWS__
	        __MS_RANDOMIZE_IF_ABLE__
	    #else
	        SUPER_MALLOC_RANDOMIZE_IF_ABLE
	    #endif
	    ;
	#endif
	char *ptr = super_malloc(&opt);

There is no doubt that an interface along the lines of the latter
could outperform the familiar malloc() in at least some situations.
But which interface would you, as a code writer, prefer to use?
Which would you expect to require more debugging time?

     I reiterate my earlier question about your keyboard: Are you
still using nineteenth-century QWERTY?  I'm not saying that you
are wrong (or right) to do so, just asking you to examine the
reasons for your choice, and to reflect on those same reasons as
they may apply to other standardized interfaces.

> Examples include the return values of fgets(), strcpy(), strcat()
> (thanks Eric Sosman for mentioning the last 2)

     You're welcome, I am sure.  But don't read so much into it: In
hindsight we may wish that some choices had been made differently,
but that's no reason to go ballistic.

> Surely there must be a good library somewhere, or do all C programmers
> really carry their own routines with them?

     That's a complicated question I'm too weary to address just now.
Ponder it for yourself, and you may discover some useful answers, or
if not answers, insights.

     And f'gawd'sake relax!

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

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

#19619

On Thu, 12 Apr 2012 21:23:03 -0400, Eric Sosman wrote:
>      Despite its infelicities, I see little in the C library design
> that forces implementations or callers to perform poorly.  Certainly,
> there are some interfaces that could, if revised, admit of higher-
> erforming implementations.  For example, malloc() is a fairly "narrow"
> interface, and one can imagine a super_malloc() to which one could pass
> information about the expected lifetime of the allocation, its affinity
> or disaffinity to other allocations, whether it's more likely to be used
> by the GPU or the DMA chip, and so on.  But one can also see that such a
> super_malloc() could be rather messy to use:
> 
> 	char *ptr = malloc(42);
> 
> vs.
> 
> 	super_malloc_options opt = { 0 };
> 	opt.request_size = 42;
> 	opt.growth_allowance = 42 * 6;
> 	opt.lifetime_hint = SUPER_MALLOC_LIFETIME_BRIEF; opt.cache_choice 
=
> 	SUPER_MALLOC_CACHE_AVOID(&blivet); #if __STDC_VERSION__ > 201306L
> 	    opt.address_randomization =
> 	    #ifdef __WINDOWS__
> 	        __MS_RANDOMIZE_IF_ABLE__
> 	    #else
> 	        SUPER_MALLOC_RANDOMIZE_IF_ABLE
> 	    #endif
> 	    ;
> 	#endif
> 	char *ptr = super_malloc(&opt);
> 
> There is no doubt that an interface along the lines of the latter could
> outperform the familiar malloc() in at least some situations. But which
> interface would you, as a code writer, prefer to use? Which would you
> expect to require more debugging time?

Come on Eric, this is a straw man argument. Of course it is possible to 
get the best of both worlds.

For example, in the Pthreads API, the pthread_create() function takes a 
pthread_attr_t * argument, but you just need to provide NULL to get a 
sensible set of defaults.

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

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

Back to top | Article view | comp.lang.c

csiph-web