memory allocator project ...

[James Ladd]

All,

Would anyone like to work on a memory allocator project for win32 and possibly linux ?
This project would be released under the MIT license.

The project is to write an allocator that is fast and makes the most of memory with
very little fragmentation and allocation/management overhead.

I'd write this myself but I dont have a 'lot' of free time. It's also not on a critical time-/path
so it could be done over a long period. I'd like to run it here as a community project with some
main people driving things.

Maybe if its proven to be a great allocator then linux could make use of it as well as other p
projects. I see a need for this in my own stuff.

Before you sign-up or comment please read some of the doco available online to do with
memory allocation and the work done from around 1960 - 1996.

I look forward to participating with other in this project.

rgs, James.

[James Ladd]

Is everyone too busy ?

[zooba]

Pretty close to too busy, I'm not real keen on picking up another project :wink

Have you looked through some of the older Laboratory posts? There was a lot of benchmarking done with the Windows functions and some contributed ones, IIRC, designed for lots of small allocations. It's probably worth a look.

Cheers,

Zooba :U

[James Ladd]

thanks for the suggestions.

What I am looking at is an allocator that can be proven to be effective in both memory allocation
and fragmentation. ie: Allocates memory with little overhead and little fragmentation.

There are a lot of allocators out there, but im yet to see any with good supporting proof
of the above characteristics.

[KSS]

James Ladd, why You not use MS Heap function? :eek

Platform SDK: Memory Management
Low-fragmentation Heap
Heap fragmentation is when available memory is broken into small, non-contiguous blocks. When this occurs, memory allocation can fail even though there is enough memory in the heap to satisfy the request, because no one block of memory is large enough to satisfy the allocation request.


For applications that have a low memory usage, the standard heap is adequate; allocations will not fail due to heap fragmentation. However, if the application allocates memory frequently and uses a variety of allocation sizes, memory allocation can fail due to heap fragmentation.

Windows XP and Windows Server 2003 family introduce the low-fragmentation heap (LFH). This mechanism is built on top of the existing heap, but as the name implies, it reduces fragmentation of the heap. Applications that allocate large amounts of memory in various allocation sizes should use the LFH. Note that the LFH can allocate blocks up to 16 KB. For blocks greater than this, the LFH uses the standard heap.

To use the LFH in your application, call the HeapCreate or GetProcessHeap function to obtain a handle to a standard heap. Then call the HeapSetInformation function to enable the LFH. When you call the heap API, memory is allocated and freed in this heap.

The LFH avoids fragmentation by managing all allocated blocks in 128 predetermined different block-size ranges. Each of the 128 size ranges is called a bucket. When an application needs to allocate memory from the heap, the LFH chooses the bucket that can allocate the smallest block large enough to contain the requested size.

The smallest block that can be allocated is 8 bytes. The granularity of the first 32 buckets is 8 bytes. The first bucket is used for allocations between 1 and 8 bytes in size. The next bucket is used for allocations between 9 and 16 bytes in size, and so on until the 32nd bucket, which is used for allocations between 249 and 256 bytes in size. The granularity of buckets 33 to 127 is 16 bytes. The 33rd bucket is used for allocations between 257 and 272 bytes in size. The 34th bucket is used for allocations between 273 and 288 bytes in size, and so on. The final bucket (128th) is used for allocations between 15,873 and 16,384 bytes in size.

For example, if an application needs to allocate 10 bytes of memory, the smallest block size that can accommodate this request is 16 bytes. Bucket two is used for allocations that are 16 bytes in size, therefore, the LFH will allocate the memory from bucket two.

If the allocation is not a multiple of eight, there will be unused bytes. This is another form of fragmentation called internal fragmentation. The LFH was designed to balance internal and external fragmentation.

[James Ladd]

KSS,

Thats a good suggestion, however Im wanting some information on how well that allocator does
in managing the memory and stoping fragmentation. I havent found any really detailed info on
this for that allocator.

That allocator looks like a good start as a base for providing memory and Ill look into it further.

Rgs, James.

[KSS]

James,

Code Select Expand

however Im wanting some information on how well that allocator does in managing the memory and stoping fragmentation
I know how it very interestingly, but you must understand for what you spend your time... and maybe more trust to MS. MS guys provide memory manager FOR YOU {and for me, and for all other :bg }, they have done hard work and created MemMan which work good as they thinks.

But if you want MemMan for special things... I have 3-5 days rest time (almost). So if you say(write) me requirement for MemMan (work with small MemBlocks or not; ratio: Speed/MemEconomy;etc.) I think about how your requirement realize and write code (without visualization memory use)

Just for info: To get info about used MemoryBlocks use HeapWalk(). And if need do visual window that display info (such as defragmentation program)

[James Ladd]

KSS,
I think the task would take more than just a few days, however, feel free to propose a policy and approach for
allocating memory such that the allocation is fast, has low overhead (memory wastage) and causes little
fragmentation.
Rgs, James.

[KSS]

James, you want ideal MemMan!?!

At this time I use this macros:

Code Select Expand

;————————————————————————————————————————————————————————————————
MemMan_GetMem MACRO nMemSize:REQ
PUSH PAGE_READWRITE
PUSH MEM_COMMIT
PUSH nMemSize
PUSH NULL
CALL VirtualAlloc

     IFDEF DEBUG
     .IF EAX==0
      IFDEF UNICODE
      invoke FatalAppExitW,0,uni$("MemMan_GetMem:VirtualAlloc=0")
      ELSE
      invoke FatalAppExitA,0,CTXT("MemMan_GetMem:VirtualAlloc=0")
      ENDIF
     .ENDIF
     ENDIF
ENDM
;————————————————————————————————————————————————————————————————
MemMan_FreeMem MACRO lpAddress:REQ
INVOKE VirtualFree,lpAddress,0,MEM_RELEASE

     IFDEF DEBUG
     .IF EAX==0
      IFDEF UNICODE
      invoke FatalAppExitW,0,uni$("MemMan_FreeMem:VirtualFree=0")
      ELSE
      invoke FatalAppExitA,0,CTXT("MemMan_FreeMem:VirtualFree=0")
      ENDIF
     .ENDIF
     ENDIF
ENDM
;————————————————————————————————————————————————————————————————
MemMan_RealocateMem MACRO lpAddress:REQ,nMemSize:REQ
MemMan_FreeMem (lpAddress)
MemMan_GetMem (nMemSize)
MOV [lpAddress],EAX ;This string is not need
ENDM
;————————————————————————————————————————————————————————————————

P.S. The ideal does not exist! But I shall try to write this.

[James Ladd]

I think the 'ideal' does exist, as its a relative term.
I think you will also find this ideal and look forward to seeing what you do.

How are you going to measure the suitability of the allocator ?

[KSS]

Suitability?
Suitability is known before program/functions are will write by programmer, I think.
+ Synthetic speed/MemoryUse test + Info from some program: ProcessExplorer(www.sysinternals.com) + Debug function in MemAllocator.

Now I think that MemMan may use Virtual Memory Functions for get free mem and internally manage blocks of memory that smallest that PageSize (4096bytes on my comp)(such as Low-fragmentation Heap)
So what you think about? Have you any suggestion?

Can you see error in my MemMan_RealocateMem() macros? If saw why you not told me about this?

[James Ladd]

KSS,

I didn't see an error in the allocator macros or yes I would have suggested this to you.

My suggestion for the allocator is:

1. Form a hypothesis as to which approach and policy is going to be best. Then write a test
    to prove or dis-prove the hypothesis.
    By policy I mean the algorithm you are going to use and you choice of when to coales (sp?)
    the free space.

2. Run the tests and report the results.

3. Try with different allocators made available from the OS, if the OS provides them.
    eg: HeapAlloc vs VitualAlloc etc.

To do a proper evaluation you will need a good symulation for allocations and de-allocations.
I don't advise using a random number driven allocation as this isnt really a good representation
of the real world. Instead Id suggest reading an exe byte by byte and if the byte is even
allocate and if its not, deallocate. This way, each run over the same exe would produce the
same allocation/deallocation pattern which can be used to verify different allocators and
your policy for allocation/deallocation and coalecing the free-space.

How does this sound ?

Rgs, James.

[KSS]

James,
• VitualAlloc() is the best way for speed (I decided this many years ago) {Look: QMemory 2.01}
• Sound good idea about "reading an exe"!
Now I am start to write code.

Look to: «Reply #8 on: 26-06-2006, 21:45:51»

[James Ladd]

KSS,

Im sure you are correct about VirtualAlloc, however, having some code and output that
others can see and compare is always invaluable. It really helps if you can provide this.

When someone says "but what about using HeapAlloc, or XYZ" you can say run TestX
or just add it to function Y and test and this makes the who conversation easier.

I look forward to what you produce and trying it. Im also keen to plug-in other allocators
and see how they do. Maybe they will perform differently based on the algorithm you
come up with.

Don't forget that the best allocator will be one that is fast, uses available memory wisely
and can re-use fragmented free memory well.

I tried to attached a zipped document that covers the work on allocators from 1950 to today.
It's worth reading before you start coding, but it's too big. Is there some other way
I can get it to you?

Also, before you start coding, can we discuss the design. What approach do you have in mind?

Rgs, James.

[zooba]

• VitualAlloc() is the best way for speed (I decided this many years ago) {Look: QMemory 2.01}

For large blocks, this is true. Smaller blocks are much faster with the Heap functions. However, I believe this is a recent change, with Microsoft spending the last few years (ie. after you made your decision :wink ) optimising the heap functions.

Of course, since you are doing your own allocation, a huge block from VirtualAlloc is definitely the way to go :thumbu

Cheers,

Zooba :U