I apologize in advance if this is an incredibly dumb question...
Currently I have a circular linked list. The number of nodes is normally held static. When I want to add to it, I malloc a number of nodes (ex. 100000 or so) and splice it in. This part works fine when I malloc the nodes one by one.
I want to attempt to allocate by blocks:
NODE *temp_node = node->next;
NODE *free_nodes = malloc( size_block * sizeof( NODE ) );
node->next = free_nodes;
for ( i = 0; i < size_block - 1; i++ ) {
free_nodes[i].src = 1;
free_nodes[i].dst = 0;
free_nodes[i].next = &free_nodes[i+1];
}
free_nodes[size_block - 1].next = temp_node;
The list works as long as I don't attempt to free anything ('glibc detected: double free or corruption' error). Intuitively, I think that is because freeing it doesn't free the single node, and looping through the normal way is attempting to free it multiple times (plus freeing the entire block probably screws up all the other pointers from the nodes that still exist?), but:
- Could somebody please explain to me explicitly what is happening?
- Is there a way to allocate the nodes by blocks and not break things?
The purpose of this is because I am calling malloc hundreds of thousands of times, and it would be nice if things were faster. If there is a better way around this, or I can't expect it to get faster, I would appreciate hearing that too. :)
Heisenbug :
\n Could somebody please explain to me explicitly what is happening?\n\n\nExactly what you said. You are allocating a single space of contiguous memory for all blocks. Then if you free it, all memory will be released.\n\n\n Is there a way to allocate the nodes by blocks and not break things?\n\n\nAllocate different memory segments for each block. In your code (that isn't complete) should be something like:\n\nfor ( i = 0; i < size_block ; i++ ) {\n free_nodes[i] = malloc (sizeof( NODE ));\n}\n",
2011-09-24T02:00:28
Jens Gustedt :
First, the way you allocated your nodes in blocks, you always have to free the whole block with exactly the same start address as you got from malloc. There is no way around this, malloc is designed like this.\n\nPutting up your own ways around this is complicated and usually not worth it. Modern run-times have quite efficient garbage collection behind malloc/free (for its buffers, not for user allocations) and it will be hard for you to achieve something better, better meaning more efficient but still guaranteeing the consistency of your data.\n\nBefore losing yourself in such a project measure where the real bottlenecks of your program are. If the allocation part is a problem there is still another possibility that is more likely to be the cause, namely bad design. If you are using so many elements in your linked list such that allocation dominates, probably a linked list is just not the appropriate data structure. Think of using an array with a moving cursor or something like that. ",
2011-09-24T07:11:50