How to predict the behavior of a system based on previous behavior

Question

I am looking for an algorithm that, based on the previous behavior of a system, predicts the future behavior.

I'm building a parallel memory allocator that has a public list of empty blocks. Each thread, when it needs, can take blocks from this list and allocate from them. The blocks are grouped in bins, depending on the allocation size (8, 12, 16 bytes... to about 4 KB). When a block becomes empty it is returned to the global list (with a synchronization overhead, of course). If no block is empty in a bin, it tries to "steal" locations from blocks in other bins before getting a new empty one.

Now there are two situations that concern me:

1. It may be possible that a thread allocates, lets say, memory that takes 5 blocks. After a while, it deallocates all this memory (and the blocks go to the global list). Immediately after, it allocates again 5 blocks, deallocates them, and so on. In this case, it would be wise to keep those 5 blocks all the time and don't return them to the global list, as it avoids the synchronization overhead.
2. If the allocator "steals" a location, it uses memory that would otherwise be wasted. But there are cases when this is going to increase the memory use.

I want to make a system that can observe this kind of patterns, and save the results somewhere so that the next time, the allocators knows what is wise to do and what not (keep at least N blocks in bin X, don't "steal" from bin Y).

Are genetic algorithms of any use? I don't know anything about them, but I heard they are good at machine learning, or something like this.

Thanks in advance!

Answer 1

I believe artificial neural networks are more appropriate to your task than genetic algorithms.

Check out these SO questions:

• When to use Genetic Algorithms and when to use Neural Networks?
• What are some good resources for learning about Neural Networks?

Answer 2

There are quite a few articles about proper implementation of memory managers. Most of these articles provide time measurements of what took what time, and why. So I would suggest you to take a look at what has already been done in this field. There are quite a few interesting ideas, many of which work well, and have wise and interesting concepts.

Although machine learning techniques are interesting to learn and know, I suspect that they will not give good results in real life. The reason is the large overhead they need in order to work. I believe more in methods closer to the way modern caches work - different variations on the least recently used method.

So in your example, I would do the following:

• Use a "cache" made of different sizes, and use it. This means saving a minimal size that is not returned to the system, and used for 'reuse'.
• The cache size could be determined dynamically: Check how often new memory is allocated and de-allocated for this thread. If threshing is made too often (often could be a parameter of time), the cache size is increased.
• Regarding stealing: the cache size could be non-stealable, solving problems of caching and threshing.

The main drawback of this method is the memory overhead. It too can be reduced if cache sizes are reduced (as it is a trade-off in your case).

Answer 3

Maybe you should try count the number of allocations and deallocations of blocks of specific size for specific thread, say, per second. If counters are high and number of allocations is about the same as number of deallocations you may try to ignore that amount of deallocations in next second.

Answer 4

If you're going to have free blocks of sizes 2, 4, 8, 16, etc, then your threads should also request memory in sizes 2, 4, 8, 16, etc. Request whatever you need rounded up to the nearest power of two.