My memory manager

[proxy]

Memaker, easy:

Code: Select all

node **ptr = &list;
while(*ptr != NULL) {
    if(*ptr == item3) {
        *ptr = *ptr->next;
         break;
    }
    ptr = &ptr->next;
}

simplicatico

[bkilgore]

And I dont see how I can do this Without traversing the list(or having a previous pointer)?

@proxy: I'm not sure how this is doing it without traversing the list....

Using double-pointers does make it easy to change lists, but not if you only have a single-pointer to somewhere in the middle and want to change something before it. With a previous pointer, updating would be O(1), but with tranversing the list it becomes O(n).

[proxy]

oh i see, you want to not traverse at all

well then you need a prev pointer ..

oh well

proxy

[Dreamsmith]

Yeah, requirement #1 of my malloc implementation is that it must be able to guarentee that it will return from malloc or free under a certain amount of time, no matter how large the free lists get. I set a flag each call specifying whether I'm more concerned with speed or memory efficiency. If I'm in "fast" mode, there are no indefinite loops, no list traversals, etc. The number of instructions executed can vary depending on certain branches (if/else statements), but there's a guarenteed maximum. I actually maintain an array of 28 freelists -- freed blocks get spliced into the freelist specified by BSR(blocksize)-4. In memory efficient "slow" mode, when a block is requested of a specified size, I go to the freelist that holds blocks with a BSR of that size and traverse it until I find a block large enough to satisfy the request. In "fast" mode, I just add 1 to the BSR result, which guarentees that the first block examined will be large enough to satisfy the request. This tends to fragment memory a tad more than "slow" mode, but that's a small price to pay for O(1) performance when you need it.

[Memmaker]

Well I?ve rewritten the entire manager (only using 8 bytes header, storing freed blocks in 28 different lists). Then problem is: Suppose I want to allocate 12 bytes of memory. Then I look in the "9-16 bytes" list. If I find something there, I use it. But if I dont, should I get up and look in the other lists (which mean I can find a block with the size of 50) and use it, or should I simply "extend" the memory (allocate a completly new memory-area, as if I didnt find a freed block to use).

[Dreamsmith]

Just bump up to the next higher freelist, at which point you can simple take the first entry, since any entry in any higher freelist is guarenteed to be large enough. If the next higher freelist is empty, bump up again. You don't need to grab more core unless you bump past the 2GB-4GB freelist without finding a non-empty list.

[distantvoices]

@dreamsmith:

Hmmm ... your ideas/concepts are intrigueing (is that written correctly?)

So I have a question:
What, if I only store a prev?ous/next pointer in the bookkeeping data, and the rest of information, esp.: Size of allocated chunk - at the end of the chunk? it would require 16 bytes of book keeping information, but the advanced speed of allocation and freeing might be worth the 'waste'.

The previous/next pointers would render alloc and free operations O(1), if I understand this correctly - and if the free chunks are ordered in size ranges.

If I'm right, this would make my own implementation more stable and faster - it's done by one who does such a thing the very first time - and I'm not satisfied with it.

STay safe

[Pype.Clicker]

So I have a question:
What, if I only store a prev?ous/next pointer in the bookkeeping data, and the rest of information, esp.: Size of allocated chunk - at the end of the chunk?

Just a consideration: your processor has a cache, which works by *lines* (32 bytes). When you request a dword, you usually get 8 for the price of 1 from the main memory ... Keeping things that are accessed together close from each others helps things keeping fasts.

All things being equals, traversing a N-entries tables of pointers may be up to 8 times faster than traversing a N-sized list ...

[Memmaker]

beyond infinity:
I dont know if I understand you right, but you dont need 16 bytes of data(even if you want to store the size two times and two pointers) since the only type of chunk that requires a next/previous pointer is a freed one.

Insteasd you can use the "real data" inside the available chunk to store the pointers, the chunk is freed and it doesnt matter if you mess around with the data in it. This might seem a little bit bad cause it requires all chunks to be at least 8 bytes (so you are sure that there?ll be enough space for the pointers), but it doesnt matter. For a chunk larger than 8 bytes you save 8 bytes this way(smaller header). For a chunk smaller than 8 bytes, you have to allocate 8 bytes, but you would have been forced to do this anyways (just that the extra space would be in the header).

[BI lazy]

It's not about the free list, but about issueing free(address).

how shall a freed chunk of memory know its size(excl. bookkeeping data), if it isn't stored somewhere?

keep different sort of bookkeeping data types?

one with only the size and one with the two pointers?

I currently work with two linked lists: one for free chunks and one for used chunks in order to issue free without the risk to cause undefined behaviour in case of freeing an unallocated or already freed memory area.

[Memmaker]

For Allocated blocks, my chunks looks like this:

SIZE
[the DATA, "SIZE" bytes]
0

For a free block, the chunk looks like this:

SIZE
Pointer to the next/prev chunk
[DATA, "SIZE"-bytes - 8, the pointers used 8 bytes of this space];
SIZE

this way I can look at the last 4 bytes to see if a chunk is allocated or not (if it?s used, the last 4 bytes are zero). I use something like this:

struct memory_chunk {
unsigned long size;
struct memory_chunk *next, *prev;
unsigned long *size2;
}

Then I set
some_block->size2 = (unsigned long)some_block + 4 + some_block->size;

this way the header will only be 8 bytes (16 bytes for a free chunk but who cares). then suppose you want to use free(address), you can have it something like this:

void free(void *address) {
memory_chunk *some_block= (memory_block)((unsigned long)address-4);'
some_block->size2 = (unsigned long)some_block + 4 + some_block->size;
if(*some_block->size2 == 0)
// The block is used, can be freed
else
// The chunk?s allready free
}

[Pype.Clicker]

just to let you know, i've added this thread to the 'related threads' of Allocating & Freeing Memory in the FAQ.

[Dreamsmith]

@dreamsmith:

Hmmm ... your ideas/concepts are intrigueing (is that written correctly?)

So I have a question:
What, if I only store a prev?ous/next pointer in the bookkeeping data, and the rest of information, esp.: Size of allocated chunk - at the end of the chunk?

If you only store a prev/next pointer in the bookkeeping data, you've already stored all the information you'll ever need for an allocated chunk. Why are your trying to use more bytes to store the size? The size is equal to ptr.next - ptr. Don't store anything at all at the end of the chunk. That's rather inconvenient, in addition to being completely unnecessary.

Now, blocks in the free lists require a bit more than the 8 bytes in the header, that's why in the code I posted above they have the extra two pointers. But understand there is no other bookkeeping data besides what's declared in that code. 8 bytes is all you need for an allocated block, ever. 16 bytes is needed for the freed blocks, but they just reuse the same memory that for allocated blocks is used for the application data. You never need to store the size, ever. You always know it. It is always ptr.next - ptr. No need to store what you can calculate in a couple of nanoseconds (indeed you can probably calculate it faster than you could perform a memory fetch, assuming the other information is already in registers).

The previous/next pointers would render alloc and free operations O(1), if I understand this correctly - and if the free chunks are ordered in size ranges.

Yes, mostly. Calls to free() under this scheme are always O(1), and calls to malloc() are optionally O(1), if you start your "search" on the next higher freelist than you otherwise might. And even when you don't need O(1) allocations, it's still pretty damn fast (worst case performance would be O(n), but average case is going to be pretty short -- in fact, assuming random sized allocations and frees, on average you will examine 1.5 entries in the freelist before satisfying the request. If you frequently allocate and free blocks of a particular size, the average drops closer to 1. Still, when you NEED O(1), just start looking in the next higher list to guarentee your first hit is a good one. I wrote my malloc specifically to work in an environment where I had to be guarenteed a result in a fixed amount of time, then added the functionality to take a little longer [and fragment memory a bit less] when I could afford to).