Sunday, November 2, 2014

Digest for comp.lang.c++@googlegroups.com - 25 updates in 4 topics

comp.lang.c++@googlegroups.com Google Groups
Unsure why you received this message? You previously subscribed to digests from this group, but we haven't been sending them for a while. We fixed that, but if you don't want to get these messages, send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Luca Risolia <luca.risolia@linux-projects.org>: Nov 02 01:55AM +0100

Il 01/11/2014 23:02, JiiPee ha scritto:
 
> my fast function please ask, I can give it then. Also, if somebody knows
> faster way to convert, am ready to test it against this! I have a test
> platform ready.
 
And how can we reproduce your tests? Please post the full, compilable
test program together with all the informations about the compiler,
compiler version and compilation flags that you used.
JiiPee <no@notvalid.com>: Nov 02 01:19AM

On 02/11/2014 00:55, Luca Risolia wrote:
 
> And how can we reproduce your tests? Please post the full, compilable
> test program together with all the informations about the compiler,
> compiler version and compilation flags that you used.
 
I also tested intToStr that it converts correctly: first 20 million is
correct. Needs to test all integers, takes 2 hours.... gonna do sometimes.
 
compiler: GCC 4.8.1, use C++11, -O3, -s
 
Here you go:
 
#include <iostream>
#include <ctime>
 
inline void intToStr(unsigned val, char* c)
{
int size;
if(val>=10000)
{
if(val>=10000000)
{
if(val>=1000000000)
size=10;
else if(val>=100000000)
size=9;
else
size=8;
}
else
{
if(val>=1000000)
size=7;
else if(val>=100000)
size=6;
else
size=5;
}
}
else
{
if(val>=100)
{
if(val>=1000)
size=4;
else
size=3;
}
else
{
if(val>=10)
size=2;
else if (val==0) {
c[0]='0';
c[1] = '\0';
return;
}
else
size=1;
}
}
 
c += size-1;
while(val>=100)
{
int pos = val % 100;
val /= 100;
*(short*)(c-1)=*(short*)(digit_pairs+2*pos);
c-=2;
}
while(val>0)
{
*c--='0' + (val % 10);
val /= 10;
}
c[size+1] = '\0';
}
 
// speed test function:
 
// intToStr is 132 faster than snprintf
// loop 1294967295 step 60 (i+=60): intToStr 0.41 s, snprintf 54.4 s
(x132), sprintf 54.2 (x131)
// (max uint=4294967295)
void benchmark() {
 
clock_t begin = clock();
 
char str2[16];
char cU;
for(unsigned int i = 0; i < 1294967295; i+=60) {
 
// HERE COMMENT OUT THE FUNCTION YOU WANT TO TEST:
//intToStr(i, str2);
//snprintf (str2, 15, "%d",i);
sprintf(str2,"%d",i);
//itoa (i,str2,10);
 
cU += str2[6]; // use the string so that the compiler will not
optimize things out
}
 
clock_t end = clock();
double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
 
std::cout<<"Time: "<<elapsed_secs<<cU<<std::endl;
}
JiiPee <no@notvalid.com>: Nov 02 01:23AM

On 02/11/2014 01:19, JiiPee wrote:
> // HERE COMMENT OUT THE FUNCTION YOU WANT TO TEST:
 
obviously below that only one conversion function should be without
comments... others should be in comments: like if testing snprintf then:
 
//intToStr(i, str2);
snprintf (str2, 15, "%d",i);
//sprintf(str2,"%d",i);
//itoa (i,str2,10);
Jorgen Grahn <grahn+nntp@snipabacken.se>: Nov 02 02:10AM

On Sat, 2014-11-01, JiiPee wrote:
> also used the sixth item from the result: cU += str2[6]; inside the loop
> and then printed it at the end so that the compiler would not optimize
> things out).
 
That's not a bad setup, but it's even harder than that to make
benchmarks. E.g. how does this implementation affect data and code
caches? Unlike in real code, the caches are probably warm when you
enter the function you're benchmarking.
 
> checking integers from it.
 
> Not really complaining but want to start a discussion about this: why
> std sometimes does not make fast functions/classes?
 
The C++ standard has not so much to do with it; it's a problem with
whatever implementation of the standard library you use.
 
But /that/ is an interesting question: are we losing performance due
to suboptimal standard library implemntations, and is it feasible to
do something about it?
 
I know, after earlier discussions here, that std::ostream
implementations tend to be slower than C stdio. And I don't see that
they /have/ to be.
 
> my fast function please ask, I can give it then. Also, if somebody knows
> faster way to convert, am ready to test it against this! I have a test
> platform ready.
 
/Jorgen
 
--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
Paavo Helde <myfirstname@osa.pri.ee>: Nov 02 02:08AM -0600

> correct. Needs to test all integers, takes 2 hours.... gonna do
> sometimes.
 
> compiler: GCC 4.8.1, use C++11, -O3, -s
 
 
It appears that the crux of the fast algorithm is to have some static
lookup buffer (digit_pairs) which encodes the ASCII representation of
numbers 0..99. (You forgot to include that, copied it from the
stackoverflow page). So, it trades some memory for speed. So far, so
good.
 
For fast operation it is essential the digit_pairs array is in the cache.
In your test, this is most probably the case, but in real code the int-
to-string conversions probably happen much less often, so the performance
would not be so great in the real code. Standard library implementations
probably operate only with data in registers so the cache access is not
an issue.
 
Another point is that in C++ you want to wrap the result in a std::string
or something, and that will also slow things down. In my test runs
wrapping time was in the same range than the conversion itself and if
std::string happens to not use SSO then I guess it may be even much
slower.
 
So, it is not really clear how much would the win be in real programs.
Anyway, here are my test results for running your test program (MSVC2012,
Release x64 mode):
 
Using _snprintf, no wrapping: 4.622 s
Using intToStr, no wrapping: 1.143 s (4.0 times faster)
 
Using _snprintf, wrapping to a std::string: 6.622 s
Using boost::lexical_cast<std::string>: 8.75 s
Using intToStr, wrapping to a std::string: 2.996 s (2.2 times faster than
_snprintf and 2.9 times faster than boost::lexical_cast).
 
So, here the differences are around 2-3 times and probably smaller in the
real code when the lookup array is out of the cache. Not sure if this
justifies optimizing something which is already quite fast anyway.
 
OTOH, if there are indeed differences like 130 times on some platform,
then I guess the standard library implementation must be quite bad
indeed.
 
Cheers
Paavo
 
 
Christian Gollwitzer <auriocus@gmx.de>: Nov 02 09:35AM +0100

Am 02.11.14 03:10, schrieb Jorgen Grahn:
> I know, after earlier discussions here, that std::ostream
> implementations tend to be slower than C stdio. And I don't see that
> they /have/ to be.
 
For sprintf vs. intToStr (or itoa), I'm also not surprised - sprintf has
to interpret the format string at runtime, unless the compiler has a
special optimization to inline sprintf.
 
Christian
JiiPee <no@notvalid.com>: Nov 02 10:09AM

hmmm, interesting. How is it possible you have only 3 times faster and I
have here constantly 130 times faster? Any idea? Did you try also with GCC?
Jorgen Grahn <grahn+nntp@snipabacken.se>: Nov 02 12:06PM

On Sun, 2014-11-02, Christian Gollwitzer wrote:
>> they /have/ to be.
 
> For sprintf vs. intToStr (or itoa), I'm also not surprised - sprintf has
> to interpret the format string at runtime,
 
Oh, I'm not surprised by /that/ -- I was only talking about iostreams
above.
 
> unless the compiler has a
> special optimization to inline sprintf.
 
I was going to say "sprintf() seems unlikely to be one of those
functions", but gcc apparently has it as a builtin. No idea why
though -- the documentation doesn't say.
 
/Jorgen
 
--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
"Jouko Koski" <joukokoskispam101@netti.fi>: Nov 02 02:21PM +0200

"JiiPee" wrote:
 
> I wonder how C++ standard library has not implemented a very fast
> integer-to-string conversion function. They have sprintf, snprintf,
> stringstream and to_string.
 
Considering what these functions do, they may perform pretty well, actually.
It is so easy to implement a function which simple, fast, and produces
incorrect results. It is so obvious that 1234 should yield "1234" but what
if the result, say, "१२३४" would be preferred?
 
--
Jouko
Paavo Helde <myfirstname@osa.pri.ee>: Nov 02 07:11AM -0600


> hmmm, interesting. How is it possible you have only 3 times faster and
> I have here constantly 130 times faster? Any idea? Did you try also
> with GCC?
 
Gcc/Linux results:
 
snprintf: 2.85 s
intToStr: 0.4 s (7.1 times faster)
 
snprintf + std::string wrap: 4.37 s
boost::lexical_cast to std::string: 2.44 s
intToStr + std::string wrap: 1.67 s
 
Command-line options: g++ -O3 -Wall
 
> g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib64/gcc/x86_64-suse-linux/4.6/lto-wrapper
Target: x86_64-suse-linux
Configured with: ../configure --prefix=/usr --infodir=/usr/share/info --
mandir=/usr/share/man --libdir=/usr/lib64 --libexecdir=/usr/lib64 --
enable-languages=c,c++,objc,fortran,obj-c++,java,ada --enable-
checking=release --with-gxx-include-dir=/usr/include/c++/4.6 --enable-ssp
--disable-libssp --disable-plugin --with-bugurl=http://bugs.opensuse.org/
--with-pkgversion='SUSE Linux' --disable-libgcj --disable-libmudflap --
with-slibdir=/lib64 --with-system-zlib --enable-__cxa_atexit --enable-
libstdcxx-allocator=new --disable-libstdcxx-pch --enable-version-
specific-runtime-libs --program-suffix=-4.6 --enable-linux-futex --
without-system-libunwind --with-arch-32=i586 --with-tune=generic --
build=x86_64-suse-linux
Thread model: posix
gcc version 4.6.2 (SUSE Linux)
JiiPee <no@notvalid.com>: Nov 02 02:22PM

and needs this one as well:
 
const char digit_pairs[201] = {
"00010203040506070809"
"10111213141516171819"
"20212223242526272829"
"30313233343536373839"
"40414243444546474849"
"50515253545556575859"
"60616263646566676869"
"70717273747576777879"
"80818283848586878889"
"90919293949596979899"
};
 
On 02/11/2014 01:19, JiiPee wrote:
JiiPee <no@notvalid.com>: Nov 02 02:25PM

you have the same intToStr time as I have, but I have like 40 secs for
snprintf. But I have 32 bit computer, so maybe thats the reason.
 
I ran it again, it took more than 50 secs with snprintf. Dont know....
 
 
On 02/11/2014 13:11, Paavo Helde wrote:
Ben Bacarisse <ben.usenet@bsb.me.uk>: Nov 02 02:48PM

Paavo Helde <myfirstname@osa.pri.ee> writes:
<snip>
>>>> wants my fast function please ask, I can give it then. Also, if
>>>> somebody knows faster way to convert, am ready to test it against
>>>> this! I have a test platform ready.
<snip>
> It appears that the crux of the fast algorithm is to have some static
> lookup buffer (digit_pairs) which encodes the ASCII representation of
> numbers 0..99.
 
Worth pointing out that the code that copies the pairs is not portable
for a number of reasons and, in those cases where it works, the
performance may depend on the buffer alignment. I changed the code to
copy the two bytes portably, and saw no significant penalty, at least in
optimised code.
 
Dragons:
>> val /= 100;
>> *(short*)(c-1)=*(short*)(digit_pairs+2*pos);
>> c-=2;
 
<snip>
--
Ben.
"Öö Tiib" <ootiib@hot.ee>: Nov 02 07:03AM -0800

On Sunday, 2 November 2014 16:25:53 UTC+2, JiiPee wrote:
> you have the same intToStr time as I have, but I have like 40 secs for
> snprintf. But I have 32 bit computer, so maybe thats the reason.
 
No. You likely did something wrong and possibly already discovered what.
Or why else you avoid posting command lines, compiler versions and
system confs? Test carefully. Otherwise you just spread groundless FUD.
"Öö Tiib" <ootiib@hot.ee>: Nov 02 07:20AM -0800

On Sunday, 2 November 2014 01:02:49 UTC+2, JiiPee wrote:
> I wonder how C++ standard library has not implemented a very fast
> integer-to-string conversion function. They have sprintf, snprintf,
> stringstream and to_string.
 
In my tests all of the conversions ('snprintf', 'boost::lexical_cast',
'std::to_string' etc.) are already blindingly fast. 'boost::format' for
example compares most slow but is still tolerable since nothing needs
to turn hundreds of millions of 'int's into readable sub second.
 
If the string conversions affect performance then I can bet that the
whole algorithm can be made faster by few orders of magnitude since
something is wrong with the whole nature of it. What you do with
*gigabytes* of *human-readable* ints on your 32 bit computer?
"K' Dash" <adnanrashidpk@gmail.com>: Nov 01 04:51PM -0700

Ptr<Mac48Address> Mac
 
people call it smart pointer. but I dont know the exact difference.
Ptr is a class also, because when I click on Ptr<Mac48Address> Mac, then IDE show me this "class ptr". they mixed things with templates. :(
Ben Bacarisse <ben.usenet@bsb.me.uk>: Nov 02 12:37AM


> jacob navia <jacob@spamsink.net> writes:
>>You know immediately what "Mac" is: a pointer to some class
 
> This might be so in C.
 
Since C does not have classes, that's not possible.
 
> But in C++ there also are so-called »alias-declarations«
> by which »Mac48Address« does not have to be class!
 
True, but Jacob was just using information given by the op:
 
| where Mac48Address is a class
 
<snip>
--
Ben.
Jorgen Grahn <grahn+nntp@snipabacken.se>: Nov 02 01:50AM

On Sat, 2014-11-01, K' Dash wrote:
> Ptr is a class also, because when I click on Ptr<Mac48Address> Mac,
> then IDE show me this "class ptr".
> they mixed things with templates. :(
 
It's like with everything else: to use it you have to read the
documentation. This Ptr<T> thing seems to be a smart pointer of some
kind, but it's not one of those defined by the C++ language, so
exactly what it does is anyone's guess. The name doesn't exactly give
any clues ...
 
Who are "they"?
 
BTW, it also seems a bit unusual to have a smart pointer to a
"Mac48Address", which surely is an Ethernet address. These are small
enough to be treated the same way as e.g. an int: copied when someone
else needs them and so on.
 
/Jorgen
 
--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
jacob navia <jacob@spamsink.net>: Nov 02 08:05AM +0100

Le 02/11/2014 01:21, Stefan Ram a écrit :
> This might be so in C.
 
> But in C++ there also are so-called »alias-declarations«
> by which »Mac48Address« does not have to be class!
 
Excuse, I forgot that.
 
Thanks for confirming, C++ is unreadable. Actually you can NEVER know
what you are reading since most words can be redefined at will.
 
Luckily we don't do that in natural language. Imagine what would happen
if we could do in english:
 
using yes = no;
using no = yes;
 
and Romeo and Juliette talking in a warm summer night...
 
:-)
Paavo Helde <myfirstname@osa.pri.ee>: Nov 02 02:27AM -0600

jacob navia <jacob@spamsink.net> wrote in news:m34l3e$rsv$1
 
> Excuse, I forgot that.
 
> Thanks for confirming, C++ is unreadable. Actually you can NEVER know
> what you are reading since most words can be redefined at will.
 
Yes, one can shoot yourself in the foot in many ways in C++ and in C, or
one can choose names which are useful. "Ptr" actually contains some hint
that it is a pointer. "*" on the other hand does not convey any such
information, you have to know what it means.
 
Besides, it is also possible in C to have "typedef Mac48Address* Ptr".
Microsoft uses things like that a lot (LPCTSTR et. al.). Not saying this is
good for anything.
 
Cheers
Paavo
Jorgen Grahn <grahn+nntp@snipabacken.se>: Nov 02 08:40AM

On Sun, 2014-11-02, Paavo Helde wrote:
 
> Besides, it is also possible in C to have "typedef Mac48Address* Ptr".
> Microsoft uses things like that a lot (LPCTSTR et. al.). Not saying this is
> good for anything.
 
The situation in C is worse, because
 
- Typedefs are used a lot more in many subcultures (e.g. Microsoft).
One API I'm using has

typedef char* String;
typedef const char* ConstString;
 
and I fail to see the point of such exercises.
 
- It is more common in C that you /do/ need to know what something
really is, since the "irregular" types are so much more used:
pointers, arrays, the struct hack ...
 
/Jorgen
 
--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
ram@zedat.fu-berlin.de (Stefan Ram): Nov 02 12:12AM

>and
>Ptr<Mac48Address> Mac
>where Mac48Address is a class
 
C++ does not define a difference for such a case.
In C++, one can calculate the difference of numbers
or of pointers.
 
C++ also does not define »Mac48Address« nor »Ptr«.
C++ uses the name »Ptr« sometimes in examples.
 
However, when one writes each line into a file,
the diff program gives:
 
1c1
< Mac48Address* Mac
---
ram@zedat.fu-berlin.de (Stefan Ram): Nov 02 12:21AM

>You know immediately what "Mac" is: a pointer to some class
 
This might be so in C.
 
But in C++ there also are so-called »alias-declarations«
by which »Mac48Address« does not have to be class!
 
For example:
 
#include <iostream>
#include <ostream>
 
int main( void )
{ using Mac48Address = int;
Mac48Address buffer;
Mac48Address* Mac = &buffer;
*Mac = 22;
::std::cout << *Mac << '\n'; }
 
Above, »Mac48Address« is a alias for a type, but not for
a class.
ram@zedat.fu-berlin.de (Stefan Ram): Nov 02 12:42AM

>>by which »Mac48Address« does not have to be class!
>True, but Jacob was just using information given by the op:
>| where Mac48Address is a class
 
Oops. Sorry, I missed that part in the OP!
woodbrian77@gmail.com: Nov 01 05:06PM -0700

On Saturday, November 1, 2014 5:33:58 PM UTC-5, Öö Tiib wrote:
 
> What the 112 bytes can possibly contain?
> Didn't you make something odd there (like comparing "debug"
> versions, or forbidding inlining)?
 
I used the same makefile for both builds
 
http://webEbenezer.net/misc/makefile .
 
The only thing that changed is that line.
I'm not at my office now, but I'll check into
what is in those 112 bytes later.
 
Brian
Ebenezer Enterprises
http://webEbenezer.net
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)