Thread: Question about memory taken by list structur.

  1. #1
    Registered User
    Join Date
    May 2005
    Posts
    76

    Question about memory taken by list structur.

    Hi,
    I need to use a list structure in my program. I don't use STL list but my own (very simple one, I don't need very sophisticated functions):
    Code:
    class element
    {
    public:
            int     i;
            element *next;
            element()
            {
                    i=0;
                    next=NULL;
            }
    };
    
    class _list
    {
    public:
            element *start,
                    *last;
            _list()
            {
                    start=NULL;
                    last=NULL;
            }
            int add(int);
    };
    
    int _list::add(int i)
    {
            element *new_;
            new_=new element;
    
            new_->i=i;
            new_->next=NULL;
    
            if(last==NULL)
            {
                    start=new_;
                    last=new_;
            }
            else
            {
                    last->next=new_;
                    last=new_;
            }
            return 0;
    }
    And then I have such short code:
    Code:
    _list   L[1000000];
    
    int main()
    {
            for(int i = 0; i < 1000000; i++)
                    L[i].add(i);
            return 0;
    }
    So I have an array of 10^6 lists. And then to each list L[x] I add one element. So the memory taken by that structure should be something like 19 mb (main list class - 2 pointers each 4 bytes, so it's 8 *10^6/1024/1024 = 7.6 Mb; then we have 10^6 elements, each one has a 1 pointer (4b) and integer number (8b) so it's 12*10^6/1024/1024 = 11.4Mb, to if we sum it up to should be ~ 19 Mb). But when I add sleep(1000) before returning the main function and run ps aux I have:
    $ ps aux
    USER PID %CPU %MEM VSZ RSS TT STAT STARTED TIME COMMAND
    apacz 3431 22.4 9.8 25780 24716 p0 S+ 10:36PM 0:00.72 ./my_program
    25780Kb? 25Mb? How? Can any one explain me that?
    Regards,
    apacz

  2. #2
    Super Moderator Harbinger's Avatar
    Join Date
    Nov 2004
    Posts
    74
    Allocation isn't free, there's additional overhead in your attempt to allocate say 8 bytes for your element.

  3. #3
    Registered User
    Join Date
    May 2005
    Posts
    76
    Thx for reply. But I really don't have such extra memory. Is it possible to allocate exactly what I want and nothing more ?

  4. #4
    Super Moderator Harbinger's Avatar
    Join Date
    Nov 2004
    Posts
    74
    > But I really don't have such extra memory
    Huh?
    It's all virtual, what are you complaining about?

    > Is it possible to allocate exactly what I want and nothing more ?
    Yes, use an array.

  5. #5
    Registered User
    Join Date
    Sep 2004
    Posts
    197
    its part of the runtime and OS, it has markers to show where allocated memory begins and ends. The memory usage also has to do with your actual code in memory, so the size of the binary you end up with maters as well. One suggestion, is striping the binary which might help get rid of excess debug information and the like.

    If your working in an embeded enviorment, then your might want to rethink your design, such as using arrays as pools of usable memory.
    If any part of my post is incorrect, please correct me.

    This post is not guarantied to be correct, and is not to be taken as a matter of fact, but of opinion or a guess, unless otherwise noted.

  6. #6
    Registered User
    Join Date
    May 2005
    Posts
    76
    Quote Originally Posted by Harbinger
    > But I really don't have such extra memory
    Huh?
    It's all virtual, what are you complaining about?
    > Is it possible to allocate exactly what I want and nothing more ?
    Yes, use an array.
    But I need a list or another structure in which I can add elemets one by one, not to alloc at the beggining, let's say 200 elements and then fill it... is there any way ?

  7. #7
    Super Moderator Harbinger's Avatar
    Join Date
    Nov 2004
    Posts
    74
    Then live with the overheads of the standard allocator.

    Or since this is C++, write your own new() which doesn't have any overheads.

  8. #8
    Registered User
    Join Date
    May 2005
    Posts
    76
    Do you think that it would solve the problem? I tried to replace the piece of code where is allocation by new to malloc fro <cstdlib> but it was as same as with new.

  9. #9
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Do you think that it would solve the problem? I tried to replace the piece of code where is allocation by new to malloc fro <cstdlib> but it was as same as with new.
    new isn't exactly the same as malloc. In C++ you should use new, because malloc doesn't call the constructor for the new object[s].
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  10. #10
    Super Moderator Harbinger's Avatar
    Join Date
    Nov 2004
    Posts
    74
    What problem?

    Since new() is just malloc and calls to constructors all wrapped up, it's hardly surprising the result was the same.

  11. #11
    Registered User
    Join Date
    May 2005
    Posts
    76
    Quote Originally Posted by Harbinger
    What problem?

    Since new() is just malloc and calls to constructors all wrapped up, it's hardly surprising the result was the same.
    For me too.
    Regards.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list question
    By brb9412 in forum C Programming
    Replies: 16
    Last Post: 01-04-2009, 04:05 PM
  2. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 01:21 PM
  3. List Question
    By ConsulVortex in forum C++ Programming
    Replies: 3
    Last Post: 01-14-2006, 04:38 AM
  4. pointers
    By InvariantLoop in forum C Programming
    Replies: 13
    Last Post: 02-04-2005, 09:32 AM
  5. compiler build error
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-30-2003, 10:16 AM