Stack vs malloc vs heap

[CommonTater]

I've been messing about with various tests to try to determine if there's a penalty for various methods of creating strings... With the goal of creating a safe strings library at some point...
 
Here's my code...

Code: [Select]


 // speed hit test for private heaps
#define WIN32_DEFAULT_LIBS
#include <windows.h>
#include <stdio.h>
#include <string.h>

#define HITS 10000000

#define STRING "The quick brown fox jumped over the lazy dog in the field"

HANDLE hHeap;

#pragma optimize(time)
 
// strings on the stack
void teststack (char *str)
  {
    char t[strlen(str) + 1];
    strcpy(t,str);
  }
 
// strings in default heap
void testmalloc (char *str)
  {
    char *t = malloc(strlen(str) + 1);
    strcpy(t,str);
    free(t);
  }
 
// strings in private heap
void testheap (char *str)
  {
    char *t = HeapAlloc(hHeap,0,strlen(str) +1);
    strcpy(t,str);
    HeapFree(hHeap,0,t);
  }

// start time marker
DWORD marktime (void)
  {
    return GetTickCount();
  }
// elapsed time
DWORD usedtime (DWORD ticks)
  {
    return (GetTickCount() - ticks);
  }
 

int main(void)
  {
    DWORD ticks;
    char *s = STRING;
 
    hHeap = HeapCreate(HEAP_GENERATE_EXCEPTIONS,65535,0);
    if (! hHeap)
      {
        printf("Heap creation failed\n");
        exit(-1);
      }
    // set low fragmentation
    ULONG hi = 2;
    HeapSetInformation(hHeap,0,&hi,sizeof(ULONG));
 
    // pass one using the stack
    ticks = marktime();
    for(int x = 0; x < HITS; x++)
      teststack(s);
    printf("Stack Time = %u\n", usedtime(ticks));     
       
    // pass 2 using malloc
    ticks = marktime();
    for(int x = 0; x < HITS; x++)
      testmalloc(s);
    printf("Malloc Time = %u\n", usedtime(ticks));     
 
    // pass 3 using private heap
    ticks = marktime();
    for(int x = 0; x < HITS; x++)
      testheap(s);
    printf("Heap Time = %u\n", usedtime(ticks));     
 
    return 0;
  }

It's pretty primative but just I wanted to know if there was a substantial difference between using the somewhat standard char string[] method and various memory allocation methods... The attahments show my results for an x64 console project using the single threaded lib and inlining at default... on an AMD x64 dual core machine with win7 x64...

 
What I'm wondering is of  others get similar results from differing systems...  and if anyone thinks the speed hit ( which took 10,000,000 hits to make obvious) is anything I need to worry about...

 
 

[JohnF]

If you want a higher resolution timer.

Code: [Select]

long long __declspec(naked) __cdecl rdtsc(void)
{ // rdtsc puts the low order 32-bits to eax
// and high order 32-bits to edx
__asm{
rdtsc
ret
}
}

John

[TimoVJL]

If you want a higher resolution timer.

PellesC also have a function _rdtsc().

[JohnF]

That makes it easier.

John

[CommonTater]

Thanks guys, but it's not timer resolution that I'm concerned with... The big Q at this point is whether the obvious speed hit of using char* instead of char[] for strings is going to significantly impact software performance...

My thought is that if the speed hit is deemed either "trivial" or "acceptable" (meaning it's worth it for what we gain) then perhaps it's time to re-think the way C handles strings.  I've roughed out some of the base library functions (eg. StrCat() that includes realloc() to avoid buffer overflows) and it looks promising.  But it's a lot of work and I'd just as soon not waste the time (possibly in months) if it's not going to be deemed helpful.

[Stefan Pendl]

If you know how many characters the string will hold as a maximum, you can use the fixed size.

For dynamically sized strings you would use the temporary allocation.

It is a consideration for multi-thread programming too.

[CommonTater]

If you know how many characters the string will hold as a maximum, you can use the fixed size.

For dynamically sized strings you would use the temporary allocation.

It is a consideration for multi-thread programming too.

Trust me, I know how strings work in the current incarnation of C...

The thing is I've never liked the way C handles strings.  As I've frequently suggested, C should have gotten a native string type (i.e. language keyword "string") with compiler level support at it's first revision.  That it wasn't in the first version ranks as an oversight... that it was never incorporated (even in C++, where it's still just a library) is just plain foolishness. 

I mean really... both Pascal and BASIC had compiler level string types before C was ported to DOS by Borland... so surely they must have had some idea of the shortcoming.

[aardvajk]

Considering the difference is 70 nanoseconds per string and that it takes a third of a second to blink (333ms):
333 milliseconds / 70 nanoseconds = 4757142 (and a bit) strings to save enough time to be able to blink

if you copied 50 strings in your program:
4757142 / 50 = 95142 (and a bit) runs of your program

If I run your program 50 times a day:
95142 / 50 = 1902 (and a bit) days

1902 days = 5 1/5 years

So if I run your program everyday for 5 years and 2 months you'll have saved me enough time to be able blink once more. Yeah, I think you should be truly concerned. Who knows when I might need that blink to block a fly hitting my eye.

If you're ever doing anything performance related and the quote "which took 10,000,000 hits to make obvious" comes about, you're wasting your time because the difference is so minor it's not even worth it.

[CommonTater]

If you're ever doing anything performance related and the quote "which took 10,000,000 hits to make obvious" comes about, you're wasting your time because the difference is so minor it's not even worth it.

This was my impression too... but I thought I should raise the discussion here as a means of being extra double certain sure ...  I did realize we were looking at something like a few nanoseconds per string...
 
but I was also hoping some would run it on their machines... wondering if my results were consistent across various AMD and Intel platforms and other versions of windows as well. 
 
I'm planning a very extensive project and it would be a real pain to find out it only worked as expected on *my* machine... LOL.

 

[Bitbeisser]

If you're ever doing anything performance related and the quote "which took 10,000,000 hits to make obvious" comes about, you're wasting your time because the difference is so minor it's not even worth it.

This was my impression too... but I thought I should raise the discussion here as a means of being extra double certain sure ...  I did realize we were looking at something like a few nanoseconds per string...
 
but I was also hoping some would run it on their machines... wondering if my results were consistent across various AMD and Intel platforms and other versions of windows as well. 
 
I'm planning a very extensive project and it would be a real pain to find out it only worked as expected on *my* machine... LOL.

What would be working only on "your" machine?

Using the stack is the fastest of the option in the test and is the default/standard way of doing this in C, unless you work on some (embedded) system/CPU that has only a very limited stack size or none at all...

Ralf

[CommonTater]

What would be working only on "your" machine?

It's about "Murphy's Law"... anything that can go wrong, will go wrong... lol.
 

Using the stack is the fastest of the option in the test and is the default/standard way of doing this in C, unless you work on some (embedded) system/CPU that has only a very limited stack size or none at all...

Yep, I know that.  But, well, I remain convinced there just has to be a better way...

When you can do this...

Code: [Select]

newstring := oldstring;
newstring := newstring + extrastring;
In pascal... or this...

Code: [Select]

$newstring = $oldstring;
$newstring = $newstring + $extrastring;
in BASIC...

One does have to think there just has to be a better way.  Pascal and BASIC are ancient history... BASIC was doing strings before C was ever written.... It's not like the issue was a total surprise to K&R... but here we are, using a language with no real awareness of text, 30 years later.

Not that C can't manipulate text... it clearly can... but look at all the problems with buffer exploits and string overruns that have plagued Windows (and other OSs too)... all of this could have been avoided with just a little forethought, way back when...

Here's a hint... Pascal and Delphi both have native string types.  They also have built in array bounds checking... and guess what, nobody has ever penetrated either with buffer exploits or overruns... That's gotta tell you something.

Oh and incase we don't speak before ... Happy new year, my friend.

[Bitbeisser]

What would be working only on "your" machine?

It's about "Murphy's Law"... anything that can go wrong, will go wrong... lol.

The last couple of month of my life have been the proof for that... 

Yep, I know that.  But, well, I remain convinced there just has to be a better way...

well...

One does have to think there just has to be a better way.  Pascal and BASIC are ancient history... BASIC was doing strings before C was ever written.... It's not like the issue was a total surprise to K&R... but here we are, using a language with no real awareness of text, 30 years later.

Well, that's all a matter of perspective and on priorities/purpose for the language written...
C was perceived as a tool to write an operating system and its tools, being able to handle any kind of data in any location of memory. That's the way how all data is more or less seen as a "stream" and the way most everything is accessed by explicit pointers (more or less, all a bit simplified). That's also the reason why there are basically only 4 types of data in C, char, int, float and pointer. As simplistic as assembler, which is one of the reasons why a lot of people refer to C as a "higher level assembly" language.

BASIC and Pascal at least originated with a different purpose, providing a tool to teach/learn programming.
BASIC was made easy to understand and getting started, so to "communicate", it had from the start a string type as well as floats.
Same for Pascal, though Wirth took it one step further and integrated more stricter rules, which in return "turned off" a lot of professional programmers, who (or at least thought so) "know what they are doing".
But because they make a lot of application type programming easier, both BASIC and Pascal quickly saw widespread use in that area, in particular after suitable compilers became available, like the flurry of Business BASIC variants in the '80s as well as UCSD and Borland/Turbo Pascal, which then evolved into Delphi on Windows...

But in any case, the way how strings can be used in any language doesn't really have anything to do with your subject of using stack or heap... 

Not that C can't manipulate text... it clearly can... but look at all the problems with buffer exploits and string overruns that have plagued Windows (and other OSs too)... all of this could have been avoided with just a little forethought, way back when...

Actually, the first version of Windows were written with a heavy dose of Pascal... ;-)
But that we have those kinds of issues today, that is more the fault of the programmers than of the language being used. You can write safe programs in C as well, it just requires a more methodical way of working, which in turn takes more time, which in turn casts more money and therefor is discouraged in order to rush products out of the door...

Here's a hint... Pascal and Delphi both have native string types.  They also have built in array bounds checking... and guess what, nobody has ever penetrated either with buffer exploits or overruns... That's gotta tell you something.

Well, Delphi IS Pascal, just a specific implementation of it... 
And I would not bank my money on the fact that this never has/will have happened, you can program a hell of a mess in any programming language, some just lend themself to this better than others... 

Oh and incase we don't speak before ... Happy new year, my friend.

Happy New Year to you as well...

Ralf

[CommonTater]

Well, that's all a matter of perspective and on priorities/purpose for the language written...

Don't misunderstand.  I like C well enough and I certainly understand the idea that hatched it.

But in any case, the way how strings can be used in any language doesn't really have anything to do with your subject of using stack or heap... 

Yeah it does...
 
I know how most people do string stuff with C and I've been pretty much following the crowd in that regard... char buffers on the stack, large arrays on the heap kind of thing... but even 7 years after moving from Pascal to C I still find myself constantly thinking there just has to be a better way to do certain things.
 
The first step in finding my way through all this is to discover and eliminate various means of doing things that are not worthwhile, hence my experiment and question...
 

Well, Delphi IS Pascal, just a specific implementation of it... 

A bastardization of Pascal is more like it.
 

And I would not bank my money on the fact that this never has/will have happened, you can program a hell of a mess in any programming language, some just lend themself to this better than others... 

As my "Bad Ideas" folder will clearly attest...
 
 

[Bitbeisser]

But in any case, the way how strings can be used in any language doesn't really have anything to do with your subject of using stack or heap... 

Yeah it does...
 
I know how most people do string stuff with C and I've been pretty much following the crowd in that regard... char buffers on the stack, large arrays on the heap kind of thing... but even 7 years after moving from Pascal to C I still find myself constantly thinking there just has to be a better way to do certain things.

Well, look how Delphi (or FreePascal for that matter) actually handles strings in the same context. You will see that there isn't much of a technical difference, you are just doing things more "by hand" in C in this case, so it is more obvious that there are differences. It's not a general issue either, I have written programs in the past that were actually a mix of C and Pascal modules. The only thing to really pay attention to and which is handled different by most compiler implementations is parameter passing, both in location (by value or by reference) and in the order of parameters, at least unless you explicitly set calling conventions to "_pascal" 

As I mentioned, there should be no real reason not to use the stack approach unless there is a technical (CPU) issue in that regards. Going astray here will rather cause you problems in the long run I guess...

Ralf

[CommonTater]

As I mentioned, there should be no real reason not to use the stack approach unless there is a technical (CPU) issue in that regards. Going astray here will rather cause you problems in the long run I guess...

Actually Pascal handled strings much differently than C does...

It was perfectly legal in Pascal to use...  if string1 < string2 then... and a whole series of other functions involving strings... concatenation was done with +, etc.  But the biggest difference is that strings were created on the heap and reference counted so you didn't need to free them. 

I doubt I'll ever get that far in C. 

The idea of getting away from the stack approach is actually 2 fold...
First, it reduces stack usage considerably and having hit a few stack overflows in my day, that does matter to me. In the heap approach only a 4 or 8 byte pointer is placed on the stack... not the 10K string.

Second I'm also looking at this syntactically.  I think my big problem lies here... Strings in C are *awkward*. 

Which flows more naturally...

Code: [Select]

char str1[100];
char str2[100];
strcpy(str2,str1);
Or...

Code: [Select]

string str1,str2;
str2 = CopyOf(str1);

I've been writing functions like StrInsertChars(), StrDeleteChars(), StrReplaceChars() and such into my code since I began with C and I'm thinking maybe it's time I did something a little more formal with them.