Thread: Problem using std::for_each

  1. #16
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by pheres View Post
    What exactly is the drawback using containers of pointers?
    Who owns those objects?

  2. #17
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Allocation overhead, reference counting overhead, loss of locality of reference, and there's simply no good reason to do it. (Unless there is one. But that's a case by case issue.)
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #18
    Registered User
    Join Date
    Nov 2006
    Posts
    519
    I see. One more question: What exactly does allocation overhead mean?

  4. #19
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by pheres View Post
    I see. One more question: What exactly does allocation overhead mean?
    If you use new to create an object, memory must be allocated. This is expensive compared to global and local variables. The allocator takes a certain amount of time to execute, it can scatter objects across memory in funny ways, and it can fragment memory.

  5. #20
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    It means all the wasted memory and time that comes from dynamically allocating something on the heap. You need space to store the pointer to the object. The runtime library needs space to store heap management information. And the runtime needs time to find a free spot on the heap and update the management information.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  6. #21
    Registered User
    Join Date
    Nov 2006
    Posts
    519
    Thanks. Until now I never though about wasting time using dynamical allocation.
    I'm going totally off-topic now, but I find this to interesting..

    So I guess the heap management and allocation algorithm is OS dependent? And is the allocation time constant or can it be expressed as depended from any parameters, maybe the fragmentation rate?
    And what always wonders me: why is stack so fast? look at that little example:
    Code:
    int main()
    {
     int a;  // push a
     int b;  // push b
    
     printf(%i, a); // pop b, pop a, print a, push a, push b
     
     printf(%i,b); // pop b, print b, push b
    }
    does the process stack work that way? if so, I guess the compiler can optimize a lot, the last pop and push b for example and push/pop are also very fast operations (1 clock tick each, right?). but for a lot of global and automatic variables, doesn't this become slow? maybe even slower than dynamic allocation? And where do all the pop'ed values go, if the cpu runs out of registers? for example if I read an vector element hidden deep in the stack?

    I guess it just doesn't work that way.

  7. #22
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Quote Originally Posted by pheres View Post
    So I guess the heap management and allocation algorithm is OS dependent?
    OS dependent and runtime library dependent. MinGW's C library might well have a different algorithm than the MS CRT.

    And is the allocation time constant or can it be expressed as depended from any parameters, maybe the fragmentation rate?
    Depends on the algorithm. Most will probably be slower when there's bad fragmentation.

    Code:
     int a;  // push a
     int b;  // push b
    Perhaps push. Perhaps just registers. Perhaps - most likely - just an increase in the stack pointer.

    Code:
     printf(%i, a); // pop b, pop a, print a, push a, push b
    Oh no, not at all. This is a function. It's more like, push string address, push a, call printf, reset stack pointer. (No need to pop arguments individually.)

    Code:
     printf(%i,b); // pop b, print b, push b
    In fact, the compiler may just leave the string address there, since it's the same as before. Push b, call printf, reset stack pointer.

    does the process stack work that way?
    Close. However, the process stack allows direct access to elements not on the top. It's after all just memory. No need to pop anything off to access an element further down; just read at an offset from the stack pointer.

    if so, I guess the compiler can optimize a lot
    An enormous lot. You can tell your compiler to write out the assembly it generates. It can be interesting. Make sure you compile in release mode.

    push/pop are also very fast operations (1 clock tick each, right?).
    No, they're memory accesses. That makes them pretty slow, actually. Although, since the top of the stack is basically always in L1 cache, they're as fast as memory accesses get.

    but for a lot of global and automatic variables, doesn't this become slow? maybe even slower than dynamic allocation?
    No. First, global variables have nothing to do with the stack. Also, at worst it's an indirect memory access, to memory that is most likely in cache. (Unlike some heap memory lying around somewhere in the huge expanses of memory. Those are only in the cache if they were recently used.)

    And where do all the pop'ed values go, if the cpu runs out of registers? for example if I read an vector element hidden deep in the stack?
    As I said, no need to pop.

    You should study computer architecture a bit.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  8. #23
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by CornedBee View Post
    Code:
     printf(%i, a); // pop b, pop a, print a, push a, push b
    Oh no, not at all. This is a function. It's more like, push string address, push a, call printf, reset stack pointer. (No need to pop arguments individually.)
    Actually it more likely pushes "a" first, then the string. But that doesn't matter really. Also, there's no reason it has to even pop the arguments after the function call. Many compilers will allow quite a few function call parameters to build up on the stack then pop them all at once. Called "deferred pop."

  9. #24
    Registered User
    Join Date
    Nov 2006
    Posts
    519
    Quote Originally Posted by CornedBee View Post
    You should study computer architecture a bit.
    That's true. But until then this gives me a lot to thing about, thank you. and brewbuck too

  10. #25
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Quote Originally Posted by brewbuck View Post
    Actually it more likely pushes "a" first, then the string.
    True. Stupid mistake.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  11. #26
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by brewbuck View Post
    Actually it more likely pushes "a" first, then the string. But that doesn't matter really. Also, there's no reason it has to even pop the arguments after the function call. Many compilers will allow quite a few function call parameters to build up on the stack then pop them all at once. Called "deferred pop."
    Actually, the order of argument pushing [if arguments are pushed at all] is dependant on the compiler you are using, and the settings[1], so there's no guarantee which is pushed first or last. Many compilers also allow passing args in registers. It is quite "normal" to push the arguments "right to left", but there's absolutely no guarantee that this is how the compiler does things.

    [1] printf() and other variable parameter functions are sort of exceptional in this case, because it becomes very difficult to find out where the "last fixed argument" (format string in printf's case) is on the stack if you don't push the fixed args last.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help understanding a problem
    By dnguyen1022 in forum C++ Programming
    Replies: 2
    Last Post: 04-29-2009, 04:21 PM
  2. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  3. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  4. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  5. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM