Offline dynamic memory allocation

[Steve Keller]

I need an offline dynamic memory allocation algorithm. That is, I
have a number of memory allocation requests each with size (in bytes),
allocation time and release time that I want to satisfy with one
contiguous memory segment of a given fixed size. All allocation
requests are known at program start time.

The allocation algorithm should give the memory allocation, i.e. the
memory address for each allocation request.

In the case that not all requests can be satified with the given
memory size I'd like to get a list of allocation that maximizes the
memory allocation, i.e. the sum of the products of used memory size
and time of usage should be maximal (as this would probably maximize
performance).

AFAIK, this is the offline dynamic memory allocation problem. Since
the number of requests can be up to 1000 I cannot try all
combinations. Also, AFAIK, the problem is NP complete.

So my question is: Is there an algorithm that computes an optimal
allocation in short time, say a few seconds or a minute (probably not
since NP completeness), and otherwise, is there an algorithm that
computes a good approximation in that time frame?

If have thought about variants of First-Fit and Best-Fit but I don't
know in which order to process the requests. Since I know all
requests in advance, I could sort by size first and then by allocation
time or vice-versa. If sorting by size, is ascending or descending
order better? Or are there better approaches?

Steve

[James Harris]

Post by Steve Keller
I need an offline dynamic memory allocation algorithm. That is, I
have a number of memory allocation requests each with size (in bytes),
allocation time and release time that I want to satisfy with one
contiguous memory segment of a given fixed size. All allocation
requests are known at program start time.
The allocation algorithm should give the memory allocation, i.e. the
memory address for each allocation request.
In the case that not all requests can be satified with the given
memory size I'd like to get a list of allocation that maximizes the
memory allocation, i.e. the sum of the products of used memory size
and time of usage should be maximal (as this would probably maximize
performance).
AFAIK, this is the offline dynamic memory allocation problem. Since
the number of requests can be up to 1000 I cannot try all
combinations. Also, AFAIK, the problem is NP complete.
So my question is: Is there an algorithm that computes an optimal
allocation in short time, say a few seconds or a minute (probably not
since NP completeness), and otherwise, is there an algorithm that
computes a good approximation in that time frame?
If have thought about variants of First-Fit and Best-Fit but I don't
know in which order to process the requests. Since I know all
requests in advance, I could sort by size first and then by allocation
time or vice-versa. If sorting by size, is ascending or descending
order better? Or are there better approaches?

I don't know of a formal algorithm but if I understand the problem there
are some things that might help.

1. Group the allocations by size, rounding up if necessary. For example,
if you have a load of requirements for 100 bytes and one for 95 bytes
round the latter up to 100 so that once it has been freed its space can
be used for a later 100-byte requirement.

2. Create a grid of requirements against time where there is one row for
each of your 1000 or so requests and the columns represent time between
events, later ones to the right. That would end up with a set of bars
like this

1 11111111 111111
2 222222222 22222 222222222
3 333333 333
4 44

except that the 'height' of a row would indicate its size and although
they appear the same in the above they will vary in reality.

3. Preallocate starting from the column which has the greatest total
height (the sum of all the occupied heights in that column), working
left and right.

4. While working out outwards from the highest column it will be like
playing tetris, fitting bars into freed spaces.

5. If you are prepared to move memory after its allocation then you
could run the whole thing in the space required by the highest bar.
Otherwise you may need to use a bit more than that indicated by the
highest bar.

[Rod Pemberton]

On Tue, 6 Apr 2021 17:00:14 +0200

Post by Steve Keller
I need an offline dynamic memory allocation algorithm. That is, I
have a number of memory allocation requests each with size (in bytes),
allocation time and release time that I want to satisfy with one
contiguous memory segment of a given fixed size. All allocation
requests are known at program start time.
The allocation algorithm should give the memory allocation, i.e. the
memory address for each allocation request.
In the case that not all requests can be satified with the given
memory size I'd like to get a list of allocation that maximizes the
memory allocation, i.e. the sum of the products of used memory size
and time of usage should be maximal (as this would probably maximize
performance).
AFAIK, this is the offline dynamic memory allocation problem. Since
the number of requests can be up to 1000 I cannot try all
combinations. Also, AFAIK, the problem is NP complete.
So my question is: Is there an algorithm that computes an optimal
allocation in short time, say a few seconds or a minute (probably not
since NP completeness), and otherwise, is there an algorithm that
computes a good approximation in that time frame?
If have thought about variants of First-Fit and Best-Fit but I don't
know in which order to process the requests. Since I know all
requests in advance, I could sort by size first and then by allocation
time or vice-versa. If sorting by size, is ascending or descending
order better? Or are there better approaches?

There are some memory allocators on the Internet (source code) and also
Wikipedia pages on different algorithms.

I can't vouch for the usefulness of the allocators available on the
internet as I've never looked at their algorithms or code. First three
links tracked down from 2012 a.o.d./c.l.f. posts of mine:

"A Memory Allocator," by Doug Lea (via Wayback)
https://web.archive.org/web/20060206090424/http://g.oswego.edu/dl/html/malloc.html

"The BGET Memory Allocator," by John Walker
http://www.fourmilab.ch/bget/

"Dynamic Storage Allocator," Richard Harter, comp.lang.c, Nov. 11, 1990
https://groups.google.com/g/comp.lang.c/c/KjMmhzBqoTo/m/4azixst9on0J

"SHMALL - Simple Heap Memory ALLocator"
https://github.com/CCareaga/heap_allocator#shmall---simple-heap-memory-allocator


Also, Wikipedia has pages describing various memory allocation
algorithms:

Buddy memory
https://en.wikipedia.org/wiki/Buddy_memory_allocation

Hoard memory
https://en.wikipedia.org/wiki/Hoard_memory_allocator

Memory pool aka fixed-size
https://en.wikipedia.org/wiki/Memory_pool

Slab allocation
https://en.wikipedia.org/wiki/Slab_allocation

SLOB
https://en.wikipedia.org/wiki/SLOB

SLUB
https://en.wikipedia.org/wiki/SLUB_(software)


If you test out any of these methods or allocators for performance,
please let us know what your results are.

[Steve Keller]

Post by Rod Pemberton
There are some memory allocators on the Internet (source code) and also
Wikipedia pages on different algorithms.
I can't vouch for the usefulness of the allocators available on the
internet as I've never looked at their algorithms or code. First three

I know some of the terms in your links and some of the actual
algorithms behind them. I think these are mostly online DSA
algorithms, i.e. without advance knowledge of all requests and
releases.

But I will look into every link and see how those allocators/ideas
could be adapted to the offline problem.

Thanks for your list.

Steve

[Alexey F]

I need an offline dynamic memory allocation algorithm. That is, I
have a number of memory allocation requests each with size (in bytes),
allocation time and release time that I want to satisfy with one
contiguous memory segment of a given fixed size. All allocation
requests are known at program start time.
The allocation algorithm should give the memory allocation, i.e. the
memory address for each allocation request.

...

A couple of thoughts...

If you could allocate and free in strictly opposite orders, that is, effectively
implementing a stack, you'd have you answer. Anything preventing you
from that? You could also task your allocator with establishing the order,
hence some waste/inefficiency.

If you care about physical memory but you also can have page translation
and there's no shortage of virtual address space, then you could calculate
the maximum number of page frames needed. There will likely be
some waste due to allocations rounding up to whole pages.

Alex

[Alexei A. Frounze]

I need an offline dynamic memory allocation algorithm. That is, I
have a number of memory allocation requests each with size (in bytes),
allocation time and release time that I want to satisfy with one
contiguous memory segment of a given fixed size. All allocation
requests are known at program start time.
The allocation algorithm should give the memory allocation, i.e. the
memory address for each allocation request.

...
A couple of thoughts...

If you could allocate and free in strictly opposite orders, that is, effectively
implementing a stack, you'd have you answer. Anything preventing you
from that? You could also task your allocator with establishing the order,
hence some waste/inefficiency.

If you care about physical memory but you also can have page translation
and there's no shortage of virtual address space, then you could calculate
the maximum number of page frames needed. There will likely be
some waste due to allocations rounding up to whole pages.

Alex

[Steve Keller]

Post by Alexey F
If you could allocate and free in strictly opposite orders, that is, effectively
implementing a stack, you'd have you answer. Anything preventing you
from that? You could also task your allocator with establishing the order,
hence some waste/inefficiency.

No. Allocation requests and releases can come in any order.

Post by Alexey F
If you care about physical memory but you also can have page translation
and there's no shortage of virtual address space, then you could calculate
the maximum number of page frames needed. There will likely be
some waste due to allocations rounding up to whole pages.

Also no MMU or page translation. Think of small embedded systems or a
linear and limited address space of a process.

Steve

[Rod Pemberton]

On Tue, 6 Apr 2021 17:00:14 +0200

Post by Steve Keller
I need an offline dynamic memory allocation algorithm. That is, I
have a number of memory allocation requests each with size (in bytes),
allocation time and release time that I want to satisfy with one
contiguous memory segment of a given fixed size. All allocation
requests are known at program start time.

...

You haven't responded to anyone since you posted. Are you still here?

Post by Steve Keller
All allocation requests are known at program start time.

Does that include the allocation time and release time, or just the
size in bytes? (My assumption is, yes, it includes the times too.)

If you know all information in advance, you can calculate the peak
memory you'll need to allocate, in advance. I.e., every allocation is
only "alive" or active from the allocation time to the release time, so
you just need a chart or array which adds up the bytes for each active
allocation on a per unit of time basis, e.g., second or minute. If the
allocations are randomized or of unknown ordering, compute it again,
repeat over and over.

Post by Steve Keller
AFAIK, this is the offline dynamic memory allocation problem. Since
the number of requests can be up to 1000 I cannot try all
combinations.

A computer program can easily brute-force or shotgun test 1000
allocations, and it can do this repeatedly, e.g., billions of times.
This can also be done without actually allocating memory, since you
know the allocations sizes in advance. So, I'm not sure what you're
getting at here as to why you can't try all the combinations, as you can
definitely easily compute all the potential combinations. Even if
you'd rather actually test all the allocations, there has to be a
computer out there somewhere where you can try out all the combinations.

Post by Steve Keller
So my question is: Is there an algorithm that computes an optimal
allocation in short time, say a few seconds or a minute (probably not
since NP completeness), and otherwise, is there an algorithm that
computes a good approximation in that time frame?

It seems that you're asking for something like a perfect hash, but
instead of a perfect hash, you want a perfect memory allocation or
allocator since you know the size and times in advance. I'm not aware
of anything like that.

The fact that you mentioned "NP complete," and seem to be limited for
computing time e.g., shared time on a mainframe, makes me think this may
be a homework assignment for a C.S. course or for a programming
competition. FYI, we don't do homework.

[Steve Keller]

You haven't responded to anyone since you posted. Are you still here?

Yes, I'm still here. I posted to comp.os.misc and alt.os.development
and waited for replies but didn't get any. In alt.os.development I
didn't even see my own posting so I checked with Google groups where
I'm reading this. My newsfeed doesn't seem to have alt.os.development
although I'm sure it had until recently.

It's not a homework assignment, but it's a somewhat academic interest,
evolved from a much simpler but somewhat similiar problem I had in an
embedded programming project.

Using Google I found it's called offline dynamic storage allocation,
it's still a research topic, it's NP complete, but there are
approximation solutions for simple cases (limited size of allocation
requests). After my posting I've found this paper on the topic:

https://www.researchgate.net/publication/221426830_New_Approximation_Algorithms_for_Some_Dynamic_Storage_Allocation_Problems

Does that include the allocation time and release time, or just the
size in bytes? (My assumption is, yes, it includes the times too.)

Yes. All requestes (size, start-time, end-time) are known in advance.
That's why it's called "offline" DSA.

And once storage is allocated to fulfill a request, it cannot be moved
afterwards. Otherwise, the problem would be extremely easy.

If you know all information in advance, you can calculate the peak
memory you'll need to allocate, in advance. I.e., every allocation is
only "alive" or active from the allocation time to the release time, so
you just need a chart or array which adds up the bytes for each active
allocation on a per unit of time basis, e.g., second or minute. If the
allocations are randomized or of unknown ordering, compute it again,
repeat over and over.

Sure, I can compute the mimimum storage size needed for any time, by
simply adding the sizes of all block active at that time. But because
of fragmentation as a result of numerous allocations and releases you
will probably need more than that minimum.

A computer program can easily brute-force or shotgun test 1000
allocations, and it can do this repeatedly, e.g., billions of times.
This can also be done without actually allocating memory, since you
know the allocations sizes in advance. So, I'm not sure what you're
getting at here as to why you can't try all the combinations, as you can
definitely easily compute all the potential combinations. Even if
you'd rather actually test all the allocations, there has to be a
computer out there somewhere where you can try out all the combinations.

Trying out all combinations and find the one with minimum storage
requirements isn't possible in practice if you have say 1000
allocation requests, since compute time grows exponetially. Probably
even the fastest computer won't give you an answer in your life-time.
That's what I meant by my (arbitrarily) chosen limit of a few seconds
or a minute. I'd like a good (not perfect, seems impossible) solution
in some "practical" time on a PC-class computer.


Steve

[Rod Pemberton]

On Fri, 9 Apr 2021 16:20:30 +0200

Post by Steve Keller

You haven't responded to anyone since you posted. Are you still here?

Yes, I'm still here. I posted to comp.os.misc and alt.os.development
and waited for replies but didn't get any. In alt.os.development I
didn't even see my own posting so I checked with Google groups where
I'm reading this. My newsfeed doesn't seem to have alt.os.development
although I'm sure it had until recently.

Since you're familiar with Usenet, I'll assume you're familiar with
Google searches and have found and read the search result articles on
Stackoverflow, IEEE.org, Javaer101, UCLA, etc for "offline dynamic
storage allocation". In fact, the one on Stackoverflow from 6 years ago
seems to use the same verbiage and expressions as you. So does the
post on Javaer101.

Really, all I can do on this - without learning exactly what offline
DSA is, without constructing an algorithm, and without writing some
code to test it - is to point you to Google search or to search-able
archives of scientific papers, e.g., arXiv, Academia, CiteSeerX, Jstor,
ResearchGate, Semantic Scholar, etc.

I looked at one .pdf on the topic, and it seems they have tested an
algorithm for "a highly predictable, low overhead and yet dynamic,
memory allocation strategy for embedded systems with scratch-pad
memory". See "Compiler-Decided Dynamic Memory Allocation for
Scratch-Pad Based Embedded Systems" by Sumesh Udayakumaran, Rajeev
Barua.

Obviously, you've been focusing on this method or idea for some time
now and for a particular reason. So, what is the "obsession" with
"offline dynamic storage allocation" instead of some other technique?