Thread: Memory allocation problem

  1. #1
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681

    Memory allocation problem

    The attached file has the source code. The purpose of the program is to
    Purpose: This program is designed to create a list of sectors that randomily connect to other sectors.
    Every sector needs to be accessible, either directly or via another sector, by the root sector (0).
    Each sector can connect to 1-6 other sectors. It is not required that a sector connect to a sector that connects to it. To clarify: Sector 5 connects to sectors: 3, 100, 238, and 584. None of these sectors are required to connect to sector 5 but they still may.
    The program will then go and verify that each sector is reachable from sector 0. If not it will randomily assign sectors to point to that those unreachable sectors. It will continue to do this until all zones are reachable.
    The program will then go and make sure that each sector is able to reach sector 0. To save time if it reaches a sector that has been verified to be able to reach sector 0 it will conclude that sector in question is able to reach sector 0.
    It compiles fine using GCC on Debain, GCC on Win XP, and Borland 5.02 on Win 2k.

    The problem lies in when you specify too many sectors I'll get segmentation faults. On the debain machine (which is a lot older and has less memory then the other two) I can specify 100,000 sectors and it will run fine.

    I am thinking that there is a limit on how big of a block of memory you can assign. Can anyone find another reason for this?

    Note: The formating got a little screwy when I loaded it into Borland. I tried to fix it and I hope it displays correctly on your IDE.

    Note 2: Overall I'm happy with this code. On the 667 mhz debain machine doing 150,000 sectors it only took abot 3.5 mins.

    Edit: made purpose a little more detailed.
    Last edited by Thantos; 01-22-2004 at 03:34 PM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    No idea here I'm afraid.

    I ran your code with the electric fence malloc debugger, and it didn't spot any out of bound accesses (up to 100K sectors).

    Your malloc calls are all followed by a NULL test, so nothing wrong there either.
    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.

  3. #3
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    >Can anyone find another reason for this?

    Too many recursions?
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  4. #4
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Too many recursions?
    This is the first program I've used recursion in so I'm not sure if thats a problem or not. I'll add some test code to try and isolate where the exact fault is occuring.

    And thanks for looking you two.

  5. #5
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Thanks Dave, that indeed was the problem. It was at 104674 recursions deep when it crashed. Looks like I'll have to do structure the way I do the check. Not sure how just yet but I'll figure out another way.

    Of course I could just enforce a more practical limit

    But it was not for lose, learned how useful recursion could be

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Ah, windows doesn't grow the stack on demand, unlike the unix/linux operating systems.
    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.

  7. #7
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Well I made some changes to the way it does it checking to use fewer number of recursions.

    Interestingly enough the higher the number of sectors the more effiecent the program becomes in regards to number of recursions vs the number of sectors.

    On the xp machine for 200,000 sectors my max depth on recursion was ~4% or 8000. And it runs faster to boot.
    Hmm the debain machine is giving me about 20% or 40000 recursions.

    Well in case anyone is interested I'm attaching the code.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem with linked list and shared memory
    By Sirfabius in forum C Programming
    Replies: 10
    Last Post: 11-10-2008, 04:45 PM
  2. Memory leaks problem in C -- Help please
    By Amely in forum C Programming
    Replies: 14
    Last Post: 05-21-2008, 11:16 AM
  3. Dynamic memory allocation.
    By HAssan in forum C Programming
    Replies: 3
    Last Post: 09-07-2006, 05:04 PM
  4. Understanding Memory Allocation
    By Ragsdale85 in forum C Programming
    Replies: 7
    Last Post: 10-31-2005, 08:36 AM
  5. Memory Problem - I think...
    By Unregistered in forum C Programming
    Replies: 4
    Last Post: 10-24-2001, 12:14 PM