Jump to content
  • Advertisement

1hod0afop

Member
  • Content Count

    30
  • Joined

  • Last visited

Community Reputation

100 Neutral

About 1hod0afop

  • Rank
    Member
  1. 1hod0afop

    String performance in C++?

    Quote:Original post by delta user btw, temporary objects do not allocate memory from the heap. They allocate from the stack. std::string might internally allocate a buffer but the temporary objects(when concatenating) don't. quick link Thanks. I found a new thing. std::string has its internal buffer. Probably will be specific to implementation. In VC2005, std::string has 16-bytes buffer which is allocated on the stack (if the string itself is allocated on the stack, of course) so strings smaller than 16 bytes will not require heap. But it still uses heap if it's larger than 16bytes, even temporary objects. BTW, I had been pretty sure that it always uses heap. So rating to you for correcting me.
  2. 1hod0afop

    String performance in C++?

    Thanks for your reply. Quote:Original post by KulSeran 1) I think you mean miliseconds (GetTickCount isn't nanoseconds) My intention was : GetTickCount is miliseconds and since the program loops 1,000,000 times, the time measured by GetTickCount() becomes nanoseconds for one iteration. I'm too lazy to write printf( "%f ns\n", uElapsed / 1000.0 / 1000000 /*# of iterations*/ * 1E+9 /**/ ); Quote: 2) you can always call std::string::reserve if you know you are doing a lot of concatanations (equivelent to your wonderful buf[21] trick) But in my opinion std::string::reserve() allocates the buffer from the heap and that's still not the same. BTW, your word "wonderful trick" made me laugh a lot. Quote: 3) If string are you bottleneck, and you don't NEED strings, you may as well replace them with something like CRC hashes of the strings in question. 4) If you do NEED string, you may want to rethink your algorithm anyway. Lots of temporary copies and concatenations can be a sign of you doing it wrong to start with. Changing how you make you pass over the dataset can mean that you don't even need to be making copies of anything. I saw some sources written in Java and was shocked at that it's pretty fast despite of a lot of string operations. And yes, one can always optimize algorithms to minimize string operations. I'm kind of lazy in that sense. I always think about 'how to make good things without headache'. Quote: 5) get a custom allocator for the string, especially if you know you are going to be allocating many small strings. Could you recommend me some? I'd like to look at them so that I can optimize my heap allocator further. Quote:You have to remember that std::blah is a GENERAL PURPOSE tool. You can always speed it up by giving it knowledge about the current situation you are using it in. And you can probably write a faster SINGLE PURPOSE tool, but you have to weigh in the cost of time spent on your tool vs. just using a proven library. Thanks. Fortunately this case seems to me profitable. I think the heap I'm making now can be used for other purposes also. And rating you up for giving many ideas
  3. 1hod0afop

    String performance in C++?

    Quote:Original post by Bregma Post your C code and I could tell for certain. Here #include <windows.h> #include <stdio.h> #include <string.h> void concat( char* pDest, const char* pStr1, const char* pStr2 ) { strcpy( pDest, pStr1 ); strcat( pDest, pStr2 ); } void main() { unsigned int uStart = GetTickCount(); const char* pstr1 = "0123456789"; const char* pstr2 = "abcdefghij"; char buf[21]; for( int i = 0; i < 1000000; i ++ ) { _asm { mov ebx, pstr2 mov eax, pstr1 lea edx, buf push ebx push eax push edx call concat add esp, 0ch } } unsigned int uElapsed = GetTickCount() - uStart; printf( "%d ns\n", uElapsed ); } My compiler often optimizes away strcpy/strcat function calls so I had to use tricks to fool the optimization. Here's the assembly code generated by VC2005. ... omitted ... ; const char* pstr1 = "0123456789"; 0040106E mov dword ptr [ebp-28h],offset string "0123456789" (4020F4h) ; const char* pstr2 = "abcdefghij"; 00401075 mov dword ptr [ebp-20h],offset string "abcdefghij" (402100h) ; for( int i = 0; i < 1000000; i ++ ) { 0040107C mov esi,0F4240h ; _asm ; { ; mov ebx, pstr2 00401081 mov ebx,dword ptr [ebp-20h] <------+ ; mov eax, pstr1 | 00401084 mov eax,dword ptr [ebp-28h] | ; lea edx, buf | 00401087 lea edx,[ebp-1Ch] | ; push ebx | 0040108A push ebx | ; push eax | 0040108B push eax | ; push edx | 0040108C push edx | ; call concat | 0040108D call concat (401000h) | ; add esp, 0ch | 00401092 add esp,0Ch | 00401095 sub esi,1 | 00401098 jne main+31h (401081h) ------------+ ; } ; } ... omitted... ;void concat( char* pDest, const char* pStr1, const char* pStr2 ) ;{ ; strcpy( pDest, pStr1 ); 00401000 mov eax,dword ptr [esp+8] ; pStr1 00401004 push esi 00401005 push edi 00401006 mov edi,dword ptr [esp+0Ch] ; pStr2 0040100A mov edx,edi 0040100C sub edx,eax 0040100E mov edi,edi 00401010 mov cl,byte ptr [eax] ; pDest <--+ 00401012 mov byte ptr [edx+eax],cl | 00401015 add eax,1 | 00401018 test cl,cl | 0040101A jne concat+10h (401010h) ---------+ ; strcat( pDest, pStr2 ); 0040101C mov eax,dword ptr [esp+14h] 00401020 mov edx,eax 00401022 mov cl,byte ptr [eax] 00401024 add eax,1 00401027 test cl,cl 00401029 jne concat+22h (401022h) 0040102B sub eax,edx 0040102D add edi,0FFFFFFFFh 00401030 mov cl,byte ptr [edi+1] <---------+ 00401033 add edi,1 | 00401036 test cl,cl | 00401038 jne concat+30h (401030h) ---------+ 0040103A mov ecx,eax 0040103C shr ecx,2 0040103F mov esi,edx 00401041 rep movs dword ptr es:[edi],dword ptr [esi] 00401043 mov ecx,eax 00401045 and ecx,3 00401048 rep movs byte ptr es:[edi],byte ptr [esi] 0040104A pop edi 0040104B pop esi ;} 0040104C ret On my machine the program gives me the result "94 ns". But wait! If I make my own string class, I can optimize further. (if heap allocation cost is low enough) How? I can store length of string in the string class, so I can eliminate 2 loops (401010 - 40101A, 401030 - 401038), which allows me double the speed. Quote:Original post by Bregma I would argue that ignorance of how to use a tool is not a valid reason to criticize a tool as inadequate for the job. Quote:Original post by Antheus But before you are able to analyze the problem, there really is no point in blaming the tools. Certainly. But I'm talking about tradeoffs between performace and simplicity. One can get similar performance with std::string by writing tricky code. What's the point of doing that? If you have to seriously consider using "+" overloaded operator, why don't you just sweep away it? And you won't be able to get same performance as strXXX functions since std::string always involves heap operation. If you can obtain high performance in convenient way, (for example, let's say SOMETHING::string concat = str1 + str2; takes 100 ns) will you still adhere to std::string? (Don't try to bother me with porting problems. Let's imagine SOMETHING::string is fully compatible with std::string) Regards
  4. 1hod0afop

    String performance in C++?

    Quote:Original post by iMalc Quote:Original post by 1hod0afop OK here's a simple program *** Source Snippet Removed *** That's not valid C++. main must be declared as returning int, NOT void. I personally see 860ns for 1 million string concatenations as being blazingly fast. That's over 1.1 billion per second! If you ever find such std::string usage to be a bottleneck in a real-life program then I'd be happy to hear from you. (Assuming GDev.net is still around then) No, the output 860ns is for 1 string concatenation, meaning 1.1M per second.
  5. 1hod0afop

    String performance in C++?

    Quote:Original post by EasilyConfused Quote:Original post by 1hod0afop Quote:Original post by Ra Give an example of your supposed usage. It's probably abusive. I'm highly negative of using std::string. On my computer just concatenating 2 std::string's each 10 characters-long takes 0.9 miliseconds! (don't think I'm using 10-year-old or such antique machine) If I instead use strcpy/strcat it takes only 50 nanoseconds. That's why I never use std::string. Now the reason why I'm doing this is to allow such abuse of strings. Actually the guys behind me are using std::string now also. They're making me crazy. Analyzing their code, find such abuses, optimizing ... It's time to end this crazy course. Are you sure that you are not profiling in debug mode? That seems like a huge time difference. Sorry for my mistake, microseconds. That's still too slow for me. ^^
  6. 1hod0afop

    String performance in C++?

    Quote:Original post by thre3dee GetTickCount is in milliseconds, not nanoseconds btw. I know. That's why the program loops 1,000,000 times.
  7. 1hod0afop

    String performance in C++?

    Quote:Original post by EasilyConfused Are you sure that you are not profiling in debug mode? That seems like a huge time difference. OK here's a simple program #include <windows.h> #include <stdio.h> #include <string> void main() { unsigned int uStart = GetTickCount(); std::string str1 = "0123456789"; std::string str2 = "abcdefghij"; for( int i = 0; i < 1000000; i ++ ) std::string concat = str1 + str2; unsigned int uElapsed = GetTickCount() - uStart; printf( "%d ns\n", uElapsed ); } In Visual Studio 2005, it outputs Debug build : 3015 ns Release build : 860 ns However, by linking CRT library static it gets a little faster Release build /MT : 657 ns
  8. 1hod0afop

    String performance in C++?

    Quote:Original post by Ra Give an example of your supposed usage. It's probably abusive. I'm highly negative of using std::string. On my computer just concatenating 2 std::string's each 10 characters-long takes 0.9 microseconds! (don't think I'm using 10-year-old or such antique machine) If I instead use strcpy/strcat it takes only 50 nanoseconds. That's why I never use std::string. Now the reason why I'm doing this is to allow such abuse of strings. Actually the guys behind me are using std::string now also. They're making me crazy. Analyzing their code, find such abuses, optimizing ... It's time to end this crazy course. [Edited by - 1hod0afop on July 11, 2008 2:10:47 AM]
  9. 1hod0afop

    String performance in C++?

    Thanks for replies. In-place allocators are incredibly fast, yeah. But it has very restricted usage since it can't free blocks individually. The allocator probably doesn't know if requested memory is for temporary or relatively permanent. The goal in GC heap is its "relocatability". i.e. memory blocks can be moved from place to place behind the scene. Because of that the heap can remain compacted and thus allowing fast allocation like in-place allocators. Moving heap frame behind the scene is very dangerous in C++ and will require a great care. I couldn't find way to implement relocatable allocator in STL (without ENORMOUS overhead). Probably the GC heap will also have restricted usage. I don't think it's possible to allocate objects in GC heap without compiler's support. Quote:Original post by Antheus Improvements noted are up to a factor of 50. The fact that in-place allocator can be 50x faster encouraged me a lot. I'm gonna start CRAZY battle again, with GC heap (more precisely "relocatable heap") Regards
  10. Hi everyone I was considering performance of std::string and CString class in MFC and so far I came up with an idea that string performance could be improved. ( I'm not 100% sure so pls correct me if I'm wrong :) ) - When string operation is performed, there exists many temporary objects and each allocates (and soon deallocate) a buffer from heap. (Am I right?) - If that's the case, wouldn't it possible to enhance string performance by implementing a specific heap for temporary storage? I've got the idea of temporary-specific heap from here ((Chapter 2 "And in theory ...")::("2) Garbage collection ...")::(3rd paragraph, "with GC, ...")). Though I don't totally agree with that article, I think it might be profitable for temporary storage. So, would it enhance performance of string operation? and if it does, will it be worth? Or is there already solution for temporary-specific heap? Thanks in advance
  11. Quote:Original post by Gage64 I'll again recommend that you take a look at boost::object_pool. I saw it already. It's basically like this: template <class T0> element_type* construct( T0 ) { ... } template <class T0, class T1> element_type* construct( T0, T1 ) { ... } template <class T0, class T1, class T2> element_type* construct( T0, T1, T2 ) { ... } template <class T0, class T1, class T2, class T3> element_type* construct( T0, T1, T2, T3 ) { ... } ... ... And my boss doesn't like it. It seems to me not genuine, either. Anyways, thanks very much for your effort. The boost library gave me a lot of ideas.
  12. One solution I found so far is this struct cust_init_tag {}; void* operator new( size_t, void* Ptr, cust_init_tag ) { return Ptr; } void operator delete( void*, void*, cust_init_tag ) {} template <class T> struct _destruct_ { T Value; void operator delete( void* ) {} }; template <class T> void destruct( T* p ) { delete reinterpret_cast< _destruct_<T>* >(p); } And now I can invoke constructors and destructors like normal functions: struct Foo { Foo( int, int ); ~Foo(); ... }; Foo* pFoo = (Foo*) ::malloc( sizeof (Foo) ); new(pFoo, cust_init_tag()) Foo( 1, 2 ); destruct( pFoo ); ::free( pFoo ); But looks messy. Please tell me if there's better way. And my boss still wants me to implement the CRAZY arraylist. =(
  13. Hell, why doesn't C++ have constructor inheritance? If so, I could write this: template <class T> struct _init_ : T { void* operator new( size_t, T* Ptr ) { return Ptr; } void operator delete( void* ) { } void operator delete( void*, T* ) { } }; #define CONSTRUCT( type, ptr, args ) ( (void) new(ptr) _init_<type> args ) #define DESTRUCT( type, ptr ) ( delete _init_<type> ) class Foo { Foo( int, int ); .... }; .... CONSTRUCT( Foo, pFoo, (1,2) ); Is there any way around? Or do I have to write this stupid code? template <class T> struct _init_ { T Data; _init_() : Data() {} template <class A1> _init_( A1 a1 ) : Data(a1) {} template <class A1, class A2> _init_( A1 a1, A2 a2 ) : Data(a1, a2) {} template <class A1, class A2, class A3> _init_( A1 a1, A2 a2, A3 a3 ) : Data(a1, a2, a3) {} .... void* operator new( size_t, T* Ptr ) { return Ptr; } void operator delete( void* ) { } void operator delete( void*, T* ) { } }; [Edited by - 1hod0afop on July 8, 2008 9:55:25 AM]
  14. Quote:Original post by fboivin btw, sometimes, to avoid the temporary you can just grow your vector first and take a reference on the last element. The resize will internally call the default constructor of T though. *** Source Snippet Removed *** No, in that case also unnecessary assignment operator call will be made, if the compiler is not "smart enough" to optimize it. In perfect case we should be able to construct the element *directly* in the vector.
  15. 1hod0afop

    [MOVED] Help with constructors

    OK what I tried is being discussed in here. So renaming title [MOVED].
  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!