#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2012
    Posts
    75
    Rep Power
    3

    Huge linked list hangs Ubuntu 12.04


    I wrote a simple linked list program which inserts around 10^8 integers into a list.
    When I ran the program, all things started lagging. Mouse moved slowly, firefox hanged and overall Ubuntu became slow for quite a while.

    I want to know the reason behind this. I believe each program has fixed amount of memory allocated to it. So if the memory exceeded it should give SegFault or something. I can't find any reason for this lagging.
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,417
    Rep Power
    1871
    Let's examine the amount of memory this might consume.

    For 100M allocations for a simple linked list, consisting of an integer (4 bytes) and a next pointer (4 bytes), that's 800MB of memory.

    But wait, there's more.
    Each allocation has a certain amount of bookkeeping maintained by the runtime library. At a bare minimum, this would be the size of the allocated block (4 bytes) and a pointer to the next block (another 4 bytes)
    So that overhead itself is another 800MB.

    Now in order to minimise memory fragmentation issues, small malloc requests are often rounded up in size. You might be asking for only 8 bytes, but the amount of space actually allocated may be larger.

    Here's an example.
    Code:
    $ cat foo.c
    #include<stdio.h>
    #include<stdlib.h>
    
    struct foo {
      int a;
      struct foo *next;
    };
    
    int main()
    {
      int i;
      struct foo *p[5];
      for ( i = 0 ; i < 5 ; i++ ) {
        p[i] = malloc( sizeof(struct foo) );
      }
      printf("Size of struct=%zd\n", sizeof(struct foo));
      for ( i = 0 ; i < 5 ; i++ ) {
        printf("%p\n", p[i] );
      }
      return 0;
    }
    $ gcc foo.c
    $ ./a.out 
    Size of struct=16
    0x692010
    0x692030
    0x692050
    0x692070
    0x692090
    The size of the struct is 16 bytes, but the stride between adjacent allocations is 32 bytes.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2012
    Posts
    75
    Rep Power
    3
    Okay, it seems over 1GB of memory is being used in this program. This means there is lot of swapping and the OS has to go back and forth between hard disk and main memory. Is that the reason for lagging?

IMN logo majestic logo threadwatch logo seochat tools logo